李少偉 曹成濤

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

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

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

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

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

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

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

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

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

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

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

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

6 ? 結(jié)論（Conclusion）

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

參考文獻(xiàn)（References）

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

[2] 朱慶，李淵.2007道路網(wǎng)絡(luò)模型研究綜述[J].武漢大學(xué)學(xué)報（信息科學(xué)版），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)絡(luò)最短路徑關(guān)鍵轉(zhuǎn)向研究[J].公路，2018（9）：199-202.

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

[6] 段麗瓊，劉立國.應(yīng)用層次分析法確定道路屬性指標(biāo)的權(quán)重[J].海洋測繪，2004，24（3）：44-46.

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

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

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

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

作者簡介：

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

曹成濤（1981-），男，博士，教授.研究領(lǐng)域：智能交通技術(shù).