最佳旅游线路-数学建模最佳数学建模旅游路线最佳旅游线路最佳旅游路线.doc
《最佳旅游线路-数学建模最佳数学建模旅游路线最佳旅游线路最佳旅游路线.doc》由会员分享，可在线阅读，更多相关《最佳旅游线路-数学建模最佳数学建模旅游路线最佳旅游线路最佳旅游路线.doc（35页珍藏版）》请在冰点文库上搜索。
最佳旅游路线设计
摘要
本文主要研究最佳旅游路线的设计问题。
在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。
基于对此的研究，建立数学模型，设计出最佳的旅游路线。
第一问给定时间约束，要求为主办方设计合适的旅游路线。
我们建立了一个最优规划模型，在给定游览景点个数的情况下以人均总费用最小为目标。
再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。
推荐方案：
成都→都江堰→青城山→丹巴→乐山→成都，人均费用为949元（此处不考虑旅游人数对游览费用的影响）。
第二问放松时间约束，要求代表们游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。
同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为：
成都→乐山→峨眉→海螺沟→康定→丹巴→四姑娘山→青城山→都江堰→九寨沟→黄龙→成都，人均费用为3243元。
第三问要求在第一问的基础上充分考虑代表们的旅游意向，建立模型求解。
通过对附件一数据的观察，我们使用综合评判的方法，巧妙地将代表们的意愿转化为对相应旅游景点的权重，再对第一问的模型稍加修改，编程求出对应不同景点数的最佳路线。
推荐路线：
成都→乐山→都江堰→青城山→丹巴→成都，人均费用为927元。
对于第四问，由于参观景点的人数越多每人承担的费用越少，因此我们要考虑的是尽量使得两组代表在共同旅游的时间内在相同的景点游览。
正是基于此，我们建立模型求解。
推荐路线：
第一组：
成都→乐山→丹巴→都江堰→青城山→成都第二组：
成都→都江堰→青城山→峨眉→乐山→成都，两组在都江堰会合并且共同游览了都江堰和青城山，人均费用为971元。
第五问中，首先我们修改了不合理数据，并用SPSS软件对缺省数据进行了时间序列预测。
其次我们合理定义了阴雨天气带来的损失，以人均总花费最小和阴雨天气带来的损失最小为目标，建立加权双目标规划模型。
推荐路线：
成都→康定→青城山→都江堰→乐山→成都，相应人均消费987元，阴雨天气带来的损失为1.6。
本文思路清晰，模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，SPSS预测，这样给处理数据带来了不少的方便。
本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。
此外，本文建立的模型具有很强普适性，便于推广。
关键词：
最佳路线TCP问题综合评判景点个数最小费用
1问题重述
今年暑假，西南交通大学数学系要召开“××学术会议”，届时来自国内外的许多著名学者都会相聚成都。
在会议结束后，主办方希望能安排这些远道而来的贵宾参观四川省境内的著名自然和人文景观，初步设想有如下线路可供选择：
一号线：
成都→九寨沟、黄龙；
二号线：
成都→乐山、峨嵋；
三号线：
成都→四姑娘山、丹巴；
四号线：
成都→都江堰、青城山；
五号线：
成都→海螺沟、康定；
每条线路中的景点可以全部参观，也可以参观其中之一。
不仅如此，一起参观景点的人数越多，每人承担的费用也会越小。
结合上述要求，请你回答下列问题：
一、请你们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。
二、如果有一些会议代表的时间非常充裕（比如一个月），他们打算将上述旅游景点全部参观完毕后才离开四川，请你们为他们设计合适的旅游路线，使在四川境内的交通费用尽量地节省。
三、主办方在会议开始前对所有参会的100位代表旅游意向进行了调查，调查数据见附件1所示。
充分考虑这些代表的意愿，请你们为主办方设计代表们合适的旅游路线，使他们在会议结束后的10天时间内花最少的钱游尽可能多的地方。
四、由于会议安排原因，附件1中的后50位代表要拖后四天时间才能去旅游观光（每人旅游总时间保持不变）。
请在问题三基础上考虑时间滞后因素，为主办方设计合适的旅游路线，使代表们在10天的时间里花最少的钱游尽可能多的地方。
五、在旅游过程中最担心出现阴雨天气，这种气候环境是最不适合旅游的。
因此，在出发前，主办方询问了四川省气象局这五条旅游线路降雨的概率，具体数据见附件2。
请在问题三的基础上增加气候因素，为主办方设计合适的旅游路线，使代表们在10天的时间里花最少的钱游尽可能多的地方，同时因阴雨天气而带来的旅游不便损失降为最低。
2问题分析
2.1问题背景的理解：
根据对题目的理解我们可以知道，旅游的总费用包括交通费用和在景点游览时的费用，而在确定了要游览的景点的个数后，所以我们的目标就是在满足所有约束条件的情况下，求出成本的最小值。
2.2问题一和问题二的分析：
问题一要求我们为主办方设计合适的旅游路线，使会议代表在会议结束后的10天时间内花最少的钱游尽可能多的地方。
在这里我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。
这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。
问题二实质上是在问题一的基础上改变了时间约束，即代表们要游览所有的景点，我们完全可以使用与问题一同样的方法进行求解。
2.3问题三的分析：
问题三要求我们在问题一的基础上充分考虑代表们对各个景点的意愿来设计最佳旅游路线，而代表们的意愿由附件1给出。
对于意愿，我们的做法是将其转化为相应的权重，然后乘以相应的旅游景点的花费，再利用问题一的模型得出几种最佳方案供主办方选择。
2.4问题四和问题五的分析：
问题四将100名代表平均分成了两组，而第二组则晚了四天出发。
由于题目中告诉我们参观景点的人数越多，每人承担的费用越少，因此我们应该考虑使两组同时在外旅游是尽量在同一景点游览，来减少旅游总费用。
基于此思想建立模型求解即可。
问题五在问题三的基础上考虑了天气的因素，因为阴雨会给代表们带来一定的损失，因此该问又增加了一个使损失最小的目标。
我们在定义这个损失后，对总费用和损失两个目标分别加权，以最小为目标求出相应的方案即可。
3模型假设
1.所给的5条路线每条路线中的景点可以全部参观，也可以参观其一；
2.参观景点的人数越多，每人承担的费用越少；
3.数学系使用旅游大巴安排代表们往返于各个旅游景点，其交通费用、在景点的花费、在景点的逗留时间参照当地客运公司及旅行社的数据；
4.代表们所乘坐的旅游大巴平均时速为50km/h，平均费用为0.3元/km；
5.一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地，而并不进行游览；
6.在限定的时间内，代表们最终要返回成都，并且假设成都是代表们肯定要去的一个旅游景点；
7.假设参观景点的人数每增加一人，每个代表在景点的费用就减少原价的1‰；
8.代表们在途中和游览景点的时间为12小时，而另外12小时为休息、用餐及其他琐事时间。
4符号说明
——第个或者第个景点，，=1，2，……，11；
分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定；
——每个会议代表的旅游总花费；
——每个会议代表在第个景点的逗留时间；
——每个会议代表在个景点的总消费；
——从第个景点到第个景点路途中所需时间；
——从第个景点到第个景点所需的交通费用；
5模型建立及求解
5.1问题一：
5.1.1目标函数的确立：
经过对题目分析，我们可以知道本题所要实现的目标是，使会议代表在10天时间内花最少的钱游览尽可能多的地方。
显然，花费最少和游览的景点尽量多是该问题的两个目标。
因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。
这样最终会得出几种旅游路线，而组织方可以根据自己的实际情况进行选择。
游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。
我们定义：
——每个代表的旅游总花费；
——每个代表的交通总费用；
——每个代表的旅游景点的花费；
从而得到目标函数：
Min＝＋
（1）交通总花费
因为表示从第个景点到第个景点所需的交通费用，而是判断代表们是否从第个景点直接到第个景点的0—1变量，因此我们可以很容易的得到交通总费用为：
（2）旅游景点的花费
因为表示会议代表们在个景点的总消费，也可以表示出代表们是否到达过第个和第个景点，而整个旅游路线又是一个环形，因此实际上将代表们在所到景点的花费计算了两遍，从而我们可得旅游景点的花费为：
从而我们可以得到目标函数为：
Min＝＋
＝+
5.1.2约束条件：
①时间约束
由题目可知，代表们在川的旅游时间应该不多于10天（120小时），而这些时间包括在路途中的时间和在旅游景点逗留的时间。
因为表示从第个景点到第个景点路途中所需时间，所以路途中所需总时间为；表示会议代表们在第个景点的逗留时间，故代表们在旅游景点的总逗留时间为。
因此，总的时间约束为：
+120
②旅游景点数约束
根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此即表示代表们旅游的景点数，这里我们假定要旅游的景点数为（=2，3，……，11）。
因此旅游景点数约束为：
（=2，3，……，11）
③0——1变量约束
我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。
对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。
因此可得约束：
（，=1，2，……，11）
当时，因为成都是出发点，所以；
时，因为代表们最终要回到成都，所以。
综合以上可知，
（，=1，2，……，11）
同样，当，时，根据题意不可能出现，即不可能出
现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。
因此我们可得约束：
（，=2，3，……，11）
5.1.3模型建立：
综上所述，我们可以得到总的模型为：
Min＝＋
＝+
约束条件：
+120
（=2，3，……，11）
（，=1，2，……，11）
（，=2，3，……，11）
5.1.4模型求解与结果分析：
在这里我们引入以下符号：
——第个景点和第个景点之间的路程；
——代表们所乘坐的旅游大巴的平均时速，=50km/h；
——代表们所乘坐的旅游大巴的平均费用，=0.3元/h；
通过上网查询资料，我们可以得到的具体值，根据公式=/可得到相应的，同样根据公式=×可以得到相应的（，=1，2，……，11）。
（、和的具体数值见附录）
同样，通过对四川的一些旅行社进行咨询，我们得出会议代表们在第个景点的最佳逗留时间和他们在第个景点总消费：
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
7
24
18
12
36
30
12
9
15
24
17
（单位：
小时）
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
120
423
300
135
378
390
175
90
148
303
241
（单位：
元）
从而根据模型，使用Lingo编程，得出结果如下表：
旅游景点数n
2
3
4
每人总花费m（单位：
元）
250
406
623
路线
1→8→1
1→9→8→1
1→4→8→9→1
旅游景点数n
5
6
每人总花费m
（单位：
元）
949
1207
路线
1→8→9→7→4→1
1→4→11→7→9→8→1
旅游景点数n
7
每人总花费m（单位：
元）
1534
路线
1→4→10→11→7→9→8→1
（其中数字1—11分别表示成都、九寨沟、黄龙、乐山、
峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定）
对于上述结果，我们的推荐为：
路线一：
成都→乐山→都江堰→青城山→成都
旅游景点数：
4人均费用：
623元；
路线二：
成都→都江堰→青城山→丹巴→乐山→成都
旅游景点数：
5人均费用：
949元；
路线三：
成都→乐山→康定→丹巴→青城山→都江堰→成都
旅游景点数：
6人均费用：
1207元。
5.2问题二
5.2.1目标函数的确立：
此问与第一问大同小异，不同的是代表们要完成所有景点的旅游，而目标函数是求最少的交通费。
由第一问结论可知，交通费用为：
因此，该问题的目标函数为：
Min
5.2.2约束条件：
①时间约束
该问与上一问相比，放宽了对时间的要求，不妨可以假定限制的时间为一个月（360个小时），同上一问可得：
+360
②旅游景点数约束
由题目要求可知，因为代表们时间充裕，因此他们打算游览完全部11个景点。
由第一问知道表示代表们游览的景点总数，因此该约束为：
（，=1，2，……，11）
③0——1变量约束
根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此我们可以把整个路线看做一个Hamilton圈，这样该问题就归结为货郎担（TSP）问题，当然前提是我们已经知道了要旅游所有的景点。
因此，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。
用公式表示即为：
（，=1，2，……，11）
同样，当，时，根据题意不可能出现，即不可能出
现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。
因此我们可得约束：
（，=2，3，……，11）
5.2.3模型建立：
综上所述，我们可以得到总的模型为：
Min
约束条件：
+360
（，=1，2，……，11）
（，=1，2，……，11）
（，=2，3，……，11）
5.2.4模型求解与结果分析：
根据模型，使用Lingo编程，得出结果为：
旅游景点数n
11
每人总花费m
（单位：
元）
3243
路线
成都→乐山→峨眉→海螺沟→康定→丹巴→四姑娘山→青城山→都江堰→九寨沟→黄龙→成都
5.3问题三
5.3.1目标函数的确立
5.3.1.1问题的再次分析
此问在第一问的基础上增加了代表们意愿这一条件，通过对附件一的观察，我们发现代表们的意愿分为“去”、“不去”和“无所谓”三种。
怎样将这些文字转换到公式中来表达代表们的意愿就成为了解决该问的关键。
在这里我们采用加权重的方式，将代表们的意愿理解为对该线路上两个景点的权重，又因为我们最终的目标是使旅游的费用最少，因此越热门的景点相应的权重也应该越低（这是因为权重越低，其与该景点的费用相乘后也越低，从而增加了对该景点游览的可能性）。
5.3.1.2数据处理
将所有的“去”替换为0，所有的“不去”替换为1，所有的“无所谓”替换为0.5，从而得到一个1005的矩阵（见附录）。
我们定义：
——第个旅游景点的权重。
由假设可知成都是代表们肯定要游览的一个景点，因此。
对其他权重进行标准化处理可得：
=0.185=0.217
=0.196=0.206
0.196
5.3.1.3确定目标函数
本文我们的做法同样是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。
这样最终会得出几种最佳方案，而组织方可以根据自己的实际情况进行选择。
游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。
又根据假设，参观景点的人数每增加一人，在景点的总费用就减少原价的1‰，由于共有100名代表，这就相当于每人在旅游景点的花费打了“九折”，因此得目标函数为：
Min=+
而所得结果所对应的每个代表的总花费为：
=+
5.3.2约束条件
①时间约束
由题目可知，代表们在川的旅游时间应该不多于10天（120小时），而这些时间包括在路途中的时间和在旅游景点逗留的时间。
因为表示从第个景点到第个景点路途中所需时间，所以路途中所需总时间为；表示会议代表们在第个景点的逗留时间，故代表们在旅游景点的总逗留时间为。
因此，总的时间约束为：
+120
②旅游景点数约束
根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此即表示代表们旅游的景点数，这里我们假定要旅游的景点数为（=2，3，……，11）。
因此旅游景点数约束为：
（=2，3，……，11）
③0——1变量约束
我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。
对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。
因此可得约束：
（，=1，2，……，11）
当时，因为成都是出发点，所以；
当时，因为代表们最终要回到成都，所以。
综合以上可知，
（，=1，2，……，11）
同样，当，时，根据题意不可能出现，即不可能出
现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。
因此我们可得约束：
（，=2，3，……，11）
5.3.3模型建立：
综上所述，我们可以得到总的模型为：
Min=+
约束条件：
+120
（=2，3，……11）
（，=1，2，……，11）
（，=2，3，……，11）
（，=2，3，……，11）
5.3.4模型求解与结果分析：
旅游景点数n
2
3
4
每人总花费c
（单位：
元）
229
370
573
路线
1→8→1
1→8→9→1
1→9→8→4→1
旅游景点数n
5
6
每人总花费c
（单位：
元）
927
1160
路线
1→4→8→9→7→1
1→4→8→9→7→11→1
旅游景点数n
7
每人总花费c
（单位：
元）
1412
路线
1→8→9→7→11→10→4→1
（其中数字1—11分别表示成都、九寨沟、黄龙、乐山、
峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定）
对于上述结果，我们的推荐为：
路线一：
成都→青城山→都江堰→乐山→成都
旅游景点数：
4人均费用：
573元；
路线二：
成都→乐山→都江堰→青城山→丹巴→成都
旅游景点数：
5人均费用：
927元；
路线三：
成都→乐山→都江堰→青城山→丹巴→康定→成都
旅游景点数：
6人均费用：
1160元。
第四问：
5.4.1
5.4.1.1问题的再次分析：
该问中，由于会议安排原因，前50名（第一组）代表先行出发旅游，而后50名代表（第二组）则拖后4天。
由假设可知，参观景点的人数越多，每人承担的费用越少，因此为了达到费用最少的目标，我们应该尽量安排两组代表在同时旅游的6天内在同样的景点旅游。
5.4.1.2数据的处理
类似上一问，我们定义：
——第个旅游景点对于第一组代表的权重；
——第个旅游景点对于第二组代表的权重。
运用与第一问同样的方法，我们可以得到：
=0
=0
5.4.1.3目标函数的确立：
此问中，我们引入以下符号：
——旅游总花费；
——第一组每个代表的交通总费用；
——第二组每个代表的交通总费用；
——第一组每个代表的旅游景点的花费；
——第二组每个代表的旅游景点的花费。
（上述四个量是假设两个组分别旅游的费用）
——两个组同时在一景点旅游比分别旅游节约的费用。
由以上的假设和符号，我们可以很容易的得到总的目标函数为：
Min=+++－
而所得结果所对应的每个代表的总花费为：
=+
定义：
从而可以推得：
又因为假设参观景点的人数每增加一人，每个代表在景点的费用就减少原价的1‰，因此可得：
=
=
（2）节约的费用
定义：
因为两组分别旅行时按照原价的95﹪收费，而两组同时在同一景点旅游时按照原价的90﹪收费，因此后者比前者便宜了定价的5﹪，因此：
5.4.2约束条件
①时间约束
由题目可知，代表们在川的旅游时间应该不多于10天（120小时），而这些时间包括在路途中的时间和在旅游景点逗留的时间。
因为表示从第个景点到第个景点路途中所需时间，所以两组代表们在路途中所需总时间分别为和；表示会议代表们在第个景点的逗留时间，故两组代表们在旅游景点的总逗留时间分别为和。
因此，总的时间约束为：
+120
+120
②旅游景点数约束
根据假设，整个旅游路线是环形，即最终代表们要回到成都，因此即表示代表们旅游的景点数，这里我们假定两组代表要旅游的景点数均为（=2，3，……，11）。
因此旅游景点数约束为：
=
③0——1变量约束
我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。
对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。
因此可得约束：
（，=2，……，11）
当时，因为成都是出发点，所以并且；
当时，因为代表们最终要回到成都，所以并且。
综合以上可知，
（，=2，……，11）
同样，当，时，根据题意不可能出现和，即不可能出现游客在两地见往返旅游，因为这样显然不满足游览景点尽量多的原则。
因此我们可得约束：
（，=2，3，……，11）
5.4.3模型建立：
综上所述，我们可以得到总的模型为：
Min=+++－
其中：
=
=
约束条件：
+120
+120
=（=2，3，……，11）
（，=1，2，……，11）
（，=2，3，……，11）
5.4.4模型求解与结果分析：
使用lingo编程，得到最佳结果：
旅游景点数n
5
每人总花费c
（单位：
元）
971
路线
第一组：
成都→乐山→丹巴→都江堰→青城山→成都
第二组：
成都→都江堰→青城山→峨眉→乐山→成都
即第一组先行出发，在游览了乐山和丹巴后前往都江堰，与第二组代表会合，两组代表共同游览了都江堰和青城山，之后第一组返回成都，而第一组则前往峨眉和乐山游览。
问题五：
在问题三的基础上我们引入以下符号：
——阴雨天气带来的旅游损失；
——代表们旅游个景点需要的最小的花费；
——代表们旅游个景点需要的最大的花费；
——代表们旅游个景点阴雨天气所带大的最小损失；
——代表们旅游个景点阴雨天气所带大的最大损失。
5.5.1目标函数的确立
5.5.1.1问题的再次分析
本问在问题三的基础上考虑了天气的因素，相应的也就增加了一个目标即：
升级会员 