城市道路交通瓶頸識(shí)別算法研究

馮嘉松,楊國(guó)平,徐啟祿，羅 強(qiáng),帥 祥

(1.成都信息工程大學(xué) 軟件工程學(xué)院， 成都 610225;2.青島地鐵集團(tuán)有限公司， 山東 青島 266100)

0 引言

隨著城市化發(fā)展，城市居住人口呈現(xiàn)爆炸式增長(zhǎng)，給城市交通帶來(lái)了巨大壓力，交通擁堵已經(jīng)是所有現(xiàn)代化大城市難以解決的嚴(yán)重問(wèn)題[1]。交通擁堵不僅影響人們?nèi)粘３鲂校档徒煌ɑA(chǔ)設(shè)施的工作效率，同時(shí)也對(duì)生態(tài)環(huán)境造成了一定程度的破壞，進(jìn)一步導(dǎo)致了各種社會(huì)和經(jīng)濟(jì)問(wèn)題[2]。

城市交通壓力主要來(lái)自于交通瓶頸，分析城市道路交通瓶頸并進(jìn)一步得到擁堵擴(kuò)散趨勢(shì)，可以為改善城市擁堵提供技術(shù)支持。通常情況下，在瓶頸處進(jìn)行道路拓寬、信號(hào)燈優(yōu)化、道路封禁等措施都可以緩解交通擁堵，降低城市車(chē)輛通行的壓力[3-4]。

在以往的研究中，大多數(shù)學(xué)者將目光著眼于高速公路上[5]，因其具有結(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，然而在實(shí)際生活中，城市道路網(wǎng)絡(luò)中的瓶頸識(shí)別更加迫在眉睫。首先，城市道路網(wǎng)絡(luò)錯(cuò)綜復(fù)雜，對(duì)路段因果關(guān)系的分析更加困難。其次，城市道路網(wǎng)絡(luò)中可能發(fā)生的意外情況更多，對(duì)模型如何去除這些“臟數(shù)據(jù)”要求更高。最后，高速公路上幾乎沒(méi)有信號(hào)燈，但城市道路網(wǎng)絡(luò)中有大量的交通信號(hào)燈，對(duì)交通路網(wǎng)中車(chē)輛的通行能力影響很大。

現(xiàn)有的城市道路交通瓶頸識(shí)別技術(shù)大多關(guān)注擁堵路段本身，在考慮擁堵擴(kuò)散效應(yīng)上還有所空白，這樣找到的瓶頸并不是緩解擁堵的最優(yōu)解，很多時(shí)候?qū)矶碌木徑庑Ч跷ⅲ踔量赡苁清e(cuò)誤的瓶頸。為了正確的描述交通瓶頸，本文考慮以下2個(gè)主要特征：① 路段本身的擁堵程度；② 該路段的擁堵對(duì)周邊路段造成的影響。

為了填補(bǔ)目前該方向研究的空白，本文從擁堵擴(kuò)散的角度對(duì)交通瓶頸做了全新定義，提出了一種全新的交通瓶頸識(shí)別算法，能更有效地識(shí)別交通瓶頸。此外，本文使用SUMO仿真工具來(lái)驗(yàn)證所識(shí)別的交通瓶頸，并在實(shí)際場(chǎng)景中進(jìn)行了測(cè)試。具體來(lái)說(shuō)，本文貢獻(xiàn)如下：

1)基于擁堵路段本身及其對(duì)周邊路段的影響，對(duì)擁堵瓶頸做了全新的定義，可以更好地描述擁堵路段之間的因果關(guān)系，這樣得到的擁堵瓶頸更為準(zhǔn)確。

2)提出了一種全新的城市道路交通瓶頸識(shí)別算法，通過(guò)圖論法模擬城市交通路網(wǎng)，采用時(shí)間序列分析方法計(jì)算擁堵擴(kuò)散程度，最終將擁堵路段對(duì)城市交通造成的負(fù)面影響數(shù)值化，確定交通瓶頸。

3)使用SUMO仿真工具進(jìn)行瓶頸驗(yàn)證，并與現(xiàn)有的方法進(jìn)行橫向?qū)Ρ确治觯撟C了使用本文所提出的方法可以更有效地緩解交通擁堵，并在真實(shí)路網(wǎng)中也進(jìn)行了實(shí)證。

1 相關(guān)工作

1.1 基于路線引導(dǎo)的擁堵緩解方法

交通擁堵是現(xiàn)代社會(huì)一個(gè)長(zhǎng)期存在且日益嚴(yán)重的問(wèn)題。在路線引導(dǎo)方面，重新路由的方法被廣泛用于以更有組織的方式管理交通網(wǎng)絡(luò)，緩解道路網(wǎng)絡(luò)的擁堵。楊留輝等[6]將重路由的方法和信號(hào)燈的控制相結(jié)合，利用交通攝像頭采集的道路信息分析行人與車(chē)輛的運(yùn)動(dòng)狀態(tài)，動(dòng)態(tài)優(yōu)化信號(hào)燈配時(shí)方案，從而加快行人和車(chē)輛通過(guò)路口的時(shí)間。實(shí)驗(yàn)證明，該方法可以有效增加人們出行的效率，降低交通擁堵發(fā)生的概率。Huo等[7]同樣提出了一種基于聚類(lèi)的交通擁堵避免混合重新路由系統(tǒng)(clustering-based hybrid re-routing system for traffic congestion avoidance,CHRT)。CHRT開(kāi)發(fā)了一種多層混合架構(gòu)，中央服務(wù)器訪問(wèn)流量的全局視圖，分布式部分由分成集群的車(chē)輛組成，以減少延遲和通信開(kāi)銷(xiāo)。然后，提出了一種基于聚類(lèi)的優(yōu)先級(jí)機(jī)制，基于實(shí)時(shí)交通信息設(shè)置聚類(lèi)優(yōu)先級(jí)，避免二次擁堵。Cao等[8-9]綜合考慮到達(dá)時(shí)間和總旅行時(shí)間，先后提出了一種分散的基于多主體的路線引導(dǎo)方法和半分散的基于多智能體的路線引導(dǎo)方法。

1.2 基于路段自身?yè)矶鲁潭鹊钠款i識(shí)別技術(shù)

路線引導(dǎo)方法是在交通擁堵發(fā)生后用于緩解交通壓力的手段，需要在多個(gè)路口應(yīng)用交通控制策略，在一定程度上可以緩解交通擁堵，但無(wú)法從源頭處解決問(wèn)題。因此，先確定路網(wǎng)中導(dǎo)致?lián)矶碌年P(guān)鍵位置，再實(shí)行交通控制策略，可以達(dá)到事半功倍的效果。 Thilakshan等[10]利用眾包實(shí)時(shí)旅行時(shí)間數(shù)據(jù)識(shí)別瓶頸，這在收集和分析方面更為有效。Chen等[11]提出了一種基于梯度增強(qiáng)決策樹(shù)(gradient boosting decision trees,GBDT)的方法來(lái)識(shí)別道路網(wǎng)絡(luò)擁堵的根本原因，并使用不同類(lèi)型的解釋變量對(duì)影響因素進(jìn)行排序。以蘇福爾斯網(wǎng)絡(luò)為例，利用SUMO仿真工具對(duì)不同交通流量下不同交叉口和路段車(chē)道數(shù)的信號(hào)控制策略，對(duì)GBDT模型進(jìn)行訓(xùn)練和測(cè)試。

1.3 基于擁堵路段因果關(guān)系的瓶頸識(shí)別技術(shù)

作為分析城市交通瓶頸的新視角，路段的擁堵擴(kuò)散最近受到了廣泛關(guān)注。Nguyen等[12]引入了一種基于擁堵擴(kuò)散因果樹(shù)的算法，該算法演示了路段的擁堵擴(kuò)散趨勢(shì)，并基于擁堵的時(shí)間和空間信息估計(jì)了它們的擴(kuò)散概率。Tao等[13]采用一種基于細(xì)胞傳輸模型(cell transmission model,CTM)的交通流模型進(jìn)行復(fù)雜城市交通環(huán)境的模擬，建立了以鏈路為節(jié)點(diǎn)的鏈路狀態(tài)圖來(lái)分析節(jié)點(diǎn)之間的關(guān)系。在文獻(xiàn)[14]中也得出了同樣的結(jié)論，Yong等[14]通過(guò)網(wǎng)絡(luò)個(gè)體之間的協(xié)調(diào)博弈和交通擁塞過(guò)程中旅行者的決策行為，描述了交通網(wǎng)絡(luò)中擁塞的擴(kuò)散過(guò)程。實(shí)驗(yàn)表明，當(dāng)擁堵擴(kuò)散影響達(dá)到某一臨界閾值時(shí)，必須采取適當(dāng)措施控制局部交通擁堵的擴(kuò)散才不會(huì)發(fā)生大規(guī)模的交通擁堵。

基于上述研究，研究者們進(jìn)一步提出了一些直接或間接考慮擁堵擴(kuò)散的城市交通瓶頸識(shí)別方法。Ma等[15]提出了一種基于復(fù)雜網(wǎng)絡(luò)理論和用戶均衡模型(user equilibrium,UE)的關(guān)鍵瓶頸識(shí)別算法。該方法綜合考慮了部分路段失效前后網(wǎng)絡(luò)有效性和差旅成本的變化。然而，由于流量阻抗和網(wǎng)絡(luò)有效性難以計(jì)算，該方法識(shí)別出的瓶頸還有待驗(yàn)證。除此之外，該方法在識(shí)別瓶頸時(shí)沒(méi)有明確考慮路段之間的擁堵擴(kuò)散情況。Zhao等[16]從一個(gè)新角度來(lái)解決交通瓶頸識(shí)別問(wèn)題：交通流量影響(traffic flow influence,TFI)最大化。該模型基于交通擁堵擴(kuò)散(traffic congestion diffusion,TCD)模型并與TFI相結(jié)合，可以解釋交通狀況的變化，并捕捉道路網(wǎng)絡(luò)的動(dòng)態(tài)。然后將交通瓶頸識(shí)別問(wèn)題簡(jiǎn)化為T(mén)CD條件下的NP-hard影響最大化問(wèn)題。Li等[17]也研究了一種考慮擁堵擴(kuò)散效應(yīng)的瓶頸識(shí)別方法，但是路段之間的相關(guān)性分析不夠嚴(yán)謹(jǐn)，沒(méi)有考慮長(zhǎng)時(shí)間范圍內(nèi)的相關(guān)性，并且擁堵路段擴(kuò)散成本的定義和計(jì)算尚待完善。

2 瓶頸識(shí)別技術(shù)

2.1 瓶頸識(shí)別技術(shù)工作流

城市交通瓶頸識(shí)別模型的主要步驟包括：

1) 首先獲取城市交通路網(wǎng)以及某個(gè)長(zhǎng)時(shí)間段里的車(chē)輛運(yùn)行軌跡數(shù)據(jù)，對(duì)路網(wǎng)數(shù)據(jù)進(jìn)行圖論建模，使用仿真軟件還原實(shí)際交通狀況。

2) 然后分析各路段擁堵?tīng)顩r，進(jìn)一步分析擁堵路段之間的空間位置關(guān)系、因果關(guān)系，得到擁堵擴(kuò)散趨勢(shì)圖。

3) 最后分別計(jì)算擁堵成本和擴(kuò)散成本，量化了擁堵路段對(duì)交通路網(wǎng)產(chǎn)生的影響，從而確定交通瓶頸。

本文所提出的城市交通瓶頸識(shí)別模型需要一系列相應(yīng)輔助模塊共同協(xié)作，其工作原理如圖1所示。

圖1 瓶頸識(shí)別系統(tǒng)框架圖

2.2 擁堵路網(wǎng)識(shí)別

交通擁堵的性質(zhì)通常情況下分為常發(fā)性和偶發(fā)性，城市道路的偶發(fā)性擁堵主要是由事故、特殊事件以及極端天氣造成的，相比之下，偶發(fā)性的識(shí)別比較困難，通常被視為一種模式的識(shí)別[18-19]，并使用許多分類(lèi)器來(lái)確定擁堵的位置和嚴(yán)重程度。本文關(guān)注的重點(diǎn)是常發(fā)性擁堵瓶頸識(shí)別。

2.2.1道路狀態(tài)識(shí)別

車(chē)輛行駛速度作為評(píng)估道路狀況的重要指標(biāo)，目前相關(guān)研究已經(jīng)沿多個(gè)方向進(jìn)行。現(xiàn)在關(guān)于機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)的技術(shù)越來(lái)越成熟，在與交通有關(guān)的預(yù)測(cè)中也使用了許多常用的神經(jīng)網(wǎng)絡(luò)，如循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network,RNN)[20]和Elman神經(jīng)網(wǎng)絡(luò)[21]，這些方法大多利用車(chē)輛平均行駛速度來(lái)對(duì)路段狀態(tài)進(jìn)行分類(lèi)。在本文中，為了識(shí)別道路是否擁堵，以道路車(chē)道占用率以及停滯車(chē)輛長(zhǎng)度作為指標(biāo)。相比之下，這樣比利用車(chē)輛平均行駛速度作為指標(biāo)更能表述路段擁堵?tīng)顟B(tài)。具體來(lái)說(shuō)，假設(shè)一條路段上車(chē)輛的總長(zhǎng)度與路段總長(zhǎng)度之比為L(zhǎng)en%，路段上停滯車(chē)輛數(shù)與總車(chē)輛數(shù)之比為Amo%，如果Len%大于M%并且Amo%大于N%，則判定路段在該時(shí)刻為擁堵?tīng)顟B(tài)。其中M和N的值根據(jù)具體城市而定，通常情況下，M∈[50,80]，N∈[40,70]，具體判別標(biāo)準(zhǔn)如表1所示。

表1 擁堵?tīng)顟B(tài)判別標(biāo)準(zhǔn)

定義1(車(chē)輛軌跡數(shù)據(jù))：車(chē)輛軌跡數(shù)據(jù)定義為T(mén)rai={lane1,lane2,…,lanen}，Trai為車(chē)輛i的軌跡，lanen為路段編號(hào)，n不超過(guò)路網(wǎng)中路段總數(shù)。

利用車(chē)輛軌跡數(shù)據(jù)和相應(yīng)地圖數(shù)據(jù)，通過(guò)仿真軟件可以還原實(shí)際的交通狀況，分析出路網(wǎng)中擁堵路段集合，進(jìn)一步結(jié)合路網(wǎng)拓?fù)浣Y(jié)構(gòu)可以得到擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)。

傳統(tǒng)方法和對(duì)偶方法是提取復(fù)雜道路網(wǎng)絡(luò)的2種常用方法。傳統(tǒng)方法將交叉口視為節(jié)點(diǎn)，將路段視為節(jié)點(diǎn)之間的邊，該方法可以反映城市路網(wǎng)的物理結(jié)構(gòu)。采用對(duì)偶方法，路段由節(jié)點(diǎn)表示，相鄰路段的連接用邊表示[22]。本文重點(diǎn)關(guān)注的對(duì)象是路段，分析擁堵路段之間的因果關(guān)系。因此，本文采用對(duì)偶方法將城市道路網(wǎng)表示為一個(gè)有向圖網(wǎng)絡(luò)。具體定義如下。

定義2(路網(wǎng)拓?fù)浣Y(jié)構(gòu))：路網(wǎng)拓?fù)浣Y(jié)構(gòu)表示為一個(gè)圖Map=(V,E)，V是頂點(diǎn)集，由所有路段組成，E是邊集，由路段之間車(chē)輛行駛方向組成，每一條邊就是一個(gè)點(diǎn)對(duì)(u,w)，其中u、w∈V。

2.2.2擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)

路段之間的擁堵往往不是獨(dú)立存在的，它們互相影響，相互牽制，當(dāng)一條路段發(fā)生擁堵后，周?chē)范味紩?huì)受到影響，導(dǎo)致其通行能力下降。為了清楚地描述擁堵路段之間的聯(lián)系，需要構(gòu)建擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)，擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)描述了擁堵路段之間可能的因果關(guān)系。

定義3(擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu))：將頂點(diǎn)集V表示為擁堵路段集合的路網(wǎng)拓?fù)浣Y(jié)構(gòu)稱為擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)。

以每個(gè)擁堵路段作為根節(jié)點(diǎn)，在路網(wǎng)拓?fù)浣Y(jié)構(gòu)中進(jìn)行遍歷篩選，找到符合以下條件的邊〈u,w〉來(lái)構(gòu)成擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)：

1) 節(jié)點(diǎn)u、w均發(fā)生過(guò)擁堵，并且w先于u發(fā)生擁堵。

2) 節(jié)點(diǎn)u、w最短路徑距離必須小于閾值。

給出一個(gè)簡(jiǎn)單示例。如圖2所示的路網(wǎng)，包含44個(gè)路段，將路網(wǎng)中的路段看成一個(gè)節(jié)點(diǎn)，道路行駛方向看成一條邊，圖2所示的路網(wǎng)可以通過(guò)圖3的拓?fù)浣Y(jié)構(gòu)來(lái)表示，其中紅色節(jié)點(diǎn)表示該路段在整個(gè)時(shí)間段中發(fā)生過(guò)擁堵。進(jìn)一步篩選符合擁堵路網(wǎng)的拓?fù)潢P(guān)系，得到擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)，如圖4所示，其中邊表示擁堵路段之間可能存在的牽制關(guān)系。

圖2 實(shí)際路網(wǎng)圖

圖3 路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖

圖4 擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖

2.3 擴(kuò)散趨勢(shì)識(shí)別

路段的擁堵都會(huì)向周?chē)M(jìn)行擴(kuò)散，擁堵路段和被影響的路段從長(zhǎng)時(shí)間來(lái)看必然存在一定的因果關(guān)系。本小節(jié)分析了擁堵路段的因果關(guān)系，在此基礎(chǔ)上得到了擁堵路段的擴(kuò)散趨勢(shì)圖。

2.3.1擁堵路段因果關(guān)系分析

本文通過(guò)擁堵?tīng)顟B(tài)構(gòu)成的時(shí)間序列來(lái)進(jìn)行因果關(guān)系判斷，相關(guān)定義如下。

定義4(路段i的擁堵?tīng)顟B(tài)時(shí)間序列)：給定一個(gè)路段lanei,則稱Seqi={STi1,STi2,…,STit|STit=0,1}為路段lanei的擁堵?tīng)顟B(tài)時(shí)間序列，STit表示路段lanei在時(shí)刻t的擁堵?tīng)顟B(tài)，值取1表示路段擁堵，0表示路段通暢。

由于路段之間的擁堵存在時(shí)差，不是實(shí)時(shí)相關(guān)的，因此采用時(shí)間滯后互相關(guān)(TLCC)來(lái)確定擁堵路段之間的因果關(guān)系。

定義5(時(shí)間滯后程度)：lanei的擁堵在時(shí)間k后擴(kuò)散到lanej，則時(shí)間差k稱為兩路段的時(shí)間滯后程度。

TLCC用于計(jì)算時(shí)間滯后互相關(guān)程度，主要分為兩步：① 構(gòu)建時(shí)間滯后的擁堵?tīng)顟B(tài)時(shí)間序列；② 計(jì)算擁堵?tīng)顟B(tài)時(shí)間序列互相關(guān)程度。

首先需要構(gòu)建每個(gè)路段不同時(shí)間滯后程度的擁堵?tīng)顟B(tài)時(shí)間序列。假設(shè)lanei的擁堵?tīng)顟B(tài)時(shí)間序列為Seqi，時(shí)間滯后程度為k，lanei的時(shí)間滯后擁堵?tīng)顟B(tài)時(shí)間序列NSeqi的構(gòu)建過(guò)程如圖5所示。

圖5 時(shí)間滯后的擁堵?tīng)顟B(tài)時(shí)間序列

通過(guò)上述步驟可以得到每個(gè)擁堵路段的時(shí)間滯后擁堵?tīng)顟B(tài)時(shí)間序列，進(jìn)一步可以分析2個(gè)擁堵路段之間時(shí)間滯后擁堵?tīng)顟B(tài)時(shí)間序列的相關(guān)聯(lián)程度。

本文采用皮爾遜相關(guān)系數(shù)來(lái)計(jì)算兩路段擁堵的相關(guān)程度，通過(guò)相關(guān)系數(shù)來(lái)描述擁堵的因果相關(guān)程度，皮爾遜相關(guān)性系數(shù)見(jiàn)式(1)：

(1)

式中：cov為協(xié)方差，σ為標(biāo)準(zhǔn)差，Ε為期望，X、Y依次為擁堵路段的擁堵?tīng)顟B(tài)時(shí)間序列和被影響路段的時(shí)間滯后擁堵?tīng)顟B(tài)時(shí)間序列。可以進(jìn)一步化簡(jiǎn)為式(2)：

(2)

當(dāng)計(jì)算出相關(guān)系數(shù)后，可以通過(guò)以下取值范圍判斷變量的相關(guān)強(qiáng)度，如表2所示。

表2 相關(guān)系數(shù)強(qiáng)度

定義6(擁堵路段間因果關(guān)系)：給定2個(gè)擁堵路段lane1和lane2，lane1的擁堵?tīng)顟B(tài)時(shí)間序列為Seq1，lane2的時(shí)間滯后擁堵?tīng)顟B(tài)時(shí)間序列為NSeq2，如果兩路段時(shí)間滯后互相關(guān)程度(TLCC(Seq1,NSeq2))超過(guò)閾值(r)，則稱lane1和lane2擁有因果關(guān)系。具體分析見(jiàn)式(3)：

(3)

式中：R表示擁堵路段間因果關(guān)系，R=1代表?yè)碛幸蚬P(guān)系，R=0代表沒(méi)有因果關(guān)系；TLCC(·)為計(jì)算兩擁堵路段時(shí)間滯后互相關(guān)程度的方法；r為指定閾值。

假設(shè)lane1和lane2時(shí)間滯后互相關(guān)如圖6所示，橫坐標(biāo)表示時(shí)間滯后的程度，縱坐標(biāo)表示每個(gè)滯后時(shí)間點(diǎn)的互相關(guān)程度。從圖中可以得到，在時(shí)間滯后程度為0時(shí)，2個(gè)路段互相關(guān)程度較小；在滯后6個(gè)時(shí)間點(diǎn)時(shí)，TLCC(Seq1,NSeq2)=0.689，假設(shè)滯后6個(gè)時(shí)間點(diǎn)符合時(shí)間滯后范圍，且r取值小于0.689，則R(lane1,lane2)=1。

2.3.2擴(kuò)散趨勢(shì)圖分析

通過(guò)對(duì)擁堵路網(wǎng)進(jìn)行因果分析，從而得到每個(gè)擁堵路段的擴(kuò)散趨勢(shì)圖，用于描述擁堵向周?chē)鷶U(kuò)散的情況。

圖6 時(shí)間滯后互相關(guān)曲線

定義7(擴(kuò)散趨勢(shì)圖)：將邊集E為擁堵路段因果關(guān)系的擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)稱為擴(kuò)散趨勢(shì)圖。

擁堵路網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖描述了擁堵路段之間可能的關(guān)系，路段之間的擁堵可能沒(méi)有必然聯(lián)系或者相關(guān)性較小，因此提出了一個(gè)算法用于分析擴(kuò)散趨勢(shì)圖，如算法1所示。

算法1：擴(kuò)散趨勢(shì)圖分析算法

輸入：各時(shí)間點(diǎn)擁堵路段集合，擁堵路網(wǎng)拓?fù)鋱D鄰接表AL。

輸出：一組擴(kuò)散趨勢(shì)圖。

1:Plist← 一個(gè)空集合

2:AL← 將AL所有邊反向

3: for 節(jié)點(diǎn)lanei(i≤n) do

4:Que← 一個(gè)空隊(duì)列

5: 節(jié)點(diǎn)lanei入Que隊(duì)列

6:Graph← 一個(gè)空集合

7: whileQue隊(duì)列非空 do

8: 節(jié)點(diǎn)lanex←Que隊(duì)頭出隊(duì)列

9: 將節(jié)點(diǎn)lanex標(biāo)記為已遍歷

10:TempList← 節(jié)點(diǎn)lanex的鄰接表節(jié)點(diǎn)

11: for 節(jié)點(diǎn)laney(laney∈TempList) do

12: ifTLCC(Seqx,NSeqy)>Randlanex不在laney節(jié)點(diǎn)的鄰接表中

13:Graph←Graph∪

14: iflaney未遍歷 then

15:Que←Que∪laney

16: end if

17: end if

18: end for

19: end while

20:Plist←Plist∪Graph

21: end for

擁堵路網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖表示的是車(chē)流方向，而擁堵擴(kuò)散的方向應(yīng)與車(chē)流方向相反，因此算法1首先要將鄰接表進(jìn)行反向操作(第2行)，即將圖中所有邊的方向反向。以路段42為例，算法1會(huì)篩選符合條件的邊(如圖7(b)所示)，得到的子圖即為擴(kuò)散趨勢(shì)圖，如圖7(c)所示。同理可以得到其他路段的擁堵擴(kuò)散趨勢(shì)圖。

圖7 擴(kuò)散趨勢(shì)圖

2.4 瓶頸識(shí)別

城市中各個(gè)路段并非是獨(dú)立的存在，它們彼此相連，互相影響。因此，一條路段發(fā)生擁堵后，影響的不僅僅是需要經(jīng)過(guò)該路段的車(chē)，對(duì)需要經(jīng)過(guò)周?chē)范蔚能?chē)也有一定的影響。因此，為了保證識(shí)別的瓶頸具有更加優(yōu)越的性能，不僅需要計(jì)算擁堵路段自身的擁堵成本，還要分析這些路段的擁堵給周?chē)范螏?lái)的負(fù)面影響，即擁堵擴(kuò)散成本。最終，將擁堵總成本超過(guò)閾值的路段作為交通瓶頸。

定義8(路段擁堵總成本)：路段總成本為路段自身成本與擴(kuò)散成本之和，表示為：

(4)

式中：Slanei表示路段自身?yè)矶鲁杀荆珼lanei表示單個(gè)擁堵擴(kuò)散成本，即向某一條路擴(kuò)散的成本，m為受擁堵影響路段的總數(shù)。

2.4.1自身?yè)矶鲁潭扔?jì)算

首先需要計(jì)算每條擁堵路段的自身?yè)矶鲁杀尽Ｏ嗤膿矶鲁潭仍诓煌缆飞辖o城市帶來(lái)的影響是不一樣的，對(duì)于市中心和郊區(qū)2條擁堵程度一樣的路段，計(jì)算擁堵成本時(shí)不應(yīng)該得到同樣的數(shù)值，因?yàn)槭兄行牡穆范螕矶滤鶐?lái)的經(jīng)濟(jì)損失必然高于郊區(qū)路段，因此，擁堵程度一樣，市中心的路段擁堵成本應(yīng)該更高才符合實(shí)際。通常而言，車(chē)流量越大的路段重要性越高，其擁堵造成的損失也越大。因此記錄了全時(shí)段所有路段的車(chē)流量信息，通過(guò)路段的平均車(chē)流量信息作為描述路段重要程度的指標(biāo)。道路占用率可以直觀地表示路段擁擠程度，將路段的平均車(chē)流量信息和平均占用率共同表示其自身?yè)頂D程度。假設(shè)路段lanei的平均車(chē)流量為αi(輛)，道路平均占用率為βi，那么路段lanei的自身?yè)矶鲁杀颈硎緸椋篠lanei=αi*βi(輛)。

2.4.2擁堵擴(kuò)散程度分析

得到路段自身?yè)矶鲁杀竞螅枰治雎范螕矶孪蛑車(chē)范螖U(kuò)散的擴(kuò)散成本。前面的工作已經(jīng)得到每個(gè)擁堵路段的擴(kuò)散趨勢(shì)圖，如圖8(a)所示。圖8(b)為擴(kuò)散趨勢(shì)圖的直觀表示，類(lèi)似于一棵樹(shù)的結(jié)構(gòu)，如果把節(jié)點(diǎn)42看作根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的權(quán)值為對(duì)應(yīng)擁堵路段的自身?yè)矶鲁杀維，邊的權(quán)重Q為2個(gè)節(jié)點(diǎn)之間的時(shí)間滯后互相關(guān)程度，那么節(jié)點(diǎn)42的總擁堵成本(擴(kuò)散趨勢(shì)圖的權(quán)重)可以通過(guò)圖8(b)所展示的方式得到，具體計(jì)算方式為：根節(jié)點(diǎn)總擁堵成本為路段自身?yè)矶鲁杀九c擁堵擴(kuò)散成本之和，其中擴(kuò)散成本為所有子節(jié)點(diǎn)權(quán)重與邊權(quán)重乘積之和(見(jiàn)算法2)。同理可以得到所有節(jié)點(diǎn)擴(kuò)散趨勢(shì)圖的權(quán)重。

圖8 成本計(jì)算擴(kuò)散趨勢(shì)

算法2：總擁堵成本計(jì)算算法

輸入：擴(kuò)散趨勢(shì)圖，節(jié)點(diǎn)權(quán)值集合S，邊權(quán)重集合Q。

輸出：根節(jié)點(diǎn)總擁堵成本。

1: while 圖中節(jié)點(diǎn)數(shù)量 > 1 do

2:nodes← 圖中所有出度為0的節(jié)點(diǎn)

3:sides← 空集合

4: whilenode(node∈nodes) do

5:sides←sides∪與node連接的邊

6: end while

7: while 邊side(side∈sides) do

8:tail←side弧尾

9:head←side弧頭

10:Dtail←Shead*Qside

11:Stail←Stail+Dtail

12: 刪除head、side

13: end while

14: end while

2.4.3瓶頸確定

通過(guò)上訴步驟，分別得到了擁堵路段的自身?yè)矶鲁杀疽约皵U(kuò)散成本，兩者之和可以共同描述擁堵路段對(duì)整個(gè)路網(wǎng)的影響，數(shù)值越大，表明擁堵對(duì)整個(gè)路網(wǎng)車(chē)輛通行能力影響越大。

城市道路交通瓶頸是路網(wǎng)中對(duì)整體路網(wǎng)通行能力影響最大的路段，即瓶頸處的擁堵會(huì)嚴(yán)重影響周?chē)鷧^(qū)域交通狀況，瓶頸處的流量緩解帶來(lái)的是整體路網(wǎng)通行能力的提升。定義如下。

定義9(城市交通瓶頸)：城市交通瓶頸是路網(wǎng)中擁堵總成本超過(guò)閾值的路段，分析見(jiàn)式(5):

(5)

式中：flanei=1代表lanei為交通瓶頸；T表示成本閾值。根據(jù)式(5)，將總成本超過(guò)閾值的擁堵路段作為交通瓶頸。

3 模擬與討論

SUMO是一款開(kāi)源、微觀、多模態(tài)的交通仿真軟件，可以對(duì)每輛車(chē)進(jìn)行單獨(dú)控制，對(duì)于基本數(shù)據(jù)的獲取也相對(duì)容易。因此，本文選擇SUMO交通模擬器來(lái)進(jìn)行相關(guān)實(shí)驗(yàn)。首先識(shí)別了蘇福爾斯路網(wǎng)中的交通瓶頸，并且通過(guò)增加車(chē)道數(shù)來(lái)提高車(chē)道通行能力，計(jì)算了整個(gè)路網(wǎng)的平均行駛速度改善百分比。除此之外，比較了現(xiàn)有技術(shù)所識(shí)別的瓶頸對(duì)路網(wǎng)通行能力的改善效果，以此證明所提出的方法具有更加優(yōu)越的性能。

3.1 瓶頸識(shí)別

在本小節(jié)中，分別計(jì)算了路段自身?yè)矶鲁杀竞蛿U(kuò)散成本，確定了蘇福爾斯路網(wǎng)中的交通瓶頸。如圖9所示，橫軸表示路網(wǎng)中所有路段的編號(hào)，縱軸表示各路段的擁堵成本。從圖中可以看到，基于現(xiàn)有的瓶頸識(shí)別技術(shù)(僅考慮路段自身的擁堵程度)，路段35和37將被識(shí)別為蘇福爾斯路網(wǎng)的瓶頸。然而，當(dāng)結(jié)合擁堵擴(kuò)散效應(yīng)來(lái)量化路段的擁堵成本時(shí)，路段43和46更有可能被視為瓶頸。特別是與其他路段(如路段35、37和46)相比，路段43自身?yè)矶鲁潭炔皇呛芨撸倱矶聰U(kuò)散成本卻高很多，這是由于路段之間的空間連接，導(dǎo)致路段43上的擁堵往往會(huì)蔓延到路段35、37和46。實(shí)驗(yàn)結(jié)果表明，路網(wǎng)中最擁堵的路段不一定是交通瓶頸，僅根據(jù)路段自身的數(shù)據(jù)去分析交通瓶頸是不嚴(yán)謹(jǐn)?shù)摹?/p>

圖9 路段擁堵成本曲線

3.2 瓶頸驗(yàn)證

交通瓶頸的直觀表達(dá)是：瓶頸處的流量緩解帶來(lái)了顯著的路網(wǎng)范圍內(nèi)的流量改善。因此，為了驗(yàn)證本文所提方法在識(shí)別交通瓶頸方面的有效性，在SUMO上增加了每個(gè)路段的車(chē)道數(shù)，并分別比較了增加前后路網(wǎng)的車(chē)輛通行能力的提高情況。本文通過(guò)車(chē)輛的出行速度表示路網(wǎng)的車(chē)輛通行能力。

如圖10所示，路網(wǎng)的通行能力在路段車(chē)道數(shù)增加后都得到了提高，特別是路段43和路段46，增加車(chē)道數(shù)后平均行駛速度分別提升了88.1%和92.3%，改善效果遠(yuǎn)遠(yuǎn)高于其他路段，說(shuō)明這2個(gè)路段的交通狀況會(huì)對(duì)周?chē)范萎a(chǎn)生較大影響。根據(jù)定義9可以確定，蘇福爾斯路網(wǎng)的交通瓶頸為路段43和路段46。結(jié)果表明，提出的同時(shí)考慮自身?yè)矶鲁杀竞蛿U(kuò)散成本的瓶頸識(shí)別方法可以更好地捕捉城市道路交通瓶頸，在城市道路交通路網(wǎng)的瓶頸識(shí)別方面具有優(yōu)越的性能。

3.3 實(shí)驗(yàn)結(jié)果對(duì)比

在本小節(jié)中，分別在不同瓶頸識(shí)別技術(shù)識(shí)別的瓶頸處增加車(chē)道數(shù)，按方法分類(lèi)，比較了在不同車(chē)輛到達(dá)率下的路網(wǎng)的車(chē)輛通行能力，結(jié)果如圖11所示。可以看到，當(dāng)車(chē)輛到達(dá)率較小時(shí)，幾種方法識(shí)別的瓶頸對(duì)路網(wǎng)通行能力的改善效果相差無(wú)幾，因?yàn)檫@時(shí)路網(wǎng)的容量還沒(méi)有飽和，換言之，路網(wǎng)本身就不是很擁堵，增加車(chē)道后自然對(duì)擁堵緩解不明顯。當(dāng)車(chē)輛到達(dá)率逐漸增大，路網(wǎng)的擁堵開(kāi)始加重，這時(shí)不同瓶頸識(shí)別技術(shù)的優(yōu)劣便體現(xiàn)了出來(lái)。從圖11中可以看出，當(dāng)車(chē)輛到達(dá)率為每小時(shí)5 400輛車(chē)時(shí)，在識(shí)別的瓶頸處增加車(chē)道數(shù)所帶來(lái)的交通改善收益遠(yuǎn)高于其他方法，路網(wǎng)平均行駛速度提高了90.6%，說(shuō)明提出的考慮擁堵擴(kuò)散的瓶頸識(shí)別方法可以更有效地捕捉城市交通瓶頸，能夠最大程度地緩解交通擁堵。

圖10 行駛速度改善的百分比曲線

圖11 行駛速度改善的百分比柱狀圖

4 實(shí)際場(chǎng)景應(yīng)用實(shí)驗(yàn)

4.1 應(yīng)用場(chǎng)景介紹

本次采集的數(shù)據(jù)來(lái)自四川省綿陽(yáng)市，通過(guò)路邊攝像頭對(duì)車(chē)輛信息采集，將采集的數(shù)據(jù)通過(guò)算法進(jìn)行軌跡還原，從而得到本文所需要的原始數(shù)據(jù)集。數(shù)據(jù)集包含路網(wǎng)數(shù)據(jù)和車(chē)輛數(shù)據(jù)，其中路網(wǎng)數(shù)據(jù)包含288條路段以及97個(gè)交叉路口，車(chē)輛數(shù)據(jù)包含 100 000輛車(chē)的軌跡路線。將數(shù)據(jù)集在SUMO仿真平臺(tái)上運(yùn)行，記錄各個(gè)時(shí)刻的道路占用率以及指定時(shí)間范圍內(nèi)道路的車(chē)流量信息，這樣可以得到本文算法需要的初始數(shù)據(jù)。通過(guò)分析這些數(shù)據(jù)，使用本文所提出的技術(shù)實(shí)現(xiàn)交通瓶頸識(shí)別。

4.2 因果關(guān)系分析

在本文中，通過(guò)道路車(chē)道占用率以及車(chē)輛停滯比例來(lái)確定道路的擁堵?tīng)顟B(tài)。根據(jù)綿陽(yáng)市交通具體情況，路段擁堵閾值M、N分別設(shè)置為70和50。實(shí)際生活場(chǎng)景中，路段擁堵?tīng)顟B(tài)改變后會(huì)維持一段時(shí)間，不會(huì)立即又發(fā)生改變。因此，為了同時(shí)考慮數(shù)據(jù)的有效性和整個(gè)算法的計(jì)算效率，采用時(shí)間片段來(lái)收集數(shù)據(jù)，結(jié)合當(dāng)?shù)貙?shí)際情況，最終以15 s為一個(gè)時(shí)間片段，收集各時(shí)間點(diǎn)路網(wǎng)中路段的擁堵?tīng)顟B(tài)。如圖12所示，統(tǒng)計(jì)了各時(shí)間點(diǎn)擁堵路段的數(shù)量，從圖中可以得到，前面2 h整個(gè)路網(wǎng)基本沒(méi)有發(fā)生擁堵，之后擁堵路段數(shù)量開(kāi)始增加，嚴(yán)重時(shí)有43條主干道發(fā)生擁堵。在10 h后擁堵情況沒(méi)有繼續(xù)惡化，擁堵路段數(shù)量開(kāi)始緩慢減少，第19 h后路網(wǎng)基本沒(méi)有擁堵。

圖12 各時(shí)間點(diǎn)擁堵路段數(shù)量

在分析擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖時(shí)，如果2個(gè)擁堵路段距離過(guò)遠(yuǎn)，就可以認(rèn)為這2個(gè)路段的擁堵不存在因果關(guān)系。首先獲取了路網(wǎng)中所有路段的長(zhǎng)度，按照長(zhǎng)度對(duì)路段排序，剔除其中長(zhǎng)度過(guò)長(zhǎng)或過(guò)短的路段，計(jì)算剩余路段的平均長(zhǎng)度，最終以平均長(zhǎng)度的4倍作為本文算法的距離閾值，如圖13所示。時(shí)間滯后相關(guān)程度可以確定2個(gè)路段的擁堵互相影響的程度，結(jié)合表2中關(guān)于相關(guān)系數(shù)強(qiáng)度的闡述，將時(shí)間滯后相關(guān)程度大于0.3的2個(gè)擁堵路段視為擁有因果關(guān)系。

4.3 擴(kuò)散趨勢(shì)識(shí)別

在本小節(jié)中，通過(guò)算法1分析出擁堵路段的擴(kuò)散趨勢(shì)圖。為了方便起見(jiàn)，從每個(gè)擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖中給出其中一個(gè)擴(kuò)散趨勢(shì)圖。如圖14所示，從圖中可以看出，路網(wǎng)中有三片區(qū)域發(fā)生了嚴(yán)重?fù)矶拢渲新范?9的擴(kuò)散趨勢(shì)圖最大，擁堵向西北方向擴(kuò)散，從而導(dǎo)致大片區(qū)域發(fā)生擁堵。

圖13 路段長(zhǎng)度

圖14 擴(kuò)散趨勢(shì)圖

4.4 瓶頸識(shí)別與優(yōu)化

4.4.1瓶頸識(shí)別

得到每個(gè)擁堵路段的自身?yè)矶鲁杀竞蛿U(kuò)散成本，兩者之和視為綿陽(yáng)市路網(wǎng)中各路段的總擁堵成本，將總擁堵成本超過(guò)閾值的路段作為該擁堵區(qū)域的交通瓶頸。圖15為其中一個(gè)擴(kuò)散趨勢(shì)圖的計(jì)算結(jié)果，從圖中可以發(fā)現(xiàn)，某些路段(例如路段19)的擁堵程度不如其他路段(例如路段22、34、37和39)高，但它們的擁堵擴(kuò)散效應(yīng)顯著，緩解這些路段的擁堵可以使整個(gè)路網(wǎng)車(chē)輛通行能力顯著提升。因此，這些路段才應(yīng)被視為路網(wǎng)的瓶頸。

圖15 路段擁堵成本

4.4.2瓶頸優(yōu)化

如果能夠有效緩解交通瓶頸處的流量，那么整個(gè)城市交通路網(wǎng)的擁堵就可以顯著緩解。在本文模擬實(shí)驗(yàn)中通過(guò)增加交通瓶頸處車(chē)道數(shù)量使得瓶頸處擁堵減少，但在實(shí)際生活中，通過(guò)增加基礎(chǔ)設(shè)施來(lái)緩解擁堵并不常見(jiàn)，更多的是優(yōu)化交通信號(hào)燈。因此，手動(dòng)將交通瓶頸處的信號(hào)燈做一定優(yōu)化，使得瓶頸處的擁堵能夠得到有效緩解，并且對(duì)比了優(yōu)化前后整個(gè)路網(wǎng)中車(chē)輛平均行駛速度，如圖16所示。通過(guò)計(jì)算，優(yōu)化后車(chē)輛平均行駛速度相較于優(yōu)化前提升了94%。

圖16 交通狀況改善效果

5 結(jié)論

為解決城市交通網(wǎng)絡(luò)中的瓶頸，提出了一種新的城市交通瓶頸定義，該定義計(jì)算路段的擁堵成本，同時(shí)考慮了道路自身?yè)矶鲁杀竞蛿U(kuò)散成本。首先從車(chē)道占用率以及車(chē)輛停滯比例對(duì)路段擁堵作了闡述，得到路網(wǎng)中的擁堵路段，并進(jìn)一步分析出擁堵路網(wǎng)拓?fù)浣Y(jié)構(gòu)圖。其次給出了2條擁堵路段因果分析的方法，得到擁堵路段擴(kuò)散趨勢(shì)圖。然后根據(jù)平均交通流量和平均占用率計(jì)算了道路自身?yè)矶鲁杀荆鶕?jù)擴(kuò)散趨勢(shì)圖得到路段的擴(kuò)散成本。此外，利用道路自身?yè)矶鲁杀竞蛿U(kuò)散成本，計(jì)算了不同路段的總擁堵成本，并確定了城市道路交通網(wǎng)絡(luò)中的交通瓶頸。最后，通過(guò)SUMO交通仿真軟件進(jìn)行了模擬實(shí)驗(yàn)，并進(jìn)一步在實(shí)際生活場(chǎng)景中驗(yàn)證。結(jié)果表明，所識(shí)別的交通瓶頸在城市地區(qū)能夠表現(xiàn)更加優(yōu)越的性能，特別是在路網(wǎng)容量比較飽和時(shí)優(yōu)勢(shì)更加明顯。