搜索
参赛密码（由组委会填写）全全第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校西南交通大学参赛队号10613003队员姓名1.朱允瑞2.周平3.陈平-1-参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目旅游路线优化设计问题研究摘要本文分别通过建立带约束的非线性单目标和多目标优化模型，解决了旅游路线的最优设计问题。线路的设计主要受旅游费用、旅游时间、可游览景点数等因素制约，通过将路线规划问题转化为旅行商（TSP）问题，使用蚁群算法和遗传算法求解得到最优的旅游路线。问题一要求设计最优的旅游路线在最少的年数内游完全国201个5A景点。本文建立带约束的非线性单目标优化模型，以旅游时间花销最少为优化目标。将普通公路里程和高速公路里程统一转化为高速公路里程，推导出总旅游时间花费函数表达式。合理地引入0-1变量表示旅行者是否游玩过景点，得到将旅游时间转化为天数的分段函数表达式。将旅游路途时间花销和游览时间花销转化为景点i到景点j的旅游天数时间花销，从而将旅游路线规划问题转化为TSP问题，进而通过编程使用蚁群算法求解得到最优的旅游路线。获得最优旅游路线及时间花销之后，结合人工判断合理的旅游花销天数（即满足一年旅游时间不超过30天，每年外出次数不超过4次）组合成一年的总时间花销进而得到旅游的最少总年数。问题二要求在十年内游完201个5A级景区，并综合考虑多种出行方式，给出费用最优的费用最优、旅游体验最好的旅游线路。本文建立了带约束的非线性多目标约束模型，以费用最优和体验最佳为优化目标。与问题一不同的是，本问要求花费时间最少、体验最佳，本文对体验最佳的理解为交通耗时最少而游览时间较多。同样地，本题也可以用问题一的方法，将旅游路途交通花费和游览时间花销转化为景点i到景点j的旅游天数费用花销，将问题二转化为TSP问题。使用遗传算法求解得到花销最少的旅游路线集，结合人工判断从中挑选出时间花销最短的旅游路线。-2-问题三需要在第二问所建立的模型基础上加以推广，为全国的自驾游爱好者规划设计旅游线路并给旅游爱好者和旅游有关部门提出建议。为使模型更具通用性，本文将旅行者的餐饮费和不同景点的门票费用加入到拓展的模型之中，并推导出旅游总花费函数表达式和总游览时间函数表达式。和问题二类似，将旅游路途交通花费和游览时间花销转化为景点i到景点j的旅游天数费用花销，将问题三转化为TSP问题，通过编程使用遗传算法求解得到花销最少的旅游路线集，结合人工判断从中挑选出时间花销最短的旅游路线。结合前三问的结果，并进行分析给旅游相关部门提出了两条建议：（1）完善景区之间的高速公路建设，（2）在热门景点设置一定数量的停车场；给旅游者提出了三条建议：（1）尽量延长每次出游时间，（2）可以考虑组团自驾游，（3）避开旅游热季。问题四要求参考附件6与附件7，更为合理地规划未来十年的旅游计划。通过改进模糊层次分析法模型，从可能被摘牌的5A景区所在省份选拔出评分较高的4A景区作为备选5A景区。本文将5A景区的评定细则分为服务质量与环境质量、景观质量、游客意见三部分作为模型的准则层，每个部分的评定款项作为方案层。由细则给定的打分作为各款项的权重。由改进模糊层次分析法模型得到各省内4A景区的综合排名，从而得到最优的备选4A景区。以最优的4A景区替换可能被摘牌的5A景区，使用问题三的算法进行求解，得到更为合理地规划未来十年的旅游计划。基于本文较为完善的机理分析，建立带约束的非线性单目标和多目标优化模型，并借助蚁群算法和遗传算法结合的方式，得到符合要求的最优路线设计方案。成功地对0-1变量进行使用和约束，简化模型建立难度，得到较好的结果。最后本文对模型进行评价与推广，模型的精准性高、鲁棒性强、普适性强。关键词：旅行路线规划多目标优化蚁群算法遗传算法TSP问题0-1变量-3-一、问题重述及国内外研究情况1.1问题的背景旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动。1.2问题的提出附件给出了全国201个5A级景区的名单，全国高速公路，全国火车、高铁、飞机班次等信息。一位自驾游爱好者拟按这些附件制定旅游计划。根据该旅游爱好者的个人偏好，景点位置及开放时间的实际情况，在旅行中需要达到以下条件：该旅游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天；根据个人偏好，每个5A级景区的游览时间不得小于附件中的要求，最长逗留时间不得超过附件中最少时间的2倍；基于安全考虑，行车时间限定于每天7:00至19:00之间，每天开车时间不超过8小时；若是全天游览，则开车时间控制在3小时内；若是半天游览，开车时间控制在5小时内；在高速公路上的行车平均速度为90公里/小时，在普通公路上的行车平均速度为40公里/小时；该旅游爱好者计划在每一个省会城市至少停留24小时，以安排专门时间去游览城市特色建筑和体验当地风土人情（不安排景区浏览）；选择高铁出行要求当天乘坐高铁的时间不超过6个小时，乘坐高铁或飞机的当天至多安排半天的景区游览;景区开放时间统一为8:00至18:00；旅行中租车费用300元/天，油费和高速过路费另计，租车和还车需在同一城市；住宿费简化为省会城市和旅游景区200元/人•天，地级市150元/人•天，县城100元/人•天；高速公路的油耗加过路费平均为1.00元/公里，普通公路上油耗平均为0.60元/公里；根据上述条件，需要解决下面问题：（1）该旅行者出行先通过高速公路到达与景区邻近的城市，再自驾到景区。以其常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年？给出每一次旅游的具体行程（每一天的出发地、行车时间、行车里程、游览景区）。（2）若出行方式考虑乘坐高铁或飞机到达与景区相邻的省会城市，而后租车自驾到景区游览。根据附件材料，建立数学模型设计一个十年游遍所有201个5A景区、费用最优、旅游体验最好的旅游线路，给出每一次旅游的具体线路（含每次具体出行方式；每一天的出发地、费用、路途时间、游览景区、每个景区的游览时间）。（3）在（2）的基础上加以推广，为全国的自驾游爱好者规划设计类似的旅游线路，进而给出常住地在北京市的自驾游爱好者的十年旅游计划；根据上述三问的结果给旅游爱好者和旅游有关部门提出建议。（4）根据国家5A级旅游景区评定的相关信息，更合理地规划该旅游爱好者的十年旅游计划。-4-1.3国内外现状国内外有学者对于旅游路线规划等问题也进行了相关研究，佟欣[1]等人将黑龙江30个景点之间的关系转化为图论问题，建立赋权图，利用蚁群算法来解决最短路径问题，从而研究出黑龙江的最优旅游路线。潘玉侠[2]等人根据旅游线路设计的特点对遗传算法进行了改进，建立了基于遗传算法的旅游线路优化算法。国外部分学者[3-5]等也针对旅游路线规划等相关问题进行了研究，得到了较为丰富的结果。二、基本假设1.假设未来十年多的物价等维持在现在水平；2.途中没有遇到意外情况，行程没有延误；3.计算交通耗时四舍五入像一刻钟取整；4.除了当天能够游玩两个景点的情况，旅行者在到达景点后不在安排行车；5.票价以当前时间为准，未发生变动；6.假设被警告的9个5A景区在未来被摘牌；7.升级的4A景区从被摘牌的9个5A景区所在省中选取。三、符号说明与名词解释3.1符号说明序号符号符号说明1it在景点j停留时间2mk第k次出游游玩的景点数3ijr是否从景点i到景点j4()kijT第k次出游为从第个景点到景点i路上花费的时间和景点j游览时间转化后的天数5()kdT第k次旅游游览时间为两天的次数6()kT第k次旅游游览的天数7ijd两个城市i与j之间的高速公路距离8TC交通费总和9DC住宿费总和10RC餐饮费总和11iC为景点i的门票费3.2名词解释序号名词名词解释1国家5A级旅中华人民共和国旅游景区质量等级划分为五级，从高到低依次为-5-游景区AAAAA、AAAA、AAA、AA、A级。5A级为中国旅游景区最高等级，代表着中国世界级精品的旅游风景区等级。四、问题分析4.1问题一的分析本问要求一种设计合适的方法，建立数学模型，以旅游爱好者的常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年。该问题与TSP问题类似，但是又不是常见的TSP问题，因此考虑通过相应的转换，将该问题转化为TSP问题。该问的约束较多，需要逐一满足，同时要满足总体约束即满足一年旅游时间不超过30天，每年外出次数不超过4次。通过查询各景点之间的公路里程，我们将普通公路和高速公路混合的路线通过加权的方式统一转化为高速公路以方便计算。将旅游路途时间花销和游览时间花销转化为景点i到景点j的旅游天数时间花销，从而将旅游路线规划问题转化为TSP问题，这类问题可以通过二叉树、蚁群算法、遗传算法等算法来求解。4.2问题二的分析问题二要求在十年内游完201个5A级景区，并综合考虑出行方式，给出费用最优的费用最优、旅游体验最好的旅游线路。这是一个带约束的非线性多目标约束问题，以费用最优和体验最佳为优化目标。与问题一不同的是，本问要求花费时间最少、体验最佳，我们对体验最佳的理解为交通耗时最少而浏览时间较多。与第一问类似，本问可以同样地将旅游路途交通花费和游览时间花销转化为景点i到景点j的旅游天数费用花销，将问题二转化为TSP问题。在求解时，可以通过使用遗传算法和蚁群算法结合的方式，通过遗传算法播撒可能的结果种子，蚁群算法计算花费时间。当得到几组费用花销最少的旅游路线之后，可以从中筛选出时间花销最少的旅游路线。4.3问题三的分析问题三需要在问题二所建立的模型基础上加以推广，为全国的自驾游爱好者规划设计旅游线路并给旅游爱好者和旅游有关部门提出建议。为使模型更具通用性，我们可以考虑将旅行者的餐饮费和不同景点的门票费作加入到问题二的模型之中。模型建立之后，可以采用与问题二类似的算法求解。最后需要结合前三问的结果进行分析给旅游相关部门和旅游者提出建议。4.4问题四的分析问题四要求参考附件6与附件7，更为合理地规划未来十年的旅游计划。通过附件6可以知道2015年4月2日上午，国家旅游局通报，从2014去年四季度到2015年一季度，山西忻州五台山、南京夫子庙秦淮河观光带等9家5A景区被警告。我们考虑将可能被摘牌的5A景区所在省份选拔出评分较高的4A景区作为备选5A景区。这样可以更好地规划未来十年的旅游路线。因为在附件6中给出了5A级景区的评定细则，考虑建立层次分析法来合理地筛选备选5A景区。将备选5A替换原可能被摘牌的5A景区之后，收集替换后的5A景区各景点的公路里程，接下来可以重用问题三的算法进行求解，并得到最优路线。-6-五、问题一模型的建立、求解及应用本文要求一种设计合适的方法，建立数学模型，以旅游爱好者的常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年。本文在百度地图[6]上收集数据，该数据包括两部分：省内景点与景点之间的最短距离（其中包括高速路距离和普通公路）和各省会与景点之间的距离。景点大致分布图如下图1所示。在满足相应的约束条件下，建立数学模型计算得出最佳路线，从而得到时间（天数）最少的目标函数，并对目标函数里的参数进行多目标约束，采用蚁群算法求解出以西安为起点的旅游路线，并得到每一次旅游的具体行程（每一天的出发地、行车时间、行车里程、游览景区等），从而可得出至少需要的时间，解题思路如图2所示。图1A5景点大致分布图收集景点间公路信息开始结束推导总旅游时间花费函数表达式设置模型约束转化为TSP问题计算最优旅游路线每次出游的旅游天数集将普通公路和高速公路统一转换为高速公路旅游的总年数及最优路线各景点之间的高速公路距离蚁群算法求解人工组合图2问题1的思路流程图-7-5.1模型的