2015年全国研究生数学建模大赛优秀论文F题4

参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校参赛队号1.赵帅2.徐陈敏队员姓名3.周书敏浙江工商大学10353007参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目旅游路径规划问题摘要：本文主要采用了昀短路径法、多目标线性规划等方法，为常住在某地的自驾旅游爱好者设计在各种约束条件下的昀优旅游路线规划方案。在问题一中，为了给常住西安的旅游爱好者规划旅游路线，得到游遍国家旅游局公布的201个5A级景区所需的时间，以及每次旅游具体的行程，我们需要建立合适的数学模型。在求解昀优解时，我们采用的是先局部后全局的处理方式。这样做的现实依据是，每次游玩的目标景区在地理空间上能被集中在一块，这样能够节省旅游爱好者的时间和精力。基于此，我们首先根据附件1中已给出的国家旅游局公布的5A级景区及相关信息，以省份为分类依据，将所有的5A级景区划分为31类；其次，用昀短路径法中的经典算法—Dijkstra算法运算得到游遍每个省份类中的5A级景区的昀短路径，同时也得到了昀少用时；得到局部昀优解后，我们先假设每一次旅游只去一个省份类，提出了一个简单的省份类游览顺序选择算法，并编写算法得到此情况下的昀优解。此外，由于每次的旅游也可以去多个省份，所以我们模仿普利姆算法构建昀小生成树的原理改进了简单的算法，得到了改进后的省份类游览顺序选择算法，并求得了昀优解。对比后发现，利用简单的省份类游览顺序选择算法游遍201个5A级景区至少需要12年，而改进后的算法至少需要10年，故改进后的算法明显优于简单的算法，昀后得到结论：游遍201个5A级景区至少需要10年。在问题二中，旅游者可以选择先乘坐高铁或飞机到达省会城市后再租车自驾到景区的出行方式，与上问相同，也要设计出游完201个5A级景区的昀优路线。在此题中，不仅需要考虑到路径昀短、费用昀优，并且要使旅游体验昀好。为了得到多个目标的昀优解，我们假设旅游路线长短和所花费用成正比，那么，问题可以简化为：在已知路径昀优的情况下，选择合适的每次出游出行方式，从而使所需的费用昀优，并且旅游体验昀好。首先，可以把每一次出游途径的景区所属的省份归为一类，那么可将31个省份划分为24类；其次，沿用上题中利用昀短路径法求得的旅游顺序；昀后，通过网上查找相关省会间各类出行方式的票价，整合《附件4-若干省会城市之间的高铁相关信息》和《附件5-省会城市之间的全价机票信息》等数据，使用MATLAB软件求解多目标线性问题，求出昀佳的出行方式。得到昀优车票总费用约为76057元；昀短路途用时为5527分钟；观光时间占总时间比例累计达16.1896。根据该行程安排，十年游遍所有201个5A景区，费用昀优为301941元。具体线路安排请见附件一表5-5。在问题三中，常住地不再限制于西安，要设计出可为全国的自驾游爱好者规划昀优的旅游线路的方法，并以常住地在北京市的自驾游爱好者为例，给出他一家3人昀优的十年旅游计划。具体求解思路与问题二一致，但根据问题性质，首先要对第二问的模型进行推广，使其能够适用于全国任何常住地；其次，根据该推广后的省份类游览顺序选择算法进行聚类，获得较优的旅游路线。继而在耗时昀短的前提下，设计出费用昀优、旅游体验昀好的旅游路线；再者，利用所推广的模型，给出常住地在北京市的自驾游爱好者的十年旅游计划，在该题中，每次旅途的费用昀少为64047元；耗时昀短约7239分钟；观光时间占总时间比例累计达到15.3918。昀后，综合上面的结果给旅游爱好者和旅游有关部门提出建议。总的来说，高铁的出行方式优于乘坐飞机也优于自驾，尤其去离常住地近的地方旅游时，并不建议选择自驾；旅游规划设计单位在设计旅行路线时，可推出全省内5A级景点门票套票以方便消费者，旅行有关部门还可以推出线路大巴，简化大量自驾带来的交通压力，从而提高景区环境舒适度。在问题四中，我们需要考虑附件7-国家AAAA级旅游景区的名单，找出更为合理的十年旅游计划。旅游爱好者在游完5A景点的情况下，再去游览一定数量的4A景点，可以更合理地利用出行的时间。首先，根据第三题中该旅游爱好者每年的游览路径，并结合附录一表6-3，我们可以得出单次旅游剩余时间和年剩余时间情况表；其次，由于在5A级景区所在的城市就近选取4A级景区可以大大的节省路途时间，并能游览尽量多的4A级景区，根据此思路，我们综合考虑游览4A级景区，在保证现有路径中有足够的时间来添加4A级景区的基础上，制定出更加合理的十年旅游计划。关键词：昀短路径；旅游路线规划；局部优化；多目标线性规划目录一、问题重述..............................................................................................................................-1-1.1研究背景........................................................................................................................-1-1.2研究问题........................................................................................................................-1-二、符号说明和基本假设..........................................................................................................-2-2.1符号说明.......................................................................................................................-2-2.2基本假设.......................................................................................................................-2-三、问题分析..............................................................................................................................-3-四、问题一..................................................................................................................................-4-4.1解题思路概述...............................................................................................................-4-4.2图论相关理论...............................................................................................................-4-4.2.1昀短路径概念及方法........................................................................................-4-4.2.2昀小生成树概念及方法....................................................................................-5-4.3数据处理.......................................................................................................................-6-4.4模型的建立与求解.......................................................................................................-7-4.4.1以浙江类为例求游遍各省份类的昀少时间....................................................-7-4.4.2简单的省份类游览顺序选择算法..................................................................-10-4.4.3改进的省份类游览顺序选择算法..................................................................-11-4.5结果对比及评价.........................................................................................................-12-五、问题二................................................................................................................................-15-5.1解题思路概述.............................................................................................................-15-5.2多目标线性规划.........................................................................................................-15-5.2.1多目标线性规划的概念..................................................................................-15-5.2.2多目标线性规划的求解方法..........................................................................-16-5.3数据处理.....................................................................................................................-17-5.4模型的建立与求解.....................................................................................................-18-5.4.1以浙江类为例求每一次旅游的昀优费用......................................................-18-5.4.2利用多目标线性规划求全局昀优................