基于Dijkstras算法的主題公園游覽路徑規(guī)劃研究

劉小玲

摘要：在主題公園競爭越來越激烈的今天，研究游客行為，并基于游客行為為游客提供一種適合游客游覽的路徑十分必要。本文分析了狄杰斯特拉算法，該算法非常適合在主題公園中應(yīng)用，但由于主題公園游樂設(shè)施的特殊性，非到達(dá)即能游覽的特性，將狄杰斯特拉算法進(jìn)行了預(yù)處理，將等待時間問題轉(zhuǎn)化為節(jié)點(diǎn)本身的距離問題，再通過狄杰斯特拉算法，計算在旅游旺季游客需要在游樂設(shè)施前等待時的路徑選擇問題。

關(guān)鍵詞：狄杰斯特拉算法；主題公園；路徑選擇；Dijkstra

中圖分類號：TP249 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2018）09-0096-02

1 引言

在主題公園競爭越來越激烈的今天，同質(zhì)化的服務(wù)已逐漸不能滿足游客個性化體驗的需求。提高游客體驗是主題公園提供差異化服務(wù)所追求的目標(biāo)之一，也是未來智慧主題公園提升服務(wù)質(zhì)量的全新增長點(diǎn)。智能導(dǎo)航系統(tǒng)為解決此問題提供了可能的解決方案。目前，國內(nèi)學(xué)者從景區(qū)管理角度和游客體驗角度兩個視角來研究智能導(dǎo)航系統(tǒng).從景區(qū)管理視角研究此問題的成果較多[1][2]，為景區(qū)調(diào)度提供解決方案，通過游客分流解決了景區(qū)超載問題，減輕了景區(qū)負(fù)荷，從而提升了游客滿意度。從游客體驗視角研究智能導(dǎo)航系統(tǒng)的文獻(xiàn)較為分散，這些研究的主要思想集中在利用狄杰斯特拉（Dijkstra）算法求出景點(diǎn)間最短距離[3][4]。但由于主題公園內(nèi)每個游樂設(shè)施存在時間窗問題，不是一個靜態(tài)的景點(diǎn)，故在解決實(shí)際問題時應(yīng)加入游客抵達(dá)游樂設(shè)施后的等待時間這一變量。

2 基于游客體驗的智能導(dǎo)航系統(tǒng)的建立

2.1 問題分析與假設(shè)

假設(shè)游客在主題公園游覽時的游覽路徑基于三個因素：當(dāng)前所在位置與游樂設(shè)施間的距離，個人偏好和游樂設(shè)施的等待時間。由于個人偏好無法量化，故舍棄這一影響因素，選擇到達(dá)游樂設(shè)施的距離和游樂設(shè)施等待時間兩個因素。假設(shè)游客滿意度與等待時間成正比，那么系統(tǒng)為游客選擇的下一游玩項目應(yīng)是在當(dāng)前未游玩項目中等待時間最短的那個項目?；诖耍谟慰蜐M意度的主題公園游覽路徑選擇問題可以轉(zhuǎn)換成選取游客等待時間最短的游樂設(shè)施的路徑分析問題。

2.2 經(jīng)典狄杰斯特拉算法及其優(yōu)化算法

狄杰斯特拉（Dijkstra）算法是一種最短路徑搜索算法，它提供了從圖的一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)的最短路徑。設(shè)G=（V，E）是一個帶權(quán)的有向圖，V表示頂點(diǎn)，E表示頂點(diǎn)組成的邊。所有的V節(jié)點(diǎn)組成一個集合，該集合分為兩類，第一類節(jié)點(diǎn)是已求知的最短路徑節(jié)點(diǎn)的集合P，第二類為未求知的最短路徑節(jié)點(diǎn)集合T。在V中設(shè)定一個源點(diǎn)v1，并把v1放入P中，在E中求出與v1距離最點(diǎn)的點(diǎn)v2，并把v2放入P中，求出第三個節(jié)點(diǎn)v3，使其距離v2的E最小，并將v3放入P中，以此類推，直到求出最后一個Vn。

先不考慮游樂設(shè)備需等待的問題，即假設(shè)所有游樂設(shè)施無需等待，通過經(jīng)典狄杰斯特拉算法即可完成。采用圖的結(jié)構(gòu)來表示主題公園中的路徑結(jié)構(gòu)。圖1抽象的描述了主題公園游樂設(shè)施平面圖，其中S1～S5分別表示主題公園中若干游樂設(shè)施所在地，頂點(diǎn)之間的邊長為游樂設(shè)施間的距離，具體數(shù)據(jù)見表1。

使用Dijkstra計算游客從S1出發(fā)，計算距離游客當(dāng)前位置最近的下一個游樂設(shè)計的計算過程如表2。

在表2中的符號P、D（x）、p（x）分別代表以下含義：

P：結(jié)點(diǎn)子集，如果從源結(jié)點(diǎn)到目的結(jié)點(diǎn)x的最短路徑已確知，x在P中；

D（x）：隨著算法進(jìn)行本次迭代，從源結(jié)點(diǎn)到目的結(jié)點(diǎn)x的最短路徑的距離；p（x）：從源結(jié)點(diǎn)到目的結(jié)點(diǎn)x沿著當(dāng)前最短路徑的前一結(jié)點(diǎn)（x的鄰居）。

2.3 基于游客體驗的智能導(dǎo)航系統(tǒng)

狄杰斯特拉算法只能解決頂點(diǎn)等待時間為零的靜態(tài)路線規(guī)劃問題，但在主題公園里，由于游樂設(shè)施分為需等待和無需等待兩種狀態(tài)，故基于游客體驗的智能導(dǎo)航系統(tǒng)需對該算法進(jìn)行改進(jìn)。改進(jìn)的方案是先對頂點(diǎn)數(shù)據(jù)進(jìn)行預(yù)處理，把Vi與Vj之間的距離轉(zhuǎn)化成游客由Vi走到Vj所需的時間再加上在游樂設(shè)施Sj前需要等待的時間。

定義1設(shè)f（vj）=g（vs，vj）+h（vj），其中g(shù)（vs，vj）為從起始節(jié)點(diǎn)vs經(jīng)過狄杰斯特拉算法到達(dá)vj的最短路徑，h（vj）為節(jié)點(diǎn)vj的代價函數(shù)，它表示游客在游樂設(shè)施Sj前的等待時間。

假設(shè)Wait（S2）=10，Wait（S3）=30，Wait（S4）=28，Wait（S5）=12，將游樂設(shè)施間的距離轉(zhuǎn)化成時間，假設(shè)步行速度為2，則設(shè)施間距離矩陣轉(zhuǎn)化為時間矩陣，即h（vj）=Wait（Sj）/2，f（vj）=g（vs，vj）+h（vj）數(shù)據(jù)如表3。

再次使用Dijkstra計算游客從S1出發(fā)，計算距離游客當(dāng)前位置最近的下一個游樂設(shè)計的計算過程如表4。

3 結(jié)語

經(jīng)過一次狄杰斯特拉算法可以搜尋出離當(dāng)前位置最近的點(diǎn)，它非常適合應(yīng)用于主題公園最優(yōu)路徑的選擇。但由于主題公園游樂設(shè)施在旅游旺季常常出現(xiàn)需要排隊等待的情況，故到達(dá)某景點(diǎn)后，并不能立即對該景點(diǎn)進(jìn)行研究。本文對狄杰斯特拉算法進(jìn)行了預(yù)處理，將景點(diǎn)的等待時間轉(zhuǎn)化成達(dá)到目的地的代價時間，再利用狄杰斯特拉算法算法求出離當(dāng)前景點(diǎn)代價最小的下一景點(diǎn)，為游客提供最優(yōu)路徑。

參考文獻(xiàn)

[1]鄭天翔.基于動態(tài)實(shí)時調(diào)度的主題公園游客時空分流導(dǎo)航管理研究[J].旅游科學(xué)，2012，26（4）：8-16.

[2]邱厭慶.基于復(fù)雜系統(tǒng)控制的景區(qū)游客時空分流導(dǎo)航管理研究[J].管理科學(xué)，2011，25（9）：54-57.

[3]呂瓊藝.基于改進(jìn)的Dijkstra算法的旅游規(guī)劃線路研究與實(shí)踐[J].柳州職業(yè)技術(shù)學(xué)院學(xué)報，2017，17（2）：32-36.

[4]魏菲.基于WiFi定位技術(shù)的自助導(dǎo)游系統(tǒng)的研究與設(shè)計[D].延邊：延邊大學(xué)，2014：5.