基于粒子群算法的江西景点自驾游路线规划

宋艳艳，李广宏，朱 玲，夏传林，郑 巍

（1. 桂林理工大学旅游与风景园林学院，桂林 541000；2. 南昌航空大学数学与信息科学学院，南昌 330063；3. 南昌航空大学软件学院，南昌 330063）

0 引言

随着科技的发展，通过携程、美团、飞猪等APP 可以在网上查询各地的旅游景点，十分方便人们的出行，在一定程度上也促进了旅游业的发展。随着汽车的普及，自驾游也越来越受到年轻人的喜爱，人们会根据出行的时间合理地规划旅游行程，选择合适的景点个数，但是实际出行中，还会伴随其他问题的产生，例如旅游路径的规划［1-2］、旅游费用等，这个时候需要合理的方法解决这个问题。许多学者对这个问题进行研究，最早源于TSP 旅行商问题［3］，随后对该问题的算法进行深入研究，解决这类问题常用的方法有蚁群［4-7］、粒子群［8-11］、遗传算法［12-15］等。本文结合粒子群算法，对江西13 个5A 旅游景点进行路径规划，粒子群算法可以为我们提供最佳的旅游顺序［16］。

1 算法介绍

粒子群优化算法（particle swarm optimization，PSO）又称粒子群算法［17］，是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法［18-20］，主要应用在连续优化的问题中，对于离散问题，PSO应用在TSP旅行商问题是一个新的研究方向。

一群鸟在寻找食物，在这个区域中只有一只虫子，所有的鸟都不知道食物在哪。但是它们知道自己的当前位置距离食物有多远，同时它们知道离食物最近的鸟的位置［21-24］。如图1 所示，表示的是鸟群在觅食过程中的几种状态。小黑点表示一只鸟，箭头指示的方向表示鸟群飞行的方向。图1（a）表示鸟群的初始觅食状态，鸟群都是分散开来的，朝着区域内最可能找到食物的方向运动；图（b）表示鸟群中间觅食的状态，可以看到鸟群已经呈现出聚集状态，分布在食物周围，找到局部最优解；图（c）表示鸟群的最终觅食状态，鸟群分布在食物的周围，此时找到了最优解［25］。

图1 鸟群觅食状态

图2 描述了粒子群优化算法的运算流程，如下［26］：

图2 粒子群优化算法的运算流程［27］

步骤1：初始化粒子群，包括群体规模N，每个粒子的位置xi和速度vi。

步骤2：计算每个粒子的适应度值fit(i)。

步骤3：对每个粒子，用它的适应度值fit(i)和个体极值pbest(i)比较。如果fit(i)＜pbest(i)，则用fit(i)替换掉pbest(i)。第i个粒子迄今为止搜索到的最优位置称为个体极值，记为

（4）对每个粒子，用它的适应度值fit(i)和全局极值gbest比较。如果fit(i)＜gbest(i)，则用fit(i)替换掉gbest。整个粒子群迄今为止搜索到的最优位置为全局极值，记为

（5）迭代更新粒子的速度vi和位置xi。根据公式（1）和（2）得到两个最优值pbest和gbest，可根据公式（3）和（4）来更新粒子的速度和位置。

其中：c1和c2称为学习因子，分别调节pbest和gbest方向飞行的最大步长；r1和r2为［0，1］范围内的均匀随机数。

（6）进行边界条件处理。

（7）判断算法终止条件是否满足：若是，则结束算法并输出优化结果；否则返回步骤（2）。

2 实例验证

2.1 实例介绍

江西省是一个具有浓厚历史韵味和人文特色的著名旅游城市，本文选取江西省13个5A景区作为分析对象，其中包含自然景观、历史遗址、现代建筑等相对具有代表性的旅游景点。其中包含滕王阁、庐山、庐山西海、龙虎山、三清山、龟峰、井冈山、江湾、明月山、共和国摇篮、武功山、大觉山、古窑民俗博览区13个景点。这些景点有的在南昌市内，有的在九江市，分布在江西省的各个地区。如果想去多个景点旅游，要是没有做好路线规划，会造成去过相同的路线，非常浪费时间。因此，本文重点对13 个景区进行一个顺序排序，对景点进行路径规划，使得总路线最短。各个景点的位置坐标如表1所示，景点坐标是通过百度的拾取坐标系统获得的经纬度坐标，在后续实验计算中，需要将经纬度坐标转换为距离坐标。

表1 江西省13个5A景区坐标

2.2 实验结果分析

本文中景点坐标是经纬度坐标，而地球是一个三维的球体，不能够直接通过经纬度计算距离，所以需要将景点的经纬度坐标转换为距离进行计算。

把表1中景点坐标数据输入Matlab中，通过粒子群优化算法对江西13个5A景区进行路径规划。根据若干次Matlab 仿真实验结果对蚁群算法的其他参数进行设定：城市数量为13，种群大小为50，学习因子c1为2，学习因子c2为2，pbest-xi的保留概率r1为0.7，gbest-xi的保留概率r2为0.8，算法最大迭代次数为1000。利用同样的参数和程序对江西省旅游景点进行多次Matlab 仿真计算，最优结果如图3所示。

图3 粒子群优化算法最优路径

根据仿真实验结果，得到最短路径顺序为：11→10→12→4→8→5→6→13→2→3→1→9→7→11。

表2 除了统计了景点间的直线距离(根据经纬度计算)，还展示了景点间的真实距离（通过高德导航，选择驾驶模式）。从表2 可以看出导航的真实距离和通过经纬度计算得到的直线距离有较大差别，而导航的真实距离才是日常生活中使用的，所以本文把导航的真实距离作为实验结果。

表2 最优路径各区间距离

由表2 中的导航真实距离得到最短距离为2582 km，相邻景点间的距离依次为429 km、288 km、108 km、276 km、102 km、147 km、173 km、159 km、104 km、97 km、249 km、248 km和202 km。

3 结语

TSP 旅行商问题是一个生活中很常见的问题，本文通过粒子群优化算法模拟对江西省13个5A 景区进行路径规划，通过对参数的多次调整，最终找到一条最短的旅游路径，为乘客节省旅途时间的成本，完成了本文需要实现的目标。本文得到的最短距离是根据导航的真实距离，更加贴近真实的生活，但是没有考虑到旅途中路线等真实费用问题，在日后的研究中应当把这些实际因素考虑进来，这样才能更好地解决生活中的实际问题，让科学研究走进生活。