云南自驾游最优路线设计.doc

云南自驾游最优路线设计 摘要：大众旅游时代的到来，使旅游日益成为现代人类社会主要的生活方式和社会经济活动，旅游业以其强劲的势头成为全球经济产业中最具活力的“朝阳产业”。随着社会生产力不断发展，劳动生产率不断提高，以及人们生活水平的迅速提高和带薪假期的增加，旅游业将持续高速度发展，成为世界最重要的经济部门之一。目前旅游业在我省得到了迅速健康的发展，并极大的促进了我省经济的发展。随着我国国民可支配收入和闲暇时间的增多，国内旅游需求日益扩大。这将为我省旅游业提供更大的发展空间。本文对云南几大著名旅游景区的消费等方面进行了讨论，在满足相关约束条件的情况下，设计线路最短、费用最低的旅游线路。基于对此的研究，建立数学模型（运用图论模型得出最短路程，再运用非线性规划软件进行求解），从而设计出最佳的旅游路线。关键词：最短路线 最少费用 最优设计 lingo求解 决策变量一、问题重述 云南是我国的旅游大省，拥有丰富的旅游资源，吸引了大批的省外游客，旅游业正在成为云南的支柱产业。随着越来越多的人选择到云南旅游，旅行社也推出了各种不同类型的旅行路线，使得公众面临多条线路的选择问题。 问题：某一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发，并最终返回昆明。请你选择以下两种旅行方式之一为他设计一条在云南旅游的最佳路线（要有清晰的评价说明）。1、旅行者采取自驾游的旅行方式。2、旅行者可以根据不同情况自由选择交通方式，比如乘飞机、乘汽车、乘火车。二、问题分析时间允许的情况下，着重分析昆明、楚雄、大理、丽江、香格里拉、临沧、思茅、西双版纳、玉溪、曲靖几大旅游景区之间的距离，找出最短的旅游路线达到用时最短，花钱最少的目的，由此得出最佳的旅游路线。根据（附录1）可大致得出云南各旅游景区分布图的距离赋权图（如图1所示）。进而得出最短旅游路线，运用非线性规划求出用时最短，花钱最少的旅游路线即可。把每个旅游景区看作是图1中的顶点,i=1,2,，10,把每个旅游景区间的公路看成边，两景区间的距离看作边上的权值，则云南的旅游路线图可看成是一个赋权图或网络。求最佳旅游路线就转化成了对应旅游路线图中的闭路径。此题为一推销员问题，可将其转化为求一赋权完全图的最优哈密尔顿回路问题。3、 模型假设1）我们只考虑这10个旅游景区的情况，到达每个旅游景区可以游览全部的旅游景点，也可以不全部游览，但游览景点总数不少于20；2）假设旅游者在云南旅游的时间最多不超过一个月，时间不允许情况下不超过10天；3）假定油价7.5元/升，每升油可供汽车行驶20公里；4）没有阴雨天气，汽车匀速行驶，且时速为80公里/小时；5）旅游者每次都能正确到达下一旅游景区，没有迷路的情况；6）路上没有车抛锚现象，且不计加油时间；7）在考虑最短路线时，所截取的路线均是直线，不涉及实际路线要求；8）到达每个旅游景区只游览一次，可重复经过同一条路线；9）忽略景区内4个景点间的距离，即：不计景点间的交通费；10）本文只考虑自驾的旅游路线。四、符号说明,第个或者第个景点，=1，2，10；分别表示昆明、楚雄、大理、丽江、香格里拉、临沧、思茅、西双版纳、玉溪、曲靖；网络中任意两个顶点；到的距离；第个景区的第个景点；表示从第个景区到第个景区路途中所需时间；表示旅游者在第个景区的第个景点的逗留时间；表示旅游者在第个景区的逗留时间任一条旅游路线；每个旅游者的旅游总花费；每个旅游者在第个景区的总消费；每个旅游者在第个景区的第个景点的总费用；从第个景点到第个景点所需的交通费用； ； 。五、模型建立方案一：消费最少路线。根据给定的时间约束，以费用最小为目标，我们建立了一个最优规划模型。再根据引入的01变量表示是否游览某个景区，从而推出交通费用和景区花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解，得到最优规划。游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。我们定义：每个旅游者的旅游总花费；每个旅游者在旅游景点的花费；每个旅游者的交通总费用；从而得到目标函数： Min （1）旅游景区的总花费因为，表示旅游者在个景区和在第个景区的总消费，表示旅游者在第个景区和在第个景区的第个景点的花费，表示出旅游者是否去第个景区和在第个景区的第个景点的01变量，则，即旅游者在旅游景区的总花费为：（2）交通总花费由于表示从第个景区到第个景区所需的交通费用，而表示旅游者是否从第个景区直接到达第个景区的01变量，因此可以得到交通总费用为： ()从而我们可以得到目标函数为：Min + 时间约束时间包括在路途中需要的时间和在旅游景点逗留的时间。因为表示从第个景区直达第个景区路途中所需时间，所以路途中所需总时间为；表示旅游者在第个景区的逗留时间， ，表示旅游者在第个景区和第个景区的第个景点的逗留时间，表示出旅游者是否去第个景区和第个景区的第个景点的01变量，则 ，故旅游者在旅游景区的总逗留时间为因此，总的时间约束为：+240 旅游景区数约束根据题目假设知，旅游者从昆明出发最终要回到昆明，整个旅游路线是环形，故旅游者旅游的景区数为，这里我们假定要旅游的景区数为（=2，3，10）。因此旅游景区数约束为： = （=2，3，10） 01变量约束我们可以把所有的景区连成一个圈，而把每一个景区看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束： （，=1，2，10） 当时，因为昆明是出发点，所以； 当时，因为代表们最终要回到昆明，所以。 综合以上可知， （，=1，2，10） 同样，当，时，假设不可能出现，即不可能出现旅游者在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束： （，=2，3，10）综上所述，我们可以得到总的模型为：Min +约束条件：1) +2402) = （=2，3，10）3) （，=1，2，10）4) 5) （，=2，3，10）方案二：线路最短方案。放松时间约束，旅游者可以游遍所有的景区，该思路也就成了典型的推销员（TSP）问题。以游览的景点多，用时最少，消费最低为目标，建立模型，使用lingo软件求解得到最佳旅游路线。要完成所有景区的旅游，而目标函数是求最少的交通费。由方案一的结论可知，旅游者所要出的总交通费用为： （）因此，该问题的目标函数为：Min （）时间约束 在这我们放松对时间的要求，我们不妨假定时间限制为一个月（720个小时），因此可得时间约束为：+720旅游景区数约束 假定旅游者时间充裕，因此旅游者可以游览完全部10个景区。由方案一知道表示旅游者游览的景区总数，因此该约束为： (，=1，2，10)旅游景点数约束假定在旅游者游览10个景区的前提下必须游览的总景点数必须不小于于20，因为表示出旅游者是否去第个景区的第个景点的01变量，故得到此约束为： ;总的旅游景区有10个，而一个景区有4个景点，所以旅游者游览的景点数不会超过40，即又得约束为：.01变量约束根据假设，整个旅游路线是环形，即最终旅游者要回到昆明，因此我们可以把整个路线看做一个Hamilton（哈密尔顿）圈，这样该问题就归结为货郎担（TSP）（哈密尔顿）问题，当然前提是我们已经知道了要旅游所有的景点。因此，对于Hamilton圈中的每个点来说，只允许有一条边进入，同样，也只允许有一条边出去。问题的重点在于找出最小权Hamilton圈，称这种圈为最优圈（H圈）。设G=（V（G）,E(G)）是一无向连通图，其中，我们将无向网络用三角不等式法转化为最优哈密尔顿回路（如图2所示）。由附录4可知，则圈将是圈G的一个改进。 图1 各旅游景区分布及距离赋权图，则为巡回总距离，则，目标： 令决策变量为： 则目标： 约束条件： 用公式表示即为： （，=1，2，10）同样，当，时，我们假设不可能出现，即不可能出现游客在两地间往返旅游，因为这样显然不满足游览景区尽量多的原则。因此我们可得约束： （，=2，3，10）综上所述，做对上述分析进步变换我们据第一方案思路可以得到总的模型为：Min （）约束条件：1) +7202) （，=1，2，10）3) （，=1，2，10）4) （，=1，2，10）5) （，=2，3，10）六、模型求解通过上网查询资料，我们可以得到的具体值，根据公式=/可得到相应的，同样根据公式可以得到相应的（，=1，2，10）。（、和的具体数值见附录4、5、6） 方案一：通过对云南的一些旅行社上网进行咨询，我们得出旅游者在第个景点的最佳逗留时间和他们在第个景点总消费（如表1所示）：表1 旅游者在各景区的最佳逗留时间(单位：小时)编号景点最佳逗留时间（小时）编号景点最佳逗留时间（小时）1昆明86临沧322楚雄107思茅133大理208西双版纳254丽江349玉溪355香格里拉1010曲靖23 表2 旅游者在各景区的总消费(单位：元)340285325390350175265365245250根据模型知，该模型为非线性规划模型，因此使用Lingo软件进行求解（程序见附录2），得出结果如表3：表3 第一方案程序运行结果旅游景区数n2 3 4 人均总花费m（单位：元）342.5672.5820路线旅游景区数n5 6 人均总花费m（单位：元）7791219.5路线旅游景区数n7 每人总花费m（单位：元）1383路线旅游景区数n8 每人总花费m（单位：元）1644路线旅游景区数n9 每人总花费m（单位：元）1950路线旅游景区数n10 每人总花费m（单位：元）2253路线注：(i=1,2,，10)分别表示昆明、楚雄、大理、丽江、香格里拉、临沧、思茅、西双版纳、玉溪、曲靖.基于上述结果，我们一般推荐线路为：路线一：昆明楚雄大理丽江玉溪昆明旅游景点数：5 人均费用：155.8 元；路线二：昆明楚雄大理临沧思茅玉溪曲靖昆明 旅游景点数：7 人均费用：197.57 元；路线三：昆明楚雄大理临沧思茅西双版纳玉溪曲靖昆明旅游景点数：8 人均费用：205.5 元。方案二：线路最短方案求解。由于使用lingo求解，程序录入比较困难，因此此方案我们根据附录4的数据，使用MATLAB软件进行求解（程序见附录3），得出结果如下表：表3 第二方案程序运行结果旅游景区数n10 行驶路程（单位：公里）2398路线昆明玉溪西双版纳思茅临沧大理丽江香格里拉楚雄曲靖昆明七、模型评价及推广优点：1) 整篇文章思路比较简单，没有太多复杂的运算过程。2) 方案一，未规定必须游览的景区数以及景点数，也就是旅游者可以对任何景区进行自由选择，可去可不去。3) 方案二,在假定10个景区都必须游览，而且游览景点总数不少于20的条件下，建立模型，与现实中旅游者游览比较接近。4) 利用的数据间的对比得到结果，比起复杂的计算过程更直观，更让人容易明白。5) 求解出的最短路程，与实际路程基本保持一致。6) 提供了优化方案，以供参考，模型短小精练，有很强的推广性，可由10个旅游景区推广至个景区，旅游景点也可由4个推广至个，都可以构造连通网络进行求解，此处不再进行求解。缺点：1)数据大部分参考互联网，数据缺乏一定的准确性。 2)没有考虑旅行路线以及行驶过程中会出现的实际情况，一切均是最优考虑。 3)数据太多，列出来比较麻烦。 4)对于方案二用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。5)方案二所采用的方法已被进一步发展，圈的修改过程一次替换三条边比一次仅替换两条边更为有效。八、参考文献1 姜启源数学建模J北京：高等教育出版社，2003年2 白其峥数学建模案例分析J北京：海洋出版社，2000年3 薛毅动态规划，图论与网络模型北京：北京工业大学出版社，2005年4 陈东彦 李冬梅 王树忠，数学建模 科学出版社，2007年5 党林立 孙晓群 数学建模简明教程 西安电子科技大学出版社，2009年附录：附录1 云南旅游景区分布图 附录2方案一：消费最少路线，利用lingo 软件设计程序程序如下：Model:sets:jingdian/1.10/:c,t,l;!其中：1,2,.,10分别代表昆明、楚雄、大理、丽江、香格里拉、临沧、思茅、西双版纳、玉溪、曲靖；w，t分别表示旅行团在各景点的吃住消费和逗留时间；c表示各景点选择性权重；l是为了控制不出现两个以上环形回路而设的一个变量;links(jingdian,jingdian):r,cc,tt;!其中：r为0-1变量（0表示两景区不相连，1表示两景区相通）；cc为两景区之间的交通费用；tt为两景区之间的交通时间;endsetsdata:t=8 10 20 34 10 32 13 25 35 23;c=120 285 378 390 175 383 300 135 423 350;tt=0 2.7 4.78 9.12 11.4 9.22 7.55 9.73 1.7 2.062.7 0 2.386.72 8.95 6.98 9.98 12.12 4 4.54.78 2.38 04.58 7 6.32 8.25 14.38 6.28 6.769.12 6.72 4.58 0 3.47 10.78 12.72 18.65 10.5311.3511.4 8.95 73.47 0 13.06 15 20.95 12.83 13.39.22 6.98 6.32 10.78 13.06 05.65 7.85 9.3 11.287.55 9.98 8.25 12.72 155.65 0 14.926.03 9.179.73 12.12 14.38 18.65 20.95 7.85 14.92 0 8.28 11.431.7 4 6.28 10.53 12.83 9.3 6.03 8.28 0 3.452.06 4.5 6.76 11.35 13.3 11.28 9.17 11.43 3.450;!其中：主对角线为零,表示各景区到自身交通费用为零;cc=048113158188179158207253948050105143111170207678511350054948814021011713515810554053145193311172196188143945301832353492152281791118814518309313116619615817014019323593037981462072072103113491313701352102567117172215166981350663985135196228196164210660;!其中：主对角线为零,表示各景区到自身的交通时间为零;n=?;!其中：n表示计划游玩的景区数目;enddatamin=sum(jingdian(j):sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j);!目标函数：表示计划游玩的景区数目为n时的最小费用;for(jingdian(i):r(i,i)=0);!约束条件：表示各景点到自身没有路线相连的约束条件;for(jingdian(i)|i#ge#2:for(jingdian(j)|j#ge#2:r(i,j)+r(j,i)1);!约束条件：表示除起点（昆明）外，若旅游者从景区i到景区j去游玩（即r(i,j)=1），则不会再从景区j到景区i去游玩（即r(j,i)=0），也就是说除起点外每个景区只游玩一次;a=sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j);sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)240;!约束条件:表示总的旅行时间（交通时间和景区逗留时间）不超过给定时间10天240小时;for(jingdian(i):sum(jingdian(j):r(i,j)=sum(jingdian(j):r(j,i);for(jingdian(i)|i#eq#1:sum(jingdian(j):r(i,j)=1);for(jingdian(i)|i#ne#1:sum(jingdian(j):r(i,j)=l(i)+r(i,j)-(n-2)*(1-r(i,j)+(n-3)*r(j,i);for(jingdian(i)|i#gt#1:l(i)1+(n-2)*r(i,1);!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线；附录3 方案二：设计路线最短方案，利用MATLAB 软件求解程序如下：clc,cleara(1,2)=160;a(1,3)=377;a(1,4)=527;a(1,5)=629.4;a(1,6)=598;a(1,7)=529;a(1,8)=692;a(1,9)=86;a(1,10)=130;a(2,3)=169.3;a(2,4)=352.2;a(2,5)=478.5;a(2,6)=372.7;a(2,7)=567.3;a(2,8)=690;a(2,9)=225.5;a(2,10)=286.3;a(3,4)=183.8;a(3,5)=314;a(3,6)=296.5;a(3,7)=469.3;a(3,8)=700;a(3,9)=390.5;a(3,10)=451.2;a(4,5)=178.5;a(4,6)=484.8;a(4,7)=657.7;a(4,8)=1039;a(4,9)=574.5;a(4,10)=654.6;a(5,6)=611;a(5,7)=783.8;a(5,8)=1164.8;a(5,9)=716.7;a(5,10)=761.3;a(6,7)=312.4;a(6,8)=436.9;a(6,9)=554.1;a(6,10)=655;a(7,8)=124.7;a(7,9)=329.2;a(7,10)=547.8;a(8,9)=451.4;a(8,10)=670;a(9,10)=223.2;a(10,:)=0;a=a+a;c1=1 2:9 10;L=length(c1);flag=1;while flag0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1). a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1sum sum=sum1; circle=c1;endcircle,sum附录4 距离（单位：公里）地点昆明楚雄大理丽江香格里拉临沧思茅西双版纳玉溪曲靖昆明0160377527629.459852969286130楚雄1600169.3352.2478.5372.7567.3690225.5286.3大理377169.30183.8314296.5469.3700390.5451.2丽江527352.2183.80178.3484.8657.71039574.5654.6香格里拉629.4478.5314178.30611783.81164.8716.7761.3临沧598372.7296.5484.86110312.4436.9554.1655思茅529567.3469.3657.7783.8312.40124.7329.2