基于SFLA-GA混合算法求解时间最优的旅行商问题

发布时间：2020-03-29 01:04

【摘要】：随着我国旅游业的快速发展,景区需要接纳的游客越来越多,如何更好地管理景区、服务游客成为当今旅游业发展的趋势所向。旅游业可分为淡季和旺季,本文以经典的对称旅行商问题(STSP,Symmetric Traveling Salesman Problem)为基础,求解时间最优的旅行商问题(TOTSP,Time Optimal TSP),引入拟合函数和Tanimoto系数,构造出算法的适应度函数,将游览时间作为适应度函数的值,目的是旅游旺季提供一条游览时间最短的旅游路径。本论文的主要研究工作可以概括为以下几点:(1)考虑到景区客流量是随着时间变化的,本文通过采用正态分布来对景区客流量随时间变化的分析来求解TOTSP问题;(2)针对TOTSP,引入拟合函数和Tanimoto系数,构造出算法的适应度函数,将游览时间作为适应度函数的值,旨在旅游旺季给游客提供一条游览时间最短的路径推送服务;(3)首先,介绍了求解TOTSP的混合粒子群遗传算法(PSO-GA,Particle Swarm Optimization-Genetic Algorithm)、混合蛙跳算法(SFLA,Shuffled Frog Leaping Algorithm)和混合蛙跳遗传算法(SFLA-GA,Shuffled Frog Leaping Algorithm-Genetic Algorithm)的适应度函数;其次,介绍了求解TOTSP的PSO-GA混合算法、SFLA和SFLA-GA混合算法的基本原理和算法流程;(4)对SFLA,PSO-GA混合算法以及SFLA-GA混合算法3种算法的实验结果进行相互对比和分析,可知SFLA-GA混合算法求解TOTSP时有更好的性能;(5)研究了 SFLA-GA混合算法对于景点数目的敏感性,由实验结果可知SFLA-GA混合算法适用于景点数目不等的不同景区中,即景点数目的不同不影响SFLA-GA混合算法快速寻找最优解。实验结果表明:相对于随机游览路径,SFLA-GA混合算法得到的游览路径明显节省了游览时间;与SFLA和PSO-GA混合算法相比较,SFLA-GA混合算法具有计算量少、收敛速度快、对初始种群依赖性低以及全局性更好等优点,在求解TOTSP上搜索性能更强、时间更优;相对于SFLA,SFLA-GA混合算法具有较强的适应性和鲁棒性,SFLA-GA混合算法适用于景点数目不等的不同景区中,即景点数目的不同不影响SFLA-GA混合算法快速寻找最优解,能用最少的时间给游客提供一条游览时间最短的路径推送服务。
【图文】：

逦２０２１逡逑＿中国旅游人数（丨乙入次）逡逑图１．邋２中投顾问对２０１７－２０２１年我国旅游总人数预测逡逑Ｆｉｇ邋１．２邋Ｔｈｅ邋ｔｏｔａｌ邋ｎｕｍｂｅｒ邋ｏｆ邋ｔｏｕｒｉｓｔｓ邋ｉｎ邋Ｃｈｉｎａ邋ｆｒｏｍ邋２０１７邋ｔｏ邋２０２１邋ｃｏｍｅｓ邋ｆｒｏｍ邋Ｉｎｖｅｓｔｍｅｎｔ逡逑Ａｄｖｉｓｅｒｓ逡逑１．１．２研究理汾基础逡逑通过对自然界中众多优化现象的内在规律的研究，可以推演出一些有用的逡逑优化方法。近几十年来，众多经典的智能优化算法被陆续地发现，其主要包括？逡逑模拟退火算法丨７］邋（邋ＳＡＡ，Ｓｉｍｕｌａｔｅｄ邋Ａｎｎｅａｌｉｎｇ邋Ａｌｇｏｒｉｔｈｍ邋）、免疫算法［８］邋（ＩＡ，Ｉｍｍｕｎｅ逡逑２逡逑

应度函数值的大小，，并将其作为种群更新策略中的判断条件。游览T辰包含景逡逑点之间来回走动的时间、游玩景点所需的时光和在景点列队等候的时间三部分。逡逑游览时间的具体描述情况如图１．３所示：某景区内共计有ＡＡ个景点，某一旅客逡逑首先在起点（５１）处的景点位置排队等待，直到等待结束便进入当下所在位置逡逑的景点进行游玩，游玩结束后便向下一个景点出发前进，以此类推，直到最后逡逑一个景点游览完毕为止，即终点（五）游玩结束，最后从终点离开景区。整个逡逑游览过程所需要的总时间即是上述的游览时间大小，即为ＳＦＬＡ－ＧＡ混合算法逡逑的适应度函数值。逡逑／Ｗ逦Ｉ逦＇Ｓ＇＼逡逑／邋Ｖ邋Ｆ，逦４。逦＼逡逑／邋Ｘ邋，邋ｊｊ邋ｍ逡逑锎‘？NB逦

本文编号：2605192