聶易彬, 譚明軍, 劉 剛, 馬 璐
(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)地圖的最短路徑搜索。
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*算法確定能找到一條最短路徑。
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.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.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)
本文以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é)果
本文在傳統(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)化,未來需進行更深入的研究。