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

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

關鍵詞： 智慧旅游； 導覽； 線路規(guī)劃； 個性化游覽線路

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 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 引 言

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

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

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

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

1 問題背景

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

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

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

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

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

Step4：步行到達待參觀的景點并花費一定時間完成對該景點的參觀。此時，檢查剩余時間是否可繼續(xù)游覽活動。若剩余時間可繼續(xù)游覽活動，則返回Step3，若剩余時間無法滿足繼續(xù)游覽要求，則執(zhí)行Step5。

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

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

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

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

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

2.1 建立無向圖處理模型

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

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

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

2.2 景點信息表示策略

2.2.1 節(jié)點相對價值

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

對表1的幾點說明：

（1） 目標節(jié)點表示以節(jié)點[vi]為起點出發(fā)需要達到的節(jié)點。節(jié)點vi的相對價值表中目標節(jié)點中包含無向圖[G]中除vi以外的所有節(jié)點。

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

（3） 節(jié)點時間代價表示目標節(jié)點的時間代價，即游覽目標節(jié)點對應景點所需要的時間。

（4） 節(jié)點價值表示目標節(jié)點的價值，為目標節(jié)點對應景點的自身固有價值。

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

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

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

3 條件約束與個性化路線生成

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

3.1 路線起點選擇

3.3 路線終點選擇

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

4 結(jié) 論

本文針對在有限時間生成最佳游覽路線的問題，從游客的實際需求分析著手，設計了使用無向圖數(shù)學模型，總結(jié)出在時間限定條件下影響景點與路徑選擇的三個主要因素，并根據(jù)分析結(jié)果為每個節(jié)點生成各自H?RVT表，從而成功實現(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ù)學模型分析[J].大學數(shù)學，2012，28（6）：78?82.

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

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

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

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

[8] 劉浩，鮑遠律.A*算法在矢量地圖最優(yōu)路徑搜索中的應用[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] 李念祖.關于中國郵遞員問題的最優(yōu)完全子圖算法[J].上海師范大學學報（自然科學版），2006，35（4）：26?29.

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