云南自驾游最优路线设计摘要：大众旅游时代的到来，使旅游日益成为现代人类社会主要的生活方式和社会经济活动，旅游业以其强劲的势头成为全球经济产业中最具活力的“朝阳产业”。

随着社会生产力不断发展，劳动生产率不断提高，以及人们生活水平的迅速提高和带薪假期的增加，旅游业将持续高速度发展，成为世界最重要的经济部门之一。

目前旅游业在我省得到了迅速健康的发展，并极大的促进了我省经济的发展。

随着我国国民可支配收入和闲暇时间的增多，国内旅游需求日益扩大。

这将为我省旅游业提供更大的发展空间。

本文对云南几大著名旅游景区的消费等方面进行了讨论，在满足相关约束条件的情况下，设计线路最短、费用最低的旅游线路。

基于对此的研究，建立数学模型（运用图论模型得出最短路程，再运用非线性规划软件进行求解），从而设计出最佳的旅游路线。

关键词：最短路线最少费用最优设计 lingo求解决策变量一、问题重述云南是我国的旅游大省，拥有丰富的旅游资源，吸引了大批的省外游客，旅游业正在成为云南的支柱产业。

随着越来越多的人选择到云南旅游，旅行社也推出了各种不同类型的旅行路线，使得公众面临多条线路的选择问题。

问题：某一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发，并最终返回昆明。

请你选择以下两种旅行方式之一为他设计一条在云南旅游的最佳路线（要有清晰的评价说明）。

1、旅行者采取自驾游的旅行方式。

2、旅行者可以根据不同情况自由选择交通方式，比如乘飞机、乘汽车、乘火车。

二、问题分析时间允许的情况下，着重分析昆明、楚雄、大理、丽江、香格里拉、临沧、思茅、西双版纳、玉溪、曲靖几大旅游景区之间的距离，找出最短的旅游路线达到用时最短，花钱最少的目的，由此得出最佳的旅游路线。

根据（附录1）可大致得出云南各旅游景区分布图的距离赋权图（如图1所示）。

进而得出最短旅游路线，运用非线性规划求出用时最短，花钱最少的旅游路线即可。

把每个旅游景区看作是图1中的顶点vi,i=1,2,…，10,把每个旅游景区间的公路看成边，两景区间的距离看作边上的权值，则云南的旅游路线图可看成是一个赋权图或网络。

求最佳旅游路线就转化成了对应旅游路线图中的闭路径。

此题为一推销员问题，可将其转化为求一赋权完全图的最优哈密尔顿回路问题。

三、模型假设1）我们只考虑这10个旅游景区的情况，到达每个旅游景区可以游览全部的旅游景点，也可以不全部游览，但游览景点总数不少于20；2）假设旅游者在云南旅游的时间最多不超过一个月，时间不允许情况下不超过10天；3）假定油价7.5元/升，每升油可供汽车行驶20公里；4）没有阴雨天气，汽车匀速行驶，且时速为80公里/小时；5）旅游者每次都能正确到达下一旅游景区，没有迷路的情况；6）路上没有车抛锚现象，且不计加油时间；7）在考虑最短路线时，所截取的路线均是直线，不涉及实际路线要求；8）到达每个旅游景区只游览一次，可重复经过同一条路线；9）忽略景区内4个景点间的距离，即：不计景点间的交通费；10）本文只考虑自驾的旅游路线。

四、符号说明i ,j ——第i 个或者第j 个景点，i ，j =1，2， (10)分别表示昆明、楚雄、大理、丽江、香格里拉、临沧、思茅、西双版纳、玉溪、曲靖；j i v v ,——网络中任意两个顶点；ij d ——i v 到j v 的距离；m i v ——第i 个景区的第m 个景点；ij t ——表示从第i 个景区到第j 个景区路途中所需时间；m i t ——表示旅游者在第i 个景区的第m 个景点的逗留时间； i t ——表示旅游者在第i 个景区的逗留时间()k c ——任一条旅游路线；w ——每个旅游者的旅游总花费；i w ——每个旅游者在第i 个景区的总消费；m i w ——每个旅游者在第i 个景区的第m 个景点的总费用； ij w ——从第i 个景点到第j 个景点所需的交通费用；⎩⎨⎧其他个景点旅游个景区的第旅游者到第01m i r m i ； ⎩⎨⎧=01ij r 其他个景点个景点到达第旅游者直接从第j i 。

五、模型建立方案一：消费最少路线。

根据给定的时间约束，以费用最小为目标，我们建立了一个最优规划模型。

再根据引入的0—1变量表示是否游览某个景区，从而推出交通费用和景区花费的函数表达式，给出相应的约束条件，使用lingo 编程对模型求解，得到最优规划。

游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。

我们定义：w ——每个旅游者的旅游总花费；w '——每个旅游者在旅游景点的花费；w ''——每个旅游者的交通总费用；从而得到目标函数： Min w ＝w ''＋w '（1）旅游景区的总花费因为i w ，j w 表示旅游者在i 个景区和在第j 个景区的总消费，m i w ，m j w 表示旅游者在第i 个景区和在第j 个景区的第m 个景点的花费，m i r ，m j r 表示出旅游者是否去第i 个景区和在第j 个景区的第m 个景点的0—1变量，则∑==41m m i m i i r w w ，∑==41m m j m j j r w w ，即旅游者在旅游景区的总花费为：∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯='101101414121i j m m j m j m m i m i ij r w r w r w （2）交通总花费由于ij w 表示从第i 个景区到第j 个景区所需的交通费用，而ij r 表示旅游者是否从第i 个景区直接到达第j 个景区的0—1变量，因此可以得到交通总费用为：∑∑==⨯=''101101i j ij ij w r w (ij j i t w 30=)从而我们可以得到目标函数为：Min w ＝w '＋w ''＝∑∑==⨯101101i j ij ij w r +∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯101101414121i j m m j m j m m i m i ij r w r w r ①时间约束时间包括在路途中需要的时间和在旅游景点逗留的时间。

因为ij t 表示从第i 个景区直达第j 个景区路途中所需时间，所以路途中所需总时间为∑∑==⨯101101i j ij ij t r ；i t 表示旅游者在第i 个景区的逗留时间， m i t ，m j t 表示旅游者在第i 个景区和第j 个景区的第m 个景点的逗留时间，m i r ，m j r 表示出旅游者是否去第i 个景区和第j 个景区的第m 个景点的0—1变量， 则 ∑==41m m i m i i t r t ，∑==41m m j m j j t r t故旅游者在旅游景区的总逗留时间为∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯101101414121i j m m j m j m m i m i ij t r t r r 因此，总的时间约束为：∑∑==⨯101101i j ij ij t r +∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯101101414121i j m m j m j m m i m i ij t r t r r ≤240 ②旅游景区数约束根据题目假设知，旅游者从昆明出发最终要回到昆明，整个旅游路线是环形，故旅游者旅游的景区数为∑∑==101101i j ij r ，这里我们假定要旅游的景区数为n （n =2，3，……，10）。

因此旅游景区数约束为：∑∑==101101i j ij r =n （n =2，3， (10)③0——1变量约束我们可以把所有的景区连成一个圈，而把每一个景区看做圈上一个点。

对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。

因此可得约束：=∑i ij r1≤∑j ij r （i ，j =1，2， (10)当1=i 时，因为昆明是出发点，所以11=∑=i ij r ；当1=j 时，因为代表们最终要回到昆明，所以11=∑=j ij r 。

综合以上可知，=∑iij r1≤∑j ij r （i ，j =1，2，……，10） 11=∑=i ij r 11=∑=j ij r 同样，当i ，2≥j 时，假设不可能出现1==ji ij r r ，即不可能出 现旅游者在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。

因此我们可得约束：0=⨯ji ij r r （i ，j =2，3， (10)综上所述，我们可以得到总的模型为：Min w ＝w '＋w ''＝∑∑==⨯101101i j ij ij w r +∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯101101414121i j m m j m j m m i m i ij r w r w r约束条件：1) ∑∑==⨯101101i j ij ij t r +∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯101101414121i j m m j m j m m i m i ij t r t r r ≤240 2) ∑∑==101101i j ij r =n （n =2，3， (10)3) =∑i ij r 1≤∑jij r （i ，j =1，2， (10)4) 11=∑=i ij r 11=∑=j ij r5) 0=⨯ji ij r r （i ，j =2，3， (10)方案二：线路最短方案。

放松时间约束，旅游者可以游遍所有的景区，该思路也就成了典型的推销员（TSP ）问题。

以游览的景点多，用时最少，消费最低为目标，建立模型，使用lingo 软件求解得到最佳旅游路线。

要完成所有景区的旅游，而目标函数是求最少的交通费。

由方案一的结论可知，旅游者所要出的总交通费用为：∑∑==⨯=''101101i j ij ij w r w （ij j i t w 30=）因此，该问题的目标函数为：Min ∑∑==⨯=''101101i j ij ij w r w （ij j i t w 30=）①时间约束在这我们放松对时间的要求，我们不妨假定时间限制为一个月（720个小时），因此可得时间约束为：∑∑==⨯101101i j ij ij t r +∑∑∑∑====⎪⎭⎫ ⎝⎛+⨯⨯101101414121i j m m j m j m m i m i ij t r t r r ≤720 ②旅游景区数约束假定旅游者时间充裕，因此旅游者可以游览完全部10个景区。

由方案一知道∑∑==101101i j ij r 表示旅游者游览的景区总数，因此该约束为：10101101=∑∑==i j ij r (i ，j =1，2， (10)③旅游景点数约束假定在旅游者游览10个景区的前提下必须游览的总景点数必须不小于于20，因为m i r 表示出旅游者是否去第i 个景区的第m 个景点的0—1变量，故得到此约束为：2010141≥∑∑=-i m m i r ;总的旅游景区有10个，而一个景区有4个景点，所以旅游者游览的景点数不会超过40，即又得约束为：4010141≤∑∑=-i m m i r.④0——1变量约束根据假设，整个旅游路线是环形，即最终旅游者要回到昆明，因此我们可以把整个路线看做一个Hamilton （哈密尔顿）圈，这样该问题就归结为货郎担（TSP ）（哈密尔顿）问题，当然前提是我们已经知道了要旅游所有的景点。