基于粒子群算法的城市旅游路线优化研究

张成龙

(茅台学院 酿酒工程自动化系，贵州 遵义 564500)

基于粒子群算法的城市旅游路线优化研究

张成龙

(茅台学院 酿酒工程自动化系，贵州 遵义 564500)

针对城市内旅游景点众多，游客出行路线复杂等问题，提出一种基于经典旅行商问题的城市旅游路线模型，并利用粒子群算法对该模型进行求解优化，最后利用MATLAB进行仿真实验，实验结果表明，粒子群算法能够有效实现城市旅游路线的优化，降低游客城市旅行的出行成本，节约游玩时间。

粒子群算法；路径优化；旅行商问题

“互联网＋旅游”战略的提出，越来越多的景点开始响应这一发展战略，不断完善景区的基础设施建设，为游客提供更为优质的服务，从而吸引了大量国内外游客。但是城市内旅游景点众多，交通路线复杂，为降低游客出行成本，节约出行时间，有必要对出行路线进行规划。

城市旅游路线优化问题可以看作经典的旅行商问题(Traveling Salesman Problem,TSP)，目前用来求解TSP问题的方法主要有遗传算法[1]、模拟退火算法[2]、蚁群算法[3]、粒子群算法[4]等群体智能优化算法。其中粒子群算法具有种群搜索能力强、运算效率高等特点，成为了近年来求解TSP问题的一个常用方法，因此本文采用粒子群算法进行城市旅游路线模型求解优化。

1 城市旅游路线模型描述

因为经典旅行商问题有如下定义：给定一系列城市和两两城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。所以我们可以将经典旅行商问题中的城市看作旅游景点，定义城市旅游路线模型如下：

首先将某城市内各旅游景点之间构成的网络图转换为带权完全无向图。按照图论思想描述为：G=(V,A)，V表示为图中结点的集合，一个结点代表城市内的某个旅游景点，A表示图中弧的集合，已知各结点间的连接距离，找一个权值最小的Hamilton回路。即遍历所有顶点一次且仅一次的最短回路，设 dij为城市内旅游景点 i与 j之间的距离，即弧(i,j)长度，引入决策变量：

则其目标函数为

TSP问题模型虽然简单，但是由于该问题的可行解是所有顶点的全排列组合，且随着顶点数的增加，易产生组合爆炸，导致求解困难，因此本文选择采取粒子群算法进行TSP问题求解。

2 基本粒子群优化

粒子群算法(ParticleSwarm Optimization,PSO)[5-6]，1995 年由 Russell Eberhart博士和 James Kennedy博士提出，多年以来经过数学、物理学、生物学、心理学等诸多领域专家的研究与改进，现今广泛应用于求解各类工业、经济和社会等实际应用中需要优化的多目标问题、约束问题、动态问题，具有参数少，简单易于理解实现等特点。

粒子群算法作为一种随机优化方法，将待优化问题潜在解描述为在D维空间内以一定的速度“飞行”且没有质量和体积的粒子。其数学模型定义为：假设粒子群中粒子数量为N，搜索空间维数为D，那么粒子的空间坐标位置向量表示为xi=(xi1,xi2,…,xiD)，粒子的速度向量表示为vi=(vi1,vi2,…,viD)，单个粒子寻优过程中其个体最优位置表示为Pi=(Pi1,Pi2,…,PiD)，粒子群中最佳位置表示为Pg=(Pg1,Pg2,…,PgD)。粒子的当前位置优劣由适应度函数评价，在粒子群迭代进化过程中，通过粒子的位置和速度更新公式进行空间搜索寻得的最优位置，其中速度和位置更新公式为[7]：

式中，i=1,2,…,N；ω为惯性权重系数；r1和r2是独立随机变量，服从(0,1)均匀分布；h1和h2是学习因子，且为非负常数；vi∈[-vmax,vmax]，vmax是约束速度的常数，由用户根据具体问题设定。粒子群算法基本流程如图1所示。

图1 粒子群算法流程

3 实验仿真

3.1 实验环境

为进行城市旅游路线模型验证求解，选取实验平台为Win10/MATLAB(R2010b)，计算机配置为：Intel(R)Core(TM)i3-3240 CPU@3.40GHz，4.00GB RAM，64位操作系统，设计了基于Matlab的仿真程序。

为模拟某城市内旅游景点的布局情况，设定城市内10个旅游景点坐标如表1所示，粒子群算法运算过程中的城市旅游路线距离值变化如图2所示，由运算结果可知，粒子群算法运行至200代已经收敛得到全局最优解。同时得出粒子群算法优化后的城市旅游路径如图3所示，根据图3得出最终该城市旅游路线为景点1→景点4→景点5→景点6→景点7→景点8→景点9→景点10→景点2→景点3，最优总里程数为269.0671 km。

表1 城市景点位置坐标(单位：km)

4 结论

图2 城市旅游路线距离值

图3 粒子群算法规划路径

本文针对城市内旅游景点众多，交通路线复杂，为能够对外来游客提供更为优质的服务，降低出行成本，节约出行时间，基于经典的旅行商问题，提出一种城市旅游路线模型，并利用粒子群算法进行模型的求解与路径规划，通过MATLAB仿真验证，本文提出模型具有一定的实际应用价值，能够有效的规划游客出行路线，为游客提供便利。

[1]沈继红,王侃.求解旅行商问题的混合粒子群优化算法[J].智能系统学报,2012(2):174-182.

[2]易正俊,李勇霞,易校石.自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2016,(12):1-5.

[3]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.

[4]Li Y,Jiao L,Shang R,et al.Dynamic-context cooperative quantum-behaved particle swarm optimization Based on mul⁃tilevel thresholding applied to medical image segmentation[J].Information Sciences,2015,294：408-422.

[5]Kennedy J,Eberhart R.Particle swarm optimization[C]//Neu⁃ral Networks,1995.Proceedings.,IEEE International Confer⁃ence on.IEEE,1995,4：1942-1948.

[6]Eberhart R C,Kennedy J.A new optimizer using particle swarm theory[C]//Proceedings of the sixth international sympo⁃sium on micro machine and human science.1995,1：39-43.

[7]Shi Y,Eberhart R.A modified particle swarm optimizer[C]//Evolutionary Computation Proceedings,1998.IEEE World

TP301

A

1672-7517(2017)08-0040-02

2017-07-15

2017-08-25

张成龙(1992—)，男，山东枣庄人，硕士，主要研究方向为无线传感器网络、多源数据融合与集成。