基于動態規劃在旅游線路規劃中的應用研究

切吉卓瑪

摘要：為給旅行者提供更優的旅游路線，使得所設計的路線更為合理和貼近人們的期望；本文以青海省內多日游為例運用運籌學中動態規劃等相關知識，利用LINGO軟件，分析各景點之間的最短路徑關系，通過建立模型、數據分析來實現目標最優化。

關鍵詞：旅游線路；動態規劃；LINGO

一、引言

旅游線路是在旅游景點路線規劃過程和線路設計過程中經常用到的詞匯。對于個人而言；滿足消費需求、在旅游過程中使成本最小、日程安排最方便是最初期望。而在滿足基本需求的基礎上降低成本、提高效益、并可面對突發事件及時調整路線是旅行社的期望。因此，在規劃和設計旅游線路時就要盡可能的考慮旅游線路的科學合理性。從旅游線路的研究方法來說；用動態規劃相關知識進行旅游線路分析和運算問題、能做出合理的優化安排、且便于發展有限資源的效益并可獲得合理性的結果。

迎合了當前社會的高速發展和旅游業的快速崛起及現代人對精神文化的渴求；且為了促進青海省內旅游發展的力度，以青海省內主要的旅游景點為例，運用動態規劃知識探討并分析旅游路程的情況。并應用LINGO解決最優路徑問題；并希望最終能推廣LINGO軟件及動態規劃知識在旅游線路中的實際運用。

二、問題提出

最短路徑是網絡規劃中的基本問題，在網絡理論中廣泛應用；因許多管理和實際應用問題都與最短路徑問題有關；因此，這類問題都可用最短路徑問題來建立并優化模型。由動態規劃求多個目標之間的多階段路徑問題；并用lingo來解決數據問題，可使結果更為合理實用。選取青海省內部分景點為例，在高速發展的快餐文化及物質文化泛濫而精神需求日益高漲的現狀下分析并探討各個景點之間的最優路徑問題。

最短路問題的一個典型應用就是設點問題，設點問題又稱為整數規劃問題；這類問題可分為連續和離散型兩類、單設施和多設施。不同類型的設點問題對設點的要求和指標都會有影響。而在實際旅游問題中的目標景點，為固定存在的多個點由旅客本人選擇目標圈中的一些點來規劃自己的路程問題，在這類問題中我們主要考慮個人的利益問題即消費成本最小化、日程安排最方便、所花費的路程最短。由動態規劃知識得多個目標之間的多階段路徑問題，并用lingo來解決實際中相應的數據問題。lingo api 的作用與complex的作用相同，均為算法引擎；Lingo是數學建模工具；具有簡潔的編程語言、友好的編輯和執行環境、更方便糾錯與調試；通過調用相應的優化引擎程序來求解模型，可以使得結果更為合理實用。

1.問題假設及其符號說明

1.1問題假設

1、旅客最先從塔爾寺出發；2、十五個目的地旅客都可到達； 3、旅客在途中不發生任何意外事故； 4、旅客在途中身體狀況良好且不會影響行程； 5、旅客在途中不做停留，只考慮行程問題； 6、旅客在考慮觀光景點時綜合各種情況優先考慮離市區較近的景點。

1.2 符號說明

i，j=（1，2…15）分別表示：dij——表示第i個目的地到第j個目的地的距離。D——表示總距離。ai——表示各個目的地i=（1…15）.其中a1=塔爾寺，a2 =青海湖，a3=孟達天池，a4 =龍羊峽，a5 =托索湖，a6 =萬丈鹽橋，a7 =察爾汗鹽湖，a8=昆侖山口，a9 =瀾滄江源頭，a10 =黃河源，a11=可可西里，a12 =長江源，a13=魯藏寺舊址，a14=文成公主廟，a15=年保玉則。Xij——表示第i目的地和第j目的地的0-1變量。

2.相關數據

對于選擇各個目標景點之間的距離通過高德地圖軟件查詢而得；相關數據如下表：

各景點之間距離（單位為Km）

塔爾寺 青海湖 孟達天池 龍羊峽 托索湖 萬丈鹽橋 察爾汗鹽湖 昆侖山 瀾滄江源頭 黃河

源 可可西里 長江源 魯藏寺舊址 文成公主廟

塔爾寺 0 269.1 202.4 169.1 429.9 769 755.8 959.9 773.6 532.9 140.7 1215.2 218.6 820

2.1問題解決

最短路問題是從某地出發，途經若干結點并最后到達目的地，要求找出路程或費用最小的路線。我們把旅游目的地問題看成是一個多階段決策問題。從a1出發，經過n階段，每個階段的決策是選擇下一個目的地。如果用所在的位置來表示狀態，那么狀態與階段數就不能完全決定決策集合了，因為已去過的目的地不需再去，所以決策集合與前選決策有關，用（ai，A）表示狀態，a1時所在目的地，A是還沒有去過目的地的集合。在狀態（ai，A）決策集合A中，取決策aiA，獲得的效益是ai到aj的距離dij，轉入下一個狀態（ai，A＼{aj}），再用最優化原理尋遞推公式。

采用Lingo程序編程求解，Lingo程序編程及運行結果如下：

最優路線：

a1→a13→a4→a2→a5→a10→a9→a14→a12→a11→a3→a7→a6→a15→a3→a1

三、總結

在快餐文化膨脹的現狀下，以當下最為流行的旅游為話題引述了其中所可能出現的一切問題。而動態規劃恰恰就可解決這類實際問題，盡管所求的問題的過程及方法不計其數；但運用最短路徑能更簡便精確的求得實際旅游中的最優問題。最短路徑問題是算法設計中的經典問題、也是現實世界許多應用中的基本問題。在解決旅游中遇到的各類問題時往往由于缺乏對路線的合理安排，造成了旅游途中自身體力的過度耗費；而且在自身有限時間的不合理利用上也造成了多種困擾。為此，此文將以青海省內旅游為例，并選取部分景點作為目標點；通過動態規劃知識尋求各個景點之間的最短路問題，將它看成一個多階段決策問題。利用最優化原理，尋找遞推公式，建立矩陣并采用lingo程序編程求解得出相應問題的結論。通過結論，希望旅游者在旅行途中盡可能的花費最少的路程去觀光完各個景點。

參考文獻：

[1]刁在筠，劉桂真，宿潔等，運籌學[M][第三版]，北京：高等教育出版社，2007.01.

[2] 張錚. 基于最短路徑分析的中間件設計與應用研究[J]. 測繪與空間地理信息. 2013（12）

[3]鄒時林，阮見，劉波等，最短路徑算法在旅游線路規劃中的應用——以廬山為例[J]測繪科學.2008.5