黄金周旅游方案设计
摘要
本文主要解决的是去安徽旅游的最佳旅游路线的设计问题。花最少的钱游览尽可能满意度高的景点是我们追求的目标。基于对此的研究,我们建立了三个模型。
针对方案一:建立了单目标最优化模型。选定10个游览景点,在约束条件下,建立0-1规划模型,以总费用最小为目标函数。使用lingo 编程,最后求得的最小费用是:755元。具体方案为:11→7→4→6→3→2→1→10→11针对方案二:建立了单目标最优化模型。巧妙地将该问题化为TSP,以满意度为目标函数,在时间的约束条件下,运用lingo 编程,最后求得满意度是:0.86。旅游路线为:11→2→4→7→9→10→11
针对方案三:建立了多目标最优化模型。基于方案一与二,以最小费用和最大满意度为目标函数,在约束条件下,采用分层求解法,运用lingo 编程,最后得出满意度是:0.83,费用为782元。推荐路线:11→2→7→6→3→10→9→11
、
关键词:多目标最优化模型 0-1规划模型 TSP lingo求解%
!
一、问题重述
1.1问题背景
安徽是全国旅游大省,每年接纳游客上千万人次。现假设黄金周期间,你在外地读书的老同学、好朋友前来看望你,并要在安徽游玩几天,请查阅相关资料,从车费,餐饮,门票,景点满意度等多方面综合考虑,建立相关数学模型,列出一个四天三夜的游玩计划。
1.2需要解决的问题
根据对题目的理解我们可以知道,需要解决的问题是在安徽游玩四天三夜,并且综合考虑车费,餐饮,门票,景点满意度等多方面因素。所以我们的目标就是在满足所有约束条件的情况下,求出最少费用。
:
二、模型假设
假设1:旅行路线的总路程不包括在某一城市中观光旅游的路程;
假设2:旅行者在某一城市的旅游结束前往下一个目的地时,所乘坐的交通工具都是非常顺利的,不会出现被滞留等意外情况;
假设3:在乘坐交通工具的途中,不考虑除交通费用之外的其它任何费用;
假设4:任意两点之间来回路程相等;
假设5:每个景点游玩时间与满意度成正比,比例常数为k;
假设6:定义满意度为该景点客流量占总客流量的比例;
假设7:每天固定餐饮等消费为100元/天;
)
假设8:每天游玩10个小时;
。
四、问题分析
设计路线的原则是:满足旅游者的意愿;在有限的四天内尽量游玩更多的景点;尽量使费用最低。对路线安排规划的时候时刻关注以上三个目标,从而在题目要求范围内求得最优解。
4.1方案一的分析
经过对题目分析,我们可以知道本题所要实现的目标是,使游客在4天时间内花最少的钱游览尽可能多的地方。显然,花费最少和游览的景点尽量多是该问题的两个目标。因此,我们的做法是在满足相应的约束条件下,计算出在这种情况下的最小花费,这样最终会得出几种推荐旅游路线。游览的总费用由3部分组成,分别为交通总费用、在旅游景点的花费和每天的餐饮费。
4.2方案二的分析
本方案所要实现的目标是,使游客在4天时间内游览满意度高。显然,满意度高和游览的景点尽量多是该问题的两个目标。因此,我们的做法是在满足相应的约束条件下,计算出在这种情况下的最小花费。
4.3方案三的分析
》
此方案在方案一的基础上增加了代表们满意度这一约束条件。我们可以知道本题所要实现的目标是,使游客在4天时间内花最少的钱游览尽可能多的地方。显然,花费最少和游览的景点尽量多是该问题的两个目标。因此,我们的做法是在满足相应的约束条件下,计算出在这种情况下的最小花费。这样最终会得出几种推荐旅游路线,而组织方可以根据自己的实际情况进行选择。
五、数据分析
数据收集如下:
旅游过程都乘坐公交车,公交车时速40Km/小时,价格每1元/10Km;
分别表示:
;
1—白鹅岭, 2—始信峰,3—梦笔生花, 4—飞来石,5—光明顶,6—玉屏楼,7—迎客松, 8—化城寺,9—地藏禅寺, 10—肉身宝殿
各景点间的距离(Km)
黄金周各景点客流量(万人次/天)
六、模型的建立与求解
问题:比照TSP 巡回旅行商问题,建立TSP 模型,利用Lingo 和旅行商问题的结合,求出结果.
6.1 方案一:
6.1.1 目标函数的确立:
¥
我们定义:
m —每个游客的旅游总花费;
1m —每个游客的交通总费用; 2m —每个游客的旅游景点的花费; 3m —每个游客的餐饮费用;
从而得到目标函数:min m 。m 为交通总花费 因为D ij 表示从第 i 个景点到第 j 个景点距离,而 Xij 是判断代 表们是否从第 i 个景点直接到第 j 个景点的 0—1 变量,因此我们可以很容易 的得到交通总费用为:
123m m m m =++
1111
111
1X D 10ij ij i j m ===∑∑
(
1111
11
1C +C )2ij i j i j X ==∑∑(
3300m =
6.1.2 约束条件: (1)时间约束
由题目可知,游客在安徽旅游时间应该不多于 4 天(40 小时),而这些时间
包括在路途中的时间和在旅游景点逗留的时间。因为i T 表示在第 i 个景点逗留时间,所以在景点游玩总时间为:
1111
1111k ()2ij i j i j T X σσ==??=+?
?∑∑
所以路途中所需总时间为
-
()1111
211
140ij ij i j T X D ===∑∑
总的时间约束为:
()()11111111
1111
11k ()+240ij i j ij ij i j i j T X X D σσ=====+∑∑∑∑
T<40
(2)0—1 变量约束
我们可以把所有的景点连成一个圈,而把每一个景点看做圈上一个点。 对于每个点来说,只允许最多一条边进入,同样只允许最多一条边出来, 并且只要有一条边进入就要有一条边出去。因此可得约束:
j=11时,10
11
1111ij i j X ===∑∑
i=11时,10
11111
1ij j i X ===∑∑
、
无往返:
0ij ji X X =
(3)游玩景点个数限制
最多游玩安徽包括南艳湖在内的11个景点
1111
1
1
11ij
ij
i j X X
==+≤∑∑
从而我们可以得到目标函数为:
123min m m m m =++
11111111
1111
11X C +C )300
102ij ij ij i j i j i j m D X =====+∑∑∑∑+(
11
11
11
1011
1111011
1111111
1111111
1111
11
111
11.01111k ()30
240ij ij i j ij i j ij j i ij ji ij i j ij i j ij ij X X X X s t X X X X X D σσ========?+≤???=???=???=??≤????++≤?∑∑∑∑∑∑∑∑∑∑∑∑ }
6.1.3 模型的求解
通过LINGO 求解,推荐路线为:11→7→ 4→6→3→2→1→10→11
·
从南艳湖出发,第一站迎客松,第二站飞来石,第三站玉屏楼,第四站梦笔
生花,第五站始信峰,第六站白鹅岭,第七站肉身宝殿,最后回到南艳湖。
6.2方案二:
6.2.1 目标函数的确立: 最高满意度
1111
11
1ax ()2ij i j i j M X σσσ===+∑∑
6.2.2 约束条件:
(
(1)时间约束
景点逗留时间
1111
111
1k ()2ij i j i j T X σσ===+∑∑
所以路途中所需总时间为
1111
211
140ij ij i j T X D ===∑∑
总的时间约束为:
11111111
1111
11k ()+240ij i j ij ij i j i j T X X D σσ=====+∑∑∑∑
30T ≤
\
(2)0—1 变量约束
j=11时,1011
1111ij i j X ===∑∑
i=11时,10
11
111
1ij j i X ===∑∑
0ij ji X X =
最多游玩包括南艳湖在内的11个景点:
1111
1
1
11ij
ij
i j X X
==+≤∑∑
从而我们可以得到目标函数为:
,
1111
11
1ax ()2ij i j i j M X σσσ===+∑∑
6.2.4 模型求解
根据模型,使用 Lingo 编程,得出结果为:11→2→4→7→9→10→11
从南艳湖出发,第一站始信峰,第二站飞来石,第三站迎客松,第四站地藏禅寺,第五站肉身宝殿,最后回到南艳湖。
11
11
11
1011
1111011
1111111
1111111
1111
11
111
11.01111k ()30
240ij ij i j ij i j ij j i ij ji ij i j ij i j ij ij X X X X s t X X X X X D σσ========?+≤???=???=???=??≤????++≤?∑∑∑∑∑∑∑∑∑∑∑∑ %
6.3方案三
6.3.1 目标函数的确立 6.3.2 约束条件: (1)时间约束
景点逗留时间:
1111
111
1k ()2ij i j i j T X σσ==??=+??∑∑ 所以路途中所需总时间为:
()1111
211140ij ij i j T X D ===∑∑
$
总的时间约束为:
()()11111111
1111
11k ()+240ij i j ij ij i j i j T X X D σσ=====+∑∑∑∑
30T ≤
(2)0—1 变量约束
j=11时,10
11
1111ij i j X ===∑∑
i=11时,10
11111
1ij j i X ===∑∑
0ij ji X X =
~
(3)最多游玩包括南艳湖在内的11个景点:
1111
1
1
11ij
ij
i j X X
==+≤∑∑
(4)满意度约束
满意度与客流量成正比:
1111
11
1()0.82ij i j i j X σσσ===+≥∑∑
从而得到目标函数:
123min m m m m =++
11111111
1111
11X C +C )300102ij ij ij i j i j i j m D X =====+∑∑∑∑+(
《
11
1111
1111
1111111
1111111
1111111111111
111111
111
11.0
111()0.8211k ()30
240ij ij i j ij i j ij j i ij ji ij i j ij i j i j ij i j ij ij X X X X s t X X X X X X D σσσσ==========?+≤???=???=???
=???≤???+≥??
?++≤??∑∑∑∑∑∑∑∑∑∑∑∑∑∑ 6.3.3 模型的求解
通过LINGO 求解,推荐路线为:11→2→7→6→3→10→9→11
从南艳湖出发,第一站始信峰,第二站迎客松,第三站玉屏楼,第四站梦笔生花,第五站肉身宝殿,第六站地藏禅寺,最后回到南艳湖。
6 模型的评价、改进及推广
6.1.模型的评价
【
1.本文思路清晰,模型恰当,得出的方案合理;
2.本文成功的使用了 0—1 变量,使模型的建立和编程得以顺利进行;
3.在第二问中采用了 TCP 算法,简化了模型的求解难度;
4.由于数据庞大,对程序的要求很高,尽管经过了检验,但结果依然比较粗糙,
有待进行进一步的改进。
6.2.模型的与推广
1.实际情况中,两景点之间可能还有出公路外其他交通方式,如航班、铁路,增加这些考虑后,结果会更加合理。
2.因数据资料搜集的不完整,准确性也有待商榷,而且没有对最终方案进行更为细致的讨论研究,这些方面有待改进。
7 参考文献
[1].姜启源、谢金星、叶俊《数学模型(第三版)》北京:高等教育出版社,2003。
[2].高惠璇《应用多元统计分析》北京大学出版社,2005。
[3].朱晓临《数值分析》安徽:中国科学技术大学出版社,2010。
8 附录
附录清单:附录 1 为搜集的一些数据附录 2 为相关程序及运行结果
程序如下:
model:
sets:
h/1..11/:b;!b是门票费用;
n/1..11/:r,a;!r表示客流量百分比;
link(h,n):x,d;
endsets
data:
a=20 60 180 105 20 67 67 55 67 67 0;
b=20 60 180 105 20 67 67 55 67 67 0;
r=0.1169 0.0858 0.1558 0.1827 0.0637 0.0997 0.0798 0.0367 0.084 0.0949 0;
d=0 21.2 67.8 39.2 43.3 6 5.9 100.7 14 4.8 4.1
21.2 0 50.5 22.2 20.6 15.1 15.5 25.7 27.1 16.4 25.8
67.8 50.5 0 34.2 32.5 65.8 65.7 85.5 68.8 64.6 26.2
39.2 22.2 34.2 0 8.50 36.7 36.6 67.9 39.7 35.4 38.2
43.3 20.6 32.5 8.50 0 39.3 39.2 67.4 42.3 38.1 42.4
6 15.1 65.8 36.
7 39.3 0 0.34 100.7 11.9 1.2 10.6
5.9 15.5 65.7 3
6.6 39.2 0.34 0 100.5 11.8 11.1 10.5
100.7 25.7 85.5 67.9 67.4 100.7 100.5 0 104.3 100.1 102.5
14 27.1 68.8 39.7 42.3 11.9 11.8 104.3 0 41.2 13
4.8 16.4 64.6 3
5.4 38.1 1.2 1.1 100.1 41.2 0 9.4
4.1 2
5.8 2
6.2 38.2 42.2 10.6 10.5 102.5 13 9.4 0;
enddata
min=@sum(link(i,j):x(i,j)*(b(i)+a(j)))/2+@sum(link:d*x)/2+300; @for(link:@bin(x));
@for(link:@sum(n(j):x*20*r(j))<=30);
@for(n(j):@sum(h(i):x)=1);
@for(h(i):@sum(n(j):x)=1);
end