运筹学论文_重庆市旅游线路规划

1、重庆市旅游线路规划钟道军摘要： 重庆位于中国西南部，位于长江与嘉陵江交汇处，四面环山，江水回绕，游资源堪称得天独厚。重庆近几年旅游业迅速发展，许多人在重庆旅游时，由于缺少相关指导和路线规划，造成了许多时间和金钱的浪费。本文列举了重庆的一部分景点，分别讨论了不考虑时间如何让旅游费用最省、不考虑费用如何让用时最少两种情况，运用运筹学相关知识建立模型，并用计算机进行求解，找出合适的旅游线路，以此来为游客选择旅游线路提供参考。关键词： 旅游；线路规划；旅行商问题1、提出问题一名游客准备今年7月1日从涞滩古镇出发在重庆市范围内旅游（包括出发点），希望能够游玩的景点如下图所示：图11 游客的目标景点游客到

2、各景点的乘车时间、费用以及停留时间和住宿时间、费用如下表所示：表11 各景点之间的乘车时间表（单位：小时）涞滩古镇大足石刻渣滓洞樵坪山仙女山万盛石林四面山涞滩古镇032.544.53.53.5大足石刻3033.5433渣滓洞2.5201.53.522.5樵坪山2.52.51.5032.53仙女山4.5433044万盛石林3.5322.5403四面山3.532.53430表12 各景点之间的乘车费用表（单位：元）涞滩古镇大足石刻渣滓洞樵坪山仙女山万盛石林四面山涞滩古镇05042551159086大足石刻50043551218968渣滓洞4046030765360樵坪山5156210654658仙

3、女山1151207265074110万盛石林9089534674052四面山86686058110520表13 游客在各景点停留的时间（单位：小时）景点名称涞滩古镇大足石刻渣滓洞樵坪山仙女山万盛石林四面山停留时间3.54.52.53433.5表14 各景点食宿费用表（单位：元）景点名称涞滩古镇大足石刻渣滓洞樵坪山仙女山万盛石林四面山食宿费用60175130125190150165表15 游客在各景点可能住宿的时间（单位：小时）景点名称涞滩古镇大足石刻渣滓洞樵坪山仙女山万盛石林四面山住宿时间09879108问题一：不考虑费用，为该游客设计一条出行路线，要求用最少的时间将全部景点游览一遍。问题二：

4、不考虑时间，要求用最少的费用将全部景点游览一遍。2、分析问题2.1问题一分析：问题一要求游览完全部景点之后，所花的时间最少，而无需考虑费用问题。即是要求从涞滩古镇出发，不重复地游览各景点，最终回到起点，找出一条用时最短的路线，可以根据相关数据资料,在满足约束的条件下建立模型，并用计算机进行求解。2.2问题二分析：问题二要求游览完全部景点之后，所花费用最少，而无需考虑时间问题。即是要求从涞滩古镇出发，不重复的游览各景点，最终回到起点，找出一条费用最省的路线，解决方法与问题一类似。1 5 762 4 3 图12 网络图顶点说明：1表示涞滩古镇，2表示大足石刻，3表示渣滓洞，4表示樵坪山，5表示仙女

5、山，6表示万盛石林，7表示四面山。2.3假设条件：（1）该名游客要求游览完计划的全部景点，并且所到之处均不重复。（2）天气、交通状况良好，无意外情况发生。（3）查询相关资料得知，这几处景点的门票总费用约为580元，但不论如何选择旅游路线，所支付的门票总费用都一样，所以此处暂不考虑门票费用。2.4符号说明：i,j：景点i或景点jT：此次旅游的所用总时间Ta：乘车所花的总时间Tb：在景点停留所花的总时间Tc：在景点住宿所花的总时间Ki：在景点i可能住宿的时间Tij：从景点i到景点j乘车的时间Ti：在景点i停留所花的时间Z：此次旅游的总费用Za：乘车总费用Zb：景点食宿费用Cij：从景点i到景点j的

6、乘车费用Ci：景点i的食宿费用Xij=1：从景点i前往景点jXij=0：不从景点i前往景点j3、建立模型3.1问题一：3.1.1目标函数的确立：本问题的目标是找到用时最短的旅游路线，而旅行时间由乘车时间、景点停留时间和景点住宿时间三部分组成，因此目标函数为： （11）乘车总时间为： （12）景点停留总时间为： （13）景点住宿总时间为： （14）综上，目标函数为： （15）3.1.2约束条件的确立：景点数量约束： （16）变量约束： i，j=1,2, ,7 （17） i，j=1,2, ,7 （18）3.1.3模型的建立：根据以上分析，可建立如下模型：s.t. i，j=1,2, ,7 i，j=1

7、,2, ,73.2问题二：3.2.1目标函数的确立：本问题的目标是找到费用最省的旅游路线，而旅行费用由乘车费用、食住宿费用两部分组成，因此目标函数为： （21）乘车总费用为： （22）食宿总费用为： （23）综上，目标函数为： （24）3.2.2约束条件的确立：景点约束： （25）变量约束： i，j=1,2, ,7 （26） i，j=1,2, ,7 （27）3.2.3模型的建立：根据以上分析，可建立如下模型：s.t. i，j=1,2, ,7 4、计算机求解代码4.1问题一：model:sets:place/1.7/:t,k,l;connect(place,place):x,tt;endsets

8、data:t=3.5 4.5 2.5 3 4 3 3.5;k=0 9 8 7 9 10 8;tt=032.544.53.53.53033.54332.5201.53.522.52.52.51.5032.534.54330443.5322.54033.532.53430;enddatamin=sum(place(j):sum(place(i):x(i,j)*(tt(i,j)+0.5*(t(i)+t(j)+0.5*(k(i)+k(j);for(place(i):x(i,i)=0);for(place(i)|i#ge#2:for(place(j)|j#ge#2:x(i,j)+x(j,i)1);for

9、(place(i):sum(place(j):x(i,j)=sum(place(j):x(j,i);for(place(i)|i#eq#1:sum(place(j):x(i,j)=1);for(place(i)|i#ne#1:sum(place(j):x(i,j)=l(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(place(i)|i#gt#1:l(i)1+(n-2)*x(i,1);end4.2问题二：model:sets:place/1.7/:c,l;connect(place,place):x,cc;endsetsdata:c=60 175 130

10、125 190 150 165;cc=0 504255115908650043551218968404603076536051562106546581151207265074110908953467405286686058110520;enddatamin=sum(place(j):sum(place(i):x(i,j)*(cc(i,j)+0.5*(c(i)+c(j);for(place(i):x(i,i)=0);for(place(i)|i#ge#2:for(place(j)|j#ge#2:x(i,j)+x(j,i)1);for(place(i):sum(place(j):x(i,j)=su

11、m(place(j):x(j,i);for(place(i)|i#eq#1:sum(place(j):x(i,j)=1);for(place(i)|i#ne#1:sum(place(j):x(i,j)=l(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(place(i)|i#gt#1:l(i)1+(n-2)*x(i,1);end5、计算机求解结果5.1问题一求解结果（重要部分）：Local optimal solution found. Objective value: 95.00000 Objective bound: 95.00000 Infeasib

12、ilities: 0.1276399E-05 Extended solver steps: 41Total solver iterations: 3362Variable ValueX( 1, 2) 1.000000X( 2, 7) 1.000000X( 3, 1) 1.000000X( 4, 6) 1.000000X( 5, 4) 1.000000X( 6, 3) 1.000000X( 7, 5) 1.0000005.1问题二求解结果（重要部分）：Local optimal solution found. Objective value: 1365.000 Objective bound:

13、1365.000 Infeasibilities: 0.2075714E-06 Extended solver steps: 0 Total solver iterations: 434Variable Value Reduced CostX( 1, 2) 1.000000 0.000000X( 2, 7) 1.000000 0.000000X( 3, 1) 1.000000 0.000000X( 4, 3) 1.000000 0.000000X( 5, 4) 1.000000 -5.000000X( 6, 5) 1.000000 0.000000X( 7, 6) 1.000000 -6.00

14、00006、解决方案6.1问题一：根据计算机求解结果，得出不考虑费用的情况下，用时最短的旅游路线：涞滩古镇大足石刻四面山仙女山樵坪山万盛石林渣滓洞涞滩古镇此路线所花的时间为4天。6.2问题二：根据计算机求解结果，得出不考虑用时的情况下，费用最省的旅游路线：涞滩古镇大足石刻四面山万盛石林仙女山樵坪山渣滓洞涞滩古镇此路线所花的费用为1365元（不含门票），若包含门票则为1945。7、启发和启示1.本文将游客是否由某一景点直接前往另一景点设置为0-1变量，以此来建立了模型。2.本文在限定条件下，成功运用lingo软件解决了问题。3.本文中的问题只考虑了最小费用、最少时间两种情况，还有很多可能出现的情况没有考虑到。4.本文中的天气、交通状况等假设在实际操作中不一定完全符合，并且实际生活中的客观条件会更加复杂，例如景点门票的价格可能会随节假日而变动。5.本文的景点数据来源于网络搜集，可能与实际情况有差距。8、问题的