关于云南旅游路线设计的数学模型

关于云南旅游路线的设计模型第8页（共12页）关于云南旅游路线设计的数学模型张永辉常建幻段倩倩摘要：本文主要研究在云南省内的最佳旅游路线的设计问题。在满足相关约束条件的情况下，花钱最少且游览尽可能多的景点是我们追求的目标。从题目所给的条件可知，最终问题是让我们设计一条在云南省内的最佳旅游路线，基于此进行研究，建立了相应的数学模型，并通过lingo软件编程，计算出模型的结果，并结合模型进行分析，从而寻找出最佳的旅游路线，由于旅游的景点数不同，所以可以在不同的旅游数下选择出不同的旅游路线，例如，通过计算后得出，当景点数为2时，路线为1→9→1，花费为775.2，而景点数为8时，路线为1→2→15→3→14→4→11→9→1，花费为3433.1，景点数为10时，路线为1→2→15→3→13→5→14→4→11→9→1，花费为4356.5。在问题分析中，我们忽略在旅途中天气、交通等意外因素影响，所以问题与实际生活对应问题待改善。关键词：最佳路线综合评判0—1变量最小费用模型求解一、问题重述云南是我国的旅游大省，拥有丰富的旅游资源，吸引了大批的省外游客，旅游业正在成为云南的支柱产业。随着越来越多的人选择到云南旅游，旅行社也推出了各种不同类型的旅行路线，使得公众的面临多条线路的选择问题。某一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发，并最终返回昆明。请你们选择以下两种旅行方式之一为他设计一条在云南旅游的最佳路线（要有清晰的评价说明）。１、旅行者采取自驾游的旅行方式。２、旅行者可以根据不同情况自由选择交通方式，比如乘飞机、乘汽车、乘火车。二、问题分析旅游中要考虑的因素很多，我们要追求的目标是在规定的时间内花费最少但能旅游的景点多，所以我们在进行分析前对问题要做假设，假设不考虑旅游中发生的一切意外，即旅游按照所设计的路程顺利进行，在旅途中不考虑阴雨天气给旅游时间滞留带来的麻烦，并且把因为去旅游人员的多少带来门票打折的因素忽略了，在此基础上，我们通过0—1规划方法，分析并写出了目标函数，同时对假设中涉及到的问题进行约束，这样寻找不同景点数时的最优旅游路线，并对路线进行简单分析，最终得到最优的旅游线路。三、模型假设1、假设中途不发生任何堵车等交通事故以及天气等影响行程；2、在途中和游览景点的时间为12小时，而另外12小时为休息、用餐及其他琐事时间。3、在限定的时间内，游客最终要返回昆明，并且假设昆明是肯定要去的一个旅游景点。四、符号说明,——第个或者第个景点，，=1，2，…，15；分别表示昆明、楚雄、大理、保山、丽江、曲靖、西双版纳、昭通、玉溪、普洱、文山、红河、迪庆、德宏、临沧——每个游客的旅游总花费；——每个游客在第个景点的逗留时间；——每个游客在个景点的总消费；——从第个景点到第个景点路途中所需时间；——从第个景点到第个景点所需的交通费用；五、模型构成1、目标函数的确立：经过对题目分析，我们可以知道本题所要实现的目标是，使旅游者在最短时间内花最少的钱游览尽可能多的地方。显然，花费最少和游览的景点尽量多是该问题的两个目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后计算出在这种情况下的最小花费。这样最终会得出几种旅游路线，而组织方可以根据自己的实际情况进行选择。游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。我们定义：——每个游客的旅游总花费；——每个游客的交通总费用；——每个游客的旅游景点的花费；从而得到目标函数：Min（1）交通总花费因为表示从第个景点到第个景点所需的交通费用，而是判断游客们是否从第个景点直接到第个景点的0—1变量，因此我们可以很容易的得到交通总费用为：（2）旅游景点的花费因为表示游客在个景点的总消费，也可以表示出代表们是否到达过第个和第个景点，而整个旅游路线又是一个环形，因此实际上将代表们在所到景点的花费计算了两遍，从而我们可得旅游景点的花费为：从而我们可以得到目标函数为：Min＝+2、约束条件：①时间约束假设旅游时间应该不多于20天(240小时)，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为表示从第个景点到第个景点路途中所需时间，所以路途中所需总时间为；表示会议代表们在第个景点的逗留时间，故代表们在旅游景点的总逗留时间为。因此，总的时间约束为：②旅游景点数约束根据假设，整个旅游路线是环形，即最终代表们要回到昆明，因此即表示旅游者的景点数，这里我们假定要旅游的景点数为（=2，3，……，15）。因此旅游景点数约束为：（=2，3，……，15）③0——1变量约束我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：当时，因为成都是出发点，所以；时，因为代表们最终要回到成都，所以。综合以上可知，同样，当时，根据题意不可能出现，即不可能出现游客在两地间往返旅游，因为这样显然不满足游览景点尽量多的原则。因此我们可得约束：（=2，3，……，11）综上所述，我们可以得到总的模型为：Min＝+约束条件：六、模型求解与结果分析：在这里我们引入以下符号：——第个景点和第个景点之间的路程；——游客所乘坐的旅游大巴的平均时速，=80km/h；——游客所乘坐的旅游大巴的平均费用，=0.35元/km；通过上网查询资料，我们可以得到的具体值，根据公式=/可得到相应的，同样根据公式=×可以得到相应的（，=1，2，……，15）。（、和的具体数值见附录）同样，通过对昆明、楚雄等一些旅行社进行咨询，我们得出旅游者在第个景点的最佳逗留时间和他们在第个景点总消费：t1t2t3t4t5t6t7t8t9t10t11t12t13t14t1518222519282030102418181419169(单位：小时)c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15320420348430380530340450400340300410280290230(单位：元)旅游景点数n23456每人总花费m（单位：元）775.21241.81661.82075.22496.2路线1→9→11→3→15→11→2→3→15→11→15→4→14→3→11→15→4→14→3→2→1旅游景点数n78910每人总花费m（单位：元）2948.03433.13871.44356.5路线1→2→3→15→4→14→9→11→2→15→3→14→4→11→9→11→2→3→13→5→14→4→15→9→11→2→15→3→13→5→14→4→11→9→1（其中数字1—15分别表示昆明、楚雄、大理、保山、丽江、曲靖、西双版纳、昭通、玉溪、普洱、文山、红河、迪庆、德宏、临沧）七、模型评价本文思路清晰，模型恰当，得出的方案相对合理；成功的使用了0—1变量，使模型的建立和编程得以顺利进行；但是由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进行进一步的改进。实际情况中，两景点之间可能还有除公路外其他交通方式，如航班、铁路，增加这些考虑后，结果会更加合理。因数据资料搜集的不完整，准确性也有待商榷，而且没有对最终方案进行更为细致的讨论研究，这些方面有待改进。参考文献[1]王向东等编，《数学实验》，高等教育出版社[2]姜启源等编，《数学模型》，高等教育出版社[3]李大潜等编，《工程数学学报》，2007年第24卷增刊二[4]周义仓等编，《数学建模竞赛赛题简析与论文点评》，西安交通大学出版社[5]冯杰等编，《数学建模·原理与案例》，科学出版社附录附录1：网上查询到的一些数据及相应的计算出的数据：（1）路程表（km）昆明楚雄大理保山丽江曲靖版纳昭通玉溪普洱文山红河迪庆德宏临沧昆明016038057154013674037296660335330819638573楚雄1600220411380296900532256820495490659478413大理380220019116051611207524761095715710439258193保山57141119103517071311943667104071590163067246丽江540380160351067612809126361200875870279418430曲靖1362965167076760876508232796471466955774709版纳74090011201311128087601112644801075974155913781313昭通37253275294391250811120468103270770211911010945玉溪882484686596282246524600564431234915734669普洱6608201095104012007968010325720995798147912981233文山335495715715875471107570742399506651154973908红河3304907109018704669827022428146650114914571392迪庆819659439630279955155911919071479115411490968800德宏6384782586741877413781010726129897314579680780临沧5734131932464307091313945661123390813928007800（2）时间表（h）=昆明楚雄大理保山丽江曲靖版纳昭通玉溪普洱文山红河迪庆德宏临沧昆明024.757.146.751.79.254.651.28.254.1884.1310.27.987.16楚雄202.755.144.753.711.36.653.210.36.1886.138.245.985.16大理4.752.7502.3926.45149.45.9513.78.9388.885.493.232.41保山7.145.142.3904.398.8416.411.88.34138.93811.37.880.843.08丽江6.754.7524.3908.451611.47.951510.9410.93.495.235.38曲靖1.73.76.458.848.450116.352.99.955.8885.8311.99.688.86版纳9.2511.31416.41611013.98.05113.4412.219.517.216.4昭通4.656.659.411.811.46.3513.905.8512.98.8388.7814.912.611.8玉溪1.13.15.858.247.852.88.155.7507.055.3882.9311.49.188.36普洱8.2510.313.713159.95112.97.15012.449.9818.516.215.4文山4.196.198.948.9410.95.8913.48.845.2912.408.3114.412.211.4红河4.136.138.8811.310.95.8312.38.783.0310.28.313014.418.217.4迪庆10.28.245.497.883.4911.919.514.911.318.514.4314.4012.110德宏7.985.983.230.845.239.6817.212.69.0816.212.1618.212.109.75临沧7.165.162.413.085.388.8616.411.88.2615.411.3517.4109.750（3）价格表（元）=昆明楚雄大理保山丽江曲靖版纳昭通玉溪普洱文山红河迪庆德宏临沧昆明04811417116240.822211228.8198100.599246191172楚雄4806612311488.827016076.8246148.5147198143124大理11466057.348155336226143329214.521313277.457.9保山17112357.30105212393283200312214.527018920.173.8丽江162114481050203384274191360262.526183.7125129曲靖40.888.8155212203026315269.6239141.3140287232213版纳222270336393384263033419324322.5292468413394昭通1121602262832741523340140310212.1211357303284玉溪26.474.414019818867.21961380169129.370.2275220201普洱198246329312360239243101720298.5239444389370文山1011492152152631413232121272990200346292272红河9914721327026114029521172.6244199.50345437418迪庆24619813218983.7287468357272444346.23450290240德宏19114377.420.1125232413303218389291.94372900234临沧17212457.973.8129213394284198370272.44182402340附录2：程序及运行结果（由于数据庞大，只选择了部分数据）（程序）sets:jingdian/1..15/:c,t,l;!其中：1,2,...,15分别代表昆明、楚雄、大理、保山、丽江、曲靖、西双版纳、昭通、玉溪、普洱、文山、红河、迪庆、德宏、临沧；links(jingdian,jingdian):r,cc,tt;!其中：r为0-1变量（0表示两景点不相连，1表示两景点相通）；cc为两景点之间的交通费用；tt为两景点之间的交通时间;endsetsdata:t=18 22 25 19 28 20 30 10 24 18 18 14 19 16 9；c=320 420 348 430 380 530 340 450 400 340 300 410 280 290 230tt=0 2 4.75 7.1375 6.75 1.7 9.25 4.65 1.2 8.25 4.1875 4.125 10.2375 7.975 7.16252 0 2.75 5.1375 4.75 3.7 11.25 6.65 3.2 10.25 6.1875 6.125 8.2375 5.975 5.16254.75 2.75 0 2.3875 2 6.45 14 9.4 5.95 13.6875 8.9375 8.875 5.4875 3.225 2.41257.1375 5.1375 2.3875 0 4.3875 8.8375 16.3875 11.7875 8.3375 13 8.9375 11.2625 7.875 0.8375 3.0756.75 4.75 2 4.3875 0 8.45 16 11.4 7.95 15 10.9375 10.875 3.4875 5.225 5.3751.7 3.7 6.45 8.8375 8.45 0 10.95 6.35 2.9 9.95 5.8875 5.825 11.9375 9.675 8.86259.25 11.25 14 16.3875 16 10.95 0 13.9 8.05 1 13.4375 12.175 19.4875 17.225 16.41254.65 6.65 9.4 11.7875 11.4 6.35 13.9 0 5.85 12.9 8.8375 8.775 14.8875 12.625 11.81251.1 3.1 5.85 8.2375 7.85 2.8 8.15 5.75 0 7.05 5.3875 2.925 11.4375 9.175 8.36258.25 10.25 13.6875 13 15 9.95 1 12.9 7.15 0 12.4375 9.975 18.4875 16.225 15.41254.1875 6.1875 8.9375 8.9375 10.9375 5.8875 13.4375 8.8375 5.2875 12.4375 0 8.3125 14.425 12.1625 11.354.125 6.125 8.875 11.2625 10.875 5.825 12.275 8.775 3.025 10.175 8.3125 0 14.3625 18.2125 17.410.2375 8.2375 5.4875 7.875 3.4875 11.9375 19.4875 14.8875 11.3375 18.4875 14.425 14.3625 0 12.1 107.975 5.975 3.225 0.8375 5.225 9.675 17.225 12.625 9.075 16.225 12.1625 18.2125 12.1 0 9.757.1625 5.1625 2.4125 3.075 5.375 8.8625 16.4125 11.8125 8.2625 15.4125 11.35 17.4 10 9.75 0!其中：主对角线为零,表示各景点到自身交通费用为零;cc=0 48 114 171.3 162 40.8 222 111.6 28.8 198 100.5 99 245.7 191.4 171.948 0 66 123.3 114 88.8 270 159.6 76.8 246 148.5 147 197.7 143.4 123.9114 66 0 57.3 48 154.8 336 225.6 142.8 328.5 214.5 213 131.7 77.4 57.9171.3 123.3 57.3 0 105.3 212.1 393.3 282.9 200.1 312 214.5 270.3 189 20.1 73.8162 114 48 105.3 0 202.8 384 273.6 190.8 360 262.5 261 83.7 125.4 12940.8 88.8 154.8 212.1 202.8 0 262.8 152.4 69.6 238.8 141.3 139.8 286.5 232.2 212.7222 270 336 393.3 384 262.8 0 333.6 193.2 24 322.5 292.2 467.7 413.4 393.9111.6 159.6 225.6 282.9 273.6 152.4 333.6 0 140.4 309.6 212.1 210.6 357.3 303 283.526.4 74.4 140.4 197.7 188.4 67.2 195.6 138 0 169.2 129.3 70.2 274.5 220.2 200.7198 246 328.5 312 360 238.8 24 309.6 171.6 0 298.5 239.4 443.7 389.4 369.9100.5 148.5 214.5 214.5 262.5 141.3 322.5 212.1 126.9 298.5 0 199.5 346.2 291.9 272.499 147 213 270.3 261 139.8 294.6 210.6 72.6 244.2 199.5 0 344.7 437.1 417.6245.7 197.7 131.7 189 83.7 286.5 467.7 357.3 272.1 443.7 346.2 344.7 0 290.4 240191.4 143.4 77.4 20.1 125.4 232.2 413.4 303 217.8 389.4 291.9 437.1 290.4 0 234171.9 123.9 57.9 73.8 129 212.7 393.9 283.5 198.3 369.9 272.4 417.6 240 234 0!其中：主对角线为零,表示各景点到自身的交通时间为零;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)))))<120;!约束条件:表示总的旅行时间（交通时间和景点逗留时间）不超过给定时间10天120小时;@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))<1);!这三个约束条件：表示起点（昆明）有且仅有一条路线出去和一条路线进来，其它景点要么有且仅有一条路线出去和一条路线进来，要么既没有路线出去也没有路线进来;@for(links:@bin(r));!约束条件:表示0-1变量约束;@sum(jingdian(j):@sum(jingdian(i):r(i,j)))=n;!约束条件:表示旅游景点的数目为n的约束;@for(jingdian(i):@for(jingdian(j)|j#gt#1#and#j#ne#i:l(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)<n-1-(n-2)*r(1,i);l(i)>1+(n-2)*r(i,1));!这两个约束条件：为了控制不出现两个以上环形回路，保证有且仅有一条环形路线；以8个景点为例：Globaloptimalsolutionfound.Objectivevalue:3433.100Extendedsolversteps:1707Totalsolveriterations:71966Variable