一種基于路網(wǎng)躍遷的高效路徑搜索算法

武娟+高正東

摘要：針對移動導(dǎo)航設(shè)備內(nèi)存小、運算能力相對弱的特點，以分級分幅路網(wǎng)模型為基礎(chǔ)，設(shè)計了一種新的以“路網(wǎng)躍遷”為核心思想的高效最優(yōu)路徑搜索算法，并應(yīng)用到實際產(chǎn)品中。實踐表明，該搜索算法具有計算速度快、消耗內(nèi)存低、路線質(zhì)量總體接近最優(yōu)等優(yōu)點。

關(guān)鍵詞：分級；分幅；路網(wǎng)躍遷；路徑搜索算法

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2015）30-0073-02

An Efficient Route Search Algorithm Based on Road Transition

WU Juan， GAO Zheng-dong

（SCTV， Shucheng 231300， China）

Abstract： Corresponding to the shortage of having less memory and weaker compute capability within mobile navigation device， a new efficient best route search algorithm based on road classification and map sheet， which takes “road transition” as key point， is implemented and has being applied to the real products. Practice has shown that it has advantage of faster speed， less memory occupation， and perfect route quality， etc.

Key words： road classification； map sheet； road transition； route search algorithm

1 概述

為了適應(yīng)車載設(shè)備內(nèi)存低、運算能力相對較弱的特點，我們對路網(wǎng)進行了分級和分幅處理。分級指的是將路網(wǎng)根據(jù)道路屬性分成多個等級，如將地區(qū)內(nèi)路網(wǎng)分成三級（0級，1級，2級），將全國路網(wǎng)分成兩個等級（3級、4級）；分幅指的是將整個路網(wǎng)網(wǎng)格化，每個網(wǎng)格覆蓋路網(wǎng)一定的區(qū)域，如10公里*10公里區(qū)域范圍。分級的好處是允許搜索過程從低級路網(wǎng)躍遷到高級路網(wǎng)，加快搜索速度；分幅的好處是降低搜索的節(jié)點空間，降低內(nèi)存占用率。關(guān)于分級分幅路網(wǎng)數(shù)據(jù)組織格式的詳細介紹可參閱文獻[1]。

在分級分幅路網(wǎng)數(shù)據(jù)做支撐的基礎(chǔ)上，我們改進了經(jīng)典的Dijkstra算法，引入路網(wǎng)躍遷機制，設(shè)計了高效的雙向啟發(fā)式最優(yōu)路徑搜索算法。經(jīng)典的Dijkstra算法已產(chǎn)生許多變體[2-3]，總的來說，現(xiàn)有最優(yōu)路徑搜索算法基于的均不是分級和分幅的地圖數(shù)據(jù)，因此本算法首先在基礎(chǔ)數(shù)據(jù)層次上對時空效率的提高提供了有力保證。

2 算法描述

為了保證快速的搜索過程和良好的路線質(zhì)量，我們對算法做了多方面的改進，主要有：利用四叉堆進行節(jié)點排序、雙向搜索、優(yōu)化的代價函數(shù)、路網(wǎng)躍遷以及路網(wǎng)圖幅化。通過將地區(qū)內(nèi)路網(wǎng)和全國路網(wǎng)進行分級分幅化處理，在所有類型路網(wǎng)上都支持路網(wǎng)躍遷操作。以下詳細描述算法的搜索過程，算法原理示意圖如圖1所示：

搜索算法用到三個地圖數(shù)據(jù)：發(fā)源地區(qū)路網(wǎng)、目的地區(qū)路網(wǎng)、全國路網(wǎng)。根據(jù)出發(fā)點和目的點所在地區(qū)位置，將搜索算法分為以下三類：

1）地區(qū)內(nèi)搜索：出發(fā)點和目的點都在同一地區(qū)內(nèi)，則搜索僅在本地區(qū)范圍內(nèi)進行，不需要搜索全國路網(wǎng)，搜索過程相對最簡單。

2） 相鄰地區(qū)搜索：出發(fā)點和目的點不在同一地區(qū)，但地區(qū)內(nèi)搜索到達的邊界點存在重合，即一個地區(qū)的地區(qū)邊界點同時也是另一個地區(qū)的地區(qū)邊界點，此時也不需要搜索全國路網(wǎng)。

3） 跨地區(qū)搜索：當(dāng)出發(fā)點和目的點既不在同一地區(qū)，也不發(fā)生兩個地區(qū)邊界點重合時，就必須借助全國路網(wǎng)搜索兩個地區(qū)之外的路線。

以下給出跨地區(qū)算法描述，地區(qū)內(nèi)搜索和相鄰地區(qū)搜索是跨地區(qū)搜索的特例情況，不再詳述。

1） 由發(fā)源點經(jīng)緯度找到發(fā)源最近路段；

2） 由發(fā)源最近路段選擇某個端點作為出發(fā)點；

3） 由目的點經(jīng)緯度找到目的最近路段；

4） 由目的最近路段選擇某個端點作為到達點；

5） 以到達點為目的點，從發(fā)源地區(qū)正向搜索到一條到達節(jié)點是地區(qū)邊界點S的路線L1；

6） 以出發(fā)點為出發(fā)點，從目的地區(qū)逆向搜索到一條前驅(qū)節(jié)點是地區(qū)邊界點D的路段L2；

7） 將源地區(qū)邊界點S向全國路網(wǎng)投影，找到其在全國路網(wǎng)上的投影節(jié)點 Sp；

8） 將目的地區(qū)邊界點D向全國路網(wǎng)投影，找到其在全國路網(wǎng)上的投影節(jié)點Dp；

9） 設(shè)置投影節(jié)點Sp的所有前趨節(jié)點為回避點，防止起始回頭路；

10） 設(shè)置投影節(jié)點Dp的所有后繼節(jié)點為回避點，防止到達回頭路；

11） 在全國路網(wǎng)上，雙向搜索一條路線L3；

12） 合并總路線：L = L1 + L3 + L2；

13） 剔除重復(fù)路段，組成最終路線。

躍遷過程如圖2所示，搜索起始階段，搜索過程在等級最低的路網(wǎng)中進行，隨著搜索的進行，不斷地有新的節(jié)點加入，其中必定包括躍點（此特性由數(shù)據(jù)源保證）。當(dāng)躍點成為最小代價節(jié)點從OPEN表彈出時，按照躍遷條件判斷其是否符合躍遷條件，如符合則記錄躍點在高等級路網(wǎng)上的投影點，退出當(dāng)前等級路網(wǎng)，并載入允許躍入的最大等級路網(wǎng)繼續(xù)進行搜索。

3 幾個問題

3.1 盡量走高等級路

由于實際路網(wǎng)中，等級相同的道路，往往路況卻相差很大，因此，在實際應(yīng)用中，為了有更好的通行質(zhì)量，在容許的路線長度范圍內(nèi)，客戶常常要求盡量多走高等級的道路。為此我們設(shè)計了新的啟發(fā)函數(shù)，核心思想是以高等級路網(wǎng)所占比例作為啟發(fā)條件。

對于某個節(jié)點n，其總代價函數(shù)為：

f（n） = W（g）G（n） + W（h）H（n） – n * R（n）

其中，f：節(jié)點總代價；G：實際代價，為實際已走路線長度；H：估計代價，為當(dāng)前點到目的點的直線距離；R：已經(jīng)過的高等級路段長度；n：高等級路段比例調(diào)整因子；

需要說明的是，引入高等級路網(wǎng)比例啟發(fā)因子后，總代價函數(shù)f（n）仍滿足完備性要求。

通過合理地改變調(diào)整因子n的值，可得到不同質(zhì)量的搜索路線。n越大，路線中的高等級道路所占比例越大，通行性越好。但n也不可過大，否則會容易出現(xiàn)為了盡量走高速而避開距離短但等級較低的“過度繞路”的現(xiàn)象。據(jù)實際經(jīng)驗，n通常取0.2～0.6較合適。

3.2 躍遷時機

為了解決路網(wǎng)躍遷可能帶來的走回頭路、找不到路等現(xiàn)象，躍遷點的選擇必須符合如下三個條件：

1）已經(jīng)過一定距離的高等級路段，且躍遷點在高等級路段；

2）無轉(zhuǎn)向限制約束；

3）當(dāng)前節(jié)點所在路網(wǎng)等級小于最大允許躍遷等級；

同時為了最大程度提高路徑計算效率，取節(jié)點最大躍遷等級躍遷。

3.3 實驗和性能分析

將搜索算法移植到PC上，在實際路網(wǎng)上進行運算，記錄每次搜索載入的圖幅數(shù)、運算時間和生成路線，并將路線導(dǎo)入到MapInfo中人工評判路線質(zhì)量，如圖3所示。

表1為真實路網(wǎng)下躍遷與非躍遷對搜索性能的比較，其中地區(qū)內(nèi)搜索時節(jié)點表示為圖幅號和節(jié)點號，跨地區(qū)搜索時節(jié)點表示為經(jīng)緯度。統(tǒng)計分析表明：

1） 在較近的距離范圍內(nèi)，躍遷與非躍遷兩種搜索算法的效率大致相等，因為不需要躍遷到高等級路網(wǎng)。分級算法的效率偶爾還略微下降，這是由于增加了躍遷點判斷和處理的開銷。

2） 當(dāng)搜索距離較遠，需跨越多個圖幅時，分級算法體現(xiàn)出了其優(yōu)越性。表現(xiàn)在兩個方面：

① 搜索的效率更高。由于可以躍遷到更高等級路網(wǎng)，需載入的0級路網(wǎng)圖幅數(shù)量大大減少，且更高等級路網(wǎng)的搜索空間較小，因而搜索的時空開銷大大降低。而對于跨地區(qū)大范圍搜索，性能提升最為明顯，通常躍遷時載入的圖幅數(shù)目要比沒有躍遷時載入的圖幅數(shù)目少50%以上，效率提高1倍以上。

② 搜索的路線可能更佳。由于高級路網(wǎng)中的路段具有更佳的通行特性，因而分級算法有可能得到具有更佳通行質(zhì)量的搜索路線。

4 結(jié)論

車載導(dǎo)航設(shè)備內(nèi)存小、CPU運算速度較低，因此必須設(shè)計高效的路網(wǎng)存儲模型和路線搜索，本文在自主研發(fā)的分級分幅路網(wǎng)模型的基礎(chǔ)上，開發(fā)了一種基于路網(wǎng)躍遷高效的最優(yōu)路徑搜索算法，詳細描述了算法的基本原理和幾個關(guān)鍵問題點的處理。統(tǒng)計分析表明，該算法計算速度快、消耗內(nèi)存低，且得到的路線總體質(zhì)量接近最優(yōu)，具有良好的實用性。

參考文獻：

[1] 胥銳. 車載導(dǎo)航電子地圖的路網(wǎng)模型[J]. 電腦知識與技術(shù)， 2008（25）.

[2] 嚴(yán)寒冰，劉迎春. 基于GIS的城市道路網(wǎng)最短路徑算法探討[J]. 計算機學(xué)報，2000，23（2）：210.

[3] 唐文武，施曉東，朱大奎. GIS中使用改進的Dijkstra算法實現(xiàn)最短路徑的計算[J]. 中國圖像圖形學(xué)報，2000，5A（12）：1019.