最优旅游路线规划问题研究F题

参赛密码（由组委会填写）全全第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校上海对外经贸大学参赛队号10273011队员姓名1.陈迁2.施予3.张欣1参赛密码（由组委会填写）题目最优旅游路线规划问题研究（F题）摘要：本文针对全国201家5A级景点的最优旅游路线的规划问题，从不同出行需求的旅游爱好者的角度出发，运用能够收集到的大量真实数据完成了以下几个方面的工作：对于问题1，在收集每个省份内的景点间的里程数并换算成在途时间后，建立经典的TSP问题规划模型，利用模拟退火算法求得了每个省份内景点的最短在途耗时旅行路线。然后根据题目中的众多条件对最短路线进行微调，得到了在每个以省份为单位的大景区的最短逗留天数，并将201个5A景点降维到31个省份景区。进而构建了基于这31个景区的带有时间约束的TSP问题规划模型，通过对一定数量可行解的严格筛选分析，我们得到了28条共计可以用最短时间12.5年遍历201个国家5A级景点的旅游路线。对于问题2，通过建立多目标的TSP问题规划模型，并在问题1的基础上对该问题的可行解进行了分析。在对飞机和高铁/动车的出行选择根据费用进行了决策后，我们通过设计合理的可行解筛选步骤，最后得到十年内可以遍历201个国家5A级景区的23条旅游路线。最少总费用为353,240.68元。问题3是问题2的延伸，将起始地点从西安变成了北京。与问题2的分析方法基本类似，我们得到了从北京出发可以十年内遍历完201个国家5A级景点的23条旅游线路。最少总费用为447,017.94元。另外，在问题3的解答中，2我们还根据省内费用总计、里程数、游玩景点个数和平均每个景点费用4个指标给出了全部31个以省为单位的景区的性价比排名。依据此排名，我们分别对旅游爱好者和政府部门提出了有质量的建议。对于问题4，我们创新性地建立了以星级景点的价格、旅游交通、市场吸引力和游客满意度四个维度构成的评价体系框架。以云南省的5A级景点和部分4A级景点为例，通过层次分析法计算了每个维度的权重以及每个景点间的相对权重。最终我们发现其实部分4A景点相比5A景点会更具优势。因此，在进行10年旅游规划时，我们认为完全可以用部分更具优势的4A级景点来替代5A景点。这样，对旅游爱好者而言，由于4A景点在每个省内有非常多的分布，经观察，只要在每个我们优化的省内最短旅游路径上，可以在不改变原有线路的情况下将部分5A级景点替换成临近的更优4A级景点，便可以同时保证十年内遍历完而且体验更佳。关键词：TSP规划、模拟退火算法、层次分析法、Hamilton圈、最短旅游路径、5A景点3目录一.问题重述.........................................................................................................41.1.问题背景................................................................................................41.2问题提出.................................................................................................4二.问题分析.........................................................................................................6三.基本假设.........................................................................................................7四.模型建立与求解.............................................................................................84.1问题1的模型与求解.............................................................................84.1.1模拟退火算法求解各省市内部景点最短在途耗时路径..........84.1.231个以省份为单位的景区最短在途耗时规划模型.............124.2问题2的模型与求解...........................................................................154.3问题3的分析.......................................................................................194.3.1从北京出发的最优路径分析....................................................194.3.2建议............................................................................................25五、结论..............................................................................................................32六.模型的优缺点评价.......................................................................................33参考文献..............................................................................................................34附录1模拟退火算法Matlab程序...................................................................35附录2省内旅游线路.........................................................................................384一.问题重述1.1.问题背景旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动。随着近年来旅游业的不断发展，全国各地的旅游景点越来越吸引着广大的游客。为此，2007年5月22日，国家旅游局(NationalTourismAdministration)在其官方网站发布通知公告，经全国旅游景区质量等级评定委员会委派地评定小组现场验收，全国旅游景区质量等级评定委员会审核批准，决定批准北京市故宫博物院(BeijingCityMuseumoftheImperialPalace)等66家景区为国家5A级旅游景区。各省级旅游景区评定机构在指定期限内向国家旅游局推荐的5A级旅游景区创建试点单位数量达到106家。在最后评定中，有66家成为5A级旅游景区。截至2015年，国家旅游局共确定了201家国家5A级旅游风景区。这201家5A级旅游景区重点注重人性化和细节化，也更能反映出游客对旅游景区的普遍心理需求，强调以人为本，因此是人们休闲娱乐的最好去处。但另一方面，由于当今工作压力的加大，偶尔空闲出的休假如何好好利用成了现在城市人面临的难题。虽然5A级景区是非常值得一去的地方，但由于时间、交通、费用等因素的限制，需要对旅行的线路进行仔细规划。因此，如何科学的优化设计旅游线路不仅有利于居民的出行，对政府未来的规划也有着很重要的现实意义。1.2问题提出面对全国201家5A级旅游景点的分布问题，必须进行科学地优化组合研究，否则容易对出行者造成困扰。因此，本文立足现实，量力而行，尽力而为地完成为不同出行需求的旅游者科学合理地设计旅行线路的任务，并为政府的未来景点规划做出建议。本题要求运用数学模型来规划合理的旅行路线来满足不同出行的需求（自驾、高铁、飞机）。为此，需做好以下几项工作。5第一，对题概及各题的限制条件进行归纳总结：（1）该旅游爱好者需遍历201家5A级景点，每个景点不重复旅游。（2）该旅游爱好者每年旅行总天数不超过30天，每次不超过15天，每年不超过4次。（3）行车（在途）时间限定于每天上午7点至晚上7点，共计12小时。但一天行车总时间不超过8小时。（4）若安排半天景点游玩，行车（在途）时间不得超过5小时。（5）若安排全天景点游玩，行车（在途）时间不得超过3小时。（6）高速公路行车平均速度为90公里/小时；普通公路行车平均速度40公里/小时。（7）该旅游爱好者需在省会城市（非景点游览）停留至少24小时。（8）景区开放时间统一为上午8点至傍晚6点，共计10小时。（9）行车线路设计采取高速公路优先策略。（10）若选择乘坐飞机或高铁到达临近省会城市或地级市，而后需采用租车方式到达景区，租车费用为300元/天。（11）若选择乘坐飞机或高铁出行，该旅游爱好者可以在一个景点最长逗留不超过建议游玩时间的2倍时间。（12）旅游爱好者一家3人同行，住宿费省会城市和旅游景区200元/人•天，地级市150元/人•天，县城100元/人•天。（13）高速公路的油耗加过路费平均为1元/公里，普通公路油耗平均为0.6元/公里。（14）半天=4小时；一天=8小时；两天=两个一天（景点住宿一晚）。（15）若存在线路并没有全线连通的，在模型解算时若涉及到某条高速公路，只能考虑已连通的部分路段。（16）高铁和动车数据的设计上主要以运行时间较短者优先，或者选择的车次对旅游出行较为有利。（17）模型解算时需确定相应线路中具体包含的高速公路里程和普通公路里程数据。（18）乘坐高铁或飞机出行时间仍安排在每天7:00至19:00之间。（19）任两城市之间的全价往返机票价格是一样的。（1）~（8）是题干提出的条件；（9）是问题1提出的条件；（10）~（13）是问题2提出的条件；（14）~（19）是备注中提到的条件。第二，满足全自驾旅游爱好者的需求。以该旅游爱好者的常住地在西安市6为例，用数学手段规划设计自驾旅游线路，确定游遍201个5A级景区至少需要的年数，并给出每一次旅游的具体行程安排。第三，满足一般旅游爱好者的需求（可以选择高铁和飞机出行）。以一家三口常住地为西安市为例，用数学手段规划出行旅游线路满足以下三个要求：（1）十年内游遍201家国家5A级景点；（2）费用最优；（3）体验最好。第四，将上述的数学模型进行一般化，然后对居住地在北京市的旅游爱好者优化类似的十年旅游规划。同时，根据目前政府在旅游景点规划方面存在的问题，结合前几问的解答对旅行者以及旅游相关部门提出建议。第五，在引入国家4A级景点之后，基于上述的分析，为旅游爱好者规划更合理和有意义的十年旅行路线。二.问题分析旅游线路的优化组合问题一直以来是学术界关注的问题。同时，因其与我们的生活息息相关，所以，合理规划旅游线路也具有很强的现实意义。对来往各地的里程数和在途时间数据，景点游玩的逗留时间数据以及旅行途中的费用数据进行分析和建模对于制定合理的旅游规划路线有重要的参考的意义。问题1是西安市的一名旅游爱好者全程自驾旅行并采用高速公路优先策略，要求确定遍历全部201个5A级景区需要多少年数。考虑到201个景点的道路里程距离涉及到至少20000个数据的手