北京市旅游线路的最优设计毕业设计论文.doc

论文成绩：

北京市旅游线路的最优设计

队 别：一队一区队
姓 名：高勇吉 陆豪 韩枫
时 间：2016年6月25日

防化学院

北京市旅游线路的最优设计

摘 要：本文主要解决的是去北京旅游的最佳旅游路线的设计问题。针对一日游，二日游，三日游花最少的钱，基于对此的研究，我们建立了三个模型。
针对方案一：建立了单目标最优化模型。分别以一日游，二日游，三日游为目标，在北京市选定11个游览点，在约束条件下，建立0-1规划模型，以总费用最小为目标函数。使用 lingo 编程，最后求得的最小费用分别是：668元，1134元,1745元。具体方案为： 2→1→11，2→1→11→5→6，2→1→11→5→6→4→3→9
针对方案二：建立了单目标最优化模型。以满意度为目标函数，在时间的约束条件下，运用lingo 编程，最后针对一日游，二日游，三日游分别求得满意度是：0.96,0.93,0.89。旅游路线为： 2→4→3, 11→2→1→3→9, 2→1→11→9→10→5→4→3
关键词：多目标最优化模型 0-1规划模型 TSP lingo求解
一、 问题重述
1.1问题背景
北京是全国著名旅游城市，每年接纳游客上千万人次。现假设黄金周期间，在外地读书的老同学、好朋友会过来北京游玩。根据不同游客的要求标准，对以下三种旅游：
1.一日游
2.二日游
3.三日游
设计出最佳的旅游路线。
1.2需要解决的问题
根据对题目的理解我们可以知道，需要解决的问题是在北京游玩天数，并且综合考虑车费，餐饮，门票 ，景点满意度等多方面因素。所以我们的目标就是针对不同游玩天数求出最少费用，以及针对满意度做出最佳旅游线路。

二、模型假设
假设1：旅行路线的总路程只包括在北京中观光旅游的路程；

假设2：旅行者在北京的某一旅游景点游玩结束前往下一个景点时，所乘坐的交通工具都是非常顺利的，不会出现被滞留等意外情况；

假设3：在乘坐交通工具的途中，不考虑除交通费用之外的其它任何费用；

假设4：任意两点之间来回路程相等；

假设5：每个景点游玩时间与满意度成正比，比例常数为k；

假设6：定义满意度为针对本次该景点游客满意人数占总游客人数的比例；

三、 符号说明

符号
符号说明

旅游者在第i个景点的逗留时间

第i个景点门票

第i个景点到第j个景点的距离

=0表示景点i和景点j不连接
=1表示景点i和景点j连接

景点i的满意度

四、问题分析
设计路线的原则是：满足旅游者的意愿；在有限的时间内尽量游玩更多的景点；尽量使费用最低。对路线安排规划的时候时刻关注以上三个目标，从而在题目要求范围内求得最优解。
4.1方案一的分析
经过对题目分析，我们可以知道本题所要实现的目标是，使游客在有限时间内花最少的钱游览尽可能多的地方。显然，花费最少和游览的景点尽量多是该问题的两个目标。因此，我们的做法是在满足相应的约束条件下，计算出在这种情况下的最小花费，这样最终会得出几种推荐旅游路线。游览的总费用由3部分组成，分别为交通总费用、在旅游景点的花费和每天的餐饮费。
4.2方案二的分析
本方案所要实现的目标是，使游客在有限时间内游览满意度高。显然，满意度高和游览的景点尽量多是该问题的两个目标。

五、数据分析
数据收集如下：
旅游过程都乘坐公交车，公交车时速40Km/小时，价格每1元/10Km；
分别表示：
1—故宫， 2—天安门广场，3—天坛， 4—颐和园，5—长城，6—十三陵水库， 7—鸟巢水立方外景， 8—恭王府，9—清华北大， 10—圆明园， 11-北海公园
各景点间的距离（Km）

1
2
3
4
5
6
7
8
9
10
11
1
0
0.3
4.9
17.4
81.8
44.6
9.2
2.2
14.2
14.6
0.86
2
0.3
0
4.6
12.5
64.4
37.2
35.4
7.0
12.0
0.4
13.14
3
4.9
4.6
0
12.5
76.9
39.7
4.3
2.7
9.3
9.7
3.04
4
17.4
12.5
12.5
0
64.4
27.2
8.2
15.2
3.2
2.8
16.54
5
81.8
64.4
76.9
64.4
0
37.2
72.6
79.6
67.6
67.2
80.94
6
44.6
37.2
39.7
27.2
37.2
0
35.4
42.4
30.4
30.8
43.74
7
9.2
35.4
4.3
8.2
72.6
35.4
0
7.0
5.0
5.4
8.34
8
2.2
7.0
2.7
15.2
79.6
42.4
7.0
0
12.0
12.4
1.34
9
14.2
12.0
9.3
3.2
67.6
30.4
5.0
12.0
0
0.4
13.14
10
14.6
0.4
9.7
2.8
67.2
30.8
5.4
12.4
0.4
0
13.54
11
0.86
3.04
26.2
16.54
80.94
43.74
8.34
1.34
13.14
13.54
0

各景点客流量（万人次/天）
1
2
3
4
5
6
7
8
9
10
11
30.37
29.87
21.14
22.45
23.64
12.25
24.65
17.32
10.32
28.65
26.72

各景点门票（元）
1
2
3
4
5
6
7
8
9
10
11
60
15
15
60
45
65
80
40
0
25
10

六、模型的建立与求解
问题：比照TSP巡回旅行商问题，建立TSP模型，利用Lingo和旅行商问题的结合，求出结果.
6.1 方案一：

6.1.1 目标函数的确立：
我们定义：
—每个游客的旅游总花费；
—每个游客的交通总费用；
—每个游客的旅游景点的花费；
—每个游客的餐饮费用；
从而得到目标函数： 。m为交通总花费 因为 表示从第 i个景点到第 j个景点距离，而 Xij 是判断代 表们是否从第 i个景点直接到第 j个景点的 0—1 变量，因此我们可以很容易 的得到交通总费用为：

6.1.2 约束条件：
（1）时间约束
由题目可知，游客在北京旅游时间应该不多于 3 天(30 小时)，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为表示在第 i个景点逗留时间，所以在景点游玩总时间为：

所以路途中所需总时间为

总的时间约束为：

（2）0—1 变量约束
我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。 对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来， 并且只要有一条边进入就要有一条边出去。因此可得约束：
j=11时，
i=11时，
无往返：

（3）游玩景点个数限制
最多游玩11个景点

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

6.1.3 模型的求解
通过LINGO求解，分别求出推荐路线为：2→1→11，2→1→11→5→6，2→1→11→5→6→4→3→9
6.1.4模型的结果分析
一日游，第一站天安门广场，第二站故宫，第三站北海公园。二日游第一站天安门广场，第二站故宫，第三站北海公园，第四站长城，第五站十三陵水库。三日游第一站天安门广场，第二站故宫，第三站北海公园，第四站长城，第五站十三陵水库，第六站颐和园，第七站天坛，最后到清华北大。

6.2方案二：
6.2.1 目标函数的确立：
最高满意度

6.2.2 约束条件：
（1）时间约束
景点逗留时间

所以路途中所需总时间为

总的时间约束为：

（2）0—1 变量约束
j=11时，
i=11时，

最多游玩11个景点：

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

6.2.4 模型求解
根据模型，使用 Lingo 编程，分别对一日游，二日游，三日游得出结果为：2→4→3, 11→2→1→3→9, 2→1→11→9→10→5→4→3
6.2.5模型的结果分析
一日游，第一站天安门广场，第二站颐和园，第三站天坛。二日游，第一站北海公园，第二站天安门广场，第三站故宫，第四站天坛，第五站清华北大。三日游，第一站天安门广场，第二站故宫，第三站北海公园，第四站清华北大，第五站圆明园，第六站长城，第七站颐和园，第八站天坛。

6 模型的评价、改进及推广
6.1．模型的评价
1.本文思路清晰，模型恰当，得出的方案合理；
2.本文成功的使用了 0—1 变量，使模型的建立和编程得以顺利进行；
3.在第二问中采用了 TCP 算法，简化了模型的求解难度；
4.由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然 比较粗糙，有待进行进一步的改进。
6.2．模型的与推广
1.实际情况中，两景点之间可能还有出公路外其他交通方式，如地铁，出租车， 增加这些考虑后，结果会更加合理。
2.因数据资料搜集的不完整，准确性也有待商榷，而且没有对最终方案进行 更为细致的讨论研究，这些方面有待改进。

7 参考文献
[1].姜启源、谢金星、叶俊《数学模型（第三版）》北京：高等教育出版社，2003。
[2].谢金星《优化建模与 LINDO/LINGO 软件》，北京：清华大学出版社,2005。
[3].周仁郁《SPSS13.0 统计软件》,成都，西南交通大学出版社,2005。
[4].李庆扬、王能超、易大义《数值分析》，北京：清华大学出版社版社，2001。