李少偉 曹成濤

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

關鍵詞：最優(yōu)路徑;A*算法;交通規(guī)則;道路權值

中圖分類號：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）

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

2 ? 城市道路網(wǎng)絡模型（Urban road network model）

最優(yōu)路徑分析本質屬于圖論研究中的一個經(jīng)典問題，但在實際應用中，需要結合交通規(guī)則和實際道路環(huán)境，將其抽象為有現(xiàn)實意義的城市道路網(wǎng)絡模型。

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

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

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

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

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

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

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

6 ? 結論（Conclusion）

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

參考文獻（References）

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

[2] 朱慶，李淵.2007道路網(wǎng)絡模型研究綜述[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] 高明霞.道路交通網(wǎng)絡最短路徑關鍵轉向研究[J].公路，2018（9）：199-202.

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

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

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

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

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

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

作者簡介：

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

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