基于變鄰域搜索的導航線路快速規劃算法

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

關鍵詞：導航;路線規劃;變鄰域搜索;實時性

中圖分類號：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

前言

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

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

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

1 背景模型

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

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

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

2 算法

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

步驟一：根據起點和終點和中間關鍵結點得到部分可行路線。

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

步驟三：執行變鄰域搜索算法得到新的優化解。

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

步驟五;輸出結果。

算法的停止條件一般為循環次數或者一定時間范圍，根據導航的實時性要求，可設為一定時間內或較少的循環次數。

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

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

3 實驗和分析

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

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

4 結束語

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

參考文獻：

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

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

[3]王仁民，閉應洲，劉阿寧，等.改進變鄰域搜索算法求解動態車輛路徑問題[J].計算機工程與應用，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]王仁民.改進變鄰域搜索算法在動態車輛路徑問題中的研究[D].廣西師范學院，2013.