基于粒子群算法的拉萨市最短旅游路线规划

胡冉 西藏大学 工学院

1.引言

拉萨市的旅游业发展虽一直稳中求进，但由于拉萨市地理位置的特殊，导致了拉萨市产业结构单一的现象，目前旅游业所带来的经济收入难以满足城市经济的发展要求。受到地形地质等自然条件的影响，现阶段想通过改变交通运输方式来提高拉萨市的整体旅游效率和收入仍存在着较大的技术空缺，因此缩短旅游路线，为旅客提供高效旅游服务是解决当务之急的有效方法。

粒子群算法是近年来较为科学有效的全局寻优算法，它模拟鸟群飞行觅食的行为，通过鸟之间的集体协作使群体达到最优。尽管每个个体的行为准则是很简单的，但组合成整个群体的行为将会是非常复杂的。此算法是在解空间中利用种群迭代的方法对最优粒子进行搜索。它具有模型简单且易实现的优点，目前在科学研究以及工程应用都发挥了一定的作用。

2.模型简介

2.1 旅行商问题

旅行商问题，即TSP问题是数学领域中著名问题之一。即要求商人在每个城市只能拜访一次的前提下走完所有选定的城市并返回出发点通过旅行商问题的启发，本文利用基于交叉变异的混合粒子群算法，寻找出各旅游景点的之间的最短路径。

2.2 粒子群优化算法

其中：K是迭代次数，r1和r2为之间的随机数，用来保持群体的多样性。c1和c2为学习因子，也称为加速因子，其使粒子具有自我总结和向群体中最优秀个体学习的能力，从而向自己的历史最优点以及群体内历史最优点靠近。

2.3 模型求解

PSO算法是依靠群体之间的相互合作和竞争在问题空间中搜索最优值，本文为了弥补粒子自身缺乏选择、交叉和变异的特性，在基本粒子群算法中引入了交叉和变异的机制，既加快了算法的收敛速度，又保证了粒子群的寻优精度。

本文通过对拉萨市四个著名景点做出了景点之间的分布图1。

图1 景点分布图

为了更直观的展现各景点之间的距离，本文将路径均以直线代替且取整。其中①代表罗布林卡；②代表布达拉宫；③代表小昭寺；④代表大昭寺。

2.4.1 仿真参数设置

种群数量N=1000，迭代次数k=50。表1为各景点的具体坐标。

表1 景点坐标图

2.4.2 仿真结果与分析

在MATLAB2018b版本中的运行结果如下图2所示。通过交叉变异的混合粒子群算法，可较为精确的确定各个景点之间路径最短的旅行方式，以①号罗布林卡为起点，可先选择②号布达拉宫游玩，再经过③号小昭寺，最后选择大昭寺回到起点布达拉宫。由于旅行路线为无向图，因此还可以选择反方向的旅游路线。

图2 最短旅行路线

3.结论

本文利用基于交叉变异的混合粒子群算法本文粗略地介绍了基于交叉变异的混合粒子群算法在PSO问题上的简单应用，并能有效解决拉萨市旅游规划上带来效率低下等问题。但由于本文景点个数较少，因此难以体现此算法在收敛速度上的优势。但此算法在生活和工业应用中具有极大的探究潜能，可延申至有向图等非对称问题上的研究。将本算法应用至西藏自治区中将有更大的实践价值和意义，西藏自治区地域广袤、旅游景点众多，距离因素是影响当地旅游业发展的主要因素，可利用此算法有效地将旅游资源整合，更好地推动西藏自治区旅游业的发展。