最佳旅游線路-數(shù)學(xué)建模

1、最佳云南旅游路線設(shè)計摘 要本文主要研究最佳旅游路線的設(shè)計問題。在滿足相關(guān)約束條件的情況下，花最少的錢游覽盡可能多的景點(diǎn)是我們追求的目標(biāo)?；趯Υ说难芯?，建立數(shù)學(xué)模型，設(shè)計出最佳的旅游路線。第一問給定時間約束，要求為設(shè)計合適的旅游路線。我們建立了一個最優(yōu)規(guī)劃模型，在給定游覽景點(diǎn)個數(shù)的情況下以人均總費(fèi)用最小為目標(biāo)。再引入01變量表示是否游覽某個景點(diǎn)，從而推出交通費(fèi)用和景點(diǎn)花費(fèi)的函數(shù)表達(dá)式，給出相應(yīng)的約束條件，使用lingo編程對模型求解。推薦方案： 第二問放松時間約束，要求游客們游遍所有的景點(diǎn)，該問題也就成了典型的貨郎擔(dān)（TSP）問題。同樣使用第一問的模型，改變時間約束，使用lingo編程得到最佳

2、旅游路線為： 本文思路清晰，模型恰當(dāng)，結(jié)果合理.由于附件所給數(shù)據(jù)的繁雜，給數(shù)據(jù)的整理帶來了很多麻煩，故我們利用Excel排序，SPSS預(yù)測，這樣給處理數(shù)據(jù)帶來了不少的方便。本文成功地對01變量進(jìn)行了使用和約束，簡化了模型建立難度，并且可方便地利用數(shù)學(xué)軟件進(jìn)行求解。此外，本文建立的模型具有很強(qiáng)普適性，便于推廣。關(guān)鍵詞：最佳路線 TCP問題 景點(diǎn)個數(shù) 最小費(fèi)用一 問題重述云南是我國的旅游大省，擁有豐富的旅游資源，吸引了大批的省外游客，旅游業(yè)正在成為云南的支柱產(chǎn)業(yè)。隨著越來越多的人選擇到云南旅游，旅行社也推出了各種不同類型的旅行路線，使得公眾的面臨多條線路的選擇問題。假設(shè)某一個從沒有到過云南的人準(zhǔn)備

3、在假期帶家人到云南旅游，預(yù)計從昆明出發(fā)，并最終返回昆明。請你們?yōu)樗O(shè)計一條在云南旅游的最佳路線初步設(shè)想有如下線路可供選擇：一號線：昆明-玉溪-思茅二號線：昆明-大理-麗江三號線：昆明-大理-香格里拉四號線：昆明-玉溪-西雙版納五號線：昆明-玉溪-思茅-西雙版納-大理-麗江-香格里拉每條線路中的景點(diǎn)可以全部參觀，也可以參觀其中之一。結(jié)合上述要求，請你回答下列問題：一、請你們?yōu)橛慰驮O(shè)計合適的旅游路線，假設(shè)使游客在10天時間內(nèi)花最少的錢盡可能的游更多的地方。二、如果有游客的時間非常充裕（比如一個月），游客打算將上述旅游景點(diǎn)全部參觀完畢后才離開云南，請你們?yōu)橛慰驮O(shè)計合適的旅游路線，使在云南境內(nèi)的交通費(fèi)

4、用盡量地節(jié)省。二 問題分析2.1問題背景的理解：根據(jù)對題目的理解我們可以知道，旅游的總費(fèi)用包括交通費(fèi)用和在景點(diǎn)游覽時的費(fèi)用，而在確定了要游覽的景點(diǎn)的個數(shù)后，所以我們的目標(biāo)就是在滿足所有約束條件的情況下，求出成本的最小值。2.2問題一和問題二的分析：問題一要求我們?yōu)橛慰驮O(shè)計合適的旅游路線，假設(shè)使游客在10天時間內(nèi)花最少的錢游盡可能多的地方。在這里我們的做法是在滿足相應(yīng)的約束條件下，先確定游覽的景點(diǎn)數(shù)，然后計算出在這種情況下的最小花費(fèi)。這樣最終會得出幾種最佳方案，而游客可以根據(jù)自己的實(shí)際情況進(jìn)行選擇。問題二實(shí)質(zhì)上是在問題一的基礎(chǔ)上改變了時間約束，即游客要游覽所有的景點(diǎn)，我們完全可以使用與問題一同樣

5、的方法進(jìn)行求解。三 模型假設(shè)1.所給的5條路線每條路線中的景點(diǎn)可以全部參觀，也可以參觀其一；2. 游客使用旅游大巴安排他們往返于各個旅游景點(diǎn)，其交通費(fèi)用、在景點(diǎn)的花費(fèi)、在景點(diǎn)的逗留時間參照當(dāng)?shù)乜瓦\(yùn)公司及旅行社的數(shù)據(jù)；3. 游客們所乘坐的旅游大巴平均時速為50km/h，平均費(fèi)用為0.3元/km；4.一個景點(diǎn)直接到達(dá)另外一個景點(diǎn)是指，途中經(jīng)過的其他景點(diǎn)只是一個轉(zhuǎn)站地，而并不進(jìn)行游覽；5.在限定的時間內(nèi)，游客最終要返回昆明，并且假設(shè)昆明是游客們肯定要去的一個旅游景點(diǎn)；6. 游客們在途中和游覽景點(diǎn)的時間為12小時，而另外12小時為休息、用餐及其他瑣事時間。四 符號說明,第個或者第個景點(diǎn)， ，=1，2，

6、7；分別表示昆明 玉溪 思茅 西雙版納 大理 麗江 香格里拉 每個游客的旅游總花費(fèi)；每個游客在第個景點(diǎn)的逗留時間；每個游客在個景點(diǎn)的總消費(fèi)；從第個景點(diǎn)到第個景點(diǎn)路途中所需時間；從第個景點(diǎn)到第個景點(diǎn)所需的交通費(fèi)用； 五 模型建立及求解5.1 問題一： 5.1.1 目標(biāo)函數(shù)的確立： 經(jīng)過對題目分析，我們可以知道本題所要實(shí)現(xiàn)的目標(biāo)是，使游客在10天時間內(nèi)花最少的錢游覽盡可能多的地方。顯然，花費(fèi)最少和游覽的景點(diǎn)盡量多是該問題的兩個目標(biāo)。因此，我們的做法是在滿足相應(yīng)的約束條件下，先確定游覽的景點(diǎn)數(shù)，然后計算出在這種情況下的最小花費(fèi)。這樣最終會得出幾種旅游路線，而游客可以根據(jù)自己的實(shí)際情況進(jìn)行選擇。 游覽

7、的總費(fèi)用由2部分組成，分別為交通總費(fèi)用和在旅游景點(diǎn)的花費(fèi)。我們定義：每個游客的旅游總花費(fèi)；每個游客的交通總費(fèi)用；每個游客的旅游景點(diǎn)的花費(fèi)；從而得到目標(biāo)函數(shù)： Min （1）交通總花費(fèi)因?yàn)楸硎緩牡趥€景點(diǎn)到第個景點(diǎn)所需的交通費(fèi)用，而是判斷游客是否從第個景點(diǎn)直接到第個景點(diǎn)的01變量，因此我們可以很容易的得到交通總費(fèi)用為：（2）旅游景點(diǎn)的花費(fèi) 因?yàn)楸硎居慰驮趥€景點(diǎn)的總消費(fèi)，也可以表示出游客是否到達(dá)過第個和第個景點(diǎn)，而整個旅游路線又是一個環(huán)形，因此實(shí)際上將游客在所到景點(diǎn)的花費(fèi)計算了兩遍，從而我們可得旅游景點(diǎn)的花費(fèi)為：從而我們可以得到目標(biāo)函數(shù)為：Min +5.1.2 約束條件：時間約束假設(shè)游客在云南的旅游

8、時間應(yīng)該不多于10天(120小時)，而這些時間包括在路途中的時間和在旅游景點(diǎn)逗留的時間。因?yàn)楸硎緩牡趥€景點(diǎn)到第個景點(diǎn)路途中所需時間，所以路途中所需總時間為；表示游客在第個景點(diǎn)的逗留時間，故游客在旅游景點(diǎn)的總逗留時間為。因此，總的時間約束為：+120 旅游景點(diǎn)數(shù)約束 根據(jù)假設(shè)，整個旅游路線是環(huán)形，即最終游客要回到成都，因此即表示游客旅游的景點(diǎn)數(shù)，這里我們假定要旅游的景點(diǎn)數(shù)為（=2，3，11）。因此旅游景點(diǎn)數(shù)約束為： （=2，3，7）01變量約束 我們可以把所有的景點(diǎn)連成一個圈，而把每一個景點(diǎn)看做圈上一個點(diǎn)。對于每個點(diǎn)來說，只允許最多一條邊進(jìn)入，同樣只允許最多一條邊出來，并且只要有一條邊進(jìn)入就要有

9、一條邊出去。因此可得約束： （，=1，2，7） 當(dāng)時，因?yàn)槔ッ魇浅霭l(fā)點(diǎn)，所以；時，因?yàn)橛慰妥罱K要回到昆明，所以。 綜合以上可知， （，=1，2，7） 同樣，當(dāng)，時，根據(jù)題意不可能出現(xiàn)，即不可能出現(xiàn)游客在兩地間往返旅游，因?yàn)檫@樣顯然不滿足游覽景點(diǎn)盡量多的原則。因此我們可得約束： （，=2，3，7）5.1.3模型建立：綜上所述，我們可以得到總的模型為：Min +約束條件：+120 （=2，3，7） （，=1，2，7） （，=2，3，7）5.1.4 模型求解與結(jié)果分析： 在這里我們引入以下符號：第個景點(diǎn)和第個景點(diǎn)之間的路程；游客所乘坐的旅游大巴的平均時速，=50km/h； 游客所乘坐的旅游大巴的平均

10、費(fèi)用，=0.3元/h；通過上網(wǎng)查詢資料，我們可以得到的具體值，根據(jù)公式=/可得到相應(yīng)的，同樣根據(jù)公式=×可以得到相應(yīng)的（，=1，2，7）。（、和的具體數(shù)值見附錄）同樣，通過對云南的一些旅行社進(jìn)行咨詢，我們得出游客在第個景點(diǎn)的最佳逗留時間和游客在第個景點(diǎn)總消費(fèi)：t1t2t3t4t5t6t7(單位：小時)c1c2c3c4c5c6c7 (單位：元)從而根據(jù)模型，使用Lingo編程，得出結(jié)果如下表：旅游景點(diǎn)數(shù)n234每人總花費(fèi)m（單位：元）路線旅游景點(diǎn)數(shù)n56每人總花費(fèi)m（單位：元）路線旅游景點(diǎn)數(shù)n7每人總花費(fèi)m（單位：元）路線（其中數(shù)字1，2，7；分別表示昆明 玉溪 思茅 西雙版納 大理

11、麗江 香格里拉）對于上述結(jié)果，我們的推薦為：路線一：路線二：路線三：5.2 問題二5.2.1 目標(biāo)函數(shù)的確立：此問與第一問大同小異，不同的是游客要完成所有景點(diǎn)的旅游，而目標(biāo)函數(shù)是求最少的交通費(fèi)。由第一問結(jié)論可知，交通費(fèi)用為：因此，該問題的目標(biāo)函數(shù)為：Min 5.2.2 約束條件：時間約束 該問與上一問相比，放寬了對時間的要求，不妨可以假定限制的時間為一個月（360個小時），同上一問可得：+360旅游景點(diǎn)數(shù)約束 由題目要求可知，因?yàn)橛慰蜁r間充裕，因此他們打算游覽完全部7個景點(diǎn)。由第一問知道表示游客游覽的景點(diǎn)總數(shù)，因此該約束為： (，=1，2，7)01變量約束根據(jù)假設(shè)，整個旅游路線是環(huán)形，即最終游

12、客要回到昆明，因此我們可以把整個路線看做一個Hamilton（哈密爾頓）圈，這樣該問題就歸結(jié)為貨郎擔(dān)（TSP）（哈密爾頓）問題，當(dāng)然前提是我們已經(jīng)知道了要旅游所有的景點(diǎn)。因此，對于Hamilton圈中的每個點(diǎn)來說，只允許有一條邊進(jìn)入，同樣，也只允許有一條邊出去。用公式表示即為： （，=1，2，7）同樣，當(dāng)，時，根據(jù)題意不可能出現(xiàn)，即不可能出現(xiàn)游客在兩地間往返旅游，因?yàn)檫@樣顯然不滿足游覽景點(diǎn)盡量多的原則。因此我們可得約束： （，=2，3，7）5.2.3模型建立：綜上所述，我們可以得到總的模型為：Min 約束條件：+360 （，=1，2，7） （，=1，2，7） （，=2，3，7）5.2.4 模型

13、求解與結(jié)果分析：根據(jù)模型，使用Lingo編程，得出結(jié)果為：旅游景點(diǎn)數(shù)n7每人總花費(fèi)m（單位：元）路線六 模型的評價、改進(jìn)及推廣6.1模型的評價1.本文思路清晰，模型恰當(dāng)，得出的方案合理； 2.本文成功的使用了01變量，使模型的建立和編程得以順利進(jìn)行；3.在第二問中采用了TCP算法，簡化了模型的求解難度；4.問題五由于數(shù)據(jù)龐大，對程序的要求很高，盡管經(jīng)過了檢驗(yàn)，但結(jié)果依然比較粗糙，有待進(jìn)行進(jìn)一步的改進(jìn)。6.2模型的改進(jìn)與推廣： 1.實(shí)際情況中，兩景點(diǎn)之間可能還有出公路外其他交通方式，如航班、鐵路，增加這些考慮后，結(jié)果會更加合理。2.因數(shù)據(jù)資料搜集的不完整，準(zhǔn)確性也有待商榷，而且沒有對最終方案進(jìn)行

14、更為細(xì)致的討論研究，這些方面有待七 參考文獻(xiàn)1姜啟源 謝金星 葉俊，數(shù)學(xué)模型（第三版），北京：高等教育出版社，2003。2謝金星 薛毅，優(yōu)化建模與LINDO/LINGO軟件，北京：清華大學(xué)出版社，2005。3周仁郁，SPSS13.0統(tǒng)計軟件，成都，西南交通大學(xué)出版社，2005。4李慶揚(yáng) 王能超 易大義，數(shù)值分析，北京：清華大學(xué)出版社 施普林格出版社，2001。八 附錄附錄清單：附錄1為搜集的一些數(shù)據(jù)附錄2為相關(guān)程序及運(yùn)行結(jié)果附錄1： 網(wǎng)上查詢到的一些數(shù)據(jù)及相應(yīng)的計算出的數(shù)據(jù)：=附錄2：程序及運(yùn)行結(jié)果（由于數(shù)據(jù)龐大，只選擇了部分?jǐn)?shù)據(jù)）第一問：（程序）sets:jingdian/1.7/:c,t,

15、l;!其中：1,2,.,7分別代表昆明 玉溪 思茅 西雙版納 大理 麗江 香格里拉 ；c，t分別表示旅行團(tuán)在各景點(diǎn)的吃住消費(fèi)和逗留時間；w表示各景點(diǎn)選擇性權(quán)重；l是為了控制不出現(xiàn)兩個以上環(huán)形回路而設(shè)的一個變量;links(jingdian,jingdian):r,cc,tt;!其中：r為0-1變量（0表示兩景點(diǎn)不相連，1表示兩景點(diǎn)相通）；cc為兩景點(diǎn)之間的交通費(fèi)用；tt為兩景點(diǎn)之間的交通時間;endsetsdata:t=7 24 18 12 36 30 12 9 15 24 17;c=120 423 300 135 378 390 175 90 148 303 241;tt=08.544.74

16、2.823.445.088.41.321.546.146.68.5401.2211.5212.1410.913.18.848.9814.8415.544.741.22011.2211.829.3811.587.667.4613.4413.92.8211.5211.2200.887.788.084.024.245.846.33.4412.1411.820.8808.428.244.664.8866.465.0810.99.387.788.4202.184.244.045.986.748.413.111.588.088.242.1806.086.223.862.861.328.847.664.02

17、4.664.246.0800.36.286.741.548.987.464.244.884.046.220.306.086.546.1414.8413.445.8465.983.866.286.0802.086.615.5413.96.36.466.742.866.746.542.080;!其中：主對角線為零,表示各景點(diǎn)到自身交通費(fèi)用為零;cc=0128.171.142.351.676.212619.823.192.199128.1018.3172.8182.1163.5196.5132.6134.7222.6233.171.118.30168.3177.3140.7173.7114.9111

18、.9201.6208.542.3172.8168.3013.2116.7121.260.363.687.694.551.6182.1177.313.20126.3123.669.973.29096.976.2163.5140.7116.7126.3032.763.660.689.7101.1126196.5173.7121.2123.632.7091.293.357.942.919.8132.6114.960.369.963.691.204.594.2101.123.1134.7111.963.673.260.693.34.5091.298.192.1222.6201.687.69089.75

19、7.994.291.2031.299233.1208.594.596.9101.142.9101.198.131.20;!其中：主對角線為零,表示各景點(diǎn)到自身的交通時間為零;n=?;!其中：n表示計劃游玩的景點(diǎn)數(shù)目;enddatamin=sum(jingdian(j):sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j);!目標(biāo)函數(shù)：表示計劃游玩的景點(diǎn)數(shù)目為n時的最小費(fèi)用;for(jingdian(i):r(i,i)=0);!約束條件：表示各景點(diǎn)到自身沒有路線相連的約束條件;for(jingdian(i)|i#ge#2:for(jingdian(j)|j

20、#ge#2:r(i,j)+r(j,i)<1);!約束條件：表示除起點(diǎn)（成都）外，若旅行團(tuán)從景點(diǎn)i到景點(diǎn)j去游玩（即r(i,j)=1），則不會再從景點(diǎn)j到景點(diǎn)i去游玩（即r(j,i)=0），也就是說除起點(diǎn)外每個景點(diǎn)只游玩一次;a=sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j);sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)<120;!約束條件:表示總的旅行時間（交通時間和景點(diǎn)逗留時間）不超過給定時間10天120小時;for(jin

21、gdian(i):sum(jingdian(j):r(i,j)=sum(jingdian(j):r(j,i);for(jingdian(i)|i#eq#1:sum(jingdian(j):r(i,j)=1);for(jingdian(i)|i#ne#1:sum(jingdian(j):r(i,j)<1);!這三個約束條件：表示起點(diǎn)（成都）有且僅有一條路線出去和一條路線進(jìn)來，其它景點(diǎn)要么有且僅有一條路線出去和一條路線進(jìn)來，要么既沒有路線出去也沒有路線進(jìn)來;for(links:bin(r);!約束條件:表示0-1變量約束;sum(jingdian(j):sum(jingdian(i):r(i

22、,j)=n;!約束條件:表示旅游景點(diǎn)的數(shù)目為n的約束;for(jingdian(i):for(jingdian(j)|j#gt#1#and#j#ne#i:l(j)>=l(i)+r(i,j)-(n-2)*(1-r(i,j)+(n-3)*r(j,i);for(jingdian(i)|i#gt#1:l(i)<n-1-(n-2)*r(1,i);l(i)>1+(n-2)*r(i,1);!這兩個約束條件：為了控制不出現(xiàn)兩個以上環(huán)形回路，保證有且僅有一條環(huán)形路線；結(jié)果：（以n=5為例）由于數(shù)據(jù)龐大，只剪切出重要的部分如下：Global optimal solution found at i

23、teration: 2042 Objective value: 949.1000 Variable Value Reduced Cost N 5.000000 0.000000 R( 1, 4) 1.000000 169.8000 R( 4, 7) 1.000000 276.2000 R( 7, 9) 1.000000 254.8000 R( 8, 1) 1.000000 124.8000 R( 9, 8) 1.000000 123.5000 第二問：sets:jingdian/1.7/:c,t,l;!其中：1,2,.,7分別代表昆明 玉溪 思茅 西雙版納 大理 麗江 香格里拉；c，t分別表示

24、旅行團(tuán)在各景點(diǎn)的吃住消費(fèi)和逗留時間；l是為了控制不出現(xiàn)兩個以上環(huán)形回路而設(shè)的一個變量;links(jingdian,jingdian):r,cc,tt;!其中：r為0-1變量（0表示兩景點(diǎn)不相連，1表示兩景點(diǎn)相通）；cc為兩景點(diǎn)之間的交通費(fèi)用；tt為兩景點(diǎn)之間的交通時間;endsetsdata:t=7 24 18 12 36 30 12 9 15 24 17;c=120 423 300 135 378 390 175 90 148 303 241;tt=08.544.742.823.445.088.41.321.546.146.68.5401.2211.5212.1410.913.18.848

25、.9814.8415.544.741.22011.2211.829.3811.587.667.4613.4413.92.8211.5211.2200.887.788.084.024.245.846.33.4412.1411.820.8808.428.244.664.8866.465.0810.99.387.788.4202.184.244.045.986.748.413.111.588.088.242.1806.086.223.862.861.328.847.664.024.664.246.0800.36.286.741.548.987.464.244.884.046.220.306.086.

26、546.1414.8413.445.8465.983.866.286.0802.086.615.5413.96.36.466.742.866.746.542.080;!其中：主對角線為零,表示各景點(diǎn)到自身交通費(fèi)用為零;cc=0128 7142527712620239299128018 173182 1641971331352232337118016817714117411511220220942173168013117 12160.648895521821771301261247073909776164 141117126033646190101126197 17412112433091935

27、843201331156070649105941012313511264736193509198922232028890905894910319923320995971014310198310;!其中：主對角線為零,表示各景點(diǎn)到自身的交通時間為零;enddatamin=sum(jingdian(j):sum(jingdian(i):r(i,j)*(cc(i,j)+0.5*(c(i)+c(j);!目標(biāo)函數(shù)：表示計劃游玩的景點(diǎn)數(shù)目為n時的最小費(fèi)用;for(jingdian(i):r(i,i)=0);!約束條件：表示各景點(diǎn)到自身沒有路線相連的約束條件;for(jingdian(i)|i#ge#2:f

28、or(jingdian(j)|j#ge#2:r(i,j)+r(j,i)<1);!約束條件：表示除起點(diǎn)（昆明）外，若旅行團(tuán)從景點(diǎn)i到景點(diǎn)j去游玩（即r(i,j)=1），則不會再從景點(diǎn)j到景點(diǎn)i去游玩（即r(j,i)=0），也就是說除起點(diǎn)外每個景點(diǎn)只游玩一次;a=sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j);sum(jingdian(j):sum(jingdian(i):r(i,j)*(tt(i,j)+0.5*(t(i)+t(j)<360;!約束條件:表示總的旅行時間（交通時間和景點(diǎn)逗留時間）不超過給定時間30天360小時;for(jingdian(i):sum(jingd