路徑誘導系統中雙向啟發式A*算法研究

楊泳，戶佐安，何金海

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

路徑誘導系統中雙向啟發式A*算法研究

楊泳，戶佐安，何金海

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

針對實際城市交通路網最優路徑規劃中存在的計算效率問題，研究了最優路徑算法的快速實現技術，提出了一種雙向啟發式A*誘導算法。在分析經典Dijkstra算法和A*啟發式搜索算法的基礎上，利用雙向A*算法分解搜索空間，采用完全二叉堆結構來實現計算過程中數據的存取，從而提高了算法的執行效率。實際路網仿真結果證明了該算法的優異性能。

最優路徑規劃；雙向啟發式A*算法；路網；二叉堆

1 引言

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

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

2 算法描述

2.1 用堆實現路網存儲結構

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

2.2 最短路徑問題數學描述

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

2.3 經典Dijkstra算法和A*算法

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

圖1 Dijkstra算法的搜索空間

2.4 雙向啟發式A*算法

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

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

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

圖2 雙向啟發式A*算法搜索空間

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

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

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

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

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

3 結果對比分析

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

3.1 算法計算效率對比

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

表1 成都市區內隨機10組OD對誘導時間s

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

3.2 算法誘導結果對比

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

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

圖4 Dijkstra算法和雙向A*算法結果對比

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

表2 成都市區內隨機1 000組OD點結果對比

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

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

4 結束語

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

[1]張起善.智能車輛定位導航系統及應用[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中最短路徑問題的研究與實現[D].成都：四川大學，2006.

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

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

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

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

[8]孫小榮，徐愛功，劉玉華.車輛導航中一種改進的路徑優化算法[J].遼寧工程技術大學學報，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—），男，博士研究生，主要研究領域為城市智能交通、城市交通規劃與管理；戶佐安（1979—），男，博士，講師，研究方向為智能鐵路車流組織、智能交通；何金海（1988—），男，碩士研究生，研究方向為物流量分配及一體化研究。E-mail：yangyong@my.sw jtu.edu.cn

2012-09-12

2012-11-02

1002-8331（2014）16-0054-03

CNKI網絡優先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1520.009.htm l