基于变邻域搜索的导航线路快速规划算法

摘  要：针对当前主流导航软件路线规划常不能为用户规划合理代价路线的问题，提出一个基于变邻域搜索的路线规划快速算法。该算法利用变邻域搜索快速的局部和全局搜索能力，在满足导航实时性要求下对原不合理路线重新规划，得到更为合理的优化路线。模拟程序验证了算法的有效性。

关键词：导航;路线规划;变邻域搜索;实时性

中图分类号：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.