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

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

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

中圖分類號： 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 引 言

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

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

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

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

1 問題背景

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

以現實中大量游客對景區的參觀游覽行為過程的總結為基礎，描述游客游覽某一景區的一般活動流程為：

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

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

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

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

Step5：從當前景點位置行至距離最近的景區出口，離開景區結束對該景區內景點的游覽，完成本次游覽活動。

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

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

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

2 景區模型抽象與景點屬性表示

2.1 建立無向圖處理模型

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

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

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

2.2 景點信息表示策略

2.2.1 節點相對價值

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

對表1的幾點說明：

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

（2） 路徑時間代價表示vi與目標節點之間最短路徑之中所有路徑的權值之和，即從vi出發達到目標節點過程中經過的路徑所用的路程時間。

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

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

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

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

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

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

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

3.1 路線起點選擇

3.3 路線終點選擇

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

4 結 論

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

參考文獻

[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] 廖川榮.校園最佳游覽路線問題的數學模型分析[J].大學數學，2012，28（6）：78?82.

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

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

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

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

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

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