基于動態(tài)規(guī)劃在旅游線路規(guī)劃中的應用研究

切吉卓瑪

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

關(guān)鍵詞：旅游線路；動態(tài)規(guī)劃；LINGO

一、引言

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

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

二、問題提出

最短路徑是網(wǎng)絡(luò)規(guī)劃中的基本問題，在網(wǎng)絡(luò)理論中廣泛應用；因許多管理和實際應用問題都與最短路徑問題有關(guān)；因此，這類問題都可用最短路徑問題來建立并優(yōu)化模型。由動態(tài)規(guī)劃求多個目標之間的多階段路徑問題；并用lingo來解決數(shù)據(jù)問題，可使結(jié)果更為合理實用。選取青海省內(nèi)部分景點為例，在高速發(fā)展的快餐文化及物質(zhì)文化泛濫而精神需求日益高漲的現(xiàn)狀下分析并探討各個景點之間的最優(yōu)路徑問題。

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

1.問題假設(shè)及其符號說明

1.1問題假設(shè)

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

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.相關(guān)數(shù)據(jù)

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

各景點之間距離（單位為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問題解決

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

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

最優(yōu)路線：

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

三、總結(jié)

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

參考文獻：

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

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

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