王艷　印國成　孫茂圣

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

關(guān)鍵詞：最短路徑；智能導(dǎo)覽；Dijkstra；最佳旅游路線

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

0 引 言

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

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

游覽路線的規(guī)劃設(shè)計的本質(zhì)工作是依據(jù)一定的規(guī)則選取何當(dāng)?shù)木包c并選擇合理的游覽路線生成完整的游覽路線[1，2]。因此本文將研究工作劃分為三個部分，為研究對象建立合適的問題模型；對Dijkstra最短路徑算法的研究與改進實現(xiàn)對景點的對比選擇[3]；最佳游覽路線生成算法的設(shè)計完成最終的路線生成。

1 相關(guān)工作

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

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

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

2 問題模型

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

圖1中，假設(shè)XXX景區(qū)有四個出入口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為景區(qū)的標志性景點。在無向圖中，出入口與景點統(tǒng)一以節(jié)點來表示，路徑以邊來表示，邊的權(quán)值表示對應(yīng)路徑步行時間，建立了如圖1所示的景區(qū)信息的圖形模型，（SS_A，2，7）表示景點SS_A為二級節(jié)點，推薦的游覽時間為7分鐘。其定義如下：

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

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

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

3 基于Dijkstra算法的LCT表生成

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

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

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

節(jié)點A的LCT表生成過程如下：

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

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

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

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

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：計算節(jié)點A到圖中其余節(jié)點的最低游覽成本。如節(jié)點B為二級節(jié)點，所以節(jié)點A到節(jié)點B的的最低游覽成本為3÷3=1。

Step6：根據(jù)Step4和Step5的結(jié)果，可以生成表1，即LCT（A）表。

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

4 最佳路線生成方案的設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

參考文獻

[1] 蔣滿元.旅行社的旅游線路優(yōu)化設(shè)置問題探討[J].技術(shù)經(jīng)濟與管理研究， 2008（4）：7-9.

[2]朱珠；張欣.淺談智慧旅游感知體系和管理平臺的構(gòu)建[J].江蘇大學(xué)學(xué)報（社會科學(xué)版），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] 廖川榮.校園最佳游覽路線問題的數(shù)學(xué)模型分析[J].大學(xué)數(shù)學(xué)，2012，28（6）：78-82.

[5] 李元臣.基于Dijkstra算法的網(wǎng)絡(luò)最短路徑分析[J].微計算機應(yīng)用，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.