基于蚁群算法的旅游路线规划问题研究

李汝佳

摘要：随着生活水平的不断提高，旅游已经成为人民追求幸福生活的主要方式之一，研究旅游线路规划问题，对普及全民旅游活动以及发展旅游业起着举足轻重的作用。为了更好地解决旅游线路规划问题，构建数学模型，利用先局部后整体的思想，基于蚁群算法，模拟退火算法，粒子群算法等优化算法，结合模糊数学，旅行商问题等理论，运用MATLAB编程求解，制定一套可以高效实用的全国5A景区旅游路线最佳规划方案。

关键词：旅游路线；蚁群算法；多目标规划；退火算法；旅行商问题

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）08-0137-04

1 引言

旅游产业的发展已经成为国民经济发展新的重要增长点，它不仅能加速区域间资金流转以及信息、技术管理的传播，还创造出了高效率的消费行为模式、催生新的市场需求需求和价值等。经济发展不断好转，时代不断地向前推进，人们生活水平得到了巨大改善，在满足基本温饱的基础上，多元化的业余生活也显得越发重要，其中旅游便成了这种多元业余生活的重要组成部分，越来越多的人爱上了旅游，也愿意花时间与精力去旅游，旅游产业也随之不断壮大。

然而另一方面，同样是因为经济的快速发展，整个社会的快节奏与高竞争使得现代人的工作压力普遍较大，很少能抽出足够的时间去深度体验旅游，所以偶尔空闲出的休假如何利用好也就成了现代人关于旅游所面临的一大难题。

本文的研究只是放眼于国内，由于国内景区数目众多，所以选取国内景区最高级别的5A景区来举例说明，虽然5A级景区都是非常值得一去的地方，但由于时间、交通、费用等因素的限制，需要对旅行的线路进行仔细规划。因此，如何科学高效的设计旅游线路不仅有利于现代人的出行，对政府未来的规划也有着很重要的现实意义。

考虑到5A景区在数量上偏多，且景区所在的位置分布不均匀，本文在研究过程中，会将这些5A景区按省进行了分类，统计出各省的5A景区个数和至少需要游览的时间。基于蚁群算法先进行局部优化，设计出每个省份最优局部路线，在把问题转化为多旅行商问题，即该旅游爱好者多次出行，进行全局优化，规划出游览全国201个5A景区的最优路线[1]。

2 解决方案

2.1景区数据汇总与整理

针对某个旅游爱好者游遍全国201个5A级景区，为了规划出一条最高效的旅游方案，以及对于每一次旅游的具体行程做出详细的规划，在研究过程中，首先对所有5A景区的数据进行汇总整理，得到所有景区的分布图如图1所示：

进一步汇总得到全国31个省份5A景区个数，汇总结果如表1所示：

2.2基于蚁群算法的湖北省内游览路线局部优化模型

在对全国31个省份进行全局旅游最短时间优化之前，首先以该旅游爱好者居住省份湖北省为例，从湖北省武汉市出发，按照一定的顺序游遍湖北省内11个5A级景区，使得每一个景区都能被游览且仅能被游览一次，最后再回到出发点武汉[2]，所以决定利用现代智能算法中的蚁群算法进行最短路径的局部优化[3]。

2.2.1基于蚁群算法的模型求解

1）蚁群算法模型建立

2）局部最优解过程

2.2.2基于湖北省5A景区最优路径求解

旅游者需从武汉市出发，按照一定的顺序游遍湖北省内11个5A级景区，使得每一个景区都能被游览且仅能被游览一次，最后再回出发地武汉市。我们首先利用百度地图查找这11个景区所在位置，并利用百度地图中的测量工具，得到了这十一个5A级景区任意两两间的距离，如下表2所示。为了表述方便，将序号A—K分别代表武汉市黄鹤楼公园、宜昌三峡大坝旅游区、宜昌三峡人家风景区、十堰丹江口市武当山风景区、恩施巴东神龙溪纤夫文化旅游区、神农架生态旅游区、宜昌长阳县清江画廊景区、武汉市东湖景区、宜昌秭归县屈原故里文化旅游区、武汉市黄陂木兰文化生态旅游区、恩施大峡谷景区。

根据优化图可知，要将湖北省11个5A景区游遍最短距离约为1382公里，最优路径为：

H→A→J→C→B→G→I→D→F→E→K→H

即先游览武汉市内的景区：东湖景区、黄鹤楼公园、黄陂木兰文化生态旅游区，然后游览宜昌市内景区：三峡人家、三峡大坝、长阳县清江画廊景区、秭归县屈原故里文化旅游区，再游览十堰武当山风景区、神农架生态旅游区，继续游览恩施市内景区：巴东神龙溪纤夫文化旅游区以及恩施大峡谷景区，最后回到武汉市。

以游览湖北省内5A景区为例，我们为该旅游爱好者设计了以下具体的行程：

2.3全国5A景区游览路线全局优化模型

通过以上建模分析，可以利用蚁群算法求解出了每一个省的局部最优路线规划，本文的研究目标是得到全国游览时间的全局最优路线[5]。可以进一步将该问题抽象为一个多旅行商问题[5]，旅行爱好者多次从常住地省会城市武汉市出发，經过各省市地区旅游，最后回到武汉市，于是我们建立一个0-1规划的模型[6][7]。

1）目标函数的建立

通过对研究对象的分析与整合，目标是使旅游者游遍全国全部201个5A景区花费时间最少，可以进一步简化为花在各省之间通勤的时间最少，目标函数如下：

2）约束条件分析

3）模型建立

4）模型求解

对于多旅行商的优化，本文在研究过程中采用模拟退火算法进行求解[8]，首先求出从出发地到各省会城市并游玩它所含景点，再回到出发地形成的哈密顿圈的游览总时间，其次对这些哈密顿圈的时间进行判定，若有一个接近15天，则将其标记为一个最佳哈密顿圈，其路线就可作为一次旅游规划路线，否则就增加一个区块进行游览[9]，再利用模拟退火算法对各个区块进行最优组合，规划每次旅行的区块[10]，使每次旅游总时间不超过15天且尽量接近15天。依此方法，则可以求出最优的总时间。通过MATLAB编程模拟退火算法，可以计算出游客从武汉出发游遍全国201个5A个景区至少需要12年。

3 结语

本文研究各大城市出发的全国5A景区旅游十年规划，基于时间、路程和费用为优化目标建立综合模型，采用遗传算法进行模型求解，给出了部分城市出发的旅游爱好者十年内运用多种交通工具游遍全国5A景区的旅游路线规划，并根据全国多个城市出发游遍201个5A景区所需的旅游总时间、旅游总费用、旅游总路程，提出以“城市旅游消费指数、城市旅游舒，适指数、城市旅游安全指数、城市旅游绿色指数”为目标建立相应的旅游可持续发展评价指标体系，利用该体系为旅游爱好者提供旅游参考，为旅游相关部门提供政策建议。

参考文献：

[1] 杨静.旅游路线的优化设计研究——以中国201个5A级景区为例[J].新经济，2016（9）.

[2] 袁光辉，谢科.旅游路线动态规划问题研究——以西安市出发为例[J].数学的实践与认识，2016（8）.

[3] 田增瑞，赵阳，赵袁军.基于遗传算法与蚁群算法的最佳旅游路线设计[J].数学的实践与认识，2016（8）.

[4] 徐锋，杜军平.改进蚁群算法在旅游路线规划中的应用研究[J].计算机工程与应用，2009（8）.

[5] 姜坤霖，李美安，张宏伟.面向旅行商问题的蚁群算法改进[J].计算机应用，2015（7）.

[6] 邹腊英.基于TSP问题的旅游路线安排[J].兰州文理学院学报：自然科学版，2015（4）.

[7] 宗德才，王康康，丁勇.蚁群算法求解旅行商问题综述[J].计算机与数字工程，2014（6）.

[8] 王徐民，方玉平，张慧慧. 旅游线路优化设计[J].中国西部科技，2011（6）.

[9] 吴成明，王毅，毕红续，等.基于不同条件的旅游路线规划问题研究[J].数学的实践与认识，2016（5）.

[10] 陆国锋. 基于多约束多目标的旅游路线推荐及关键算法研究[D].国防科学技术大学，2013.

【通联编辑：唐一东】