成都市内旅游路线规划研究——基于SA、GA算法

0 引言

随着我国经济的不断增长，旅游行业从无到有、从弱到强，在增进中国同其他国家之间的友谊和交往中发挥了积极作用和协同功能，旅游业已成为发出中国声音、讲好中国故事、加强与世界联系的重要平台。在满足基本温饱的基础之上，人民对精神文明的追求日益增长，旅游已经成为一种新兴的生活方式，是人们工作之余休闲娱乐的重要选择之一。在出行时，由于景点较多时间较短，规划出一条距离最短的最优路线，无论是对消费者还是景区都是一件不可多得的好事，同时也是提高消费者旅途幸福感的重要体现。一条合理的旅游路线可以花费最少的时间成本，将各个旅游景点串联起来形成哈密顿圈，从而获得最大的观赏体验。

2021年，成都市实现旅游总收入3085亿元，接待游客2.05亿人次，入选“2021中国旅游业最发达城市TOP6”。本文的研究以成都市内的12个热门旅游景点为例，基于SA、GA算法，利用python编程找出最优路径，为旅游者提供路线规划。

1 算法的基本思想及计算流程

本节以TSP问题为研究对象，分别介绍模拟退火算法和遗传算法在解决TSP问题时的算法思想及算法流程。

1.1 模拟退火算法

1.1.1 算法思想

由初始解和控制参数初值开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减控制参数值，算法终止时，当前解的值即为近似最优解，这便是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

①设组合优化问题的一个解i及其目标函数（fi）分别与固体的一个微观状态i及其能量Ei等价。

②令随算法进程递减其值的温度控制参数t担当固体退火过程中的温度T的角色；则对于控制参数t的每一取值，算法持续进行“产生新解一判断一接受／舍弃”的达代过程，就对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次Metropolis算法。

③重复执行Metropolis算法，就可以在控制参数，趋于零时，最终求得组合优化问题的整体最优解。

1.1.2 计算流程

使用模拟退火算法解决TSP问题的流程图如图1所示。

图1 模拟退火算法实现TSP流程

1.2 遗传算法

1.2.1 算法思想

①遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个体进行筛选，从而使适值高的个体被保留下来，组成新的群体。

②新群体包含上一代的大量信息，并且引入了新的优于上一代的个体。这样不断迭代循环，群体中各个体适值不断提高，直至满足一定的极限条件。

③此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索。

④遗传算法对于搜索空间不需要连续、可微、单峰等限制性的假设。

1.2.2 计算流程

①初始参数设置。在搜索空间U上定义一个适应度函数（fx），给定种群规模N，交叉率Pc和变异率Pm，迭代次数T。②初始种群产生。随机产生U中的N个个体S1，S2，…，SN，组成初始种群S={S1，S2，…，SN}，置迭代次数计数器t=1。③计算适应度。计算S中每个个体的适应度f（）。④迭代判断。若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。⑤选择-复制。按选择概率P（xi）所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1。⑥交叉。按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，两两随机配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2。⑦变异。按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3。⑧将群体S3作为新一代种群，即用S3代替S，t=t+1，转步③。

2 算法的实现

2022年1月20日，国务院印发《“十四五”旅游业发展规划》，成都成为首增“旅游城市布局”专栏中34个旅游枢纽城市之一。成都市4A级及以上景区51家、国家级旅游度假区1家、省级旅游度假区14家，A级景区2021年全年接待游客1.5亿人次，同比增长42.33%，门票收入15.87亿元，同比增长93.81%。

本研究选取了金沙遗址、杜甫草堂、青羊宫、武侯祠、锦里、宽窄巷子、人民公园、文殊院、春熙路、九眼桥、环球中心、成都市熊猫繁育基地等12个景点，并依次用V→V分别表示，其经纬度如表1所示。假如一位热爱自驾游的旅行者按上述景点进行旅游路线规划，在模拟退火算法和遗传算法中，采用各个景点的经纬度，用Python编程实现，最终得到景点间最优路线的闭合哈密顿圈。

2.1 SA算法的Python实现

以表1中的坐标数据为输入，根据SA算法输出结果图2可知，经过模拟退火算法进行数次迭代，得到最终的哈密顿圈，若以V为起点，得到遍历12个景点的最优路径为：V→V→V→V→V→V→V→V→V→V→V→V→V

图2 SA算法下成都市旅游最优路径

表1 成都市景区经纬度 单位：度

即游览路线为武侯祠、青羊宫、金沙遗址、宽窄巷子、文殊院、成都市熊猫培育基地、春熙路、杜甫草堂、人民公园、环球中心、九眼桥、锦里、最后回到武侯祠时，游览路径最短。

2.2 GA算法的Python实现

同样的，以表1中的坐标为数据输入，根据GA算法输出结果图3可知，经过遗传算法进行数次复制、交叉、变异，得到最终的哈密顿圈，若以V为起点，得到遍历12个景点的最优路径为：V→V→V→V→V→V→V→V→V→V→V→V→V

图3 GA算法下成都市旅游最优路径

即游览路线为环球中心、九眼桥、锦里、武侯祠、青羊宫、金沙遗址、宽窄巷子、文殊院、成都市熊猫培育基地、春熙路、杜甫草堂、人民公园、最后回到环球中心时，游览路径最短。

图4 进化过程

3 结论

本研究选取成都市内旅游景点，以自驾游或打车的旅行者为研究对象，采集百度地图上成都市内12个景点的经纬度，基于路程最优化采取SA算法和GA算法构建哈密顿圈，并采用python求解得出最优游览路线。观察两种算法得结果可以发现，模拟退火算法和遗传算法采用Python进行寻优时，得出的最小哈密顿圈路径相同。模型的优点在于：

①采用该模型，可以针对所需达到的点构造出一个哈密顿圈，求出最优路线，节约了大量的时间和资金成本。

②与传统的采用Matlab进行遍历循环不同，该模型基于python编程实现，语言更加简单优美并且免费，对旅游者来说节约成本并有更强的实用性。

除此以外，也存在一些不足之处：

①该模型采用的是景点的经纬度数据，没有考虑到实际行程中早晚行车高峰期带来的影响。

②仅是从规划串联12个景区的最优路径出发，没有考虑在景点内的游玩时间，以及一次性游玩所有景点的可能性。

为完成一次美好的旅游体验，对旅行者提出以下建议：

①旅游之前规划好出行路线，尽可能地减少中转次数，节省时间和精力。

②旅游途中安排好住宿问题，尽量安排在靠近中心区域，方便出行和景点游览。

对于旅游公司提出以下建议：

①充分发掘旅游资源的潜力，打造有特色的旅游景区，充分利用互联网媒体的广泛覆盖优势，挖掘潜在的旅游客户。

②基于数据分析，制定出各个景点之间的最优路线，达到节约资源提升旅行者的幸福感。

③在旅游旺季，增加景点摆渡车辆，减少候车时间，使旅行者更多的在景区里而不是在路上。

该方法不仅可适用于消费者规划出全国各省的最佳旅游路线，而且可以运用到网红店打卡最优问题、货物运输问题和快递行业送货上门问题以及小区、学校、医院等公共基础建设的选址问题等。本文仅选取了成都市内的景点，景点选择较为单一，后续研究可以从市内扩展到周边，例如同时考虑到周边的青城山、都江堰、峨眉山、乐山、九寨沟、黄龙景区、四姑娘山等景点，并用一定的方法赋予各个游览景点价值系数，选取其中一些价值系数更高的景点进行旅游路线规划，使旅行的价值最大化。