基于變鄰域搜索的導(dǎo)航線路快速規(guī)劃算法

摘? 要：針對當(dāng)前主流導(dǎo)航軟件路線規(guī)劃常不能為用戶規(guī)劃合理代價路線的問題，提出一個基于變鄰域搜索的路線規(guī)劃快速算法。該算法利用變鄰域搜索快速的局部和全局搜索能力，在滿足導(dǎo)航實時性要求下對原不合理路線重新規(guī)劃，得到更為合理的優(yōu)化路線。模擬程序驗證了算法的有效性。

關(guān)鍵詞：導(dǎo)航;路線規(guī)劃;變鄰域搜索;實時性

中圖分類號：TP301.6? ? ? ?文獻標志碼：A? ? ? ? ?文章編號：2095-2945（2019）08-0108-02

Abstract： In order to solve the problem that route planning of mainstream navigation software cannot plan reasonable cost route for users， a fast route planning algorithm based on variable neighborhood search is proposed. The algorithm makes use of the fast local and global search ability of variable neighborhood search to replan the original unreasonable route to meet the real-time requirements of navigation and obtain a more reasonable optimal route. The simulation program verifies the effectiveness of the algorithm.

Keywords： navigation; route planning; variable neighborhood search; real-time

前言

百度地圖和高德地圖是當(dāng)前國內(nèi)主要導(dǎo)航工具，它們作為一款導(dǎo)航服務(wù)提供軟件，路線規(guī)劃服務(wù)（Direction API）是其核心。然而，通過兩者官網(wǎng)均不能查詢到其路線規(guī)劃的策略。而據(jù)華為應(yīng)用市場的最新數(shù)據(jù)（2019.2.21），百度地圖和高德地圖分別被下載21和24億次，而對應(yīng)的評分僅為2.9和3.2（滿分為5）。由此也反映了這兩款主流導(dǎo)航產(chǎn)品不盡人意的表現(xiàn)。一般而言，路線代價最小化是用戶最大的追求。因此，不合理的路線規(guī)劃也是這些導(dǎo)航軟件的主要癥結(jié)所在。

路線規(guī)劃實質(zhì)可以抽象為一個旅行商問題（TSP， Traveling Salesman Problem），而該問題屬于NP完全性問題。近年來，TSP、VRP（Vehicle Route Problem）及其衍生模型被廣泛研究，如蟻群算法、遺傳算法和模擬退火算法等現(xiàn)代啟發(fā)式算法是該研究的主流方向。而這些元啟發(fā)式算法存在易陷入局部最優(yōu)的問題，許多學(xué)者又采用融合不同算法的方式以促進元啟發(fā)式算法的全局搜索能力[1-3]。盡管這些研究取得了不錯的最終結(jié)果，但基本以犧牲時間復(fù)雜度為代價，因而難以滿足導(dǎo)航的實時性要求。此外，這些算法常被應(yīng)用于各類車輛路線規(guī)劃，如公交、貨運等，但在導(dǎo)航領(lǐng)域卻幾乎未有涉及。

變鄰域搜索算法是一種元啟發(fā)式算法，其基本思想是系統(tǒng)地變化包含不同局部搜索算法的鄰域結(jié)構(gòu)，使得算法在局部和全局空間交替作用以此尋求全局最優(yōu)解[4-5]。該算法的特點是局部搜索能力強、運行速度快，且不易陷入局部最優(yōu)。將該算法應(yīng)用于路線導(dǎo)航，既可規(guī)劃出盡可能合理的路線，又能滿足導(dǎo)航的實時性要求。文章主要內(nèi)容安排如下：（1）介紹導(dǎo)航背景模型;（2）描述算法過程;（3）進行模擬實驗和分析;（4）最后總結(jié)全文。

1 背景模型

導(dǎo)航路線與TSP模型既有相似也有不同。為了更好地體現(xiàn)導(dǎo)航的本質(zhì)，一些繁瑣的限制條件可以摒棄。因此，文章所提模型是現(xiàn)實導(dǎo)航的簡化模型。TSP模型是指一個銷售員拜訪區(qū)域內(nèi)的所有客戶并回到原位置，要求為其提供一條最短路線。導(dǎo)航路線的起點和最終通常是不同的，且不需要經(jīng)過期間的所有路口，因此路線導(dǎo)航并不能直接等同于TSP模型。但它們又是相似的，如將交叉路口等位置設(shè)為“關(guān)鍵結(jié)點”，那么從起點經(jīng)過部分關(guān)鍵結(jié)點然后到終點的路徑也可抽象為一個開放式TSP模型。

如何處理導(dǎo)航路線與TSP模型之間的差異是建立導(dǎo)航模型的關(guān)鍵。如果將導(dǎo)航路線的起點和終點的所有可行路線都看作是一個獨立的開放式TSP模型，則導(dǎo)航路線模型是由一個或多個開放式TSP模型組成的模型。

下面建立導(dǎo)航路線規(guī)劃的背景的數(shù)學(xué)模型，如圖1所示。設(shè)起點為s，終點為e，中間m個關(guān)鍵結(jié)點為n1，n2，…，nm。導(dǎo)航的目標是規(guī)劃一條從s到e但無需經(jīng)過所有ni的代價最小路徑。需注意的是，并不是所有兩兩結(jié)點之間都是直接可達的，而且路徑短也不意味著他們的運行代價小。假設(shè)R是s和e之間的可行路線集，那么目標函數(shù)可表達如下需要注意的是，無需計算出所有可行路線，這也是文章所用算法的優(yōu)勢之一。

2 算法

該部分將應(yīng)用變鄰域搜索算法根據(jù)部分已知可行路線，快速規(guī)劃出一定時間范圍內(nèi)的最小代價路線。邊鄰域搜索算法的特點之一就是可以利用當(dāng)前已知部分解，盡可能搜索出更多可行解，并啟發(fā)得到更多優(yōu)化解。算法具體描述如下：

步驟一：根據(jù)起點和終點和中間關(guān)鍵結(jié)點得到部分可行路線。

步驟二：將部分可行路線作為變鄰域搜索算法的初始解。

步驟三：執(zhí)行變鄰域搜索算法得到新的優(yōu)化解。

步驟四：如果達到停止條件，轉(zhuǎn)步驟五，否則將步驟三的結(jié)果加入部分可行解中并轉(zhuǎn)到步驟二。

步驟五;輸出結(jié)果。

算法的停止條件一般為循環(huán)次數(shù)或者一定時間范圍，根據(jù)導(dǎo)航的實時性要求，可設(shè)為一定時間內(nèi)或較少的循環(huán)次數(shù)。

變鄰域搜索算法的主要過程如算法1所示（表1）。其中包含了全局的鄰域調(diào)整，以及調(diào)整后的局部搜索。

算法1中的第2步是指變鄰域調(diào)整策略，主要是改變不同的初始解;第3步的局部搜索主要包含三種局部搜索算法：路徑間局部交叉，路徑間局部交換和路徑間局部插入，詳見文獻[6]。對應(yīng)于導(dǎo)航模型，輸入的初始解為多種可行解，這些解往往代價較大不能滿足用戶要求。

3 實驗和分析

為驗證算法的有效性，采用MATLAB實現(xiàn)的模擬程序在5個人工數(shù)據(jù)集上運行。目前，百度地圖路線導(dǎo)航支持的最大途徑點個數(shù)為20。因此，五個人工數(shù)據(jù)集的中間結(jié)點數(shù)從12到20之間。設(shè)算法循環(huán)次數(shù)為100，表2顯示了運行結(jié)果。

從表2中可知，較大的初始值執(zhí)行位置提出的優(yōu)化算法后，其路線代價顯著降低，且運行時間都是1秒之內(nèi)，在用戶可接受的范圍之內(nèi)。

4 結(jié)束語

文章提出了基于變鄰域搜索的導(dǎo)航路線快速規(guī)劃算法，算法對原始初始路線進行快速的局部和全局搜索，并迅速得到更合理的優(yōu)化路線。該算法不僅改進了路徑規(guī)劃，同時滿足導(dǎo)航的實時性要求。最后實驗也驗證了算法的有效性。文章雖然提出了新的路線導(dǎo)航策略并取得了較好效果，但缺乏實際數(shù)據(jù)支撐，未來將進一步完善模型和算法，使其能應(yīng)用于現(xiàn)實。

參考文獻：

[1]徐坤，陳志軍，閆學(xué)勤.基于萊維飛行的改進蟻群算法求解TSP問題[J].計算機工程與設(shè)計，2019，40（01）：245-249.

[2]梅俊.基于混合遺傳算法的TSP優(yōu)化問題求解[D].安慶師范大學(xué)，2018.

[3]王仁民，閉應(yīng)洲，劉阿寧，等.改進變鄰域搜索算法求解動態(tài)車輛路徑問題[J].計算機工程與應(yīng)用，2014，50（02）：237-241.

[4]Hansen P， Mladenovi ， Nenad. Variable Neighbourhood Search[M]//Metaheuristic Procedures for Training Neutral Networks. Springer US， 2006.

[5]Hansen P， Nenad Mladenovi ， José A. MorenoPérez. Variable neighbourhood search： methods andapplications[J]. Annals of Operations Research， 2010，175（1）：367-407.

[6]王仁民.改進變鄰域搜索算法在動態(tài)車輛路徑問題中的研究[D].廣西師范學(xué)院，2013.