劉斌，陳賢富，程政

　?。ㄖ袊茖W(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 Shortest Paths, KSP)算法路徑相似度過高的缺點(diǎn)。

　　關(guā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ì)改變，大多采用道路長度、寬度等靜態(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ǎng)中道路動(dòng)態(tài)通行時(shí)間表，表中記錄了每個(gè)路段每個(gè)時(shí)間段的行程時(shí)間，由此得出了車輛經(jīng)過路段的通行時(shí)間計(jì)算方法。

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

　　本文通過分析上述算法的優(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à)。

1A*算法

　　A*算法是一種典型的啟發(fā)式搜索算法，建立在Dijkstra算法的基礎(chǔ)之上，廣泛應(yīng)用于游戲地圖、現(xiàn)實(shí)世界中，用來尋找兩點(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í)間變長。

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

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

　?。?）若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à)。

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

　　③如果NT在Q表中，且通過式(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í)間以及未來幾個(gè)時(shí)刻通行時(shí)間的預(yù)測值。

　　以t0表示導(dǎo)航系統(tǒng)開始工作的時(shí)刻，將未來一段時(shí)間劃分為若干個(gè)時(shí)段，以ΔT表示一個(gè)時(shí)段的長度，系統(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。 

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

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

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

　　T′ki=Tk(fk+i-1)(5)

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

　　其中，m的取值滿足：

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

　　在得出車輛通過路段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算法描述

　　上述調(diào)整后的A*算法一次只能搜索出單條動(dòng)態(tài)優(yōu)化路徑，為了在給定起點(diǎn)S與終點(diǎn)T之后得到多條在通行代價(jià)與路徑相似度之間取得平衡的動(dòng)態(tài)優(yōu)化路徑，提出了一種重復(fù)路徑懲罰因子的概念。算法的總體思想是：首先利用上述調(diào)整后的A*算法搜索出一條優(yōu)化路徑后，將此優(yōu)化路徑上每條道路的通行代價(jià)都乘以懲罰因子，然后再利用算法搜尋下一條優(yōu)化路徑。在描述算法之前，首先需要定義幾個(gè)符號(hào)：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)β,β為一個(gè)正系數(shù)；K為希望搜索出的最大優(yōu)化路徑條數(shù)；n為當(dāng)前已規(guī)劃出優(yōu)化路徑條數(shù)。

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

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

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

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

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

　　①n=n+1;

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

　?、?計(jì)算相似度：

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

　?、苈窂较嗨贫扰袛啵?/p>

　　若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ù)量。

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

　　表2優(yōu)化路徑通行代價(jià)與相似度路徑123長度/km13.4315.9216.37最大相似度/%-13.6330.78其中最大相似度表示的是此道路與標(biāo)號(hào)小于它的那些道路的最大D值。作為對(duì)比，百度地圖的搜索結(jié)果如圖2所示。　

　　3條道路的長度分別為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算法路徑相似度過高的缺點(diǎn)，同時(shí)提高了算法的實(shí)時(shí)性。

　　參考文獻(xiàn)

　?。?］ 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.

　?。?］ 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.

　?。?］ 蘇永云, 晏克非. 車輛導(dǎo)航系統(tǒng)的動(dòng)態(tài)最優(yōu)路徑搜索方法研究［J］. 系統(tǒng)工程, 2000, 18(4): 3237.

　?。?］ DREYFUS S E. An appraisal of some shortestpath algorithms［J］. Operations research, 1969, 17(3): 395412.