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

万慧云 蒋艳

摘 要： 根据我国普通居民旅游情况，建立并求解乘坐公共交通工具、花费较少时间进行舒适度较高、花费较低的综合效益最大化旅游体验模型，以提升我国居民生活质量。收集我国5A景点的经纬度坐标、门票费用、最佳旅游时间、路况及食宿费用等相关数据，基于蟻群算法与Matlab2018a软件进行编程求解，得出全国5A景区旅游路线规划方案。最后根据研究结果得出结论，综合时间、费用、路程和舒适度4个目标效益最大化的模型与已有单方面或只有2～3个目标函数的模型相比，其在进行旅游路线规划时，不仅考虑因素更加全面，而且更加贴合我国大部分居民的实际需求。

关键词：旅游路线规划;蚁群算法;最短路径

DOI：10. 11907/rjdk. 182281

中图分类号：TP319文献标识码：A文章编号：1672-7800（2019）004-0141-04

0 引言

随着社会的发展和人们生活水平的不断提高，旅游经济收入已成为很多城市的主要收入来源之一。由于私家车数量不断增多，导致旅途交通拥挤、景区车辆停放等问题越来越突出。因此，如何选择合适的交通工具、最佳游览时间实现舒适度较高，而花费较低的旅游体验，对于城市居民生活质量提升具有重要意义[1]。

1 研究现状

旅游路线规划问题是基于经典TSP问题演化而来的。TSP问题是一个典型的组合优化问题，目前国内外对于TSP问题研究较多，已提出基于经典算法改进的Dijkstra算法、动态规划算法、分支定界法等[2]，以及基于启发式优化算法改进的蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、Hopfieltl神经网络、粒子群优化算法、免疫算法等[3]。但截至目前，尚没有一个解决TSP问题的完美方案。20世纪90年代，我国学者开始将TSP模型应用于实际的旅游路线规划问题中，研究结果表明，旅游者类型具有多样化特征，但其目标主要归结为两种，即自我耗费成本最小化与获得收益最大化[4]。吴凯[5]将定量与定性方法相结合设计旅游路线，但未进行实证分析，仅停留在理论层面;吴小根[6]分析研究江苏省省内旅游路线中城市节点、景区节点、临时节点三大节点类型的节点配置特征;史春云[7]研究基于线路节点特性的旅游模式，探究长三角城市旅游经济收益的空间差异[8];黄燕平[9]研究影响消费者旅游路线选择的相关因素，并以湖南永州旅游路线为例进行实证分析;刘宇青[10]研究高铁开通对消费者旅游路线选择的显著影响;黄腾[11]首先采用遗传算法对河南省13个5A景点进行无约束条件下的旅游路线规划，然后运用蚁群算法进行有费用约束条件下的旅游路线规划。在以上研究基础上，本文基于蚁群算法，并以时间最短、费用最少、路线最短、舒适度最高为目标，研究以全国任意城市为起点，乘坐公共交通工具游览全国249个5A景区的旅游路线规划设计，并以上海市作为出发城市进行实证分析，得出具体旅游时间、费用以及详细行程安排。

2 蚁群算法

2.1 算法原理

蚁群算法（Ant Colony Algorithm）是由意大利学者Colorni等[12]于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式仿生进化算法[13]。该算法采用分布式并行计算机制，具有较强的鲁棒性，但是具有搜索时间长、容易陷入局部最优解的缺点[14]。

2.2 蚁群算法流程

（1）参数初始化。在计算之前对相关系数进行初始化，如蚁群数量m、信息素重要程度因子[α]、启发函数重要程度因子[β]、信息素挥发因子[ρ]、信息素释放总量Q、最大迭代次数maxiter等。设迭代次数初值iter为1，然后将m个蚂蚁放置于n个顶点上[17]。

3 模型建立

3.1 模型假设

假设旅游者出发点是随机的，是综合距离最近、交通方便、票价最低3个因素得出的一个出发点，本文假设旅游者从自己所在地到达其城市站点的相关影响因素不在路线规划考虑之内，模型选取的出发点为旅游者所在城市公共交通工具的站点。旅游者只能选择火车、飞机、长途汽车3种出行方式，因此将每个城市站点分为火车站、飞机场与长途客运站3类，其中火车站包含出行方式有高铁、动车、普快。

（1）假设旅游总时间为T，Tij表示以城市i为起点、城市j为终点乘坐公共交通工具的消耗时间，Tjda表示从j城市车站到景点a之间乘坐交通工具的消耗时间，Tdab表示从j城市景点a到景点b之间乘坐公共交通工具的消耗时间，Tijh1表示以城市i为起点、城市j为终点乘坐公共交通工具的换乘时间，Tijh2表示在同一城市之内不同地点之间的换乘时间，Tjda表示在城市j第k个景点的游玩时间。

（2）假设旅游总路程为R，Rij表示以城市i为起点、城市j为终点乘坐公共交通工具经过的路程，Rjda表示从j城市车站到景点a之间乘坐交通工具的路程，Tdab表示从j城市景点a到景点b之间乘坐公共交通工具的路程。

（3）假设旅游总费用为F，Fij表示以城市i为起点、城市j为终点乘坐公共交通工具的票价，Fjda表示从j城市车站到景点a之间乘坐交通工具的票价，Fdab表示从j城市景点a到景点b之间乘坐公共交通工具的票价，Fjdk表示j城市第k个景点门票价格，Fjdks表示在j城市第k个景点的食宿费用。

（4）假设旅游者总体舒适感为S，Sjdkt表示在j城市第k个景点旅游时间方面的舒适度，如是否为景点最佳旅游时间点;Sjdkv表示在j城市第k个景点旅游交通方面的舒适度，如旅游景点游客数量等。

（5）假设时间约束为：景区开放时间按照国家规定为8：00-18：00，共计10小时，因此在景区游玩时间0≤Tjda≤10;考虑到旅游舒适度影响因素，每天乘坐公共交通工具时间不能超过8小时，即0≤Tij+Tjda+Tdab≤8。

（6）假设选择步骤约束为：旅游者通常首先选择一个想要旅行的城市，再到该城市的5A景点游玩，只有在该城市5A景点全部游览完之后再选择下一城市，即目标选取是有层次的。因此，本文模型可简化为先对全国249个5A景点涉及的城市作一个旅游路线规划，再针对每个城市的5A景点作旅游路线规划。

3.2 目标函数

旅行总时间最小化目标为：

最终针对不同人群进行路径规划，主要分为3种：①对时间重视程度大于对金钱的重视程度;②对金钱重视程度大于对时间的重视程度;③对时间与金钱重视程度相同。对于相应权重设置可以根据个人实际情况加以考虑。

3.3 约束条件

在不同城市之间乘坐公共交通工具的时间为Tij=到达目的地时间-出发时间[21]。

（2）每天乘车时间不超过8小时[22]。

（3）先选择城市再确定景点，或者确定景点之后，在对应城市之内游玩所有5A景点，才能转移到下一城市。

4 实证研究

4.1 数据处理

根据中国旅游局官网收集全国249个5A景区数据，每个景点所在城市站点总数为165个（共获得景区所在市县237个，但部分数据无法获得，因此归并到最近市县区）。按照官网顺序从1开始编号，每组数据包含每个节点的经纬度坐标、节点名称、景区最少游玩时间、景点门票费用、景点地区最低食宿费用等，然后到12306官网收集景点所在城市之间高铁、动车、普快的相关数据（发车时间、行车时间、票价等），共得到5 445組数据[23]。

4.2 模型求解

通过Matlab 2018a编程，第一步设计全国249个5A景点涉及165个城市之间的最优路线，第二步是独立设置每个城市5A景点的最佳旅游路线。随机选择出发城市，将模型与相应数据结合，165个城市之间最佳路线如图1所示。最后得出结果：旅游最少时间为615.5天，最低费用为159 653元，最短路程为725.84km，此时舒适度相对最高。部分城市5A景区最佳路线规划如图2、图3所示。

4.3 算例结果分析

以上海作为出发城市为例，即旅游者乘坐公共交通工具从上海出发游玩国内249个5A景区。通过分析比较，综合时间、费用、路程、舒适度4个因素，得到旅游者综合效益最优的方案为：旅游总时间为587.5天，总费用为153 653元，总路程为722.435km。

5 结语

综合时间、费用、路程和舒适度4个目标效益最大化的模型与已有单方面或只有2～3个目标函数的模型相比，一方面对各影响因素考虑更加全面，另一方面更加贴合我国大部分居民实际需求，在一定程度上也为我国相关部门制定旅游景点路线规划提供了参考意见。本方法主要存在的不足是在模型假设中还有一些实际影响因素未考虑进去，另外本文仅采用蚁群算法进行求解，由于蚁群算法本身存在缺陷，容易导致结果可能不是最优解，而是相对最优解。如果能结合其它算法进行混合算法编程求解，可能会达到更好的效果。

参考文献：

[1] 杨云鹏，袁光辉，金阳，等. 全国5A级景区旅游路线规划问题研究[J]. 数学的实践与认识，2016（15）：74-80.

[2] 徐清泉，赵夏，尚庆生. 冷链配送中的优化算法分析及应用[J]. 数字技术与应用，2016（8）：143-145.

[3] 于莹莹，陈燕，李桃迎. 改进的遗传算法求解旅行商问题[J]. 控制与决策，2014（8）： 1483-1488.

[4] 杨萍. 区域旅游者行为模式及影响研究[J]. 经济问题探索，2003（6）：114-117.

[5] 吴凯. 旅游线路设计与优化中的运筹学问题[J]. 旅游科学，2004（1）：41-44，62.

[6] 吴小根，李海鸽，冯英杰. 江苏省国内旅游线路节点配置研究[J]. 地域研究与开发，2011（5）：118-122.

[7] 史春云. 旅行模式对目的地旅游经济影响的空间差异[J]. 旅游学刊，2013（6）：102-110.

[8] 邓志刚. 旅游目的地研究文章述评分析——以旅游学刊2013- 2014年为样本[J]. 旅游纵览，2015（8）：66-70.

[9] 黄燕平，程启清，王建生.  基于蚁群算法的孔群加工路径优化研究[J]. 机械研究与应用，2016（5）：37-40.

[10] 刘宇青，杨惠，类延辉，等. 蚁群算法解决CTSP问题的参数设置研究[J].  计算机与数字工程，2011（3）：34-39.

[11] 黄腾. 基于遗传蚁群算法的5A景点旅游路线规划问题研究[D]. 武汉：华中师范大学，2017.

[12] 张雨，李芳，周涛. 云计算环境下基于遗传蚁群算法的任务调度研究[J]. 计算机工程与应用，2014（6）： 51-55.

[13] 郭文昌，张惠珍. 应用混合算法求解冷链配送中心选址问题[J]. 改革与开放，2017（8）： 82-84.

[14] 佟静翠. 基于混合算法的生产调度系统在钢构企业的研究与应用[D]. 天津：河北工业大学，2015.

[15] 秦传东. 基于遗传算法选择参数的蚁群算法求解TSP问题研究[J]. 信息与电脑：理论版，2014（11）：180-185.

[16] 毕硕本，董学士，马燕. 遗传算法和蚁群算法优化TSP的设计与分析[J]. 武汉理工大学学报，2010，32（16）：89-92.

[17] 封燕，高建瓴，粱志福. 城市物流中心选址问题研究[J]. 贵州大学学报：自然科学版，2010，27（5）：76-80.

[18] WU B，SHI Z Z. A solvable continuous time dynamic principal-agent model[J]. Chinese Journal of Computers-Chinese，2001（12）： 1328-1333.

[19] 杨再甫，黄友锐，曲立国，等.  TSP的改进蚁群算法求解及其仿真研究[J]. 合肥工业大学：自然科学版，2014（8）：928-932.

[20] 张家善.  基于改进蚁群算法的物流配送车辆路径优化研究[D]. 阜新：辽宁工程技术大学，2014.

[21] DORIGO M. An ant colony algorithm based partition algorithm for TSP[J].  Machine Learning， 2010（5）：582-597.

[22] 张天赫，彭绍雄，罗亚民，等. 基于蚁群算法的舰载机避障路线分析[J]. 兵工自动化，2017，36（10）：71-74.

[23] 米永强. 蚁群算法及其在求解旅行商问题中的应用[J]. 电脑知识与技术：学术交流，2014（3）：1505-1507.

[24] 王松涛. 基于优化的遗传算子改进蚁群算法AGV路径规划[J]. 自动化应用，2017（3）：47-49.

（责任编辑：黄 健）