一種基于A*算法的動態(tài)多路徑規(guī)劃算法

劉 斌，陳賢富，程 政

(中國科學技術大學 信息科學技術學院，安徽 合肥 230027)

一種基于A*算法的動態(tài)多路徑規(guī)劃算法

劉 斌，陳賢富，程 政

(中國科學技術大學 信息科學技術學院，安徽 合肥 230027)

車載導航系統(tǒng)中最重要的功能是路徑規(guī)劃，傳統(tǒng)車載導航設備大多采用靜態(tài)算法，沒有采用實時交通信息規(guī)劃出的路徑可能不是最優(yōu)路徑。結合一種動態(tài)行程時間表對傳統(tǒng)A*算法進行調整，可以有效利用路網實時交通數據規(guī)避擁堵路線，從而實現動態(tài)路徑規(guī)劃。另外，實際應用中，單一的優(yōu)化路徑往往不能滿足需求，對此提出重復路徑懲罰因子的概念，構造出了一種多路徑規(guī)劃算法，可以在路徑相似度與路徑通行代價之間取得平衡，避免了傳統(tǒng)K最短路徑(K Shortest Paths, KSP)算法路徑相似度過高的缺點。

動態(tài)路徑規(guī)劃；A*算法；動態(tài)行程時間表；重復路徑懲罰因子；KSP

0 引言

路徑規(guī)劃算法是智能交通系統(tǒng)(Intelligent Transportation Systems, ITS)的重要組成部分之一，盡管現實世界的實時交通信息在不斷變化，但目前大部分車載導航系統(tǒng)采用的仍是靜態(tài)的路徑規(guī)劃算法[1]，如A*算法[2]、Dijkstra算法[3]。此類算法假定道路通行代價不會改變，大多采用道路長度、寬度等靜態(tài)屬性作為路權計算方式，不能反映實時動態(tài)路況。

針對動態(tài)路徑規(guī)劃算法，參考文獻[4]采用D*star算法對A*算法進行了改進；參考文獻[5]針對道路的動態(tài)通行時間計算問題，提出了一種路網中道路動態(tài)通行時間表，表中記錄了每個路段每個時間段的行程時間，由此得出了車輛經過路段的通行時間計算方法。

以上算法在點對點的路徑規(guī)劃中，只能得出單條優(yōu)化路徑，在實際應用中往往不能滿足需求。對此存在許多一次可以求出多條優(yōu)化路徑的算法，稱為KSP算法。參考文獻[6]通過設置標號的辦法得到K條最短路徑；參考文獻[7]提出了一種新的多標號算法來解決KSP問題。但上述KSP算法均存在路徑相似度較高的缺點。參考文獻[8-9]提出的算法可以求出一組邊不相交鏈路，但各條路徑相差較大。

本文通過分析上述算法的優(yōu)缺點，結合A*算法與動態(tài)行程時間表，為減少接收行程時間表時的通信量，結合矩形限制搜索區(qū)域算法[10]，給出了一種求解單一優(yōu)化路徑的動態(tài)路徑規(guī)劃算法。同時提出一種重復路徑懲罰因子，可以利用它一次搜索出多條優(yōu)化路徑，所求得的K條路徑可以兼顧路徑相似度與路徑通行代價。

1 A*算法

A*算法是一種典型的啟發(fā)式搜索算法，建立在Dijkstra算法的基礎之上，廣泛應用于游戲地圖、現實世界中，用來尋找兩點之間的最短路徑。A*算法最主要的是維護了一個啟發(fā)式估價函數，如式(1)所示。

f(n)=g(n)+h(n)

(1)

其中，f(n)是算法在搜索到每個節(jié)點時，其對應的啟發(fā)函數。它由兩部分組成，第一部分g(n)是起始節(jié)點到當前節(jié)點實際的通行代價，第二部分h(n)是當前節(jié)點到終點的通行代價的估計值。算法每次在擴展時，都選取f(n)值最小的那個節(jié)點作為最優(yōu)路徑上的下一個節(jié)點。

在實際應用中，若以最短路程為優(yōu)化目標，h(n)常取作當前點到終點的歐幾里得距離(Euclidean Distance)或曼哈頓距離(Manhattan Distance)等。若令h(n)=0，表示沒有利用任何當前節(jié)點與終點的信息，A*算法就退化為非啟發(fā)的Dijkstra算法，算法搜索空間隨之變大，搜索時間變長。

A*算法步驟如下，算法維護兩個集合：P表與Q表。P表存放那些已經搜索到、但還沒加入最優(yōu)路徑樹上的節(jié)點；Q表維護那些已加入最優(yōu)路徑樹上的節(jié)點。

(1)P表、Q表置空，將起點S加入P表，其g值置0，父節(jié)點為空，路網中其他節(jié)點g值置為無窮大。

(2)若P表為空，則算法失敗。否則選取P表中f值最小的那個節(jié)點，記為BT，將其加入Q表中。判斷BT是否為終點T，若是，轉到步驟(3)；否則根據路網拓撲屬性和交通規(guī)則找到BT的每個鄰接節(jié)點NT，進行下列步驟:

①計算NT的啟發(fā)值

f(NT)=g(NT)+h(NT)

(2)

g(NT)=g(BT)+cost(BT, NT)

(3)

其中,cost(BT, NT)是BT到NT的通行代價。

②如果NT在P表中，且通過式(3)計算的g值比NT原先的g值小，則將NT的g值更新為式(3)結果，并將NT的父節(jié)點設為BT。

③如果NT在Q表中，且通過式(3)計算的g值比NT原先的g值小，則將NT的g值更新為式(3)結果，將NT的父節(jié)點設為BT，并將NT移出到P表中。

④若NT既不在P表，也不在Q表中，則將NT的父節(jié)點設為BT，并將NT移到P表中。

⑤轉到步驟(2)繼續(xù)執(zhí)行。

(3)從終點T回溯，依次找到父節(jié)點，并加入優(yōu)化路徑中，直到起點S，即可得出優(yōu)化路徑。

2 動態(tài)行程時間表及A*算法調整

2.1 動態(tài)行程時間表

為計算在實時情況下某段道路的通行時間，采用了一種道路通行時間表的結構，表中存放了道路當前時刻的通行時間以及未來幾個時刻通行時間的預測值。

以t0表示導航系統(tǒng)開始工作的時刻，將未來一段時間劃分為若干個時段，以ΔT表示一個時段的長度，系統(tǒng)開始工作的時刻屬于第一個時段。然后對這些時段進行編號，如1,2,3,4，…。同理，也將每條道路編號為1,2,3,4，…。采用Tij表示路段i在時段j的通行時間。這樣就可得到不同道路在不同時刻的通行時間，將它們記錄為表1。

表1 道路動態(tài)通行時間表(s)

車載系統(tǒng)可能會在某個時刻進行路徑規(guī)劃，優(yōu)化路徑上可能會包含多個路段，將它們編號為1,2,3,…，k,…。以[tk,tk′]表示車輛經過路段k的通行時間Tk,則Tk=tk′-tk。車輛可能會花費多個時段才能通過路段k，將這些時段與通行時間Tk1′,Tk2′,Tk3′,…對應。

首先計算出車輛經過路段k起點的時刻對應的時段fk:

(4)

其中，?」符號表示對結果取下整。則相應地可得出：

(5)

根據時段長度ΔT、道路長度L與道路通行速度的不同取值，可能會出現車輛只需在一個時段即可通過路段，也可能需要多個時段才能通過。因此經過牛頓運動學原理進行計算，可得到車輛通過路段k的具體公式如下[9]：

(6)

其中，m的取值滿足：

(7)

2.2 A*算法調整

在得出車輛通過路段k的計算方法后，即可對傳統(tǒng)A*算法進行調整，以搜索出動態(tài)優(yōu)化路徑。具體如下：

在A*算法描述的第(2)步中，首先計算出起點S到達BT的通行時間t，則到達BT的時刻為出發(fā)時刻加上t，記為tBT，然后根據式(6)計算出BT到達NT的通行時間T。則可更新g(NT)為：

g(NT)=g(BT)+T+tli

(8)

其中，tli表示路口紅綠燈等待時間。除了這些調整外，前述A*算法的其他部分不需要改變。

3 動態(tài)多路徑規(guī)劃算法

3.1 算法描述

利用這些符號，算法可描述如下：

(1)設置MO、β和K，令n=0;

(2)利用調整后的A*算法搜索出一條優(yōu)化路徑,將其加入PC中，n=1;

(3)若n大于等于K，算法結束，否則將Pn上每一條路段的通行代價都乘以PO;

(4)路徑規(guī)劃與相似度計算：

①n=n+1;

② 利用改造A*算法規(guī)劃出下一條優(yōu)化路徑Pn;

③ 計算相似度：

Dnk=OLnk/Ln，k=n-1,n-2,…，1

④路徑相似度判斷：

若Dnk>MO，算法結束，否則將Pn加入 PC，轉步驟(3)。

利用此算法最多可以求出K條優(yōu)化路徑，各條優(yōu)化路徑的通行代價與相似度取決于MO與β的取值。當MO=1.0時，相當于沒有懲罰，此時只能得出一條路徑；當MO<1.0時,可以得到多條路徑。

3.2 實驗結果

圖1 本文算法規(guī)劃結果

本文采用真實的合肥城區(qū)電子地圖數據，構建了一個C/S(Client/Server)模型，由服務器端模擬產生實時交通數據，每條道路的通行時間范圍為道路暢通時的時間到7倍于它之間的一個隨機值。在車載終端請求實時數據時，終端會發(fā)送起點、終點坐標值給服務器，服務器采用矩形限制搜索區(qū)域算法,大大減少了通信的數據量。

以從“中國科學技術大學第一教學樓”到“安徽大學新校區(qū)”為例，規(guī)劃結果如圖1所示。 其中的參數設置為：MO=0.5，β=1.8，K=3。優(yōu)化3條路徑。路徑長度與相似度統(tǒng)計如表2所示。

表2 優(yōu)化路徑通行代價與相似度

其中最大相似度表示的是此道路與標號小于它的那些道路的最大D值。作為對比，百度地圖的搜索結果如圖2所示。

圖2 百度地圖規(guī)劃結果

3條道路的長度分別為14.3 km、16.4 km與19.1 km。

4 結論

在本文中，提出了一種基于傳統(tǒng)A*搜索算法，并結合動態(tài)通行時間表、矩形限制搜索區(qū)域算法與道路相似度懲罰因子的多優(yōu)化路徑規(guī)劃算法。實驗結果顯示，在給定起點和終點的情況下，本文提出的算法能有效規(guī)劃出在通行代價與路徑相似度之間取得平衡的多條路徑，有效解決了傳統(tǒng)KSP算法路徑相似度過高的缺點，同時提高了算法的實時性。

[1] NADI S, DELAVAR M R. Location-based service for In-vehicle route guidance with real time traffic information[C].The 12th World Conference on Transport Research (WSTR to WCTR) Proceedings, 2010: 1-10.

[2] GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: efficient point-to-point shortest path algorithms[C].ALENEX, 2006, 6(2): 129-143.

[3] M?HRING R H, SCHILLING H, SCHüTZ B, et al. Partitioning graphs to speed up Dijkstra’s algorithm[M].Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2005,11(2-8): 189-202.

[4] 隨裕猛, 陳賢富, 劉斌. D-star Lite 算法及其動態(tài)路徑規(guī)劃實驗研究[J]. 微型機與應用, 2015, 34(7): 16-19.

[5] 蘇永云, 晏克非. 車輛導航系統(tǒng)的動態(tài)最優(yōu)路徑搜索方法研究[J]. 系統(tǒng)工程, 2000, 18(4): 32-37.

[6] DREYFUS S E. An appraisal of some shortest-path algorithms[J]. Operations research, 1969, 17(3): 395-412.

[7] PALUCH S. A multi label algorithm for k shortest paths problem[J].Communications, 2007, 3(2009): 11-14.

[8] CIDON I, RON R, SHAVITT Y. Analysis of multi-path routing[J]. IEEE/ACM Transactions on Networking (TON), 1999, 7(6): 885-896.

[9] HOCHSTEIN J M, WEIHE K. Edge-disjoint routing in plane switch graphs in linear time[J]. Journal of the ACM (JACM), 2004, 51(4): 636-670.

[10] 許震洪. 動態(tài)路徑誘導系統(tǒng)的最優(yōu)路徑算法研究及相關軟件實現[D]. 南京：南京理工大學，2004.

A dynamic multi-route plan algorithm based on A*algorithm

Liu Bin, Chen Xianfu, Cheng Zheng

(School of Information Science and Technology, University of Science and Technology of China, Hefei 230027, China)

The most important function in vehicle navigation system is the path planning. The traditional vehicle navigation equipments mostly adopt the static algorithm which does not utilize real time traffic information, and the result of planning algorithm may not be the optimal one. In this paper, we adjust the traditional A*algorithm combining with a dynamic travel time table, which can effectively utilize real time traffic data of network to avoid congested routes, so as to realize the dynamic route planning. In addition, in the practical application, only one single optimization path often can’t meet the demand of users, so this paper puts forward a concept of penalty factor of overlap path, then constructs a multi-route planning algorithm. As a result, the proposed algorithm can gets a balance between path similarity and path travel cost, avoiding the weakness in traditional K shortest paths (KSP) algorithm which refers to high path similarity among determined paths.

dynamic route planning; A*algorithm; dynamic travel time table, penalty factor; KSP

TP391；U491

A

1674-7720(2016)04-0017-03

劉斌，陳賢富，程政．一種基于A*算法的動態(tài)多路徑規(guī)劃算法[J] .微型機與應用，2016，35(4)：17-19,26.

2015-10-27)

劉斌(1992-)，男,碩士研究生,主要研究方向：智能信息處理。

陳賢富(1963-),男,博士,副教授,主要研究方向：復雜系統(tǒng)與計算智能。

程政(1990-),男,碩士研究生,主要研究方向：智能信息處理。