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

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

2、各景點(diǎn)的乘車時(shí)間、費(fèi)用以及停留時(shí)間和住宿時(shí)間、費(fèi)用如下表所示：表11 各景點(diǎn)之間的乘車時(shí)間表（單位：小時(shí)）淶灘古鎮(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 各景點(diǎn)之間的乘車費(fèi)用表（單位：元）淶灘古鎮(zhèn)大足石刻渣滓洞樵坪山仙女山萬盛石林四面山淶灘古鎮(zhèn)05042551159086大足石刻50043551218968渣滓洞4046030765360樵坪山5156210654658仙

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

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

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

6、乘車費(fèi)用Ci：景點(diǎn)i的食宿費(fèi)用Xij=1：從景點(diǎn)i前往景點(diǎn)jXij=0：不從景點(diǎn)i前往景點(diǎn)j3、建立模型3.1問題一：3.1.1目標(biāo)函數(shù)的確立：本問題的目標(biāo)是找到用時(shí)最短的旅游路線，而旅行時(shí)間由乘車時(shí)間、景點(diǎn)停留時(shí)間和景點(diǎn)住宿時(shí)間三部分組成，因此目標(biāo)函數(shù)為： （11）乘車總時(shí)間為： （12）景點(diǎn)停留總時(shí)間為： （13）景點(diǎn)住宿總時(shí)間為： （14）綜上，目標(biāo)函數(shù)為： （15）3.1.2約束條件的確立：景點(diǎn)數(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)是找到費(fèi)用最省的旅游路線，而旅行費(fèi)用由乘車費(fèi)用、食住宿費(fèi)用兩部分組成，因此目標(biāo)函數(shù)為： （21）乘車總費(fèi)用為： （22）食宿總費(fèi)用為： （23）綜上，目標(biāo)函數(shù)為： （24）3.2.2約束條件的確立：景點(diǎn)約束： （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、計(jì)算機(jī)求解代碼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、計(jì)算機(jī)求解結(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ù)計(jì)算機(jī)求解結(jié)果，得出不考慮費(fèi)用的情況下，用時(shí)最短的旅游路線：淶灘古鎮(zhèn)大足石刻四面山仙女山樵坪山萬盛石林渣滓洞淶灘古鎮(zhèn)此路線所花的時(shí)間為4天。6.2問題二：根據(jù)計(jì)算機(jī)求解結(jié)果，得出不考慮用時(shí)的情況下，費(fèi)用最省的旅游路線：淶灘古鎮(zhèn)大足石刻四面山萬盛石林仙女山樵坪山渣滓洞淶灘古鎮(zhèn)此路線所花的費(fèi)用為1365元（不含門票），若包含門票則為1945。7、啟發(fā)和啟示1.本文將游客是否由某一景點(diǎn)直接前往另一景點(diǎn)設(shè)置為0-1變量，以此來建立了模型。2.本文在限定條件下，成功運(yùn)用lingo軟件解決了問題。3.本文中的問題只考慮了最小費(fèi)用、最少時(shí)間兩種情況，還有很多可能出現(xiàn)的情況沒有考慮到。4.本文中的天氣、交通狀況等假設(shè)在實(shí)際操作中不一定完全符合，并且實(shí)際生活中的客觀條件會(huì)更加復(fù)雜，例如景點(diǎn)門票的價(jià)格可能會(huì)隨節(jié)假日而變動(dòng)。5.本文的景點(diǎn)數(shù)據(jù)來源于網(wǎng)絡(luò)搜集，可能與實(shí)際情況有差距。8、問題的