旅游线路的优化设计

1、2011年第八届苏北数学建模联赛承诺书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本 队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们 愿意承担由此引起的一切后果。我们的参赛报名号为：参赛组别（研究生或本科或专科）：本科参赛队员（签名）：队员1：队员

2、2:队员3:获奖证书邮寄地址:2011年第八届苏北数学建模联赛编号专用页参赛队伍的参赛号码：（请各个参赛队提前填写好）：竞赛统一编号（由竞赛组委会送至评委团前编号）：竞赛评阅编号（由竞赛评委团评阅前进行编号）：2011年第八届苏北数学建模联赛题目旅游线路的优化设计摘要本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多 的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。第一问放松时间约束，要求游客游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。使用lingo编程得到最佳旅游路线为：徐州一常州一舟山一黄山一庐山一武汉黄鹤楼一龙

3、门石窟一秦兵马俑一祁县乔家大院一八达岭长城一青岛崂山一徐州。第二问给定时间约束，要求设计合适的旅游路线。我们建立了一个最优规划模型，在给定游览景点个数的情况下以总费用不限，时间最少为目标。再引入01变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用 lingo编程对模型求解。推荐方案：徐州一恐 龙园一舟山一黄山一庐山一黄鹤楼一秦兵马俑一龙门石窟一乔家大院一八达岭长城一青岛崂山一徐州。第三问放松时间约束，要求游客在总费用低于2000元的约束下游览最多的景点。在第一问的基础上建立模型，并增加总费用低于2000元的约束。使用lingo编程得到最佳旅行路线为：徐

4、州一常州一武汉一洛阳一西安一祁县一北京一青岛一徐州。第四问给定时间约束，放松对总费用的约束。我们在第二问的基础上建立一个最优化模型，以时间 最少为目标。再引入 01变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给 出相应的约束条件，使用 lingo编程对模型求解。推荐方案：徐州-常州-九?T -武汉-洛阳-西安-祁县-北京-徐州。第五问给定时间、总费用小于2000的双重约束。我们在第三问、第四问的基础上建立模型，以在规定时间内，规定总费用内，以游览最多景点为目标。使用lingo编程对模型求解。推荐方案：徐州-常州-舟山-黄山-九?工-武汉-洛阳-西安-徐州关键词：最佳路线

5、TCP问题景点个数最小费用1问题重述12问题分析12.1 问题背景的理解12.2 问题一和问题二的分析 12.3 问题三和问题四的分析 22.4 问题五的分析23模型假设24符号说明25模型建立及求解25.1 问题一模型的建立及求解25.2 问题二模型的建立和求解 45.3 问题三模型的建立及求解 55.4 问题四模型的建立及求解 65.5 问题五模型的建立及求解 86模型的评价改进及推广96.1. 模型的评价96.2. 模型的改进与推广： 97参考文献98附录98.1 各旅游景点可能的住宿地及到达方式（起点为火车站或住宿地）98.2 本模型计算时用到的部分lingo代码 101问题重述随着人

6、们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。表1,预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山帝普陀山6小时假设：(A)城际交通出行可以乘火车 (含高铁卜长途汽车或飞机(

7、不允许包车或包机)，并且车票或机票 可预订到。(B)市内交通出行可乘公交车 (含专线大巴、小巴 卜地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20: 00至次日早晨7: 00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时间为 8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的 交通信息(车次、航班号、起止时间、票价等 )、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览

8、完，至少需要多少旅游费用？请建立相关数学模型并设 计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设 计旅游行程表。(3)如果这位游客准备 2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行 程表。(4)如果这位游客只有 5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有 5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模 型并设计旅游行程表。2问题分析2.1 问题背景的理解根据对题目的理解我们可以知道，旅游的总费用包括交通费用和在景点游览时的费用及可能的住宿 费

9、用，在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本 的最小值。2.2 问题一和问题二的分析问题一要求我们为该旅游爱好者设计合适的旅游路线，使他在无限制的时间内花最少的钱游览所有 十个景点，并返回出发地徐州。在这里我们的做法是满足相应的约束条件，计算出在这种情况下的最小 花费。问题二实质上是在问题一的基础上把目标函数由费用函数变为时间函数，计算出在无限制费用时用 时最少的游览方案，我们完全可以使用与问题一同样的方法进行求解。2.3 问题三和问题四的分析问题三要求我们设计的方案使该旅游爱好者在有限的费用（即2000元）和无限制的时间内尽可能多的游览景点。这里与

10、问题一的解法相似，我们的做法是满足相应的约束条件（即费用约束等）确定出 游览的景点数，这样最终会得出几种最佳方案，而该爱好者可以根据自己的实际情况进行选择。问题四要求我们的方案可以使该旅行者能在有限的时间内（即5天）游览尽可能多的景点，我们的做法是，把游览的景点数作为目标函数、满足题目已给的各种约束条件规划求解确定相应的景点数。同 样，我们依然可以得到几种最佳方案，该旅游者可以根据自己的需要选择路线。2.4 问题五的分析问题五可以看作是问题三和问题四的综合，在问题三、四的基础上，我们同样的，先把问题五的约 束条件、目标函数确定，由此计算出可游览的最大景点数，然后我们可以得到几个最佳方案都满足约

11、束 条件，旅游者可以自行选择自己心仪的旅游路线。3模型假设1城际交通出行可以乘火车 （含高铁卜长途汽车或飞机（不允许包车或包机），并且车票或机票可 预订到。2市内交通出行可乘公交车 （含专线大巴、小巴 卜地铁或出租车。3旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20: 00至次日早晨7: 00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。4假设景点的开放时间为8:00至18:00。5我们所查到的相关数据 （旅馆住宿费用，市内交通费用等）都是已确定且最低的的，市内的交通出行线路也是已经确定不变了的。6从景点到交通站

12、点的时间忽略不计，且从市内到景点的时间忽略不计。4符号说明i,j 第i个或者第j个景点,i , j =0, 1, 2,9, 10;分别表示徐州、常州恐龙园、青岛崂山、八达岭长城、祁县乔家大院、洛阳市龙门石窟、黄山市黄 山、武汉市黄鹤楼、西安市秦始皇兵马俑、九江市庐山、舟山市普陀山。c该旅游爱好者的旅游总花费；tit lijcij该旅游者第i个景点的逗留时间；该旅游者在i个景点的总消费；从第i个景点到第j个景点路途中所需时间;i从第i个景点到第j个景点所需的交通费用;rij X；该旅游者直接从第i个景点到达第j个景点 其他5模型建立及求解5.1 问题一模型的建立及求解5.1.1 目标函数的确立：

13、该问中要求旅行者完成所有景点的参观和旅行，并且对时间没有任何限制，而目标函数是求最少的 旅行费用。通过分析可得交通费用为：1010因此，该问题的目标函数为:mCi 0 j 01010Minmriji 0 j 0cij5.1.2约束条件:时间约束该问对时间没有要求和限制，所以不妨假定限制的时间为一个月（101011010r t +r t t 360ij ijj ji 0 j 02 i 0 j 0旅游景点数约束360个小时），同上一问可得:由题目要求可知，因为时间充裕，因此旅行者打算游览完全部表示代表们游览的景点总数，因此该约束为：10 10rij10（ i, j =1, 2,i 1 j 15.1

14、.3模型建立综上所述，我们可以得到总的模型为：10 1010个景点。通过分析知道，归i 1 j 110）1010Mi%i 0 j 0约束条件：10110 10r.t + r t t1 ij ij1 ij i jj 12 i 1 j 110rij 10( i , j =0, 1,0 j 0360，10)n旅游景点数10总花费（单位：元）3181 元路线徐州一常州一舟山一黄山一庐山一武汉黄鹤楼一龙门石窟一秦兵马 俑一祁县乔家大院一八达岭长城一青岛崂山一徐州5.1.4模型求解与结果分析：根据模型，使用 Lingo编程，得出结果为:项目日数时间安排D18:1513:43乘坐K1905次列车从徐州到常州

15、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:099:5612:50乘坐2239次列车从黄山到东乡，再乘 K398次列车 从东乡到九江12:5519:55游览庐山22:00次日2:00乘汽车到达武汉D58:0010:00游览武汉黄鹤楼16:4501:16

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 目标函数的确立经过对题目分析，我们可以知道本题所要实现的目标是，旅行者在最少的时间内花不加限制的钱游 览所有景点。显然，时间最少是该问

17、题的目标。因此，我们的做法是满足相应的约束条件，计算出在这 种情况下的最小时间。游览的时间有两部分组成，分别是每个景点的最短游览时间和景点到景点之间的交通时间(特别注意题目中要求的住宿时间和游览时间的限制)从而得到目标函数：Min t =t1+t2(1)交通总时间因为I。表示从第i个景点到第j个景点所需的交通费用，而rj是判断旅游者是否从第i个景点直接到第j个景点的01变量，因此我们可以很容易的得到交通总时间为：1010t dr t1ij ij1 0 j 0(2)旅游景点的时间因为所经过景点的数目和名称为已知条件，且题目中已经给出旅游者在每一处景点的最短游览时间，所以旅游景点的时间是一个定值，

18、为 43ho从而我们可以得到目标函数为：Min t = t1 + t21010= L tj +43i 0 j 05.2.2模型建立综上所述，我们可以得到总的模型为：Min t = 11 + t 21010= j 品 +431 0 j 0约束条件：-1010 t j +43i 0 j 01010rij10(i , j =0, 1,，10)7 0 j 05.2.3模型求解与结果分析通过上网查询资料，我们得到该旅行者在第i个景点的最佳逗留时间和他们在第i个景点总消费:t1t2t3t4t5t6t7t8t9t104h6h3h3h3h7h2h2h7h6h根据模型，使用 Lingo编程，得出结果为:旅游景点

19、数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游览

20、武汉黄鹤楼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.

21、1 目标函数的确立：该问中要求旅行者使用2000元以内的费用，在不限制时间的情况下尽可能多的游览景点，所以标函数是求最大的游览景点数。因此，该问题的目标函数为：10 10Max n= "5.3.2 约束条件:360个小时），同上一问可得:时间约束 该问对时间没有要求和限制，所以不妨假定限制的时间为一个月（101011010r t +r t t 360lj ljljI ji 0 j 02 I 0 j 0旅游景点数约束由题目要求可知,因为时间充裕，因此旅行者打算游览完全部表示代表们游览的景点总数，因此该约束为:10 10rij 10i 1 j 1(I, j =0, 1,10 1010个景

22、点。通过分析知道，ji 1 j 111）5.3.3 模型建立 综上所述，我们可以得到总的模型为：10 10Max n=riji 1 i 1约束条件：10 101010360，10)二1r.t+ rtt1 ijlij o1 ijLi ji 1 j 12i 1 j 1f 10 10rij 10( i , j =0, 1,Q 0 j 05.3.4模型求解与结果分析：根据模型，使用 Lingo编程，得出结果（具体行程安排）如下:项目日数时间安排D18:1513:43乘坐K1905次列车从徐州到常州13:4317:43游览中华恐龙园18:102:10K1512到武汉D28:0010:00游览武汉黄鹤楼1

23、6: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 目标函数的确立经过对题目分析，我们可以知道本题所要实现的目标是，旅行者在有限的五天时间内，费用

24、不加限 制，游览所有尽可能多的景点。显然，游览景点数最多是该问题的目标。因此，我们的做法是满足相应 的约束条件，计算出在这种情况下最大的游览景点数。在此，我彳门引入 n表示游览的景点数，有题目分析可以知道，n受到时间的影响，而游览的时间有两部分组成，分别是每个景点的最短游览时间和景点到景点之间的交通时间(特别注意题目中要求的住 宿时间和游览时间的限制)(1)交通总时间因为tij表示从第i个景点到第j个景点所需的交通费用， 而rj是判断旅游者是否从第i个景点直接到 第j个景点的01变量，因此我们可以很容易的得到交通总时间为：1010tiStji 0 j 0(2)旅游景点的时间因为在此处游览的景点

25、不确定，数目未知，且恰为目标函数，所以，Min t = t1 + t210 10111 11=rijtij +rijti tji 0 j 02 i 1 j 1(3) 01变量约束我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最 多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：rjrj1( i , j =0, 1,，11)ij当i 1时，因为成都是出发点，所以rj1；i 1j 1时，因为旅行者最终要回到徐州，所以rjj 1综合以上可知，rj。1( i , j =1, 2,，11)ijrj 1。1i 1j 11,即不

26、可能出同样，当i , j 2时，根据题意不可能出现rj y现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束: % rji0( i , j =1, 2,11)5.4.2模型建立综上所述，我们可以得到总的模型为:Max n= i 1 i 1约束条件：11 111jtj：i 1 j 12rij。1ijrij1i 1jJur010 1011 11rijti tj 120i 1 j 111)(i , j =0, 1,，r 1 rj1i , j =1, 2,，11)5.4.3模型的求解根据模型，使用lingo编程，得到答案，具体行程如下表:8:1513:43乘坐K1905次

27、列车从徐州到常州Day 113:4317:43游览中华恐龙园21:274:25乘K25常州至I向塘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北

28、京到徐州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乘坐7

29、101次列车从南京到黄山14:3020:00游览黄山20:008:00住宿D48:009:30继续游览黄山20:564:099: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 .本文思路清晰，模型恰当，得出的方案合理；

30、2 .本文成功的使用了 01变量，使模型的建立和编程得以顺利进行；3 .在第二问中采用了 TCP算法，简化了模型的求解难度；4 .该模型有许多实际因素没有考虑在内，比如旅行者的年龄、健康状况等，若考虑后模型将更加精 确完整。5 .2.模型的改进与推广：1 .实际情况中，两景点之间可能通过其他交通方式连接，每一个景点的游览时间、市内交通（公交、 计程车和地铁）的到达时间、等待时间、旅行者步行时间和天气因素都未考虑在内，考虑之后模型将更 加精确、详细。2 .因数据资料搜集的不完整，准确性也有待商榷，而且没有对最终方案进行更为细致的讨论研究，这些方面有待改进。7参考文献1姜启源 谢金星 叶俊，数学模

31、型（第三版），北京：高等教育出版社，2003 o2谢金星薛毅，优化建模与 LINDO/LINGO 软件，北京：清华大学出版社，20058附录8.1 各旅游景点可能的住宿地及到达方式（起点为火车站或住宿地）表一 恐龙园、崂山、八达岭长城、乔家大院、龙门石窟景点名称相关数据常州市中华恐 龙园青岛市崂山风 景区八达岭长城祁县乔家大院洛阳市龙门石 窟可到达公交线 路29（火车站至恐 龙园）公交301或304路到西姜站地铁2号线（外/ 内）德胜门下 车，919路公交 汽车直达八达 岭长城步行81路到龙门石 窟下可住宿旅馆常州吾家吾庭 商旅酒店青岛晨旭商务 宾馆北东城市青年 酒店晋中平遥天禄 客栈中州快捷

32、洛阳 金谷园店表二黄山、黄鹤楼、兵马俑、庐山、普陀山景点名称相关数据黄山市黄山风 景区武汉市黄鹤楼西安市秦兵马 俑九江市庐山风 景区舟山帝普陀山 风景区可到达公交线 路黄山风景区班 车“屯溪-太 平”542路914路到秦始皇 兵马俑博物馆101路公交车（1）到长 途汽车站转车 去庐山打车到半升洞 码头，做船到达 普陀山可住宿旅馆黄山国际青年 旅馆武汉力国宾馆西安铁路饭店格林豪泰九江 火车站店百时快捷宁波 火车站店表三（1）各景点、城市花费一览景点名称相关数据常州市中华恐 龙园青岛市崂山风 景区八达岭长城祁县乔家大院洛阳市龙门石 窟门票票价160 ¥90 ¥45 ¥

33、40 ¥120Y交通费1 ¥1 ¥3¥0¥1 ¥可能的住宿费190¥128Y150Y88¥135Y其他费用60 ¥60 ¥60 ¥60 ¥60 ¥表三(2)各景点、城市花费一览景点名称相关数据黄山市黄山风 景区武汉市黄鹤楼西安市秦兵马 俑九江市庐山风 景区舟山帝普陀山 风景区门票票价230 ¥80 ¥90 ¥180 ¥160Y交通费15¥1 ¥1 ¥13Y48Y可能的住宿费90Y148Y158Y136Y119Y其他费用60 ¥60 ¥60 ¥60 ¥60 ¥8.2 本模型计算时用到的部分lingo代码sets:jinngdian/1.10/