面向智能導(dǎo)覽的個(gè)性化線路規(guī)劃研究

摘 要： 個(gè)性化游覽線路的規(guī)劃是智能導(dǎo)覽的核心問題之一，景區(qū)及景點(diǎn)信息的形式化表示是個(gè)性化游覽線路自動(dòng)規(guī)劃的基礎(chǔ)。針對(duì)導(dǎo)覽線路的自動(dòng)規(guī)劃問題，提出一種基于無(wú)向圖及H?RVT表的、帶用戶偏好表示的導(dǎo)覽線路生成方法。在問題約束及影響因素分析的基礎(chǔ)上，首先給出了景區(qū)及景點(diǎn)的有向圖表示，進(jìn)而提出基于最大相對(duì)價(jià)值表的景點(diǎn)信息表示方法，最后給出一種綜合考慮起點(diǎn)與終點(diǎn)選擇、景點(diǎn)選擇和游覽時(shí)間控制的個(gè)性化游覽線路自動(dòng)規(guī)劃方法。該方法解決了景區(qū)、景點(diǎn)及路線生成的形式化表示問題，為路線規(guī)劃的實(shí)現(xiàn)提供了理論支撐。

關(guān)鍵詞： 智慧旅游； 導(dǎo)覽； 線路規(guī)劃； 個(gè)性化游覽線路

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）20?0092?05

Abstract： Personalized tour route planning is one of cores of intelligent guiding to visitors， and the formalizing denotation of the information of scenic regions and view spots is the fundament of personalized automatic planning of touring routes. A method of generating the route automatically is given in this paper for automatic planning of touring route based on directed graph， H?RVT and users′ preference. On the basis of analyzing the related factors， a method of how to express the information of scenic regions and view spots is given in this paper. A expressive method of view spot information is proposed according to the table of maximum relative price. An automatic planning method of personalized tour route is offered， which considers the selection of start point， end point， view spots and visiting time control. The method of formal representation for scenic regions， view spots and routing generation provide a theory support for realization of route planning.

Keywords： wisdom tourism； guiding to visitor； rout planning； personalized tour route

0 引 言

智能導(dǎo)覽是智慧旅游研究與建設(shè)的關(guān)鍵內(nèi)容之一，也是物聯(lián)網(wǎng)技術(shù)的重要應(yīng)用[1?2]。參觀游覽路線是否科學(xué)合理在很大程度上影響到整個(gè)游覽過程的用戶體驗(yàn)。對(duì)游客而言，科學(xué)合理的游覽路線能夠使其在較短的時(shí)間、較小的路程代價(jià)下獲得較好的游覽體驗(yàn)，同時(shí)，對(duì)旅游服務(wù)提供者來說，高效的游覽路線也能使得相同服務(wù)資源代價(jià)的情況下獲得游客更高的服務(wù)評(píng)價(jià)，從而促進(jìn)旅游及其服務(wù)業(yè)的健康持續(xù)發(fā)展和進(jìn)步[3?4]。

實(shí)際情況下，游客的游覽時(shí)間有限，不足以完整地游覽當(dāng)前景區(qū)中所有的景點(diǎn)。游客的真實(shí)需求是在有限的時(shí)間內(nèi)個(gè)性化地對(duì)當(dāng)前景區(qū)內(nèi)景點(diǎn)進(jìn)行游覽。因此，如何安排游覽路線，成為智能導(dǎo)覽系統(tǒng)中急需解決的一大問題，生成的游覽路線是否可行有效且滿足游客的偏好，對(duì)用戶體驗(yàn)至關(guān)重要。

游覽路線的規(guī)劃設(shè)計(jì)工作本質(zhì)是依據(jù)游客當(dāng)前的位置信息和待參觀的景區(qū)景點(diǎn)信息，根據(jù)一定的策略篩選合適的路線和景點(diǎn)，并將之有序排列在具體游覽行程路線的過程中。完整的游覽路線應(yīng)當(dāng)包括起點(diǎn)、景點(diǎn)集合、景點(diǎn)間的路徑集合以及終點(diǎn)。因此，對(duì)景區(qū)內(nèi)最佳游覽路線問題模型的建立以及路線生成策略的設(shè)計(jì)是決定游覽路線優(yōu)劣程度的關(guān)鍵所在。

面向智能導(dǎo)覽的個(gè)性化線路自動(dòng)規(guī)劃本質(zhì)上是解決在有限約束下的最短路徑應(yīng)用問題，它是運(yùn)籌學(xué)、地理信息學(xué)以及計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科中的研究熱點(diǎn)，比如求單源且無(wú)負(fù)邊權(quán)的“一對(duì)多”的Dijkstra算法[5]、用于求多源且無(wú)負(fù)權(quán)邊的“一對(duì)一”最短路徑的Floyd算法[6]、求多個(gè)備選優(yōu)化路徑的K最短路徑算法[7]以及靜態(tài)路網(wǎng)中較為有效的“直接搜索”A*算法[8]等。同時(shí)，隨著經(jīng)典圖論和計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)的有效結(jié)合，使得各類最短路徑算法不斷涌現(xiàn)以解決不同特征的實(shí)際問題，它們?cè)跁r(shí)間復(fù)雜度、空間復(fù)雜度、應(yīng)用范圍以及易實(shí)現(xiàn)等性能上各具特色[9?10]。國(guó)內(nèi)有學(xué)者專門就最短路徑算法的分類體系以及研究進(jìn)展[11]方面進(jìn)行過較為全面的總結(jié)與研究分析。文獻(xiàn)[12]提出了一種利用線圖以及頂點(diǎn)賦權(quán)圖的最優(yōu)完全子圖的方案解決中國(guó)郵遞員問題中如何生成最優(yōu)郵遞路線的問題。該方法與通常圖的相關(guān)概念的區(qū)別在于其為圖中的節(jié)點(diǎn)（也稱頂點(diǎn)）賦加了權(quán)值，最終求出一條能訪問到圖中所有節(jié)點(diǎn)且具有最小權(quán)值的環(huán)游。文獻(xiàn)[13]提出了一種解決圖中受K頂點(diǎn)數(shù)限制的所有最短路徑BCSP算法以及其改進(jìn)的ICSP算法，運(yùn)用圖的廣度遍歷算法以及逆鄰接表、指針等數(shù)據(jù)結(jié)構(gòu)知識(shí)生成擴(kuò)展最短路徑樹。

1 問題背景

在游覽過程中，以有限的時(shí)間條件為前提，從游客需求的角度出發(fā)，有如下三點(diǎn)直觀的要求：優(yōu)先參觀景區(qū)內(nèi)游覽價(jià)值大的景點(diǎn)；要求所步行的路程最少，即花費(fèi)在步行過程中的時(shí)間短；在不超出限定時(shí)間的前提下，盡可能充分地利用限定的時(shí)間。

以現(xiàn)實(shí)中大量游客對(duì)景區(qū)的參觀游覽行為過程的總結(jié)為基礎(chǔ)，描述游客游覽某一景區(qū)的一般活動(dòng)流程為：

Step1：根據(jù)當(dāng)前的位置尋找到該景區(qū)最近的入口，從入口處進(jìn)入景區(qū)。

Step2：若游覽時(shí)間足夠長(zhǎng)，則從當(dāng)前位置開始按距離的遠(yuǎn)近開始按序游覽景區(qū)內(nèi)景點(diǎn)，直至景區(qū)內(nèi)所有景點(diǎn)都游覽完畢，結(jié)束游覽活動(dòng)。若時(shí)間有限，不能完整游覽整個(gè)景區(qū)內(nèi)所有景點(diǎn)，則執(zhí)行Step3。

Step3：以當(dāng)前位置為參考，在限定時(shí)間內(nèi)，選擇相對(duì)游覽價(jià)值最高的未被游覽的景點(diǎn)（即該景點(diǎn)知名度高且對(duì)其進(jìn)行游覽花費(fèi)時(shí)間少）。

Step4：步行到達(dá)待參觀的景點(diǎn)并花費(fèi)一定時(shí)間完成對(duì)該景點(diǎn)的參觀。此時(shí)，檢查剩余時(shí)間是否可繼續(xù)游覽活動(dòng)。若剩余時(shí)間可繼續(xù)游覽活動(dòng)，則返回Step3，若剩余時(shí)間無(wú)法滿足繼續(xù)游覽要求，則執(zhí)行Step5。

Step5：從當(dāng)前景點(diǎn)位置行至距離最近的景區(qū)出口，離開景區(qū)結(jié)束對(duì)該景區(qū)內(nèi)景點(diǎn)的游覽，完成本次游覽活動(dòng)。

因此，解決最佳游覽路線生成問題需要完成工作為：

（1） 尋找或設(shè)計(jì)最短路徑算法，以無(wú)向圖中任意某一節(jié)點(diǎn)為起點(diǎn)，根據(jù)其余節(jié)點(diǎn)的權(quán)值、價(jià)值以及該節(jié)點(diǎn)與其余各節(jié)點(diǎn)之間的最短路徑，得到在當(dāng)前位置狀態(tài)下，滿足時(shí)間限制條件的最佳下一個(gè)待游覽節(jié)點(diǎn)。

（2） 當(dāng)需要游覽的節(jié)點(diǎn)集合選定之后，在無(wú)向圖[G]中根據(jù)邊信息以及邊的權(quán)值數(shù)據(jù)確定最佳的游覽路線，生成選定節(jié)點(diǎn)集合中節(jié)點(diǎn)的最終游覽序列。

2 景區(qū)模型抽象與景點(diǎn)屬性表示

2.1 建立無(wú)向圖處理模型

旅游景區(qū)由多個(gè)出入口、內(nèi)部景點(diǎn)集、公共服務(wù)點(diǎn)及內(nèi)部相互之間的路徑組成，游覽路線的生成工作即根據(jù)約束條件按序選擇合適的景點(diǎn)集合與路徑集合。本文以無(wú)向圖作為景區(qū)及景點(diǎn)的表示模型，將景區(qū)相關(guān)信息抽象成如圖1所示附加節(jié)點(diǎn)值的帶邊權(quán)的無(wú)向圖模型。

由圖1可知，將某景區(qū)的平面示意圖轉(zhuǎn)換為無(wú)向圖[G]，將景區(qū)中的景點(diǎn)以及出入口轉(zhuǎn)換為無(wú)向圖[G]中的頂點(diǎn)，景點(diǎn)之間的路徑轉(zhuǎn)換為無(wú)向圖中的邊。

定義1：無(wú)向圖[G]由一個(gè)二元組[V，E]組成，其中集合[V]稱為無(wú)向圖[G]的節(jié)點(diǎn)集合，記為[V={v0，v1，v2，…，vn}，（n∈N*）]，[V]中每個(gè)元素對(duì)應(yīng)代表實(shí)際景區(qū)中一個(gè)景點(diǎn)；集合[G]稱為無(wú)向圖[G]的邊集，是由集合[V]中的元素組成的無(wú)序?qū)vi，vjvi∈V，vj∈V]組成，記為[E=ei，jei，j=vi，vj或ei，j=vj，vi，vi∈V，vj∈V，][E]中每個(gè)元素表示實(shí)際情況下景區(qū)景點(diǎn)之間的一條路徑。

2.2 景點(diǎn)信息表示策略

2.2.1 節(jié)點(diǎn)相對(duì)價(jià)值

在無(wú)向圖[G]中，以[vi]為起點(diǎn)，[vj]為終點(diǎn)的一條路徑[px（vi，vj）]的定義，以及該路徑的路徑代價(jià)[Wpx（vi，vj）]的定義。一般情況下，從節(jié)點(diǎn)[vi]出發(fā)到節(jié)點(diǎn)[vj]的路徑并不惟一，并且不同的路徑代價(jià)一般各不相同。根據(jù)每條路徑的路徑代價(jià)大小，節(jié)點(diǎn)[vi]到節(jié)點(diǎn)[vj]的所有路徑的集合[Pij]中必定存在一條路徑代價(jià)最小的路徑。

對(duì)表1的幾點(diǎn)說明：

（1） 目標(biāo)節(jié)點(diǎn)表示以節(jié)點(diǎn)[vi]為起點(diǎn)出發(fā)需要達(dá)到的節(jié)點(diǎn)。節(jié)點(diǎn)vi的相對(duì)價(jià)值表中目標(biāo)節(jié)點(diǎn)中包含無(wú)向圖[G]中除vi以外的所有節(jié)點(diǎn)。

（2） 路徑時(shí)間代價(jià)表示vi與目標(biāo)節(jié)點(diǎn)之間最短路徑之中所有路徑的權(quán)值之和，即從vi出發(fā)達(dá)到目標(biāo)節(jié)點(diǎn)過程中經(jīng)過的路徑所用的路程時(shí)間。

（3） 節(jié)點(diǎn)時(shí)間代價(jià)表示目標(biāo)節(jié)點(diǎn)的時(shí)間代價(jià)，即游覽目標(biāo)節(jié)點(diǎn)對(duì)應(yīng)景點(diǎn)所需要的時(shí)間。

（4） 節(jié)點(diǎn)價(jià)值表示目標(biāo)節(jié)點(diǎn)的價(jià)值，為目標(biāo)節(jié)點(diǎn)對(duì)應(yīng)景點(diǎn)的自身固有價(jià)值。

（5） 是否已加入路線標(biāo)記目標(biāo)節(jié)點(diǎn)，是否已經(jīng)被加入到最佳路線中，1代表該目標(biāo)節(jié)點(diǎn)已加入到最佳路線中，0代表未加入。

（6） 最大相對(duì)價(jià)值表示目標(biāo)節(jié)點(diǎn)在以[vi]為起點(diǎn)的情況下的最大相對(duì)價(jià)值。在最佳路線的生成過程中，優(yōu)先選擇表[H-RVT（vi）]中相對(duì)價(jià)值高的目標(biāo)節(jié)點(diǎn)加入到最佳路線中。

在表示景點(diǎn)和路徑信息的無(wú)向圖[G]中，所有節(jié)點(diǎn)都有其最大相對(duì)價(jià)值表，每一張表中都包含了以該節(jié)點(diǎn)為起點(diǎn)，到其他所有節(jié)點(diǎn)的最大相對(duì)價(jià)值。

3 條件約束與個(gè)性化路線生成

游覽時(shí)間分為路程中花費(fèi)的時(shí)間以及對(duì)景點(diǎn)進(jìn)行參觀游覽花費(fèi)的時(shí)間，游覽價(jià)值取決于路線中所有景點(diǎn)的價(jià)值高低。從宏觀上描述最佳游覽路線的要求為“在限定的時(shí)間內(nèi)，最高效地利用有限的時(shí)間，尋找游覽價(jià)值最高游覽路線”；從路線生成過程中描述最佳游覽路線的要求為“保證每次加入到游覽路線中的景點(diǎn)都是當(dāng)前條件下最值得游覽的景點(diǎn)”。

3.1 路線起點(diǎn)選擇

3.3 路線終點(diǎn)選擇

生成最佳路線的整個(gè)流程，首先生成最佳路線的起點(diǎn)，也就是選擇進(jìn)入景區(qū)的入口；第二步是生成最佳游覽路線的主要內(nèi)容，不斷的在為圖中未加入最佳路線的節(jié)點(diǎn)集合中按照加入之后的“效益”大小的順序以及是否滿足時(shí)間限制條件來選擇下一個(gè)最值得加入路線；當(dāng)圖中未加入最佳路線的節(jié)點(diǎn)集合中沒有滿足時(shí)間限制條件的節(jié)點(diǎn)時(shí)，為最佳路線按照選擇終點(diǎn)，即選擇離開景區(qū)的出口，生成完整的最佳路線并輸出結(jié)果。

4 結(jié) 論

本文針對(duì)在有限時(shí)間生成最佳游覽路線的問題，從游客的實(shí)際需求分析著手，設(shè)計(jì)了使用無(wú)向圖數(shù)學(xué)模型，總結(jié)出在時(shí)間限定條件下影響景點(diǎn)與路徑選擇的三個(gè)主要因素，并根據(jù)分析結(jié)果為每個(gè)節(jié)點(diǎn)生成各自H?RVT表，從而成功實(shí)現(xiàn)了生成最佳的游覽路線。

參考文獻(xiàn)

[1] OWAIED H H， FARHAN H A， AL?HAWAMDEH N， et al. A model for intelligent tourism guide system [J]. Journal of applied sciences， 2011， 11（2）： 342?347.

[2] GAVALAS Damianos， KENTERIS Michael. A web?based pervasive recommendation system for mobile tourist guide [J]. Personal and ubiquitous computing， 2011， 15（7）： 759?770.

[3] 廖川榮.校園最佳游覽路線問題的數(shù)學(xué)模型分析[J].大學(xué)數(shù)學(xué)，2012，28（6）：78?82.

[4] 姜西瑞.基于GPS和GSM/GPRS的定位系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京：中國(guó)科學(xué)院計(jì)算機(jī)技術(shù)研究所，2006.

[5] 章永龍.Dijkstra最短路徑算法優(yōu)化[J].南昌工程學(xué)院學(xué)報(bào)，2006，25（3）：30?33.

[6] 赫自軍，何尚錄.最短路問題的Floyd算法的若干討論[J].重慶工學(xué)院學(xué)報(bào)（自然科學(xué)版），2008，22（5）：156?159.

[7] 徐濤，丁曉璐，李建伏.K最短路徑算法綜述[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（11）：3900?3906.

[8] 劉浩，鮑遠(yuǎn)律.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J].計(jì)算機(jī)仿真，2008，25（4）：253?257.

[9] ZHAN F B， NOON C E. Shortest paths algorithms： an evaluation using real road networks [J]. Transportation science， 1998， 32（1）： 65?73.

[10] CHERK ASSKY B V， GOLDBERG A V， DIZK T R A. Shortest paths algorithms： theory and experimental evaluation[J]. Mathematical programming， 1996， 73（2）： 129?174.

[11] LU Feng. Shortest path algorithms： taxonomy and advance in research [J]. ACAT geodaetica cartographica， 2001， 30（3）： 269?275.

[12] 李念祖.關(guān)于中國(guó)郵遞員問題的最優(yōu)完全子圖算法[J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，35（4）：26?29.

[13] 王衛(wèi)強(qiáng).求圖中受頂點(diǎn)數(shù)限制的所有最短路徑的算法分析研究[D].上海：華東師范大學(xué)，2007.