基于內(nèi)容的推薦算法在交通信號(hào)配時(shí)中的應(yīng)用*

□ 黃霖霖，屈嘉宸，張夢(mèng)瑤，林 麗

(南京林業(yè)大學(xué) 汽車(chē)與交通工程學(xué)院，江蘇 南京 210037)

交通信號(hào)控制經(jīng)過(guò)近幾十年的部署和發(fā)展，使得交通安全與效率有了極大的提升。但是傳統(tǒng)的固定配時(shí)方法使交叉口的延誤時(shí)間大幅上升，損害了人、貨運(yùn)輸?shù)谋憬菪砸?，提高了交通參與者的出行成本以及公路運(yùn)輸?shù)臅r(shí)間成本[1]。

交通信號(hào)控制可以追溯到20世紀(jì)中期Webster法的提出。由于Webster法易于實(shí)施且效果顯著，常被選為交通信號(hào)控制的設(shè)計(jì)基礎(chǔ)。近年來(lái)，有研究者提出利用數(shù)據(jù)挖掘和智慧交通系統(tǒng)技術(shù)改進(jìn)交通信號(hào)控制系統(tǒng)。ZHAO GAO[2]考慮到交通系統(tǒng)中存在大量的無(wú)法完全統(tǒng)計(jì)和量化的不確定性因素，在交通系統(tǒng)中應(yīng)用了潛在因子模型。通過(guò)訓(xùn)練大量歷史數(shù)據(jù)，利用潛在因子模型成功地處理了在數(shù)學(xué)中不能精確建模的不確定性因素。方丹麗提出以交通狀態(tài)對(duì)相應(yīng)配時(shí)方案的評(píng)級(jí)由智慧交通系統(tǒng)生成相應(yīng)信號(hào)控制方案[3]。通過(guò)實(shí)際計(jì)算模擬，預(yù)測(cè)了交叉口與配時(shí)方案的匹配程度。結(jié)果顯示通過(guò)訓(xùn)練數(shù)據(jù)提供信號(hào)配時(shí)的方法在降低延誤方面優(yōu)于經(jīng)典的Webster方法。

上述信控方法必須依賴大量良好的歷史數(shù)據(jù)，而這些數(shù)據(jù)在現(xiàn)實(shí)中通常并不容易獲得，因?yàn)榻煌ㄏ到y(tǒng)的動(dòng)態(tài)性使得數(shù)據(jù)信息容量超過(guò)傳統(tǒng)配時(shí)方法的處理能力[4]。因此對(duì)于配時(shí)方案的選擇，本文應(yīng)用基于內(nèi)容的推薦算法，基于內(nèi)容的推薦(content based recommendation)根據(jù)內(nèi)容的相似度向用戶推薦相似度高的物品或信息，被認(rèn)為是處理信息過(guò)載問(wèn)題最有效的工具之一[5]。在交通信號(hào)配時(shí)中應(yīng)用此算法的過(guò)程為：以路況為用戶，配時(shí)方案為推薦內(nèi)容，延誤為評(píng)級(jí)，根據(jù)路況的特點(diǎn)，通過(guò)計(jì)算找到相似度最高的k個(gè)的路況作為類(lèi)別標(biāo)簽，根據(jù)相似度高低對(duì)各類(lèi)別加權(quán)，然后使用KNN (k-Nearest neighbour )算法對(duì)各個(gè)未使用的配時(shí)方案進(jìn)行分類(lèi)并預(yù)測(cè)其延誤等級(jí)，最終根據(jù)權(quán)重從k個(gè)分類(lèi)中選取延誤最小前n個(gè)配時(shí)方案構(gòu)成推薦列表并將其推薦給路況。

使用基于內(nèi)容的推薦算法來(lái)預(yù)測(cè)交通狀況與配時(shí)方案的匹配程度時(shí)，有以下優(yōu)點(diǎn):

①它提供了類(lèi)似于無(wú)模型自適應(yīng)控制的思想。它不僅可以屏蔽建模過(guò)程中的不確定性細(xì)節(jié)，而且可以保證潛在因素的作用不被忽略;

②交通信號(hào)控制系統(tǒng)可以讓它執(zhí)行離線訓(xùn)練，然后結(jié)合當(dāng)前的交通狀況在線運(yùn)行。如此可以保證預(yù)測(cè)精度和實(shí)時(shí)性;

③它不需要依賴于大量的數(shù)據(jù)。同時(shí)考慮了道路狀況的特點(diǎn)，可以根據(jù)需要進(jìn)行擴(kuò)充。

總的來(lái)說(shuō)，基于內(nèi)容的推薦算法是對(duì)交通信號(hào)控制中推薦內(nèi)容的補(bǔ)充和優(yōu)化。

1 信號(hào)配時(shí)推薦算法介紹

應(yīng)用基于內(nèi)容的推薦算法，為當(dāng)前交通狀況推薦以配時(shí)方案為內(nèi)容的有序推薦列表。為提高排序質(zhì)量，采用標(biāo)準(zhǔn)化折扣增益(nDCG)作為推薦列表的評(píng)價(jià)指標(biāo)。

1.1 基于內(nèi)容的推薦算法步驟

推薦系統(tǒng)的首要目的是推薦最適合用戶需求的項(xiàng)目，在本文中，也就是尋找最合適的配時(shí)方案以滿足不同交通狀況下的交通需求。應(yīng)用基于內(nèi)容的推薦算法，即采用交通狀況中共同特性對(duì)交通狀況進(jìn)行刻畫(huà)，根據(jù)特性計(jì)算兩種交通狀況的相似度，然后，從幾種最相似的交通狀況下配時(shí)方案中選出最佳的配時(shí)方案。

在基于內(nèi)容的推薦算法中選擇不同的交通狀況作為用戶，并為其配置相應(yīng)的OD(origin-destination)矩陣。然后選擇一些配時(shí)方案作為推薦項(xiàng)目。同時(shí)，記錄下每一對(duì)交通狀況和配時(shí)方案下的延誤時(shí)間作為評(píng)級(jí)依據(jù)。因此，將生成一個(gè)由延誤時(shí)間填充的用戶-對(duì)象矩陣。另外，對(duì)于延誤數(shù)據(jù)應(yīng)該進(jìn)行一些預(yù)處理步驟，使它們更適合評(píng)級(jí)。

應(yīng)用基于內(nèi)容的推薦算法推薦最佳配時(shí)方案的流程描述如下:

步驟1:對(duì)原始延誤數(shù)據(jù)進(jìn)行預(yù)處理。繼而產(chǎn)生一個(gè)標(biāo)準(zhǔn)的評(píng)級(jí)矩陣。

步驟2:將每?jī)蓚€(gè)區(qū)域行駛的車(chē)輛數(shù)量作為所有交通狀況的共同特性。然后將交通狀況a和b用向量(a1,a2,…,ai,…) 和(b1,b2,…,bi,…) 表示。

步驟3：使用歐氏距離計(jì)算任意兩個(gè)交通狀況間的相似度[6]。交通狀況a與交通狀況b的相似度計(jì)算，用公式(1)表示如下：

(1)

步驟4:當(dāng)某些特定交通狀況出現(xiàn)時(shí)(通常在每周期結(jié)束時(shí)檢測(cè))，KNN算法將根據(jù)步驟3生成的相似度，選擇k個(gè)最相似的交通狀況作為類(lèi)別標(biāo)簽對(duì)其他未使用的配時(shí)方案進(jìn)行分類(lèi)并預(yù)測(cè)其在此交通狀況下的延誤等級(jí)。應(yīng)用KNN算法，用于預(yù)測(cè)交通狀況a對(duì)配時(shí)方案c的評(píng)級(jí)的公式(2)如下：

(2)

公式(2)中rb,c是交通狀況b給予配時(shí)方案c的評(píng)級(jí)，它是延誤的倒數(shù)。

步驟5:在步驟4之后，得到了一個(gè)有序的推薦列表(c1,c2,…,ci,ci+1,…)。其中ci是第i個(gè)最合適的配時(shí)方案，優(yōu)于ci+1。

步驟6:在Paramics軟件中驗(yàn)證獲得的配時(shí)方案。根據(jù)Paramics軟件仿真的結(jié)果，得到另一個(gè)有序列表(c1’,c2’,…,ci’,ci+1’,…)。

步驟7:比較列表(c1,c2,…,ci,ci+1,…)和列表(c1’,c2’,…,ci’,ci+1’,…)，評(píng)價(jià)預(yù)測(cè)的有效性。

1.2 推薦列表的評(píng)價(jià)指標(biāo)

通過(guò)預(yù)測(cè)當(dāng)前路況與未使用的配時(shí)方案的匹配程度獲得推薦方案的關(guān)鍵在于尋找?guī)讉€(gè)最合適的配時(shí)方案，構(gòu)成一個(gè)有序列表。在一個(gè)高質(zhì)量的有序推薦列表中，相似度越高，配時(shí)方案在列表中的位置就應(yīng)該越靠前。同時(shí)，列表中的所有配時(shí)方案都應(yīng)盡可能地與當(dāng)前的路況匹配。因此采用nDCG(標(biāo)準(zhǔn)化折扣累積增益)[7]作為評(píng)價(jià)指標(biāo)，定義如下:

(3)

其中DCGP代表推薦列表中處于第p位的對(duì)象的折扣累積增益。IDCGP(理想化折扣累積增益)是第p位對(duì)象的最大折扣累積增益。nDCGP是標(biāo)準(zhǔn)化折扣累積增益。

DCG用于分級(jí)相關(guān)性的度量，根據(jù)其在結(jié)果列表中的位置來(lái)度量返回結(jié)果的有效性或增益。以此為推薦列表中的對(duì)象排序[8]。其在位置P處的定義如下：

(4)

其中reli為列表中位置i處結(jié)果的分級(jí)相關(guān)性。

對(duì)于選定的p值，每個(gè)位置的累積增益應(yīng)該進(jìn)行歸一化。通過(guò)與理想化折扣累積增益IDCG對(duì)比?？梢垣@得所有推薦對(duì)象對(duì)應(yīng)的nDCG值。

2 推薦方法Paramics仿真

2.1 交叉路口建模

推薦方案基于各種交通狀況參數(shù)，如延誤時(shí)間等參數(shù)進(jìn)行制定。為了便于理解，引入如圖1所示的一個(gè)典型的交叉路口。交叉路口由向量I=(r1,r2,…,rm)表示，m為連接到交叉口的道路數(shù)，在圖1中m=4，ri是一個(gè)5維向量,表示為ri=(l1,l2,l3,l4,l5)，l1代表U型轉(zhuǎn)彎車(chē)道，l2代表左轉(zhuǎn)車(chē)道，l3代表直行車(chē)道，l4代表直行右轉(zhuǎn)車(chē)道，l5代表右轉(zhuǎn)車(chē)道。它們都是依次表示的，lj的數(shù)值代表每種車(chē)道的數(shù)量。例如,ri=(0,1,2,0,1)表示有1條左轉(zhuǎn)車(chē)道，2條直車(chē)道和1條右轉(zhuǎn)車(chē)道。假定車(chē)輛在轉(zhuǎn)彎時(shí)會(huì)沿著給定的路徑行駛。

圖1 實(shí)驗(yàn)交叉路口設(shè)置

2.2 初始數(shù)據(jù)設(shè)置

在2.1節(jié)圖1屬于有4條道路交匯的典型單交叉口仿真路網(wǎng)，即I=(r1,r2,r3,r4)。每路有3條車(chē)道，1條左轉(zhuǎn)車(chē)道，1條直行車(chē)道和1條右轉(zhuǎn)車(chē)道，即r1=r2=r3=r4=(0,1,1,0,1)。在Paramics中，時(shí)間步長(zhǎng)設(shè)置為0.5s，而仿真持續(xù)時(shí)間為1h。每條車(chē)道的長(zhǎng)度為1000m。

圖2 實(shí)驗(yàn)相位設(shè)置

圖2依序列舉了實(shí)驗(yàn)采用的交叉路口信號(hào)燈的四種相位。在每個(gè)配時(shí)方案中，每個(gè)相位的黃燈時(shí)間被設(shè)置為3s。另外，在每個(gè)相位中總是允許右轉(zhuǎn)。

在實(shí)驗(yàn)中使用了40組不同OD矩陣代表40種不同的交通需求，由此創(chuàng)建了40種不同的交通狀況。以及使用了40個(gè)固定的配時(shí)方案，這些配時(shí)周期長(zhǎng)度從88s到122s不等。配時(shí)方案的范圍覆蓋了大多數(shù)交通情況的范圍。車(chē)輛數(shù)從120到23400不等。

2.3 實(shí)驗(yàn)仿真過(guò)程

首先將3個(gè)OD矩陣與3個(gè)配時(shí)方案進(jìn)行交叉實(shí)驗(yàn)，并收集這9個(gè)實(shí)驗(yàn)的延誤數(shù)據(jù)。在Paramics軟件中進(jìn)行仿真的3個(gè)OD矩陣吸發(fā)量設(shè)置見(jiàn)表1，表2和表3中的OD 1,OD 2和OD 3。其中，OD 1設(shè)置區(qū)1和區(qū)2的出行量多于區(qū)3和區(qū)4，OD 2設(shè)置第3區(qū)和第4區(qū)的出行量多于區(qū)1和區(qū)2。OD 3設(shè)置每個(gè)區(qū)的出行量相等。

表1 實(shí)驗(yàn)中的OD 1數(shù)據(jù)

表2 實(shí)驗(yàn)中的OD 2數(shù)據(jù)

表3 實(shí)驗(yàn)中的OD3 數(shù)據(jù)

表4 實(shí)驗(yàn)中的3個(gè)配時(shí)方案

表4中給出了3個(gè)配時(shí)方案，在每個(gè)配時(shí)方案中，周期時(shí)長(zhǎng)設(shè)置為100s。在配時(shí)方案1中，相位1和相位2的時(shí)長(zhǎng)比相位3和相位4長(zhǎng)6s，而在配時(shí)方案2中相位3的時(shí)長(zhǎng)和相位4比相位1和相位2長(zhǎng)6s。在配時(shí)方案3中各個(gè)相位的時(shí)長(zhǎng)相等。

表5 實(shí)驗(yàn)中獲得的延誤時(shí)間

從9組實(shí)驗(yàn)中得到的延誤數(shù)據(jù)可以轉(zhuǎn)換成一個(gè)延誤矩陣，列于表5。延誤時(shí)間采用的單位是s。

表6 實(shí)驗(yàn)中的OD 4數(shù)據(jù)

除了3個(gè)OD用以模擬交通狀況，添加OD4預(yù)測(cè)該OD量在3個(gè)配時(shí)方案下的匹配度。OD4的設(shè)置見(jiàn)表6。

然后采用基于內(nèi)容的推薦算法計(jì)算OD4與其它三種OD矩陣的相似度，列于表7。

表7 OD 4與其他三種OD的相似度

利用上述數(shù)據(jù)，通過(guò)第1節(jié)所述的方法預(yù)測(cè)OD 4和3個(gè)配時(shí)方案之間的匹配程度。預(yù)測(cè)結(jié)果表明，OD 3與OD 4最為匹配。而Paramics軟件仿真的結(jié)果表明，配時(shí)方案3是最匹配的，而配時(shí)方案2是最不匹配的。這與預(yù)測(cè)結(jié)果相同。

2.4 全交通情況仿真實(shí)驗(yàn)

實(shí)際情況中交通情景更為復(fù)雜，需要通過(guò)稀疏延誤矩陣預(yù)測(cè)交通狀況與其未使用的配時(shí)方案之間的匹配程度。

首先，通過(guò)Paramics軟件對(duì)40個(gè)OD矩陣搭配40個(gè)配時(shí)方案進(jìn)行仿真，得到延誤時(shí)間的稀疏矩陣作為評(píng)級(jí)標(biāo)準(zhǔn)，其稀疏度為75%。然后，向每個(gè)OD矩陣推薦了6個(gè)未使用的配時(shí)方案。得到有序推薦列表Li=(c1,c2,c3,c4,c5,c6),其中Li代表第i個(gè)OD的列表。此外，在Paramics軟件中，還將每個(gè)OD矩陣搭配其Li中的6個(gè)推薦的配時(shí)方案進(jìn)行了仿真。然后根據(jù)延誤數(shù)據(jù)得到每個(gè)OD的理想順序列表Li，=(c1’，c2’,c3’,c4’,c5’,c6’)。假定ODi與列表Li中cj(其中j=1,2,3,4,5,6)的相似度依次是5 4 3 2 1 0。然后計(jì)算每個(gè)OD推薦列表Li的nDCG值，結(jié)果見(jiàn)圖3:

圖3 40個(gè)交通狀況的nDCG@6

從圖3中不難看出基于內(nèi)容的推薦算法表現(xiàn)出了良好的性能，所有OD矩陣的nDCG值均大于0.6。且多數(shù)趨近于1。這表明了基于內(nèi)容的推薦算法的有效性。

3 推薦配時(shí)方法與Webster固定配時(shí)方法的比較

經(jīng)過(guò)排序后，每個(gè)Li中的第一項(xiàng)c1都對(duì)應(yīng)于ODi中最好的未使用的配時(shí)方案。為了獲得最終的最佳配時(shí)方案Cbest，需要將c1和使用的配時(shí)方案進(jìn)行比較。

為了比較基于內(nèi)容的推薦算法與Webster方法的性能，對(duì)上述的40個(gè)交通狀況采用Webster方法獲取對(duì)應(yīng)的配時(shí)方案。采用Webster方法進(jìn)行交叉口信號(hào)配時(shí)時(shí)，需設(shè)定的相關(guān)參數(shù)見(jiàn)表8，其中AR為全紅時(shí)間，以s為單位，l為每相位平均損失時(shí)間(以s為單位，不包括全紅時(shí)期和黃燈時(shí)期)，S為交叉口飽和交通量,用擴(kuò)展為一小時(shí)的飽和流率來(lái)表示，單位采用Vehs/h。

表8 Webster方法的參數(shù)

通過(guò)用近似解法，可以得到Webster配時(shí)方法下最佳周期時(shí)長(zhǎng)為:

(5)

式中：L為每個(gè)周期的總損失時(shí)間，s；l為起動(dòng)損失時(shí)間，s；A為黃燈時(shí)間，s；I為綠燈間隔時(shí)間，s；Y為交叉口交通流量比。

將40個(gè)OD矩陣搭配對(duì)應(yīng)最優(yōu)周期Cbest得到的延誤時(shí)間與搭配Webster方法得到的配時(shí)方案同時(shí)進(jìn)行仿真，并將得到的延誤時(shí)間進(jìn)行比較，數(shù)據(jù)見(jiàn)圖4。

圖4 延誤時(shí)間比較

圖4中交通狀況1-40是對(duì)應(yīng)交通流從小到大的順序，與Webster方法相比，基于內(nèi)容的推薦算法的推薦的配時(shí)方案總體延誤時(shí)間要小得多。此外，當(dāng)處于第9至第20交通狀況之間時(shí)，基于內(nèi)容的推薦算法推薦的配時(shí)方案相比webster方法的得到的配時(shí)方案，其延誤明顯更低。盡管如此，在最初的5到8的交通狀況中，兩種方法產(chǎn)生的延誤并沒(méi)有較大的差別。當(dāng)交通流量較小時(shí)，使用基于內(nèi)容的推薦算法推薦的配時(shí)方案與webster方法推薦的配時(shí)方案延誤并沒(méi)有太大差距。同時(shí)，當(dāng)交通流量過(guò)大時(shí)，延誤時(shí)間會(huì)在小范圍內(nèi)波動(dòng)。另外，當(dāng)交通狀況為1-4時(shí)，無(wú)法應(yīng)用Webster方法配時(shí)。因?yàn)閃ebster方法應(yīng)用時(shí)交叉口交通流量比Y應(yīng)該保持在0.4到0.9之間。在這些低OD量情況下，基于內(nèi)容的推薦算法表現(xiàn)良好。

4 結(jié)束語(yǔ)

本文的靈感來(lái)自于推薦系統(tǒng)的思想，通過(guò)基于內(nèi)容的推薦算法，研究不同配時(shí)方案與各交通狀況之間的匹配度高低。實(shí)驗(yàn)結(jié)果表明，反饋?lái)樞蛲扑]列表與理想序列列表有很高的相關(guān)性，證明了該方法的有效性。然后，將基于內(nèi)容的推薦算法與傳統(tǒng)Webster進(jìn)行比較，發(fā)現(xiàn)基于內(nèi)容的推薦算法在降低運(yùn)輸過(guò)程中交叉口等待延誤方面優(yōu)于Webster方法。未來(lái)的研究將考慮更多影響交通環(huán)境和代表交通狀況的因素以及將基于內(nèi)容的推薦算法與協(xié)同過(guò)濾方法相結(jié)合。