基于模拟退火算法针对多目标优化的最优旅游路径实证研究11000字【论文】

基于模拟退火算法针对多目标优化的最优旅游路径摘要本文主要针对如何制定最优旅游路径的问题，以杭州市的25个景区为例，优旅游路径模型，应用MATLAB软件调用相关数据，分别使用模拟退火算法和遗传算法对模型进行求解，对比求解结果，模拟退火算法求得最短路径为460.0926千米，遗传算法求得结果为465.0773千米，发现模拟退火算法结果更目录 1 3 31.1.1研究背景 3 31.2研究意义 4 42.1选取推荐景点 42.2.1确定评价指标 52.2.2数据统计及整理结果 52.2推荐景点地理位置 62.3旅游时间统计 8 94.符号说明 95.模型建立与求解 5.1建立多目标最优旅游路径模型 5.1.2模型建立 5.2模型求解 5.2.2遗传算法对模型求解 5.2.3求解结果分析 5.3改进多目标最优旅游路径模型 5.4改进的模拟退火算法求解 5.4.2求解结果分析 6.结果分析与方案制定 7.1模型优点 217.2模型缺点 21 9.参考文献 1.1.1研究背景关统计数据显示，2019年中国的国内游客达到60.1亿人次，即便2020年由于疫情影响国内旅游人次同比减少，到2020年底，全国游客竟也达到50.7亿人次，可见国民对旅游的热衷程度。据了解，大部分人会在旅市统计局报道，截至2020年底，余杭地区共接待游客总人次2323.44万人，恢复到2019年同期91.63%;旅游的总收入同比增长0.25%,因此，本课题将以杭州1.1.2国内外研究现状在复杂环境中容易变得固定，导致部分蚂蚁会失效，从而造成效率低下，迭代次数增多的问题，所以在实际中应用不大。近年来，随着旅游业、物流业及交通运输业的发展，多目标的最优路径问题的研究越来越深入，除了传统的蚁群算法，遗传算法在多目标优化领域开始被广泛应用，例如2018年李振业等人应用遗传算法对徐州的旅游最优路径进行了研究，考虑了景点位置、旅游团时间和停留时间这三个因素，应用遗传算法解决问题，但是其约束条件过少，并且现在更多人愿意自助游，所以缺少实际性。2020年李梦丹等人应用蚁群算法对西安的最优旅行路径进行了研究和规划，但其只考虑到了位置因素，对费用、交通等因素不做考虑，缺乏实际性。可见在旅游路径规划上有空间可以深入研究。当前人们生活水平逐步提升，旅游成为人民群众重要的娱乐方式，但假期时间有限，且在交通上会消耗时间，所以如何规划最优的旅游路径成为游客需要解决的一大难题。并且目前是信息化时代，游客可以通过旅游网站寻找最优旅游路线，所以对旅游网站来说，设计出更加合理的旅游路线非常有意义。本文是以杭州市旅游为例，如果想应用于其他省市，可以直接按照文中方法查找相关数据，然后应用模型求解即可得到结果，可以看出本文研究内容具有实际应用价值。同时，多数最短路径问题更多的只考虑最短旅行时间和路程，本文中改进的多目标最优旅游路径综合考虑了景点的开放时间，建议游玩时间和最短路径等因素，使研究内容更贴合实际情况，并且根据建立的数学模型，应用模拟退火算法和遗传算法分别求解，对比两种算法求解的差异，最终考虑应用模拟退火算法，然后对模拟退火算法进行了改进，使其能够根据时间和路径的优先级进行扩张，具有一定的理论意义。杭州市是历史七大古都之一，拥有众多著名的旅游景点，民间也一直流传着2.2.1确定评价指标再根据这三点的重要程度对他们分配占比，具体分配见下表2-1:表2-1评价指标及占比指标占比(%)景点等级景点评分景点票价2.2.2数据统计及整理结果根据2.2.1建立的评价指标，在旅游网站上查找相关信息记录并统计，共选取了35个旅游景点进行统计，根据最后的排名结果，选取前25个旅游景点作为表2-2所示：表2-2推荐景点数据级(A)排名排名(携程)西湖51121六和塔46252西溪国家湿地公园5233千岛湖景区5344雷峰塔45485475464427河4828湘湖4929谷441灵隐寺026041白堤021大明山景区42瑶琳仙境4442苏堤027031断桥残雪033047三潭印月03杭州灵隐(飞来峰)029曲院风荷027柳浪闻莺027044阅资料，选择应用阿里云所提供的地图选择器网站，通过这个网站，可以很快的查到景点的具体位置信息，并且可以直接转换成想要的文件格式。此处，为了方便后续的计算，我将其转换成了.shp文件。具体操作步骤如下图2-1所示：到网站内下载地区的最终得到的地理位置坐标如表2-3所示：西湖大明山景区六和塔瑶琳仙境西溪国家湿地公园杭州野生动千岛湖景区苏堤雷峰塔断桥残雪花港观鱼垂云通天河三潭印月湘湖杭州灵隐(飞来峰)浙西大峡谷曲院风荷灵隐寺柳浪闻莺南宋御街白堤在MATLAB中画出的位置图如下图2-2所示：图2-2景区地理位置图同样通过旅游网站，查找各个景区的详细数据，得到各个景区的建议游玩时间，如下表2-4所示：表2-4景区建议旅游时间时间(分钟)间(分钟)时间(分钟)西湖浙西大峡谷断桥残雪六和塔灵隐寺花港观鱼西溪国家湿地公园三潭印月千岛湖景区白堤杭州灵隐(飞来峰)雷峰塔大明山景区曲院风荷瑶琳仙境柳浪闻莺动物世界南宋御街垂云通天河苏堤湘湖4.符号说明符号说明由所给数据构造的有向图X节点集合E有向边集合编号i对应的节点节点x;到x;所花费的总时间5.模型建立与求解5.1.1多目标优化问题概述minF=F(x)=[f₁(x),f(x),…,fn(x)]n=1,2,…,NE5.1.2模型建立基于多目标优化问题的具体描述，思考多目标最优旅游路径问题，首先从最短路径条件考虑，该问题可以描述为：对于G=(X,E),节点集为X,节点间的有向边集合为E,IX|=n,IE|=m,令F(s=1,2…,S)表示第s个目标值，ds(i,j)为从节点i到节点j的第s个目标值，以此建立多目标最优旅游路径模型：为了方便后续求解，在此处应用效用最优化模型，即将规划问题的各个目标函数通过加权的方式进行求和运算，将所有目标函数与效用函数建立关系，各目标之间通过效用函数协调，使多目标规划问题转化为传统的单目标规划问题，单目标规划问题的简单数学描述如公式(5-2)(5-3):在应用效用函数当作目标函数之前，需要确定一组合适的权值θ来反映原问题中各个目标函数在所有目标函数中的权重值。在该问题中，每两个景点之间都可以有通过情况，并且概率相等，所以权重值可以忽略不计，最终将原始的多目标最优旅游路径转换为如下模型：下面根据建立的最优旅游路径模型和相关数据进行模型求解。5.2.1模拟退火算法对模型求解模拟退火算法思想简介模拟退火算法是基于Monte-Carlo迭代求解策略的一种随机寻找最优解的算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似从热力学方面来看，退火实际上就是一种物体实现温度逐渐降低的一个物理过程。随着物体温度的降低，物体的能量状态也逐渐变低，当温度达到足够低时，物体的状态就会变化，会变得冷凝和结晶。根据热力学相关知识：如果物体处于结晶状态，那么物体能量状态就处于平衡时的最低能量时期。当物体温度逐渐降低时，物体可以达到最低的能量状态，就是结晶的物理状态，但降温过程过快时则会导致物体处于能量非最低的非结晶状态。[5]总的来说，模拟退火算法就是从某一较高初温出发，随着温度参数的不断下降，结合适应度函数在解空间中寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能。模拟退火算法具体步骤根据本文具体研究的最优旅游路径问题、即将要求解的内容和模拟退火算法的基本思想，设计模拟退火算法具体的求解步骤，如下所示：(3)对当前所求的解S₁进行随机扰动，使其产生一个新的解S₂。(4)计算S₂的增加量df=f(S₂)-f(S₁),其中f(S₁)为代价函数，代价函数的含义于适应度函数一致。(5)若dg<0,则接受S₂作为新的当前解，即S₁=S₂;否则，计算S₂的接受概率exp(-df/T),T是温度。随机产生(0,1)区间上均匀分布的随机数rand,若exp(-df/T)>rand,也接受S₂作为新的当前解S₁=S₂,否则保留当前解S₁。91(6)如果满足所设定的终止条件，那就输出当前的解S₁作为所求问题的最优解，结束当前运行的程序，如果不满足终止条件，就按衰减函数对温度T进行衰减，衰减后再返回步骤(2),对所求的问题进行降温，令不是最优解的解被接受的可能性逐渐降低，让最终的结果逐渐接近最优解。模拟退火算法模型求解根据上述算法概述，应用MATLAB进行编程，调用相关数据对模型求解，多次运行后选择最短的一条路径，得到的结果如下图5-1、5-2、5-3和5-4所示，具体代码见附录：图5-3路径最优解初始种群中的一个随机值：7一>13一>9一>11->10->4->20一>6一>22一>18->2一>14一>16一>3一>19一>17一>5一>25一>15一>1->23一>12一>8一>21->24->7最优解：20一>5一>12->6一>18一>19一>13一>21一>17->23一>22一>7一>2->9一>25一>24一>11->3一>10一>14一>4->15一>8一>16一>1-20总距离：460.092611->3->10->14->4->22->20->2->7->8->15->16->23->19->13->17->1->11,结果中数字为各机的1073.7328(千米)到最短的总距离为460.0926(千米),减少了约614千米的路5.2.2遗传算法对模型求解遗传算法思想简介遗传算法具体步骤的编码原则是每一个染色体表示一条可能的旅游路径，由按一定顺序排列的252.生成初始种群遗传算法一般都是在迭代开始随机的生成初始种群，在MATLAB软件中可f=1-(f₁-fmin)/fmax-fmin)(5-4)其操作流程为：选择算子->交叉算子->变异算子->搜索每一代的最优路径；的每条染色体都随机的选择两个变异点，分别把它们记为Pos1和Pos2,如果生同样的，根据上述算法概述，应用MATLAB进行编程，调用相关数据对模型求解，多次运行后选择最短的路径，得到的结果如下图5-5、5-6和5-7所示，图5-5模拟退火算法最优路径图5-6最优路径细节图最优解：22->1->2->7一>9一>20->21一>17一>23一>19一>13一>5一>24一>25->12->6一>18->11->10一>14->4一>15->8一>16->3->22总距离：465.077301图5-7最优解路线图5.2.3求解结果分析通过用两种方法对模型求解，得到了游玩25个景区的最短路径，其中模拟退火算法求得的最短路径为460.0926(千米),而遗传算法求得的最短路径为465.077301(千米),可见应用模拟退火算法求的结果更好，所以后续求解改进的中不容易出现陷入局部极值的情况，更加表明了该算法在求解类似货郎担路径5.2中建立的数学模型只考虑了路径最短的情况，对于实际生活中的实用性8:00-12:00和下午14:00-18:00,晚上3个小时，时间不限，建立改进的最优旅游时间问题，且增加两点之间时间不可以超过4小时的约束条件(因为景点的开放时间的连续间隔最长为4个小时),该模型的建立符合实际情况，对比原始模型足以下条件：连续游玩的至少三个景点总时间不可以超过180分钟(3个小时),况，最终确定假设汽车的平均速度为40公里每小时，假设地铁的平均速度为80根据以上求解思想，应用MATLAB调用查询的相关数据，对改进的模拟退最优的一组，求解得到结果如下图5-8、5-9、5-10和5-11所示：图5-8优化过程迭代图图5-9路径最优解图5-10最优解细节图初始种群中的一个随机值：8->18->10->17->3->20->1->13一>12->16->7->15->22->14->24->6->23->2->11->19->21->9一>5->4->25->8总距离是：1274.2357总时间是：1150最优解：4一>14->10->16->7一>1->23->17一>21->3->22->11->20->5->24->19一>13->25一>12->6一>18->9一>2一>8一>15->4最优总距离为：452.3376最优路途汽车耗时为：685.3599最优路途地铁耗时为：347.952汽车出行总游玩时间为：1835.3599地铁出行总游玩时间为：1497.952图5-11最优解路线与耗时结果5.4.2求解结果分析4->14->10->16->7->1->23->17->21->3->22-->24->19->13->25->12->6->18->9->2->根据改进的数学模型，限定路途时间不可以超过4个小时，4个小时即为240分钟，模型求解得到的最短路途上花费的时间为347.952分钟，该时间为三日旅游的总时间，如果把它平均分配给三天，那每天花费的时间不超过200分钟，200<240,所以符合设定条件。并且按照定义的旅游景点开放时间，三天内旅游景区可用时间为(4+4+3)*60*3=1980(分钟),而我们最终求得的总的最短时间为1497.953分钟，少于1980分钟，符合条件，因此可以看出求解结果是合理的。4->14->10->16->7->1->23->17->21->3->22-->24->19->13->25->12->6->18->9->2-短，如果考虑地铁换乘的时间，首选站内换乘，则再增加20分钟换乘时间，总结合求解结果和相关数据，下面对旅游景区进行合理安排，制定三日旅游计第一天：8:00-12:00游玩：千岛湖景区(4)->大明山景区(14)->浙西大峡谷(10),共耗时170分钟，在时间限制范围内14:00-18:00游玩杭州野生动物园(16)->杭州宋城(7)->曲院荷风(23),共耗时160分钟，在时间限制范围内19:00-22:00游玩苏堤(17)->三潭映月(21),共耗时80分钟第二天：共耗时160分钟，在时间限制范围内14:00-18:00游玩：花港观鱼(20)->雷峰塔(5)->柳浪闻莺(24),共耗时100分钟，在时间限制范围内19:00-22:00游玩：断桥残雪(19)->白堤(13),共耗时80分钟，在时间限制范围内第三天：8:00-12:00游玩：南宋御街(12)->清河坊街(6)->钱塘江(12),共耗时140分钟，在时间限制范围内14:00-18:00游玩：湘湖(9)->六和塔(2)->垂云通天河(8),共耗时110分钟，在时间限制范围内19:00-22:00游玩：瑶琳仙境(15),共耗时80分钟，在时间限制范围内以上是根据求解结果制定的旅游计划，可以看出每一个时间段的旅游路径选取均在规定的最优旅游路径中，游客有充足的时间对突发情况进行合理的安排，例如考虑天气因素，当天气为雷雨天气时，增加交通耗时在20-60分钟，依旧在时间限制范围内，即方案同样具有可行性。主要应用多目标优化、最优路径、模拟退火算法和遗传算法，从多个方面对模型进行研究，所建立的模型更加客观全面，具有实际意义，同时避免了单一算法对解决问题的错误计算，改进后的数学模型在实际生活中也可以有较好的应用。1.本文中只考虑应用两景点间直线距离作为实际距离，且汽车和地铁发车时间连续的情况，忽略行程中路段复杂以及其他交通工具的情况，可能会造成一定2.相关数据都是从网上查找所得，与实际情况可能有出入，且在不同网站上获取的数据也可能会有差异，在某些程度上会影响得到的结果。本文主要应用多目标优化、模拟退火算法和遗传算法相关知识，对如何制定最优旅游方案的问题进行研究。通过多目标优化模型的求解结果，与随机路线进行对比，两种算法都减少了大约600千米的路程，效果显著。再将两种求解算法的结果进行对比，发现模拟退火算法求得的结果更优，最终确定应用模拟退火算法对模型求解。原始模型没有考虑过多的实际情况，所以又对模型进行改进，加入时间的约束条件，考虑了景区开放时间、路程耗费时间等情况，应用改进的模拟退火算法对模型求解，将得到的结果与设定的条件作比较，最终得到的结果符合本文设定的条件以及实际情况。在此可以看出，改进的模拟退火算法可以用于求解目标规划类问题，并且具有一定的准确性，在以后的研究中还可以考虑更多方面，持续对其优化改进。最后根据求得结果制定三日游方案，方案中的每一天都是根据时间和路途合理安排的，且经过验证都在规定范围内，可以为游客提供可靠且高效的游玩方案。。模型的建立和求解都是从多个方面进行研究，比较全面，具有实际意义，但同时也缺少突发际情况以及路段复杂的一些判断和解决措施，所以如果后续有机会的话，还可以对本文内容做进一步的改进，使其更加具有实用性，发挥更大的价值。[1]王梦甜.基于遗传算法的南京周边城市旅游规划研究[J].市场周[2]杨帅.求解多旅行商问题的进化多目标优化和决策算法研究[D].武汉科技大[3]李梦丹.基于蚁群算法西安旅游路线的优化研究[J].价值工程，2020,39(20):136-[4]刘建军，司光亚，王艳正，何大川.基于模型的多目标优化问题方法研究[J