网站地图985论文网
主要服务：硕士论文、论文发表、论文修改服务 
蚁群算法在旅游路线规划中的应用研究
来源：985论文网 添加时间：2020-05-22 14:27
摘 要
旅游路线规划是旅游中至关重要的一个环节。旅游路线规划问题数学模型的建立以旅行商问题为基础，求解可通过蚁群算法实现。本文主要研究基于改进蚁群算法的旅行商问题求解、自驾游路线规划问题和智慧旅游路线规划问题。首先，本文提出了一种基于改进蚁群算法的旅行商问题求解。为了将蚁群算法应用于求解旅游路线规划问题，需要蚁群算法求解旅行商问题时能有较大概率获取最优解，同时算法的求解时间相对较短。我们对路径选择概率和信息素更新规则进行了改进，对最优路径进行局部搜索，优化了算法的求解过程，确定了算法的合理参数。针对旅游路线规划的问题，改进了路径的求法，使蚁群算法可以实现动态规划，从而实现旅游景区的负载均衡。提出一种基于改进蚁群算法的旅游路线规划问题求解的有效方法。实验结果表明该方法具有较好的有效性和实用性。
关键词：旅游路线规划；蚁群算法；改进
1 绪论
1.1研究背景
随着国家经济的持续发展，人民生活水平的不断提高，旅游逐渐成为人们生活娱乐的一个重要组成部分，旅游业也升级成为了国家的一项支柱产业。随着旅游业的蓬勃发展，旅游者的消费方式也有了较大的改变，人们对旅游的质量也提出了更高的要求。正是在这样的大背景下，智慧旅游的概念应运而出。智慧旅游是指利用云计算、大数据、人工智能等新兴技术，通过互联网/移动互联网，借助智能手机、平板电脑等设备，为旅游者提供各种各样的帮助。智慧旅游的概念得到了国家的认可和大力推广，2014年8月，国务院发布了《关于促进旅游业改革发展的若干意见》，其中明确提出要增强旅游发展的动力，要加快智慧景区、智慧旅游企业的建设，完善旅游信息服务体系。传统旅游的六要素为吃住行游购娱，行作为旅游中至关重要的一环，很大程度上影响着人们的旅游体验。行包含着旅游工具的选择，旅游线路的设计等。行在一次旅游时间中占有很大的比例，同时行的费用也占一次旅行总消费的很大一部分。所以说，一个好的旅游路线规划可以为一次旅行节省很多不必要的时间和经费开支。在旅游方式上，相对于传统的跟着旅行团出游，自驾游成为了更多人旅游的选择。相较之前听从导游的安排，自驾游存在更多的选择空间，同时也意味着要自己安排旅行的线路。同时，随着信息技术的发展，旅游路线的安排也由传统的凭借经验设计向更高层级进行转变。传统的旅游路线一般是由旅行社设计的一条或多条固定的路线，适合组团形式的旅游，传统旅游路线是旅游经验的结晶，其设计一般需要耗费一定的时间。人工智能的提出很大程度上提高了个人旅游路线的合理程度，其中蚁群算法应用于路线规划问题对智慧旅游路线规划起到了很大的促进作用。通过建立模型并结合蚁群算法求解的旅游路线规划更具有科学性和说服力，也更有效率。旅游线路规划要考虑交通网络、个人喜好、时间成本和金钱成本等因素。首先，游客可以在各类网站查询到各类景点及景点间的可达线路，然后，要确定在各景点间的游览顺序、游览时间，在两点间选择和某种交通方式出行。旅游线路规划系统要为游客提供个性化的旅游线路，并对出游时间进行合理安排，根据现有条件，设计出游客的旅游费用支出、时间花费较少的线路，是一个在多个约束条件下的组合优化问题，本文拟采用蚁群算法解决此问题，并对蚁群算法进行改进，达到路径选择的优化效果。
1.2研究意义
旅游路线规划从区域范围可以分为三个部分：城市之间的旅游路线规划、城市内各景区的旅游路线规划、景区内各景点的旅游路线规划。城市之间的旅游路线规划和景区内各景点的旅游路线规划 都是从一点出发，经过其他点，且只经过一次，最后回到出发点的路线规划，即 TSP 回路问题。这是一个经典的 NP 难问题。所以解决方法非常多。其中包括：蚁群算法、退火算法、遗传算法、粒子群算法和禁忌搜索算法等。该文采用动态组合优化和蚁群算法进行问题求解。蚁 群 算 法（antcolony algorithm）是一种模拟进化算法，该算法由意大利学者M.Dorigo、V.Maniezzo、A.Colorini 等人首先提出，它是一种应用于组合优化问题的启发式搜索算法，该算法在求解 TSP 问题、分配问题、job-shop 调度问题等都取得了较好的效果。在旅游路线的规划中，需要系统在用户提交请求后，在最短的时间内给出一个最优的路线规划。该文对改进的蚁群算法进行了研究，提出了偶遇算法。偶遇算法可以提高蚂蚁一次周游的质量，缩短系统运算时间。通过实验对改进的蚁群算法从最优路径求解和动态规划两个方面进行了研究。实验结果表明，改进后的蚁群算法在最优路径求解和动态规划两个方面都有很好的表现。
随着人们的生活水平不断提高，旅游成为人民幸福生活新指标，随着旅游消费升级，游客更需要个性化的旅游产品。在信息化时代，游客需要更加丰富、多元的旅游服务信息，在外出旅游时，通过各类数据信息进行自主选择意识也不断增强。对于游客而言，合理、舒适、节约的旅游线路是提升旅行体验的重要标准。智能线路规划可以为游客推荐合理的个性化旅游线路，既节约时间，又减少花销，可以改善旅游体验，提升旅游目的地的形象，对促进当地旅游业的可持续发展，实现旅游服务智慧化具有重要意义。
1.3国内外研究现状
近十年，学者们对蚁群算法的改进主要集中在信息素和算法融合方面。在国外，KefiS等将粒子群算法、局部搜索算法和蚁群算法相结合，提出了一种蚁群-粒子群-2-Opt混合算法，新算法的测试有较好的结果。MavrovouniotisM等提出了一种局部搜索算子，并将其与蚁群算法进行了结合，局部搜索算子用于删除和插入城市，从而提高了解的质量，该算法应用于求解旅行商问题有较好的效率和结果。在国内，夏亚梅等提出了多信息素动态更新蚁群算法，并对旅游服务推荐系统的数据进行了验证，有着较好的性能。吴华锋提出了一种基于“优胜劣汰”进化策略的改进蚁群算法，该算法对求解大规模旅行商问题有较好的效果。李擎等提出了一种基于粒子群优化参数的改进蚁群算法，该算法对在求解大规模旅行商问题时具有明显的速度优势。杜鹏桢等等提出了一种面向对象的多角色蚁群算法，该算法可以在较少的迭代次数就非常接近于旅行商问题的最优解。胡军国等结合蚁群算法和模拟退火算法提出一种改进得蚁群算法，该算法通过模拟退火算法对蚁群算法的路径进行取舍和重复迭代，从而获得全局最优解，并应用于旅游景区的路线规划问题上。孙琼等应用伪随机比例规则对蚁群算法进行了改进，改进后的算法在旅游路线规划中有较好的效果。
2 相关技术分析
本章主要介绍了旅行商问题和蚁群算法的理论基础。首先介绍了旅行商问题的理论基础，包括标准旅行商问题、多旅行商问题以及旅行商问题的求解方法。旅行商问题常用于测试和评判优化方法的好坏，同时也是许多实际问题的基础模型。接着介绍了蚁群算法的理论基础，包括蚁群算法的原理、蚁群算法的数学模型、蚁群算法的实现步骤和蚁群算法的问题及改进思路。蚁群算法在求解旅行商问题上有较为有效。
2.1问题提出
以景区内各景点的旅游路线规划为例来进行蚁群算法在旅游路线规划中的应用研究。假设旅游者A从景区的入口T进入景区开始旅游，对于旅游路线的规划有如下三点基本要求：（1）在尽可能短的时间内给出旅游路线规划。（2）旅游路线要经过所有景点，且只经过一次，最后回到入口T。（3）景点与景点之间的距离要尽可能的短，景点的目前人数尽可能的少。要求算法的反应时间尽可能快，同时规划出的路线质量不但要短，而且要人性化
2.2旅行商问题
优化问题是人们在科学研究、工程技术等领域经常遇到的一类问题。组合优化问题是优化问题研究中的一个重要分支。组合优化问题的基础数学模型[30]是：
(2.1)
（2.2）
(2.3)
组合优化问题最主要的有三个参数（D,F,f），其中D为决策变量的定义域， 为可行域，f为目标函数。
旅行商问题（TravellingSalesmanProblem,TSP）是组合优化问题中的经典问题。旅行商问题因其在诸多领域具有代表性，从提出至今一直受到国内外众多学者的关注。
2.3旅行商问题的求解方法
旅行商问题的求解方法主要有两种类型：精确性算法和智能优化算法。精确性算法的优点是可以确定得到问题的最优解，缺点是时间代价太大。而且随着旅行商问题中城市规模的增大，其时间复杂度几何级增大，这就导致精确性算法的求解很难实现。精确性算法包括穷举法、线性规划算法和分支定界算法等。
(1)穷举法
从理论上讲，穷举法是必然能够求得最优解的。穷举法意味着列出了旅行商人所有可能的行走方案，也即可求得所有方案的路径长度，通过比较即可得到路径最短的一条。但是旅行商人可能行走的方案数是随着城市数量的增加而急剧增加的。5个城市的旅行商问题存在12个可能的方案，而10个城市的旅行商问题就存在181440个可能的方案，当城市数量增大到50个时，可能的方案就有641.5210，即使是处理速度非常快的CPU，解决起来也变得很困难。这就意味着穷举法求解城市数量较多的旅行商问题是不现实的。
(2)线性规划算法
线性规划算法（LinearProgramming，LP）是早期求解旅行商问题的一种算法。线性规划算法求解旅行商问题主要是采用整数规划中的割平面法，通过不等式约束的增加，产生更多的割平面，从而去除不含整数可行解的部分，从而使求得的解逐步收敛到最优。线性规划算法的求解效率比穷举法要高，但该算法在寻找割平面时常常要凭借人为的判断，这也意味着线性规划算法求解城市数量较多的旅行商问题并不十分有效。
(3)分支定界算法
分支定界算法（BranchandBoundMethod）求解旅行商问题是通过有效的约束界限使得搜索进程得以控制，使求得的解向着最优解的分支推进。分支定界算法的关键在于如何选取合适的约束界限，不同的约束界限所形成的分支定界法是不同的。分支定界法对于城市数量较多的旅行商问题也并不十分有效。智能优化算法的目的是以降低最优解的可能从而使得计算时间的减少到实验可以接受的程度。降低最优解意味着算法所求得的解不一定是该问题的最优解，可能是一个接近最优解的近似解，也即所谓的局部最优解。求解旅行商的智能优化算法包括模拟退火算法、遗传算法、神经网络算法、禁忌搜索算法、蚁群算法等。
(1)模拟退火算法
模拟退火算法（Simulatedannealing,SA）求解旅行商问题的思想是根据初始解和约束条件，重复迭代计算与目标值得差值，如果在设定的范围则停止迭代。模拟退火算法本身是一种蒙特卡罗迭代，其退火的过程需要设定初始值、约束条件、迭代条件和算法停止迭代的条件。
(2)遗传算法
遗传算法(GeneticAlgorithm，GA)求解旅行商问题的思想是将旅行商问题的求解相应的变换成“染色体”的生存过程，根据“染色体”群进化过程，进行复制、交叉和变异等操作，从而获得一个最适应环境的个体，从而获得旅行商问题的最优解。
(3)神经网络算法
神经网络优化算法(NeuralNetworkAlgorithm)求解旅行商问题的思想是通过将旅行商问题的解映射为一个置换矩阵，设置合理的能量函数，根据旅行商问题的最优解与能量函数的最小值的对应关系。找出满足置换矩阵要求的最优解。
(4)禁忌搜索算法
禁忌搜索算法(TabuSearch)求解旅行商问题的思想是通过是从一个可行的初始解出发进行搜索，通过设置禁忌表，从而避免算法陷入局部最优的困境中。禁忌表的使用使得算法在优化过程中可以进行记录和选择，从而在之后的搜索过程中忽略这些点。
(5)蚁群算法
蚁群算法求解旅行商问题的思想是通过蚂蚁间的相互协作，依靠信息素的信息传递，指导蚂蚁的运动方向，从而找到最短路径。蚁群算法在解决旅行商问题上有较好的应用。
2.4蚁群算法原理
20世纪90年代初期，意大利学者M.Dorigo，V.Maniezzo等人首次提出蚁群算法（AntColonyAlgorithm，缩写为ACO）。蚁群算法是一种仿生进化算法，具有种群的启发功能，专家们通过模拟自然界中真实蚁群集体觅食行为得到本算法。单个蚂蚁选择路径具有随机性，但蚁群中的蚂蚁根据一种称之为信息素的指示信息从巢穴到食物源寻找到最短路径。一群蚂蚁寻找食物源时，一只蚂蚁走过某条路时会在经过的路留下信息素，后面的蚂蚁可以感知信息素，并根据信息的浓度大小，在所有可以到达食物源的路径中逐个比较，最后选择一条最短路径，同时在自己走过时也释放信息素。具体的方法是：对比两点间各条可达路径上的信息素的浓度，当某条路径的信息素浓度比其他的路径的信息素浓度都要大时，蚂蚁选择这条路径的概率就大，反之蚂蚁选择信息素浓度小的路径概率就小。同时，蚂蚁在走过某条路时会再次留下信息素，所有的信息素会随着时间的推移不断挥发，这样一来，蚂蚁选择信息素浓度大的路径的概率大，走的蚂蚁数量多了后留下的信息素也有所增大。信息素浓度小的路径蚂蚁选择的概率小，所以走过此路径的蚂蚁数量少，留下的信息也在减少，随着信息素的不断挥发，蚂蚁选择此路径的概率越来越小。经过多次迭代，蚂蚁依据信息素浓度选择，最后可以选择出一条最短路径，实现线路的优化选择。
蚁群算法的原理是根据信息素的浓度进行路经选择。首先，在n个城市里随机放置m只蚂蚁，位于某个城市i的第k只蚂蚁选择下一个城市j的概率为 ，可以表示为：
（1）
其中：
是两个城市i和j间信息素浓度，概率与信息度成正比；
是一个启发信息， 表示城市i和j间的距离，启发信息与两点间距离成反比；
和 为信息启发因子，反映了信息素与启发信息的重要性；tabuk表示蚂蚁k已经访问过的城市列表，也称之为禁忌列表。蚂蚁按照概率选择的方法选择路径对所有城市进行遍历，完成遍历后，需要按照信息的增加及挥发进行更新，更新方法如公式（2）所示。
（2）
其中： 为小于1的常数，表示信息素的持久性因子， 表示挥发因子， 表示本次蚂蚁走过本路径留下的信息素，下一次遍历的信息素浓度为本次增
加量与上一次挥发后的剩余量之和。
（3）
其中：Q为一个常数，可以对其进行设置； 表示第k只蚂蚁在本次迭代中走过的路径长度，那么信息素的浓度就与路径的蚂蚁走过的路径成反比。
3 蚁群算法改进
蚁群算法系统可以用式（1）和式（2）表示，在式中可以看出算法的性能会受到启发因子α、信息素浓度 、启发式因子 、局部更新信息素的持久性因子 等等影响，算法的收敛性也会受到各参数组合的影响。参数 表示信息素的持久性因子，同时也反映了挥发率。信息素的更新采用了正反馈机制，容易造成一种信息素累积，导致算法陷入局部最优解。本文针对蚁群算法存在着收敛速度慢、容易陷入局部最优的缺陷，对算法进行改进。信息素持久性因子ρ的大小可以影响到蚁群算法的全局搜索能力，同时，也可以影响到算法的收敛速度，所以 不宜过大或者过小，要根据实际情况适时改变；在公式（3）中，Q是一个常数，表示信息素强度， 表示第k只蚂蚁在本次对路径的遍历中所走过的总长度。从公式（3）可以看出，蚂蚁所走的某次遍历中走过的路径越短，即 越小， 越大，说明这只蚂蚁在路上留下的信息素也就越多，所有的信息素叠加后，得到 也就越大，最终得到的 也就越大，说明后续蚂蚁经过这条路径的概率越大。本文要根据 的作用进行算法的改进，针对 只考虑了第K只蚂蚁走过的路径长度的问题，对前K-1只蚂蚁所走的路径进行综合比较后，进行加权后计算信息素浓度，增加全局影响因素。
首先，假设最优路径一般都会在较短路径中得到，所以增加较短路径的影响力。蚂蚁k走过全程以后，在信息素更新前，先和平均路径总长度进行比较，如果 说明这一只蚂蚁所走路径劣于前K-1只蚂蚁走过路径的平均值，在最优路径上的可能性较小，蚂蚁留下的信息素 应相应减小，使得此路径的选择概率减小；反之，如果Lk<Laverage，说明这一只蚂蚁走过的路径优于前K-1只蚂蚁走过路径的平均值，在最优路径上的可能性增加，蚂蚁留下的信息素 相应增加，从而使得该路径选择概率变大，加快寻优速度，同时考虑了全局最优性，减小了局部最优的可能性。具体的方是在计算第K只蚂蚁的信息素时，即计算在 时，加入影响因子λ，计算公式如式（4）所示，令 ，对Lk加权后，增加走过全局短路径的影响力，增加了算法全局最优性表现。
4 实验及结果分析
为了验证改进行蚁群算法的有效性和收敛性，根据上一节和蚁群算法设计流程，在Windows7系统下，用MATLABR2015a软件进行仿真实验，实验数据采用30城市TSP标准数据库，对算法的初始值设置如表1所示。
表1算法的参数设置
对30城市TSP问题加以测试，用传统ACO算法与本文算法计算最优路径，对于不同的迭代次数得到最短路径长度果，如图2所示，在相同的迭代次数条件下，本文算法所得到的最短距离比传统ACO算法要小，而且在150次迭代与200次迭代的结果相同，算法趋于收敛，所以本文算法收敛的速度要快。本算法在200次迭代时所得的最优路径如图3所示。
图2 ACO算法与本文算法测试结果对比
图3本文算法在200次迭代时得到的最优路径
结语
本文分析了旅游线路问题，并建立数学模型，在线路规划时采用蚁群算法，并且对基于蚁群算法的旅游线路规划算法进行改进。首先对ACO蚁群算法进行了分析，然后基于ACO算法进行了改进设计。改进算法在信息素更新前，先和平均路径总长度进行比较，如果大于平均路径，说明该蚂蚁走过的路径不是最短的；反之说明该只蚂蚁走过的路径优于前次，从而使得该路径转移概率变大，加快寻优速度。将本算法在MATLAB开发平台上实现算法进行仿真实验，得到的最优路径优于ACO算法。实验结果验证了该旅游线路规划算法的可行性和有效性。
参考文献
[1] 牛悦诚.基于蚁群算法的智慧旅游路线规划研究[D].
[2] 杨晓敏.基于蚁群算法的黄河金三角旅游路线规划研究[J].计算机时代,2018(12).
[3] 周茂杰,张翠.基于改进蚁群算法的旅游线路优化[J].现代计算机(专业版),2018,No.615(15):26-29.
[4] 田德伟.改进蚁群算法在三维路径规划中的应用研究[J].工业控制计算机,2017(08):67-68.
[5] 喻环.改进蚁群算法在机器人路径规划上的应用研究[D].2017.
[6] 荀燕琴.基于群体智能优化的AGV路径规划算法研究[D].
[7] 张晓玲,王正存,吴作君.基于改进蚁群算法的机器人路径规划[J].中国石油大学胜利学院学报,2018,v.32；No.116(02):50-53.
[8] 朱艳,游晓明,刘升,etal.基于改进蚁群算法的机器人路径规划问题研究[J].计算机工程与应用,2018,54(19):135-140.
[9] 吴启迪,汪镭.智能蚁群算法及应用[M].上海科技教育出版社,2004.
[10] 窦全胜,陈姝颖.演化计算方法及应用[M].电子工业出版社,2016.
[11] 杨淑莹,张桦.群体智能与仿生计算:Matlab技术实现[M].电子工业出版社,2012.
[12] 夏亚梅,程渤,陈俊亮,等.基于改进蚁群算法的服务组合优化[J].计算机学报,2012,35(2):270-281.
[13] 吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013(4):165-170.
[14] 李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013(6):873-878.
[15] 杜鹏桢,唐振民,孙研.一种面向对象的多角色蚁群算法及其TSP问题求解[J].控制与决策,
[16] 国务院.关于促进旅游业改革发展的若干意见[EB/OL].http://www.gov.cn/zhengce/content/2014-08/21/content_8999.htm, 2014-08-21.
[17] Kefi S, Rokbani N, Krömer P, et al. Ant supervised by PSO and 2-Opt algorithm applied to Traveling Salesman Problem[C]. IEEE International Conference on Systems, Man and Cybernetics, 2016: 4866-4871.
[18]
[19] 2014(10):1729-1736
[20] 胡军国,祁亨年,董峰,等.一种改进蚁群算法研究和旅游景区路径规划问题求解[J].计算机应用研究,2011,28(5):1647-1650
[21] 孙琼,李林.旅游路线规划蚁群算法的伪随机比例规则优化[J].科技通报,2016,32(1):175-178.
[22] 王凌.智能优化算法及其应用[M].清华大学出版社,2001:17-29.
重要提示：转载本站信息须注明来源：985论文网，具体权责及声明请参阅网站声明。
阅读提示：请自行判断信息的真实性及观点的正误，本站概不负责。
论文服务
专科论文咨询
