梁 偉，張 毅*,2,3，胡堅明

(1.清華大學自動化系，北京100084；2.清華—伯克利深圳學院，廣東 深圳518055；3.江蘇省現(xiàn)代城市交通技術(shù)創(chuàng)新中心，南京210096)

0 引言

隨著現(xiàn)代城市路網(wǎng)規(guī)模的不斷擴大，道路結(jié)構(gòu)越發(fā)復雜，同時駕車購物出行需求日益增加，使得交通流狀態(tài)呈現(xiàn)出復雜多樣的變化趨勢，“行車難、停車難”問題突出，形勢嚴峻，已引起社會各界的廣泛關(guān)注.為了合理利用資源，解決這一社會難題，給出行者帶來舒適的駕車體驗，許多專家學者對此展開了研究.目前，出行時規(guī)劃行車路線，即路徑誘導，給出行者提供一個或多個時間最短或距離最短路徑，已經(jīng)成為大多數(shù)城市居民駕車購物出行時的優(yōu)先選擇.在路徑誘導方法中，通常分為傳統(tǒng)路徑規(guī)劃方法和智能路徑規(guī)劃方法兩類.傳統(tǒng)方法[1-4]應用最短路搜索算法來規(guī)劃最優(yōu)行駛路徑，這種方法成熟可靠，但是大多不能自適應實時交通流狀態(tài)的變化，當路網(wǎng)信息發(fā)生較大變化時，路徑誘導效果就會出現(xiàn)明顯偏差，嚴重影響駕車購物者的出行體驗.智能方法利用啟發(fā)式算法搜索最優(yōu)路徑[5-6]，或者利用神經(jīng)網(wǎng)絡(luò)和遺傳算法等動態(tài)搜索最優(yōu)路徑[7]，大多在全局路網(wǎng)結(jié)構(gòu)上重新搜索，路徑規(guī)劃的計算量和計算時間負擔較重，路徑規(guī)劃實時性差.購物出行是以購物為目的的一種出行方式，目的地(購物中心)多處于鬧市區(qū).人們購物出行時希望處于舒適的出行環(huán)境中，通常會對心理預期的車輛平均行駛速度格外關(guān)注；而且，由于目的地比較明確，途中如果需要改變行駛路線，出行者也大多傾向于局部調(diào)整其行前誘導路徑.因此，有必要研究根據(jù)交通流狀態(tài)動態(tài)變化情況自適應對局部路徑進行更新的路徑誘導方法，以滿足駕車購物的實際誘導需求.

本文首先引入出行期望速度閾值，分析路網(wǎng)中節(jié)點之間的動態(tài)連通性，優(yōu)化路網(wǎng)結(jié)構(gòu)，限制路網(wǎng)規(guī)模，建立局部路網(wǎng)模型，然后提出一種基于局部連通性的在途路徑誘導方法，實現(xiàn)有效的在途動態(tài)路徑誘導.

1 局部路網(wǎng)建模

一個包含m個路口和路口間路段組成的路網(wǎng)可表示為有向圖模型其中P={p1,p2,…,pm}是節(jié)點(路口)集合；E={eij|i,j=1,2,…,m} 是邊(路段)集合，eij是從節(jié)點pi出發(fā)到達節(jié)點pj的路段是路阻集合，dij是邊eij的路阻，表示車輛通過該路段的通行代價，用道路交通狀態(tài)系數(shù)[8]Iij來描述，它是在途車輛在路段上平均行駛速度的倒數(shù)，即

在途車輛行駛通常會受到道路交通流狀態(tài)的影響，道路交通狀態(tài)系數(shù)可以描述道路的交通流狀態(tài).路網(wǎng)模型中，路阻越大，道路交通越擁堵，這將直接影響節(jié)點之間的連通狀態(tài).

1.1 動態(tài)連通性分析

引入出行期望速度閾值λ，其描述了購物者出行希望達到的平均速度(即出行者能暢通行駛的速度).根據(jù)中國道路交通管理評價指標規(guī)定：城市主干道機動車平均行程速度不低于30 km/h為暢通，20～30 km/h為輕度擁擠，10～20 km/h為擁擠，低于10 km/h為嚴重擁擠.將20 km/h與道路的實際限速進行比較，取兩者平均值，作為出行期望速度閾值.

當某路段的路阻大于閾值時，說明出行者駕車行駛時，將不能處于通暢狀態(tài)，影響其出行體驗，該路阻可近似為無窮大，此時連接該路段的多個節(jié)點之間視為不連通；反之，節(jié)點之間處于連通狀態(tài).路阻矩陣D(λ)表示在λ下路網(wǎng)中相鄰2個節(jié)點之間的實際通行代價，表達式為

式中：aij是2個節(jié)點的空間鄰接關(guān)系.

在出行期望速度閾值λ下，路網(wǎng)的空間動態(tài)鄰接矩陣為

進而，在2個節(jié)點之間的所有連通路徑中，經(jīng)過l條邊的路徑總路阻為

式中：p1,p2,…,pl-1是從節(jié)點pi出發(fā)到達節(jié)點pj的連通路徑所經(jīng)過的節(jié)點，滿足p1,p2,…,pl-1∈P且p1≠p2≠…≠pl-1.

當出行期望速度閾值不同時，路網(wǎng)節(jié)點間表現(xiàn)出不同的連通性.如圖1所示的仿真路網(wǎng)，線段上的數(shù)字表示該道路的路阻值.

當期望速度閾值分別是0.050、0.040和0.033時，其路網(wǎng)拓撲如圖2所示(圖中相應節(jié)點的編號同圖1).

圖1 仿真初始路網(wǎng)的拓撲結(jié)構(gòu)Fig.1 The initial road network

圖2 不同期望速度閾值下的路網(wǎng)拓撲Fig.2 Structures under different traffic congestions

考察圖2中從節(jié)點p6到節(jié)點p7的邊e6-7，當出行者駕車行駛時，期望速度較小時(λ=0.050)，邊e6-7處于連通狀態(tài)；當期望速度較大時(λ=0.040)，邊e6-7處于斷路狀態(tài).在以上2種不同期望速度下，路網(wǎng)表現(xiàn)出截然不同的連通性.

交通路網(wǎng)是一種復雜網(wǎng)絡(luò)，由相關(guān)研究[9]可知，復雜網(wǎng)絡(luò)的連通性能可用網(wǎng)絡(luò)節(jié)點之間連通路徑的總數(shù)目來評價.以此為基礎(chǔ)，提出2個動態(tài)連通性指標——有效可達值Φ和平均可達路阻γ，來評估在不同出行期望速度閾值下節(jié)點之間的動態(tài)連通可達程度.

(1)有效可達值Φ.

(2)平均可達路阻γ.

式中：Nij(L,λ)是從節(jié)點pi出發(fā)到達節(jié)點pj的連通路徑數(shù)目[9]；Qij(λ)是從節(jié)點pi出發(fā)到達節(jié)點pj時含有回路的連通路徑數(shù)目；l為2個節(jié)點之間的連通路徑經(jīng)過的邊數(shù)目；L是連通路徑經(jīng)過邊的最大數(shù)目；M是連通路阻閾值，它限制了路網(wǎng)節(jié)點間連通路徑的最大路阻，通常受到行前誘導路徑路阻的影響，當行前誘導路徑路阻較大時，閾值也較大，反之則較小.

1.2 局部路網(wǎng)模型

當城市交通路網(wǎng)中局部交通流較大或發(fā)生交通事故、臨時交通管制等，致使車輛還未行駛過的誘導路徑出現(xiàn)擁堵、造成連通失效時，在途車輛須及時更新誘導路徑.為了保證行駛路徑的可靠有效連通，本節(jié)利用動態(tài)連通性指標來計算并評估車輛當前位置附近的局部路網(wǎng)，并在其中進行誘導路徑的局部更新.局部路網(wǎng)以在誘導路徑上行駛的車輛位置為基準，涵蓋周圍部分區(qū)域.它隨著在途車輛的行駛位置動態(tài)可變，保持著從當前節(jié)點到目的地終點的動態(tài)連通能力.

節(jié)點pO和pD均處在行前誘導路徑上，它們之間滿足pO,pD的關(guān)系，即車輛行駛時先經(jīng)過節(jié)點pO，后經(jīng)過節(jié)點pD.為了討論方便，本文將局部誘導路徑上的節(jié)點按照車輛行駛通過的先后次序進行編號，即局部誘導路徑上的節(jié)點pO,…,pi,…,pD映射為正整數(shù)1,…,i,…,q，依此，節(jié)點pO和pD的關(guān)系也可表示為pO＜pD.另外，2個節(jié)點之間動態(tài)路阻和拓撲關(guān)系是有向圖模型分析的重點，這里用一個ω算子將實際距離Ψ轉(zhuǎn)換成誘導路徑上它們之間間隔的節(jié)點數(shù)目以避免實際距離不同對模型分析的影響.

假設(shè)車輛到達節(jié)點pGet時獲取到實時交通信息，計算誘導信息花費時間是tcompute-select；當出行者收到誘導信息后開始做出更換車道等操作反應時，車輛位置處于反應節(jié)點pRenew；車輛執(zhí)行操作反應所花費的最少時間是tmin，之后車輛到達起點pO.另設(shè)計算局部路網(wǎng)需要的最大時間值是T，在途車輛的平均行駛速度是，實時交通信息更新周期為Γtr.雖然在收到誘導信息時，出行者也需要一個心理反應時間，但根據(jù)蔡伯根等[10]的研究，該心理反應時間相對較小，本文暫不考慮.上述節(jié)點之間的關(guān)系如圖3所示.

圖3 起點與其他節(jié)點之間的關(guān)系示意圖Fig.3 Relationship between the origin and other intersection

(1)起點的計算.

計算起點pO的目的是為出行者更新路徑提供充足時間進行決策并做出反應，具體來說，它影響著局部路網(wǎng)的計算、誘導路徑的更新、車輛對誘導做出反應的時間等.起點的設(shè)置與車輛的當前位置、車輛行駛速度和實時交通信息更新頻率等因素有關(guān).

若Γtr≥tcompute-select+tmin，即車輛經(jīng)過反應節(jié)點pGet后，就不再接收新的交通信息，此時可得T=Γtr；若Γtr＜tcompute-select+tmin，則可令Γt'r=n?Γtr,n=1,2,…，取的最小值

已知車輛到達節(jié)點pGet時，獲取實時交通信息，則有

觀察組治療總有效率98.67%(148/150)高于對照組87.33%(131/150),對比差異有統(tǒng)計學意義(P<0.05)。見表1:

節(jié)點pRenew滿足

綜上，起點pO應滿足

(2)確定終點和局部路網(wǎng)規(guī)模.

終點和局部路網(wǎng)規(guī)模決定了出行者在局部路網(wǎng)中可能選擇的備選路徑.合理的終點能夠保證在不同程度的交通擁堵下，其與起點之間總能存在連通路徑.設(shè)置1個有效可達值閾值K，終點pD須滿足式(11)的條件.

而局部路網(wǎng)規(guī)模則決定了出行者選擇備選路徑的范圍.當規(guī)模較大時，備選路徑一般也會較多.當備選路徑達到一定數(shù)量時，出行者就足以尋找到高效合理的連通路徑.但是，如果規(guī)模太大，備選路徑的冗余率提高，從而增加駕車購物者的出行成本，加大城市交通出行的整體壓力.另外，一般會存在多個滿足式(11)要求的局部路網(wǎng)，但是它們涵蓋備選路徑的路阻卻不盡相同，平均可達路阻越小的那些局部路網(wǎng)的連通性能自然越好.因此，最優(yōu)局部路網(wǎng)的規(guī)模須滿足

綜上，根據(jù)交通擁堵閾值和路阻函數(shù)，計算D(λ)，在此基礎(chǔ)上，求得起點pO，根據(jù)式(11)求得終點pD，再根據(jù)式(12)，計算集合P和E，至此解得最優(yōu)局部路網(wǎng)，可保證在途車輛在遇到交通擁堵時能夠選擇高效的備選路徑行駛，更新誘導路徑.

2 在途動態(tài)路徑誘導方法

在途動態(tài)路徑誘導方法是在局部路網(wǎng)中尋找最優(yōu)路徑以局部更新行前誘導路徑，保證在途車輛當前位置與終點的連通性，自適應道路交通流的變化.具體地，該方法將行前誘導路徑作為初始路徑，根據(jù)車輛位置，首先確定起點pO和終點pD，并構(gòu)建一個初始局部路網(wǎng)Ginit作為初始解，再求解出最優(yōu)局部路網(wǎng)GLocal，繼而在GLocal上更新局部路徑，直至誘導車輛到達終點.整個方法采用開放式設(shè)計，原理框架圖如圖4所示.

3 實驗驗證和評估

實驗以北京市海淀區(qū)某購物中心駕車出行為例，出行起點為學府樹家園，終點為金源新燕莎購物中心(行程距離約15 km)，出行區(qū)間涵蓋約上百個路口.出行區(qū)間的部分地圖如圖5所示，圖中黑色實線是行前誘導路徑，右圖為左邊圓圈內(nèi)實驗區(qū)域路網(wǎng)的有向圖(道路均是雙向通行，由于篇幅限制，圖中未標出道路方向和路阻).

實驗假設(shè)在途車輛到達節(jié)點p29前的一個計算周期內(nèi)，節(jié)點p3處發(fā)生3種不同嚴重程度的交通事件，導致附近交通狀態(tài)變化較大，分別造成1個路口、3個路口和4個路口的擁堵(圖6中深黑色線條所示)，分別優(yōu)化求解局部路網(wǎng)，驗證本文方法對不同最短路算法(Dijkstra算法、A*算法)的有效性和適應性.

圖4 在途動態(tài)路徑誘導方法原理框架圖Fig.4 Diagram of en-route dynamic route guidance

實驗中交通擁堵影響了從節(jié)點p29到節(jié)點p2的誘導路徑其原路阻為0.057.本文方法需要優(yōu)化局部路網(wǎng)，而局部路網(wǎng)規(guī)模受到出行期望速度閾值的影響，針對3種情況分別進行討論，結(jié)果如表1所示.實驗中，出行期望速度閾值設(shè)置為0.070.

(1)當交通擁堵影響1個路口(p3)時，本文方法中最優(yōu)路徑搜索算法采用Dijkstra算法，路徑規(guī)劃時涉及到8個節(jié)點，計算時間為0.12 s，誘導路徑更新為

圖5 北京市海淀區(qū)部分地圖及實驗區(qū)域Fig.5 Example in part of Beijing Haidian District

圖6 不同嚴重程度交通擁堵示意Fig.6 Congestions in different intersections

(2)當交通擁堵影響3個路口(p3、p4、p6)時，求解出的局部路網(wǎng)規(guī)模相應變大，本文方法中最優(yōu)路徑搜索算法采用A*算法，路徑規(guī)劃時涉及到10個節(jié)點，計算時間為0.18 s，局部誘導路徑更新為

(3)當交通擁堵影響4個路口(p3、p4、p6、p11)時，求解出的局部路網(wǎng)規(guī)模較大，本文方法中最優(yōu)路徑搜索算法采用A*算法，路徑規(guī)劃時涉及到11個節(jié)點，計算時間為0.22 s，局部誘導更新路徑為

將本文方法和神經(jīng)網(wǎng)絡(luò)與遺傳算法相結(jié)合的動態(tài)路徑誘導方法[7]進行比較.在車輛到達節(jié)點p29前的計算周期里，對比方法基于神經(jīng)網(wǎng)絡(luò)對實驗區(qū)域內(nèi)各路段的路阻進行預測，并構(gòu)建其具有時變性的路阻矩陣，再采用遺傳算法選擇最優(yōu)路徑.針對3種不同擁堵情況，對比方法計算時分別涉及到28個、26個和25個節(jié)點，計算時間分別為0.73 s、0.61 s和0.45 s.具體計算指標如表1所示.

表1 不同方法的計算指標比較Table 1 Comparison of different approaches

從表1中可以看出，在3種不同交通擁堵情況下，本文方法具有更好的開放性和計算規(guī)模上的優(yōu)勢，表現(xiàn)出良好的誘導效果和對于實時交通流狀態(tài)變化的自適應能力.

4 結(jié)論

針對傳統(tǒng)路徑誘導方法沒有實現(xiàn)實時局部在途更新的缺陷，本文針對駕車購物出行的自適應路徑誘導方法展開研究.引入出行期望速度閾值，研究了實時交通流影響下路網(wǎng)的動態(tài)連通性，給出動態(tài)連通性指標，優(yōu)化局部路網(wǎng)結(jié)構(gòu)，提出了一種在途動態(tài)路徑誘導方法，根據(jù)實時交通流狀態(tài)為出行者實時更新局部誘導路徑.對該方法進行了實地實驗驗證，并跟神經(jīng)網(wǎng)絡(luò)與遺傳算法相結(jié)合的動態(tài)路徑誘導方法進行比較，實驗結(jié)果表明，本文方法更能實時準確地確定局部路網(wǎng)最優(yōu)路徑.在該算法的開放性結(jié)構(gòu)下，隨著更先進的最短路徑搜索算法和路阻函數(shù)的出現(xiàn)可得到進一步的發(fā)展，以滿足在途動態(tài)路徑誘導的實際需要.

[1]HAWAS Y E,EL-SAYED H.Autonomous real time route guidance in inter-vehicular communication urban networks[J].Vehicular Communications,2015,2(1):36-46.

[2]SHIFFMAN S.Analytical hierarchy process using fuzzy inference technique for real-time route guidance system[J].IEEE Transactions on Intelligent Transportation Systems,2014,15(1):84-93.

[3]LIANG Z L,WAKAHARA Y.Real-time urban traffic amount prediction models for dynamic route guidance systems[J].EURASIP Journal on Wireless Communications and Networking,2014,2014(1):1-13.

[4]PAN J,POPA I S,ZEITOUNI K,et al.Proactive vehicular traffic rerouting for lower travel time[J].IEEE Transactions on Vehicular Technology,2013,62(8):3551-3568.

[5]SHAHZADA A,ASKAR K.Dynamic vehicle navigation:An A*algorithm based approach using traffic and road information[C]//IEEE International Conference on Computer Applications and Industrial Electronics.Penang:IEEE,2011:514-518.

[6]JIANG J C,WU L X.A re-optimization dynamic shortest path algorithm for vehicle navigation[C]//Geoscience and Remote Sensing Symposium,IEEE,Quebec City,2014:3109-3112.

[7]吳成東,楊麗英,許可.神經(jīng)網(wǎng)絡(luò)和遺傳算法在動態(tài)路徑誘導中的應用[J].計算機應用研究,2006(5):177-179.[WU C D,YANG L Y,XU K.Application of neural network and genetic algorithm in dynamic route guidance[J].Application Research of Computers,2006(5):177-179.]

[8]張和生,張毅,胡東成,等.區(qū)域交通狀態(tài)分析的時空分層模型[J].清華大學學報(自然科學版),2007,47(1):157-160.[ZHANG H S,ZHANG Y,HU D C,et al.Spatial-temporal hierarchical model for area traffic state analysis[J].Journal of Tsinghua University,2007,47(1):157-160.]

[9]吳俊,譚索怡,譚躍進,等.基于自然連通度的復雜網(wǎng)絡(luò)抗毀性分析[J].復雜系統(tǒng)與復雜性科學,2014,11(1):77-86.[WU J,TAN S Y,TAN Y J,et al.Analysis of invulnerability in complex networks based on natural connectivity[J].Complex Systems and Complexity Science,2014,11(1):77-86.]

[10]柴琳果,蔡伯根,王化深,等.車聯(lián)網(wǎng)中駕駛員反應時間實時估計方法[J].交通運輸系統(tǒng)工程與信息,2016,16(5):71-78.[CHAI L G,CAI B G,WANG H S,et al.Real-time estimating method of diver’s reacting time under the condition of internet of vehicles[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(5):71-78.]