引 言
對于游客而言，參觀游覽的路線是否科學合理很大程度影響到游覽的體驗效果?？茖W合理的游覽路線能夠讓游客在花費較短的時間、路程代價下獲得更佳的游覽體驗。高質(zhì)量的游覽路線也能在旅游服務提供者在付出相同服務資源代價的情況下為其贏得游客更高的評價從而促進旅游相關產(chǎn)業(yè)的不斷發(fā)展進步。
完整的游覽路線由起點、終點、景點以及游覽活動需要經(jīng)過的所有路徑組成。游覽路線之間的區(qū)別在于能否使得游客合理有效的參觀游覽，能否滿足游客的相關要求。本文從游客的角度出發(fā)，將研究的目標定為尋找出能夠在滿足游覽時間限制的條件下最佳游覽路線的設計生成方案。
游覽路線的規(guī)劃設計的本質(zhì)工作是依據(jù)一定的規(guī)則選取何當?shù)木包c并選擇合理的游覽路線生成完整的游覽路線[1,2]。因此本文將研究工作劃分為三個部分，為研究對象建立合適的問題模型 ；對 Dijkstra 最短路徑算法的研究與改進實現(xiàn)對景點的對比選擇 [3] ；最佳游覽路線生成算法的設計完成最終的路線生成。
1 相關工作
旅游路線設計的相關研究根據(jù)出發(fā)點的不同主要分為基于旅行社需求的旅游路線的設計研究和基于游客需求的旅游路線的設計研究。兩者的相同之處在于都是以旅游景區(qū)為研究對象尋找滿足一定要求的游覽路線，不同之處在于其設定的游覽路線需要滿足的要求是不一樣的。游客對旅游路線的需求主要包括時間少、路程短、景點多、景點參觀價值高等。本文主要研究從游客的需求出發(fā)設計最佳游覽路線的生成方案， 因此對最佳游覽路線的要求與游客對游覽路線的需求是一致的。所以本文研究的目的是能夠生成一條滿足游客游覽時間限制，且游覽景點的數(shù)量、質(zhì)量都比其他路線占優(yōu)的最佳游覽路線。
Dijkstra 算法是圖論中用于求有向圖節(jié)點之間最短路徑問題的經(jīng)典算法，在工程項目的最短路徑問題研究中得到廣泛的應用。Dijkstra 算法在一定程度上進行了廣度優(yōu)先遍歷的變異，也可以視為啟發(fā)性搜索算法的特例。其特點為通用性強、程序設計簡單。而對于本文研究問題來說，其最大的優(yōu)點在于算法的運行結果是某一節(jié)點到圖中其他所有節(jié)點的最短路徑，這一特點使得可以設計更加合理全面的游覽路線中景點的選取策略并能提高景點選取的效率。
《校園最佳游覽路線問題的數(shù)學模型分析》一文中介紹了游覽校園的最佳游覽路線的問題處理模型的分析對本文中景區(qū)旅游最佳路線的設計方案提供了可參考的建模思路 [4]。將旅游路線的設計規(guī)劃問題轉(zhuǎn)化成在圖論視角下的無向圖最佳路線的設計問題，利用尋找無向圖中最短路徑的算法為最佳旅游路線的設計方案提供了可行的處理方案。
2 問題模型
一個旅游景區(qū)一般由多個出入口、內(nèi)部景點景觀、公共服務點以及相互之間路徑組成。游客在景區(qū)內(nèi)參觀游覽時，必定是按照一定游覽路線進行的。當游覽時間不足以參觀完景區(qū)內(nèi)所有景點時，此時對游客而言，最佳的游覽路線是在限定時間之內(nèi)能夠最有價值的游覽當前景區(qū)內(nèi)景點的路線。因此需要解決的問題為 ：如何定義游覽路線的游覽價值以及如何尋找在當前時間限制條件下游覽價值最高的路線。圖 1 所示即為某景區(qū)的旅游示意圖。
圖 1 中， 假設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é)點來表示，路徑以邊來表示，邊的權值表示對應路徑步行時間，建立了如圖 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 的最短路徑的權值與節(jié)點B 的游覽價值的比值。
3 基于Dijkstra算法的 LCT表生成
Dijkstra 算法[5,6] 也被稱為最短路徑算法，是圖論中用于求節(jié)點之間最短路徑的經(jīng)典算法。它采用標記法按照邊權值的大小順序來尋找節(jié)點之間的最短路徑。算法的基本思想為從源節(jié)點出發(fā)，從相鄰節(jié)點中找到邊最短的一條路徑，然后以該路徑為基礎尋找下一個可直接達到且最短的路徑并標記找到的節(jié)點，通過不斷的執(zhí)行上述步驟，最終得到源節(jié)點到圖中所有節(jié)點的最短路徑。本文中最佳游覽路線生成方案的基本思想是不斷尋找新的節(jié)點加入到游覽路線中直至該路線的游覽時間大于規(guī)定的時間限制。
通過運用 Dijkstra 算法尋找出節(jié)點之間的最短路徑結合 本文中節(jié)點的游覽價值屬性，綜合考慮得出節(jié)點之間的最低游 覽成本，實現(xiàn)從未選擇的節(jié)點之中選取游覽成本最低的景點， 從而使得最終生成的游覽路線是相同條件游覽成本最低、價 值最高的最佳游覽路線。
根據(jù)游覽價值的定義設一級節(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→ T L = 3 、 A→ B→ T R = 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 的結果，可以生成表 1，即LCT（A）表。
為圖中其他的節(jié)點進行相同的處理即可生成每個節(jié)點各自的LCT 表。當成功得到表中所有節(jié)點LCT 之后，就可開始游覽路線節(jié)點的選取工作，進行最佳游覽路線的設計實現(xiàn)。
4 最佳路線生成方案的設計
在前面的問題描述中我們對最佳游覽路線進行了初步的描述，此處給出本文最佳游覽線路的定義 ：最佳游覽線路是能夠在滿足時間限制條件下，以游覽成本從低到高的順序選擇景點進行游覽直至超出時間限制的路線。
根據(jù)上述定義以及實際需求，本文制定了如下幾點規(guī)則：
(1) 游覽路線必須以出入口節(jié)點開始并以出入口節(jié)點結束。
(2) 在時間限制允許的條件下，景點按照游覽價值從高到低的順序進行選取。
最佳路線生成方案的基本思想為 ：在規(guī)則 2的基礎上， 從一級景點中選擇推薦游覽時間最短的景點為基礎，選擇最近的兩個出口和入口為路線的起點生成一條過程路線，計算當前路線的游覽耗時，若未超過限定的游覽時間，就從過程路線中所有景點的LCT表中選取未加入游覽路線，并按照游覽價值由高到低且游覽成本最小的景點加入到游覽路線中，并驗證是否滿足時間限制。若滿足則重復上述操作 ；若超過時間限制，放棄最后選取的景點，得到最佳的游覽路線。這里需要說明的是，本文游覽路線設計方案能夠得到最佳游覽路線主要依據(jù)如下：
(1) 規(guī)則 2 的制定保證了游覽路線中游覽價值高的景點能夠優(yōu)先考慮。
(2) 基于Dijkstra最短路徑算法生成的LCT表能夠保證相同游覽價值的景點，路徑短的被優(yōu)先加入到游覽路線之中。
(3) 最佳游覽路線生成方案保證了游覽時間得到最大程度的利用。
如仍然以圖 1 中XXX 景點為例，實現(xiàn)最佳游覽路線的生成，這里假設限定的游覽時間為 45 分鐘。則：
Step1 ：因節(jié)點 C 與節(jié)點D 的游覽價值最高且節(jié)點C 的推薦游覽時間大于節(jié)點 D 的推薦游覽時間，以景點 D 為基礎，根據(jù) LCT（D）表得到兩個出入口 TR 和 BR，生成最短過程路線TR → D → H → BR，需注意此處D 節(jié)點并未參觀，因此當前路線所需要的游覽時間為 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，當前路線游覽所需時間為 3.5+12+5+15+3=38.5<45。
Step3 ：從TR、D、C、TL 四個節(jié)點的LCT 表中以游覽價值高低順序選擇游覽成本最低的節(jié)點，得到節(jié)點 A，并生成最短過程路線TR → D → A → C → TL，當前路線隨需游覽時間為 3.5+12+4+7+2+15+3=46.5>45，因此節(jié)點A 不能加入游覽路線當中，故在 45 分鐘的時間限制條件下，XXX 景區(qū)的最佳游覽路線為TR → D → C → TL。
5 結 語
針對在一定時間限制條件下設計景區(qū)的游覽路線設計規(guī)劃問題，本文通過對Dijkstra 最短路徑算法的研究定義并導出了節(jié)點的最低游覽成本LCT，并結合制定的三項路線生成規(guī)則成功設計了合理可行的最佳路線生成方案。本文在研究路線的生成方案時，考慮的因素包括景點的游覽價值和景點的游覽成本，而在實際的游覽過程中，會有更多的因素可能會對游客需要的游覽線路產(chǎn)生影響，如游客的個人偏好、景點附近的服務設施等因素。因此在未來的研究中可以研究更多的能夠影響路線生成方案的因素，使得研究對象符合實際需要解決的問題從而得到更加具有實用性的研究成果。
下載文檔
