交通路網最優路徑的搜索仿真研究

楊智宇 宗 群

(天津大學電氣與自動化工程學院 天津 300072)

?

交通路網最優路徑的搜索仿真研究

楊智宇 宗 群

(天津大學電氣與自動化工程學院 天津 300072)

在道路狀況日趨復雜的今天，交通路網中兩點之間的最短路徑已經不再是人們駕駛所需要的最優路徑。傳統路徑規劃方法存在考慮路徑規劃影響因素過于單一以及搜索效率過低的問題。在路徑規劃問題中缺少一種在多約束條件下的具體方法來實現交通路網中最優路徑的高效搜索。針對上述問題，提出一種基于AHP層次分析法的改進Dijkstra算法。該算法在保有經典Dijkstra算法準確性的基礎上，考慮了多種約束條件并大大提升了搜索效率。仿真結果表明，這種基于AHP層次分析法的改進Dijkstra算法具有良好的性能，能夠滿足當前路徑規劃問題的要求。

路徑規劃 Dijkstra算法 車聯網 二叉堆 層次分析法

0 引 言

隨著汽車行業的發展，以及車聯網議題的提出，傳統路徑規劃算法所得到的最短路徑已經越來越不能滿足當代人的需求，如何在多約束條件下來獲取交通路網兩點間的最優路徑是當前車聯網領域研究的熱點問題[1]。

過去，人們在尋求最短路徑時所用到的路徑規劃算法有很多，其中使用最為廣泛也最為有效的是Dijkstra算法。在交通道路建設高速發展的今天，該算法能夠很好地適應道路拓撲模型的變化、性能穩定且通用性強。但它也存在計算量上的冗余、算法效率低、運算中占用空間大等缺點。于是文獻[2]首先利用桶排序將數據存儲結構轉換成臨接表結構，然后采用矩形區域限制搜索來減少遍歷結點數目；文獻[3-4]提供了一種雙向Dijkstra算法的策略來提高路徑規劃的效率；文獻[5-6]對Dijkstra標號法進行了改進，并通過算法實驗進行驗證。文獻[7]采取了一種可變搜索域的方法來減少Dijkstra算法的冗余操作并確保找到最短路徑。在對經典Dijkstra算法的改進與應用中，人們往往只考慮了道路長度這一影響因素，缺少一種在多約束條件下的具體方法來實現交通路網中最優路徑的高效搜索。

為了解決在多約束條件下交通路網最優路徑的搜索問題，本文提出了一種基于AHP層次分析法的改進Dijkstra算法。該算法將經典Dijkstra算法和AHP層次分析法相結合，首先考慮了當代交通路網中的多種約束條件，如道路長度、道路寬度、車速限制等，設計了權重矩陣，提升了路徑規劃的合理性。其次，由于Dijkstra算法存在低效性等問題，將優先隊列(堆)的概念引入到Dijkstra算法當中，又因為待搜索結點與起始結點連線距離小于起始結點與目的結點之間距離的結點被選取為最優路徑中結點的概率極大，提出了一種基于距離限制的可變范圍的結點篩選策略，減小了搜索計算的范圍，大大提升了算法的效率。最后在Matlab(由于仿真平臺使用Matlab，故本文中編程指令和語法均以Matlab中的指令和語法為準)中對改進的算法進行了實驗驗證，證明了算法的有效性。

1 交通路網路徑規劃原理

在對交通路網進行路徑規劃時，首先會把路與路之間的拓撲關系以圖G=(V,E)的形式存儲起來[8]，其中V和E是兩個集合，前者是圖G中頂點的有限非空集合。后者稱之為頂點之間關系的集合，也就是邊的集合。V和E的表達方式如式(1)、式(2)所示：

(1)

E={VE}

(2)

(3)

式(3)是對邊集合E的一個解釋，其中P(x,y)表示頂點x與y之間存在的路徑。在這里，V中的每一個頂點代表著地圖相應的路口結點并存儲該路口的位置信息。E中的每一條邊代表著與其連接的兩個路口結點之間的權值。

于是復雜的交通路網就可以簡化為圖1的形式。

圖1 交通路網道路拓撲關系圖

于是結點和邊之間的關系就可以用鄰接矩陣A=(aij)n×n來存放。其中aij如式(4)所示：

(4)

式中，i,j=1,2,…,n;wij是結點Vi和結點Vj之間的權值，如果兩個結點不相連則用inf表示。故圖1所示的交通路網模型所對應的鄰接矩陣如式(5)所示。

(5)

隨著現代社會的發展，交通線路變化越來越快，具有良好適應性Dijkstra算法也越來越受到重視[9]。經典Dijkstra算法采用遍歷搜索所有節點的方式來完成最優路徑的獲取，即從起始結點開始，計算出所有結點與起始結點之間的權值，并通過比較找到最小權值的結點。將此結點標記并記錄該結點的信息(被標記過的結點之后不再參與搜索)，然后將該結點作為新的起始結點。重復上述步驟，直到找到目的結點為止，最終記錄得到的途徑結點集合就是所需要的最優路徑[10]。

在傳統路徑規劃方法中，兩路口結點之間的權值通常為兩路口之間的距離。因此通過傳統權值鄰接矩陣所得到的最優路徑即為最短路徑，但隨著現代交通的發展，影響路徑規劃的因素越來越多，如道路長度，車道數目，車輛密度等。并且隨著交通線路越來越多、越來越復雜、遍歷式搜索的Dijkstra算法需要搜索大量的無關結點，計算的冗余性大大降低了路徑規劃的效率[11-12]。于是這種考慮影響因素單一、低效的路徑規劃方法越來越不能滿足路徑規劃的需求。

綜上所述，在路徑規劃問題中構建一個考慮了多種影響因素的權值鄰接矩陣成為了獲得良好路徑的前提，再根據優先隊列的特點以及待搜索結點與起始結點連線距離小于起始結點與目的結點之間距離的結點被選取為最優路徑中結點的概率極大的特性，將Dijkstra算法進行改進。改進的Dijkstra算法使得單次搜索效率以及獲得最優路徑的質量顯著提升。這樣利用改進的Dijkstra算法所搜索到的最優路徑能夠更好地滿足路徑規劃的需求。

2 基于AHP層次分析法的改進Dijkstra算法

2.1AHP層次分析法

2.1.1 多約束條件權重的獲取

AHP層次分析法是美國運籌學家薩迪教授提出的，該方法在賦權的過程中能夠充分利用專家的經驗，并具有較廣的適用范圍[13]。在存在多約束條件的路網模型中，AHP層次分析法能夠設計出一種滿足用戶需求的權重矩陣。

采用層次分析法確定權重矩陣的步驟如下所示。

(1) 建立遞階層次結構模型

在交通路網中，對車輛行駛的約束條件有許多，按照車輛行駛的實際情況并根據層次分析思想建立了影響道路權值的層次結構模型。如圖2所示。

圖2 道路權值的層次結構

(2) 構造兩兩比較判斷矩陣

專家參照表1對指標體系各個層次的元素進行評價意見，得出兩兩判斷矩陣A，并根據式(6)從判斷矩陣中計算出每個指標相對于上一層元素的相對權重。

AW=λmaxW

(6)

其中W是特征向量，將其歸一化處理后得出相應指標權重。

表1 1- 9標度的含義

(3) 一致性判斷

若C.R.<0.1，則認為判斷矩陣滿足一致性要求。表2為最終求得的影響道路權值的各項指標所占的權重。

表2 影響道路權值的指標及其權重

2.1.2 多約束條件的整合

在得到了不同約束條件的影響權重后，我們需要將不同約束條件整合在一起。首先我們將不同約束條件分為成本型和效益型，對每個約束條件設其取值范圍為ui=(ai,bi)，當約束條件為成本型時，根據式(7)進行量化，當約束條件為效益型時，根據式(8)進行量化。

(7)

(8)

我們將得到的權重以及該約束條件量化后的結果通過式(9)進行計算，以W作為道路的權值，并以此來構建路徑規劃問題中的鄰接矩陣。

W=ω1×g1+ω2×g2+…+ω6×g6

(9)

2.2Dijkstra算法的改進

2.2.1 優先隊列

在Dijkstra算法中，最消耗時間的一個步驟就是在未標記的結點集合中找到距當前結點距離最小的那個結點(下文稱為最小結點)，然后更新距離矩陣。如果不采取任何排序策略，在數據量較大的情況下，這將嚴重影響算法的執行速度。而Dijkstra算法的這種運算策略恰恰與優先隊列這種數據結構的特點相符，找到最小結點并標記的步驟恰恰與優先隊列的deleteMin(刪除最小者)操作相似。

本文采用二叉堆對優先隊列進行具體實現。二叉堆具有兩個性質，即結構性和堆序性，因為我們需要尋找的是最小結點，所以在構建二叉堆時將最小結點放在根結點處，這使得Dijkstra算法在進行最小結點搜索的時候只需要提取根結點就能夠得到滿足要求的結點，再令剩余的結點保持堆序性形成一個新的最小二叉堆，重復這個過程即可滿足算法的需要。在這個過程中我們不僅得到了最小結點，還省去了經典Dijkstra算法中標記結點的工作，因為最小結點已經自動在最小二叉堆中刪除。堆結構的另一個優點是我們只需用一個一維數組就能夠實現堆，從而實現對交通路網中待搜索結點的存儲。通常二叉堆數組中任意位置i上的元素，其位置2i上為其左兒子，位置2i+1上為其右兒子，其父結點則在i/2位置上，而在本文所構建的二叉堆數組中還將在其第n+1個位置上存放堆結點的數目。

用一個例子來說明本文中最小二叉堆的數組表示方法，每個結點對應的值如表3所示。其數組實現如圖3所示。

表3 結點數值表

3521764712345678

圖3 二叉堆的數組實現

2.2.2 結點的篩選

Dijkstra算法是一種貪婪算法，它會以起點為圓心向外發散式的搜索結點。在實際操作中，經典Dijkstra算法可能會遍歷圖中的任意結點，即使該結點距離起點非常遠，顯然這將消耗大量的時間和資源并且是無意義的。而文獻[3]雙向Dijkstra算法從兩端同時向中間搜索結點，理想情況下能夠減少近50%的搜索結點的數目，但是當結點數目達到一定規模的時候，從起始結點和目的結點之間有許多不同的路徑，在最壞的情況下雙向搜索會是單向搜索工作量的兩倍，故雙向Dijkstra算法并沒有看上去那么高的搜索效率。并且當搜索迭代次數需要進行成百上千次乃至更高時，通過復雜計算篩選結點的方式反而會增加路徑規劃算法的時間。

本文根據現代交通路網的特點：待搜索結點與起始結點連線距離小于起始結點與目的結點之間距離的結點被選取為最優路徑中結點的概率極大，提出了一種基于距離限制的可變范圍的結點篩選策略，進一步改進了Dijkstra算法的效率，提升了算法質量。我們通過確定起點s的坐標(x1,y1)，和終點e的坐標(x2,y2)，然后通過式(10)，求得優先搜索范圍的半徑。

(10)

當搜索結點不在本文所設定的圓形搜索范圍內時，我們將該結點“拋棄”使其不在優先搜索結點的范圍之中，偽代碼如下所示：

DISTANCELIMIT(G, s ,e , n)

1 Q←?

2 R←DISTANCE(s ,e , n)

//確定搜索范圍半徑

3.for each vertex v∈V[G]

4 IF DISTANCE(s ,v)

5 Q←Q∪{v}

因為在交通路網中兩點之間一定是可達的，為了避免在結點篩選過程中丟失重要路徑，從而出現改進Dijkstra算法無法搜索到最優路徑的情況，本文使用的距離限制方法是一種可變范圍的結點篩選策略。我們在式(10)中引入一個常數項C和一個變量n，當改進Dijkstra算法沒有找到最優路徑時，我們將變量n按梯度增加，從而擴大改進Dijkstra算法的搜索范圍，使其覆蓋范圍包括更多數目的結點，再進行搜索。如此反復，直至改進Dijkstra算法在交通路網中發現最優路徑為止。

如圖4所示，在使用結點篩選策略以前改進Dijkstra算法需要對全圖的結點進行搜索運算，即使該結點已經遠遠偏離目的結點，根本不可能成為最優路徑中的一員。在引入基于距離限制的可變范圍的結點篩選策略以后，我們將搜索范圍牢牢控制在本文所規定的圓形范圍之內，這使得我們需要進行搜索的結點數目大大減少，并且搜索結點的位置更加集中，不會出現搜索遠距離偏移的現象，提高了搜索的效率和質量。一旦在規定的范圍內沒有搜索到最優路徑，那么算法就會自動進入到下一輪搜索之中，擴大搜索范圍直至發現最優路徑。通過實驗驗證，本文所設計的基于距離限制的可變范圍的結點篩選策略能夠滿足交通路網的需求，最終找到最優路徑。

圖4 改進Dijkstra算法使用可變范圍的結點篩選策略搜索最優路徑

綜上所述，改進Dijkstra算法在交通路網中搜索最優路徑的流程如圖5所示。

圖5 改進Dijkstra算法搜索最優路徑的流程圖

3 仿真結果與分析

為了驗證改進后算法的性能，在Matlab中設計仿真實驗進行驗證。首先在Matlab中讀取矢量電子地圖的圖形數據，然后在Matlab中構建矢量電子地圖，如圖6所示。我們先在僅考慮道路長度的情況下使用改進Dijkstra算法和經典Dijkstra算法對起點為58號結點，終點為141號結點以及起點為26號結點，終點為164號結點的兩條路徑進行搜索，在表4和表5中記錄運行時間、搜索結點數等相關實驗數據和結果。

圖6 交通路網模型

起點終點運行時間搜索結點數量路徑經典Dijkstra改進Dijkstra58581411410.202s0.053s644858→79→80→98→99→118→140→141

表5 實驗結果對比表2

在表4和表5的對比分析中可知，改進Dijkstra算法在運行時間上明顯少于經典Dijkstra算法，這不僅僅是因為改進Dijkstra算法搜索的結點數目偏少，還因為改進Dijkstra算法的。

對于圖7所示的實驗而言，經典Dijkstra算法在252個節點中搜索了64次確定了最優路徑58→79→80→98→99→118→140→141；改進Dijkstra算法經篩選后確定了更加精確的結點范圍，確定最優路徑在其中126個結點之間，隨后在126個節點中搜索了48次確定了最優路徑58→79→80→98→99→118→140→141。

對于圖8所示的實驗而言，經典Dijkstra算法在252個節點中搜索了115次確定了最優路徑26→42→43→56→76→78→96→112→113→114→115→137→138→164，而改進Dijkstra算法則在147個節點中搜索了89次確定了同樣的路徑。

圖7和圖8中的粗線為標記出的此次算法實驗所獲得最優路徑。

圖7 起點為58、終點為141的路線

圖8 起點為26、終點為164的路線

單次搜索效率要明顯優于經典Dijkstra算法。因此可以看出，改進Dijkstra算法在路徑規化效率上有了很大的提高。兩次實驗所搜索到的最優路徑是一致的，故改進Dijkstra算法在提升工作效率的同時并沒有破壞其路徑規劃的準確性。并且通過這兩組實驗數據我們還可以發現，使用結點篩選策略處理后的Dijkstra算法的搜索區域明顯減小，這一特點將隨著路網復雜程度的增加有著明顯的提高；并且搜索的路徑越短，搜索結點的范圍越精確，故該算法更適合短距離搜索或城市內部搜索，恰恰適用于在城市車聯網中應用。

我們再在多種約束條件的情況下使用改進Dijkstra算法對起點為58號結點和終點為141號結點進行路徑搜索，得到如圖9所示的路線圖。

圖9 多約束條件下起點為58、終點為141的最優路線

在考慮了多種約束條件帶來的影響以后，我們所得到的路線為58→79→80→81→82→100→119→141，該路線和圖7所示的路線有著些許的不同，但是不難發現圖9所顯示的路線更加平滑、連貫。此時雖然所得到的路徑不是最短路徑，但是在可以接受的范圍內，并且更加符合當代人的駕駛習慣、道路質量明顯優于圖7所示的道路質量，故該路徑應為最優路徑。

綜上所述，在考慮多種約束條件的影響下，改進Dijkstra算法不僅縮小了搜索區域，提升了搜索線路的效率和質量。還通過引入二叉堆使得單次搜索需要耗費的時間大大減少，這也是改進Dijkstra算法效率顯著提升的重要原因之一。

4 結 語

Dijkstra算法是路徑規劃領域得到廣泛應用的一種算法。本文提出一種基于AHP層次分析法的改進Dijkstra算法。將二叉堆引入到經典Dijkstra算法當中，又結合對現代路網特性的考慮，提出了基于距離限制的可變范圍的結點篩選策略來縮小搜索區域，節省了存儲空間，減少了搜索次數，提高了搜索效率，使得算法的性能得到了全面提升。并在考慮多種約束條件的情況下，構建權重鄰接矩陣，使得算法所得到的路徑更加合理，更加符合當代人的駕駛習慣。實驗表明，基于AHP層次分析法的改進Dijkstra算法能夠有效地在矢量電子地圖中找到最優路徑并標記出來，并且該算法獨有的特性更加適用于在城市車聯網中應用，具有良好的使用價值。

[1] Bast H, Delling D, Goldberg A, et al. Route Planning in Transportation Networks[J]. Microsoft Research, 2015.

[2] 沈國杰. 車載導航系統的最優路徑規劃算法研究[D]. 大連理工大學, 2013.

[3] 李杰, 張文棟, 楊衛. 雙向Dijkstra算法設計與實現[C]// 中國宇航學會深空探測技術專業委員會學術年會. 2007.

[4] Yin C, Wang H. Developed Dijkstra shortest path search algorithm and simulation[C]// Computer Design and Applications (ICCDA), 2010 International Conference on. IEEE, 2010:V1-116 - V1-119.

[5] 王樹西, 吳政學. 改進的Dijkstra最短路徑算法及其應用研究[J]. 計算機科學, 2012, 39(5):223-228.

[6] 楊柳. 車載導航系統中路徑規劃算法的研究及實現[D].北京交通大學, 2008.

[7] Wang S X, Zhao X Q. The improved Dijkstra's shortest path algorithm[C]// Natural Computation (ICNC), 2011 Seventh International Conference on. IEEE, 2011:2313-2316.

[8] 郁曉慧. 基于智能終端的車載導航路徑規劃的研究[D]. 東華大學,2015.

[9] Kang H I, Lee B, Kim K. Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm[C]// The Workshop on Computational Intelligence & Industrial Application. IEEE Computer Society, 2008:1002-1004.

[10] 林青巖. 智能交通中車輛最優路徑規劃策略研究[D].吉林大學,2013.

[11] Zhang F, Liu J. An Algorithm of Shortest Path Based on Dijkstra for Huge Data.[C]// Fuzzy Systems and Knowledge Discovery, Fourth International Conference on. IEEE, 2009:244-247.

[12] Xiao J X, Lu F L. An improvement of the shortest path algorithm based on Dijkstra algorithm[C]// Computer and Automation Engineering (ICCAE), 2010 The 2nd International Conference on. IEEE, 2010:383-385.

[13] Zhi-Jun S U, Yan H. Research on the Feasibility Evaluation of Helicopter Route Based on GIS and AHP[J]. Surveying & Mapping of Geology & Mineral Resources, 2013.

RESEARCH ON SIMULATION OF OPTIMAL PATH OF TRAFFIC NETWORK

Yang Zhiyu Zong Qun

(SchoolofAutomationandElectricalEngineering,TianjinUniversity,Tianjin300072,China)

In the increasingly complex road conditions today, the shortest path between two points in the traffic network is no longer the optimal path that people need to drive. The traditional path planning method has the problem that the factors of path planning are too single and the search efficiency is too low. In the path planning problem, there is a lack of a specific method in the multi-constraint conditions to achieve the optimal search path in the traffic network. Aiming at these problems, an improved Dijkstra algorithm based on analytic hierarchy process (AHP) is proposed. Based on the accuracy of the classical Dijkstra algorithm, the algorithm considers various constraints and greatly improves the search efficiency. The simulation results show that the improved Dijkstra algorithm based on AHP has good performance and can meet the requirements of current path planning problems.

Route planning Dijkstra algorithm Internet of vehicles Binary heap AHP

2016-05-12。國家自然科學基金面上項目(61273092)。楊智宇，碩士生，主研領域：車聯網，無人駕駛。宗群，教授。

TP368.1

A

10.3969/j.issn.1000-386x.2017.07.004