楊泳，戶佐安，何金海

西南交通大學(xué)交通運(yùn)輸學(xué)院，成都 610031

路徑誘導(dǎo)系統(tǒng)中雙向啟發(fā)式A*算法研究

楊泳，戶佐安，何金海

西南交通大學(xué)交通運(yùn)輸學(xué)院，成都 610031

針對(duì)實(shí)際城市交通路網(wǎng)最優(yōu)路徑規(guī)劃中存在的計(jì)算效率問(wèn)題，研究了最優(yōu)路徑算法的快速實(shí)現(xiàn)技術(shù)，提出了一種雙向啟發(fā)式A*誘導(dǎo)算法。在分析經(jīng)典Dijkstra算法和A*啟發(fā)式搜索算法的基礎(chǔ)上，利用雙向A*算法分解搜索空間，采用完全二叉堆結(jié)構(gòu)來(lái)實(shí)現(xiàn)計(jì)算過(guò)程中數(shù)據(jù)的存取，從而提高了算法的執(zhí)行效率。實(shí)際路網(wǎng)仿真結(jié)果證明了該算法的優(yōu)異性能。

最優(yōu)路徑規(guī)劃；雙向啟發(fā)式A*算法；路網(wǎng)；二叉堆

1 引言

路徑誘導(dǎo)是智能交通的研究熱點(diǎn)，是交通流分配、物流配送、智能停車(chē)、車(chē)輛導(dǎo)航、集成電路設(shè)計(jì)等領(lǐng)域的基本問(wèn)題，而網(wǎng)絡(luò)中兩點(diǎn)之間的路徑誘導(dǎo)問(wèn)題可以歸納為圖論中計(jì)算求解帶權(quán)有向圖的最優(yōu)路徑問(wèn)題。由于誘導(dǎo)系統(tǒng)實(shí)時(shí)性要求高、實(shí)際路網(wǎng)的規(guī)模龐大，而誘導(dǎo)計(jì)算機(jī)的處理能力和系統(tǒng)的存儲(chǔ)資源有限，從而要求誘導(dǎo)算法的執(zhí)行效率很高，甚至可以犧牲一些算法的精度。即使算法求得的最優(yōu)路徑解并非傳統(tǒng)意義上的“最優(yōu)”，是有一定偏差的次優(yōu)解，但是只要能滿足實(shí)際交通信息瞬時(shí)多變的實(shí)時(shí)性要求，同樣能吻合客戶交通出行的需求[1]。

在計(jì)算能力確定的前提下，主要有三種算法的優(yōu)化策略[2]：存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)優(yōu)化、誘導(dǎo)算法優(yōu)化及分層技術(shù)控制路網(wǎng)規(guī)模優(yōu)化。楊瑜君[3]針對(duì)超大路網(wǎng)下最短路徑問(wèn)題展開(kāi)研究，指出城市路網(wǎng)道路等級(jí)特性平緩，不適合采用分層技術(shù)。劉張雷[4]基于對(duì)Dijkstra、A*、D*Lite等幾種算法對(duì)比分析提出一種基于路網(wǎng)變化的跳變動(dòng)態(tài)路徑規(guī)劃策略，提高誘導(dǎo)效率。張玲[5]提出一種改進(jìn)的Floyd最短路徑算法來(lái)求解動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中的“多準(zhǔn)最優(yōu)路徑”問(wèn)題。王士同[6]率先提出隨機(jī)產(chǎn)生系統(tǒng)的雙向啟發(fā)式圖搜索算法并證明其可行性。鄭年波[7]通過(guò)改進(jìn)傳統(tǒng)的Dijkstra算法，提出基于搜索節(jié)點(diǎn)的雙向啟發(fā)式A*算法，并通過(guò)小范圍路網(wǎng)算例實(shí)驗(yàn)表明該算法在效率和結(jié)果方面均能滿足車(chē)輛導(dǎo)航及路徑規(guī)劃的要求。孫小榮[8]以Dijkstra算法和A*啟發(fā)式算法為基礎(chǔ)，結(jié)合雙向A*算法和分層技術(shù)證明雙向A*算法效率的優(yōu)越性，同時(shí)指出最佳分層結(jié)構(gòu)的弊端。本文在經(jīng)典Dijkstra算法的基礎(chǔ)上，結(jié)合優(yōu)先隊(duì)列數(shù)據(jù)結(jié)構(gòu)，研究一種高效的雙向啟發(fā)式A*算法搜索策略。

2 算法描述

2.1 用堆實(shí)現(xiàn)路網(wǎng)存儲(chǔ)結(jié)構(gòu)

表示路網(wǎng)的數(shù)據(jù)結(jié)構(gòu)有很多，例如鄰接矩陣、鄰接表、十字鏈表、隊(duì)列等。然而實(shí)際路網(wǎng)的結(jié)構(gòu)屬于典型的邊稀疏網(wǎng)絡(luò)，表示路網(wǎng)的數(shù)據(jù)結(jié)構(gòu)中最有效的是二叉堆[2]。W illioms在1964年提出了堆排序方法，該方法引入“堆”這種特定的數(shù)據(jù)結(jié)構(gòu)。這里堆結(jié)構(gòu)可以被視為一棵完全二叉樹(shù)，可以作為高效的優(yōu)先級(jí)隊(duì)列來(lái)使用。本文在計(jì)算過(guò)程中，采用優(yōu)先級(jí)隊(duì)列與完全二叉樹(shù)相結(jié)合的存儲(chǔ)方式，實(shí)現(xiàn)雙向啟發(fā)式A*誘導(dǎo)算法。

2.2 最短路徑問(wèn)題數(shù)學(xué)描述

最短路徑問(wèn)題是指在一個(gè)帶權(quán)值的圖中找出兩個(gè)指定節(jié)點(diǎn)間的一條權(quán)值和最小的路徑。數(shù)學(xué)上，將交通道路網(wǎng)絡(luò)的拓?fù)潢P(guān)系模型記為賦權(quán)有向圖G=(N，A)。其中，節(jié)點(diǎn)N={i}，節(jié)點(diǎn)數(shù)n=|N|，弧集A={a|a=(i，j);i，j∈N}，弧數(shù)m=|A|，對(duì)任意弧度a=(i，j)，定義ca或ci，j為路段權(quán)值，滿足ci，j＞0。對(duì)G中任意路徑P=(a1，a2，…，al-1，al)，路徑長(zhǎng)度C(P)=ca1+ca2+…+cal為路徑所經(jīng)過(guò)的所有路段的弧長(zhǎng)之和。最短路徑問(wèn)題就是求解有向圖中任意給定兩個(gè)節(jié)點(diǎn)α，z的最短路徑M in(C(P)α，z)。在實(shí)際交通誘導(dǎo)系統(tǒng)中，根據(jù)誘導(dǎo)服務(wù)的目的不同，路段權(quán)值ca描述的因素有所區(qū)別，最短路徑問(wèn)題可以分為距離最短、時(shí)間最短、擁擠程度最低、道路質(zhì)量最優(yōu)等，本文的研究是基于行車(chē)距離最短這一條件下，符合路網(wǎng)較暢通條件下的交通出行目的。

2.3 經(jīng)典Dijkstra算法和A*算法

Dijkstra算法求解最短路徑問(wèn)題的經(jīng)典算法，是許多應(yīng)用中解決最短路徑問(wèn)題的理論基礎(chǔ)。Dijkstra算法是一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的窮舉算法，求解結(jié)果是原點(diǎn)到其他所有各節(jié)點(diǎn)的最短路徑，搜索空間是以原節(jié)點(diǎn)為圓心的圓（圖1），算法比較簡(jiǎn)單，容易實(shí)現(xiàn)，適合小范圍的最短路徑的計(jì)算。Dijkstra算法是已經(jīng)被證明能得出最短路徑的最優(yōu)解，但它的效率是個(gè)很大的問(wèn)題，對(duì)于具有n個(gè)節(jié)點(diǎn)道路網(wǎng)，Dijkstra算法的時(shí)間復(fù)雜度為O(n2)，一座大中型城市的路網(wǎng)節(jié)點(diǎn)數(shù)據(jù)就能達(dá)到幾萬(wàn)個(gè)到幾十萬(wàn)個(gè)，Dijkstra算法并不太適合在大型交通網(wǎng)絡(luò)中使用。而啟發(fā)式A*算法的基本思想是引入啟發(fā)函數(shù)h(n)優(yōu)先搜索最佳鄰接路段節(jié)點(diǎn)，節(jié)點(diǎn)n的估價(jià)函數(shù)定義為f(n)=g(n)+h(n)，式中g(shù)(n)是開(kāi)始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià)路徑的代價(jià)，h(n)是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)之間代價(jià)的估計(jì)，稱為啟發(fā)函數(shù)，f(n)就代表節(jié)點(diǎn)n總的代價(jià)。

圖1 Dijkstra算法的搜索空間

2.4 雙向啟發(fā)式A*算法

雙向搜索就是將搜索過(guò)程分解成獨(dú)立的兩個(gè)搜索過(guò)程同時(shí)進(jìn)行，即從原結(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)正向搜索過(guò)程和從目標(biāo)結(jié)點(diǎn)向原節(jié)點(diǎn)的逆向搜索過(guò)程，其關(guān)鍵在于終止條件和切換條件的設(shè)定。雙向啟發(fā)式A*算法[2]結(jié)合雙向搜索技術(shù)和啟發(fā)式信息提出的一種快速搜索算法，它由正向啟發(fā)式A*算法和逆向啟發(fā)A*算法疊加進(jìn)行。正向過(guò)程啟發(fā)算法的啟發(fā)函數(shù)基于目標(biāo)節(jié)點(diǎn)計(jì)算，而逆向過(guò)程啟發(fā)式函數(shù)則基于原節(jié)點(diǎn)計(jì)算，本文計(jì)算均采用曼哈頓（M anhattan）距離：

其中(xA，yA)為節(jié)點(diǎn)A的經(jīng)緯度，(xB，yB)為節(jié)點(diǎn)B的經(jīng)緯度，R為地球的半徑，常量。

理想狀況下，正向搜索和逆向搜索在原節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的幾何中心相遇，這樣可以減少50%的搜索空間，搜索空間如圖2。但在實(shí)際路網(wǎng)中，原節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)所處的路網(wǎng)密度、通達(dá)程度等均不同，搜索很可能不在中間點(diǎn)相遇，在極端情況下，甚至可能導(dǎo)致雙向啟發(fā)算法的搜索節(jié)點(diǎn)為單向啟發(fā)搜索的兩倍。因此，設(shè)計(jì)一個(gè)好的雙向啟發(fā)式搜索算法的關(guān)鍵是使其在搜索區(qū)域的中間部分相遇，而避免算法在中間部分不相遇，本文采用“迭代式最佳節(jié)點(diǎn)替換法”實(shí)現(xiàn)前向啟發(fā)式搜索和后向啟發(fā)式搜索切換來(lái)滿足中間部分相遇和退出條件的要求。

圖2 雙向啟發(fā)式A*算法搜索空間

具體的改進(jìn)方法是不使前向和后向搜索進(jìn)行簡(jiǎn)單的交替切換執(zhí)行，具體步驟如下：

（1）進(jìn)行前向搜索，生成一個(gè)前向最佳節(jié)點(diǎn)。

（2）后向搜索以此前向最佳節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，同時(shí)生成一個(gè)后向最佳節(jié)點(diǎn)，當(dāng)執(zhí)行前向搜索時(shí)以此后向最佳節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)。

（3）反復(fù)迭代，直至相遇退出。

前向和后向之間的切換取決于搜索空間最佳節(jié)點(diǎn)的啟發(fā)式估價(jià)函數(shù)，如果在前向搜索中基于目標(biāo)節(jié)點(diǎn)的當(dāng)前節(jié)點(diǎn)的估價(jià)函數(shù)小于后向搜索基于原節(jié)點(diǎn)的當(dāng)前節(jié)點(diǎn)的估價(jià)函數(shù)，這就意味著在前向搜索中更偏于“中間區(qū)域”，此時(shí)執(zhí)行后向搜索，反之，則執(zhí)行后向搜索，這樣就能保證前向和后向搜索中間區(qū)域相遇的理想情況。

3 結(jié)果對(duì)比分析

為了驗(yàn)證搜索算法的有效性，在W indow s操作系統(tǒng)平臺(tái)下基于.net技術(shù)和Visual Studio工具開(kāi)發(fā)出路徑誘導(dǎo)原型系統(tǒng)，分別按經(jīng)典Dijkstra算法、雙向啟發(fā)式A*算法搜索最優(yōu)路徑。選取成都市真實(shí)交通網(wǎng)數(shù)據(jù)：39 446個(gè)節(jié)點(diǎn)和28 067條路段。仿真程序的運(yùn)行環(huán)境為W indow s server 2008R2，Intel 2.8 GHz四核處理器，4 GB主存，512 GB硬盤(pán)。測(cè)試分為兩部分：（1）測(cè)試算法的計(jì)算效率；（2）測(cè)試路徑誘導(dǎo)結(jié)果的合理性。

3.1 算法計(jì)算效率對(duì)比

在成都市路網(wǎng)上隨機(jī)選取10個(gè)起點(diǎn)和終點(diǎn)對(duì)（OD對(duì)），分別利用Dijkstra算法和雙向啟發(fā)式A*算法進(jìn)行最優(yōu)路徑誘導(dǎo)，利用CPU時(shí)間來(lái)衡量算法的效率。為消除和減少誤差，對(duì)每組OD對(duì)分別計(jì)算10次，并取其平均值作為誘導(dǎo)時(shí)間，結(jié)果如表1所示。

表1 成都市區(qū)內(nèi)隨機(jī)10組OD對(duì)誘導(dǎo)時(shí)間s

從表1可以看出，隨著OD對(duì)距離的波動(dòng)，搜索時(shí)間呈現(xiàn)相同趨勢(shì)的波動(dòng)。對(duì)于同一OD對(duì)，雙向啟發(fā)式搜索算法的平均計(jì)算時(shí)間明顯小于Dijkstra算法的平均計(jì)算時(shí)間，且不同的OD之間提高幅度有所區(qū)別，平均提高78%左右，如圖3所示。

3.2 算法誘導(dǎo)結(jié)果對(duì)比

首先對(duì)比路網(wǎng)上10組OD對(duì)兩種不同算法之間的誘導(dǎo)路徑結(jié)果，如圖4所示，可以看出雙向啟發(fā)式A*算法規(guī)劃出來(lái)的路徑長(zhǎng)度比Dijkstra算法規(guī)劃的路徑長(zhǎng)度稍長(zhǎng)，吻合程度很高，說(shuō)明雙向啟發(fā)式誘導(dǎo)算法計(jì)算出的路線是較好的“次優(yōu)路”。

圖3 Dijkstra算法和雙向A*算法效率對(duì)比

圖4 Dijkstra算法和雙向A*算法結(jié)果對(duì)比

其次，為了進(jìn)一步量化誘導(dǎo)路徑精度，隨機(jī)選取1 000組OD點(diǎn)，分別使用經(jīng)典Dijkstra算法和雙向A*算法進(jìn)行最優(yōu)路徑誘導(dǎo)，對(duì)每組OD對(duì)分別計(jì)算10次，并取其平均值作為OD對(duì)誘導(dǎo)時(shí)間。以Dijkstra最短距離為最優(yōu)路徑誘導(dǎo)基準(zhǔn)，結(jié)果如表2所示，其中平均值是指算法下所有1 000組OD結(jié)果的數(shù)值平均?？梢钥闯鰧?duì)于最短距離OD對(duì)，兩種算法獲取的誘導(dǎo)路徑結(jié)果完全一致，而對(duì)于最長(zhǎng)距離33 km的OD對(duì)誘導(dǎo)，產(chǎn)生3.8 km的偏差。平均而言，采用雙向啟發(fā)式A*算法產(chǎn)生4.98%的誤差，基本能滿足出行者的出行要求。

表2 成都市區(qū)內(nèi)隨機(jī)1 000組OD點(diǎn)結(jié)果對(duì)比

最后，對(duì)某一組OD對(duì)示例分析，起點(diǎn)為天一廣場(chǎng)停車(chē)場(chǎng)，終點(diǎn)為金福路，Dijkstra誘導(dǎo)路徑9.2 km，誘導(dǎo)時(shí)間0.18 s，雙向啟發(fā)式A*算法誘導(dǎo)路徑9.5 km，誘導(dǎo)時(shí)間為0.05 s。比較而言，誘導(dǎo)時(shí)間有比較大的提升，而在誘導(dǎo)結(jié)果上，絕大部分路段重合，只有在三環(huán)路蘇坡立交橋處理上兩種算法結(jié)果不一致：Dijkstra算法選擇從橋上通過(guò)，而雙向A*算法選擇從橋下箍道通過(guò)，如圖5。

圖5 Dijkstra算法和雙向A*算法誘導(dǎo)路徑

4 結(jié)束語(yǔ)

結(jié)合經(jīng)典Dijkstra算法和雙向啟發(fā)式A*算法搜索可以發(fā)現(xiàn)，雙向啟發(fā)式A*算法在運(yùn)行時(shí)間上具有明顯優(yōu)勢(shì)，雖然規(guī)劃出來(lái)的路徑不是最優(yōu)路徑，但“次優(yōu)路徑”能較好地滿足出行者的出行要求，具有一定的實(shí)用價(jià)值。實(shí)際中，由于司機(jī)主觀偏好及路網(wǎng)信息認(rèn)可程度等因素的影響，本文算法對(duì)研究“多準(zhǔn)最優(yōu)路徑”問(wèn)題提供新的研究思路。

[1]張起善.智能車(chē)輛定位導(dǎo)航系統(tǒng)及應(yīng)用[M].北京：科學(xué)出版社，2002.

[2]Fu L，Sun D，Rilett L R.Heuristic shortest path algorithms for transportation applications：state of the art[J].Computers &Operations Research，2006，33（1）：3324-3343.

[3]楊瑜君.GIS中最短路徑問(wèn)題的研究與實(shí)現(xiàn)[D].成都：四川大學(xué)，2006.

[4]劉張雷，史忠科.一種基于路網(wǎng)變化的動(dòng)態(tài)路徑規(guī)劃策略[J].交通運(yùn)輸系統(tǒng)工程與信息，2010，10（3）：147-152.

[5]張玲，高淑萍.動(dòng)態(tài)多路選擇的混合演化算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（8）：200-203.

[6]王士同.雙向啟發(fā)式圖搜索算法BFFRA*[J].電子學(xué)報(bào)，1990，18（6）：34-39.

[7]鄭年波，李清權(quán).基于轉(zhuǎn)向限制和延誤的雙向啟發(fā)式最短路徑算法[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2006，31（3）：256-259.

[8]孫小榮，徐愛(ài)功，劉玉華.車(chē)輛導(dǎo)航中一種改進(jìn)的路徑優(yōu)化算法[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2005，24（Suppl）：74-76.

YANG Yong,HU Zuo’an,HE Jinhai

School of Traffic&Transport,Southwest Jiaotong University,Chengdu 610031,China

Computational efficiency is widely recognized to be an essential issue in the optimal route planning against realistic urban road traffic network,the fast search technology is studied and a bidirectional heuristic A*algorithm is presented.Based on analysis of classic Dijkstra algorithm and heuristic A*algorithm,bidirectional heuristic A*is used to decompose the search space and binary heap data structure is utilized to operate data.Simulation results against real data demonstrate performance boost.

optimal route planning;bi-directional heuristic A*algorithm;traffic network;binary heap

A

TP18

10.3778/j.issn.1002-8331.1209-0081

YANG Yong,HU Zuo’an,HE Jinhai.Research of bidirectional heuristic A*algorithm in route guide system.Computer Engineering and Applications,2014,50（16）：54-56.

國(guó)家自然科學(xué)基金（No.61104175）。

楊泳（1982—），男，博士研究生，主要研究領(lǐng)域?yàn)槌鞘兄悄芙煌?、城市交通?guī)劃與管理；戶佐安（1979—），男，博士，講師，研究方向?yàn)橹悄荑F路車(chē)流組織、智能交通；何金海（1988—），男，碩士研究生，研究方向?yàn)槲锪髁糠峙浼耙惑w化研究。E-mail：yangyong@my.sw jtu.edu.cn

2012-09-12

2012-11-02

1002-8331（2014）16-0054-03

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1520.009.htm l