最佳游覽路線生成方案的設計與實現

王艷　印國成　孫茂圣

摘 要：當游客選擇一個景區進行游覽參觀活動時，往往是希望能以一個能夠滿足自己游覽需求的最優游覽路線來進行旅游活動。在相同時間的限制條件下，該游覽路線優于其他游覽路線的地方在于能使游客獲得更高的游覽滿意度。因此，文章主要研究在已知景區及其包含景點、路徑等相關信息條件下，從圖論視角以無向圖相關知識為工具進行最佳游覽路線生成方案的設計研究。文中的研究完成了三項工作：建立以無向圖為知識背景的問題對象研究模型；改進Dijkstra最短路徑算法實現導出節點的LCT表；最佳游覽路線生成算法，并依據上述三個工作的研究成果來最終實現最佳游覽路線生成的完整方案。

關鍵詞：最短路徑；智能導覽；Dijkstra；最佳旅游路線

中圖分類號：TP311 文獻標識碼：A 文章編號：2095-1302（2015）12-00-02

0 引 言

對于游客而言，參觀游覽的路線是否科學合理很大程度影響到游覽的體驗效果。科學合理的游覽路線能夠讓游客在花費較短的時間、路程代價下獲得更佳的游覽體驗。高質量的游覽路線也能在旅游服務提供者在付出相同服務資源代價的情況下為其贏得游客更高的評價從而促進旅游相關產業的不斷發展進步。

完整的游覽路線由起點、終點、景點以及游覽活動需要經過的所有路徑組成。游覽路線之間的區別在于能否使得游客合理有效的參觀游覽，能否滿足游客的相關要求。本文從游客的角度出發，將研究的目標定為尋找出能夠在滿足游覽時間限制的條件下最佳游覽路線的設計生成方案。

游覽路線的規劃設計的本質工作是依據一定的規則選取何當的景點并選擇合理的游覽路線生成完整的游覽路線[1，2]。因此本文將研究工作劃分為三個部分，為研究對象建立合適的問題模型；對Dijkstra最短路徑算法的研究與改進實現對景點的對比選擇[3]；最佳游覽路線生成算法的設計完成最終的路線生成。

1 相關工作

旅游路線設計的相關研究根據出發點的不同主要分為基于旅行社需求的旅游路線的設計研究和基于游客需求的旅游路線的設計研究。兩者的相同之處在于都是以旅游景區為研究對象尋找滿足一定要求的游覽路線，不同之處在于其設定的游覽路線需要滿足的要求是不一樣的。游客對旅游路線的需求主要包括時間少、路程短、景點多、景點參觀價值高等。本文主要研究從游客的需求出發設計最佳游覽路線的生成方案，因此對最佳游覽路線的要求與游客對游覽路線的需求是一致的。所以本文研究的目的是能夠生成一條滿足游客游覽時間限制，且游覽景點的數量、質量都比其他路線占優的最佳游覽路線。

Dijkstra算法是圖論中用于求有向圖節點之間最短路徑問題的經典算法，在工程項目的最短路徑問題研究中得到廣泛的應用。Dijkstra算法在一定程度上進行了廣度優先遍歷的變異，也可以視為啟發性搜索算法的特例。其特點為通用性強、程序設計簡單。而對于本文研究問題來說，其最大的優點在于算法的運行結果是某一節點到圖中其他所有節點的最短路徑，這一特點使得可以設計更加合理全面的游覽路線中景點的選取策略并能提高景點選取的效率。

《校園最佳游覽路線問題的數學模型分析》一文中介紹了游覽校園的最佳游覽路線的問題處理模型的分析對本文中景區旅游最佳路線的設計方案提供了可參考的建模思路[4]。將旅游路線的設計規劃問題轉化成在圖論視角下的無向圖最佳路線的設計問題，利用尋找無向圖中最短路徑的算法為最佳旅游路線的設計方案提供了可行的處理方案。

2 問題模型

一個旅游景區一般由多個出入口、內部景點景觀、公共服務點以及相互之間路徑組成。游客在景區內參觀游覽時，必定是按照一定游覽路線進行的。當游覽時間不足以參觀完景區內所有景點時，此時對游客而言，最佳的游覽路線是在限定時間之內能夠最有價值的游覽當前景區內景點的路線。因此需要解決的問題為：如何定義游覽路線的游覽價值以及如何尋找在當前時間限制條件下游覽價值最高的路線。圖1所示即為某景區的旅游示意圖。

圖1中，假設XXX景區有四個出入口E/E_TL、E/E_TR、E/E_BL、E/E_BR和九個景點SS_A、SS_B、SS_C、SS_D、SS_E、SS_F、SS_G、SS_H、SS_I，其中景點SS_C和SS_D為景區的標志性景點。在無向圖中，出入口與景點統一以節點來表示，路徑以邊來表示，邊的權值表示對應路徑步行時間，建立了如圖1所示的景區信息的圖形模型，（SS_A，2，7）表示景點SS_A為二級節點，推薦的游覽時間為7分鐘。其定義如下：

定義1：游覽價值G（x），表示節點x的參觀游覽價值。在本此研究中將無向圖中節點分為四個等級，分別為一級節點、二級節點、三級節點和四級節點。其中一級節點代表景區的標志性景點，游覽價值最高，二級節點和三級節點的游覽價值依次減弱，四級節點代表景區的出入口，不具備游覽價值。

定義2：最短路徑S（a） = {Sab， Sac， Sad， ......}，表示從節點a到圖中其它節點b、c、d......的最短路徑。

定義3：最低游覽成本表LCT（x），表示節點x到圖中其它任意節點的最低游覽成本。游覽成本是綜合考慮節點的游覽價值與路徑代價而定義的，規定節點A到節點B的最低游覽成本為節點A到節點B的最短路徑的權值與節點B的游覽價值的比值。

3 基于Dijkstra算法的LCT表生成

Dijkstra算法[5，6]也被稱為最短路徑算法，是圖論中用于求節點之間最短路徑的經典算法。它采用標記法按照邊權值的大小順序來尋找節點之間的最短路徑。算法的基本思想為從源節點出發，從相鄰節點中找到邊最短的一條路徑，然后以該路徑為基礎尋找下一個可直接達到且最短的路徑并標記找到的節點，通過不斷的執行上述步驟，最終得到源節點到圖中所有節點的最短路徑。本文中最佳游覽路線生成方案的基本思想是不斷尋找新的節點加入到游覽路線中直至該路線的游覽時間大于規定的時間限制。

通過運用Dijkstra算法尋找出節點之間的最短路徑結合本文中節點的游覽價值屬性，綜合考慮得出節點之間的最低游覽成本，實現從未選擇的節點之中選取游覽成本最低的景點，從而使得最終生成的游覽路線是相同條件游覽成本最低、價值最高的最佳游覽路線。

根據游覽價值的定義設一級節點、二級節點、三級節點以及四級節點的游覽價值分別為10、3、2、0.1。現以圖1中SS_A節點為例，描述Dijkstra算法在本文中的運用以及節點LCT表的實現過程（注：在下面的內容中，為方便描述，以X代表形如SS_X的節點，以XX代表形如E/E_XX的節點）。

節點A的LCT表生成過程如下：

Step1：以節點A為源點，標記節點，從相鄰的節點中尋找路徑長度最短的節點得到節點C，標記節點A，得到A到C的最短路徑A→C=2。

Step2：以節點C為中間點，在未標記的相鄰節點中尋找最短路徑得到節點TL，發現（A→C→TL=5）>（A→TL=3）（A→B=3），標記節點TL與節點B，得到最短路徑A→TL=3和A→B=3，此時已有三條最短路徑A→C=2、A→TL=3和A→B=3。

Step3：分別以節點TL和節點B為中間節點，在未標記的相鄰節點中尋找最短路徑得到（A→TL→E=7）>（A→B→TR=5）>（A→D=5），標記節點D，得到最短路徑A→D=4，此時已有四條最短路徑A→C=2、A→TL=3、A→B=3和A→D=4。

Step4： 以上一步中標記的節點為中間節點，按照上述規律不斷尋找最短路徑直至所有節點都被標記，得到節點A到圖中其余所有節點的最短路徑分別為：

A→B=3、A→C=2、A→D=4、A→TL→E=7、A→C→F=5.5、A→C→F→G=7.5、A→D→H=6.5、A→D→I=9.5、A→TL=3、A→B→TR=5、A→C→F→BL=8.5、A→D→H→BR=8.5。

Step5：計算節點A到圖中其余節點的最低游覽成本。如節點B為二級節點，所以節點A到節點B的的最低游覽成本為3÷3=1。

Step6：根據Step4和Step5的結果，可以生成表1，即LCT（A）表。

為圖中其他的節點進行相同的處理即可生成每個節點各自的LCT表。當成功得到表中所有節點LCT之后，就可開始游覽路線節點的選取工作，進行最佳游覽路線的設計實現。

4 最佳路線生成方案的設計

在前面的問題描述中我們對最佳游覽路線進行了初步的描述，此處給出本文最佳游覽線路的定義：最佳游覽線路是能夠在滿足時間限制條件下，以游覽成本從低到高的順序選擇景點進行游覽直至超出時間限制的路線。

根據上述定義以及實際需求，本文制定了如下幾點規則：

（1）游覽路線必須以出入口節點開始并以出入口節點結束。

（2）在時間限制允許的條件下，景點按照游覽價值從高到低的順序進行選取。

最佳路線生成方案的基本思想為：在規則2的基礎上，從一級景點中選擇推薦游覽時間最短的景點為基礎，選擇最近的兩個出口和入口為路線的起點生成一條過程路線，計算當前路線的游覽耗時，若未超過限定的游覽時間，就從過程路線中所有景點的LCT表中選取未加入游覽路線，并按照游覽價值由高到低且游覽成本最小的景點加入到游覽路線中，并驗證是否滿足時間限制。若滿足則重復上述操作；若超過時間限制，放棄最后選取的景點，得到最佳的游覽路線。這里需要說明的是，本文游覽路線設計方案能夠得到最佳游覽路線主要依據如下：

（1）規則2的制定保證了游覽路線中游覽價值高的景點能夠優先考慮。

（2）基于Dijkstra最短路徑算法生成的LCT表能夠保證相同游覽價值的景點，路徑短的被優先加入到游覽路線之中。

（3）最佳游覽路線生成方案保證了游覽時間得到最大程度的利用。

如仍然以圖1中XXX景點為例，實現最佳游覽路線的生成，這里假設限定的游覽時間為45分鐘。則：

Step1： 因節點C與節點D的游覽價值最高且節點C的推薦游覽時間大于節點D的推薦游覽時間，以景點D為基礎，根據LCT（D）表得到兩個出入口TR和BR，生成最短過程路線TR→D→H→BR，需注意此處D節點并未參觀，因此當前路線所需要的游覽時間為3.5+12+2.5+2=20<45。

Step2： 從TR、BR以及D的三個節點的LCT表中尋找游覽成本最低的一級節點。若沒有一級節點，則尋找二級節點游覽成本最低的節點并依次類推，得到節點C，根據節點C和D的LCT表生成最短過程路線TR→D→C→TL，當前路線游覽所需時間為3.5+12+5+15+3=38.5<45。

Step3： 從TR、D、C、TL四個節點的LCT表中以游覽價值高低順序選擇游覽成本最低的節點，得到節點A，并生成最短過程路線TR→D→A→C→TL，當前路線隨需游覽時間為3.5+12+4+7+2+15+3=46.5>45，因此節點A不能加入游覽路線當中，故在45分鐘的時間限制條件下，XXX景區的最佳游覽路線為TR→D→C→TL。

5 結 語

針對在一定時間限制條件下設計景區的游覽路線設計規劃問題，本文通過對Dijkstra最短路徑算法的研究定義并導出了節點的最低游覽成本LCT，并結合制定的三項路線生成規則成功設計了合理可行的最佳路線生成方案。本文在研究路線的生成方案時，考慮的因素包括景點的游覽價值和景點的游覽成本，而在實際的游覽過程中，會有更多的因素可能會對游客需要的游覽線路產生影響，如游客的個人偏好、景點附近的服務設施等因素。因此在未來的研究中可以研究更多的能夠影響路線生成方案的因素，使得研究對象符合實際需要解決的問題從而得到更加具有實用性的研究成果。

參考文獻

[1] 蔣滿元.旅行社的旅游線路優化設置問題探討[J].技術經濟與管理研究， 2008（4）：7-9.

[2]朱珠；張欣.淺談智慧旅游感知體系和管理平臺的構建[J].江蘇大學學報（社會科學版），2011（6）：97-100.

[3] Schrijver， A. A combinatorial algorithm minimizing sub-modular functions in strongly polynomial time[J]. Comb. Theory Ser. B ，2000，80：346–355.

[4] 廖川榮.校園最佳游覽路線問題的數學模型分析[J].大學數學，2012，28（6）：78-82.

[5] 李元臣.基于Dijkstra算法的網絡最短路徑分析[J].微計算機應用，2004，25（3）：295-362.

[6] Kolmogorov， V， Shioura， A. New algorithms for convex cost tension problem with application to computer vision[J]. Discrete Optim，2009（6）：378–393.