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

引 言

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

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

游览路线的规划设计的本质工作是依据一定的规则选取何当的景点并选择合理的游览路线生成完整的游览路线[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→ T L = 3 、 A→ B→ T R = 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，并结合制定的三项路线生成规则成功设计了合理可行的最佳路线生成方案。本文在研究路线的生成方案时，考虑的因素包括景点的游览价值和景点的游览成本，而在实际的游览过程中，会有更多的因素可能会对游客需要的游览线路产生影响，如游客的个人偏好、景点附近的服务设施等因素。因此在未来的研究中可以研究更多的能够影响路线生成方案的因素，使得研究对象符合实际需要解决的问题从而得到更加具有实用性的研究成果。