淺談旅游線路的優(yōu)化設(shè)計(jì)

1、旅游線路的優(yōu)化設(shè)計(jì)摘要在基本假設(shè)和符號(hào)說(shuō)明的基礎(chǔ)上，建立了最優(yōu)線路rm與時(shí)間t、花費(fèi)s的函數(shù)f(s,t).對(duì)于第一問(wèn)本文以十一個(gè)城市的經(jīng)緯度坐標(biāo)算得城市之間的距離，構(gòu)造成完備圖,進(jìn)而用tsp算法,使用蟻群算法程序解得最優(yōu)路徑和最少費(fèi)用為3394元并設(shè)計(jì)出行程表.第二問(wèn)以完全城市之間距離的最短時(shí)間為權(quán)重，運(yùn)用01變量來(lái)控制住宿等不確定因素，使用lingo算法確定最優(yōu)路徑和最短時(shí)間為185小時(shí).第三問(wèn)和第四問(wèn)是建立在第一和第二問(wèn)的基礎(chǔ)上，添加約束條件s2000元t120小時(shí)，使用排除法得到最終結(jié)果：第三問(wèn)的最少費(fèi)用為1998元，游覽城市8個(gè)，第四問(wèn)的最短時(shí)間為107小時(shí)，游覽城市7個(gè)；第五小問(wèn)是第

2、三和第四小問(wèn)的有機(jī)整合，同時(shí)考慮時(shí)間和花費(fèi)的約束，聯(lián)系實(shí)際情況，得到最終結(jié)果為；最少費(fèi)用1848元，對(duì)應(yīng)的最短時(shí)間為103小時(shí)，游覽城市為5個(gè)。最后，給出模型的優(yōu)點(diǎn)和缺點(diǎn)的說(shuō)明。 關(guān)鍵字：完備圖 蟻群算法 01規(guī)劃 約束條件 一、問(wèn)題重述江蘇徐州有一位旅游愛(ài)好者打算現(xiàn)在的今年的五月一日早上8點(diǎn)之后出發(fā)，到全國(guó)一些著名景點(diǎn)旅游，最后回到徐州。由于跟團(tuán)旅游會(huì)受到若干限制，他(她)打算自己作為背包客出游。他預(yù)選了十個(gè)省市旅游景點(diǎn)，如表所示：現(xiàn)假設(shè)： 省市景點(diǎn)名稱在景點(diǎn)的最短停留時(shí)間江蘇常州市恐龍園4小時(shí)山東青島市嶗山風(fēng)景區(qū)6小時(shí)北京八達(dá)嶺長(zhǎng)城3小時(shí)山西祁縣喬家大院3小時(shí)河南洛陽(yáng)市龍門(mén)石窟3小時(shí)安徽黃

3、山市黃山7小時(shí)湖北武漢市黃鶴樓2小時(shí)陜西西安市秦始皇兵馬俑2小時(shí)江西九江市廬山7小時(shí)浙江舟山市普陀山6小時(shí)(a) 城際交通出行可以乘火車(含高鐵)、長(zhǎng)途汽車或飛機(jī)（不允許包車或包機(jī)），并且車票或機(jī)票可預(yù)訂到。(b) 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(c) 旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門(mén)票(第一門(mén)票)。晚上20：00至次日早晨7：00之間，如果在某地停留超過(guò)6小時(shí)，必須住宿，住宿費(fèi)用不超過(guò)200元/天。吃飯等其它費(fèi)用60元/天。(d) 假設(shè)景點(diǎn)的開(kāi)放時(shí)間為8:00至18:00。根據(jù)以上要求，針對(duì)如下的幾種情況，為該旅游愛(ài)好者設(shè)計(jì)詳細(xì)的行程表，該行

4、程表應(yīng)包括具體的交通信息(車次、航班號(hào)、起止時(shí)間、票價(jià)等)、賓館地點(diǎn)和名稱，門(mén)票費(fèi)用，在景點(diǎn)的停留時(shí)間等信息。(1) 如果時(shí)間不限，游客將十個(gè)景點(diǎn)全游覽完，至少需要多少旅游費(fèi)用？請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程表。(2) 如果旅游費(fèi)用不限，游客將十個(gè)景點(diǎn)全游覽完，至少需要多少時(shí)間？請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程表。(3) 如果這位游客準(zhǔn)備2000元旅游費(fèi)用，想盡可能多游覽景點(diǎn)，請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程表。(4) 如果這位游客只有5天的時(shí)間，想盡可能多游覽景點(diǎn)，請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程表。(5) 如果這位游客只有5天的時(shí)間和2000元的旅游費(fèi)用，想盡可能多游覽景點(diǎn)，請(qǐng)建立相關(guān)數(shù)

5、學(xué)模型并設(shè)計(jì)旅游行程表。二、問(wèn)題分析旅游最優(yōu)路線問(wèn)題已成為現(xiàn)今人們所感興趣的話題之一。本題通過(guò)給定相關(guān)資料和數(shù)據(jù)，要求為旅游愛(ài)好者設(shè)計(jì)最優(yōu)路線，建立具體優(yōu)化模型，最后求解最優(yōu)行程表。本題類似于旅行商問(wèn)題（tsp問(wèn)題），求解tsp問(wèn)題的關(guān)鍵在于設(shè)計(jì)合適的優(yōu)化算法【1】，主要包括分支定界法、改良回路法、貪婪算法、mst算法、插入法，蟻群算法、遺傳算法，在算法的選取上，應(yīng)該講求合適便捷的準(zhǔn)則。基于本題的實(shí)際情況，可以按以下的求解過(guò)程實(shí)現(xiàn)：首先，建立以十一個(gè)城市為頂點(diǎn)的完全圖。對(duì)于第一問(wèn)，題目要求遍歷所有城市使得話費(fèi)最小，為了解題方便，我們可以選取城市之間的距離作為相應(yīng)點(diǎn)與點(diǎn)之間的權(quán)重，最后通過(guò)合適的

6、算法求解最優(yōu)路線并設(shè)計(jì)出最優(yōu)行程表；對(duì)于第二問(wèn)，題目要求遍歷所有城市使得時(shí)間最小，通過(guò)改變第一問(wèn)的權(quán)重（把距離改成完成這段距離的最短時(shí)間）即可實(shí)現(xiàn)；然后，第三問(wèn)和第四問(wèn)分別是在第一問(wèn)和第二問(wèn)的基礎(chǔ)上，通過(guò)添加約束條件，即費(fèi)用和時(shí)間的約束，即可求得最優(yōu)線路，進(jìn)而設(shè)計(jì)最優(yōu)行程表；最后，第五問(wèn)是建立在第三和第四小問(wèn)基礎(chǔ)上的有機(jī)組合，實(shí)現(xiàn)的方法是：在第三問(wèn)所求得的結(jié)果的基礎(chǔ)上，把第四問(wèn)的約束條件添加進(jìn)去，最后解得最優(yōu)線路并設(shè)計(jì)最有行程表。三、模型假設(shè)1、不考慮班車和航班的推遲或取消，忽略天氣影響或不可預(yù)測(cè)的事故； 2、把經(jīng)緯度看成是平面坐標(biāo)的兩簇相互垂直的平行線； 3、旅館處于非滿客狀態(tài)，即總可預(yù)訂到

7、房間； 4、在時(shí)間的認(rèn)識(shí)上，把當(dāng)天早上八點(diǎn)到次日的早上八點(diǎn)定義為一天； 5、不考慮實(shí)際生活中出現(xiàn)的堵車等車等不可知現(xiàn)象。四、符號(hào)說(shuō)明城市i與城市j的圖上距離 旅游總費(fèi)用 第i個(gè)城市到第j個(gè)城市的交通費(fèi) 第i個(gè)城市到第j個(gè)城市是否需要通車 第個(gè)城市到第個(gè)城市的時(shí)間表示最優(yōu)線路五、模型建立根據(jù)以上假設(shè)，把最優(yōu)線路問(wèn)題看成是時(shí)間和花費(fèi)的函數(shù)，而時(shí)間和花費(fèi)又是相互聯(lián)系的，通過(guò)建立以下（01）變量，構(gòu)造模型的目標(biāo)函數(shù)、旅游費(fèi)用函數(shù) 。六、模型求解第一問(wèn)求解：根據(jù)以上模型，本小問(wèn)即是求解函數(shù)f使得s取得最小值（設(shè)為），轉(zhuǎn)化為tsp問(wèn)題，目標(biāo)函數(shù)就是： min根據(jù)相關(guān)資料得到各個(gè)城市的經(jīng)緯度，以經(jīng)度為橫坐標(biāo)

8、，緯度為縱坐標(biāo)，建立（經(jīng)度緯度）坐標(biāo)圖像（圖1）(見(jiàn)代碼1)：圖1再運(yùn)用歐拉距離公式： 算得任意兩點(diǎn)間的圖上距離（表1）（代碼2）：?jiǎn)挝唬篶m徐州常州青島北京祁縣洛陽(yáng)黃山武漢西安九江舟山徐州03.69643.61575.70825.77294.78034.17714.72658.25004.71336.6644常州3.696404.029688.84749.43878.05412.41585.781211.2 7614.49 072.97 24青島3.61574.296805.45898.10338.00816.27468.188011.52157.71106.4102北京5.70828.84

9、745.458904.85916.58859.87409.64279.398010.221811.5372祁縣5.77299.43878.10334.859102.66239.22854.57968.14 1812.4 024.78 03洛陽(yáng)8.05548.00816.58852.66233.662307.26844.57923.51646.115410.9358黃山4.7712.41586.27469.87409.22857.268403.844210.05502.22254.1658武漢4.72655.78128.18809.64277.12084.57923.844206.5416108

10、4718.0089西安8.250011.276111.52159.3.9804.57963.516410.05506.541608.371014.0254九江4.71334.49077.711010.22188.47186.11242.22251.84718.371006.3353舟山6.66442.97246.410211.537212.410210.93584.16588.008914.02546.33530 表1并使用floyd算法（見(jiàn)代碼3）算得任意兩點(diǎn)間的最短距離，構(gòu)造以下圖上最近距離矩陣為： 0 3.6964 3.6157 5.7082 5.7729 4.7803 4.1771 4

11、.7265 8.2500 4.7133 6.6644 3.6964 0 4.2968 8.8474 9.4387 8.0541 2.4158 5.7812 11.2761 4.4907 2.9724 3.6157 4.2968 0 5.4589 8.1033 8.0081 6.2746 8.1880 11.5215 7.7110 6.4102 5.7082 8.8474 5.4589 0 4.8591 6.5885 9.8740 9.6427 9.3980 10.2218 11.5372 5.7729 9.4387 8.1033 4.8591 0 2.6623 9.2285 1208 4.57

12、96 8.4718 12.4102 4.7803 8.0541 8.0081 6.5885 2.6623 0 7.2684 4.5792 3.5164 6.1124 10.9358 4.1771 2.4158 6.2746 9.8740 9.2285 7.2684 0 3.8442 10.0550 2.2225 4.1658 4.7265 5.7812 8.1880 9.6427 7.1208 4.5792 3.8442 0 6.5416 1.8471 8.0089 8.2500 11.2761 11.5215 9.3980 4.5796 3.5164 10.0550 6.5416 0 8.3

13、710 14.0254 4.7133 4.4907 7.7110 10.2218 8.4718 6.1124 2.2225 1.8471 8.3710 0 6.3353 6.6644 2.9724 6.4102 11.5372 12.4102 10.9358 4.1658 8.0089 14.0254 6.3353 0 并對(duì)各個(gè)城市進(jìn)行編號(hào)如下（表2）： 城市徐州常州青島北京祁縣洛陽(yáng)黃山武漢西安九江舟山編號(hào)1234567891011 表2根據(jù)以上圖上最近距離矩陣，設(shè)計(jì)蟻群算法（見(jiàn)代碼4），得到最優(yōu)路線為（如圖2所示）：到最優(yōu)路線為： rm=6 9 5 4 3 1 2 11 7 10 8 即：洛

14、陽(yáng)西安祁縣北京青島徐州常州舟山黃山九江武漢 圖2根據(jù)各個(gè)城市之間的實(shí)際距離（表3）: 單位: km徐州常州青島北京祁縣洛陽(yáng)黃山武漢西安九江舟山徐州0401.9388.2634.36620.33507.3462.82518.9877.61523.41707.31常州401.90476.71977.941019.41862.64266.66620.721205.61486.39305.56青島388.2476.710594.65857.51849.77695.18890.721224.43846.73701.16北京634.36977394594.650857.51849.771096.31069

15、.851008.151136.461257.97祁縣620.331019.41857.51514.360715.71006.78791.23497.51935.471324.68洛陽(yáng)507.3826.64849.77715.7297.110784.59506.59375.22670.21156.69黃山462.82266.66695.181096.31006.78784.590470.991078.11235.64430.58武漢518.9620.72890.721069.85791.23506.59407.990709.48198.47838.37西安877.611205.611224.43

16、1008.15497.51375.221078.11709.480905.661484.54九江523.41486.39846.731136.46935.47670.2235.64198.47905.660660.46舟山707.31305.56701.161257.971324.681156.69430.58838.371484.54660.460 表3得到最優(yōu)線路的總路程為： min=4448.680km根據(jù)以上最優(yōu)路線，并通過(guò)查閱大量相關(guān)資料，得到以下行程表：日期時(shí)間行程價(jià)格（元）5月1日7；5012：36乘坐列車t114（徐州常州）7012：4013：40乘坐公交29路到常州恐龍園11

17、3：4018：00游玩常州恐龍園19018：0020：00游玩常州020：007：00住宿于常州藍(lán)色快舟營(yíng)銷認(rèn)連鎖店1205月2日7：0010：51游玩常州010：5115：08乘坐列車d5431（常州寧波東）7315：0817：38乘坐728w公交到白峰碼頭乘坐船到普陀區(qū)1617：3920：00游玩普陀區(qū)020：007：00住宿于普陀山金沙小院905月3日7：008：00乘坐公交到普陀山風(fēng)景區(qū)48：0014：00游玩普陀山風(fēng)景區(qū)20014：0015：41返回寧波東站1615：4122：16乘坐列車k8500（寧波東宣城）6322：1601：33候車05月4日01：3305：07乘坐列車k16

18、1（宣城黃山）2905：077：00休息07：008：00乘坐公交到黃山風(fēng)景區(qū)158：0015：00游玩黃山23015：0016：00乘公交返回黃山站1516：0018：28游玩黃山市018：2823：29乘坐列車k70（黃山鷹潭）5123：2900：22候車05月5日00：2203：47乘坐列車k253（鷹潭九江）4206：477：00休息07：008：00乘坐公交到廬山風(fēng)景區(qū)28：0015：00游玩廬山風(fēng)景區(qū)18015：0016：00乘公交返回九江站716：0020：24游玩九江市020：2422：22乘列車k752（九江南昌）2222：2200：22候車05月6日01：426：28乘坐列

19、車1586（南昌武昌）466：287：30休息07：308：00乘坐432w公交到黃鶴樓28：0010：00游玩黃鶴樓8010：0010：30乘坐43w公交返回武昌站210：3020：40游玩武昌市020：4006：27乘坐列車k896（武昌洛陽(yáng)）925月7日6：277：30休息07：308：30乘坐81w公交到龍門(mén)石窟28：3011：30游玩龍門(mén)石窟12011：3012：30乘坐43w返回洛陽(yáng)站212：3015：00游玩洛陽(yáng)市015：0019：54乘坐列車k388(洛陽(yáng)西安)5519：5421：00乘坐306w公交車到秦始皇兵馬俑221：008：00住宿于西安美寶賓館后辛門(mén)點(diǎn)1385月8日8

20、：0010：00游玩秦始皇兵馬俑15010：0011：00乘坐306w公交車返回西安站211：0020：46游玩西安020：4606：19乘坐列車2670（西安祁縣）395月9日06：1907：30休息007：3008：30乘坐公交到喬家大院208：3012：30游玩喬家大院4012：3013：29乘坐公交返回祁縣站213：2904：00乘坐列車2604（祁縣北京）945月10日04：0007：00休息007:00-8:00乘坐地鐵2號(hào)線和919公交車到八達(dá)嶺長(zhǎng)城148:0011：00游玩八達(dá)嶺長(zhǎng)城4511：0012：00乘坐地鐵2號(hào)線和919公交車返回北京站1412;0019：28游玩北京0

21、19：2826：08乘坐列車t215(北京德州)5423：0800：45候車05月11日00：455：59乘坐列車2244（德州藍(lán)村）575：5907：00休息007：0008：00乘坐公交到嶗山風(fēng)景區(qū)2008：0014：00游玩嶗山風(fēng)景區(qū)13014：0014：15乘坐311w公交車到青島站714：1515：22游玩青島市015:2201:25乘坐列車1112（青島徐州087吃飯等其他費(fèi)用660總旅游費(fèi)用3394總時(shí)間（單位：小時(shí)）257.58第二問(wèn)求解：類似的，本小問(wèn)即是求解函數(shù)使得t取得最小值（設(shè)為），根據(jù)問(wèn)題分析，只需把第一問(wèn)完全圖的權(quán)重改為時(shí)間，目標(biāo)函數(shù)即是： min確定城市之間到達(dá)的

22、最短時(shí)間矩陣:通過(guò)網(wǎng)上的相關(guān)資料，我們得到各個(gè)城市之間到達(dá)的最短時(shí)間矩陣為：0 322 320 70 660 280 602 562 521 528 724 322 0 944 85 1140 735 583 250 110 840 272 320 944 0 75 100 914 1395 115 110 1015 90 70 85 75 0 75 105 120 110 105 135 130 660 1140 100 75 0 701 994 80 65 731 960 280 735 914 105 701 0 1750 423 270 696 1320 602 583 1395 12

23、0 994 1750 0 467 1300 484 490 562 250 115 110 80 423 467 0 70 215 75 521 110 110 105 65 270 1300 70 0 967 170 528 840 1015 135 731 696 484 215 967 0 828 724 272 90 130 960 1320 490 75 170 828 0 求解最優(yōu)遍歷路線:由于每個(gè)城市去且僅去一次，最終肯定是形成一個(gè)圈的結(jié)構(gòu)，這就導(dǎo)致了這十一個(gè)城市其中有的兩個(gè)城市是直接相連的，另外也有兩個(gè)城市是不連接的。這就可以考慮設(shè)0-1變量，如果兩個(gè)城市緊接著去旅游的則為1，

24、否則為0。因?yàn)槊總€(gè)城市只去一次，所以其中任何一個(gè)城市的必有且僅有一條進(jìn)入路線和一條出的路線。我們引入0-1變量，若通過(guò)兩城市之間的路徑，則賦值為1；若不通過(guò)兩城市之間的路徑，則賦值為0。對(duì)于無(wú)向圖的最短時(shí)間路徑問(wèn)題，可以這樣理解，從點(diǎn)到點(diǎn)和點(diǎn)到點(diǎn)的邊，看成有向弧，其他各條邊均看成有不同方向的雙弧。使用lingo設(shè)計(jì)算法（代碼5），得到最優(yōu)解為（截取有通路部分）： variable value reduced cost x12 1.000000 322.0000 x16 1.000000 280.0000 x29 1.000000 110.0000 x35 1.000000 100.0000 x

25、311 1.000000 90.00000 x46 1.000000 105.0000 x47 1.000000 120.0000 x59 1.000000 65.00000 x710 1.000000 484.0000 x810 1.000000 215.0000 x811 1.000000 75.00000 即最優(yōu)路線是: 11 8 10 7 4 6 1 2 9 5 3 即（圖3）：舟山武漢九江黃山北京洛陽(yáng)徐州常州西安祁縣青島得 min=1966min 圖 3計(jì)時(shí)間最短的行程表:根據(jù)以上線路，結(jié)合實(shí)際情況，設(shè)計(jì)出以下線路表，時(shí)間最短為：184小時(shí)日期時(shí)間行程價(jià)格（元）5月1日07：3512

26、：26乘坐列車t54（徐州常州）7012：2613：30乘坐出租車到常州恐龍公園4013：3017：30游玩常州恐龍公園19017：3018：60乘坐出租車到常州奔牛機(jī)場(chǎng)4018：3021：10休息021：1023：00乘坐飛機(jī)mu5638(常州西安)62323：0024：00乘坐出租車到秦始皇兵馬俑405月2日00:008：00住宿于西安美寶賓館后辛門(mén)店1388；0010：00游玩秦始皇兵馬俑15010：0011：00乘坐出租車西安咸陽(yáng)飛機(jī)場(chǎng)4011：0011：35游玩西安市011：3512：50乘坐飛機(jī)gs4612（西安太原）41312：5014：00乘坐公交車到喬家大院4014：0017

27、：00游玩喬家大院4017：0018：00乘坐出租車到西安咸陽(yáng)飛機(jī)場(chǎng)4018：0018：35游玩太原018：3519：55乘坐飛機(jī)sc4612（太原青島）63119：5521：00乘坐出租車到嶗山風(fēng)景取4021：008：00住宿于青島新天橋賓館885月3日8：0014:00游玩嶗山風(fēng)景區(qū)13014:0015:00乘公交車返回青島流亭機(jī)場(chǎng)4015：0017：30游玩青島017：3018：55乘坐飛機(jī)hu7842（青島寧波）74318：5520：00乘坐出租車到普陀山風(fēng)景區(qū)4020：0008：00住宿于舟山華融大酒店1585月4日8：0014：00游玩普陀山風(fēng)景區(qū)20014：0015：00乘坐出租

28、車返回寧波櫟社飛機(jī)場(chǎng)4015：0020：40游玩寧波市020：4022：00乘坐飛機(jī)mu2532（寧波武漢）53622：0023：00乘坐出租車到黃鶴樓4023：0008：00住宿于武漢鄂鋼大酒店895月5日08：0010：00游玩黃鶴樓8010：0011：00乘坐出租車到武漢天河國(guó)際場(chǎng)4011：0013：08游玩武漢市013：0814：52乘坐列車d3241（武漢廬山）11814：5216：00乘坐出租車到廬山風(fēng)景區(qū)18016：0020：00游玩九江市4020：0008：00住宿于九江悠然快捷酒店425月6日08：0015：00游玩廬山風(fēng)景區(qū)18015：0016：15乘出租車到九江4016：

29、1520：04乘坐列車k1187（九江鷹潭）4220：0422：29候車022：2903：47乘坐列車（鷹潭黃山）515月7日03：4707：00休息007：0008：00承租出租車到黃山風(fēng)景區(qū)4008：0015：00游玩黃山23015：0016：00乘出租車到黃山機(jī)場(chǎng)4016：0021：35游玩黃山市021：3523：35乘坐飛機(jī)ca1552（黃山北京）86523：3507;00住宿于北京佳號(hào)賓館1685月8日07:0008：00乘坐出租車到八達(dá)嶺長(zhǎng)城4008：0011：00游玩八達(dá)嶺長(zhǎng)城4511：0012：00乘坐出租車返回北京首都機(jī)場(chǎng)012：0012：55游玩北京012：5514：40乘

30、坐飛機(jī)mu5695（北京洛陽(yáng)075614：4015：00乘坐出租車到龍門(mén)石窟4015：0018：00游玩龍門(mén)石窟12018：0018：32乘坐出租車返回洛陽(yáng)站4018：3201：02乘坐列車k1132（洛陽(yáng)徐州）70吃飯等其他費(fèi)用480總旅游費(fèi)8272總時(shí)間（單位：小時(shí)）185第三問(wèn)求解：在第一問(wèn)的求解結(jié)果的基礎(chǔ)上，我們添加以下約束，旅游總經(jīng)費(fèi)：并且把旅游景點(diǎn)的個(gè)數(shù)調(diào)整為動(dòng)態(tài)的。首先，確定第一小問(wèn)各個(gè)景點(diǎn)的總花費(fèi)（如表4）和城際交通費(fèi)用（如表5），列出下表：城市1234567891011花費(fèi)（元）0311214734414428984292253326 表4城市1-22-1111-77-101

31、0-88-66-99-55-44-33-1花費(fèi)（元）7073635146925539945487 表5根據(jù)第一小問(wèn)的總費(fèi)用為3394，運(yùn)用排除法，基本步驟是： 1、把最大花費(fèi)的城市剔除，刪去相關(guān)車費(fèi)，并添加與該城市相連的兩點(diǎn)間的車費(fèi)； 2、確定路線設(shè)計(jì)最優(yōu)行程表，把所得最少經(jīng)費(fèi)與2000對(duì)比； 重復(fù)以上步驟直至最少經(jīng)費(fèi)大于2000跳出。 根據(jù)相關(guān)數(shù)據(jù)，我們得到最優(yōu)路線（如圖4）是： 圖4=6 9 5 4 3 1 7 10 8 即：洛陽(yáng)西安祁縣北京青島徐州黃山九江武漢具體行程表如下：日期時(shí)間行程價(jià)格（元）5月1日21：3807：08乘坐列車k614（徐州九江）875月2日7：088：00乘坐公交

32、到廬山風(fēng)景區(qū)28：0015：00游玩廬山風(fēng)景區(qū)18015：0016：00乘坐公交返回九江站216：0020：24游玩九江市020：2422：22乘坐列車k752（九江南昌）2222：2201：42候車001：426：28乘坐列車1586（南昌武昌）466：287：30休息05月3日7：308：00乘坐43w公交到黃鶴樓28：0010：00游玩黃鶴樓8010：0010：30乘坐43w公交返回武昌站210：3020：40游玩武昌市020：4006：27乘坐列車k896（武昌洛陽(yáng)）926：277：30休息05月4日7：308：30乘坐81w公交到龍門(mén)石窟28：3011：30游玩龍門(mén)石窟12011：3

33、012：30乘坐43w返回洛陽(yáng)站212：3017：15游玩洛陽(yáng)市017：1522：47乘坐列車k388（洛陽(yáng)西安）3222：4700：00乘坐306w公交車到秦始皇兵馬俑200：008：00住宿于西安美寶賓館后辛門(mén)店1385月5日8：0010：00游玩秦始皇兵馬俑15010：0011：00乘坐306w公交返回西安站211：0020：46游玩西安020：4606：19乘坐列車2670（西安祁縣）3906：1907：30休息007：3008：30乘坐公交到喬家大院208：3012：30游玩喬家大院405月6日12：3013：29乘公交返回祁縣站213：2904：00乘坐列車2604（祁縣北京094

34、04：0007：00休息007：0008:00乘坐地鐵2號(hào)線和919公交到八達(dá)嶺長(zhǎng)城1408:0011:00游玩八達(dá)嶺4511：0012：00乘坐地鐵2號(hào)線和919公交返回北京站145月7日12：0019：28游玩北京019：2823：08乘坐列車t215（北京德州）5423：0800：45候車000：455：59乘坐列車2244（德州藍(lán)村）575：5907：00休息007：0008：30乘坐公交到嶗山2008：3014：00游玩嶗山13014：0014：15乘坐311w公交車到青島站714：1515：22游玩青島0015：2201：25乘坐列車1112（青島徐州）87吃飯等其他費(fèi)用420總費(fèi)

35、用1988總時(shí)間（單位：分鐘）10307由于第一天都在徐州，直到21：38才出發(fā)，故第一天的其他費(fèi)用不計(jì)，求得最后最少費(fèi)用為1998元。第四問(wèn)求解：同樣類似于第三問(wèn)，基于第二問(wèn)的求解結(jié)果，添加時(shí)間上的約束（7200分鐘）, 并且把旅游景點(diǎn)的個(gè)數(shù)調(diào)整為動(dòng)態(tài)的。首先，確定第一小問(wèn)各個(gè)景點(diǎn)的總花費(fèi)時(shí)間（如表6）和城際交通時(shí)間（如表7），列出下表： 城市1234567891011時(shí)間(min)052412957603452281072788147518231545表6城市1-22-99-55-33-1111-88-1010-77-44-66-1時(shí)間（min）2911106580858010231812

36、0105280 表7先把停留時(shí)間最長(zhǎng)的四個(gè)城市剔除，即西安、九江、舟山、青島，將剩下的城市計(jì)算得到最短花費(fèi)時(shí)間為4593min（不包括到達(dá)中斷城市的車程），遠(yuǎn)遠(yuǎn)小與7200min。把四個(gè)城市分別添加進(jìn)去，通過(guò)計(jì)算，發(fā)現(xiàn)添加青島進(jìn)去時(shí)，結(jié)果較好?？紤]到祁縣的交通問(wèn)題，把西安添加進(jìn)去，再計(jì)算總時(shí)間，結(jié)果不符合要求，最后，把黃山剔除，得到的結(jié)果符合要求。即得到最優(yōu)路線：8 4 6 1 2 9 5 3 即：武漢北京洛陽(yáng)徐州常州西安祁縣青島具體行程表如下：日期時(shí)間行程價(jià)格（元）5月1日07：3512：26乘坐列車t54（徐州常州）7012;2613:30乘坐出租車到常州恐龍園4013：3017：30游玩

37、常州恐龍園19017：3018：30乘坐出租車到常州奔牛機(jī)場(chǎng)4018：3021：10休息021：1023：00乘坐飛機(jī)mu5638（常州西安）62323：0024：00車出租車到秦始皇兵馬俑0405月2日00：0008：00住宿于西安美寶賓館后辛門(mén)店13808：0010：00游玩秦始皇兵馬俑15010：0011：00乘坐出租到西安咸陽(yáng)飛機(jī)場(chǎng)4011：0011：35游玩西安市011：3512：50乘飛機(jī)gs7582（西安太原）41312：5014：00乘坐公交到喬家大院4014：0017：00游玩喬家大院4017：0018：00乘坐出租車返回安咸陽(yáng)機(jī)場(chǎng)4018：0018：35游玩太原018：35

38、19：55乘坐飛機(jī)sc4612（太原青島）63119：5521：00乘出租車到嶗山4021：008：00住宿于青島親天橋賓館885月3日8：0014：00游玩嶗山13014：0015：00乘公交返回青島流亭機(jī)場(chǎng)4015：0020：00游玩青島020：0021：55乘飛機(jī)hu9960（青島武漢0144521：5523：00乘出租車到黃鶴樓4023：0008：00住宿于武漢鄂鋼大酒店895月4日08：0010：00游玩黃鶴樓8010：0010：40乘出租車到武漢天河國(guó)際機(jī)場(chǎng)4010：4012：35乘坐飛機(jī)ca1334（武漢北京）94112：3513;35乘出租到八達(dá)嶺長(zhǎng)城4013:3516:35游

39、玩八達(dá)嶺長(zhǎng)城4516:3517：35乘出租返回北京首都機(jī)場(chǎng)4017：3519：20游玩北京019：2021：05乘坐飛機(jī)mu（北京洛陽(yáng)074821：0522：00乘坐出租到洛陽(yáng)東山賓館4022：0007：00住宿于東山賓館5585月5日07：0008;00乘出租到龍門(mén)石窟4008:0011:00游玩龍門(mén)石窟12011:0012:07乘出租到洛陽(yáng)站4012:0718:23乘坐列車k1352（洛陽(yáng)徐州）70吃飯等其他費(fèi)用300總費(fèi)用7469總時(shí)間（單位：分鐘）6408第五問(wèn)求解：考慮到此題是在時(shí)間和花費(fèi)上雙重約束，根據(jù)第三小問(wèn)和第四小問(wèn)所得到的各個(gè)城市和各條路線的停留時(shí)間和花費(fèi)，首先，剔除停留時(shí)間

40、最長(zhǎng)的四個(gè)和花費(fèi)最多的四個(gè)，由于重復(fù)，最后剩下北京、祁縣、洛陽(yáng)、武漢四個(gè)城市，通過(guò)計(jì)算，得知明顯還有時(shí)間和費(fèi)用，把青島添加進(jìn)去，并結(jié)合實(shí)際情況，得到最后結(jié)果為： =1 6 8 5 4 3 即：徐州洛陽(yáng)武漢祁縣北京青島設(shè)計(jì)出以下線路表：日期時(shí)間行程價(jià)格（元）5月1日23：0005：26乘坐列車k560(徐州洛陽(yáng))705月2日05：2607：00休息007：0008：00乘坐81w公交到龍門(mén)石窟208：0011：00游玩龍門(mén)石窟12011：0012：07乘坐81w公交返回洛陽(yáng)站212：0714：10乘坐列車d1003（洛陽(yáng)西安）19014：1015：10乘坐81w公交車到達(dá)秦始皇兵馬俑115：10

41、17：10游玩秦始皇兵馬俑15017：1018：10乘坐81w公交返回西安站118：1020：46游玩西安市020：4606：19乘坐列車2670（西安祁縣0395月3日06：1907：00休息007：0008：00乘坐公交車到喬家大院108：0011;00游玩喬家大院4011:0012:00乘公交返回祁縣站112:0013；29乘坐列車2604（祁縣北京）013：2904：00游玩祁縣945月4日04：0007：00休息007：0008;00乘坐地鐵2號(hào)線和919公交到八達(dá)嶺長(zhǎng)城1408；0011：00游玩八達(dá)嶺長(zhǎng)城4511：0012：00乘坐地鐵2號(hào)線和919公交返回北京西站14123：0

42、022：22游玩北京市022：2210：08乘坐列車k712（北京青島）1135月5日10：0811;00乘坐311w公交車到嶗山風(fēng)景區(qū)711:0017：00游玩嶗山風(fēng)景區(qū)13017：0018：00乘坐311w公交返回青島站718：0019：28游玩青島019：2804：52乘坐列車k70（青島徐州099吃飯等其它費(fèi)用300總費(fèi)用1848總時(shí)間（單位：分鐘06142七、模型評(píng)價(jià)優(yōu)點(diǎn) ：1、把最優(yōu)解問(wèn)題看成是時(shí)間與花費(fèi)的函數(shù)，通過(guò)添加不同的約束條件來(lái)求解不同的問(wèn)題，在一定的程度上，簡(jiǎn)化了問(wèn)題的解答過(guò)程； 2、用tsp問(wèn)題的解答方法來(lái)確定最優(yōu)路線，最后再根據(jù)實(shí)際設(shè)計(jì)行程表； 3、引入01變量，把最

43、短路徑問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題，直接用lingo軟件即可求解； 4、可以推廣到網(wǎng)絡(luò)優(yōu)化等問(wèn)題，容易解決實(shí)際問(wèn)題； 缺點(diǎn) ：1、求解過(guò)程中出現(xiàn)深夜處于休息狀態(tài)而不是到旅館住宿，不符合實(shí)際情況，缺乏合理性； 2、在求解第五小問(wèn)時(shí)沒(méi)有采用更精確的方法進(jìn)行預(yù)測(cè)，得到的只是較優(yōu)線路； 3、由于時(shí)間和數(shù)據(jù)有限和網(wǎng)絡(luò)數(shù)據(jù)的不確定性，不具備足夠的說(shuō)服力；八附錄：代碼1x=117.2 119.95 120.33 116.46 112.33 112.44 118.14 114.31 108.95 115.97 122.3;y=34.26 31.79 36.07 39.92 37.36 34.7 30.19 30.5

44、2 34.27 29.71 29.97;plot(x,y,'+')grid onxlabel('經(jīng)度');ylabel('緯度');title('經(jīng)度緯度圖象')代碼2：%floyd算法通用程序，輸入a為賦權(quán)鄰接矩陣 %由經(jīng)緯度算得兩兩面之間距離矩陣 d, c=117.2 34.26 119.95 31.79 120.33 36.07 116.46 39.92 112.33 37.36 112.44 34.7 118.14 30.19 114.31 30.52 108.95 34.27 115.97 29.71 122.3 29.

45、97; % c 11個(gè)城市的坐標(biāo)(經(jīng)緯度)，11×2的矩陣 c,d=size(c); d=zeros(c,c); for i=1:c for j=i:c bb=(c(i,1)-c(j,1).2+(c(i,2)-c(j,2).2; d(i,j)=bb(0.5); d(j,i)=d(i,j); end end d 由經(jīng)緯度算得兩兩之間距離矩陣d為: d= 0 3.6964 3.6157 5.7082 5.7729 4.7803 4.1771 4.7265 8.2500 4.7133 6.6644; 3.6964 0 4.2968 8.8474 9.4387 8.0541 2.4158 5.7812 11.2761 4.4907 2.9724; 3.6157 4.2968 0 5.4589 8.1033 8.0081 6.2746 8.1880 11.5215 7.7110 6.4102; 5.7082 8.8474 5.4589 0 4.8591 6.5885 9.8740 9.6427 9.3980 10.2218 11.5372; 5.7729 9.4387 8.1033 4.8591