□ 黃霖霖，屈嘉宸，張夢瑤，林 麗

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

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

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

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

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

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

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

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

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

1 信號配時推薦算法介紹

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

1.2 推薦列表的評價指標(biāo)

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

(3)

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

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

(4)

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

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

2 推薦方法Paramics仿真

2.1 交叉路口建模

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

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

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

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

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

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

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

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

首先將3個OD矩陣與3個配時方案進(jìn)行交叉實(shí)驗(yàn)，并收集這9個實(shí)驗(yàn)的延誤數(shù)據(jù)。在Paramics軟件中進(jìn)行仿真的3個OD矩陣吸發(fā)量設(shè)置見表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è)置每個區(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個配時方案

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

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

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

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

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

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

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

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

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

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

首先，通過Paramics軟件對40個OD矩陣搭配40個配時方案進(jìn)行仿真，得到延誤時間的稀疏矩陣作為評級標(biāo)準(zhǔn)，其稀疏度為75%。然后，向每個OD矩陣推薦了6個未使用的配時方案。得到有序推薦列表Li=(c1,c2,c3,c4,c5,c6),其中Li代表第i個OD的列表。此外，在Paramics軟件中，還將每個OD矩陣搭配其Li中的6個推薦的配時方案進(jìn)行了仿真。然后根據(jù)延誤數(shù)據(jù)得到每個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ì)算每個OD推薦列表Li的nDCG值，結(jié)果見圖3:

圖3 40個交通狀況的nDCG@6

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

3 推薦配時方法與Webster固定配時方法的比較

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

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

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

通過用近似解法，可以得到Webster配時方法下最佳周期時長為:

(5)

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

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

圖4 延誤時間比較

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

4 結(jié)束語

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