劉斌，陳賢富，程政
?。ㄖ袊茖W(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*算法進行調(diào)整，可以有效利用路網(wǎng)實時交通數(shù)據(jù)規(guī)避擁堵路線，從而實現(xiàn)動態(tài)路徑規(guī)劃。另外，實際應(yīng)用中，單一的優(yōu)化路徑往往不能滿足需求，對此提出重復(fù)路徑懲罰因子的概念，構(gòu)造出了一種多路徑規(guī)劃算法，可以在路徑相似度與路徑通行代價之間取得平衡，避免了傳統(tǒng)Ｋ最短路徑(K Shortest Paths, KSP)算法路徑相似度過高的缺點。
關(guān)鍵詞：動態(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ī)劃算法，參考文獻［4］采用D* star算法對A*算法進行了改進；參考文獻［5］針對道路的動態(tài)通行時間計算問題，提出了一種路網(wǎng)中道路動態(tài)通行時間表，表中記錄了每個路段每個時間段的行程時間，由此得出了車輛經(jīng)過路段的通行時間計算方法。
以上算法在點對點的路徑規(guī)劃中，只能得出單條優(yōu)化路徑，在實際應(yīng)用中往往不能滿足需求。對此存在許多一次可以求出多條優(yōu)化路徑的算法，稱為KSP算法。參考文獻［6］通過設(shè)置標號的辦法得到K條最短路徑；參考文獻［7］提出了一種新的多標號算法來解決KSP問題。但上述KSP算法均存在路徑相似度較高的缺點。參考文獻［8-9］提出的算法可以求出一組邊不相交鏈路，但各條路徑相差較大。
本文通過分析上述算法的優(yōu)缺點，結(jié)合A*算法與動態(tài)行程時間表，為減少接收行程時間表時的通信量，結(jié)合矩形限制搜索區(qū)域算法［10］，給出了一種求解單一優(yōu)化路徑的動態(tài)路徑規(guī)劃算法。同時提出一種重復(fù)路徑懲罰因子，可以利用它一次搜索出多條優(yōu)化路徑，所求得的K條路徑可以兼顧路徑相似度與路徑通行代價。
1A*算法
A*算法是一種典型的啟發(fā)式搜索算法，建立在Dijkstra算法的基礎(chǔ)之上，廣泛應(yīng)用于游戲地圖、現(xiàn)實世界中，用來尋找兩點之間的最短路徑。A*算法最主要的是維護了一個啟發(fā)式估價函數(shù)，如式(1)所示。
f(n)=g(n)+h(n)(1)
其中，f(n)是算法在搜索到每個節(jié)點時，其對應(yīng)的啟發(fā)函數(shù)。它由兩部分組成，第一部分g(n)是起始節(jié)點到當前節(jié)點實際的通行代價，第二部分h(n)是當前節(jié)點到終點的通行代價的估計值。算法每次在擴展時，都選取f(n)值最小的那個節(jié)點作為最優(yōu)路徑上的下一個節(jié)點。
在實際應(yīng)用中，若以最短路程為優(yōu)化目標，h(n)常取作當前點到終點的歐幾里得距離(Euclidean Distance)或曼哈頓距離(Manhattan Distance)等。若令h(n)=0，表示沒有利用任何當前節(jié)點與終點的信息，A*算法就退化為非啟發(fā)的Dijkstra算法，算法搜索空間隨之變大，搜索時間變長。
A*算法步驟如下，算法維護兩個集合：P表與Q表。P表存放那些已經(jīng)搜索到、但還沒加入最優(yōu)路徑樹上的節(jié)點；Q表維護那些已加入最優(yōu)路徑樹上的節(jié)點。
?。?）P表、Q表置空，將起點S加入P表，其g值置0，父節(jié)點為空，路網(wǎng)中其他節(jié)點g值置為無窮大。
?。?）若P表為空，則算法失敗。否則選取P表中f值最小的那個節(jié)點，記為BT，將其加入Q表中。判斷BT是否為終點T，若是，轉(zhuǎn)到步驟（3）；否則根據(jù)路網(wǎng)拓撲屬性和交通規(guī)則找到BT的每個鄰接節(jié)點NT，進行下列步驟:
?、儆嬎鉔T的啟發(fā)值
f(NT)=g(NT)+h(NT)(2)
g(NT)=g(BT)+cost(BT, NT)(3)
其中,cost(BT, NT)是BT到NT的通行代價。
?、谌绻鸑T在P表中，且通過式(3)計算的g值比NT原先的g值小，則將NT的g值更新為式(3)結(jié)果，并將NT的父節(jié)點設(shè)為BT。
?、廴绻鸑T在Q表中，且通過式(3)計算的g值比NT原先的g值小，則將NT的g值更新為式(3)結(jié)果，將NT的父節(jié)點設(shè)為BT，并將NT移出到P表中。
?、苋鬘T既不在P表，也不在Q表中，則將NT的父節(jié)點設(shè)為BT，并將NT移到P表中。
?、蒉D(zhuǎn)到步驟（2）繼續(xù)執(zhí)行。
?。?）從終點T回溯，依次找到父節(jié)點，并加入優(yōu)化路徑中，直到起點S，即可得出優(yōu)化路徑。
2動態(tài)行程時間表及A*算法調(diào)整
2.1動態(tài)行程時間表
為計算在實時情況下某段道路的通行時間，采用了一種道路通行時間表的結(jié)構(gòu)，表中存放了道路當前時刻的通行時間以及未來幾個時刻通行時間的預(yù)測值。
以t0表示導(dǎo)航系統(tǒng)開始工作的時刻，將未來一段時間劃分為若干個時段，以ΔT表示一個時段的長度，系統(tǒng)開始工作的時刻屬于第一個時段。然后對這些時段進行編號，如1,2,3,4，…。同理，也將每條道路編號為1,2,3,4，…。采用Tij表示路段i在時段j的通行時間。這樣就可得到不同道路在不同時刻的通行時間，將它們記錄為表1。
車載系統(tǒng)可能會在某個時刻進行路徑規(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:
其中，」符號表示對結(jié)果取下整。則相應(yīng)地可得出：
T′ki=Tk(fk+i-1)(5)
根據(jù)時段長度ΔT、道路長度L與道路通行速度的不同取值，可能會出現(xiàn)車輛只需在一個時段即可通過路段，也可能需要多個時段才能通過。因此經(jīng)過牛頓運動學(xué)原理進行計算，可得到車輛通過路段k的具體公式如下［9］：
其中，m的取值滿足：
2.2A*算法調(diào)整
在得出車輛通過路段k的計算方法后，即可對傳統(tǒng)A*算法進行調(diào)整，以搜索出動態(tài)優(yōu)化路徑。具體如下：
在A*算法描述的第（2）步中，首先計算出起點S到達BT的通行時間t，則到達BT的時刻為出發(fā)時刻加上t，記為tBT，然后根據(jù)式(6)計算出BT到達NT的通行時間T。則可更新g(NT)為：
g(NT)=g(BT)+T+tli(8)
其中，tli表示路口紅綠燈等待時間。除了這些調(diào)整外，前述A*算法的其他部分不需要改變。
3動態(tài)多路徑規(guī)劃算法
3.1算法描述
上述調(diào)整后的A*算法一次只能搜索出單條動態(tài)優(yōu)化路徑，為了在給定起點S與終點T之后得到多條在通行代價與路徑相似度之間取得平衡的動態(tài)優(yōu)化路徑，提出了一種重復(fù)路徑懲罰因子的概念。算法的總體思想是：首先利用上述調(diào)整后的A*算法搜索出一條優(yōu)化路徑后，將此優(yōu)化路徑上每條道路的通行代價都乘以懲罰因子，然后再利用算法搜尋下一條優(yōu)化路徑。在描述算法之前，首先需要定義幾個符號：Pk為S到T之間的第k條優(yōu)化路徑；Lk為Pk的長度；PC為存放優(yōu)化路徑的集合；OLnk為第n條優(yōu)化路徑與第k條優(yōu)化路徑的重合度，表示為兩條路徑上重復(fù)路段的總長度, k=n-1,n-2,…，1；Dnk為第n條優(yōu)化路徑與第k條優(yōu)化路徑的相似度，Dnk=OLnk/Ln,k=n-1,n-2,…，1；MO為設(shè)定的最大相似度；PO為重復(fù)路徑懲罰因子，PO=(1MO)β,β為一個正系數(shù)；K為希望搜索出的最大優(yōu)化路徑條數(shù)；n為當前已規(guī)劃出優(yōu)化路徑條數(shù)。
利用這些符號，算法可描述如下：
（1）設(shè)置MO、β和K，令n=0;
?。?）利用調(diào)整后的A*算法搜索出一條優(yōu)化路徑,將其加入PC中，n=1;
（3）若n大于等于K，算法結(jié)束，否則將Pn上每一條路段的通行代價都乘以PO;
?。?）路徑規(guī)劃與相似度計算：
?、賜=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與β的取值。當MO=1.0時，相當于沒有懲罰，此時只能得出一條路徑；當MO<1.0時,可以得到多條路徑。
3.2實驗結(jié)果
圖1本文算法規(guī)劃結(jié)果本文采用真實的合肥城區(qū)電子地圖數(shù)據(jù)，構(gòu)建了一個C/S(Client/Server)模型，由服務(wù)器端模擬產(chǎn)生實時交通數(shù)據(jù)，每條道路的通行時間范圍為道路暢通時的時間到7倍于它之間的一個隨機值。在車載終端請求實時數(shù)據(jù)時，終端會發(fā)送起點、終點坐標值給服務(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)化路徑通行代價與相似度路徑123長度/km13.4315.9216.37最大相似度/%-13.6330.78其中最大相似度表示的是此道路與標號小于它的那些道路的最大D值。作為對比，百度地圖的搜索結(jié)果如圖2所示?！?/p>
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算法路徑相似度過高的缺點，同時提高了算法的實時性。
參考文獻
?。?］ NADI S, DELAVAR M R. Locationbased service for Invehicle route guidance with real time traffic information［C］.The 12th World Conference on Transport Research (WSTR to WCTR) Proceedings, 2010: 110.
?。?］ GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: efficient pointtopoint shortest path algorithms［C］.ALENEX, 2006, 6(2): 129143.
?。?］ MHRING R H, SCHILLING H, SCHTZ B, et al. Partitioning graphs to speed up Dijkstra’s algorithm［M］.Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2005,11(28): 189202.
?。?］ 隨裕猛, 陳賢富, 劉斌. Dstar Lite 算法及其動態(tài)路徑規(guī)劃實驗研究［J］. 微型機與應(yīng)用, 2015, 34(7): 1619.
［5］ 蘇永云, 晏克非. 車輛導(dǎo)航系統(tǒng)的動態(tài)最優(yōu)路徑搜索方法研究［J］. 系統(tǒng)工程, 2000, 18(4): 3237.
?。?］ DREYFUS S E. An appraisal of some shortestpath algorithms［J］. Operations research, 1969, 17(3): 395412.