劉 斌，陳賢富，程 政

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

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

劉 斌，陳賢富，程 政

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

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

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

0 引言

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

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

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

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

1 A*算法

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

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

(1)

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

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

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

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

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

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

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

(2)

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

(3)

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

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

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

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

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

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

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

2.1 動(dòng)態(tài)行程時(shí)間表

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

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

表1 道路動(dòng)態(tài)通行時(shí)間表(s)

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

首先計(jì)算出車輛經(jīng)過(guò)路段k起點(diǎn)的時(shí)刻對(duì)應(yīng)的時(shí)段fk:

(4)

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

(5)

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

(6)

其中，m的取值滿足：

(7)

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

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

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

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

(8)

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

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

3.1 算法描述

利用這些符號(hào)，算法可描述如下：

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

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

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

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

①n=n+1;

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

③ 計(jì)算相似度：

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

④路徑相似度判斷：

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

3條道路的長(zhǎng)度分別為14.3 km、16.4 km與19.1 km。

4 結(jié)論

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

[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 算法及其動(dòng)態(tài)路徑規(guī)劃實(shí)驗(yàn)研究[J]. 微型機(jī)與應(yīng)用, 2015, 34(7): 16-19.

[5] 蘇永云, 晏克非. 車輛導(dǎo)航系統(tǒng)的動(dò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] 許震洪. 動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)的最優(yōu)路徑算法研究及相關(guān)軟件實(shí)現(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*算法的動(dòng)態(tài)多路徑規(guī)劃算法[J] .微型機(jī)與應(yīng)用，2016，35(4)：17-19,26.

2015-10-27)

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

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

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