基于改進A*算法的高速公路互聯(lián)網(wǎng)地圖最短路徑搜索研究

聶易彬， 譚明軍， 劉 剛， 馬 璐

(1.招商局公路網(wǎng)絡科技控股股份有限公司， 北京 100022； 2.招商局重慶交通科研設計院有限公司， 重慶 400067)

國內(nèi)外學者對最短路徑問題進行了大量研究，產(chǎn)生了許多經(jīng)典算法，如Dijkstra算法[1]、Floyd算法[2]、Johnson算法[3]、A*算法[4]、D*算法[5]等，但其往往耗時較長，難以滿足高速公路靜態(tài)網(wǎng)絡的時效性要求。A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法[6]，國內(nèi)眾多學者進行了研究，但主要集中在離線地圖的最短路徑搜索上[7-14]。鑒于此，本文通過高德地圖自帶的API開發(fā)功能，創(chuàng)建了高速公路互聯(lián)網(wǎng)地圖。在傳統(tǒng)A*算法的基礎(chǔ)上，結(jié)合高速公路互聯(lián)網(wǎng)地圖的特點，對傳統(tǒng)A*算法中的網(wǎng)絡節(jié)點、數(shù)據(jù)庫、啟發(fā)式函數(shù)進行了改進，并通過重慶高速公路互聯(lián)網(wǎng)地圖實例對改進A*算法進行了應用，驗證了該算法的可行性和高效性。本文提出的改進A*算法在確保能搜索到最短路徑的前提下，可大大提高搜索的效率，可應用于大區(qū)域高速公路互聯(lián)網(wǎng)地圖的最短路徑搜索。

1 A*算法

1.1 基本原理

A*算法是一種啟發(fā)式搜索算法，常被用來解決靜態(tài)網(wǎng)絡中的最短路徑問題。A*算法的估價函數(shù)如下：

f(n)=g(n)+h(n)

(1)

式中：f(n)是從初始節(jié)點經(jīng)由任意節(jié)點n到目標節(jié)點的估價函數(shù)；g(n)是從初始節(jié)點到節(jié)點n的實際代價；h(n)為啟發(fā)式函數(shù)，表示節(jié)點n到目標節(jié)點的最優(yōu)路徑估計代價。

當h(n)比實際代價小或相等時，A*算法確定能找到一條最短路徑。

1.2 算法流程

A*算法的實現(xiàn)流程[15]如下：

1) 建立2個列表，分別命名為開放列表和關(guān)閉列表，把當前節(jié)點周圍可到達的節(jié)點加入到開放列表中，已訪問過的節(jié)點加入到關(guān)閉列表中。

2) 當從當前節(jié)點開始搜索到下一個節(jié)點時，均是從開放列表中進行比較f值的大小，把f值最小的節(jié)點作為下一步搜索的起點。

3) 所有當前節(jié)點可到達的節(jié)點再次加入到開放列表中，重新比較f值，并根據(jù)f值的大小按升序進行排列隊列。在搜索過程中，使用廣度優(yōu)先算法依次選取隊列的首元素，計算可能子節(jié)點的g、h和f值，直到找到目標節(jié)點或雖然沒有找到目標節(jié)點但開放列表已為空時，算法結(jié)束。

2 改進A*算法

2.1 互聯(lián)網(wǎng)地圖創(chuàng)建

2.1.1 網(wǎng)絡數(shù)據(jù)結(jié)構(gòu)

一個路段由多個相鄰坐標點數(shù)組構(gòu)成，相鄰坐標點的通行規(guī)則有3種，根據(jù)路段的方向?qū)傩詃irection值加以判斷。判斷準則如下：

1) 如果路段direction=0，表示首節(jié)點至尾節(jié)點之間可雙向通行。

2) 如果路段direction=1，表示首節(jié)點至尾節(jié)點之間可單向通行。

3) 如果路段direction=-1，表示尾節(jié)點至首節(jié)點之間可單向通行。

考慮到網(wǎng)絡路段可能存在3種通行方向，如果逐一去判斷路段的方向?qū)傩?，會造成路徑搜索時間較長。為減少路徑搜索時間，本文對方向?qū)傩詃irection=-1和direction=0的路段統(tǒng)一作如下處理：

1) 將direction=-1的路段坐標進行坐標反轉(zhuǎn)，即direction=-1的路段m=[(x1，y1),(x2，y2)，…，(xn-1，yn-1)，(xn，yn)]反轉(zhuǎn)為direction=1的路段m′=[(xn，yn),(xn-1，yn-1)，…，(x2，y2)，(x1，y1)]。

2) 將direction=0的路段克隆一份，并對其進行坐標反轉(zhuǎn)處理，即direction=0的路段m=[(x1，y1),(x2，y2)，…，(xn-1，yn-1)，(xn，yn)]變成了路段m=[(x1，y1),(x2，y2)，…，(xn-1，yn-1)，(xn，yn)]和路段m′=[(xn，yn),(xn-1，yn-1)，…，(x2，y2)，(x1，y1)]。

經(jīng)過上述處理后，高速公路網(wǎng)絡中所有路段的通行方向均為從首節(jié)點至尾節(jié)點的單向通行。

2.1.2 互聯(lián)網(wǎng)地圖創(chuàng)建

互聯(lián)網(wǎng)地圖的創(chuàng)建步驟如下：

1) 坐標轉(zhuǎn)換。通過互聯(lián)網(wǎng)地圖API坐標工具，將高速公路網(wǎng)絡節(jié)點的GPS坐標轉(zhuǎn)換成火星坐標。

2) 繪制路網(wǎng)。根據(jù)網(wǎng)絡節(jié)點的火星坐標，通過互聯(lián)網(wǎng)地圖API畫線工具繪制路網(wǎng)。

3) 存儲路網(wǎng)數(shù)據(jù)庫。存儲網(wǎng)絡各路段屬性列表和節(jié)點屬性列表，路段屬性列表包含路段長度、方向、路段名稱、通車年份、車道數(shù)、通行能力、通行速度、通行時間等字段信息，節(jié)點屬性列表包含節(jié)點坐標、節(jié)點鄰接信息等。

2.2 A*算法改進

2.2.1 節(jié)點改進

單個路段內(nèi)可包含多個節(jié)點，少則幾個，多則幾十個，逐點搜索效率低下。本文在建立節(jié)點集合時，只提取路段的首節(jié)點和尾節(jié)點，如圖1所示，可大大提高路徑搜索的效率。

圖1 節(jié)點改進處理

2.2.2 數(shù)據(jù)庫改進

高速公路互聯(lián)網(wǎng)地圖通常以省(直轄市)為單位，各省(直轄市)高速公路網(wǎng)絡基礎(chǔ)數(shù)據(jù)庫一般有5～10年數(shù)據(jù)(包括現(xiàn)狀路網(wǎng)和未來特征年路網(wǎng))，且每年路網(wǎng)路段數(shù)據(jù)和節(jié)點數(shù)據(jù)分別在1萬條以上，傳統(tǒng)方法是直接讀取數(shù)據(jù)庫中的每條數(shù)據(jù)，但效率較低，本文將數(shù)據(jù)庫加載到內(nèi)存上，分年度存儲路段數(shù)據(jù)和節(jié)點數(shù)據(jù)，從緩存上讀取該數(shù)據(jù)，從而大大提高數(shù)據(jù)查詢和搜索的效率。

2.2.3 啟發(fā)式函數(shù)改進

本文以行程時間最短構(gòu)建估價函數(shù)，采用節(jié)點之間的實際距離除以路網(wǎng)平均車速來確定啟發(fā)式函數(shù)。假設g(n)是開始節(jié)點s至當前節(jié)點n的總行程時間，可通過計算起始節(jié)點s至當前節(jié)點n的行程時間總和得到，h(n)是當前節(jié)點n至目標節(jié)點e的行程時間估計，可通過以下函數(shù)計算得到：

(2)

d(n,e)=

(3)

(4)

3 實例分析

本文以2030年重慶高速公路網(wǎng)絡shape格式數(shù)據(jù)作為基礎(chǔ)數(shù)據(jù)，通過高德地圖API創(chuàng)建高速公路互聯(lián)網(wǎng)地圖，創(chuàng)建結(jié)果如圖2所示，其中灰色線為未來年規(guī)劃路網(wǎng)，灰色圓圈代表收費站。該高速公路網(wǎng)包含17 772個路段，16 071個節(jié)點。

圖2 2030年重慶高速公路互聯(lián)網(wǎng)地圖

本文隨機選取5個測試樣本，分別用傳統(tǒng)A*算法、改進A*算法搜索網(wǎng)絡中兩節(jié)點之間的最短路徑。經(jīng)測試，改進A*算法能夠搜索到節(jié)點之間的最短路徑，且與傳統(tǒng)A*算法相比，搜索結(jié)果完全一致，如圖3～圖7所示，說明改進A*算法在最短路徑搜索上可行。圖3～圖7中，黑色帶方向箭頭線代表兩節(jié)點間的最短路徑，標簽框顯示了最短路徑的長度和行程耗時。

圖3 樣本1最短路徑搜索結(jié)果

圖4 樣本2最短路徑搜索結(jié)果

圖5 樣本3最短路徑搜索結(jié)果

圖6 樣本4最短路徑搜索結(jié)果

圖7 樣本5最短路徑搜索結(jié)果

此外，本文對2種算法的最短路徑搜索時間進行了測試，結(jié)果見表1。由表1可知，改進A*算法的最短路徑搜索時間基本控制在毫秒級，而傳統(tǒng) A*算法的最短路徑搜索時間則在毫秒級至秒級之間，改進A*算法相比傳統(tǒng)A*算法在算法性能上有了很大提升，搜索效率更高。

表1 傳統(tǒng)A*算法與改進A*算法下節(jié)點之間最短路徑搜索測試結(jié)果

4 結(jié)束語

本文在傳統(tǒng)A*算法的基礎(chǔ)上，對A*算法中網(wǎng)絡節(jié)點、數(shù)據(jù)庫、啟發(fā)式函數(shù)進行了改進，提出了改進A*算法并進行了應用，認識如下：

1) 改進A*算法能夠搜索到互聯(lián)網(wǎng)地圖中的最短路徑，且搜索時間基本控制在毫秒級，相比傳統(tǒng)A*算法，搜索效率更高。

2) 改進A*算法主要適用于省級(直轄市)高速公路網(wǎng)，對于全國高速公路網(wǎng)，由于其網(wǎng)絡規(guī)模增大幾十倍，搜索最短路徑的時間會大大增加，因此對其適用性不強。

3) 隨著2020年全國高速公路取消省界收費站，全國高速公路已形成一張網(wǎng)，分析跨省節(jié)點之間的最短路徑將會變得十分普遍，如何對A*算法做進一步優(yōu)化，未來需進行更深入的研究。