基于Dijkstras算法的主题公园游览路径规划研究

刘小玲

摘要：在主题公园竞争越来越激烈的今天，研究游客行为，并基于游客行为为游客提供一种适合游客游览的路径十分必要。本文分析了狄杰斯特拉算法，该算法非常适合在主题公园中应用，但由于主题公园游乐设施的特殊性，非到达即能游览的特性，将狄杰斯特拉算法进行了预处理，将等待时间问题转化为节点本身的距离问题，再通过狄杰斯特拉算法，计算在旅游旺季游客需要在游乐设施前等待时的路径选择问题。

关键词：狄杰斯特拉算法；主题公园；路径选择；Dijkstra

中图分类号：TP249 文献标识码：A 文章编号：1007-9416（2018）09-0096-02

1 引言

在主题公园竞争越来越激烈的今天，同质化的服务已逐渐不能满足游客个性化体验的需求。提高游客体验是主题公园提供差异化服务所追求的目标之一，也是未来智慧主题公园提升服务质量的全新增长点。智能导航系统为解决此问题提供了可能的解决方案。目前，国内学者从景区管理角度和游客体验角度两个视角来研究智能导航系统.从景区管理视角研究此问题的成果较多[1][2]，为景区调度提供解决方案，通过游客分流解决了景区超载问题，减轻了景区负荷，从而提升了游客满意度。从游客体验视角研究智能导航系统的文献较为分散，这些研究的主要思想集中在利用狄杰斯特拉（Dijkstra）算法求出景点间最短距离[3][4]。但由于主题公园内每个游乐设施存在时间窗问题，不是一个静态的景点，故在解决实际问题时应加入游客抵达游乐设施后的等待时间这一变量。

2 基于游客体验的智能导航系统的建立

2.1 问题分析与假设

假设游客在主题公园游览时的游览路径基于三个因素：当前所在位置与游乐设施间的距离，个人偏好和游乐设施的等待时间。由于个人偏好无法量化，故舍弃这一影响因素，选择到达游乐设施的距离和游乐设施等待时间两个因素。假设游客满意度与等待时间成正比，那么系统为游客选择的下一游玩项目应是在当前未游玩项目中等待时间最短的那个项目。基于此，基于游客满意度的主题公园游览路径选择问题可以转换成选取游客等待时间最短的游乐设施的路径分析问题。

2.2 经典狄杰斯特拉算法及其优化算法

狄杰斯特拉（Dijkstra）算法是一种最短路径搜索算法，它提供了从图的一个节点到另一个节点的最短路径。设G=（V，E）是一个带权的有向图，V表示顶点，E表示顶点组成的边。所有的V节点组成一个集合，该集合分为两类，第一类节点是已求知的最短路径节点的集合P，第二类为未求知的最短路径节点集合T。在V中设定一个源点v1，并把v1放入P中，在E中求出与v1距离最点的点v2，并把v2放入P中，求出第三个节点v3，使其距离v2的E最小，并将v3放入P中，以此类推，直到求出最后一个Vn。

先不考虑游乐设备需等待的问题，即假设所有游乐设施无需等待，通过经典狄杰斯特拉算法即可完成。采用图的结构来表示主题公园中的路径结构。图1抽象的描述了主题公园游乐设施平面图，其中S1～S5分别表示主题公园中若干游乐设施所在地，顶点之间的边长为游乐设施间的距离，具体数据见表1。

使用Dijkstra计算游客从S1出发，计算距离游客当前位置最近的下一个游乐设计的计算过程如表2。

在表2中的符号P、D（x）、p（x）分别代表以下含义：

P：结点子集，如果从源结点到目的结点x的最短路径已确知，x在P中；

D（x）：随着算法进行本次迭代，从源结点到目的结点x的最短路径的距离；p（x）：从源结点到目的结点x沿着当前最短路径的前一结点（x的邻居）。

2.3 基于游客体验的智能导航系统

狄杰斯特拉算法只能解决顶点等待时间为零的静态路线规划问题，但在主题公园里，由于游乐设施分为需等待和无需等待两种状态，故基于游客体验的智能导航系统需对该算法进行改进。改进的方案是先对顶点数据进行预处理，把Vi与Vj之间的距离转化成游客由Vi走到Vj所需的时间再加上在游乐设施Sj前需要等待的时间。

定义1设f（vj）=g（vs，vj）+h（vj），其中g（vs，vj）为从起始節点vs经过狄杰斯特拉算法到达vj的最短路径，h（vj）为节点vj的代价函数，它表示游客在游乐设施Sj前的等待时间。

假设Wait（S2）=10，Wait（S3）=30，Wait（S4）=28，Wait（S5）=12，将游乐设施间的距离转化成时间，假设步行速度为2，则设施间距离矩阵转化为时间矩阵，即h（vj）=Wait（Sj）/2，f（vj）=g（vs，vj）+h（vj）数据如表3。

再次使用Dijkstra计算游客从S1出发，计算距离游客当前位置最近的下一个游乐设计的计算过程如表4。

3 结语

经过一次狄杰斯特拉算法可以搜寻出离当前位置最近的点，它非常适合应用于主题公园最优路径的选择。但由于主题公园游乐设施在旅游旺季常常出现需要排队等待的情况，故到达某景点后，并不能立即对该景点进行研究。本文对狄杰斯特拉算法进行了预处理，将景点的等待时间转化成达到目的地的代价时间，再利用狄杰斯特拉算法算法求出离当前景点代价最小的下一景点，为游客提供最优路径。

参考文献

[1]郑天翔.基于动态实时调度的主题公园游客时空分流导航管理研究[J].旅游科学，2012，26（4）：8-16.

[2]邱厌庆.基于复杂系统控制的景区游客时空分流导航管理研究[J].管理科学，2011，25（9）：54-57.

[3]吕琼艺.基于改进的Dijkstra算法的旅游规划线路研究与实践[J].柳州职业技术学院学报，2017，17（2）：32-36.

[4]魏菲.基于WiFi定位技术的自助导游系统的研究与设计[D].延边：延边大学，2014：5.