劉 斌，陳賢富，程 政

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

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

劉 斌，陳賢富，程 政

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

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

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

0 引言

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

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

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

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

1 A*算法

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

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

(1)

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

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

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

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

(2)若P表為空，則算法失敗。否則選取P表中f值最小的那個節(jié)點，記為BT，將其加入Q表中。判斷BT是否為終點T，若是，轉(zhuǎn)到步驟(3)；否則根據(jù)路網(wǎng)拓?fù)鋵傩院徒煌ㄒ?guī)則找到BT的每個鄰接節(jié)點NT，進(jìn)行下列步驟:

①計算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)結(jié)果，并將NT的父節(jié)點設(shè)為BT。

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

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

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

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

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

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

為計算在實時情況下某段道路的通行時間，采用了一種道路通行時間表的結(jié)構(gòu)，表中存放了道路當(dāng)前時刻的通行時間以及未來幾個時刻通行時間的預(yù)測值。

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

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

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

首先計算出車輛經(jīng)過路段k起點的時刻對應(yīng)的時段fk:

(4)

其中，?」符號表示對結(jié)果取下整。則相應(yīng)地可得出：

(5)

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

(6)

其中，m的取值滿足：

(7)

2.2 A*算法調(diào)整

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

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

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

(8)

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

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

3.1 算法描述

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

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

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

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

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

①n=n+1;

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

③ 計算相似度：

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

④路徑相似度判斷：

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

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

3.2 實驗結(jié)果

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

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

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

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

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

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

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

4 結(jié)論

在本文中，提出了一種基于傳統(tǒng)A*搜索算法，并結(jié)合動態(tài)通行時間表、矩形限制搜索區(qū)域算法與道路相似度懲罰因子的多優(yōu)化路徑規(guī)劃算法。實驗結(jié)果顯示，在給定起點和終點的情況下，本文提出的算法能有效規(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]. 微型機(jī)與應(yīng)用, 2015, 34(7): 16-19.

[5] 蘇永云, 晏克非. 車輛導(dǎo)航系統(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)路徑誘導(dǎo)系統(tǒng)的最優(yōu)路徑算法研究及相關(guān)軟件實現(xiàn)[D]. 南京：南京理工大學(xué)，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] .微型機(jī)與應(yīng)用，2016，35(4)：17-19,26.

2015-10-27)

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

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

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