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

钟道军

摘要： 重庆位于中国西南部，位于长江与嘉陵江交汇处，四面环山，江水回绕，游资源堪称得天独厚。重庆近几年旅游业迅速发展，许多人在重庆旅游时，由于缺少相关指导和路线规划，造成了许多时间和金钱的浪费。本文列举了重庆的一部分景点，分别讨论了不考虑时间如何让旅游费用最省、不考虑费用如何让用时最少两种情况，运用运筹学相关知识建立模型，并用计算机进行求解，找出合适的旅游线路，以此来为游客选择旅游线路提供参考。 关键词： 旅游；线路规划；旅行商问题

1、提出问题

一名游客准备今年7月1日从涞滩古镇出发在重庆市范围内旅游（包括出发点），希望能够游玩的景点如下图所示：

图1—1 游客的目标景点

游客到各景点的乘车时间、费用以及停留时间和住宿时间、费用如下表所示：

表1—1 各景点之间的乘车时间表（单位：小时）

涞滩古镇 大足石刻 渣滓洞 樵坪山 仙女山 万盛石林 四面山 涞滩古镇 大足石刻 0 3 2.5 2.5 4.5 3.5 3.5 3 0 2 2.5 4 3 3 渣滓洞 2.5 3 0 1.5 3 2 2.5

表1—2 各景点之间的乘车费用表（单位：元）

涞滩古镇 大足石刻 渣滓洞 樵坪山 仙女山 万盛石林 四面山 涞滩古镇 大足石刻 0 50 40 51 115 90 86 50 0 46 56 120 89 68 渣滓洞 42 43 0 21 72 53 60

表1—3 游客在各景点停留的时间（单位：小时）

景点名称 涞滩古镇 大足石刻 停留时间 3.5 4.5 渣滓洞 2.5

表1—4 各景点食宿费用表（单位：元）

景点名称 涞滩古镇 大足石刻 食宿费用 60 175 渣滓洞 130 樵坪山 125 仙女山 190 万盛石林 150 四面山 165 樵坪山 3 仙女山 4 万盛石林 3 四面山 3.5 樵坪山 55 55 30 0 65 46 58 仙女山 115 121 76 65 0 74 110 万盛石林 90 89 53 46 74 0 52 四面山 86 68 60 58 110 52 0 樵坪山 4 3.5 1.5 0 3 2.5 3 仙女山 4.5 4 3.5 3 0 4 4 万盛石林 3.5 3 2 2.5 4 0 3 四面山 3.5 3 2.5 3 4 3 0 表1—5 游客在各景点可能住宿的时间（单位：小时）

景点名称 涞滩古镇 大足石刻 住宿时间 0 9 渣滓洞 8 樵坪山 7 仙女山 9 万盛石林 10 四面山 8 问题一：不考虑费用，为该游客设计一条出行路线，要求用最少的时间将全部景点游览一遍。

问题二：不考虑时间，要求用最少的费用将全部景点游览一遍。

2、分析问题

2.1问题一分析：

问题一要求游览完全部景点之后，所花的时间最少，而无需考虑费用问题。即是要求从涞滩古镇出发，不重复地游览各景点，最终回到起点，找出一条用时最短的路线，可以根据相关数据资料,在满足约束的条件下建立模型，并用计算机进行求解。

2.2问题二分析：

问题二要求游览完全部景点之后，所花费用最少，而无需考虑时间问题。即是要求从涞滩古镇出发，不重复的游览各景点，最终回到起点，找出一条费用最省的路线，解决方法与问题一类似。

1

2 3

4 5

6 7 图1—2 网络图

顶点说明：1表示涞滩古镇，2表示大足石刻，3表示渣滓洞，4表示樵坪山，5表示仙女山，6表示万盛石林，7表示四面山。

2.3假设条件：

（1）该名游客要求游览完计划的全部景点，并且所到之处均不重复。 （2）天气、交通状况良好，无意外情况发生。

（3）查询相关资料得知，这几处景点的门票总费用约为580元，但不论如何选择旅游路线，所支付的门票总费用都一样，所以此处暂不考虑门票费用。

2.4符号说明： i,j：景点i或景点j T：此次旅游的所用总时间 Ta：乘车所花的总时间 Tb：在景点停留所花的总时间 Tc：在景点住宿所花的总时间 Ki：在景点i可能住宿的时间 Tij：从景点i到景点j乘车的时间 Ti：在景点i停留所花的时间

3、建立模型

3.1问题一：

3.1.1目标函数的确立：

本问题的目标是找到用时最短的旅游路线，而旅行时间由乘车时间、景点停留时间和景点住宿时间三部分组成，因此目标函数为：

minTTaTbTc （1—1） 乘车总时间为：

Ta景点停留总时间为：

Z：此次旅游的总费用 Za：乘车总费用 Zb：景点食宿费用

Cij：从景点i到景点j的乘车费用 Ci：景点i的食宿费用 Xij=1：从景点i前往景点j Xij=0：不从景点i前往景点j

TXiji1j177ij （1—2）

177 TbXij(TiTj) （1—3）

2i1j1景点住宿总时间为：

177 TcXij(KiKj) （1—4）

2i1j1综上，目标函数为：

177177 minTTijXijXij(TiTj)Xij(KiKj) （1—5）

2i1j12i1j1i1j13.1.2约束条件的确立： 景点数量约束：

变量约束：

77Xi1j177ij7 （1—6）

Xi1ij1

Xj1ij1 i，j=1,2, …,7 （1—7）

3.1.3模型的建立：

XijXji0 i，j=1,2, …,7 （1—8）

根据以上分析，可建立如下模型：

177177minTTijXijXij(TiTj)Xij(KiKj)

2i1j12i1j1i1j1s.t.

77Xi1j177ij7

Xi1ij1

Xj1ij1 i，j=1,2, …,7

XijXji0 i，j=1,2, …,7

3.2问题二：

3.2.1目标函数的确立：

本问题的目标是找到费用最省的旅游路线，而旅行费用由乘车费用、食住宿费用两部分组成，因此目标函数为：

minZZaZb （2—1） 乘车总费用为：

Za食宿总费用为：

XCiji1j177ij （2—2）

177 ZbXijCiCj （2—3）

2i1j1综上，目标函数为：

77 minZXijCij1i1j1277 XijCiCj i1j13.2.2约束条件的确立： 景点约束：

77Xij7 i1j1变量约束：

Xij1

i1Xij1 i，j=1,2, …,7 j1 XijXji0 i，j=1,2, …,7 3.2.3模型的建立：

根据以上分析，可建立如下模型：

77XijCij177minZi1j12XijCiCj

i1j177s.t.

CijXij7

i1j1Xij1

ij1

i1Xj1

XijXji0 i，j=1,2, …,7

4、计算机求解代码

4.1问题一：

model:

2—4）

2—5）

2—6）

2—7）

（ （ （ （sets:

place/1..7/:t,k,l;

connect(place,place):x,tt; endsets data:

t=3.5 4.5 2.5 3 4 3 3.5; k=0 9 8 7 9 10 8;

tt=0 3 2.5 4 4.5 3.5 3.5 3 0 3 3.5 4 3 3 2.5 2 0 1.5 3.5 2 2.5 2.5 2.5 1.5 0 3 2.5 3 4.5 4 3 3 0 4 4 3.5 3 2 2.5 4 0 3 3.5 3 2.5 3 4 3 0; enddata

min=@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(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))<1); @for(connect:@bin(x));

@sum(place(j):@sum(place(i):x(i,j)))=7;

@for(place(i):@for(place(j)|j#gt#1#and#j#ne#i:l(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)); end

4.2问题二：

model: sets:

place/1..7/:c,l;

connect(place,place):x,cc; endsets data:

c=60 175 130 125 190 150 165; cc=0 50 42 55 115 90 86 50 0 43 55 121 89 68 40 46 0 30 76 53 60 51 56 21 0 65 46 58 115 120 72 65 0 74 110 90 89 53 46 74 0 52 86 68 60 58 110 52 0; enddata

min=@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))=@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))<1); @for(connect:@bin(x));

@sum(place(j):@sum(place(i):x(i,j)))=7;

@for(place(i):@for(place(j)|j#gt#1#and#j#ne#i:l(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)); end

5、计算机求解结果

5.1问题一求解结果（重要部分）：

Local optimal solution found.

Objective value: 95.00000 Objective bound: 95.00000 Infeasibilities: 0.1276399E-05 Extended solver steps: 41 Total solver iterations: 3362

Variable Value X( 1, 2) 1.000000 X( 2, 7) 1.000000 X( 3, 1) 1.000000 X( 4, 6) 1.000000 X( 5, 4) 1.000000 X( 6, 3) 1.000000 X( 7, 5) 1.000000

5.1问题二求解结果（重要部分）：

Local optimal solution found.

Objective value: 1365.000 Objective bound: 1365.000 Infeasibilities: 0.2075714E-06 Extended solver steps: 0 Total solver iterations: 434

Variable Value Reduced Cost X( 1, 2) 1.000000 0.000000 X( 2, 7) 1.000000 0.000000 X( 3, 1) 1.000000 0.000000 X( 4, 3) 1.000000 0.000000 X( 5, 4) 1.000000 -5.000000 X( 6, 5) 1.000000 0.000000

X( 7, 6) 1.000000 -6.000000

6、解决方案

6.1问题一：根据计算机求解结果，得出不考虑费用的情况下，用时最短的旅游路线：

涞滩古镇

大足石刻 渣滓洞

四面山

仙女山

樵坪山

万盛石林 涞滩古镇

此路线所花的时间为4天。

6.2问题二：根据计算机求解结果，得出不考虑用时的情况下，费用最省的旅游路线：

涞滩古镇

樵坪山

大足石刻 渣滓洞 四面山 涞滩古镇

万盛石林

仙女山

此路线所花的费用为1365元（不含门票），若包含门票则为1945。

7、启发和启示

1.本文将游客是否由某一景点直接前往另一景点设置为0-1变量，以此来建立了模型。

2.本文在限定条件下，成功运用lingo软件解决了问题。

3.本文中的问题只考虑了最小费用、最少时间两种情况，还有很多可能出现的情况没有考虑到。

4.本文中的天气、交通状况等假设在实际操作中不一定完全符合，并且实际生活中的客观条件会更加复杂，例如景点门票的价格可能会随节假日而变动。

5.本文的景点数据来源于网络搜集，可能与实际情况有差距。

8、问题的推广

解决本问题的方法还可以用来解决以下问题： 1.如何规划最合理、高效的道路交通，以减少拥堵； 2.如何规划物流路线，以减少运营成本；

3.在互联网环境中如何更好地设置节点，让信息更加畅通。

9、参考文献

[1] 蒋长兵，代应 .库存控制：模型、技术与仿真[M].北京：中国物资出版社，2010.

[2] 谢金星，薛毅 .优化建模与LINDO/LINGO软件[M] .北京：清华大学出版社，2005.

[3]赵刚 .重庆都市旅游线路设计存在问题与对策探讨[J].特权经济，2011(10).