搜索
-1-参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛学校西南交通大学参赛队号10613005队员姓名1.丁恒2.吴胜3.杨艺-2-参赛密码（由组委会填写）第第十十二二届届““中中关关村村青青联联杯杯””全全国国研研究究生生数数学学建建模模竞竞赛赛题目旅游路线规划问题摘要：针对旅行计划优化问题，本文基于对旅行计划的时间窗以及次数限制地研究，设计了一种区计划——行程计划——年计划的三层旅行计划描述结构。通过这个描述结构，可以由区计划组建行程计划，进一步由行程计划组建年计划来优化旅行计划。在区计划层面，以浏览时间最短，费用最省为目标，规划各省份内的景点的浏览行程。并以区计划为基础，针对问题1~4的具体要求对201个5A景点的旅游计划进行了优化设计。对于问题一，借鉴二级装箱问题的思想，利用三层旅行计划描述结构，分析了行程计划与年计划的时间窗约束，并在此基础上建立了非线性整数优化模型。针对模型特点，采取分层求解策略，首先以缩减行程计划长度和使行程长度分布均匀为目标，对使用区计划组建行程计划这一过程进行优化；并在此基础上，利用装箱问题的思路对行程计划组建年计划进行优化，最终得到问题一结果为，从西安出发遍历所有5A景点的最少旅行年份数11年。对于问题二，本文首定义了旅行体验度，并结合旅行费用指标构造满意度指标为旅行体验值除以旅行费用，即单位金钱获得的体验度。并以满意度最优为综合目标，建立了非线性整数规划模型。并对此模型的求解采取分层规划的策略。首先以行程满意度最优，缩短行程计划长度以及使得行程计划长度分布均匀为目标，规划调整区计划对行程计划的构建过程，在得到初步的行程计划的基础上，设计了满意度损失最小调整算法，使得行程计划能够以最小的满意度损失，完成对年计划的构建。最终得到了10年旅行计划，其旅行总费用为298085元(考虑门票以及旅游消费)，总平均体验值为6.1314，满意度为0.5757/千元，旅行计划的具体路线详细安排见下文以及附录中。-3-对于问题三，得益于问题二中所建立模型的一般性，使得对旅游计划的优化不依赖于出发点的位置。对此采用与问题二同样的方法对问题三进行建模与求解，并得到从北京出发的10年旅行计划，其旅行的总费用为310440元，平均体验值为6.4357，满意度为0.5805/千元，旅行计划的具体路线详细安排见下文以及附录中。此外，通过对比从西安出发和从北京出发的旅行计划优化结果，本文给出以下建议：建议一：建议相近的景区可以在限定时间内尽量一次浏览完成；建议二：对于偏远地区的景区建议采用飞机等交通方式到达景区后再租车自驾游；建议三：对于距离较近的景区建议采用自己驾游方式在当地进行浏览；建议四：对于距离中等的景区，视预计逗留的天数决定是否自驾，如果预计逗留时间比较长，可以考虑自驾；如果预计逗留时间比较短，可以考虑采用高铁飞机的交通方式。对于问题四，针对满意度随实际旅游时间占总行程时间比例升高而升高的特征，设计了4A旅行景点补偿方案。所设计的4A补偿方案可以所有已经成型的旅游方案，在不破坏其原有计划结构的前提，对其满意度水平进行优化。通过对问题二结果的遍历搜索，将4A旅行景点补偿发难应用于武汉区行程计划和云南2区、贵州区的行程计划，将原本的自驾游出行方案改为飞机出行方案，并将采用飞机出行方案节省的时间全部用于对4A景区的浏览，使得这两次行程计划的分别提高了提高0.09/千元以及0.028/千元。关键字：三层旅游计划；二级装箱问题；分层规划；满意度最小建模；满意度补偿策略-4-1、问题重述1.1问题背景旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动。1.2问题提出附件1提供了国家旅游局公布的201个5A级景区名单，一位自驾游爱好者拟按此景区名单制定旅游计划。该旅游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天；基于个人旅游偏好确定了在每个5A级景区最少的游览时间（见附件1）。基于安全考虑，行车时间限定于每天7:00至19:00之间，每天开车时间不超过8小时；在每天的行程安排上，若安排全天游览则开车时间控制在3小时内，安排半天景点游览，开车时间控制在5小时内；在高速公路上的行车平均速度为90公里/小时，在普通公路上的行车平均速度为40公里/小时。该旅游爱好者计划在每一个省会城市至少停留24小时，以安排专门时间去游览城市特色建筑和体验当地风土人情（不安排景区浏览）。景区开放时间统一为8:00至18:00。1.3要解决的问题问题一：在行车线路的设计上采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。附件1给出了各景区到相邻城市的道路和行车时间参考信息，附件2给出了国家高速公路相关信息，附件3给出了若干省会城市之间高速公路路网相关信息。设计合适的方法，建立数学模型，以该旅游爱好者的常住地在西安市为例，规划设计旅游线路，试确定游遍201个5A级景区至少需要几年？给出每一次旅游的具体行程。问题二：随着各种旅游服务业的发展，出行方式还可以考虑乘坐高铁或飞机到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览（租车费用300元/天，油费和高速过路费另计，租车和还车需在同一城市）。此种出行方式可以节省一些路途时间用于景区游览或休闲娱乐，但这种出行方式也会给旅游者带来一些不便，有时费用也会增加。该旅游爱好者根据个人旅游偏好确定在每一个景区最长逗留时间不超过附件1给出的最少时间的2倍。附件4给出了若干城市之间的高铁票价和相关信息（约定：选择高铁出行要求当天乘坐高铁的时间不超过6个小时，乘坐高铁或飞机的当天至多安排半天的景区游览）；附件5给出了若干省会城市之间的机票全价价格信息（含机场建设费）。该旅游爱好者一家3人同行，综合考虑前述全程自驾、先乘坐高铁或飞机到达省会城市后再租车自驾到景区等出行方式（住宿费简化为省会城市和旅游景区200元/人•天，地级市150元/人•天，县城100元/人•天；高速公路的油耗加过路费平均为1.00元/公里，普通公路上油耗平均为0.60元/公里；附件1中给出了各景区所在地的信息，若景区位于某城市市区或近郊，则这类景区的市内交通费用已计入住宿费中，不再另计），建立数学模型设计一个十年游遍所有201个5A景区、费用最优、旅游体验最好的旅游线路，给出每一次旅游的具体线路（含每次具体出行方式；每一天的出发地、费用、路途时间、游览景区、每个景区的游览时间）。问题三：在第二问所建立的模型基础上加以推广，可以为全国的自驾游爱好者规划设计类似的旅游线路，进而给出常住地在北京市的自驾游爱好者的十年旅游计划；根据上述-5-三问的结果给旅游爱好者和旅游有关部门提出建议。问题四：自2007年3月7日至2015年7月13日，全国旅游景区质量等级评定委员会分29批共批准了201家景区为国家5A级旅游景区。附件6是从国家旅游局官网上收集的国家5A级旅游景区评定的相关信息，附件7给出了国家旅游局官网上收集的国家4A级景区名单，依据附件6、7请更为合理地规划该旅游爱好者的十年旅游计划。2、符号假设符号符号解释iX1iX表示第i年进行旅行游动，0iX表示第i年没有进行旅行游动ijY1ijY第i个年计划第j个行程计划被采用，0ijY表示没有被采用ijkZ1ijkZ表示第i个年计划第j个行程计划包含了第k个组计划，0ijkZ表示不包含ijM1ijM表示第i个年第j个行程计划采取自驾游，0ijM时表示乘坐飞机或高铁BijT第i个年的第j个行程计划所包含的区计划的总区内时间AijT第i个年的第j个行程计划从出发点到各个区计划的省会巡回所花费的时间kt第k个区计划的区内时间kv旅游者完成k区计划旅游后获得的体验价值ijV旅游者完成第i年第j次旅游获得的体验价值3、问题假设假设1：旅行者选择乘坐飞机或者动车高铁时，如果乘坐高铁或动车可以在6小时内到达目的地的行程一律乘坐高铁动车，否则都乘坐飞机；假设2：某次行程，不考虑由当地朋友借车自驾游之类的特殊情况；假设3：总是巡回遍历，旅游者在一次旅游中，由于省会之间的交通便利，在省会之间的周转的旅行过程中总是巡回遍历而不折返的；假设4：忽略旅行者对飞机、高铁、自驾交通方式偏好对旅行体验满意度的影响。旅行体验之与景点的浏览，以及游玩时间与总行程时间的比例有关。4、模型分析、建立与求解4.1旅行计划4.1.1景点分组问题1~4要求在不同条件下，完成旅游者对201个5A景点的浏览的行程规划。同时对201个景点的浏览顺序进行规划，并且完成对旅行者行车线路，住宿等具体行程的长期的安排是非常困难而且缺乏效率的。所以对201个5A景点进行分组，再对景点组合进行规划，是一种可取的策略。而具体的分组，需要综合考虑地理位置，旅行者每次出行的最长时间，交通状况，旅行者对旅行体验与费用等的期望综合考虑，根据不同的问题要求进行不同的分组。考虑到省份会之间交通相对便利，所以一个基本分组策略是按省份分区,具体的分组在处理实际问题时根据需求进一步调整；例如部分省份不可能一次浏览完成，乘坐飞机和自交游玩的情况也不相同，就需要进一步调整。-6-4.1.2三层旅行计划：区计划——行程计划——年计划在对旅游景点合理分组的基础上，本文对旅游计划进行三个层次的划分，依次为区计划、行程计划、年计划。通过对区计划、行程计划、年计划的逐层规划，完成对题目旅行者计划的设计。下图5.1展示了这种分层规划旅行计划的主要思路。图4.1区计划——行程计划——年计划下面对区计划、行程计划、年计划进行进一步的介绍(1)区计划区计划是最底层的旅游计划，指一个区域内景点内具体的旅游行程进行安排，包括对区内景点的浏览顺序，交通方式，住宿地点等相关细节。我们依据省份对旅游景点分组，那么每个区计划的行程都有且包含一个省会城市，旅游者从出发点到达该区计划的省会城市后开始对该区计划内的景点进行浏览，并在完成本区计划浏览后由省会城市离开。主要从三个方面描述一个区计划，具体如下：区内行程R：旅游者到达该省区的省会城市后，从省会出发，完成浏览计划并返回省会的具体行程安排，包括行车路线，浏览时间，住宿地点等所有相关细节。区内时间t:旅游者到达该省区的省会城市开始，直到完成浏览计划并由省会城市在该省区的停留时间，不包括到达和离开的路途时间。区内费用c:旅游者到达该省区的省会城市开始，直到完成该组景点浏览并由省会城市离开的除了租车以外的所有费用，同样不包括到达和离开的路途费用。对于区内行程R，需要规划从区内的省会出发遍历所有景点会到省会城市的内容，主要需要考虑如下三个方面经济：尽量节省完成该组景点浏览的费用；省时：尽量节省完成该组景点浏览的时间；合理：符合题设要求的浏览时间，行车时间等相关条件；-7-本文以区内浏览时间t最小为主要目标，根据区内景点所在地里区域实际道路状况，结合Tsp规划，Kruskal最小生成树，最小路算法等图论方法规划区内行程R；考虑相关时间与路线约束，并依据实际情况和个人经验对行调整，并最终给出了31个省份内的景点的行程进行了规划，设计了关于31个省份的34个区计划的。例如：一个浙江省区计划的区内行程R浙江如下表：表4.1浙江省区计划的区内行程R浙江天数时间出发地游玩景点达到地行车时间行程里程第一天8：00-12：00杭州ZJ1/半天ZJ112：00-16：00ZJ9/半天16：00-18：00ZJ9ZJ5（住宿）2h87km第二天8：00-12：00ZJ5/半天12：00-13：00ZJ5ZJ81h40km13：00-17：00ZJ8/半天ZJ8（住宿）第三天7：00-8：00ZJ8ZJ121h45km8：00-12：00ZJ12/半天12：00-14：00ZJ12ZJ102h138km14：00-18：00ZJ10/半天ZJ10（住宿）第四天