基于粒化思想的多层次目标规划模型的研究旅游路线规划问题求解

-1-参赛密码（由组委会填写）全全第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校安徽大学参赛队号10357003队员姓名1.马闯2.程兵兵3.何玉清-2-参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目基于粒化思想的多层次目标规划模型的研究——旅游路线规划问题求解摘要：随着科技的进步和社会的发展，旅游已经成为人们的一种生活方式，是提高人们生活质量的重要活动。旅游路线最优化问题一直是旅游者们所关注的一个焦点。所以，如何对旅游路线进行合理的优化使得费用最低、使得如何花费最短时间游玩最多的景区、使得每次游玩体会最好，这都是我们需要量化、解决的问题。针对问题一，首先利用人工智能领域粒化的思想对数据进行处理，把景区按照所属市粒化成市区粒，粒化后从201个景区得到132个市区，计算每个市区的游玩总时间。接着，为了求解从西安出发自驾游遍所有景区花费年数最少的游玩线路，可以分两步进行求解。第一步建立游玩次数最小的最优化模型，应用粒子群优化遗传（PSO-GA）算法求出每次游玩路线，和所花费时间。第二步建立游玩年数最小模型，给出每条游玩路线在哪一年进行游玩并计算出最少游玩时间为：12.5年。针对问题二，在本问中旅游策略为先从西安乘坐交通工具到景区最近的省会城市，然后租车游玩。所以在第一问把景区粒化成市区的基础上，继续按照最近原则把市区粒化成省会粒。由高层次粒度建模，不考虑低层次粒度的思想，分别对旅游体验度最优、旅途费用最优和住宿费用最优分别在省会粒、市区粒、景区粒（景区本身）三个层次建立最优化模型。（1）在省会粒：根据体会最佳建立最优化模型求解每个省会的最佳游玩次数。（2）在市区粒：根据旅途车费（租车费、过路费、油费）和旅途住宿费最少建立最优化模型求得市区粒层次-3-上的最优游玩路线。（3）在景区粒上：根据住宿费最少建立最优化模型求得每个市区内部景点的游玩次序。综合三个层次求得了详细的旅行路线，并计算总共花费为230505元。针对问题三，本问中考虑是自驾游，从北京出发。在这里依然在三个粒度层次上分别建立最优化模型，模型只需要对问题二省会粒度和市区粒度上进行微小改变，求得详细路线。最后分析给出了当地政府应该有目的性的提高本地一些景区的综合评价指标，以带动周围景区的参观人数等建议。针对问题四，首先计算各个景区的评价指标，然后综合考虑旅游体验度、门票费、路费和游玩景区数目等各种指标分别建立自驾游、和非自驾游两种最优化模型以满足不同偏好的游客。最后，发现本文建立的基于粒化多层次优化模型在求解各种不同种类问题时，只需要在某个粒度层次上进行微调，而不涉及到整体模型改变。模型可移植性强，求解过程层次分明，结果合理可行。关键词：旅游路线；粒化；最优化；遗传算法；层次-4-一、问题重述旅游路线最优化问题一直是旅游者们所关注的一个社会焦点，因为近几年来随着城市的发展，人们生活物质水平的提高，外出旅游已经成为节假日必不可少的部分。因此，如何对旅游路线进行合理的优化越来越被人所重视，提供给顾客最优化旅游路线对国内外游客有莫大的帮助，这样越来越多的人会在节日期间在我国旅游，这无疑对我国旅游业的发展起着至关重要的作用。下面我们从四个问题对本文进行分析。(1)旅行者在行车线路的设计上采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。请设计合适的方法，建立数学模型，以该旅游爱好者的常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年？给出每一次旅游的具体行程，具体包括每一天的出发地、行车时间、行车里程和游览景区。(2)出行方式不仅可以采用高速优先策略，还可以考虑乘坐高铁或飞机到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览。该旅游爱好者一家3人同行，综合考虑第一问的全程自驾、先乘坐高铁或飞机到达省会城市后再租车自驾到景区等出行方式，建立数学模型设计一个十年游遍所有201个5A景区、费用最优、旅游体验最好的旅游线路，给出每一次旅游的具体线路，具体包括每次出行方式、每一天的出发地、费用、路途时间、游览景区和每个景区的游览时间。(3)在第二问所建立的模型基础上加以推广，为全国的自驾游爱好者规划设计类似的旅游线路，进而给出常住地在北京市的自驾游爱好者的十年旅游计划，并根据上述三问的结果给旅游爱好者和旅游有关部门提出建议。(4)根据201家景区为国家5A级旅游景区及附件6上关于国家5A级旅游景区评定的相关信息和附件7中国家旅游局官网上收集的国家4A级景区名单，请更为合理地规划该旅游爱好者的十年旅游计划。二、问题分析针对问题一：本问中，我们采用自驾游，高速优先策略，每次从西安出发。要求如何设计旅途路线，使得在最少的年数游完201个景区。在这里我们首先建立最优化模型使得游玩次数最优，然后针对每一次游玩天数建立花费年数最少模型。针对问题二：本问中，我们首先考虑乘坐飞机或高铁到达景区最近的省会城市，然后租车去景区，每次从西安出发。要求设计旅途线路，使得体会最优、花费最少十年游玩201个景区。在这里我们分别对旅游体验度最优、旅途费用最优和住宿费用最优分别在省会粒、市区粒、景区三个层次建立最优化模型。针对问题三：本问中，我们采用自驾游，每次从北京出发。要求设计使得体会最优、花费最少的最佳旅游路线。在这里我们分别对旅游体验度最优、旅途费用最优和住宿费用最优分别在省会粒、市区粒、景区三个层次建立最优化模型。针对问题四：本文中，添加4A景区，设计十年旅游线路使得旅途体验最优，花费最少。在这里，我们分别建立自驾游和非自驾游两种目标规划模型，以满足不同游客的需求。-5-三、符号说明与模型假设3.1符号说明表1.主要符号说明符号符号说明ijt第i个地点到第j个地点所需要的时间（小时）jtjt为游玩第j个景区所需要的时间（小时）iD第i个市区粒所花费时间（天）V表示所有景区或市区集合gijS第i地点到第j地点高速公路距离pijS第i地点到第j地点普通公路距离gv高速公路行驶速度pv普通公路行驶速度ijxijx表示我们是否从第i地点到第j个地点iT第i市区游玩时间fT景区的满意度minzPCD在第z个省会的最短时间minzPCD在第z个省会的最长时间iC第i个景区的体会得分zPCN第z个省会分配的游玩次数ozD目标城市o到省会城市z的旅途时间（天）gP高速公路上每公里油费0gP高速公路上每公里过路费pP普通公路上每公里油费3hP县城内住宿费-6-3.2基本假设：1每天旅行天气良好，城市之间交通顺畅。2可以随时顺利订到车票和机票。3行车线路的设计上采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。4市区内部景区游览过程为每次游玩后都返回市区再到其他景区（考虑交通便利）。5.乘坐高铁或飞机的当天至多安排半天的景区游览。6.西安（北京）到达每个省会城市都是全程高速公路。四、问题一的模型建立与求解：4.1数据处理由于附件所给数据有缺失，例如，各个城市之间的高铁、飞机信息不完整，景区门票价格缺失等，因此并不能直接使用附件中的数据，需要参考官方网站（如12306等）补全数据。粒计算[1-3]是人工智能领域中的一种新理念和新方法，覆盖了所有和粒度相关的理论、方法和技术，主要用于对不确定、不精确、不完整信息的处理，以及对大规模海量数据的挖掘和对复杂问题的求解，可以找到对问题的近似解决方案，实现问题的简化，降低求解代价。其主要的实现方法就是选择合适的粒化准则对问题进行粒化，实现不同粒度层次间的变换，在变换后的粒度层次对问题进行求解，最终使原本无解或者难以求解的问题得到解决。我们需要计算游遍201个经景点的最小年数，这里面存在大量数据，属于大规模数据的挖掘与处理问题，所以我们可以采用粒计算的思想，先把每个景点按每个市进行粒化，计算在该市游览需要的天数，粒化过程如图1。图1左边图A、B、C三个城市及其周边景区粒化成右边A、B、C三个市区粒化的过程需要计算两个问题：（1）小景区粒化成市区后市区到各个景点所花费时间（天）；（2）小景区粒化成市区后各个景点所花费时间（天）。假设ijt为粒化后第i个市区到第j个景区所需要的时间（小时），jt为游玩第j个景区所需要的时间。由于每个市区内的各个景区存在相互之间交通不便利的情况，所以我们假设在这个市区内游览每个景点后要返回市区，然后由市-7-区出发游览其他景区。考虑到，每天开车时间不超过8小时。在每天的行程安排上，若安排全天游览则开车时间控制在3小时内，即如果开车时间多于3小时，我们就至少浪费半天在旅途中；安排半天景点游览，开车时间控制在5小时内，即如果开车时间多于5小时，我们就至少浪费1天在旅途中；如果开车时间少于3小时，我们可以忽略不计，因为每天都存在7:00—8:00，18:00—19:00开车时间，8:00—18:00也可以抽出2个小时用来开车。所以旅途中需要的时间（天）我们可以计算得到：0,30.5,35()1,58(%8),88ttdtttdtt（1）其中8t为取整，%8t为取余。例如假设旅途中需要13个小时，我们需要先用8个小时开车（1天），再用5个小时开车（1天），即需要两天，13(13)(13%8)1(5)1128ddd。所以粒化后在该市内所需要时间为：路途时间，景区时间和是否为省会时间（在省会玩一天）。假设该市有k个景区，在第i个市区所花费时间为：112()()kkijijjjDtdti）（2）其中：0()1iii，为省会城市，为不是省会城市（3）每个市区的游玩时间可以计算出来如表2，市区间高速公路距离见附录‘市-市.xlsx’。表2为需要合并的市区游玩时间城市景区（按附件1给出顺序排列）游玩天数北京市1,2,3,4,5,6,74.5天津市8,92.5保定市12,132晋中市18,19,201.5鄂尔多斯市21,221.5大连市24,251长春市28,29,302.5上海市36,37,383苏州市39.40,44,50,53,544南京市41,452-8-无锡市42,43,521.5常州市46,551.5镇江市51,562杭州市58,61,663嘉兴市62,651黄山市70,73,772.5宁德市82,842上饶市88,902烟台市94,981洛阳市103,106,109,1103.5武汉市112,119,1212.5宜昌市113,114,118,1202.5恩施市116,1222长沙市127,1282广州市130,1322.5深圳市131,1341佛山市137,1391桂林市140,141,1422.5三亚市144,145,146,147,1482.5重庆市149,150,151,152,153,1549成都市155,157,159,1616.5乐山市156,1581.5安顺市165,1661丽江市170,1711.5拉萨市175,1762西安市177,178,1802.5银川市189,1902西宁市191,1922.54.2最优化模型建立[4-6]为了计算最少花费年数，在这里我们分两步求解：（1）建立游玩次数最小模型，给出每次游玩路线次数；（2）建立游玩年数最小模型，给出每次游玩在哪一年游玩。4.21建立游玩次数最小模型我们希望从西安出发游玩所有景区的时间最短（因为要回来，所以我们需要计算出一个环），因为每年最多可以游玩4次，每次时间不超过15天，我们假设总共游玩M次，则目标函数为：minM。现在我们假设第(1)mmM次游玩mV城市集（景区粒化成城市），V为所有景区城市集合。则我们有约束条件（1）我们要游玩所有城市（2）每个城市只能游玩一遍（3）每次游玩不为空：-9-1MmmVV（4）1MmmV（5）(1)mVmM（6）假设gijS为第i市区到第j市区高速公路距离（数据见附录‘市-市.xlsx’），gv为高速公路行驶速度；pijS为第i