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

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

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

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

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

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

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

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

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

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

1 信號配時推薦算法介紹

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

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

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

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

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

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

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

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

(1)

步驟4:當(dāng)某些特定交通狀況出現(xiàn)時(通常在每周期結(jié)束時檢測)，KNN算法將根據(jù)步驟3生成的相似度，選擇k個最相似的交通狀況作為類別標簽對其他未使用的配時方案進行分類并預(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軟件中驗證獲得的配時方案。根據(jù)Paramics軟件仿真的結(jié)果，得到另一個有序列表(c1’,c2’,…,ci’,ci+1’,…)。

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

1.2 推薦列表的評價指標

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

(3)

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

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

(4)

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

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

2 推薦方法Paramics仿真

2.1 交叉路口建模

推薦方案基于各種交通狀況參數(shù)，如延誤時間等參數(shù)進行制定。為了便于理解，引入如圖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è)置

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è)置

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

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

2.3 實驗仿真過程

首先將3個OD矩陣與3個配時方案進行交叉實驗，并收集這9個實驗的延誤數(shù)據(jù)。在Paramics軟件中進行仿真的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 實驗中的OD 1數(shù)據(jù)

表2 實驗中的OD 2數(shù)據(jù)

表3 實驗中的OD3 數(shù)據(jù)

表4 實驗中的3個配時方案

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

表5 實驗中獲得的延誤時間

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

表6 實驗中的OD 4數(shù)據(jù)

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

然后采用基于內(nèi)容的推薦算法計算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 全交通情況仿真實驗

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

首先，通過Paramics軟件對40個OD矩陣搭配40個配時方案進行仿真，得到延誤時間的稀疏矩陣作為評級標準，其稀疏度為75%。然后，向每個OD矩陣推薦了6個未使用的配時方案。得到有序推薦列表Li=(c1,c2,c3,c4,c5,c6),其中Li代表第i個OD的列表。此外，在Paramics軟件中，還將每個OD矩陣搭配其Li中的6個推薦的配時方案進行了仿真。然后根據(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。然后計算每個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中的第一項c1都對應(yīng)于ODi中最好的未使用的配時方案。為了獲得最終的最佳配時方案Cbest，需要將c1和使用的配時方案進行比較。

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

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

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

(5)

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

將40個OD矩陣搭配對應(yīng)最優(yōu)周期Cbest得到的延誤時間與搭配Webster方法得到的配時方案同時進行仿真，并將得到的延誤時間進行比較，數(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方法配時。因為Webster方法應(yīng)用時交叉口交通流量比Y應(yīng)該保持在0.4到0.9之間。在這些低OD量情況下，基于內(nèi)容的推薦算法表現(xiàn)良好。

4 結(jié)束語

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