自然保护区旅游高峰期时空分流导航管理的模型构建与分析

姜向阳 任佩瑜

(四川大学工商管理学院，四川成都610064)

1 问题提出

中国生态系统的高脆弱性以及对人为干扰的极高敏感性，决定了其旅游资源的脆弱性和易破坏性，因此建立自然风景保护区是人类对面临的生态危机所作出的积极应对(鄢和琳，等，2001)。自然风景保护区既承担着旅游观赏功能和社会经济功能，同时还要发挥其生态环境保护的功能，如果旅游过度开发，必然对生态环境造成伤害;如果采取封山育林式的过度保护，又会伤害越来越旺盛的公众旅游需求和景区的社会经济发展。特别是我国的自然风景保护区大多处于远离都市的边远贫困地区，发展当地经济，改善民生已刻不容缓(黄萍，2007)。因而在有效保护的前提下合理适度开发旅游资源是自然风景保护区可持续发展的关键。但时至今日，自然风景保护区旅游开发与保护和谐发展仍属难解之题。本文认为，针对旅游客流具有季节性特点和随时间波动的特点，为了防止和化解旅游开发与环境保护的尖锐矛盾并使开发与保护和谐发展，在旅游高峰时段进行时空分流导航管理十分必要。

旅游高峰期时空分流导航管理，是指管理部门为解决景区旅游高峰期拥挤加剧生态环境破坏等问题，根据空间的相对静态性和时间的动态性原理，运用优化理论和方法设计出若干优化的游览路线，通过信息技术和智能调度系统对游客的分布进行分流导航的管理理论与技术(冯刚，2011)。在该模式管理下，管理部门通过信息监控、决策和调度，引导一部分游客优先选择A旅游路线游玩，另一部分游客优先选择B旅游路线游玩……然后再依次交换游览线路，使不同的游客群能够在同一时间选择游历不同景点，从时间和空间上错开客流量，均衡利用各景点的接待能力。这样，第一，可消除因拥挤而产生的安全隐患，使游客在游玩过程中感到从容不迫和舒畅;第二，使用信息集成技术监控、合理调度客流，优化游览路线，从而提高管理效率和服务质量，使游客满意度大幅提高;第三，在客流量分布的有序配置条件下，景区也可以充分利用景点集群资源来扩大景区承载能力，从而扩大旅游规模;第四，在科学合理调度下，避免游客拥堵现象产生，减少垃圾的产生，减少植被践踏和损伤，同时监控生态环境。总之，利用时空分流技术，能够在很大程度上缓解旅游发展与保护生态环境的尖锐矛盾。

怎样才能使这种理想变为现实?解决该问题的工具和手段是什么?本文认为“多旅行商问题(MTSP)”可以为我们解决这类问题提供启示。本文分析了TSP(Traveling Salesman Problem)和Hamilton问题的关系，并给出了二者的等价条件，澄清了学术界的一些错误认识。在TSP的基础上通过引入虚拟点，使TSP转化为MTSP，并给出了它们的数学模型，以利于人们从数学的高度来理解时空分流问题。虽然张先迪(2005)、施光燕(2003)、俞文(1999)和Lawer等(1995)分别从一般意义上研究了旅行商问题，并给出了其数学模型的建立方法，但如何把MTSP与景区系统有机结合，在已有文献中比较鲜见。本文通过将“旅游高峰时期时空分流”问题转化为“多旅行商问题(MTSP)”，利用求解“多旅行商问题”所得最优解来安排时空分流路线，以实现景区开发和环境保护和谐发展的预期目标。

作为景区管理部门将利用信息集成技术及时收集和预测出游客人数，清楚各个旅游景点的接待能力、景点之间的线路长度、游客一般所要经历的时间和游客在各个景点一般所要花费的时间等数据，通过构建数学模型拟合出最优路线，进行科学导航。

2 基于路线优化的时空分流导航管理模型的构建与分析

假设某旅游团到某景区游玩，他们希望从景区宾馆出发，游览完每个景点，然后再回到宾馆，该如何选择旅游线路，才能使总行程最小(或费用最省等)，这就是一个典型的旅行商问题。用图论语言可描述为:给定图G=(V，E，W)，其中V为顶点集，E为各顶点相互连接组成的边集，W为定义在E上的权数(非负，实际应用中Wi，j可以表示距离、费用、时间、油量等)，如何确定一条遍历每个顶点而又长度最小的闭通路，此即为最佳旅行商回路。图论问题根据线路是否考虑方向性，可将其分为有向图和无向图，为了便于分析，本文仅讨论无向图的情形(这并不影响我们寻找最优解)。

定义1 经过一个连通图G=(V，E，W)，其中 V为顶点集，E为边集，W为定义在E上的权(非负)。G的一个Hamilton回路是顶点集上的一个循环排列 σ = σ1σ2…σnσn+1(σn+1= σ1)，其中一切 σiσi+1∈E，W(σ)为所有边权之和。当W(σ)达到最小，G称为最小Hamilton回路。G的一个旅行商路线是顶点集V的可重复但不遗漏的一个循环排列。

不少论文和教科书往往将最优旅行商问题和最小Hamilton回路混为一谈，其实二者是有区别的。对于G为连通但不是完全图的情形，G可能不存在Hamilton回路，也就不存在最小Hamilton回路，但G的最优旅游线路却总是存在。即使二者都存在，我们也不难构造出G的最小Hamilton回路却不是G的最优旅行商路线的例子(如图1所示)。

G=(V，E，W)，V由10个顶点组成，而E由13条边构成，且假设X＞1。

不难验证G有唯一Hamilton回路ABCDEFGHIJA，其最小Hamilton回路长度为8+4X，但G的最优旅行商线路ABAHGDCDEFIJA长度为10+2X。

由于， X＞1

显然， 8+4X＞10+2X

即最小Hamilton回路不为最优旅行商路线。

那么，在什么样的图中最小Hamilton回路就为最优旅行商路线呢?定理1将给出回答。

定义2 在图 G=(V，E，W)中，任何 Vi，Vj，Vk∈V，Vi≠Vj，Vj≠Vk，Vk≠Vi且满足Wi，k≤Wi，j+Wj，k，则称 G 为满足三角不式的图( 其中 Wi，j为边 ei，j上的权数，即为边ei，j的长度)。

定理1 若完全图G=(V，E，W)的权满足三角不等式:任何 Vi，Vj，Vk∈V，有Wi，k≤Wi，j+Wj，k，则 G 的最小 Hamilton 回路必为 G 的最优旅行商路线。

我们不难用反证法给定理1作出证明。由定理1，我们可以设法将最优旅行商问题转化为最优Hamilton回路问题来处理。方法是在图G=(V，E，W)的基础上，构造出一个新的完全图G′=(V，E′，W′)。构造方法是E′包含V的一切点对，将任意两点用边 ei，j连接起来，在任意一个由边构成的三角形中，满足三角不等式 W′i，j≤W′i，k+W′k，j，且在过所加边的三角形中至少有一个三角不等式取等号，W′i，j表示 G′上顶点 i与顶点j之间的距离(即连接i和j的所有线路中的最短长度)。例如，图2(b)所示的G′(V，E′，W′)就是由图2(a)所示的加权图 G=(V，E，W)构造出来的。它是满足三角形不等式的完全图，在图2(b)的最小Hamilton回路必为G′的最优旅行商路线。

问题是我们找到的图2(b)中G′的最优旅行商路线会不会就是图2(a)中G的最优旅行商路线呢?同样，我们可以用反证法给出以下结论。

定理2 连通图 G=(V，E，W)所对应的完全图 G′=(V，E′，W′)的最小Hamilton回路H′必定给出G的最优旅行商线路，其中G′中新加边的赋权方法要求满足:在任意一个由边构成的三角形中，满足三角不等式 W′i，j≤W′i，k+W′k，j，且在过所加边的三角形中至少有一个三角不等式取等号。

至此，在理论上，我们可以将最优旅行线路问题转化为最小Hamilton回路来求解，对于求得的最优Hamilton回路，我们可还原出原网络中的最优旅行商回路来。而对于Hamilton问题，我们可建立其一般的数学模型。

设有n个旅游景点A1，A2，……，An，已知从景点 Ai到 Aj距离为 Cij，某游客从某景点出发，遍历其它n－1个景点各一次，最后加到出发点，求总路最短的路线。

我们可将此问题用图表示出来，先利用前面给出的方法构造出其完全图，写出最优Hamilton回路数学模型。

(1)从景点Ai不到Ai，即Xij=0 ∀i

(4)应避免两景点之间往返，Xij+Xji≤1 (i≠j)

应避免三景点形成回路，即Xij+Xjk+Xki≤2 (i，j，k两两不同)

……

应避免在(n－1)景点之间形成回路，Xi1i2+Xi2i3+…Xin－1i1≤n－2，其中

i1，i2，…，in－1两两不等。

(5)Xij=0 或 1(i，j=1，……，n)

前面我们讨论的还只是单旅行商问题，事实上旅游高峰期进行时空分流导航管理的问题是属于多旅行商(MTSP)问题。用图论语言来讲，MTSP是指给出N个城市的集合，M个推销商从各自所在城市出发，分别走一条旅行路线，使得每个城市有且仅有一个推销商走过，最后回到原来的出发城市，且总旅程最短，TSP是MTSP的一个特例(M=1)，MTSP是TSP的一般形式。

MTSP又分为从同一中心城市出发的MTSP和从不同中心城市出发的MTSP。我们仅讨论从同一中心城市出发的MTSP问题，它与我们要解决的时空分流导航管理的问题吻合。

对从同一中心城市(不妨设为V0)出发n个点的MTSP，为了使用TSP的方法来求解MTSP，可引入m－1个虚拟点，这样n个顶点，m个旅行商的MTSP就转化为n′=n+m－1个顶点的单TSP。转化方法如下:

设 G=(V，E)是一连通图，V={Vo，V1，…Vn－1}，V0为旅行商驻地，即 m 个旅行商从V0出发，各自选取经过多个城市以后回到V0，形成不相交的m个回路。就将V0转化为 m 个顶点 V′1，V′2，…，V′m，其它顶点 Vi相应转化为 V′i+m，得到一个新图G′=(V′，E′)，其中 V′={V′1，V′2，…V′m，V′m+1，…，V′m+n－1}。由 V0转化的顶点与其它顶点之间的距离就是V0与相应顶点之间的距离，而由V0转化的顶点之间的距离为∞，即距离矩阵为

这样对从同一中心城市(设为V0)出发的多旅行商问题，就转变为单旅行商问题，其数学模型的表达形式与单旅行商问题一致。具体形式为:

(1)从景点Ai不到Ai，即Xij=0 ∀i

(4)应避免两景点之间往返，即Xij+Xji≤1 (i≠j)

应避免三景点形成回路，即Xij+Xjk+Xki≤2 (i，j，k两两不同)

……

应避免在(m+n－2)景点之间形成回路，Xi1i2+Xi2i3+…Xin－1i1≤n－2，

其中i1，i2，…，in－1两两不等。

(5)Xij=0 或 1(i，j=1，……，n)

这一转换就使我们要解决的时空分流问题和多旅行商问题很好地对应起来。时空分流是要解决在旅游高峰时期如何对客流分布进行科学导航，充分利用景区资源，均衡各景点接待能力，提高管理效率和服务质量，同时又达到保护生态环境的目的。也就是说在某景区有n个景点，在旅游高峰期，我们能不能根据游客人数多少，设计出m条不相交的旅游线路，同时这m条不相交的旅游线路又刚好覆盖所有景点，然后引导游客在同一时间段选择不同旅游线路游览，均衡各景点接待能力。其实多旅行商问题在理论上给我们提出了这m条线路应如何给出。

通过对该模型的求解，我们就可确定出m条互不相交(V0点除外)的旅游路线，而这m条线路又恰好覆盖所有景点，我们可以根据找到的这m条回路，利用信息集成技术及时收集和预测游客数，进行科学管理导航，以较好地实现时空分离分流。

3 实例分析

为了更直观地表达上述分析思路，以下通过一个简单例子加以说明。

假设某游客想两天游完V1，V2，V3，V4，V5五个景点，每天都要求从V1出发并回到V1景点，各景点之间的线路如图3所示，试设计出一条最佳旅行路线图。也就是说，如何构建两条从V1出发并回到V1的回路，使总路程最短。

首先，我们对图3进行重构，连接V2V4，V3V5，并赋值W24=53，W35=60。将图3转换为满足三角不等式的完全图(如图4所示)。

其次，引入虚拟点V6，其中W16=∞，V6到其它点的距离等于V1到其它点的对应距离(见图5)，为了清晰起见，我们在图5中，暂不将V6与其它点连接起来，且其距离矩阵为:

于是，我们可以写出该旅行问题的数学模型:

避免两景点之间往返: xij+xji≤1 (i≠j)

避免三景点形成回路: xij+xjk+xki≤2 (i，j，k两两不同)

避免四景点形成回路: xi1i2+xi2i3+xi3i4+xi4i1≤ 3 (i1，i2，i3，i4，两两不等)

避免五景点形成回路: xi1i2+xi2i3+xi3i4+xi4i5+xi5i1≤4 (i1，…，i5，两两不等)

Xij=0 或 1 (i，j=1，…，6)

求解该规划问题，得最优解:x13=x26=x32=x41=x54=x65=1，其余变量取值为0，min F=238。旅游路线如图6中粗线条所示，消去虚拟点V6，即将V1与V6合并。最佳旅行线路见图7的粗线条所示，由两个回路V1V5V4，V1V2V3构成最佳旅游路线。这样就实现了景区各景点均衡负荷，一定程度上提高了景区的承载力，又使游客在不减少欣赏景点获得精神享受的条件下能够节约了时间等成本，实现双赢。此处我们讨论的虽为假想个例，但这个实例把握了时空分流的本质特征，其思路完全可以运用到景区时空分流的实际运营当中。

4 模型的进一步讨论

接下来，我们进一步探讨带有其它约束的MTSP，因为这样与高峰期进行分流导航管理的问题更吻合。

4.1 均分各旅行商行程的MTSP

现实中，我们面临的往往是在多种约束条件下进行决策。假如在某个旅游集群区有几个大景区，可能耗时几天，如何均衡安排旅行线路，既能使总旅游路程最短，又能使每天行程大致相等?这是我们在旅游时常面临的均分旅行商行程的MTSP问题。

在前面的旅行商问题讨论中，我们在给出最优旅行商线路时，只是考虑到了边的权数，并未考虑点(旅游景点)的权数(所耗时间)。如果这种处理对单旅行商问题不会带来什么影响的话，但在处理多旅行商问题时，就会存在麻烦。因此，我们必须将点权考虑进来。为了分析的方便，我们假设旅行者在景点之间的路途上的行程速度为常数 a，并在景点 i耗时 ti，旅行商的图为 G=(V，E，W)，以 G′=(V，E′，W′)表示相应的完全图(W′为任意两点之间的距离)。

若设Di为第i个旅行商访问的路程，则均分各旅行商行驶路程的MTSP的数学模型的目标函数为:

约束条件同定理2中的多旅行商问题的约束条件。

通过对该模型的求解，我们可确定出m条互不相交(V0点除外)的旅游路线，而这m条线路又恰好覆盖所有景点，并且能够保证在一定程度上各旅游线路的大致相等(因为这是一个多目标决策问题，有时多个目标难以同时实现)。通过这一转换，我们借助相关软件求出最优解，较好地指导时空分流。

4.2 有时限要求的MTSP问题

若有m个旅行商，其各自行走路径为Li，若要求每个旅行商在［0，tmin］时间内完成所有行程，我们最少应安排多少个旅行商来完成任务?亦即m(将m看成变量)最少应为多大，才能确保各旅行商的工作时间不超过tmin?

为了求解该问题，我们可以通过引入m个虚点，先将多旅行商问题转化为单旅行商问题，通过给m赋予不同值，以找到满足限时条件的解，即找出m是旅行商人数的下界，也就是要说明m－1个旅行商无法满足限时要求。

同样，我们也可利用类似方法讨论带有其他约束条件的MTSP，或根据景区的具体要求建立相应的时空分流模型，通过计算机求解，找出最优解，指导管理工作。

5 结论

以上我们通过对多旅行商问题的转换，建立了自然保护区旅游高峰期时空分流导航管理模型。我们讨论了最小Hamilton回路和最优旅行商问题的关系，分析了如何将旅行商问题转化为Hamilton回路问题，讨论了如何将多旅行商问题转变为单旅行商问题来处理，这对我们解决在多约束条件下的旅行商问题提供了思路;同时给出了它们的一般数学模型和该问题的精确求解方法，为时空分流的导航模型奠定了科学的基础，这在同类文献中比较少见。

本文虽然主要讨论的是利用旅行商问题来解决景区旅游的时空分流的管理问题，但事实上TSP是一个典型的组合优化问题，不仅可以解决旅行商的最优回路问题，许多其它问题也都可以化为TSP求解，如货物最优选择路径设计、企业选址决策、生产工艺中加工顺序的优化、车辆调度等问题，TSP是诸多领域内出现的多种复杂问题的集中概括和简化形式。

［1］ Jennings N R.On agent-based software engineering［J］.Artificial Intelligence，2000，117(2):277-296.

［2］ Lawer E L，Lenstra JK，Rinnooy Kan A H G，et al.The Traveling salesman problem:A guided tour of combinatiorial optimization［M］.Wileys，Chichester，1995:87-143.

［3］ 鄢和琳，包维楷.川西山地生态旅游开发及其持续发展初步研究［J］.自然资源学报，2001(6):20-23.

［4］ 黄萍.保护与开发:遗产地数字化管理协同功效实证研究——以“数字九寨”为例［J］.旅游学刊，2007(7):23-28.

［5］ 冯刚.景区游客时空分流导航管理［M］.北京:北京大学出版社，2011.

［6］ 张先迪，李正良.图论及其应用［M］.北京:高等教育出版社，2005.

［7］ 施光燕，董加礼.最优化方法［M］.北京:高等教育出版社，2003.