基于北斗导航的路径规划优化算法研究

◆汪慧琳

（郑州大学地球科学与技术学院 河南 450001）

如今，支持北斗三号系统信号的 28 纳米芯片已得到广泛应用，国内外主流芯片厂商均推出兼容北斗的通导一体化芯片，支持北斗定位的手机越来越多。通过获取手机本身芯片提供的位置，地图软件就可以使用BDS进行实时定位、路径规划等功能。通常的地图软件都具备让用户选择起点-终点，从而进行两点之间最佳路径规划的基础功能。现在国内的地图软件（高德地图、百度地图、腾讯地图等）也具备设置多个途经点（主要是驾车模式）的路径规划，在手机端一般可以设置5个途经点（包括起点和终点），在PC端可设置途经点数较多的是高德地图（包括起、终点共8个）。但目前仍未有一款地图软件，能根据用户的预期途经点（地点数大于8）及用户的时间期望（愿意用于出行的时间）给用户提供智能出行规划。一种常见的情况是：用户在面临需要规划路线的情况时，容易陷入纯粹的局部最优规划（贪心算法）——总是去往离当前位置最近的位置，这往往会比真正的最优规划多出许多里程。另一种常见的情况是：由于用户时间有限，不能经过所有期望地点。

本文旨在通过优化智能算法得出两种路径规划方式，一是让用户在经过所有预期途经点的条件下尽可能地减少交通里程，二是让用户在时间有限的条件下尽可能地减少交通时间。当基于北斗导航系统的路径规划能够为用户提出更优化的方案时，将会提升用户体验。

1 研究思路

首先将用户所希望前往的地点数字化。利用北斗导航获得每两个地点之间的最佳驾车路径距离，生成距离矩阵。用户的想法分为两类：一类是用户期望能够抵达所有目标地点，一类是用户期望尽可能减少路途上的时间成本。

图1 用户选择模式

2 研究内容

2.1 数据采集、处理

本文选取苏州市25个地点为测试用例，数字及地点对应关系如下：

0-苏州站，1-周庄古镇，2-拙政园，3-虎丘山，4-同里古镇，5-金鸡湖，6-留园，7-寒山寺，8-千灯古镇，9-苏州博物馆，10-狮子林，11-西山，12-盘门，13-七里山塘，14-天平山，15-甪直古镇，16-木渎古镇，17-锦溪古镇，18-东山，19-望山，20-穹窿山，21-苏州大学，22-吴中太湖风景区，23-沧浪亭，24-网师园。

25个地点的驾车距离以矩阵形式输入计算机。

2.2 算法优化及实验结果分析

2.2.1n较小的情况

对于n小于13的情况，本文采用深度优先算法（DFS）实现对所有路径的遍历。第一类规划问题中，对于n较大的情况，本文先后实验了蚁群算法（ACO）、模拟退火算法（SA）。

（1）深度优先算法（DFS）

深度优先算法（DFS）流程如图2。

图2 DFS 算法流程

通过对该算法的优化，如建立哈希表以快速判重、减支，可以对n小于13的情况做出快速准确的处理。

（2）蚁群算法（ACO）

图3 ACO 算法流程

蚁群算法中，每个地点对于其他的任意一个地点都有一个启发值，即启发因子，初始化值为该点与另一点距离的倒数。这表示：两个地点之间的距离越近，启发因子越大，因而蚂蚁选择此点的概率越大。

同样，每个地点对于其他的任意一个地点都有一个信息素浓度，且随着迭代（蚂蚁群周而复始的运动）的进行不断挥发、更新。其初始化值为蚂蚁数量与贪心路径（见前文中的人为选择）长度的比值。

在t时刻，蚂蚁在地点i对下一个地点j的选择遵循以下公式：

其中表示地点i到地点j的路径上的信息素浓度，表示地点i到地点j的路径上的启发值。α表示信息素参数，β表示启发因子参数（在使用函数时可自己设定这两个参数的值，一般取1和2）。

信息素浓度更新公式：

式（2）表示信息素的挥发；

式（3）表示信息素浓度为挥发后的浓度加上蚂蚁新留下的信息素浓度，每只蚂蚁在两地点间留下的新浓度为该路径距离和的倒数。其中，m为曾从地点i抵达了地点j的蚂蚁的数量，k为对应的路径标记。

最后再设置迭代次数，算法即可开始运行。

蚁群算法的一个特性是：搜索结果收敛快，且当收敛完成时，很难再找到一条其他的路径。当所有蚂蚁都在同一条路径上行走时，即使有蚂蚁“突发奇想”向更优秀的路径迈出了一步，也只能留下浓度不高的信息素，而由于其他蚂蚁汇集于同一条路径，导致那条路径上的信息素浓度会很高。因此，蚁群的下一次出动中，很少有蚂蚁能够响应那位“突发奇想”的蚂蚁先驱的号召，它们仍更倾向于往信息素浓度特别高的路径上行走，故而当结果收敛于局部最优解以后，很难再迭代出一条更好的路径。

实验表明：迭代次数达到了50以后，再增加迭代次数也难以得到更好的结果。这样的一个优点是：减少了计算机的算力。当导航软件的服务器需要为所有用户提供云计算功能时，蚁群算法的易收敛性是它的一个重要优点：对于每个用户的路径规划，仅需要少量的计算机算力。

在实际测试中，选取了苏州的13个地点（其中包含苏州站，路径起点和终点都为苏州站）。首先用DFS的传统搜索算法得到最优结果（耗时38秒）为：规划路径是0-3-7-6-12-11-4-1-8-5-2-10-9，路径长度是242.8km。单独运行5次蚁群算法得到结果如表1：

表1 经过13 个点的运行结果（单独运行5 次蚁群算法）

算得平均路径长度为La=（248.9+247.5+247.5+250.9+247.5）/5=248.46。而人为选择（贪心算法）中选择的路径为：规划路径是0-9-10-2-6-7-3-12-5-4-1-8-11，路径长度为270.2km。

定义优化程度：优化程度=100%*（贪心路径长度-规划路径长度）/（贪心路径长度）。由以上数据可知，此时传统搜索算法优化程度为10.14%，蚁群算法平均优化程度为8.05%，蚁群算法最佳优化程度为8.40%。由8.4/10.14=82.84%知，蚁群算法5次运行可达到完美优化的82.84%，算法性能在可接受范围内。又如前文所提，蚁群算法无须太多迭代次数，运行较快，故可在对运行速度有严格要求时采用蚁群算法。

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

模拟退火算法（SA）流程如图4。

图4 SA 算法流程

本文采用贪心路径作为初始化的路径（因为贪心路径具备一些优良特性）。在评价一条新路径时，令Δt=length（T’）-length（T），其中T’为产生的新解（路径），T为旧解。易知，当Δt＜0时，新解较为优秀，此时用新解替换路径。当Δt＞0时，以概率exp（-Δt/T）用新解替换路径。其中T为该时刻的温度。

通过概率exp（-Δt/T）（其中Δt＞0）可知，当T较大时，exp（-Δt/T）较大，即此时更容易发生交换，算法的全局搜索性更强；当T较小时，exp（-Δt/T）较小，算法的全局搜索性较小，趋于稳定，可以认为此时算法在优解的附近寻找更优秀的解。

降温时根据降温系数降温，本文取T（t+1）=0.99997*T（t）；单独运行5 次模拟退火算法得到结果如表2：

表2 经过13 个点的运行结果（单独运行5 次模拟退火算法）

算得平均路径长度为La=（242.8+246.5+242.8+243.2+245.5）/5=244.16。由以上数据可知，此时传统搜索算法优化程度为10.14%，模拟退火算法平均优化程度为9.64%，模拟退火算法最佳优化程度为10.14%。

由10.14/10.14=100%知，这5次运行模拟退火算法最好结果可达到完美优化的100%，是性能非常好的算法。由于蚁群算法仅为多用户使用时服务器的后台算法提供参考，而模拟退火在运行时间远低于传统搜索的时间的同时优化性能比蚁群算法好，且本文所述功能无须为多用户同时提供算力，故本文后续内容基于模拟退火算法。

综上，当点数为13时得到表3。

表3 四类算法性能表（13 个点）

2.2.2n较大的情况

当n扩大至25时，此时已无法使用传统搜索算法。模拟退火算法5次运行结果如下：

表5 经过25 个点的运行结果（单独运行5 次模拟退火算法）

而贪心路径及长度为：规划路径是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，路径长度是424.1km。算得平均路径长度为La=（309.6+311.1+315.7+314.5+306.5）/5=311.48。

由以上数据可知，此时模拟退火算法平均优化程度为26.56%，模拟退火算法最佳优化程度为27.73%，算法性能相当出色。综上，当点数为25时得到表6。

表6 四类算法性能表（25 个点）

许多情况下，用户倾向于控制路途上的时间成本，使得总里程不变的情况下尽可能经过更多的目标地点。例如，一位用户的汽车所剩汽油只够该用户继续行驶100km，该用户有多个目标地点且希望最终能回到出发点；同时用户希望在这种情况下，所经过的点越多越好。本文研究的第二个功能便是为了解决此类问题而设计。

3 总结

本文主要论述了基于北斗导航系统的路径规划优化算法实现，针对用户出行常见的两类规划问题，以苏州市25个地点为实验数据，研究了多种路径规划智能算法的性能，并对其进行了优化。本文通过研究提出了针对两类情况的路径规划方案，且方案可视化后被证明是高效可行的，具有现实应用意义。