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

劉小玲

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

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

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

1 引言

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

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

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

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

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

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

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

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

在表2中的符號(hào)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 基于游客體驗(yàn)的智能導(dǎo)航系統(tǒng)

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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