顧及轉向延誤的時間依賴A＊最短路徑算法

鄭年波,陸 鋒,李清泉,段瀅瀅

1.中國科學院地理科學與資源研究所資源與環境信息系統國家重點實驗室,北京100101;2.武漢大學交通研究中心,湖北武漢430079

顧及轉向延誤的時間依賴A＊最短路徑算法

鄭年波1,陸 鋒1,李清泉2,段瀅瀅1

1.中國科學院地理科學與資源研究所資源與環境信息系統國家重點實驗室,北京100101;2.武漢大學交通研究中心,湖北武漢430079

建立基于路段的時間依賴網絡模型,將轉向延誤時間引入到FIFO(先進先出)條件的定義中,并給出滿足FIFO條件的路段到達時間和轉向延誤時間計算式。通過將時間因子引入到啟發式評價函數中,發展了基于路段標號的時間依賴A＊最短路徑算法。試驗表明,所提出的算法能預測并回避即將發生的交通擁堵,有效節省用戶的出行時間。而其平均計算時間僅比傳統算法增加10%左右。由于不再需要進行頻繁的路徑重優化,該算法能提高路徑規劃的整體效率。

路徑規劃;最短路徑;A＊算法;時間依賴網絡;轉向延誤

1 引 言

利用交通信息進行動態路徑規劃是車輛導航、位置服務等研究領域的重要課題[1]。而目前相關算法只是簡單地將當前交通信息作為路段權值調整的系數,于出發前利用各種啟發式最短路徑算法計算最優行駛路徑[2],并于行駛過程中利用實時接收的交通信息進行路徑的重計算[3]。它們忽略了路段行程時間依賴于進入該路段的時刻這一現實,不能從出行全局上為用戶考慮,導致頻繁的路徑重計算,進而影響導航系統的整體效率。有必要研究時間依賴的最短路徑算法。

時間依賴最短路徑問題將路段行程時間建模為時間依賴的變量,并在滿足先進先出條件的情況下,可以通過改進的Dijkstra、A＊等標號設定(label-setting,LS)算法來求解[4-9]。然而,這些改進的算法普遍缺乏對交叉口轉向延誤的考慮。事實上,交叉口轉向引起的時間延誤可以達到全部行駛時間的17%～35%[10]。同一交叉口不同的轉向通常有不同的延誤時間,這與LS算法單一標號的性質相矛盾,基于節點標號的LS算法不再有效[11]。針對此問題,路段標號和對偶圖法是兩種有效的解決策略[10-17]。這些方法都基于靜態網絡,缺乏對交通網絡時間依賴特性的考慮。事實上,轉向延誤的存在影響了時間依賴網絡的FIFO條件,需要考慮對之進行重新定義。

本文面向帶轉向延誤的時間依賴最短路徑問題,定義基于路段的時間依賴網絡以及考慮轉向延誤的FIFO條件,發展基于路段標號的時間依賴A＊算法。

2 基于路段的時間依賴網絡模型

基于路段的時間依賴網絡模型定義如下: GL=(L,U,W,D)。其中,L={0,1,…,n-1}表示有向路段集。U?{(i,j)|(i,j)∈L×L,e(i)=s(j)}表示轉向集,其中e(i)表示路段 i的終止節點,s(j)表示路段j的起始節點。W={wi(t)|i∈L,t∈T}表示時間依賴路段行程時間集,其中wi(t)表示t時刻在路段i上的行程時間,T表示時間集。D= {dij(t)|(i,j)∈U,t∈T}表示時間依賴轉向延誤時間集,其中,dij(t)表示 t時刻于交叉口(即e(i)或s(j))處由路段i轉向路段j的延誤時間。

設 ai(t)表示t時刻從節點s(i)出發沿路段i到達其相鄰節點e(i)的時間,有ai(t)=t+wi(t)。設rij(t)表示t時刻從節點s(i)出發沿路段i轉入相鄰路段j的時間,有

設 p={i1,i2,…,im}(m>1)為路段 i1到路段im的一條路徑,其中,e(i1)=s(i2),…,e(im-1) =s(im),則其到達時間定義如下

設 P(o,d)為路段 o到路段 d的所有路徑, EAod(t)為 t時刻從路段o出發最早到達路段 d的時間,則有 EAod(t)=min{ap(t):p∈P(o,d)}。計算 EAod(t)的過程也就是求解 o-d時間最短路徑的過程。

FIFO條件 對于網絡中的每一個轉向(i,j)∈U,如果 rij(t)非減,即

則稱網絡滿足先進先出(first in first out, FIFO)條件。文獻[4]指出,FIFO網絡中的最短路徑問題可以使用改進的Dijkstra、A＊等算法來求解。根據公式(1),要使不等式(3)成立,則路段到達時間函數ai(t)與轉向延誤函數dij(t)必須同時滿足FIFO條件,即

3 滿足FIFO條件的路段到達時間與轉向延誤時間

3.1 路段到達時間

在對路段i∈L的交通狀況進行建模時,通常將連續時間 T劃分成若干時段[t0,t1),…,[tf-1, tf),并認為每個時段[tk,tk+1)內的交通流速度 vk穩定。這樣,路段上的一個行程可能跨越速度值不同的多個時段,其滿足FIFO條件的到達時間ai(t)計算如下(其中 l表示路段i的長度)[5]

式中,

3.2 轉向延誤時間

在處理轉向延誤時間時,也將連續時間 T離散化為多個時段[t0,t1),…,[th-1,th),并認為每個時段[tk,tk+1)內的平均延誤時間恒定為 ck(ck值的確定是交通工程學中交通流理論研究的重要內容)。這樣,車輛實際的轉向延誤時間可通過如下公式來計算

此計算過程考慮了跨越兩個時段的情況(現實應用中轉向等待不太可能跨越兩個以上時段),能保證先排隊的車輛先轉入下一條路段,即滿足FIFO條件。

4 基于路段標號的時間依賴A＊算法

A＊最短路徑算法以啟發式評估函數作為節點標號,通過賦予位于最短路徑上可能性高的節點以高的優先級,來達到縮減搜索空間的目的[2]。在基于路段的時間依賴網絡中,啟發式評估函數定義為

式中,t為出發時間;ap→i(t)為沿評估路徑 p到達當前路段i的時間(根據式(2)計算);e(i,d)(ap→i(t))為ap→i(t)時刻從當前路段i到目標路段d的行程時間的估計。啟發式函數 e(i,d)(ap→i(t))的設定則是一個事關算法效率的關鍵性問題。如果其值不超過相應的實際最小行程時間(即滿足可納性),則能保證找到數學最優解[7]。鑒于此,本文令

式中,D(i,d)為當前路段 i到目標路段d的歐式距離(通過節點e(i)和節點e(d)的坐標計算而得); Vmax為所有路段最大可能的行車速度。

基于路段標號的時間依賴A＊(time-dependent A＊,TDA＊)算法的基本思想如下:從起始路段出發,循環從候選路段集中選取標號 Fi(t)最小的路段擴展生成后續路段并更新其標號值,標號更新后的路段作為下一次的選取對象再插入到候選路段集中。設o為起始路段,d為終止路段,t為從節點s(o)出發的時間,Pi為路段i在路徑上的直接前驅路段,Q為候選路段集,R為永久標號路段集(到此集合中的路段的最短路徑已經找到),則TDA＊算法的流程如下(其中,A rrival(i,t)為基于式(5)的路段到達時間計算函數,Turn(i,j,t)為基于式(6)的轉向延誤時間計算函數):

1.初始化。令 ap→o=A rrival(o,t),Fo= ap→o+D(o,d)/Vmax,Fj=ap→j= ∞ ?j≠o,Po= -1,Q={o}。

2.路段選擇。從候選路段集Q中選出Fi值最小的路段i,并將之永久標號,即:

如果i==d,則目標路段已找到,循環終止。否則:

3.路段擴展。對于路段i的每一條后繼路段j∈L,(i,j)∈U,如果它還未永久標記,即 j?R,且ap→i+Turn(i,j,ap→i)+A rrival(j,ap→i+Turn(i, j,ap→i))+D(j,d)/Vmax

4.搜索終止。如果所有路段都擴展完,即Q=?,則終止循環;否則轉向步驟2。

5 試 驗

本文在課題組自主開發的城市公眾出行路徑規劃服務系統為試驗平臺(雙核CPU 1.6 GHz,內存1.0 GB,操作系統Windows XP professional SP3)上對所提出的算法進行了驗證與測試。

5.1 數據準備

試驗路網采用北京市四環以內雙線表達的導航路網,共有路段25 602條(交叉路口處的虛擬路段和虛擬節點概化為單一的拓撲節點)。交通數據采用北京市2007年7、8、9三個月的以5 min為周期的浮動車實測車速數據,一天分為288個時段。考慮到交通流的周期性變化規律,對所有屬于同一日期類別同一時段的速度值進行平均化處理,形成了從星期一到星期日的7個速度數據集。目前的交通數據中,共有4 929條路段有交通信息,基本上覆蓋了主要道路。而對于交通信息不能覆蓋的路段,根據道路類型和進入時間設置默認速度值如表1所示。

表1 預定義的道路速度Tab 1 Predefined speeds on different road types /(km/h)

另外,考慮到準確可用的轉向延誤數據難以獲得,作者從交叉口綠信比的角度考慮,以時段和轉向類型為依據,為所有轉向建立了一個簡單的延誤模型:fij(t)=0.5×g(t,ty peij)(見3.2節)。其中,0.5表示交叉口等待的概率,g(t,ty peij)的取值如表2所示。

表2 簡單的時間依賴轉向延誤模型Tab.2 A naive model for time-dependent turn delays /min

5.2 算法準備

TDA＊算法使用四叉堆優先級隊列來實現候選路段集[18],并基于經驗將所有路段的最大可能行車速度設置為60 km/h。為了算法比較的需要,作者實現了 RTA＊(real-time A＊)算法和RTA＊_M算法。RTA＊算法是指僅考慮出發時刻交通信息的A＊算法,它與靜態A＊算法的區別僅在于以當前交通信息而不是長度/限速作為路段的權值。RTA＊_M算法是指整個導航過程中的多次RTA＊算法調用。該算法的基本流程如下:①出發前利用RTA＊算法計算一條最優路徑;②沿著規劃路徑行進,每當有新的交通信息到來時(根據歷史交通數據進行模擬,以每5 min為一個周期),調用 RTA＊算法計算新的路徑;③步驟②循環直至抵達目的地。RTA＊_M算法的計算時間為多次RTA＊算法計算時間的和,路徑為多次重計算后完整的行車路徑。

5.3 試驗結果與算法分析

為了驗證TDA＊算法的有效性,選取北辰東路為起始路段,翠微路為終止路段,設置出發時間為周二上午7:00和8:00,分別利用 TDA＊算法和RTA＊算法進行計算,結果如圖1和圖2所示。

圖1 TDA＊算法與RTA＊算法計算結果的比較(出發時間:7:00)Fig.1 Comparison of computational results of TDA＊and RTA＊(departure time:7:00)

圖2 TDA＊算法與RTA＊算法計算結果的比較(出發時間:8:00)Fig.2 Comparison of computational results of TDA＊and RTA＊(departure time:8:00)

從圖1可以看出,7:00出發時,TDA＊算法預測出車輛到達時刻三環路上將發生交通擁堵,因此建議繞道四環以避之。而RTA＊算法由于只考慮當前時刻的交通狀況,因此當車輛沿其規劃的路徑到達三環路上時,將會遇到交通擁堵。

從圖2可以看出,8:00出發時,三環路上正好發生交通擁堵,RTA＊算法基于此建議走四環以避之,而事實上,當車輛到達三環路時,交通擁堵狀況可能已經緩解。與此相反,TDA＊算法在出發時就預測到三環路上擁堵狀況即將緩解的趨勢,因此建議一條看似擁堵而實際并不擁堵的路徑(即三環路),有效地避免了不必要的繞道。

為了測試TDA＊算法的效率與精度,以周二上午7:30為出發時間,從網絡中任意選取30對OD路段,分別利用 TDA＊算法、RTA＊算法和RTA＊_M算法計算每對OD間的時間最短路徑。結果如圖3、圖4和圖5所示(橫軸表示30條按長度從小到大排序的路徑)。

圖3 TDA＊算法與RTA＊_M算法所計算路徑行程時間的比較Fig.3 Comparison of travel times of computational paths of TDA＊and RTA＊_M

圖4 TDA＊算法與RTA＊算法計算時間的比較Fig.4 Comparison of computational times of TDA＊and RTA＊

從圖3可以看出,總體而言,相比于RTA＊_ M算法,TDA＊算法所計算路徑的行程時間更短。不過這種優勢并不明顯,主要原因在于: RTA＊_M算法也考慮了回避交通擁堵的情況,在經過多次路徑調整后,RTA＊_M算法所得路徑的行程時間比 TDA＊算法所得路徑的行程時間多得有限,這種現象在路段行車速度長時間沒有大的變化的情況下,表現得更為明顯。當然,交通信息覆蓋率不高、行程時間預測模型與轉向延誤模型存在一定的誤差等也是一部分影響因素,但影響大小的定量測試需要高質量交通數據以及準確的行程時間預測模型和轉向延誤計算模型的支持。

圖5 TDA＊算法與RTA＊_M算法計算時間的比較Fig.5 Comparison of computational times of TDA＊and RTA＊_M

從圖4可以看出,TDA＊算法的計算時間比RTA＊算法略有增加,平均幅度大約為10%。其中多出的時間主要用于路段到達時間和轉向延誤時間的計算。

從圖5可以看出,TDA＊算法的計算時間遠少于RTA＊_M算法。原因在于導航過程中需要多次調用RTA＊算法以進行路徑的優化與重優化,而TDA＊算法由于預先考慮了到達時刻路段的交通狀況,整個導航過程只需一次調用即可。可見,TDA＊算法有助于降低導航過程中路徑規劃的頻率,從而提高導航系統的整體效率。

6 結 論

面向帶轉向延誤的時間依賴最短路徑問題,本文通過定義基于路段的時間依賴網絡模型,并將轉向延誤引入到FIFO條件的定義中,發展了基于路段標號的時間依賴A＊最短路徑算法。該算法能預測并回避即將發生的交通擁堵,有效節省用戶出行時間、提高導航系統整體運行效率,具有較強的實用價值。

TDA＊算法的精度和可用性與行程時間數據和轉向延誤數據的準確性直接相關,本文只是簡單對歷史交通數據作了均化處理,轉向延誤使用的也僅是經驗值。在后續工作中將深入探討準確可用的路段行程時間預測模型與交叉口轉向延誤計算模型。

[1] LU Feng,ZHENG Nianbo,DUAN Yingying,et al.Travel Information Services:State of the Art and Discussion on Crucial Technologies[J].Journal of Image and Graphics, 2009,14(7):1219-1229.(陸鋒,鄭年波,段瀅瀅,等.出行信息服務關鍵技術研究進展與問題探討[J].中國圖象圖形學報,2009,14(7):1219-1229.)

[2] FU L,SUN D,RILETT L R.Heuristic Shortest Path Algorithms for Transportation Applications:State of the Art[J].Computers&Operation Research,2006,33(11): 3324-3343.

[3] HUANG B,WU Q,ZHAN F B.A Shortest Path Algorithm with Novel Heuristics for Dynamic Transportation Networks[J]. InternationalJournalof Geographical Information Science,2007,21(6):625-644.

[4] KAUFMAN D E,SMITH R L.Fastest Paths in Timedependent Networks for Intelligent Vehicle-Highway Systems Application[J].Journal of Intelligent Transportation Systems,1993,1(1):1-11.

[5] SUNG K,BELL M G H,SEONG M,et al.Shortest Paths in a Network with Time-dependent Flow Speeds[J].European Journal of Operational Research,2000,121(1): 32-39.

[6] HORN M.Efficient Modeling of Travel in Networks with Time-Varying Link Speeds[J].Networks,2000,36(2): 80-90.

[7] CHABINI I,LAN S.Adaptations of the A＊Algorithm for the Computation of Fastest Paths in Deterministic Discrete-Time DynamicNetworks[J]. IEEE Transactions on Intelligent Transportation Systems,2002,3(1):60-74.

[8] KANOULAS E,DU Y,XIA T,et al.Finding Fastest Paths on a Road Network with Speed Patterns[C]∥Proc of the 22nd International Conference on Data Engineering. Washington D C:IEEE Computer Society,2006.

[9] NANNICINI G,LIBERTI L.Shortest Paths on Dynamic Graphs[J]. International Transactions in Operational Research,2008.15(5):551-564.

[10] HAN Gang,J IANGJie,CHEN Jun,et al.An Arc Based Dijkstra Algorithm for Road Turning Penalty in Vehicle Navigation System[J].Acta Geodaetica et Cartographic Sinica,2002,31(4):366-368.(韓剛,蔣捷,陳軍,等.車載導航系統中顧及道路轉向限制的路段Dijkstra算法[J].測繪學報,2002,31(4):366-368.)

[11] REN Gang,WANG Wei,DENG Wei.Shortest Path Problem with Turn Penalties and Prohibitions and Its Solutions[J].Journal of Southeast University:Natural Science Edition,2004,34(1):104-108.(任剛,王煒,鄧衛.帶轉向延誤和限制的最短路徑問題及其求解方法[J].東南大學學報:自然科學版,2004,34(1): 104-108.)

[12] CALDWELL T.On Finding Minimum Routes in a Network with Turn Penalties[J].Communications of the ACM, 1961,4(2):108.

[13] ZHENG Nianbo,LI Qingquan,XU Jinghai,et al.A BidirectionalHeuristic ShortestPath Algorithm with Turn Prohibitionsand Delays[J]. Geomaticsand Information Science of Wuhan University,2006,31(3): 256-259.(鄭年波,李清泉,徐敬海,等.基于轉向限制和延誤的雙向啟發式最短路徑算法[J].武漢大學學報:信息科學版,2006,31(3):256-259.)

[14] GAO Song,LU Feng.An Arc-labeling Shortest Time Path Algorithm[J].Geo-Information Science,2008,10 (5):604-610.(高松,陸鋒.基于路段標記的交通網絡時間最短路徑算法[J].地球信息科學,2008,10(5): 604-610.)

[15] GUTIéRREZ E,MEDAGLIA A L.Labeling Algorithm for the Shortest Path Problem with Turn Prohibitions with Application to Large-scaleRoad Networks[J]. Annals of Operations Research,2007,157(1):169-182.

[16] A?EZ J,DE LA BARRA T,PéREZ B.Dual Graph Representation of Transport Networks[J].Transportation Research Part B:Methodological,1996,30(3): 209-216.

[17] WINTER S.Modeling Costs of Turns in Route Planning [J].GeoInformatica,2002.6(4):345-361.

[18] LU Feng,LU Dongmei,CUI Weihong.Improved Dijkstra Algorithm Based on Quad-Heap PriorityQueueand Inverse Adjacent List[J].Journal of Image and Graphics, 1999,4A(12):1044-1050.(陸鋒,盧冬梅,崔偉宏.基于四叉堆優先級隊列及逆鄰接表的改進型Dijkstra算法[J].中國圖象圖形學報,1999,4A(12):1044-1050.)

The Adaption of A＊Algorithm for Least-time Paths in Time-dependent Transportation Networks with Turn Delays

ZHENGNianbo1,LU Feng1,LI Qingquan2,DUAN Yingying1
1.State Key Laboratory of Resources and Environmental Information System,Institute of Geographic Sciences and Natural Resources Research,Chinese Academy of Sciences,Beijing 100101,China;2.Transportation Research Center,Wuhan University, Wuhan 430079,China

A link-based time-dependent network model was built by introducing the turn delay time into the definition of“first in first out(FIFO)”condition.A link-labelling time-dependent A＊shortest path algorithm is developed by adapting temporally the heuristic evaluationfunction and using Euclidian distance divided by maximum possible driving speed as the heuristic evaluator.An experiment on the real road network showed that the proposed algorithm is capable of forecasting and bypassing those forthcoming traffic congestions and then shortening travel time,only with a cost of about 10%more computational time than the traditional algorithms.Moreover,it is able to improve overall efficiency of route planning heavily because the frequent path re-optimization processes are no longer needed.

route planning;shortest path;A＊algorithm;time-dependent network;turn delay

ZHENG Nianbo(1979—),male,postdoctoral,majors in geographic information systems for transportation,intelligent transportation systems and spatial information services.

1001-1595(2010)05-0534-06

P208

A

國家863計劃(2007AA12Z241);國家自然科學基金(40871184,40830530);中國博士后基金(20090450563)

(責任編輯:叢樹平)

2009-09-14

2010-01-07

鄭年波(1979—),男,博士后,主要從事GIS-T、ITS、空間信息服務等研究。

E-mail:zhengnb@lreis.ac.cn