2015年全国研究生数学建模竞赛

参赛密码全全第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校西安工程大学参赛队号10709012队员姓名1.卞京红2.张茜3.张永强参赛密码第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目：旅游路线规划问题摘要随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动，其已逐步成为全球经济发展的重要动力之一。本文针对旅游路线的规划问题，进行了多方面研究，设计了可行有效的旅游方案。针对问题一，首先依据TSP优化理论，建立了数学模型，其次利用DIJKSTRA算法求得任意两省会之间的最短距离，运用LINGO编写程序进行模型求解，运用MATLAB编写程序。在旅游费用不限的情况下，设计出了畅游全国5A级景区的较佳旅游路线,并得出最短旅游年限约为13年。针对问题二，采用聚类分析的方法按省会城市的离散程度进行分类，借助MATLAB软件对数据进行处理，同时，假定以西安为中心，综合考虑飞机，高铁和自驾租车等交通方式，依据题中所给的各种费用和时间限定信息，设计出了每一天具体的出行方式、出发地、费用、路途时间、游览景区和每个景区的游览时间。最终算出总费用为4.7193e+006元。针对问题三，在第二问的基础上，以北京市为中心，以自驾为主，费用最低为目标，进行旅游线路设计，规划出了更适合十年旅游计划的自驾游爱好者的旅游路线；根据旅游景区的现状及旅游者的兴趣，提供了相应的建议，以便于旅游者更好的游玩，同时也方便相关部门为游客提供更好的服务。针对问题四，根据5A级旅游景区的评定信息，结合周边的4A级景区，利用遗传算法，根据其离散程度对全国进行分区，共分为7个区域，分别为华北地区，东北地区，华东地区，华中地区，华南地区，西北地区，西南地区。依据分区结果，更合理的安排旅游者的十年旅游计划。关键字：旅游线路，MATLAB，DIJKSTRA算法，聚类分析，最优线路问题-1-一、问题重述1、背景随着科技的进步和社会的发展,旅游已成为人们的一种生活方式,是提高人们生活质量的重要活动。旅游业的不断发展成熟,使得人们外出旅游变得十分方便,一方面是旅行社提供的团队游产品日趋丰富;另一方面是个性化的自助游随着日益成熟的旅游环境让旅游者渴望尝试。不管是团队游还是自助游,旅游线路都是连接旅游客源地与旅游目的地的重要环节。设计合理的旅游线路既有利于旅游者有目的的选择、安排自己的旅游活动,避免“漫游”,又有利于发挥各旅游点的功能以及旅游者合理利用时间,还有利于旅游者有计划地支配旅游费用等等。而设计合理的旅游线路技术性和经验性都非常的强,大多数旅游者出游过程中都希望在感觉舒适和体力充沛的情况下,走较短的路程、花费较少费用和较短时间来游览更多的旅游景区。因此设计合理的旅游线路不管是对旅游组织者还是旅游者都显得尤为重要。本文根据旅游企业、旅游者面临的具体问题,利用图论和运筹学方法,建立数学模型研究旅游线路的优化设计,丰富了旅游线路优化设计的研究方法,展示了定量研究方法在旅游线路优化设计中的应用潜力。这种方法拓展了旅游线路研究的领域,为旅游企业、旅游者降低旅游成本和优化设计旅游线路提供了科学的方法。（1）附件1中对景区的最少游览时间是以“半天”为基本单位，可将“半天”理解为在8:00至18:00之间的“4个小时”，“一天”理解为在8:00至18:00之间的“8个小时”，“两天”理解为两个“一天”，一般需在景区住宿一个晚上以上。（2）景区到相邻城市的道路一般是专线公路，由部分高速公路和部分普通公路组成，为问题简化，模型解算时可参考附件1给出的相关景区到附近城市的路程和行车时间信息；（3）附件2给出了全国高速公路一览表，参赛队需注意的是目前不少线路并没有全线连通，在模型解算时若涉及到某条高速公路，只能考虑已连通的部分路段；可参考百度地图等公开信息。（4）附件3给出了省会城市之间公路里程，采用高速优先策略；也就是两城市之间若有高速公路全线相连则附件3给出的是这两城市之间的全程高速里程数据，若两城市之间不是全程高速相连，则附件3给出的这两城市之间的里程数据中包含有部分普通公路的信息。因此该附表仅供参赛队参考，在模型解算时需参阅相关资料确定相应线路中具体包含的高速公路里程和普通公路里程数据。（5）参赛队需使用附件中未给出的某两城市之间高速公路的路程信息时，鼓励参赛队查阅相关资料和文献，但需将相应的数据信息以附录形式放在论文后部。-2-（6）附件4给出了若干省会城市之间的高铁或动车二等座票价信息和运行时间，数据格式是“票价(单位：元)/运行时间（单位：分钟）”；不少城市间既有高铁也有动车，不同的车次的票价也略有差异，为简化问题，该附表给出了若干城市之间的票价信息，在数据的设计上主要以运行时间较短者优先，或者选择的车次对旅游出行较为有利。若参赛队在模型解算中还需其他相关城市之间高铁票价的信息，请查阅相关资料。（7）为使问题简化，乘坐高铁或飞机出行时间仍安排在每天7:00至19:00之间，虽然可能和实际情况有一定差异，高铁票或飞机票通过预定可以满足出行需求（8）附件5给出了若干省会城市之间的全价机票价格（单位：元）；一般来说，不少城市之间的往返机票价格会有一定的差异，为问题简化，在模型解算时可考虑任两城市之间的全价往返机票价格是一样的（例如：北京—昆明与昆明—北京的机票价格认为是一样的）；附件5中有的城市之间没有给出机票价格数据，要么是这两城市之间距离较近，要么是直达航班很少或没有直达航班。（9）附件8给出了主要的国家高速公路路线百度地图截图，供参赛队参考。（10）附件9给出了若干景区周边高速公路百度地图截图，供参赛队参考。2、问题（一）在行车线路的设计上采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。附件1给出了各景区到相邻城市的道路和行车时间参考信息，附件2给出了国家高速公路相关信息，附件3给出了若干省会城市之间高速公路路网相关信息。请设计合适的方法，建立数学模型，以该旅游爱好者的常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年？给出每一次旅游的具体行程（每一天的出发地、行车时间、行车里程、游览景区；若有必要，其他更详细表达请另列附件）。（二）随着各种旅游服务业的发展，出行方式还可以考虑乘坐高铁或飞机到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览（租车费用300元/天，油费和高速过路费另计，租车和还车需在同一城市）。此种出行方式可以节省一些路途时间用于景区游览或休闲娱乐，但这种出行方式也会给旅游者带来一些不便，有时费用也会增加。该旅游爱好者根据个人旅游偏好确定在每一个景区最长逗留时间不超过附件1给出的最少时间的2倍。附件4给出了若干城市之间的高铁票价和相关信息（约定：选择高铁出行要求当天乘坐高铁的时间不超过6个小时，乘坐高铁或飞机的当天至多安排半天的景区游览）；附件5给出了若干省会城市之间的机票全价价格信息（含机场建设费）。该旅游爱好者一家3人同行，综合考虑前述全程自驾、先乘坐高铁或飞机到达省会城市后再租车自驾到景区等出行方式（住宿费简化为省会城市和旅游景区200元/人•天，地级市150元/人•天，县城100元/人•天；高速公路的油耗加过路费平均为1.00元/公里，普通公路上油耗平均为0.60元/公里；附件1中给出了各景区所在地的信息，若景区位于某城市市区或近郊，则这类景区的市内交通费用已计入住宿费中，不再另计），建立数学模型设计一个十年游遍所有201个-3-5A景区、费用最优、旅游体验最好的旅游线路，给出每一次旅游的具体线路（含每次具体出行方式；每一天的出发地、费用、路途时间、游览景区、每个景区的游览时间）。（三）能否在第二问所建立的模型基础上加以推广，可以为全国的自驾游爱好者规划设计类似的旅游线路，进而给出常住地在北京市的自驾游爱好者的十年旅游计划；根据上述三问的结果给旅游爱好者和旅游有关部门提出建议。（四）自2007年3月7日至2015年7月13日，全国旅游景区质量等级评定委员会分29批共批准了201家景区为国家5A级旅游景区。附件6是从国家旅游局官网上收集的国家5A级旅游景区评定的相关信息，附件7给出了国家旅游局官网上收集的国家4A级景区名单，请更为合理地规划该旅游爱好者的十年旅游计划。二、问题分析随着科技的进步和社会的发展,旅游已成为人们的一种生活方式,是提高人们生活质量的重要活动。设计合理的旅游线路既有利于旅游者有目的的选择、安排自己的旅游活动,避免“漫游”,又有利于发挥各旅游点的功能以及旅游者合理利用时间,还有利于旅游者有计划地支配旅游费用等等。而设计合理的旅游线路技术性和经验性都非常的强,大多数旅游者出游过程中都希望在感觉舒适和体力充沛的情况下,走较短的路程、花费较少费用和较短时间来游览更多的旅游景区。因此设计合理的旅游线路不管是对旅游组织者还是旅游者都显得尤为重要。针对问题一，可以明显分析出其为TSP优化问题，因此建立了数学模型。通过附件3数据可求得省会之间的最短距离，并以省会城市为中心像省内所有5A级旅游景区辐射，并利用DIJKSTRA算法算出游完省内每个5A级景区的最短距离。运用LINGO编写程序进行模型求解，运用MATLAB编写程序。在旅游费用不限的情况下，设计出了畅游全国5A级景区的较佳旅游路线,并得出最短旅游年限针对问题二，假定以西安为中心，综合考虑飞机，高铁和自驾租车等交通方式，依据题中所给的各种费用和时间限定信息，设计出了每一天具体的出行方式、出发地、费用、路途时间、游览景区和每个景区的游览时间。针对问题三，在第二问的基础上，以北京市为中心，以自驾为主，费用最低为目标，处理数据及分析方法与第二问类似，进行旅游线路设计，规划出了更适合十年旅游计划的自驾游爱好者的旅游路线。针对问题四，根据5A级旅游景区的评定信息，结合周边的4A级景区，并根据其离散程度对全国进行分区，共分为7个区域，分别为华北地区，东北地区，华东地区，华中地区，华南地区，西北地区，西南地区。依据分区结果，更合理的安排旅游者的十年旅游计划。-4-三、问题假设1.本文所引用的数据均为真实有效的数据；2.在所设计的所有旅游方案中，到达旅游景点时天气均为晴朗，不影响出游；3.问题中不考虑城市间的公交线路拥堵等造成的特殊情况。四、符号表示,ijvv：第i个景点或第j个景点201,,2,1,ji；（分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、山西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳……）；c：旅行者的旅游总消费；s:旅行的总路程；ijs：第i个景点到第j个景点之间的最短距离；it：在第i个景点的逗留时间；ic：在第i个景点的总消费；ijt：旅游者从第i个景点到第j景点路途所需时间；ijc：旅游者从第i个景点到第j景点路途所需的交通费用；ijr：表示旅游者直接从第i个景点到第j景点；0表示其它；m：总的交通费用；t：旅行所花时间；p:每年出行总次数；pt：第p次出行所用时间；jt：在第j个景点的逗留时间-5-五、模型的建立与求解关于最短路的研究,目前已经具有很多算法,本文首先利用DIJKSTRA算法求得任意两景点之间的最短距离，运用LINGO编写程序进行模型求解，采用改良圈算法,运用MATLAB编写程序,设计出畅游全国的较佳旅游线路,求解结果具有合理性和实用性。5.1费用不限，时间最短Dijkstra算法及其改进设源点为0,目标点为0。DIJKSTRA算法的基本思想是:按到0的距离由近到远的顺序,依次求得0到G的所有顶点的最短距离,直到0,算法结束[1-3]。为了避免重复并保留每一步计算信息,采用了标号算法。算法的基本步骤如下：步骤1：令0)(0l，对于0，令)(vl,00S,0i；11{}iiiSSu步骤2：对每个(\)iiivSSVS，用min(),()()iuslvluwuv代替()lv，当，v不相邻时，