旅游线路的优化设计

2011年第八届苏北数学建模联赛承 诺 书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为： 参赛组别（研究生或本科或专科）：本科参赛队员 (签名) ：队员1：队员2：队员3：获奖证书邮寄地址：2011年第八届苏北数学建模联赛编 号 专 用 页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：2011年第八届苏北数学建模联赛题 目 旅游线路的优化设计摘要本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。第一问放松时间约束，要求游客游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。使用lingo编程得到最佳旅游路线为：徐州常州舟山黄山庐山武汉黄鹤楼龙门石窟秦兵马俑祁县乔家大院八达岭长城青岛崂山徐州。第二问给定时间约束，要求设计合适的旅游路线。我们建立了一个最优规划模型，在给定游览景点个数的情况下以总费用不限，时间最少为目标。再引入01变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：徐州恐龙园舟山黄山庐山黄鹤楼秦兵马俑龙门石窟乔家大院八达岭长城青岛崂山徐州。第三问放松时间约束，要求游客在总费用低于2000元的约束下游览最多的景点。在第一问的基础上建立模型，并增加总费用低于2000元的约束。使用lingo编程得到最佳旅行路线为：徐州常州武汉洛阳西安祁县北京青岛徐州。第四问给定时间约束，放松对总费用的约束。我们在第二问的基础上建立一个最优化模型，以时间最少为目标。再引入01变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：徐州-常州-九江-武汉-洛阳-西安-祁县-北京-徐州。第五问给定时间、总费用小于2000的双重约束。我们在第三问、第四问的基础上建立模型，以在规定时间内，规定总费用内，以游览最多景点为目标。使用lingo编程对模型求解。推荐方案：徐州-常州-舟山-黄山-九江-武汉-洛阳-西安-徐州关键词：最佳路线 TCP问题 景点个数 最小费用2019整理的各行业企管，经济，房产，策划，方案等工作范文，希望你用得上，不足之处请指正目 录1 问题重述12 问题分析22.1 问题背景的理解22.2 问题一和问题二的分析22.3 问题三和问题四的分析22.4 问题五的分析23 模型假设24 符号说明35 模型建立及求解35.1 问题一模型的建立及求解35.2 问题二模型的建立和求解55.3 问题三模型的建立及求解75.4 问题四模型的建立及求解85.5 问题五模型的建立及求解106 模型的评价改进及推广106.1模型的评价106.2模型的改进与推广：117 参考文献118 附录118.1 各旅游景点可能的住宿地及到达方式（起点为火车站或住宿地）118.2 本模型计算时用到的部分lingo代码121 问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。表1. 预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时假设：(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。2 问题分析2.1 问题背景的理解根据对题目的理解我们可以知道，旅游的总费用包括交通费用和在景点游览时的费用及可能的住宿费用，在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。2.2 问题一和问题二的分析问题一要求我们为该旅游爱好者设计合适的旅游路线，使他在无限制的时间内花最少的钱游览所有十个景点，并返回出发地徐州。在这里我们的做法是满足相应的约束条件，计算出在这种情况下的最小花费。问题二实质上是在问题一的基础上把目标函数由费用函数变为时间函数，计算出在无限制费用时用时最少的游览方案，我们完全可以使用与问题一同样的方法进行求解。2.3 问题三和问题四的分析问题三要求我们设计的方案使该旅游爱好者在有限的费用（即2000元）和无限制的时间内尽可能多的游览景点。这里与问题一的解法相似，我们的做法是满足相应的约束条件（即费用约束等）确定出游览的景点数，这样最终会得出几种最佳方案，而该爱好者可以根据自己的实际情况进行选择。问题四要求我们的方案可以使该旅行者能在有限的时间内（即5天）游览尽可能多的景点，我们的做法是，把游览的景点数作为目标函数、满足题目已给的各种约束条件规划求解确定相应的景点数。同样，我们依然可以得到几种最佳方案，该旅游者可以根据自己的需要选择路线。2.4 问题五的分析问题五可以看作是问题三和问题四的综合，在问题三、四的基础上，我们同样的，先把问题五的约束条件、目标函数确定，由此计算出可游览的最大景点数，然后我们可以得到几个最佳方案都满足约束条件，旅游者可以自行选择自己心仪的旅游路线。3 模型假设1 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。2 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。3 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。4 假设景点的开放时间为8:00至18:00。5 我们所查到的相关数据(旅馆住宿费用，市内交通费用等)都是已确定且最低的的，市内的交通出行线路也是已经确定不变了的。6从景点到交通站点的时间忽略不计，且从市内到景点的时间忽略不计。4 符号说明,第个或者第个景点， ，=0，1，2，9，10；分别表示徐州、常州恐龙园、青岛崂山、八达岭长城、祁县乔家大院、洛阳市龙门石窟、黄山市黄山、武汉市黄鹤楼、西安市秦始皇兵马俑、九江市庐山、舟山市普陀山。该旅游爱好者的旅游总花费；该旅游者第个景点的逗留时间；该旅游者在个景点的总消费；从第个景点到第个景点路途中所需时间；从第个景点到第个景点所需的交通费用； 5 模型建立及求解5.1 问题一模型的建立及求解5.1.1目标函数的确立：该问中要求旅行者完成所有景点的参观和旅行，并且对时间没有任何限制，而目标函数是求最少的旅行费用。通过分析可得交通费用为：因此，该问题的目标函数为：5.1.2 约束条件：时间约束该问对时间没有要求和限制，所以不妨假定限制的时间为一个月（360个小时），同上一问可得：+360旅游景点数约束由题目要求可知，因为时间充裕，因此旅行者打算游览完全部10个景点。通过分析知道，表示代表们游览的景点总数，因此该约束为： (，=1，2，10)5.1.3模型建立综上所述，我们可以得到总的模型为：约束条件：+360 （，=0，1，10）5.1.4模型求解与结果分析：根据模型，使用Lingo编程，得出结果为：旅游景点数n10总花费（单位：元）3181元路线徐州常州舟山黄山庐山武汉黄鹤楼龙门石窟秦兵马俑祁县乔家大院八达岭长城青岛崂山徐州具体线路方案如下： 项目日数时间安排D18:1513:43乘坐K1905次列车从徐州到常州13:4317:43游览中华恐龙园20:02次日01:57乘坐K8418次列车从常州到宣城D24:1410:09乘坐K8387次列车从宣城到宁波10:0916:00游览普陀山16:39次日1:49乘坐K76次列车从宁波到南京D35:3214:30乘坐7101次列车从南京到黄山14:3020:00游览黄山20:008:00住宿D48:009:30继续游览黄山20:564:09 9:5612:50乘坐2239次列车从黄山到东乡，再乘K398次列车从东乡到九江12:5519:55游览庐山22:00次日2:00乘汽车到达武汉D58:0010:00游览武汉黄鹤楼16:4501:16乘K624次列车到达洛阳8:0011:00游览龙门石窟11:0116:05乘K1130次列车从洛阳到西安16:0518:05游览秦兵马俑20:52次日6:19乘2670次列车从西安到祁县D68:0011:00游览乔家大院13:334:00乘2604次列车从祁县到北京8:0011:00游览八达岭长城22:487:38乘T25次列车从北京到青岛D78:0015:00游览青岛崂山15:160:33乘坐1112次列车从青岛到徐州5.2 问题二模型的建立和求解5.2.1 目标函数的确立经过对题目分析，我们可以知道本题所要实现的目标是，旅行者在最少的时间内花不加限制的钱游览所有景点。显然，时间最少是该问题的目标。因此，我们的做法是满足相应的约束条件，计算出在这种情况下的最小时间。游览的时间有两部分组成，分别是每个景点的最短游览时间和景点到景点之间的交通时间（特别注意题目中要求的住宿时间和游览时间的限制）从而得到目标函数： Min t （1）交通总时间因为表示从第个景点到第个景点所需的交通费用，而是判断旅游者是否从第个景点直接到第个景点的01变量，因此我们可以很容易的得到交通总时间为：（2）旅游景点的时间因为所经过景点的数目和名称为已知条件，且题目中已经给出旅游者在每一处景点的最短游览时间，所以旅游景点的时间是一个定值，为43h。从而我们可以得到目标函数为：Min +435.2.2模型建立综上所述，我们可以得到总的模型为：Min +43约束条件：+43 （，=0，1，10）5.2.3 模型求解与结果分析通过上网查询资料，我们得到该旅行者在第个景点的最佳逗留时间和他们在第个景点总消费：t1t2t3t4t5t6t7t8t9t104h6h3h3h3h7h2h2h7h6h根据模型，使用Lingo编程，得出结果为：旅游景点数n10总时间/h151.0h路线徐州恐龙园舟山黄山庐山黄鹤楼秦兵马俑龙门石窟乔家大院八达岭长城青岛崂山徐州具体的线路方案如下： 项目日数时间安排D19:3515:19乘坐k58/k55次列车从徐州到常州15:1919:19游览中华恐龙园22:30次日05:19乘坐D5589次列车从常州到宁波D28:0014:00游览普陀山15:0920:44乘列车从宁波到南京22:10次日5:07乘列车从南京到黄山D38:0015:00游览黄山16:0020:04乘汽车前往九江市（住宿）D48:0015:00游览庐山17:5819:49乘汽车前往武汉市（住宿）D58:0010:00游览武汉黄鹤楼14:4015:55乘MU2547航班从武汉飞往西安15:5517:55游览秦始皇兵马俑18:3223:06乘T232次列车从西安到洛阳（住宿）D68:0011:00游览龙门石窟12:0016:00乘汽车到祁达县乔家堡乔家大院16:0019:00游览乔家大院22:05次日10:23乘1164次列车从祁县到北京D710:3013:30游览长城13:4515:05乘CA1575次航班从北京到青岛15:3020:00开始游览青岛崂山20:00次日8:00在青岛崂山住宿D88:0010:00继续游览青岛崂山10:3016:00乘坐D75次列车从青岛到徐州5.3 问题三模型的建立及求解5.3.1目标函数的确立：该问中要求旅行者使用2000元以内的费用，在不限制时间的情况下尽可能多的游览景点，所以标函数是求最大的游览景点数。因此，该问题的目标函数为：Max 5.3.2 约束条件：时间约束该问对时间没有要求和限制，所以不妨假定限制的时间为一个月（360个小时），同上一问可得：+360旅游景点数约束由题目要求可知，因为时间充裕，因此旅行者打算游览完全部10个景点。通过分析知道，表示代表们游览的景点总数，因此该约束为： (，=0，1，11)5.3.3模型建立综上所述，我们可以得到总的模型为：Max 约束条件：+360 （，=0，1，10）5.3.4模型求解与结果分析：根据模型，使用Lingo编程，得出结果（具体行程安排）如下： 项目日数时间安排D18:1513:43乘坐K1905次列车从徐州到常州13:4317:43游览中华恐龙园18:102:10K1512到武汉D28:0010:00游览武汉黄鹤楼16:4501:16乘K624次列车到达洛阳D38:0011:00游览龙门石窟11:0116:05乘K1130次列车从洛阳到西安16:0518:05游览秦兵马俑20:52次日6:19乘2670次列车从西安到祁县D48:0011:00游览乔家大院13:334:00乘2604次列车从祁县到北京D58:0011:00游览八达岭长城22:487:38乘T25次列车从北京到青岛D68:0015:00游览青岛崂山15:160:33乘坐1112次列车从青岛到徐州共花费1651元5.4 问题四模型的建立及求解5.4.1 目标函数的确立经过对题目分析，我们可以知道本题所要实现的目标是，旅行者在有限的五天时间内，费用不加限制，游览所有尽可能多的景点。显然，游览景点数最多是该问题的目标。因此，我们的做法是满足相应的约束条件，计算出在这种情况下最大的游览景点数。在此，我们引入n表示游览的景点数，有题目分析可以知道，n受到时间的影响，而游览的时间有两部分组成，分别是每个景点的最短游览时间和景点到景点之间的交通时间（特别注意题目中要求的住宿时间和游览时间的限制）（1）交通总时间因为表示从第个景点到第个景点所需的交通费用，而是判断旅游者是否从第个景点直接到第个景点的01变量，因此我们可以很容易的得到交通总时间为：（2）旅游景点的时间因为在此处游览的景点不确定，数目未知，且恰为目标函数，所以，Min +（3）01变量约束我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束： （，=0，1，11）当时，因为成都是出发点，所以；时，因为旅行者最终要回到徐州，所以。综合以上可知， （，=1，2，11） 同样，当，时，根据题意不可能出现，即不可能出现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束： （，=1，2，11）5.4.2模型建立综上所述，我们可以得到总的模型为：Max 约束条件：+120 （，=0，1，11） （，=1，2，11）5.4.3模型的求解根据模型，使用lingo编程，得到答案，具体行程如下表：Day 18:1513:43乘坐K1905次列车从徐州到常州13:4317:43游览中华恐龙园21:274:25乘K25常州到向塘Day 25:197:181506向塘到九江7:1814:18游览庐山16:20乘汽车九江到武汉Day 38:0010:00游览武汉黄鹤楼16:4501:16乘K624次列车到达洛阳Day 48:0011:00游览龙门石窟11:0116:05乘K1130次列车从洛阳到西安16:0518:05游览秦兵马俑20:52次日6:19乘2670次列车从西安到祁县Day 58:0011:00游览乔家大院13:334:00乘2604次列车从祁县到北京8:0011:00游览八达岭长城11:0516:43乘D31北京到徐州5.5 问题五模型的建立及求解基于问题三和问题四的模型，我们建立了问题五的模型，模型的目标依旧是游览景点的最大值，但是模型的约束条件是三、四两问的有机节和，所以问题五的模型约束条件需要同时满足三、四两问的约束条件。通过lingo编程，我们得出最后结果，具体行程安排如下： 项目日数时间安排D18:1513:43乘坐K1905次列车从徐州到常州13:4317:43游览中华恐龙园20:02次日01:57乘坐K8418次列车从常州到宣城D24:1410:09乘坐K8387次列车从宣城到宁波10:0916:00游览普陀山16:39次日1:49乘坐K76次列车从宁波到南京D35:3214:30乘坐7101次列车从南京到黄山14:3020:00游览黄山20:008:00住宿D48:009:30继续游览黄山20:564:09 9:5612:50乘坐2239次列车从黄山到东乡，再乘K398次列车从东乡到九江12:5519:55游览庐山22:00次日2:00乘汽车到达武汉D58:0010:00游览武汉黄鹤楼16:4501:16乘K624次列车到达洛阳8:0011:00游览龙门石窟11:0116:05乘K1130次列车从洛阳到西安16:0518:05游览秦兵马俑18:456:40乘1148次列车从西安返回徐州6 模型的评价改进及推广6.1模型的评价1.本文思路清晰，模型恰当，得出的方案合理；2.本文成功的使用了01变量，使模型的建立和编程得以顺利进行；3.在第二问中采用了TCP算法，简化了模型的求解难度；4.该模型有许多实际因素没有考虑在内，比如旅行者的年龄、健康状况等，若考虑后模型将更加精确完整。6.2模型的改进与推广：1. 实际情况中，两景点之间可能通过其他交通方式连接，每一个景点的游览时间、市内交通（公交、计程车和地铁）的到达时间、等待时间、旅行者步行时间和天气因素都未考虑在内，考虑之后模型将更加精确、详细。2.因数据资料搜集的不完整，准确性也有待商榷，而且没有对最终方案进行更为细致的讨论研究，这些方面有待改进。7 参考文献1姜启源 谢金星 叶俊，数学模型（第三版），北京：高等教育出版社，2003。2谢金星 薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005。8 附录8.1 各旅游景点可能的住宿地及到达方式（起点为火车站或住宿地）表一 恐龙园、崂山、八达岭长城、乔家大院、龙门石窟 景点名称相关数据常州市中华恐龙园青岛市崂山风景区八达岭长城祁县乔家大院洛阳市龙门石窟可到达公交线路29（火车站至恐龙园）公交301或304路到西姜站地铁2号线(外/内)德胜门下车，919路公交汽车直达八达岭长城步行81路到龙门石窟下可住宿旅馆常州吾家吾庭商旅酒店青岛晨旭商务宾馆北京城市青年酒店晋中平遥天禄客栈中州快捷洛阳金谷园店表二 黄山、黄鹤楼、兵马俑、庐山、普陀山 景点名称相关数据黄山市黄山风景区武汉市黄鹤楼西安市秦兵马俑九江市庐山风景区舟山市普陀山风景区可到达公交线路黄山风景区班车“屯溪-太平”542路914路到秦始皇兵马俑博物馆101路公交车（1）到长途汽车站 转车去庐山打车到半升洞码头，做船到达普陀山可住宿旅馆黄山国际青年旅馆武汉万国宾馆西安铁路饭店格林豪泰九江火车站店百时快捷宁波火车站店表三（1） 各景点、城市花费一览 景点名称相关数据常州市中华恐龙园青岛市崂山风景区八达岭长城祁县乔家大院洛阳市龙门石窟门票票价160904540120交通费11301可能的住宿费19012815088135其他费用6060606060表三（2）各景点、城市花费一览 景点名称相关