運籌學(xué)論文_重慶市旅游線路規(guī)劃

1、重慶市旅游線路規(guī)劃鐘道軍摘要： 重慶位于中國西南部，位于長江與嘉陵江交匯處，四面環(huán)山，江水回繞，游資源堪稱得天獨厚。重慶近幾年旅游業(yè)迅速發(fā)展，許多人在重慶旅游時，由于缺少相關(guān)指導(dǎo)和路線規(guī)劃，造成了許多時間和金錢的浪費。本文列舉了重慶的一部分景點，分別討論了不考慮時間如何讓旅游費用最省、不考慮費用如何讓用時最少兩種情況，運用運籌學(xué)相關(guān)知識建立模型，并用計算機進行求解，找出合適的旅游線路，以此來為游客選擇旅游線路提供參考。關(guān)鍵詞： 旅游；線路規(guī)劃；旅行商問題1、提出問題一名游客準(zhǔn)備今年7月1日從淶灘古鎮(zhèn)出發(fā)在重慶市范圍內(nèi)旅游（包括出發(fā)點），希望能夠游玩的景點如下圖所示：圖11 游客的目標(biāo)景點游客到

2、各景點的乘車時間、費用以及停留時間和住宿時間、費用如下表所示：表11 各景點之間的乘車時間表（單位：小時）淶灘古鎮(zhèn)大足石刻渣滓洞樵坪山仙女山萬盛石林四面山淶灘古鎮(zhèn)032.544.53.53.5大足石刻3033.5433渣滓洞2.5201.53.522.5樵坪山2.52.51.5032.53仙女山4.5433044萬盛石林3.5322.5403四面山3.532.53430表12 各景點之間的乘車費用表（單位：元）淶灘古鎮(zhèn)大足石刻渣滓洞樵坪山仙女山萬盛石林四面山淶灘古鎮(zhèn)05042551159086大足石刻50043551218968渣滓洞4046030765360樵坪山5156210654658仙

3、女山1151207265074110萬盛石林9089534674052四面山86686058110520表13 游客在各景點停留的時間（單位：小時）景點名稱淶灘古鎮(zhèn)大足石刻渣滓洞樵坪山仙女山萬盛石林四面山停留時間3.54.52.53433.5表14 各景點食宿費用表（單位：元）景點名稱淶灘古鎮(zhèn)大足石刻渣滓洞樵坪山仙女山萬盛石林四面山食宿費用60175130125190150165表15 游客在各景點可能住宿的時間（單位：小時）景點名稱淶灘古鎮(zhèn)大足石刻渣滓洞樵坪山仙女山萬盛石林四面山住宿時間09879108問題一：不考慮費用，為該游客設(shè)計一條出行路線，要求用最少的時間將全部景點游覽一遍。問題二：

4、不考慮時間，要求用最少的費用將全部景點游覽一遍。2、分析問題2.1問題一分析：問題一要求游覽完全部景點之后，所花的時間最少，而無需考慮費用問題。即是要求從淶灘古鎮(zhèn)出發(fā)，不重復(fù)地游覽各景點，最終回到起點，找出一條用時最短的路線，可以根據(jù)相關(guān)數(shù)據(jù)資料,在滿足約束的條件下建立模型，并用計算機進行求解。2.2問題二分析：問題二要求游覽完全部景點之后，所花費用最少，而無需考慮時間問題。即是要求從淶灘古鎮(zhèn)出發(fā)，不重復(fù)的游覽各景點，最終回到起點，找出一條費用最省的路線，解決方法與問題一類似。1 5 762 4 3 圖12 網(wǎng)絡(luò)圖頂點說明：1表示淶灘古鎮(zhèn)，2表示大足石刻，3表示渣滓洞，4表示樵坪山，5表示仙女

5、山，6表示萬盛石林，7表示四面山。2.3假設(shè)條件：（1）該名游客要求游覽完計劃的全部景點，并且所到之處均不重復(fù)。（2）天氣、交通狀況良好，無意外情況發(fā)生。（3）查詢相關(guān)資料得知，這幾處景點的門票總費用約為580元，但不論如何選擇旅游路線，所支付的門票總費用都一樣，所以此處暫不考慮門票費用。2.4符號說明：i,j：景點i或景點jT：此次旅游的所用總時間Ta：乘車所花的總時間Tb：在景點停留所花的總時間Tc：在景點住宿所花的總時間Ki：在景點i可能住宿的時間Tij：從景點i到景點j乘車的時間Ti：在景點i停留所花的時間Z：此次旅游的總費用Za：乘車總費用Zb：景點食宿費用Cij：從景點i到景點j的

6、乘車費用Ci：景點i的食宿費用Xij=1：從景點i前往景點jXij=0：不從景點i前往景點j3、建立模型3.1問題一：3.1.1目標(biāo)函數(shù)的確立：本問題的目標(biāo)是找到用時最短的旅游路線，而旅行時間由乘車時間、景點停留時間和景點住宿時間三部分組成，因此目標(biāo)函數(shù)為： （11）乘車總時間為： （12）景點停留總時間為： （13）景點住宿總時間為： （14）綜上，目標(biāo)函數(shù)為： （15）3.1.2約束條件的確立：景點數(shù)量約束： （16）變量約束： i，j=1,2, ,7 （17） i，j=1,2, ,7 （18）3.1.3模型的建立：根據(jù)以上分析，可建立如下模型：s.t. i，j=1,2, ,7 i，j=1

7、,2, ,73.2問題二：3.2.1目標(biāo)函數(shù)的確立：本問題的目標(biāo)是找到費用最省的旅游路線，而旅行費用由乘車費用、食住宿費用兩部分組成，因此目標(biāo)函數(shù)為： （21）乘車總費用為： （22）食宿總費用為： （23）綜上，目標(biāo)函數(shù)為： （24）3.2.2約束條件的確立：景點約束： （25）變量約束： i，j=1,2, ,7 （26） i，j=1,2, ,7 （27）3.2.3模型的建立：根據(jù)以上分析，可建立如下模型：s.t. i，j=1,2, ,7 4、計算機求解代碼4.1問題一：model:sets:place/1.7/:t,k,l;connect(place,place):x,tt;endsets

8、data:t=3.5 4.5 2.5 3 4 3 3.5;k=0 9 8 7 9 10 8;tt=032.544.53.53.53033.54332.5201.53.522.52.52.51.5032.534.54330443.5322.54033.532.53430;enddatamin=sum(place(j):sum(place(i):x(i,j)*(tt(i,j)+0.5*(t(i)+t(j)+0.5*(k(i)+k(j);for(place(i):x(i,i)=0);for(place(i)|i#ge#2:for(place(j)|j#ge#2:x(i,j)+x(j,i)1);for

9、(place(i):sum(place(j):x(i,j)=sum(place(j):x(j,i);for(place(i)|i#eq#1:sum(place(j):x(i,j)=1);for(place(i)|i#ne#1:sum(place(j):x(i,j)=l(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(place(i)|i#gt#1:l(i)1+(n-2)*x(i,1);end4.2問題二：model:sets:place/1.7/:c,l;connect(place,place):x,cc;endsetsdata:c=60 175 130

10、125 190 150 165;cc=0 504255115908650043551218968404603076536051562106546581151207265074110908953467405286686058110520;enddatamin=sum(place(j):sum(place(i):x(i,j)*(cc(i,j)+0.5*(c(i)+c(j);for(place(i):x(i,i)=0);for(place(i)|i#ge#2:for(place(j)|j#ge#2:x(i,j)+x(j,i)1);for(place(i):sum(place(j):x(i,j)=su

11、m(place(j):x(j,i);for(place(i)|i#eq#1:sum(place(j):x(i,j)=1);for(place(i)|i#ne#1:sum(place(j):x(i,j)=l(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);for(place(i)|i#gt#1:l(i)1+(n-2)*x(i,1);end5、計算機求解結(jié)果5.1問題一求解結(jié)果（重要部分）：Local optimal solution found. Objective value: 95.00000 Objective bound: 95.00000 Infeasib

12、ilities: 0.1276399E-05 Extended solver steps: 41Total solver iterations: 3362Variable ValueX( 1, 2) 1.000000X( 2, 7) 1.000000X( 3, 1) 1.000000X( 4, 6) 1.000000X( 5, 4) 1.000000X( 6, 3) 1.000000X( 7, 5) 1.0000005.1問題二求解結(jié)果（重要部分）：Local optimal solution found. Objective value: 1365.000 Objective bound:

13、1365.000 Infeasibilities: 0.2075714E-06 Extended solver steps: 0 Total solver iterations: 434Variable Value Reduced CostX( 1, 2) 1.000000 0.000000X( 2, 7) 1.000000 0.000000X( 3, 1) 1.000000 0.000000X( 4, 3) 1.000000 0.000000X( 5, 4) 1.000000 -5.000000X( 6, 5) 1.000000 0.000000X( 7, 6) 1.000000 -6.00

14、00006、解決方案6.1問題一：根據(jù)計算機求解結(jié)果，得出不考慮費用的情況下，用時最短的旅游路線：淶灘古鎮(zhèn)大足石刻四面山仙女山樵坪山萬盛石林渣滓洞淶灘古鎮(zhèn)此路線所花的時間為4天。6.2問題二：根據(jù)計算機求解結(jié)果，得出不考慮用時的情況下，費用最省的旅游路線：淶灘古鎮(zhèn)大足石刻四面山萬盛石林仙女山樵坪山渣滓洞淶灘古鎮(zhèn)此路線所花的費用為1365元（不含門票），若包含門票則為1945。7、啟發(fā)和啟示1.本文將游客是否由某一景點直接前往另一景點設(shè)置為0-1變量，以此來建立了模型。2.本文在限定條件下，成功運用lingo軟件解決了問題。3.本文中的問題只考慮了最小費用、最少時間兩種情況，還有很多可能出現(xiàn)的情況沒有考慮到。4.本文中的天氣、交通狀況等假設(shè)在實際操作中不一定完全符合，并且實際生活中的客觀條件會更加復(fù)雜，例如景點門票的價格可能會隨節(jié)假日而變動。5.本文的景點數(shù)據(jù)來源于網(wǎng)絡(luò)搜集，可能與實際情況有差距。8、問題的