基于A*算法的復(fù)雜交通環(huán)境下出行者最優(yōu)路徑分析研究

李少偉 曹成濤

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

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

中圖分類號(hào)：TP312 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：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）

隨著移動(dòng)地理信息系統(tǒng)（GIS）技術(shù)、全球衛(wèi)星定位（GPS）技術(shù)、無線通信技術(shù)的迅猛發(fā)展和廣泛應(yīng)用，出行者利用移動(dò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í)進(jìn)行，未充分顧及出行者行車習(xí)慣和復(fù)雜交通環(huán)境的影響，得到的路徑往往只考慮距離最短，結(jié)果通常包含擁擠的道路、過多紅綠燈等，不符合出行者預(yù)期，因此，規(guī)劃符合出行者行車習(xí)慣的行程，不但能提高出行者的行車效率和駕駛體驗(yàn)，也能緩解城市交通擁堵壓力，具有重要的現(xiàn)實(shí)意義。

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

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

城市交通的快速發(fā)展，使得城市道路網(wǎng)除了具有一般道路網(wǎng)的特點(diǎn)之外，還有其特殊之處：①路段及節(jié)點(diǎn)眾多，對(duì)于大型城市來說，城市道路及交叉口數(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)，道路擁堵情況在時(shí)間上表現(xiàn)出明顯的周期性，由于道路擁堵程度的易變性，對(duì)于出行時(shí)間較長(zhǎng)的路況預(yù)測(cè)需要綜合實(shí)時(shí)交通信息和歷史交通信息。

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

③路口延誤，包括紅綠燈等待時(shí)間、通行延誤時(shí)間等，人們因?yàn)榻煌〒矶碌却煌粝牡臅r(shí)間越來越長(zhǎng)[7]。

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

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

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

6 ? 結(jié)論（Conclusion）

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

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

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

[2] 朱慶，李淵.2007道路網(wǎng)絡(luò)模型研究綜述[J].武漢大學(xué)學(xué)報(bào)（信息科學(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] 孫秋霞，孫璐，劉新民.基于出行個(gè)體行為的交通網(wǎng)絡(luò)效率研究[J].重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，35（2）：110-113.

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

[7] 朱云虹，袁一.基于改進(jìn)A*算法的最優(yōu)路徑搜索[J].計(jì)算機(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ì)算[J].測(cè)繪科學(xué)，2015，40（3）：127-131;122.

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

作者簡(jiǎn)介：

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

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