基于A*算法的動態(tài)路徑研究

鄭甜麗 任彧

摘要：為了優(yōu)化擁堵狀態(tài)的城市路網(wǎng)，對現(xiàn)有車載自主網(wǎng)（VANET， Vehicular Ad-hoc Network）[1]的通信協(xié)議進(jìn)行了相應(yīng)的改變，設(shè)計了交互式的通信策略，克服傳統(tǒng)算法的不足，提出了一種基于A*算法的最優(yōu)路徑。首先，基于實時交通信息，對道路屬性（道路長度、車輛速度、道路密度）信息進(jìn)行收集；然后通過車載自組織網(wǎng)絡(luò)中的路由協(xié)議獲取道路信息進(jìn)行擁塞判定，在獲得大量的實時道路信息的基礎(chǔ)上，利用經(jīng)典的A*算法優(yōu)化車輛行駛路徑，使得改進(jìn)后的算法可以在已知某路段擁堵的情況下選擇一條最優(yōu)路徑，最大限度地滿足駕駛者的駕駛需求。

關(guān)鍵詞：車載自組網(wǎng)；路由協(xié)議；信息采集；最優(yōu)路徑

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2019）04-0201-03

Abstract： In order to optimize the congested urban road network， the communication protocol of the existing Vehicle Autonomous Network （VANET， Vehicular Ad-hoc Network） [1] has been changed accordingly. An interactive communication strategy has been designed to overcome the shortcomings of the traditional algorithm. An optimal path based on A* algorithm is proposed. Firstly， based on real-time traffic information， road attribute information （road length， vehicle speed， road density） is collected； then road information is obtained through routing protocols in vehicular ad hoc networks for congestion determination. On the basis of obtaining a large amount of real-time road information， the classical A* algorithm is used to optimize vehicle routing， so that the improved algorithm can be used in the already existing one. Choosing an optimal route under the condition of knowing a certain section of road congestion can satisfy the driver's driving demand to the greatest extent.

Key words： Vehicle Ad Hoc Network； routing protocol； information collection； optimal path

智能交通系統(tǒng)是將網(wǎng)絡(luò)間通信、計算機(jī)處理以及控制等應(yīng)用到智能化系統(tǒng)中來，從而緩解日益凸顯的交通擁擠、事故不斷等道路交通問題。這個領(lǐng)域的大多數(shù)研究越來越集中在開發(fā)更為有效的算法。Dijkstra[2]和A*[3]算法是兩種熟知的最短路徑算法，其他的算法基本就是這兩種算法的變體，不同的嘗試是為了加快單一來源和單一目標(biāo)情況下的最短路徑搜索。我們在進(jìn)行理論研究的時候往往把它定義為簡單的如何尋找到最短的距離，在現(xiàn)實的交通情況下，對最短路徑的選擇都可以認(rèn)為是在計算最優(yōu)路徑的方案。本文的主要內(nèi)容就是在獲知了道路擁堵情況的基礎(chǔ)上選擇一條由一點到另外一點的最短路徑，應(yīng)用圖論原理將城市道路圖形化，改進(jìn)A*算法，使之可以適用于處于擁堵狀態(tài)的城市路網(wǎng)。

1算法設(shè)計

1.1計算參數(shù)

在最優(yōu)路徑選擇方法中，路徑的權(quán)值計算也是通過實時路況數(shù)據(jù)得到，兩個過程均以實時路況信息為基礎(chǔ)，從而路徑選擇結(jié)果的動態(tài)特性。文獻(xiàn)中有多種計算動態(tài)路徑權(quán)值的方法。另外也有許多文獻(xiàn)改進(jìn)了許多權(quán)值的計算參數(shù)：

1.1.1 機(jī)動性[4]

1.1.2 繞行指數(shù)[5]

1.2改進(jìn)措施

原始經(jīng)典的A*算法的估價函數(shù)是以距離為標(biāo)準(zhǔn)進(jìn)行判斷的，改進(jìn)的A*算法將以路段的權(quán)值作為標(biāo)準(zhǔn)，并且可以在某些路段存在擁堵的情況下進(jìn)行最佳路徑搜索。這樣改進(jìn)的意義在于：在實際的交通路網(wǎng)中路段出現(xiàn)擁堵的情況非常常見，因此極有可能理論上可以滿足距離最短的最佳路徑的某處出現(xiàn)擁堵，在這樣的情況下，重新探索新的路徑以保證車輛能盡快從起點移動至終點，即保證時間上最短。雖然新確定的路徑可能會繞遠(yuǎn)，但在擁堵時使車輛運行的時間最短比距離最短更有意義。

1.3 算法流程

通過比較圖6和圖7可知，道路暢通時的最佳路徑P0為S→3→7→11→12→16→D，這條路徑的權(quán)值為11。而當(dāng)路況出現(xiàn)擁堵情況時選擇的最佳路徑Ps為S→1→4→5→9→13→D，這條路徑的權(quán)值為18。雖然權(quán)值較大，但是在擁堵情況下這種路徑的選擇可以幫助駕駛者避開擁堵路線，較快的抵達(dá)目的地。

3 結(jié)束語

對城市的實際交通路網(wǎng)進(jìn)行了等效，將其近似為一個加權(quán)的有向圖，在擁堵情況下，在該有向圖中再加入一項擁堵路線集作為尋找路徑時的依據(jù)。接下來說明了交通路段的權(quán)值確定方法，最后改進(jìn)了A*算法，使得其可以在道路擁堵時避開擁堵的交叉口進(jìn)行路徑選擇從而確定最佳路徑。由于在車載自組網(wǎng)的路由協(xié)議來獲取信息時，沒有考慮到每個節(jié)點的信息存儲能力與處理過程。改進(jìn)的A*算法只實現(xiàn)了部分仿真，沒有做出全部結(jié)果，此算法許多局限性和不足之處，所以還需要通過以后的學(xué)習(xí)和研究使其不斷完善。

參考文獻(xiàn)：

[1] Hyun Yu， Joon Yoo， Sanghyun Ahn. A VANET Routing based on the real-time road vehicle density in the city environment[D]. Seoul：University of Seoul

[2] 潘若愚，褚偉，楊善林. 基于Dijkstra-PD-ACO算法的大城市公交線路優(yōu)化與評價方法研究[J]. 中國管理科學(xué)，2015，23（9）：106-115.

[3] 熊壬浩，劉羽. A*算法的改進(jìn)及并行化[J].計算機(jī)應(yīng)用，2015，35（7）：1843-1848.

[4] 白塵. 交通路網(wǎng)中最優(yōu)路徑算法的道路權(quán)重選擇[J]. 中國管理信息化，2009，12（15）：54-56.

[5] 張征. 面向功能的支路設(shè)計與單向交通組織評價[D]. 鄭州：鄭州大學(xué)，2016.

[6] 雷東升，諸彤宇. 一種基于實時路況信息的動態(tài)路徑規(guī)劃算法[J]. 計算機(jī)科學(xué)，2008，35（4）：28-30.

【通聯(lián)編輯：謝媛媛】