最佳旅游路线设计方案样本.doc

最佳旅游路线设计方案

15
2020年4月19日
文档仅供参考，不当之处，请联系改正。
最佳旅游路线设计方案
作者：吴渊、张文艳、周子晗
摘要：主办方为参加会议的代表安排了旅游，初步设想了五条线路，可是由于代表们的日程不同；还有后面出现的代表们的旅游意向；各景点的天气状况；在这些条件的影响下，
需要主办方根据不同的情况设计出不同的旅行路线。而且要求设计出的路线花钱少，游览的景点多。
在提出的几个问题中，分别利用了穷举法、图论中Hamilton图的性质，营销员推销路线模型，并尝试对附录表中的数据进行统计，处理之后取舍路线。经过特定的处理之后，问题之间会出现相似的解题模型，最后利用LINGO和逐步搜寻最优的方法得出结果。
问题的重述：主办方初步提出的参考路线如下：
一号线：成都→九寨沟、黄龙；
二号线：成都→乐山、峨嵋；
三号线：成都→四姑娘山、丹巴；
四号线：成都→都江堰、青城山；
五号线：成都→海螺沟、康定；每条线路中的景点能够全部参观，也能够参观其中之一。不但如此，一起参观景点的人数越多，每人承担的费用也会越小。
第一问和第三，四，五问中都要求在有限的10天内游览的景点多，而且花费少。可是问题三中有100个代表对五条路线的意愿限制，
问题五中又添加了未来10天之内各个景点的天气情况。在第四问中，依然有100个代表的意愿限制，可是前五十个代表先去，后五十个四天之后再去。第二个问题中每一个景点都游玩一次，有充分的时间，要求设计出交通费用最少的路线。
问题的假设：
1. 整个旅行过程的乘车方式都为汽车，每天的食宿费一定，都为100元。
2. 任意两个景点都能够直达，一个景点只游玩一次，在一个景点至少花一天的时间游完，经过大量的常规旅游行程统计，确定了在各个景点所需的游玩时间。
3. 到达景点之间的行车时间都不超过一天，且计入要到达景点的游玩时间内。
4. 由于有些景点之间的乘车价钱没有搜集到具体数据，因此我们按0.2元/公里计算。
5. 根据所查询的各景点资料得知，丹巴、康定是包含多个景点的地区，因此这两个景区总的旅行票价是当地有名景点的票价之和。
6. 对代表们的旅游意愿赋值，去的为1，不去的为-1，无所谓的为0.
若路线中含有她们不愿意去的路线，她们就不参加旅行。
引入参量： i , j………………..分别表示路线中的所有景点(i,j =0…10)
X(i , j)…………….表示从景点i到景点j
P j………………..表示景点j的票价
A(i , j)…………….表示景点i到景点j的距离
D j………………..表示在景点j的游玩时间

相关数据搜寻结果：
编号
景点(i,j)
门票(Pj)
游玩时间(Dj)
各景点到成都的距离
1
九寨沟
220元
2天
434公里
2
黄龙
200元
1天
414公里
3
乐山
70元
1天
139公里
4
峨眉山
120元
1天
172公里
5
四姑娘山
210元
1天
254公里
6
丹巴
40元
1天
364公里
7
都江堰
60元
1天
66.1公里
8
青城山
60元
1天
77.1公里
9
海螺沟
80元
2天
307公里
10
康定
85元
2天
330公里
0
成都
0元
0天
0公里

各景点之间路程 L(i,j)：(公里)两景点的往返路程相同

1
2
3
4
5
6
7
8
9
10
1
0
170
573
615
546
655
440
450
742
765
2
170
0
550
580
458
568
353
362
716
742
3
573
550
0
44.5
384
466
202
209
353
377
4
615
580
44.5
0
418
412
230
241
300
322
5
546
458
384
418
0
109
192
202
299
248
6
655
568
466
412
109
0
308
311
193
143
7
440
353
202
230
192
308
0
15.1
367
390
8
450
362
209
241
202
311
15.1
0
304
327
9
742
716
353
300
299
193
367
304
0
105
10
765
742
377
322
248
143
390
327
105
0

问题的分析：
1. 由于旅行时间和在各个景点所需游玩时间的限制，代表们只能游览部分景点，而且最多去八景点。利用穷举法，从出发点开始搜索，距离最短的景点列入路线中，再依次类推的方法搜索其它景点，有根据时间的限制，搜索出一条路线最短的方案。
2. 在一个月的时间内，代表们能够将所有的景点游完，则旅游的路线能够构成一个Hamilton图，所求问题即是使各边权之和最小，符合营销员推销路线模型。
3. 100个代表对主办方初步提供的五条线路意愿用1，-1，0赋值之后，根据我们对附表1的处理（100个代表对每条路线的满意度求和；统计出每条路线中一定去的人数），结果的正负成为取舍该路线的决定因素。之后便得到初步的游览景点，将路线2和4淘汰，去掉了3，4，7，8这四个景点，其余6个景点的游览时间小于10天。
参加旅游的人数并非为100个，减掉了一定去2和一定去4路线的人数，剩余的便是参加旅游的人数。
转化之后，此次旅行的费用求解与问题1相似。
4. 主办方在此问题中能够设计两条路线，初步的处理方法与3相同，只是把前50个人的意愿整体处理，得出她们这条路线包括那些景点，人数计算同上题一样。后50个人以同样的方法解决，主办方安排的这次旅游总花费，有这两个不同路线的旅行花费构成。而每一部分的费用计算同问题1类似。
5. 这个问题中由于天气的原因，原来设计的路线会被改动。例如：假设原定路线中，第一天去九寨沟，可是第一天九寨沟一定下雨，主办方就把第一天定为去黄龙（下雨的概率小于等于50%）；如果第二天有两个下雨概率小于等于50%的景点，就选那个离第一天所游景点最近的那个，依次选定后就会形成新的路线。可是新的路线并不是最优化的路线，因此会造成一定的损失费。
新路线的费用计算根据景点的花费水准（票价，路费，食宿费）确定下来，新路线所需费与最优化费用之差就是损失费。

模型的建立：
1. 一个人在这次旅行中花费S的最少，能够表明总的花费最少。费用包括三个部分，即景点票价，路费，食宿费。若从i到达j景点并游玩，则需花费x(i , j)*(Pj+A(i , j) ).
min=
st.

U(i)-u(j)+9x(I,j)<=8
2. 根据Hamilton图的特点，
Min=
st.

U(i)-u(j)+11x(I,j)<=10
3. 路线中的景点经过重新编号后包括：1九寨沟，2黄龙，3四姑娘山，4丹巴，5海螺沟，6康定。2路线一定去的人数是12，4路线一定去的人数是14，则参加旅游的人数是100-26=74人。

min=74
st.

U(i)-u(j)+7x(I,j)<=6
4. 前50人选择的路线中经过重新编号的景点包括：1四姑娘山，2丹巴，3海螺沟4康定，去的人数50-7-8-7=28人。

min=28
st.

U(i)-u(j)+5x(I,j)<=4

后50人选择的路线中经过重新编号的景点包括：1九寨沟，2黄龙，3青城山，4都江堰，去的人数50-4-7-7=32人。
min=32
st.

U(i)-u(j)+5x(I,j)<=4
5.路线中的景点如下： 1九寨沟，2黄龙，3四姑娘山，4丹巴，5海螺沟，6康定。
Step1,搜寻出第一天以上景点下雨概率小于等于50%的有：2，4，5，6.选取其中离成都最近的一个即4（丹巴）。
Step2, 搜寻出第二天没有去过的以上景点下雨概率小于等于50%的有：6康定。
Step3, 搜寻出第三天没有去过的以上景点下雨概率最小的有：3四姑娘山和5海螺沟。距离康定较近的是5海螺沟。
Step4,由于在海螺沟游玩2天，搜寻出第五天没有去过的以上景点下雨概率小于等于50%的有：1九寨沟，2黄龙。距海螺沟较近的是3四姑娘山。
Step5，四姑娘山距黄龙较近，且第六天不下雨，因此选2黄龙。则最后一站去1九寨沟。

模型的结果：
1. 第一题的路线（总距离为1123.7公里，耗时10天，每个人总费用为1950元）：
成都--都江堰—青城山—四姑娘山—丹巴—康定
—海螺沟--峨眉山—乐山—成都
2. 第二题的路线（总距离为1972.6公里，耗时13天，每个人总费用为2840元）：
成都—九寨沟—黄龙—都江堰—青城山—四姑娘山
—丹巴—康定—海螺沟--峨眉山—乐山—成都
3. 第三题的路线（总距离为1684公里，耗时9天，每个人总费用为2072元）：
成都—海螺沟—康定—丹巴—四姑娘山
--黄龙—九寨沟—成都
4. 第四题的路线（可分为两条路线）：
第一条路线（总距离为918公里，耗时6天，每个人总费用为1354元）：
成都—四姑娘山—丹巴—康定—海螺沟—成都
第二条路线（总距离为1005.2公里，耗时5天，每个人总费用为1241元）：
成都—都江堰—青城山—黄龙—九寨沟—成都
5. 第五题的路线（总距离为1931公里，耗时9天，每个人总费用为2121元，改变路线造成损失49元）：
成都—丹巴—康定—海螺沟—四姑娘山
--黄龙—九寨沟—成都
结果评价：
每一个问题的结果都是在一些特定的假设条件下得出，假设的条件缺少很强的合理性，比如在第三题以及后面的一些路线中出现代表们不愿意去的地点，她们就不参加这次旅行.。在实际情况中，这是不合理的假设，可是由于将问题简化，才提出这样的假设.。而且条件中有去的人越多，每个人所承担的费用越少，这一条件在模型中并没有得到体现。详细的资料搜寻为结果提供了可靠的数据保障，所得每条路线中显示了费用，耗时，和路程。总体上所得结果还是具有很大的参考性。
附件的处理：

一号线
二号线
三号线
四号线
五号线
1
1
-1
-1
0
0
2
0
1
-1
1
-1
3
0
-1
0
1
-1
4
0
0
0
-1
0
5
0
-1
1
-1
0
6
0
0
0
0
0
7
0
0
1
0
0
8
1
-1
0
-1
0
9
0
0
0
0
0
10
0
0
0
0
1
11
0
0
1
-1
0
12
-1
1
0
-1
1
13
-1
1
0
0
0
14
0
0
0
0
-1
15
0
0
1
0
0
16
0
-1
0
0
1
17
0
0
0
1
0
18
-1
0
0
0
0
19
-1
-1
0
0
0
20
0
0
0
0
0
21
0
0
0
-1
-1
22
0
-1
-1
0
0
23
0
0
-1
0
0
24
0
1
0
0
1
25
0
0
0
0
0
26
0
-1
0
0
-1
27
0
0
1
0
0
28
0
0
0
1
0
29
1
0
0
-1
0
30
0
0
0
0
0
31
0
1
0
0
1
32
0
0
0
-1
-1
33
0
0
-1
-1
0
34
0
0
0
0
0
35
-1
-1
0
0
0
36
-1
1
0
-1
1
37
0
0
0
0
0
38
1
-1
1
0
0
39
1
1
0
0
0
40
0
0
0
0
0
41
0
-1
0
1
0
42
-1
0
0
-1
0
43
0
0
1
1
0
44
-1
-1
0
0
0
45
0
-1
-1
0
1
46
0
0
1
0
0
47
1
0
0
-1
0
48
0
1
-1
0
-1
49
1
0
0
1
0
50
-1
0
0
0
1
51
1
-1
1
0
0
52
0
0
0
1
-1
53
0
0
0
-1
0
54
1
0
1
0
0
55
0
-1
0
0
0
56
0
1
0
0
-1
57
0
0
0
1
0
58
0
-1
0
0
0
59
1
0
0
0
1
60
0
0
-1
0
1
61
1
0
0
0
0
62
0
-1
1
-1
0
63
0
1
0
1
0
64
0
1
0
-1
0
65
-1
0
0
0
-1
66
0
0
0
1
0
67
0
-1
-1
0
-1
68
0
0
1
0
0
69
0
0
0
0
0
70
1
0
0
0
1
71
0
0
0
0
0
72
-1
-1
0
-1
0
73
0
0
0
0
0
74
1
0
-1
0
1
75
0
-1
0
0
0
76
0
0
0
1
1
77
0
0
0
0
0
78
-1
0
-1
0
0
79
-1
0
0
0
1
80
0
1
0
0
0
81
0
-1
0
0
0
82
1
0
-1
0
0
83
0
0
0
0
-1
84
-1
0
0
1
0
85
0
0
0
1
-1
86
0
0
1
0
0
87
0
0
0
0
0
88
1
0
0
0
1
89
1
0
0
0
0
90
0
0
0
0
-1
91
0
0
-1
0
0
92
1
0
0
0
0
93
0
0
-1
-1
0
94
0
0
0
-1
0
95
1
0
1
-1
0
96
0
0
0
0
0
97
0
-1
0
0
0
98
1
0
0
1
0
99
0
0
-1
0
0
100
1
0
1
-1
-1

6
-10
0
-5
0
一定去的人数
20
12
15
14
15
前50个代表意愿处理： 后50个代表意愿处理：
一号线
二号线
三号线
四号线
五号线
51
1
-1
1
0
0
1
-1
-1
0
0
52
0
0
0
1
-1
0
1
-1
1
-1
53
0
0
0
-1
0
0
-1
0
1
-1
54
1
0
1
0
0
0
0
0
-1
0
55
0
-1
0
0
0
0
-1
1
-1
0
56
0
1
0
0
-1
0
0
0
0
0
57
0
0
0
1
0
0
0
1
0
0
58
0
-1
0
0
0
1
-1
0
-1
0
59
1
0
0
0
1
0
0
0
0
0
60
0
0
-1
0
1
0
0
0
0
1
61
1
0
0
0
0
0
0
1
-1
0
62
0
-1
1
-1
0
-1
1
0
-1
1
63
0
1
0
1
0
-1
1
0
0
0
64
0
1
0
-1
0
0
0
0
0
-1
65
- 1
0
0
0
-1
0
0
1
0
0
66
0
0
0
1
0
0
-1
0
0
1
67
0
-1
-1
0
-1
0
0
0
1
0
68
0
0
1
0
0
-1
0
0
0
0
69
0
0
0
0
0
-1
-1
0
0
0
70
1
0
0
0
1
0
0
0
0
0
71
0
0
0
0
0
0
0
0
-1
-1
72
-1
-1
0
-1
0
0
-1
-1
0
0
73
0
0
0
0
0
0
0
-1
0
0
74
1
0
-1
0
1
0
1
0
0
1
75
0
-1
0
0
0
0
0
0
0
0
76
0
0
0
1
1
0
-1
0
0
-1
77
0
0
0
0
0
0
0
1
0
0
78
-1
0
-1
0
0
0
0
0
1
0
79
-1
0
0
0
1
1
0
0
-1
0
80
0
1
0
0
0
0
0
0
0
0
81
0
-1
0
0
0
0
1
0
0
1
82
1
0
-1
0
0
0
0
0
-1
-1
83
0
0
0
0
-1
0
0
-1
-1
0
84
-1
0
0
1
0
0
0
0
0
0
85
0
0
0
1
-1
-1
-1
0
0
0
86
0
0
1
0
0
-1
1
0
-1
1
87
0
0
0
0
0
0
0
0
0
0
88
1
0
0
0
1
1
-1
1
0
0
89
1
0
0
0
0
1
1
0
0
0
90
0
0
0
0
-1
0
0
0
0
0
91
0
0
-1
0
0
0
-1
0
1
0
92
1
0
0
0
0
-1
0
0
-1
0
93
0
0
-1
-1
0
0
0
1
1
0
94
0
0
0
-1
0
-1
-1
0
0
0
95
1
0
1
-1
0
0
-1
-1
0
1
96
0
0
0
0
0
0
0
1
0
0
97
0
-1
0
0
0
1
0
0
-1
0
98
1
0
0
1
0
0
1
-1
0
-1
99
0
0
-1
0
0
1
0
0
1
0
100
1
0
1
-1
-1
-1
0
0
0
1

-5
-1
0
-1
-2
-5
1
-5
1
7
8

7