基于A*算法的復雜交通環境下出行者最優路徑分析研究

李少偉 曹成濤

摘 ?要：傳統的路徑規劃未充分考慮出行者行車習慣和復雜交通環境的影響，通常搜索到的路徑不一定符合出行者預期，本文將影響出行者路徑選擇的多種因素進行分析，運用層次分析法（AHP）建立了行程時間最短的出行者道路綜合權值模型，并結合交通規則及實際道路環境使用A*算法進行最優路徑分析，通過廣州市天河區部分道路進行實例驗證，結果證明了本文算法的有效性。

關鍵詞：最優路徑;A*算法;交通規則;道路權值

中圖分類號：TP312 ? ? ?文獻標識碼：A

Abstract：Traditional path planning does not fully consider the influence of traveler's driving habits and complex traffic environment.Usually the searched path does not necessarily meet the traveler's expectations.This paper analyzes the various factors affecting the traveler's path selection，and adopts Analytic Hierarchy Process （AHP） to establish the model of the comprehensive road weight for the traveler with the shortest travel time.A* algorithm is used to analyze the optimal path in combination with the traffic rules and the actual road environment.Example verification is conducted on some roads in Tianhe District of Guangzhou.The results have proven the effectiveness of the proposed algorithm.

Keywords：optimal path;A* algorithm;traffic rules;road weight

1 ? 引言（Introduction）

隨著移動地理信息系統（GIS）技術、全球衛星定位（GPS）技術、無線通信技術的迅猛發展和廣泛應用，出行者利用移動智能終端進行路徑誘導的行為越來越普遍。最優路徑問題是智能交通系統（Intelligent Transportation System，ITS）中路徑誘導子系統（Route Guidance System，RGS）的核心問題[1]，傳統最優路徑搜索主要依據道路等級進行，未充分顧及出行者行車習慣和復雜交通環境的影響，得到的路徑往往只考慮距離最短，結果通常包含擁擠的道路、過多紅綠燈等，不符合出行者預期，因此，規劃符合出行者行車習慣的行程，不但能提高出行者的行車效率和駕駛體驗，也能緩解城市交通擁堵壓力，具有重要的現實意義。

2 ? 城市道路網絡模型（Urban road network model）

最優路徑分析本質屬于圖論研究中的一個經典問題，但在實際應用中，需要結合交通規則和實際道路環境，將其抽象為有現實意義的城市道路網絡模型。

城市交通的快速發展，使得城市道路網除了具有一般道路網的特點之外，還有其特殊之處：①路段及節點眾多，對于大型城市來說，城市道路及交叉口數量多而復雜;②道路網絡密集且結構復雜，多車道、單行線、轉彎限制、限速車道、交通管制、立交系統等交通特征和新的越來越多的交通規則使得城市道路網的結構變得越來越復雜[2]。

①路況，通過百度地圖API獲取城市道路擁堵情況，分為暢通、緩行、擁擠、嚴重擁堵四種通行狀態，道路擁堵情況在時間上表現出明顯的周期性，由于道路擁堵程度的易變性，對于出行時間較長的路況預測需要綜合實時交通信息和歷史交通信息。

②道路等級，城市道路等級分為快速路（高速公路市內路段）、主干道、次干道、支路四類，道路設計行車速度依次降低。

③路口延誤，包括紅綠燈等待時間、通行延誤時間等，人們因為交通擁堵等待交通燈消耗的時間越來越長[7]。

④車道數量，通常將車道數分為四類：4車道及以上、2或3車道、1車道、0車道。

依據圖1的層次結構圖，運用Saaty的1—9及其倒數作為標度的方法構造Ci對目標W的相對重要性判斷矩陣，本文參考文獻[6]多位專家對道路屬性指標的評價意見，給出判斷矩陣元素的值，判斷矩陣W-C及特征向量如表1所示。

由表3和表4可見，因為實際交通環境不同，道路綜合權值并未完全按道路等級劃分，傳統靜態的最短路徑和道路綜合權值下的最優路徑并非同一條路徑，后者得到的路徑未必是距離最短的，但一定是考慮了路況等多種影響因素的最優路徑，出行體驗更好。

6 ? 結論（Conclusion）

自駕出行已成為出行者主要出行方式之一，如何合理的規劃路徑減少行程時間是出行者關注的重要話題。本文針對城市道路網的特點，將影響出行者路徑選擇的多種因素進行分析，運用層次分析法建立基于行程時間的出行者道路綜合權值模型，并結合交通規則及實際道路環境使用A*算法進行最優路徑分析，通過廣州市天河區部分道路進行驗證，相較于傳統最佳路徑分析結果，本文提出的最優路徑算法不僅滿足復雜交通環境下的交通規則約束，而且搜索出的最優路徑更加符合出行者行車習慣和實際情況。

參考文獻（References）

[1] 潘義勇，孫璐.隨機交通網絡環境下自適應最可靠路徑問題[J].吉林大學學報（工學版），2014，44（6）：1622-1627.

[2] 朱慶，李淵.2007道路網絡模型研究綜述[J].武漢大學學報（信息科學版），2007，32（06）：471-476.

[3] Bekhor S，Ben-Akiva M E，Scott Ramming M.Adaptation of logit kernel to route choice situation[J].Transportation Research Record： Journal of the Transportation Research Board，2002，1805（1）：78-85.

[4] 高明霞.道路交通網絡最短路徑關鍵轉向研究[J].公路，2018（9）：199-202.

[5] 孫秋霞，孫璐，劉新民.基于出行個體行為的交通網絡效率研究[J].重慶交通大學學報（自然科學版），2016，35（2）：110-113.

[6] 段麗瓊，劉立國.應用層次分析法確定道路屬性指標的權重[J].海洋測繪，2004，24（3）：44-46.

[7] 朱云虹，袁一.基于改進A*算法的最優路徑搜索[J].計算機技術與發展，2018，28（4）：55-59.

[8] 阮于洲，蔣捷.基于層次分析法的路段屬性求權方法[J].地理信息世界，2004，2（2）：44-48.

[9] 王少帥，蔡忠亮，任福.加權路網分層的最優路徑計算[J].測繪科學，2015，40（3）：127-131;122.

[10] 歐陽圣，胡望宇.幾種經典搜索算法研究與應用[J].計算機系統應用，2011，20（5）：243-247.

作者簡介：

李少偉（1981-），男，碩士，講師.研究領域：GIS/GPS在智能交通中的應用.

曹成濤（1981-），男，博士，教授.研究領域：智能交通技術.