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

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

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

1 A*算法

1.1 基本原理

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

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

(1)

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

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

1.2 算法流程

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

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

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

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

2 改進(jìn)A*算法

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

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

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

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

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

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

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

1) 將direction=-1的路段坐標(biāo)進(jìn)行坐標(biāo)反轉(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的路段克隆一份，并對其進(jìn)行坐標(biāo)反轉(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)絡(luò)中所有路段的通行方向均為從首節(jié)點(diǎn)至尾節(jié)點(diǎn)的單向通行。

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

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

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

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

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

2.2 A*算法改進(jìn)

2.2.1 節(jié)點(diǎn)改進(jìn)

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

圖1 節(jié)點(diǎn)改進(jìn)處理

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

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

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

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

(2)

d(n,e)=

(3)

(4)

3 實(shí)例分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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