最佳游覽路線生成方案的設(shè)計(jì)與實(shí)現(xiàn)

王艷　印國(guó)成　孫茂圣

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）12-00-02

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

2 問(wèn)題模型

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

圖1中，假設(shè)XXX景區(qū)有四個(gè)出入口E/E_TL、E/E_TR、E/E_BL、E/E_BR和九個(gè)景點(diǎn)SS_A、SS_B、SS_C、SS_D、SS_E、SS_F、SS_G、SS_H、SS_I，其中景點(diǎn)SS_C和SS_D為景區(qū)的標(biāo)志性景點(diǎn)。在無(wú)向圖中，出入口與景點(diǎn)統(tǒng)一以節(jié)點(diǎn)來(lái)表示，路徑以邊來(lái)表示，邊的權(quán)值表示對(duì)應(yīng)路徑步行時(shí)間，建立了如圖1所示的景區(qū)信息的圖形模型，（SS_A，2，7）表示景點(diǎn)SS_A為二級(jí)節(jié)點(diǎn)，推薦的游覽時(shí)間為7分鐘。其定義如下：

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

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

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

3 基于Dijkstra算法的LCT表生成

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

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

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

節(jié)點(diǎn)A的LCT表生成過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

（2）在時(shí)間限制允許的條件下，景點(diǎn)按照游覽價(jià)值從高到低的順序進(jìn)行選取。

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

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