基于北斗導(dǎo)航的路徑規(guī)劃優(yōu)化算法研究

◆汪慧琳

（鄭州大學(xué)地球科學(xué)與技術(shù)學(xué)院 河南 450001）

如今，支持北斗三號(hào)系統(tǒng)信號(hào)的 28 納米芯片已得到廣泛應(yīng)用，國(guó)內(nèi)外主流芯片廠商均推出兼容北斗的通導(dǎo)一體化芯片，支持北斗定位的手機(jī)越來(lái)越多。通過(guò)獲取手機(jī)本身芯片提供的位置，地圖軟件就可以使用BDS進(jìn)行實(shí)時(shí)定位、路徑規(guī)劃等功能。通常的地圖軟件都具備讓用戶選擇起點(diǎn)-終點(diǎn)，從而進(jìn)行兩點(diǎn)之間最佳路徑規(guī)劃的基礎(chǔ)功能?，F(xiàn)在國(guó)內(nèi)的地圖軟件（高德地圖、百度地圖、騰訊地圖等）也具備設(shè)置多個(gè)途經(jīng)點(diǎn)（主要是駕車模式）的路徑規(guī)劃，在手機(jī)端一般可以設(shè)置5個(gè)途經(jīng)點(diǎn)（包括起點(diǎn)和終點(diǎn)），在PC端可設(shè)置途經(jīng)點(diǎn)數(shù)較多的是高德地圖（包括起、終點(diǎn)共8個(gè)）。但目前仍未有一款地圖軟件，能根據(jù)用戶的預(yù)期途經(jīng)點(diǎn)（地點(diǎn)數(shù)大于8）及用戶的時(shí)間期望（愿意用于出行的時(shí)間）給用戶提供智能出行規(guī)劃。一種常見(jiàn)的情況是：用戶在面臨需要規(guī)劃路線的情況時(shí)，容易陷入純粹的局部最優(yōu)規(guī)劃（貪心算法）——總是去往離當(dāng)前位置最近的位置，這往往會(huì)比真正的最優(yōu)規(guī)劃多出許多里程。另一種常見(jiàn)的情況是：由于用戶時(shí)間有限，不能經(jīng)過(guò)所有期望地點(diǎn)。

本文旨在通過(guò)優(yōu)化智能算法得出兩種路徑規(guī)劃方式，一是讓用戶在經(jīng)過(guò)所有預(yù)期途經(jīng)點(diǎn)的條件下盡可能地減少交通里程，二是讓用戶在時(shí)間有限的條件下盡可能地減少交通時(shí)間。當(dāng)基于北斗導(dǎo)航系統(tǒng)的路徑規(guī)劃能夠?yàn)橛脩籼岢龈鼉?yōu)化的方案時(shí)，將會(huì)提升用戶體驗(yàn)。

1 研究思路

首先將用戶所希望前往的地點(diǎn)數(shù)字化。利用北斗導(dǎo)航獲得每?jī)蓚€(gè)地點(diǎn)之間的最佳駕車路徑距離，生成距離矩陣。用戶的想法分為兩類：一類是用戶期望能夠抵達(dá)所有目標(biāo)地點(diǎn)，一類是用戶期望盡可能減少路途上的時(shí)間成本。

圖1 用戶選擇模式

2 研究?jī)?nèi)容

2.1 數(shù)據(jù)采集、處理

本文選取蘇州市25個(gè)地點(diǎn)為測(cè)試用例，數(shù)字及地點(diǎn)對(duì)應(yīng)關(guān)系如下：

0-蘇州站，1-周莊古鎮(zhèn)，2-拙政園，3-虎丘山，4-同里古鎮(zhèn)，5-金雞湖，6-留園，7-寒山寺，8-千燈古鎮(zhèn)，9-蘇州博物館，10-獅子林，11-西山，12-盤門，13-七里山塘，14-天平山，15-甪直古鎮(zhèn)，16-木瀆古鎮(zhèn)，17-錦溪古鎮(zhèn)，18-東山，19-望山，20-穹窿山，21-蘇州大學(xué)，22-吳中太湖風(fēng)景區(qū)，23-滄浪亭，24-網(wǎng)師園。

25個(gè)地點(diǎn)的駕車距離以矩陣形式輸入計(jì)算機(jī)。

2.2 算法優(yōu)化及實(shí)驗(yàn)結(jié)果分析

2.2.1n較小的情況

對(duì)于n小于13的情況，本文采用深度優(yōu)先算法（DFS）實(shí)現(xiàn)對(duì)所有路徑的遍歷。第一類規(guī)劃問(wèn)題中，對(duì)于n較大的情況，本文先后實(shí)驗(yàn)了蟻群算法（ACO）、模擬退火算法（SA）。

（1）深度優(yōu)先算法（DFS）

深度優(yōu)先算法（DFS）流程如圖2。

圖2 DFS 算法流程

通過(guò)對(duì)該算法的優(yōu)化，如建立哈希表以快速判重、減支，可以對(duì)n小于13的情況做出快速準(zhǔn)確的處理。

（2）蟻群算法（ACO）

圖3 ACO 算法流程

蟻群算法中，每個(gè)地點(diǎn)對(duì)于其他的任意一個(gè)地點(diǎn)都有一個(gè)啟發(fā)值，即啟發(fā)因子，初始化值為該點(diǎn)與另一點(diǎn)距離的倒數(shù)。這表示：兩個(gè)地點(diǎn)之間的距離越近，啟發(fā)因子越大，因而螞蟻選擇此點(diǎn)的概率越大。

同樣，每個(gè)地點(diǎn)對(duì)于其他的任意一個(gè)地點(diǎn)都有一個(gè)信息素濃度，且隨著迭代（螞蟻群周而復(fù)始的運(yùn)動(dòng)）的進(jìn)行不斷揮發(fā)、更新。其初始化值為螞蟻數(shù)量與貪心路徑（見(jiàn)前文中的人為選擇）長(zhǎng)度的比值。

在t時(shí)刻，螞蟻在地點(diǎn)i對(duì)下一個(gè)地點(diǎn)j的選擇遵循以下公式：

其中表示地點(diǎn)i到地點(diǎn)j的路徑上的信息素濃度，表示地點(diǎn)i到地點(diǎn)j的路徑上的啟發(fā)值。α表示信息素參數(shù)，β表示啟發(fā)因子參數(shù)（在使用函數(shù)時(shí)可自己設(shè)定這兩個(gè)參數(shù)的值，一般取1和2）。

信息素濃度更新公式：

式（2）表示信息素的揮發(fā)；

式（3）表示信息素濃度為揮發(fā)后的濃度加上螞蟻新留下的信息素濃度，每只螞蟻在兩地點(diǎn)間留下的新濃度為該路徑距離和的倒數(shù)。其中，m為曾從地點(diǎn)i抵達(dá)了地點(diǎn)j的螞蟻的數(shù)量，k為對(duì)應(yīng)的路徑標(biāo)記。

最后再設(shè)置迭代次數(shù)，算法即可開(kāi)始運(yùn)行。

蟻群算法的一個(gè)特性是：搜索結(jié)果收斂快，且當(dāng)收斂完成時(shí)，很難再找到一條其他的路徑。當(dāng)所有螞蟻都在同一條路徑上行走時(shí)，即使有螞蟻“突發(fā)奇想”向更優(yōu)秀的路徑邁出了一步，也只能留下濃度不高的信息素，而由于其他螞蟻匯集于同一條路徑，導(dǎo)致那條路徑上的信息素濃度會(huì)很高。因此，蟻群的下一次出動(dòng)中，很少有螞蟻能夠響應(yīng)那位“突發(fā)奇想”的螞蟻先驅(qū)的號(hào)召，它們?nèi)愿鼉A向于往信息素濃度特別高的路徑上行走，故而當(dāng)結(jié)果收斂于局部最優(yōu)解以后，很難再迭代出一條更好的路徑。

實(shí)驗(yàn)表明：迭代次數(shù)達(dá)到了50以后，再增加迭代次數(shù)也難以得到更好的結(jié)果。這樣的一個(gè)優(yōu)點(diǎn)是：減少了計(jì)算機(jī)的算力。當(dāng)導(dǎo)航軟件的服務(wù)器需要為所有用戶提供云計(jì)算功能時(shí)，蟻群算法的易收斂性是它的一個(gè)重要優(yōu)點(diǎn)：對(duì)于每個(gè)用戶的路徑規(guī)劃，僅需要少量的計(jì)算機(jī)算力。

在實(shí)際測(cè)試中，選取了蘇州的13個(gè)地點(diǎn)（其中包含蘇州站，路徑起點(diǎn)和終點(diǎn)都為蘇州站）。首先用DFS的傳統(tǒng)搜索算法得到最優(yōu)結(jié)果（耗時(shí)38秒）為：規(guī)劃路徑是0-3-7-6-12-11-4-1-8-5-2-10-9，路徑長(zhǎng)度是242.8km。單獨(dú)運(yùn)行5次蟻群算法得到結(jié)果如表1：

表1 經(jīng)過(guò)13 個(gè)點(diǎn)的運(yùn)行結(jié)果（單獨(dú)運(yùn)行5 次蟻群算法）

算得平均路徑長(zhǎng)度為L(zhǎng)a=（248.9+247.5+247.5+250.9+247.5）/5=248.46。而人為選擇（貪心算法）中選擇的路徑為：規(guī)劃路徑是0-9-10-2-6-7-3-12-5-4-1-8-11，路徑長(zhǎng)度為270.2km。

定義優(yōu)化程度：優(yōu)化程度=100%*（貪心路徑長(zhǎng)度-規(guī)劃路徑長(zhǎng)度）/（貪心路徑長(zhǎng)度）。由以上數(shù)據(jù)可知，此時(shí)傳統(tǒng)搜索算法優(yōu)化程度為10.14%，蟻群算法平均優(yōu)化程度為8.05%，蟻群算法最佳優(yōu)化程度為8.40%。由8.4/10.14=82.84%知，蟻群算法5次運(yùn)行可達(dá)到完美優(yōu)化的82.84%，算法性能在可接受范圍內(nèi)。又如前文所提，蟻群算法無(wú)須太多迭代次數(shù)，運(yùn)行較快，故可在對(duì)運(yùn)行速度有嚴(yán)格要求時(shí)采用蟻群算法。

（3）模擬退火算法（SA）

模擬退火算法（SA）流程如圖4。

圖4 SA 算法流程

本文采用貪心路徑作為初始化的路徑（因?yàn)樨澬穆窂骄邆湟恍﹥?yōu)良特性）。在評(píng)價(jià)一條新路徑時(shí)，令Δt=length（T’）-length（T），其中T’為產(chǎn)生的新解（路徑），T為舊解。易知，當(dāng)Δt＜0時(shí)，新解較為優(yōu)秀，此時(shí)用新解替換路徑。當(dāng)Δt＞0時(shí)，以概率exp（-Δt/T）用新解替換路徑。其中T為該時(shí)刻的溫度。

通過(guò)概率exp（-Δt/T）（其中Δt＞0）可知，當(dāng)T較大時(shí)，exp（-Δt/T）較大，即此時(shí)更容易發(fā)生交換，算法的全局搜索性更強(qiáng)；當(dāng)T較小時(shí)，exp（-Δt/T）較小，算法的全局搜索性較小，趨于穩(wěn)定，可以認(rèn)為此時(shí)算法在優(yōu)解的附近尋找更優(yōu)秀的解。

降溫時(shí)根據(jù)降溫系數(shù)降溫，本文取T（t+1）=0.99997*T（t）；單獨(dú)運(yùn)行5 次模擬退火算法得到結(jié)果如表2：

表2 經(jīng)過(guò)13 個(gè)點(diǎn)的運(yùn)行結(jié)果（單獨(dú)運(yùn)行5 次模擬退火算法）

算得平均路徑長(zhǎng)度為L(zhǎng)a=（242.8+246.5+242.8+243.2+245.5）/5=244.16。由以上數(shù)據(jù)可知，此時(shí)傳統(tǒng)搜索算法優(yōu)化程度為10.14%，模擬退火算法平均優(yōu)化程度為9.64%，模擬退火算法最佳優(yōu)化程度為10.14%。

由10.14/10.14=100%知，這5次運(yùn)行模擬退火算法最好結(jié)果可達(dá)到完美優(yōu)化的100%，是性能非常好的算法。由于蟻群算法僅為多用戶使用時(shí)服務(wù)器的后臺(tái)算法提供參考，而模擬退火在運(yùn)行時(shí)間遠(yuǎn)低于傳統(tǒng)搜索的時(shí)間的同時(shí)優(yōu)化性能比蟻群算法好，且本文所述功能無(wú)須為多用戶同時(shí)提供算力，故本文后續(xù)內(nèi)容基于模擬退火算法。

綜上，當(dāng)點(diǎn)數(shù)為13時(shí)得到表3。

表3 四類算法性能表（13 個(gè)點(diǎn)）

2.2.2n較大的情況

當(dāng)n擴(kuò)大至25時(shí)，此時(shí)已無(wú)法使用傳統(tǒng)搜索算法。模擬退火算法5次運(yùn)行結(jié)果如下：

表5 經(jīng)過(guò)25 個(gè)點(diǎn)的運(yùn)行結(jié)果（單獨(dú)運(yùn)行5 次模擬退火算法）

而貪心路徑及長(zhǎng)度為：規(guī)劃路徑是0-9-10-2-24-23-12-6-13-7-3-21-5-16-14-20-22-19-4-1-17-15-8-11-18，路徑長(zhǎng)度是424.1km。算得平均路徑長(zhǎng)度為L(zhǎng)a=（309.6+311.1+315.7+314.5+306.5）/5=311.48。

由以上數(shù)據(jù)可知，此時(shí)模擬退火算法平均優(yōu)化程度為26.56%，模擬退火算法最佳優(yōu)化程度為27.73%，算法性能相當(dāng)出色。綜上，當(dāng)點(diǎn)數(shù)為25時(shí)得到表6。

表6 四類算法性能表（25 個(gè)點(diǎn)）

許多情況下，用戶傾向于控制路途上的時(shí)間成本，使得總里程不變的情況下盡可能經(jīng)過(guò)更多的目標(biāo)地點(diǎn)。例如，一位用戶的汽車所剩汽油只夠該用戶繼續(xù)行駛100km，該用戶有多個(gè)目標(biāo)地點(diǎn)且希望最終能回到出發(fā)點(diǎn)；同時(shí)用戶希望在這種情況下，所經(jīng)過(guò)的點(diǎn)越多越好。本文研究的第二個(gè)功能便是為了解決此類問(wèn)題而設(shè)計(jì)。

3 總結(jié)

本文主要論述了基于北斗導(dǎo)航系統(tǒng)的路徑規(guī)劃優(yōu)化算法實(shí)現(xiàn)，針對(duì)用戶出行常見(jiàn)的兩類規(guī)劃問(wèn)題，以蘇州市25個(gè)地點(diǎn)為實(shí)驗(yàn)數(shù)據(jù)，研究了多種路徑規(guī)劃智能算法的性能，并對(duì)其進(jìn)行了優(yōu)化。本文通過(guò)研究提出了針對(duì)兩類情況的路徑規(guī)劃方案，且方案可視化后被證明是高效可行的，具有現(xiàn)實(shí)應(yīng)用意義。