最佳游览路线生成方案的设计与实现

王艳　印国成　孙茂圣

摘 要：当游客选择一个景区进行游览参观活动时，往往是希望能以一个能够满足自己游览需求的最优游览路线来进行旅游活动。在相同时间的限制条件下，该游览路线优于其他游览路线的地方在于能使游客获得更高的游览满意度。因此，文章主要研究在已知景区及其包含景点、路径等相关信息条件下，从图论视角以无向图相关知识为工具进行最佳游览路线生成方案的设计研究。文中的研究完成了三项工作：建立以无向图为知识背景的问题对象研究模型；改进Dijkstra最短路径算法实现导出节点的LCT表；最佳游览路线生成算法，并依据上述三个工作的研究成果来最终实现最佳游览路线生成的完整方案。

关键词：最短路径；智能导览；Dijkstra；最佳旅游路线

中图分类号：TP311 文献标识码：A 文章编号：2095-1302（2015）12-00-02

0 引 言

对于游客而言，参观游览的路线是否科学合理很大程度影响到游览的体验效果。科学合理的游览路线能够让游客在花费较短的时间、路程代价下获得更佳的游览体验。高质量的游览路线也能在旅游服务提供者在付出相同服务资源代价的情况下为其赢得游客更高的评价从而促进旅游相关产业的不断发展进步。

完整的游览路线由起点、终点、景点以及游览活动需要经过的所有路径组成。游览路线之间的区别在于能否使得游客合理有效的参观游览，能否满足游客的相关要求。本文从游客的角度出发，将研究的目标定为寻找出能够在满足游览时间限制的条件下最佳游览路线的设计生成方案。

游览路线的规划设计的本质工作是依据一定的规则选取何当的景点并选择合理的游览路线生成完整的游览路线[1，2]。因此本文将研究工作划分为三个部分，为研究对象建立合适的问题模型；对Dijkstra最短路径算法的研究与改进实现对景点的对比选择[3]；最佳游览路线生成算法的设计完成最终的路线生成。

1 相关工作

旅游路线设计的相关研究根据出发点的不同主要分为基于旅行社需求的旅游路线的设计研究和基于游客需求的旅游路线的设计研究。两者的相同之处在于都是以旅游景区为研究对象寻找满足一定要求的游览路线，不同之处在于其设定的游览路线需要满足的要求是不一样的。游客对旅游路线的需求主要包括时间少、路程短、景点多、景点参观价值高等。本文主要研究从游客的需求出发设计最佳游览路线的生成方案，因此对最佳游览路线的要求与游客对游览路线的需求是一致的。所以本文研究的目的是能够生成一条满足游客游览时间限制，且游览景点的数量、质量都比其他路线占优的最佳游览路线。

Dijkstra算法是图论中用于求有向图节点之间最短路径问题的经典算法，在工程项目的最短路径问题研究中得到广泛的应用。Dijkstra算法在一定程度上进行了广度优先遍历的变异，也可以视为启发性搜索算法的特例。其特点为通用性强、程序设计简单。而对于本文研究问题来说，其最大的优点在于算法的运行结果是某一节点到图中其他所有节点的最短路径，这一特点使得可以设计更加合理全面的游览路线中景点的选取策略并能提高景点选取的效率。

《校园最佳游览路线问题的数学模型分析》一文中介绍了游览校园的最佳游览路线的问题处理模型的分析对本文中景区旅游最佳路线的设计方案提供了可参考的建模思路[4]。将旅游路线的设计规划问题转化成在图论视角下的无向图最佳路线的设计问题，利用寻找无向图中最短路径的算法为最佳旅游路线的设计方案提供了可行的处理方案。

2 问题模型

一个旅游景区一般由多个出入口、内部景点景观、公共服务点以及相互之间路径组成。游客在景区内参观游览时，必定是按照一定游览路线进行的。当游览时间不足以参观完景区内所有景点时，此时对游客而言，最佳的游览路线是在限定时间之内能够最有价值的游览当前景区内景点的路线。因此需要解决的问题为：如何定义游览路线的游览价值以及如何寻找在当前时间限制条件下游览价值最高的路线。图1所示即为某景区的旅游示意图。

图1中，假设XXX景区有四个出入口E/E_TL、E/E_TR、E/E_BL、E/E_BR和九个景点SS_A、SS_B、SS_C、SS_D、SS_E、SS_F、SS_G、SS_H、SS_I，其中景点SS_C和SS_D为景区的标志性景点。在无向图中，出入口与景点统一以节点来表示，路径以边来表示，边的权值表示对应路径步行时间，建立了如图1所示的景区信息的图形模型，（SS_A，2，7）表示景点SS_A为二级节点，推荐的游览时间为7分钟。其定义如下：

定义1：游览价值G（x），表示节点x的参观游览价值。在本此研究中将无向图中节点分为四个等级，分别为一级节点、二级节点、三级节点和四级节点。其中一级节点代表景区的标志性景点，游览价值最高，二级节点和三级节点的游览价值依次减弱，四级节点代表景区的出入口，不具备游览价值。

定义2：最短路径S（a） = {Sab， Sac， Sad， ......}，表示从节点a到图中其它节点b、c、d......的最短路径。

定义3：最低游览成本表LCT（x），表示节点x到图中其它任意节点的最低游览成本。游览成本是综合考虑节点的游览价值与路径代价而定义的，规定节点A到节点B的最低游览成本为节点A到节点B的最短路径的权值与节点B的游览价值的比值。

3 基于Dijkstra算法的LCT表生成

Dijkstra算法[5，6]也被称为最短路径算法，是图论中用于求节点之间最短路径的经典算法。它采用标记法按照边权值的大小顺序来寻找节点之间的最短路径。算法的基本思想为从源节点出发，从相邻节点中找到边最短的一条路径，然后以该路径为基础寻找下一个可直接达到且最短的路径并标记找到的节点，通过不断的执行上述步骤，最终得到源节点到图中所有节点的最短路径。本文中最佳游览路线生成方案的基本思想是不断寻找新的节点加入到游览路线中直至该路线的游览时间大于规定的时间限制。

通过运用Dijkstra算法寻找出节点之间的最短路径结合本文中节点的游览价值属性，综合考虑得出节点之间的最低游览成本，实现从未选择的节点之中选取游览成本最低的景点，从而使得最终生成的游览路线是相同条件游览成本最低、价值最高的最佳游览路线。

根据游览价值的定义设一级节点、二级节点、三级节点以及四级节点的游览价值分别为10、3、2、0.1。现以图1中SS_A节点为例，描述Dijkstra算法在本文中的运用以及节点LCT表的实现过程（注：在下面的内容中，为方便描述，以X代表形如SS_X的节点，以XX代表形如E/E_XX的节点）。

节点A的LCT表生成过程如下：

Step1：以节点A为源点，标记节点，从相邻的节点中寻找路径长度最短的节点得到节点C，标记节点A，得到A到C的最短路径A→C=2。

Step2：以节点C为中间点，在未标记的相邻节点中寻找最短路径得到节点TL，发现（A→C→TL=5）>（A→TL=3）（A→B=3），标记节点TL与节点B，得到最短路径A→TL=3和A→B=3，此时已有三条最短路径A→C=2、A→TL=3和A→B=3。

Step3：分别以节点TL和节点B为中间节点，在未标记的相邻节点中寻找最短路径得到（A→TL→E=7）>（A→B→TR=5）>（A→D=5），标记节点D，得到最短路径A→D=4，此时已有四条最短路径A→C=2、A→TL=3、A→B=3和A→D=4。

Step4： 以上一步中标记的节点为中间节点，按照上述规律不断寻找最短路径直至所有节点都被标记，得到节点A到图中其余所有节点的最短路径分别为：

A→B=3、A→C=2、A→D=4、A→TL→E=7、A→C→F=5.5、A→C→F→G=7.5、A→D→H=6.5、A→D→I=9.5、A→TL=3、A→B→TR=5、A→C→F→BL=8.5、A→D→H→BR=8.5。

Step5：计算节点A到图中其余节点的最低游览成本。如节点B为二级节点，所以节点A到节点B的的最低游览成本为3÷3=1。

Step6：根据Step4和Step5的结果，可以生成表1，即LCT（A）表。

为图中其他的节点进行相同的处理即可生成每个节点各自的LCT表。当成功得到表中所有节点LCT之后，就可开始游览路线节点的选取工作，进行最佳游览路线的设计实现。

4 最佳路线生成方案的设计

在前面的问题描述中我们对最佳游览路线进行了初步的描述，此处给出本文最佳游览线路的定义：最佳游览线路是能够在满足时间限制条件下，以游览成本从低到高的顺序选择景点进行游览直至超出时间限制的路线。

根据上述定义以及实际需求，本文制定了如下几点规则：

（1）游览路线必须以出入口节点开始并以出入口节点结束。

（2）在时间限制允许的条件下，景点按照游览价值从高到低的顺序进行选取。

最佳路线生成方案的基本思想为：在规则2的基础上，从一级景点中选择推荐游览时间最短的景点为基础，选择最近的两个出口和入口为路线的起点生成一条过程路线，计算当前路线的游览耗时，若未超过限定的游览时间，就从过程路线中所有景点的LCT表中选取未加入游览路线，并按照游览价值由高到低且游览成本最小的景点加入到游览路线中，并验证是否满足时间限制。若满足则重复上述操作；若超过时间限制，放弃最后选取的景点，得到最佳的游览路线。这里需要说明的是，本文游览路线设计方案能够得到最佳游览路线主要依据如下：

（1）规则2的制定保证了游览路线中游览价值高的景点能够优先考虑。

（2）基于Dijkstra最短路径算法生成的LCT表能够保证相同游览价值的景点，路径短的被优先加入到游览路线之中。

（3）最佳游览路线生成方案保证了游览时间得到最大程度的利用。

如仍然以图1中XXX景点为例，实现最佳游览路线的生成，这里假设限定的游览时间为45分钟。则：

Step1： 因节点C与节点D的游览价值最高且节点C的推荐游览时间大于节点D的推荐游览时间，以景点D为基础，根据LCT（D）表得到两个出入口TR和BR，生成最短过程路线TR→D→H→BR，需注意此处D节点并未参观，因此当前路线所需要的游览时间为3.5+12+2.5+2=20<45。

Step2： 从TR、BR以及D的三个节点的LCT表中寻找游览成本最低的一级节点。若没有一级节点，则寻找二级节点游览成本最低的节点并依次类推，得到节点C，根据节点C和D的LCT表生成最短过程路线TR→D→C→TL，当前路线游览所需时间为3.5+12+5+15+3=38.5<45。

Step3： 从TR、D、C、TL四个节点的LCT表中以游览价值高低顺序选择游览成本最低的节点，得到节点A，并生成最短过程路线TR→D→A→C→TL，当前路线随需游览时间为3.5+12+4+7+2+15+3=46.5>45，因此节点A不能加入游览路线当中，故在45分钟的时间限制条件下，XXX景区的最佳游览路线为TR→D→C→TL。

5 结 语

针对在一定时间限制条件下设计景区的游览路线设计规划问题，本文通过对Dijkstra最短路径算法的研究定义并导出了节点的最低游览成本LCT，并结合制定的三项路线生成规则成功设计了合理可行的最佳路线生成方案。本文在研究路线的生成方案时，考虑的因素包括景点的游览价值和景点的游览成本，而在实际的游览过程中，会有更多的因素可能会对游客需要的游览线路产生影响，如游客的个人偏好、景点附近的服务设施等因素。因此在未来的研究中可以研究更多的能够影响路线生成方案的因素，使得研究对象符合实际需要解决的问题从而得到更加具有实用性的研究成果。

参考文献

[1] 蒋满元.旅行社的旅游线路优化设置问题探讨[J].技术经济与管理研究， 2008（4）：7-9.

[2]朱珠；张欣.浅谈智慧旅游感知体系和管理平台的构建[J].江苏大学学报（社会科学版），2011（6）：97-100.

[3] Schrijver， A. A combinatorial algorithm minimizing sub-modular functions in strongly polynomial time[J]. Comb. Theory Ser. B ，2000，80：346–355.

[4] 廖川荣.校园最佳游览路线问题的数学模型分析[J].大学数学，2012，28（6）：78-82.

[5] 李元臣.基于Dijkstra算法的网络最短路径分析[J].微计算机应用，2004，25（3）：295-362.

[6] Kolmogorov， V， Shioura， A. New algorithms for convex cost tension problem with application to computer vision[J]. Discrete Optim，2009（6）：378–393.