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

楊泳，戶佐安，何金海

西南交通大學交通運輸學院，成都 610031

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

楊泳，戶佐安，何金海

西南交通大學交通運輸學院，成都 610031

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

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

1 引言

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

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

2 算法描述

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

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

2.2 最短路徑問題數(shù)學描述

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

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

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

圖1 Dijkstra算法的搜索空間

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

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

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

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

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

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

（1）進行前向搜索，生成一個前向最佳節(jié)點。

（2）后向搜索以此前向最佳節(jié)點為目標節(jié)點，同時生成一個后向最佳節(jié)點，當執(zhí)行前向搜索時以此后向最佳節(jié)點為目標節(jié)點。

（3）反復迭代，直至相遇退出。

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

3 結(jié)果對比分析

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

3.1 算法計算效率對比

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

表1 成都市區(qū)內(nèi)隨機10組OD對誘導時間s

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

3.2 算法誘導結(jié)果對比

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

圖3 Dijkstra算法和雙向A*算法效率對比

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

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

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

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

圖5 Dijkstra算法和雙向A*算法誘導路徑

4 結(jié)束語

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

[1]張起善.智能車輛定位導航系統(tǒng)及應用[M].北京：科學出版社，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中最短路徑問題的研究與實現(xiàn)[D].成都：四川大學，2006.

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

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

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

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

[8]孫小榮，徐愛功，劉玉華.車輛導航中一種改進的路徑優(yōu)化算法[J].遼寧工程技術(shù)大學學報，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.

國家自然科學基金（No.61104175）。

楊泳（1982—），男，博士研究生，主要研究領域為城市智能交通、城市交通規(guī)劃與管理；戶佐安（1979—），男，博士，講師，研究方向為智能鐵路車流組織、智能交通；何金海（1988—），男，碩士研究生，研究方向為物流量分配及一體化研究。E-mail：yangyong@my.sw jtu.edu.cn

2012-09-12

2012-11-02

1002-8331（2014）16-0054-03

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