最佳旅游路线设计摘要本文主要研究最佳旅游路线的设计问题。
在满足相关约束条件的情况下,花最少的钱游览尽可能多的景点就是我们追求的目标。
基于对此的研究,建立数学模型,设计出最佳的旅游路线。
第一问给定时间约束,要求为主办方设计合适的旅游路线。
我们建立了一个最优规划模型,在给定游览景点个数的情况下以人均总费用最小为目标。
再引入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 符号说明i ,j ——第i 个或者第j 个景点, i ,j =1,2, (11)分别表示成都、九寨沟、黄龙、乐山、峨嵋、四姑娘山、丹巴、都江堰、青城山、海螺沟、康定;c ——每个会议代表的旅游总花费;i t ——每个会议代表在第i 个景点的逗留时间; i c ——每个会议代表在i 个景点的总消费;ij t ——从第i 个景点到第j 个景点路途中所需时间;ij c ——从第i 个景点到第j 个景点所需的交通费用;⎩⎨⎧=01ij r其他个景点个景点到达第代表们直接从第j i 5 模型建立及求解5、1 问题一:5、1、1 目标函数的确立:经过对题目分析,我们可以知道本题所要实现的目标就是,使会议代表在10天时间内花最少的钱游览尽可能多的地方。
显然,花费最少与游览的景点尽量多就是该问题的两个目标。
因此,我们的做法就是在满足相应的约束条件下,先确定游览的景点数,然后计算出在这种情况下的最小花费。
这样最终会得出几种旅游路线,而组织方可以根据自己的实际情况进行选择。
游览的总费用由2部分组成,分别为交通总费用与在旅游景点的花费。
我们定义:m ——每个代表的旅游总花费;1m ——每个代表的交通总费用;2m ——每个代表的旅游景点的花费; 从而得到目标函数: Min m ＝1m ＋2m (1)交通总花费因为ij c 表示从第i 个景点到第j 个景点所需的交通费用,而ij r 就是判断代表们就是否从第i 个景点直接到第j 个景点的0—1变量,因此我们可以很容易的得到交通总费用为:∑∑==⨯=1111111i j ij ij c r m(2)旅游景点的花费因为i c 表示会议代表们在i 个景点的总消费,ij r 也可以表示出代表们就是否到达过第i 个与第j 个景点,而整个旅游路线又就是一个环形,因此()∑∑==+⨯111111i j jiijc c r 实际上将代表们在所到景点的花费计算了两遍,从而我们可得旅游景点的花费为:()∑∑==+⨯⨯=111111221i j j i ij c c r m从而我们可以得到目标函数为:Min m ＝1m ＋2m＝∑∑==⨯111111i j ij ij c r +()∑∑==+⨯⨯11111121i j j i ij c c r5、1、2 约束条件:①时间约束由题目可知,代表们在川的旅游时间应该不多于10天(120小时),而这些时间包括在路途中的时间与在旅游景点逗留的时间。
因为ij t 表示从第i 个景点到第j 个景点路途中所需时间,所以路途中所需总时间为∑∑==⨯111111i j ij ij t r ;i t 表示会议代表们在第i 个景点的逗留时间,故代表们在旅游景点的总逗留时间为()∑∑==+⨯⨯11111121i j j i ij t t r 。
因此,总的时间约束为: ∑∑==⨯111111i j ij ij t r +()∑∑==+⨯⨯11111121i j j i ij t t r ≤120 ②旅游景点数约束根据假设,整个旅游路线就是环形,即最终代表们要回到成都,因此∑∑==111111i j ijr即表示代表们旅游的景点数,这里我们假定要旅游的景点数为n (n =2,3,……,11)。
因此旅游景点数约束为:∑∑===111111i j ijn r(n =2,3, (11)③0——1变量约束我们可以把所有的景点连成一个圈,而把每一个景点瞧做圈上一个点。
对于每个点来说,只允许最多一条边进入,同样只允许最多一条边出来,并且只要有一条边进入就要有一条边出去。
因此可得约束:=∑iij r 1≤∑jij r (i ,j =1,2, (11)当1=i 时,因为成都就是出发点,所以11=∑=i ij r ;1=j 时,因为代表们最终要回到成都,所以11=∑=j ij r 。
综合以上可知,=∑i ijr1≤∑jijr(i ,j =1,2, (11)11=∑=i ijr11=∑=j ij r同样,当i ,2≥j 时,根据题意不可能出现1==ji ij r r ,即不可能出现游客在两地间往返旅游,因为这样显然不满足游览景点尽量多的原则。