最佳旅游路线设计Word格式文档下载.docx
《最佳旅游路线设计Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《最佳旅游路线设计Word格式文档下载.docx（19页珍藏版）》请在冰点文库上搜索。
我们将景区进行编号，并通过网络查找到各个景点之间的距离，我们就可以将实际地图简化为赋权无向图，所以问题就变成了图论问题。
另外我们还需补充路费、最佳逗留时间以及门票费用等其他信息。
问题一的目标是找到一条能在一个月内实现的最佳旅游路线，要求花费最少，景点最多，这是一个多目标线性规划问题。
我们可以使用floyd算法求得各个顶点（景区）之间的最短路径，然后我们以花费最少为规划目标，将“景点最多”这一目标放入限制条件中，要求走过的景点数为N（N>
=12）。
然后再建立时间、景点路线为要求的约束条件，将多目标规划问题转变成单目标0-1规划问题。
使用lingo求解可得最佳旅游路线。
问题二需要两条旅游线路，这两条旅游线路可以覆盖新疆的全部景点。
同时这两条线路都从乌鲁木齐出发再回到乌鲁木齐，彼此之间无重复的景点，这两组线路所需时间都在一月之内。
我们很容易想到，将全部的景点以乌鲁木齐为界分为南北两组比较容易求出满足要求的路线。
我们将景点进行分组，并计算均衡度后利用0-1规划求解得到的最佳路线及所需时间，再根据均衡度进行调整，选取均衡度最佳的一组。
问题三是多旅行商问题。
解法同问题二，我们将所有景点分为3组，使各组的考察时间尽量相等。
由问题一中已经画出的各景点间的最短路径，求出以乌鲁木齐为起点的树，然后按照分类的原则，将景点分为三类，再进行调整即可。
确定景点的分组后，同样使用问题二中建立的0-1线性规划模型求解，只需将目标函数换成考察天数最小即可。
问题四与问题三相似，我们首先利用问题一中N=21及游遍所有景点所需的最小花费和时间，再根据五一黄金周时间限制，确定游玩路线至少应分为几条，才可以最大程度上分散景区压力。
然后按时间均衡度和花费均衡度都尽可能好的原则将景点进行分类，再按照问题二中的模型求解，即可得所需旅游路线。
三、模型的假设
1.所有景点都正常开放，开放时间没有区别。
2.交通路线全部正常，交通工具匀速。
3.景点的花销仅限于门票支出。
4.住宿费用和交通费用在所有景区都是一样的。
5.景区的先后到达不会有区别（考察和旅游时）。
6.王夫妇对于的景点喜爱程度是一样的。
四、符号的说明
总交通费用加门票费用
M除吃饭外的所有消费（包括住宿费）
总的交通费用
总的门票费用
第i个景点的门票费用
每条路线总的行驶路程
若
=1，则表示从i景点去j景点，否则
=0
表示i景点与j景点之间的距离
表示从i景点到j景点多需的时间
表示游客在i景点的最佳逗留时间
五、模型的建立与求解
问题一
基于分析，我们首先在网上收集各旅游景点之间的路程、门票、最佳逗留时间、汽车的行驶速度以及住宿费用，具体数据见表1，并据此对地图进行了简化，如下图所示:
我们加上了王先生夫妇特别向往的景点天池和达坂城。
对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑各景点的最佳逗留时间的和。
表1：
各景点最佳逗留时间及门票费用
景点编号
景点名称
逗留时间
门票（元）
1
乌鲁木齐（昌吉、达坂城）
96h
2
天池
48h
100
3
吐鲁番（火焰山）
72h
60
4
哈密（回王陵）
40
5
库尔勒（博斯腾湖）
30
6
石河子
24h
7
克拉玛依
8
阿勒泰
9
喀纳斯湖
230
10
额尔齐斯河
11
伊犁（昭苏边境的乾隆格登碑）
12
博乐（博尔塔拉，怪石沟）
13
天鹅湖
98
14
千佛洞（库车大寺）
125
15
阿克苏
16
喀什（阿图什、苏丹.沙图克麻扎、香妃墓、艾提尕清真寺）
50
17
和田
18
尼亚遗址
19
楼兰（罗布泊）
大巴平均行驶速度：
85km/h，车费为0.4/km
住宿费用：
100元/晚
我们需要根据以上数据规划出一条路线让王先生夫妇能够在一个月内用最少的花费走过最多的景点，这是一个典型的优化问题。
从上面的加权图中我明年可以使用FLOYD算法求出任意两个景点之间的最短路径，然后将其做成一个完备图。
由于该0-1规划中存在两个目标，即花费最少和最多的景点，我们可以将景点数设置为一定的情况下单独考虑花费最少这一目标函数，将多目标规划变为单目标规划。
然后不断改变设定的景点数，就不同景点数情况下的花费经过综合对比求出最佳路线。
旅途中总的消费除吃饭外主要考虑交通费用m1和门票费用m2
则得到目标函数：
约束条件如下：
约束1：
时间约束，游玩所有景点最佳路线的时间不能超过一个月，即300个小时。
此时间包括路上交通所消耗的时间和景点逗留时间，路上消耗的时间为
，景点逗留的总时间为
，由此可得
约束2：
我们假设王先生夫妇游玩的景点数为n，一共有21个景点，为保证数量，我们规定n=12，13。
。
19，由假设可知，所选路线为1个环形，因此
约束3：
所有经过的景点相连成为一个圈。
则，对于每个景点，最多只有一条边进入，同样只允许最多一条边出来。
并且只要有一条边进去就有一条边出来，因此
约束4：
所有的线路出发点终点均为乌鲁木齐，即
，
约束5：
除了乌鲁木齐外，其余的景点游客至多只会经过一次，即当
时，不会出现
，因此我们可得约束：
综上所述，我们可以建立如下0-1线性规划：
分别令n=10,11….19，求解，得到如下结果
景点数
日均消费（元）
总时间
总费用（元）
具体路线
96.2
22天
2115.4
1-6-7-12-11-13-15-14-5-19-1
97.5
23天
2241.8
1-5-19-15-14-13-11-12-6-7-8-1
93.7
25天
2341.8
1-5-19-15-14-13-11-12-6-7-8-2-1
81.3
27天
2916.2
1-4-5-19-15-14-13-11-6-12-7-8-2-1
101.5
30天
3044.6
1-2-3-4-5-14-15-13-11-12-6-7-9-8-1
…
分析上表，一个月内可参观的景点数最多为14个，但其平均消费额也最大为101.5，比景点数为13时的平均消费额高20.2，综合考虑，我们向王先生夫妇推荐景点数为13的旅游路线：
1-4-5-19-15-14-13-11-6-12-7-8-2-1总费用为2916.2元
问题二：
据分析，我们需将所有景点分为2组，保证游完每条线路的时间不超过一个月，且每组的时间尽量相等，即均衡度尽量小。
按照实际地理情况，我们将所有景点按南北疆分为如下2组：
第一种分组：
单纯以乌鲁木齐为界，将景点进行南北划分
第一组
9,8,10,7,2,1,3,4,6,12
第二组
11,13,5,14,15，19,16,18,17
以每条线路上所消耗的时间最少为目标，约束条件与问题一相似，建立0-1线性规划模型如下：
分别将上述分组代入模型，运用lingo软件求解，得到如下结果
交通费用
2466.8元
1-19-5-6-7-8-10-9-2-4-3-1
2270.4元
1-2-4-3-8-10-9-6-7-1
计算上述分组的均衡度：
对上述分组如下调整
第二种分法：
左调整
9，8，10，7，2，1，3，4，6
11，13，5，14，15，19，16，18，17，12
用上述模型及方法求解，得：
1732.4元
1-8-9-10-7-6-3-2-1
2797.8元
1-12-11-13-14-15-16-18-17-19-5-1
均衡度为
再进行如下调整：
第三种分法：
右调整
9，8，10，6，2，1，3，4，6，12，11
13，5，14，15，19，16，18，17
求解得
3461.0元
1-2-4-3-17-11-6-7-9-8-10-1
2253.4元
1-13-14-15-16-18-17-19-5-1
均衡度
比较三种分组的均衡度，按第二种分法均衡度最好，因此选择此种分组。
得到王先生夫妇2次的最佳旅游线路为:
第一个月：
乌鲁木齐—阿勒泰—喀纳斯湖—额尔齐斯河—克拉玛依—石河子—吐鲁番—天池—乌鲁木齐，交通费用为1732.4元。
第二个月：
乌鲁木齐—博乐—伊犁—天鹅湖—千佛洞—阿克苏—喀什—尼雅遗址—楼兰—库尔勒—乌鲁木齐，交通费用为2797.8元。
问题三：
据分析，首先根据问题一中求得的各景点间的最短路径，画出以乌鲁木齐为起点的树状图如下
由题意考察团分三组进行，且考察对象为所有景点，即所有景点都必需包括在内，则要把所有景点分成3组。
分组过程中需尽量遵守以下4个原则：
1.长枝与短枝组合搭配。
2.同枝的点尽量不分开。
3.相邻干枝的点分在一组。
4.尽量使各组的停留时间相等。
按以上4个原则，可将所有景点按如下所示分为6个区，分组情况如下所示：
第一种分组（严格按分组原则分）
第一组（①③）
1，7，6，18，17，16，15，14，13
第二组（④⑥）
19，5，3，4，8，10，9
第三组（②⑤）
11，12，1，2
将上述分组，按照模型二的求解方法求解，得到如下结果：
组别
考察时间
55天
1-15-16-18-17-14-13-7-6-1
56天
1-8-9-10-3-19-5-4-1
第三组
1-12-11-2-1
该种分法的均衡度为：
该分法的均衡度较差，因此我们对分组进行调整，将将⑥中的4景点调整到第三组中，将③中的21调整到第三组，分组如下：
1，7，6，17，18，16，15，14，13
1，8,10,9,5,19,4
1,2,11,12,3
仍用上述方法求解，得到如下结果：
47天
1-12-11-2-3-1
51天
1-6-7-13-14-15-18-17-16-1
48天
1-9-8-10-5-19-4-1
由比较结果可以得出，最后一种方法的均衡度较好，故选用这种分组。
即该考察团的考察路线为：
第一组：
乌鲁木齐—博乐—伊犁—昌吉—天山天池—吐鲁番—达坂城—乌鲁木齐，考察时间为47天。
第二组：
乌鲁木齐—石河子—克拉玛依—天鹅湖—千佛洞—阿克苏—尼亚遗址—和田—喀什—乌鲁木齐，考察时间为51天。
第三组：
乌鲁木齐—喀纳斯湖—阿勒泰—额尔齐斯河—库尔勒—楼兰—哈密—乌鲁木齐，考察时间为48天。
问题四：
此问题实质是对景点的分组问题。
由第一问我们求出了行遍所有景点的最短路为6713公里，花在路上的时间为6713/（7*85）=11.28天，要行遍所有景点的总逗留时间为36天，计算出总共花费的时间47.28天，44.42/12
3.94，则至少要分出4组路线。
当分成4组路线时，各组停留时间大约为36/4=9天，各组花在路途上的时间为12-9=3天。
由第三问我们求得分三组的总路程为13482km，分4组的总路程不会比分三组的路程大多少，不妨以13482km来估算。
路途中时间为13482/85=138.61h，158.6/7=19.87天，若平均分给4个组，则每组19.87/4=4.95>
4,所以分4组不可行。
因此分5组.
依照前文所述前三个原则进行分组如下：
1,13,14,15
1,16,17,18
1,6,7,11,12
第四组
1,2,8,9,10
第五组
1,3,4,5,19
用同样的方法求解得：
线路编号
门票费用
最佳路径
7天
804.0元
158元
1-14-15-13-1
11天
1900.4元
100元
1-18-17-16-1
12天
974.6元
120元
1-6-7-12-11-1
903.4元
1-9-8-10-2-1
998.4元
130元
1-19-5-4-3-1
六、模型的分析与优化
本文通过合理的假设和数据的补充，将原问题简化为图论的0-1规划问题进行解答，简单易懂，与现实的贴合度高。
模型的缺陷在于未能考虑到一些现实情况。
比如前往不同的景点可能使用不同的交通工具花费和时间是不一样的、部分景点处于维护考虑会限定开放时间、考察团对于不同的景点的考察时间会有变化、游客对于旅游景点可能会有喜爱程度上的不同。
在将这些因素考虑进模型后，模型将能够进一步贴合实际情况作出更好规划。
参考文献
[1].姜启源，谢金星，叶俊.数学模型（第三版）[M].北京：
高等教育出版社2003.
[2].赵静等.数学建模与数学实验（第3版）[M].北京：
高等教育出版社2008.
[3].卓金武.MATLAB在数学建模中的应用[M].北京：
北京航空航天大学出版社2011.
附录
model:
sets:
cities/1..19/:
ti,tickets;
link（cities,cities）:
rij,tij,xij;
endsets
data:
rij=@ole（'
D:
/新疆.xls'
rij）;
tickets=@ole（'
tickets）;
ti=@ole（'
ti）;
tij=@ole（'
tij）;
@ole（'
）=xij;
enddata
min=0.4*@sum（link（i,j）:
rij（i,j）*xij（i,j））+0.5*@sum（link（i,j）:
xij（i,j）*（tickets（i）+tickets（j）））;
@SUM（link（i,j）:
xij（i,j））=n;
@sum（link（i,j）:
（xij（i,j）*tij（i,j）））+0.5*@sum（link（i,j）:
xij（i,j）*（ti（i）+ti（j）））<
480;
@for（cities（i）:
@sum（cities（j）:
xij（i,j））<
=1）;
@for（cities（j）:
@sum（cities（i）:
（@sum（cities（i）:
xij（i,j））-@sum（cities（k）:
xij（j,k）））=0）;
xij（i,1））=1;
xij（1,j））=1;
@for（link（i,j）:
（xij（i,j）*xij（j,i））=0）;
@for（link:
@bin（xij））;
end
升级会员 