景区路线规划

摘 要

本文主要研究最短旅游路线的设计问题。在满足题目中的条件下，找到最佳的路径且用最短的距离是我们追求的目标。毕竟，能否设计出合理且令人满意的旅游路径，对景区的经济效益和长远发展有着密切的关系。对此本文用数学联系实际，建立数学模型，设计出相对科学的景区旅游景点路线，来解决此类问题。

对于问题一，从题目中我们了解到我们要设计出6种只含4个景点的最短路径，且至少包括两个特色景点，而旅游内容相近的同类景点如1，6和9,10又不能同时出现。根据这些条件，我们运用floyd算法的原理，通过matlab编程，建立带权邻接矩阵，再用插入顶点的方法构造出距离矩阵，同时也能求出插入点矩阵，最终得到初步符合条件的旅游套餐。再经过用Excel软件对得出的数据进行分类，整理，排序，最终得出符合题意的6种旅游套餐。同时，在我们对景点的组合中可以发现，有多种景点组合都存在游览顺序不同而导致的行程不同的现象。对这种游览顺序不同，但游览的景点是相同的情况，我们视其为同一种旅游套餐。

对于问题二，题目要求我们设计出6种不同旅游套餐，并在在景区特色景点的客流容纳人数是其他景点的两倍的情况下计算出各种套餐的人数比例，使得景点的客流量基本均衡，且总行程尽可能短。对此我们0-1变量的思想表示是否游览某个景点，从而推出总行程尽可能短的约束条件，再用Lingo编程对模型进行求解，得出初步可能的旅游套餐。然后再引入方差的思想，方差是描述数据离散程度的量，方差越小各景点的客流量越均衡。所以，我们接下来可以利用6 个旅游套餐中所有景点的客流量的方差来刻画景点客流量的均衡程度，要使方差尽量小，首先6个套餐应覆盖尽量多的景点，再由每种套餐的比例来约束方差，使得方差尽量小。由此，我们可以建立关于游客量的方程和关于方差的函数。然后再对之前得出的旅游套餐使用综合评判的方法，并经过灵敏度的分析，得出符合要求的6种旅游套餐。

关键词 floyd算法 Exce软件 matlab软件 0-1变量 Lingo软件

一、问题重述

图1

某景区有10个景点，各景点的交通示意图如图1。边上的权为两景点间路程。其中1，3，6，9，10五个景点为景区特色景点。景区特色景点的客流容纳人数是其他景点的两倍。在特色景点中，1和6都是海滨景点，9和10都是山区景点。

为了合理规划景区的旅游，景区旅游经营者计划推出6种不同的旅游套餐，每种旅游套餐包括4个景点，其中至少2个特色景点。由于景点1、6和景点9、10分别是同类景点，游览内容相近，景区规定，旅游套餐中的特色景点不能只是同类景点。需要解决的问题：

（1）按照上述要求，找出6种路程最短的套餐。

（2）请你设计出这6种不同旅游套餐，并计算出各种套餐的人数比例，使得景点的客流量基本均衡，且总行程尽可能短。

二、问题分析

能否设计出合理且令人满意的旅游路径，对景区的经济效益和长远发展有着密切的关系。根据题目中给景点示意图，我们可以得到任意两个景点之间的距离。如下表所示：

景点之间的距离

景点1 景点2 景点3 景点4 景点5 景点6 景点7 景点8 景点9 景点10

Inf Inf 24.6 Inf Inf Inf Inf

表一

11.6 Inf 0

另外，题中要求每种旅游套餐要有4个景点，其中至少包含2个特色景点，且特色景点不能是同一类的，对此4个景点间的路程求和即为这个旅游套餐的路径。由图1可看出，4个景点所游览的顺序不同，会出现其行程也不相同的现象，我们归其为同一类套餐。根据题目的要求，我们只选取其中行程最短的路径作为这种套餐。首先，通过matlab编程和对floyd了解及运用，找出初步符合条件的路径，再利用穷举法以及用EXCEL对得出的数据处理，最终可得到符合题意且路程最短的6种套餐。

对于问题二，在第一问的基础上，可以用6 个旅游套餐中所有景点的客流量的方差来描述景点客流量的均衡程度，方差越小各景点的客流量越均

衡。需注意，景区特色景点的客流容纳人数是其他景点的两倍， 所以需对方差进行简单处理，具体见模型建立。要使方差尽量小， 首先6 个套餐应覆盖尽量多的景点，（再由每种套餐的比例来约束方差，）使得方差尽量小。（在本问中，我们定义了一个函数——均衡程，描述方案对题意的符合度，具体见符号说明与模型建立。通过对均衡程的比较可以得出最优的6 个套餐。）

三、模型的假设与符号说明

1、模型的假设

（1）游客在旅游观览过程中，均按旅游套餐进行游览。且每种套餐上有且仅有4个景点。

（2）游客在旅游观览过程中，考虑到实际情况，在按照一种旅游套餐，4个景点仅仅是因为由于游览顺序不同而出现的多种游览方式的时候，视为同一种旅游套餐，并且是取总路程最短的游历路线方案。

（3）游客在旅游观览过程中，无任何意外情况的发生。

（4）每一个景点接待游客的能力都是相同的并且接待能力充分高，即可以实现多条旅游路线的游客们同时游览同一个景点。

（5）一个景点直接到达另外一个景点是指，途中经过的其他景点只是一个转站地，而并不进行游览. 2、符号说明

表2

表1对论文中出现的而符号加以解释，若有没有解释的，以文中出现的为主。

四、问题一

1、模型分析

针对第一问，我们要考虑： （1）每个旅游套餐中有4个景点 （2）4个景点中至少要有两个特色景点； （3）同类的特色景点不能同时出现； （4）经过4个景点的路程最短。

在旅游套餐中会出现旅游景点相同，但是因为游览顺序的不同而出现路程不同的情况，我们选取最短距离作为标准。我们客观的规定，在浏览过程中，不存在经过景点而不进入景点的情况。 2、模型建立

游客在景点间的直达距离可由以下矩阵给出，即xi到xj的直达距离为Dij，若两景点间不能直接到达则用 表示。得到如下矩阵W：

031.5

31.507.512.7 7.5014.5

12.714.50 1917 6.8

10.8

16.8

17.611.2

1917 07.8

7.8012.8

12.8012.611.8

17.6 24.6

11.2

（1）

12.611.8

018.611.6 18.60

11.6 0

6.810.816.8

Floyd算法的建立；

(0)

第一步：把带权邻接矩阵W作为距离矩阵的初值，即D(0)=(dij) =W， (1)(1)(0))(1)

D(1)= (dij) ，其中dij min{dij,di(10) d1(0j}，dij是从vi到vj的只允许以v1

作为中间点的路径中最短路的长度．

(2)(1)1)(2)(1)(2)

第二步：D(2)= (dij min{dij,di(2) ，其中dij d2j}，dij是从vi到vj的只

允许以v1 、 v2作为中间点的路径中最短路的长度．

( )( )( 1) 1)( )D( )=(dij是从vi到vj的只允许) ，其中dij min{dij,di( d (j 1)},dij

以v1、v2、…、v 作为中间点的路径中最短路的长度．即是从vi到vj中间可插入任何顶点的路径中最短路的长，因此D( )即是距离矩阵．

第三步：在建立距离矩阵的同时可建立路径矩阵R． R=(rij) , rij的含义是从vi到vj的最短路要经过点号为rij的点．

R(0) (rij(0)) , rij(0) j

每求得一个D(k)时，按下列方式产生相应的新的R(k)

r

(k)

ij

k r(k 1) ij

(k 1)(k 1)(k 1)若dij dik dkj

（2）

否则

即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 R( )时求得

D( )可由R( )来查找任何点对之间最短路的路径．

图2 第四步：利用追溯法即可在R中找出符合条件的最短路径。即：若rij( ) p1，则点p1是点i到点j的最短路的中间点.然后用同样的方法再分头查找． 若：

（１）向点i追朔得：rip1 p2,rip2 p3, ,ripk pk （２）向点j追朔得：rp1j q1,rq1j q2, ,rqmj j

( )

( )

(

)

( )

( )

( )

则由点i到j的最短路的路径为：i,pk,,p2,p1,q1,q2,,qm,j

图3

3、模型的求解

根据（1）矩阵，运用floyd算法得出权矩阵D和插入点矩阵R(程序及迭代过程见附录一)：

R =

1 2 2 5 5 5 5 5 5 5 1 2 3 4 5 4 4 4 4 3 2 2 3 4 4 4 8 8 8 10 5 2 3 4 5 6 7 8 7 8 1 2 4 4 5 6 6 4 6 4 5 4 4 4 5 6 7 4 7 4 6 4 8 4 6 6 7 8 9 8 4 4 3 4 4 4 7 8 9 10 7 7 8 7 7 7 7 8 9 8 8 8 8 8 8 8 8 8 8 10 程序见附录一，注意；在matlab中 表示为inf。 通过追溯法求得初步符合条件的路线：

表2

表2中的路线只是符合经过4个旅游景点，至少包含2个特色且不包含同类特色景点的路线，我们需要用Excel软件对数据进行再处理。

用Excel对数据进行处理得到表3：

表3

表3是对表2中的路线数据进行处理后所得结果，是无序的，不易直接找到路程最短的路线，再对表3数据进行排序。 对所得路程进行处理后得到满足条件的路线：

表4

表4中的路线即是满足要求的路线，即包括4个景点，其中至少2个特色景点，没有同类景点。

五、问题二

1、模型分析

针对问题2要考虑的问题有：

（１）计算各种旅游套餐的人数比例； （２）各景点的客流量基本平衡； （３）总路程最短。

要解决这3各问题，要从实际情况出发，设定一系列的变量及不变量。 （1）景区（包括10各景点）的总游客量为k。 （2）对各景点的游客统计假定不重复。 2、模型建立

建立0-1模型；设置相邻两景点的距离函数为；

Yij sij*xi*xj （3）

其中xi、xj为0.1变量，当旅游路线经过i，j景点时xi 1、xj 1，若旅游路线不经过i，j景点则xi 0，xj 0 目标函数：

min Yij*sij （4）

ij 1

10

10

xi 4

i 1

x1 x3 x6 x9 x10 2 （5） x1 x6 1

x9 x10 1

3、模型的求解

每个景点的客流量：

P1 k Mij （6）

j a

f

因为总游客人数是k，每个游客浏览4个景点，所以若假设每人只浏览一个景点，则游客总人数为4k，所以每个景点平均接待游客量为：

p

4k

（7） 10

为使所有景点客流量较均衡，所选的6个套餐及其比例应使所有景点接待 游客量的方差尽量小，且考虑到特色景点游客的容纳量是普通景点的两倍：

pi122（ p） （pi-p）） min （8） 10i=1、3、6、9、102i 2、、45、、78

衡量方案是否最有的函数——均衡程，即方案中6 个套餐的平均路程与10个景点的客流量方差之积，在较优的解中均衡程应尽量小：

将上述条件在LINGO中运行，得到结果表5（程序见附录二）：

表5

六、模型的优缺点

1、对模型一 优点

1、本文思路清晰，模型恰当，得出的方案合理且符合题中的要求。 2、本文成功的使用了Floyd算法以及插入点矩阵，追溯法和0—1变量，使模型的建立和编程得以顺利进行；

3、通过假设2回避了程序求解给出的答案中可能出现的景点相同、游览顺序不同的雷同旅游套餐，更贴近实际情况。

缺点

1、问题一由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进行进一步的改进。 2、此模型的求解要用到0-1规划并要熟悉掌握Floyd算法原理，对程序的正确编写要求较高。

3.在建立利用方差衡量模型中景点的均衡问题时未考虑到其他因素对景点的游客的影响。例如在实际问题中必须考虑的游览时间顺序问题，同一时间过多旅游套餐集中在一个景点可能会导致景点游客过多。在此模型之中不能解决这种问题，所以此模型考虑有欠周全。 2、对模型二 优点

1、用方差约束目标函数的方法来求解使各景点游客量均衡的问题，用

离散程度来刻画均衡。此模型简便易用。

2、合理假设，目标函数、景点客流量、（套餐比例关系明显，）体现

出各种变量对模型结果的影响，表达式简单，使得整个模型简单有效。

缺点

1、实际问题中必须考虑的游览时间顺序问题，同一时间过多旅游套餐

集中在一个景点可能会导致景点游客过多。在此模型之中不能解决这种问题，所以此模型考虑有欠周全。

2、在模型求解的过程中，根据此模型的变量约束条件不能直接的得出

最后的6种套餐，必须再采用一定量的数据处理，这是由于我们的程序不够完善导致的。

七、模型的推广

1、对模型一

通过对题目的解读我们不难发现这是一类规划问题。我们建立了具有约束条件的线性规划模型运用Matlab软件以及 Floyd算法以及追溯法求解其模型。这个模型不仅仅适用于旅游景点的路线选择问题，它对类似问题的求解都可以起到指导作用。

由于该模型具有很强的普适性，所以凡是涉及到最短路径时，选取最优方案都可以借鉴此模型。例如建筑物建设的选址问题，几个城市的铁路交通路线，战争时期的粮草运输，甚至全球贸易的物流中转站的最短路径都可以借鉴此模型来解决。 2、对模型二

首先应用0-1变量列出约束条件，然后用引入方差来衡量各景点的游客量均衡的方法，具有很强的可移植性和灵活性。可应用于解决道路资源利用的不均衡等优化问题。同时此模型可用来解决国家经济开发区的分布问题，发达城市、沿海地区、落后地区的人口分布，利于国家做出宏观调控，和经济发展。

参考文献

[1] 姜启源. 数学模型（第三版）[M]. 北京：高等教育出版社，1999.

[2] 韩中庚. 数学建模方法及其应用（第二版）[M]. 北京：高等教育出版社，2009.

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

[4]王正东. 数学软件与数学实验（第二版），北京：科学出版社，2010

八、附录

附录一：

程序1：function[D,R]=floyd(a)

n=size(a,1); D=a

for i=1:n for j=1:n R(i,j)=j; end end R for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k D R end

程序2：

a=[0 31.5 inf inf 19 inf inf inf inf inf ; 31.5 0 7.5 12.7 17 inf inf inf inf inf; inf 7.5 0 14.5 inf inf inf 17.6 inf 24.6; inf 12.7 14.5 0 6.8 10.8 16.8 11.2 inf inf ; 19 17 inf 6.8 0 7.8 inf inf inf inf ; inf inf inf 10.8 7.8 0 12.8 inf inf inf ; inf inf inf 16.8 inf 12.8 0 12.6 11.8 inf; inf inf 17.6 11.2 inf inf 12.6 0 18.6 11.6; inf inf inf inf inf inf 11.8 18.6 0 inf;

inf inf inf inf inf inf inf 11.6 inf 0;] [D,R]=floyd(a)

迭代结果：

输出：

D =

0 31.5000 Inf Inf 19.0000 Inf Inf Inf Inf Inf

31.5000 0 Inf Inf

Inf 7.5000 Inf 24.6000

Inf 12.7000 Inf Inf

19.0000 17.0000 Inf Inf

Inf Inf Inf Inf

Inf Inf 11.8000 Inf

Inf Inf 18.6000 11.6000

Inf Inf 0 Inf

Inf Inf Inf 0 R =

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 k = 1 D =

0 31.5000 Inf Inf

31.5000 0 7.5000 0 Inf Inf Inf 17.6000 Inf 24.6000 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 Inf 7.5000 12.7000 17.0000 14.5000 Inf 0 6.8000 6.8000 0 10.8000 7.8000 16.8000 Inf Inf Inf Inf Inf Inf 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 Inf 19.0000 12.7000 17.0000 Inf Inf 10.8000 7.8000 0 12.8000 Inf Inf Inf 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 Inf Inf Inf Inf 16.8000 Inf 12.8000 0 11.8000 Inf Inf Inf Inf 17.6000 11.2000 Inf Inf 12.6000 0 18.6000 11.6000 Inf Inf

14.5000 11.2000 12.6000

Inf Inf

Inf 7.5000 0 14.5000 Inf Inf Inf 17.6000 Inf 24.6000

Inf 12.7000 14.5000 0 6.8000 10.8000 16.8000 11.2000 Inf Inf

19.0000 17.0000 Inf 6.8000 0 7.8000 Inf Inf Inf Inf

Inf Inf Inf 10.8000 7.8000 0 12.8000 Inf Inf Inf

Inf Inf 11.8000 Inf

Inf Inf 18.6000 11.6000

Inf Inf 0 Inf

Inf Inf Inf 0 R =

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 k = 2 D =

0 31.5000 Inf Inf

31.5000 0 Inf Inf

39.0000 7.5000 Inf 24.6000

44.2000 12.7000 Inf Inf

19.0000 17.0000 Inf Inf

Inf Inf Inf Inf

Inf Inf Inf 17.6000 Inf 24.6000 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 4 5 39.0000 7.5000 0 14.5000 24.5000 Inf Inf 16.8000 Inf Inf Inf Inf Inf Inf 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 44.2000 19.0000 12.7000 17.0000 14.5000 24.5000 0 6.8000 6.8000 0 10.8000 7.8000 16.8000 Inf 12.8000 Inf Inf Inf 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 Inf Inf Inf 10.8000 7.8000 0 12.8000 0 11.8000 Inf Inf Inf Inf 16.8000 Inf 12.8000 0 12.6000 0 18.6000 11.6000 Inf Inf 17.6000 11.2000 Inf Inf 12.6000

11.2000 12.6000