旅游路线规划2.doc

旅游路线的优化设计
摘要
本文通过查阅各景点之间的距离及时间的相关资料，运用图论中的Hamilton圈将相连后的景点看作为一个封闭的圈，参照货郎担（TSP）问题使用线性规划列出相关目标函数后运用lingo求解。
对于问题一，在得到距离数据后，在假设距离短则花费少的思路下，使用0-1规划建立目标函数，建立关于时间和景点数量的约束条件，在软件求解下得到十个景点3892.5元的最小旅行花费。而在问题二中将距离数据改成时间数据，得到7.5天游玩8个景点的优化方案。

关键词：图论 Hamilton圈 0-1规划 一、问题重述
某背包客要独自旅游十个景点，分别是：江苏常州市恐龙园，山东青岛市崂山，北京八达岭长城，山西祁县乔家大院，河南洛阳市空门石窟，安徽黄山市黄鹤楼，陕西西安市秦始皇兵马俑，江西九江市庐山，浙江舟山市普陀山。又已知上述各个景点的最短停留时间分别是
4小时，6小时，3小时，3小时，3小时，7小时，2小时，2小时，7小时，6小时。
假设：
1． 城际交通出行可以乘火车（含高铁）、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。
2． 市内交通出行可乘公交车（含专线大巴、小巴）、地铁或出租车。
3． 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票（第一门票）。晚上20:00至次日早晨7:00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其他费用60元/天。
一、 假设景点开放时间为8:00至18:00。
问题：
根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息（车次、航班号、起止时间、票价等）、宾馆地址和名称，门票费用，在景点的停留时间等信息。
（1） 如果时间不限，游客将十个景点全旅游完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。
（2） 如果旅游费用不限，但由于“十一”假期只有7天，为了使游客能尽可能多游览景点，请通过建立相关数学模型，为其设计该旅游行程表。
如果这位游客只有7天的假期时间和5000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。

三、问题假设及符号约定
1.模型假设：
1) 问题一中尽量不考虑以飞机作为交通工具，以节省费用车次或航班在旅行途中的时间。
2) 问题中不考虑城市间的公交线路拥堵等造成的特殊情况。
3) 各城市的公交费用相等，皆为10元。

2.符号约定：
：第个景点或第个景点 ；（分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、山西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳）；

：旅行者的旅游总消费；
：在第个景点的逗留时间；
：在第个景点的总消费；
：旅游者从第个景点到第景点路途所需时间；
：旅游者从第个景点到第景点路途所需的交通费用；
：1表示旅游者直接从第个景点到第景点；0表示其它；
：总的交通费用；
：旅行所花时间

二、问题分析
将该背包客旅游的景点一一描点相连，不难发现旅游范围几乎囊括了大半个中国。旅游的时间段为10.1黄金周，也昭示着传统旅游旺季的来临，各大景点几乎是人满为患。因此旅游者安排一个合理的出行计划就至关重要了。
对于问题一，我们知道在时间不限，费用最少的要求下，黄金周时期高昂的机票让游客可以不用考虑乘坐飞机往来景点所在城市，剩下的便是城际的长途客车和铁路线系统。
生活观察中，我们发现出发地和目的地距离越远，乘坐交通工具所需的费用也就越大：参考网上的数据我们可以得到两两城市之间的大致距离，根据城际间的各种票价，我们发现不管何种交通工具，伴随着距离的增加费用也随之增长。
由此可以推断出，只要求得各大旅游城市距离总和的最小值，依据这个最小值，背包客可以决定旅游城市的先后顺序，参照当天的旅游情况，选择长途客车或铁路系统；同时为了减少费用，可以有选择的安排游客在夜间的长途客车或火车（包括动车高铁）中休息，即可省去在当地住宿的费用。
对于问题二，考虑旅游者费用充足且时间限定，因此我们可以极端的假设。一切都以时间最省为基准。在所有交通工具中飞机时间最省，加上登机时间，飞机较之于长途客车和铁路系统在时间的节省上也远远领先。参照网络中各个目的地之间的航班，确定出城市之间飞行所用时间。由于有些城市对另一城市不存在直达航班，此时我们考虑中途转机（或乘坐火车）到目的地邻近的城市再转动车或客车。在这样的安排下游客可以在7天内尽可能多游览景点。

四、模型的建立与求解
问题一：
4.1.1数据准备
根据两个城市之间的公路及铁路，经过数据查询，得到下表各个旅游城市之间的距离：
表一：各旅游城市距离表
起始
目的地
江苏常州
山东青岛
北京八达岭
山西祁县
西安兵马俑
湖北武汉
江西九江
安徽黄山
浙江舟山
河南洛阳
杭州
352
1424
1591
1596
1558
807
779
422
230
1171
常州

973
1298
1332
1344
662
586
507
385
957
青岛

819
1008
1572
1518
1420
1543
975
1185
北京

815
1159
1200
1314
1533
1430
807
祁县

593
1243
1168
1315.6
1569.6
706
西安

1025
1102
1386
1609
387
武汉

240
749
1059
638
九江

571
779
964
黄山

462
1113
舟山

1200
洛阳

←→灰格子代表该景点与另一个景点距离重复

在上表中，为方便统计，将浙江杭州到河南洛阳依次编排序号为1~11，记为 。

4.1.2 算法的确定
将至共11个点两两相连，利用排列组合公式得到11个景点共条线路，得到图一：

图一

从图中看出，11个城市之间的路线十分复杂，但必定存在一种最短路径法求解11个城市的次序。
根据假设，整个旅游路线是环形，即最终旅游者要回到杭州，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题。
4.1.3 目标函数的确立：
经过对题目分析，我们可以知道本题所要实现的目标是，使旅游者在不规定时间的情况下游玩十个景点所花的费用最少。显然，花费最少是该问题的目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点先后，然后计算出在这种情况下的最小花费。
游览的总费分别为交通总费用和在旅游景点的花费等组成，其中大部分都是规定的，只有交通费用是可以选择的。所以我们定义：
——每个旅游者的旅游总花费；
——每个旅游者的交通总费用；
从而得到目标函数：

因为表示从第个景点到第个景点所需的交通费用，而是判断代表们是否从第个景点直接到第个景点的0—1变量，因此我们可以很容易的得到交通总费用为：

从而我们可以得到目标函数为：

4.1.3约束条件：
①时间约束
问题一放宽了对时间的要求，我们不妨可以假定限制的时间为15天（360个小时），因为表示从第个景点到第个景点路途中所需时间，所以路途中所需总时间为；表示旅游者在第个景点的逗留时间，故旅游者在旅游景点的总逗留时间为。因此，总的时间约束可得：

②旅游景点数约束
由题目要求可知，因为旅游者的时间充裕，因此他（她）打算游览完全部11个景点。因此将其约束为：
(，=1，2，……，11)
③0——1变量约束
在已经知道了要旅游所有的景点的前提下，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。用公式表示即为：
（，=1，2，……，11）
同样，当，时，根据题意不可能出现，即不可能出
现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：
（，=2，3，……，11）
最后我们将其模型建立为如下所示：

运用lingo解得旅游者游行十个景点通所用的费用为1224，景点先后顺序如下所示：

浙江杭州→浙江舟山→安徽黄山→江西九江→湖北武汉→河南洛阳→西安兵马俑→山西祁县→北京八达岭→山东青岛→江苏常州→浙江杭州。

如下图所示：

图二

4.1.4问题一所建模型结果
根据搜索出来的数据值，我们在对时间的放宽情况下，选取交通费用最少的交通工具和住宿费用来安排其的行程安排表，如下表所示：

日期
起——终
车次
起止时间
价格/元
景点逗留时间/h
住宿/价格
1号
杭州——舟山
客车 高大2
7：50——1130
70
6
舟山普陀港城商务酒店单人房178元/天
2号不游玩
舟山——宁波
客车 高速
7：05——
8：30
32

宁波——黄山
客车 高大一
13：40——18：20
132

世界家庭式酒店/民宿 90元/天
3号
黄山

8：00——18：00

10
世界家庭式酒店/民宿 90元/天
4号
黄山——九江
大巴
8：00——13：00
122

学校招待所40元/天
5号
九江庐山

8：00——15：00

7

九江——武汉
火车 k398/k395
17：00——20：30
41

武汉岭南佳园连锁酒店119元/天
6号
武汉黄鹤楼

8：00——10：00

2

武汉——洛阳
火车 k864/k861
15：25——22：00
87

洛阳易国际青年旅舍40元/天
7号
洛阳市龙门石窟

8：00——11：00

3

洛阳——西安
火车 k128/k125
14：50——19：20
55

西安七贤国际青年旅舍50元/天
8号
西安秦始皇兵马俑

8：00——10：00

2

西安——太原
空调普快2
21：48——6：48
148

太原——祁县乔家大院
6815次列车

7：00——9：00
5.5

乔家大院

10：00——13：00

3

山西——北京
空调特快
T70
14：45——19：49

北京富山国际青年旅舍46元/天
9号
八达岭长城

8：00——18：00

10

北京——山东青岛
快速
K712/k709
22：00——10：08
195

10号
青岛崂山

11：00——18：00

7

青岛——南京
快速
K416/k413
20：00——11：30
208

11号
南京——杭州
空调普快
2001
12：42——20：02
64

在将其交通所用的费用，住宿所用的费用，10个景点门票所花的费用，以及11天所用的伙食费累加起来得到在时间不限的情况下至少要消费3892.5元。

问题二：
4.2.1模型的建立与求解
在得到各个旅游城市之间的最小旅行时间后，可以同样利用问题一中所用的，将点与点之间的时间看作为它们边的权值，起点与终点相连可以构成封闭圈，采用Hamilton图的概念求最小距离（时间）的Hamilton圈。
将看作为i地点到j地点之间的最少时间，（1表示连接，0表示不连），则可以建立目标函数：

下表为各点之间相互往来所花时间的最小值，将表中的数据带入Lingo求解上述目标函数（程序见附录）。

表二：各景点之间的最短时间值
起始
目的地
浙江杭州
江苏常州
山东青岛
北京八达岭
山西祁县
西安兵马俑
湖北武汉
江西九江
安徽黄山
浙江舟山
河南洛阳
杭州
0
2.5
1.5
2
3.3
2
1.5
5
2
2.5
1.8
常州
2.5
0
5.8
1.5
3.5
2
4.2
5
6
5
4.2
青岛
1.5
5.8
0
1.16
3
2
1.91
4
3
3.5
3.8
北京
2
1.5
1.16
0
2.5
18
2
2.25
2
2.25
2.8
祁县
3.3
3.5
3
2.5
0
2.5
2.5
2.6
1.7
3.7
3.5
西安
2
2
2
1.8
2.5
0
1
4
1.6
3.5
3.5
武汉
1.5
4.2
1.91
2
2.5
1
0
2.6
3.3
2.8
3.2
九江
5
5
4
2.25
2.6
4
2.6
0
2.3
4.2
3.2
黄山
2
6
3
2
1.7
1.6
3.3
2.3
0
3.7
3.5
舟山
2.5
5
3.5
225
3.7
3.5
2.8
4.2
3.7
0
3
洛阳
1.8
4.2
3.8
2.8
3.5
3.5
3.2
3.2
3.5
3
0

求解得到10个旅游城市旅行的先后顺序是：
杭州→青岛→北京→常州→西安→黄山→祁县→九江→武汉→舟山→洛阳→杭州

图三
在上图中我们看到线路杂乱无章，这是考虑了飞机后的影响因素，在飞机的速度下，相距很近的两个景点城市所花的时间反而要大于两个相距很远的城市时间，在这样的情况下，使用软件求解线性规划的函数，得到各个城市跨度如此大的路线图，甚至可以满足7天内游玩遍所有的城市景点。
得到所花时间t为22.26 ，但这个数值是仅代表该游客在飞机上乘坐所用时间。在实际游玩中，需要考虑到景点游玩时间，候机时间，上下登机时间，市内公交等，而乘坐飞机时间花费短，也断绝了在交通工具上休息的可能性，还需包括住酒店宾馆等的休息时间。

4.2.2 问题二所建模型结果

景点游玩最少时间=43h，上下登机总时间=221=22h，市内公交101=10h，
休息时间=96=54h .
全局最优解为：160.26小时，但任何时候人要服从与现实中交通的安排，所以在旅行途中还应包括各种班次的等待时间，所以最后结果会跟计算出来的时间总和以及景点顺序会与软件求出的最优解产生偏差。
根据得到的顺序，我们安排游客按下列行程旅游：

表三：旅途行程表（问题二）
日期
起——终
车次/航班
起止时间
价格
行程
住宿/价格
1
杭州—— 青岛
山东航空SC4684
9：00-
10：30
749
青岛崂山游玩6小时
北京富山国际青年旅社/199
青岛——北京
山东航空
SC1576
21：15-
22：40
620
2
北京——西安
东方航空MU2781
11:40 -
13:45
990
北京八达岭游玩3小时至12点，2点45到达兵马俑景地
欣燕都连锁西安互助路 /135
3
西安——武汉
海南航空HU7889
8：25 -
9：30
480
10：30点到达黄鹤楼，游玩2小时
在列车中住宿
4
武汉——祁县
K522/K519
中转K868/K865
16：11 -
6：29转
7：40-
8：47
417+15
9：30到达桥架大院，游玩3小时至12点
在列车终度过
5
祁县至常州
先乘坐4626转太原，再乘坐K374/K371到常州
14：55-
16：14转17：51-
12:28
7+440
游玩常州恐龙园4小时至18点
在列车中度过
6
常州——黄山
K8418/K8419( 上海- 黄山)
23:32 -
09:00
252
游玩黄鹤楼7小时

黄山——洛阳
乘坐上海航空FM9266至上海
18：00 -
20：00
370+100

上海鹰都宾馆/128
7
黄山——洛阳
东方航空MU5389
7：50-9:40
450+150
游玩龙门石窟3小时

洛阳——杭州
东方航空MU5700
15：35-17：15
1300

按照上表中的顺序，最终游客的旅游路线为：
杭州→青岛→北京→西安→武汉→祁县→常州→黄山→洛阳→杭州

所需时间t为7天，符合题目中所要求的7天内回到杭州。

五、模型评价及推广
论文中的模型利用图论以及计算机进行优化，得到的旅游行进路线，游客的旅游计划得到了合理化的安排。但是由于文中各地的繁杂的车次导致变量过多，很难得到真正意义上的全局最优解，但是在短途旅行中，本模型能适用于求最短路径或最短时间下其他的约束问题。

六、参考文献
[1]王兵团，数学建模基础，北京：清华大学出版社，2004年
[2]姜启源，数学模型（第三版），北京：高等教育出版社，2003年
[3]刘承平，数学建模方法，北京：高等教育出版社，2002年
[4]于义良，数学建模，北京：中国人民大学出版社，2004年
[5]朱道元，数学建模案例精选，北京：科学出版社，2003年
[6]吴祈宗，运筹学，北京：机械工业出版社，2004年1月
五、
程序附录：
附录：

费用

浙江杭州
江苏常州
山东青岛
北京八达岭
山西祁县
西安兵马俑
湖北武汉
江西九江
安徽黄山
浙江舟山
河南洛阳
浙江杭州
0
46
274
330
330
301
224
87
70
70
256
江苏常州
46
0
238
272
288
282
190
87
130
180
216
山东青岛
202
238
0
195
206
221
301
298
312
430
256
北京八达岭
330
272
195
0
73
256
263
262
320
604
130
山西祁县
330
288
206
73
0
153.5
256
200
250
242
172
西安兵马俑
301
282
221
256
153.5
0
234
229
358
350
55
湖北武汉
224
190
301
263
256
234
0
41
260
263
87
江西九江
87
87
298
262
200
229
41
0
122
205
216
安徽黄山
70
130
312
320
250

358
260
122
0
164
135
浙江舟山
70
180
430
604
242
350
263
205
164
0
258
河南洛阳
256
216
256
130
172
55
87
216
135
258
0

时间

浙江杭州
江苏常州
山东青岛
北京八达岭
山西祁县
西安兵马俑
湖北武汉
江西九江
安徽黄山
浙江舟山
河南洛阳
浙江杭州
0
5
22.8
15.7
22.5
20.3
8.5
10.5
2.5
3.7
15
江苏常州
5
0
10
13.5
20
14
8.5
9
9.5
5
10
山东青岛
22.8
10
0
11.7
12.5
19
20.5
15.8
23
16
15.7
北京八达岭
15.7
13.5
11.7
0
5
11.5
10
14.5
16
2
8
山西祁县
22.5
20
12.5
5
0
12
16
18
21
20
12
西安兵马俑
20.3
14
19
11.5
12
0
11.2
18
13
25
4.5
湖北武汉
8.5
8.5
20.5
10
16
11.2
0
37
10
11
7
江西九江
10.5
9
15.8
14.5
18
18
3.7
0
5
14
12.5
安徽黄山
2.5
9.5
23
16
21
13
10
5
0
6
15
浙江舟山
3.7
5
16
2
20
25
11
14
6
0
19
河南洛阳
15
10
15.7
8
12
4.5
7
12.5
15
19
0

问题一程序：
sets:
jingdian/1..11/:c,t,l;
!其中：1,2,...,11分别代表浙江杭州、江苏常州、山东青岛、北京八达岭、陕西祁县、西安兵马俑、湖北武汉、江西九江、安徽黄山、浙江舟山、河南洛阳；c，t分别表示旅行者在各景点的吃住消费和逗留时间；l是为了控制不出现两个以上环形回路而设的一个变量;
links(jingdian,jingdian):r,cc,tt;
!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间;
endsets
data:
t=0 4 6 3 3 2 2 7 7 6 3;
c=0 0 0 0 0 0 0 0 0 0 0;
tt=0 5 19 15.7 22.5 20.3 8.5 10.5 2.5 3.7 15
5 0 10 13.5 20 14 8.5 9 9.5 5 10
19 10 0 6 12.5 19 20.5 15.8 23 16 15.7
15.7 13.5 6 0 5.7 11.5 10 14.5 16 2 8
22.5 20 12.5 5.7 0 11 16 18 21 20 12
20.3 14 19 11.5 11 0 11.2 18 13 25 4.5
8.5 8.5 20.5 10 16 11.2 0 3.7 10 11 7
10.5 9 15.8 14.5 18 18 3.7 0 5 14 12.5
2.5 9.5 23 16 21 13 10 5 0 6 15

3.7 5 16 2 20 25 11 14 6 0 19
15 10 15.7 8 12 4.5 7 12.5 15 19 0

!其中：主对角线为零,表示各景点到自身交通费用为零;
cc0 46 202 330 330 301 224 87 70 70 256
46 0 238 272 288 282 190 87 130 180 216
202 238 0 113 206 221 301 298 312 430 256
330 272 113 0 80 256 263 262 320 604 130
330 288 206 80 0 148 256 200 250 242 172
301 282 221 256 148 0 234 229 358 350 55
224 190 301 263 256 234 0 41 260 263 87
87 87 298 262 200 229 41 0 90 205 216
70 130 312 320 250 358 260 90 0 139 135
70 180 430 604 242 350 263 205 139 0 258
256 216 256 130 172 55 87 216 135 258 0
;
!其中：主对角线为零,表示各景点到自身的交通时间为零;
enddata
min=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j)))));
!目标函数：表示计划游玩的景点数目为n时的最小费用;
@for(jingdian(i):r(i,i)=0);
!约束条件：表示各景点到自身没有路线相连的约束条件;
@for(jingdian(i)|i#ge#2:@for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)<1));
!约束条件：表示除起点（杭州）外，若旅行者从景点i到景点j去游玩（即r(i,j)=1），则不会再从景点j到景点i去游玩（即r(j,i)=0），也就是说除起点外每个景点只游玩一次;
a=@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)))));
@sum(jingdian(j):@sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j))))<360;
!约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间15天360小时;
@for(jingdian(i):@sum(jingdian(j):r(i,j))=@sum(jingdian(j):r(j,i)));
@for(jingdian(i)|i#eq#1@sum(jingdian(j):r(i,j))=1);
@for(jingdian(i)|i#ne#1:@sum(jingdian(j):r(i,j))<1);
!这三个约束条件：表示起点（杭州）有且仅有一条路线出去和一条路线进来，其它景点要么有且仅有一条路线出去和一条路线进来，要么既没有路线出去也没有路线进来;
@for(links:@bin(r));
!约束条件:表示0-1变量约束;
@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=11;
!约束条件:表示旅游景点的数目为n的约束;
@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)-(n-2)*(1-r(i,j))+(n-3)*r(j,i)));
@for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1));

问题二：
MODEL:
SETS:!初始设置;
CITY / 1.. 11/: U;!U(i)为地点编号;
LINK( CITY, CITY):DIST, X;!DIST为两地间花费;
ENDSETS
!数据区;
DATA:
DIST =0 2.5 1.5 2 3.3 2 1.5 5 2 2.5 1.8
2.5 0 5.8 1.5 3.5 2 4.2 5 6 5 4.2
1.5 5.8 0 1.16 3 2 1.91 4 3 3.5 3.8
2 1.5 1.16 0 2.5 1.8 2 2.25 2 2.25 2.8
3.3 3.5 3 2.5 0 2.5 2.5 2.6 1.7 3.7 3.5
2 2 2 1.8 2.5 0 1 4 1.6 3.5 3.5
1.5 4.2 1.91 2 2.5 1 0 2.6 3.3 2.8 3.2
5 5 4 2.25 2.6 4 2.6 0 2.3 4.2 3.2
2 6 3 2 1.7 1.6 3.3 23 0 3.7 3.5
2.5 5 3.5 2.25 3.7 3.5 2.8 4.2 3.7 0 3
1.8 4.2 3.8 2.8 3.5 3.5 3.2 3.2 3.5 3 0;
ENDDATA
N = @SIZE( CITY);!模型的大小;
MIN = @SUM( LINK: DIST * X);!目标函数为点距之和最小的路径;
@FOR( CITY( K):
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;!对于线路中每一个地点只有一条路指向这个地点;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!从这个城市出发只有一条路可以离开;
@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:!如果连接cityk和cityj,则cityj = cityk+1;
U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K));
);
@FOR( LINK: @BIN( X));
@FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
U( K) >= 1 + ( N - 2) * X( K, 1));
END

16