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

1、52/52HYPERLINK /旅游線路的優(yōu)化設(shè)計摘要在差不多假設(shè)和符號講明的基礎(chǔ)上，建立了最優(yōu)線路Rm與時刻T、花費S的函數(shù)F(S,T).關(guān)于第一問本文以十一個都市的經(jīng)緯度坐標(biāo)算得都市之間的距離，構(gòu)造成完備圖,進(jìn)而用TSP算法,使用蟻群算法程序解得最優(yōu)路徑和最少費用為3394元并設(shè)計出行程表.第二問以完全都市之間距離的最短時刻為權(quán)重，運用01變量來操縱住宿等不確定因素，使用lingo算法確定最優(yōu)路徑和最短時刻為185小時.第三問和第四問是建立在第一和第二問的基礎(chǔ)上，添加約束條件S2000元T120小時，使用排除法得到最終結(jié)果：第三問的最少費用為1998元，巡游都市8個，第四問的最短時刻為10

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

3、小時河南洛陽市龍門石窟3小時安徽黃山市黃山7小時湖北武漢市黃鶴樓2小時陜西西安市秦始皇兵馬俑2小時江西九江市廬山7小時浙江舟山市普陀山6小時(A) 城際交通出行能夠乘火車(含高鐵)、長途汽車或飛機(jī)（不同意包車或包機(jī)），同時車票或機(jī)票可預(yù)訂到。(B) 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(C) 旅游費用以網(wǎng)上公布為準(zhǔn)，具體包括交通費、住宿費、景點門票(第一門票)。晚上20：00至次日早晨7：00之間，假如在某地停留超過6小時，必須住宿，住宿費用不超過200元/天。吃飯等其它費用60元/天。(D) 假設(shè)景點的開放時刻為8:00至18:00。依照以上要求，針對如下的幾種情況，為

4、該旅游愛好者設(shè)計詳細(xì)的行程表，該行程表應(yīng)包括具體的交通信息(車次、航班號、起止時刻、票價等)、賓館地點和名稱，門票費用，在景點的停留時刻等信息。(1) 假如時刻不限，游客將十個景點全巡游完，至少需要多少旅游費用？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(2) 假如旅游費用不限，游客將十個景點全巡游完，至少需要多少時刻？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(3) 假如這位游客預(yù)備2000元旅游費用，想盡可能多巡游景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(4) 假如這位游客只有5天的時刻，想盡可能多巡游景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(5) 假如這位游客只有5天的時刻和2000元的旅游費用

5、，想盡可能多巡游景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。二、問題分析旅游最優(yōu)路線問題已成為現(xiàn)今人們所感興趣的話題之一。本題通過給定相關(guān)資料和數(shù)據(jù)，要求為旅游愛好者設(shè)計最優(yōu)路線，建立具體優(yōu)化模型，最后求解最優(yōu)行程表。本題類似于旅行商問題（TSP問題），求解TSP問題的關(guān)鍵在于設(shè)計合適的優(yōu)化算法【1】，要緊包括分支定界法、改良回路法、貪欲算法、MST算法、插入法，蟻群算法、遺傳算法，在算法的選取上，應(yīng)該講求合適便捷的準(zhǔn)則?；诒绢}的實際情況，能夠按以下的求解過程實現(xiàn)：首先，建立以十一個都市為頂點的完全圖。關(guān)于第一問，題目要求遍歷所有都市使得話費最小，為了解題方便，我們能夠選取都市之間的距離作為相

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

7、 3、旅館處于非滿客狀態(tài)，即總可預(yù)訂到房間； 4、在時刻的認(rèn)識上，把當(dāng)天早上八點到次日的早上八點定義為一天； 5、不考慮實際生活中出現(xiàn)的堵車等車等不可知現(xiàn)象。四、符號講明都市i與都市j的圖上距離 旅游總費用 第i個都市到第j個都市的交通費 第i個都市到第j個都市是否需要通車 第個都市到第個都市的時刻表示最優(yōu)線路五、模型建立依照以上假設(shè)，把最優(yōu)線路問題看成是時刻和花費的函數(shù)，而時刻和花費又是相互聯(lián)系的，通過建立以下（01）變量，構(gòu)造模型的目標(biāo)函數(shù)、旅游費用函數(shù) 。六、模型求解第一問求解：依照以上模型，本小問即是求解函數(shù)F使得S取得最小值（設(shè)為），轉(zhuǎn)化為TSP問題，目標(biāo)函數(shù)確實是： min依照相關(guān)

8、資料得到各個都市的經(jīng)緯度，以經(jīng)度為橫坐標(biāo)，緯度為縱坐標(biāo)，建立（經(jīng)度緯度）坐標(biāo)圖像（圖1）(見代碼1)：圖1再運用歐拉距離公式： 算得任意兩點間的圖上距離（表1）（代碼2）：單位：CM徐州常州青島北京祁縣洛陽黃山武漢西安九江舟山徐州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.71

9、106.4102北京5.70828.84745.458904.85916.58859.87409.64279.398010.221811.5372祁縣5.77299.43878.10334.859102.66239.22854.57968.14 1812.4 024.78 03洛陽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.

10、57923.844206.54161084718.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算法（見代碼3）算得任意兩點間的最短距離，構(gòu)造以下圖上最近距離矩陣為： 0 3.6964 3.6157 5.7082 5.

11、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 0 2.6

12、623 9.2285 1208 4.5796 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

13、10.0550 6.5416 0 8.3710 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 并對各個都市進(jìn)行編號如下（表2）： 都市徐州常州青島北京祁縣洛陽黃山武漢西安九江舟山編號1234567891011 表2依照以上圖上最近距離矩陣，設(shè)計蟻群算法（見代碼4），得到最優(yōu)路線為（如圖2所示）：到最優(yōu)路線為： Rm=6 9 5 4

14、 3 1 2 11 7 10 8 即：洛陽西安祁縣北京青島徐州常州舟山黃山九江武漢 圖2依照各個都市之間的實際距離（表3）: 單位: km徐州常州青島北京祁縣洛陽黃山武漢西安九江舟山徐州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.65085

15、7.51849.771096.31069.851008.151136.461257.97祁縣620.331019.41857.51514.360715.71006.78791.23497.51935.471324.68洛陽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西安

16、877.611205.611224.431008.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依照以上最優(yōu)路線，并通過查閱大量相關(guān)資料，得到以下行程表：日期時刻行程價格（元）5月1日7；5012：36乘坐列車T114（徐州常州）7012：40

17、13：40乘坐公交29路到常州恐龍園113：4018：00游玩常州恐龍園19018：0020：00游玩常州020：007：00住宿于常州藍(lán)色快舟營銷認(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

18、月4日01：3305：07乘坐列車K161（宣城黃山）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：2

19、2候車05月6日01：426：28乘坐列車1586（南昌武昌）466：287：30休息07：308：00乘坐432W公交到黃鶴樓28：0010：00游玩黃鶴樓8010：0010：30乘坐43W公交返回武昌站210：3020：40游玩武昌市020：4006：27乘坐列車K896（武昌洛陽）925月7日6：277：30休息07：308：30乘坐81W公交到龍門石窟28：3011：30游玩龍門石窟12011：3012：30乘坐43W返回洛陽站212：3015：00游玩洛陽市015：0019：54乘坐列車K388(洛陽西安)5519：5421：00乘坐306W公交車到秦始皇兵馬俑221：008：00住

20、宿于西安美寶賓館后辛門點1385月8日8：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號線和919公交車到八達(dá)嶺長城148:0011：00游玩八達(dá)嶺長城4511：0012：00乘坐地鐵2號線和919公交車返回

21、北京站1412;0019：28游玩北京019：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吃飯等其他費用660總旅游費用3394總時刻（單位：小時）257.58第二問求解：類似的，本小問即是求解函數(shù)使得T取得最小值（設(shè)為），依照問題分析，只需把第一問完全圖的權(quán)重改為時刻，

22、目標(biāo)函數(shù)即是： min確定都市之間到達(dá)的最短時刻矩陣:通過網(wǎng)上的相關(guān)資料，我們得到各個都市之間到達(dá)的最短時刻矩陣為：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

23、1320 602 583 1395 120 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)遍歷路線:由于每個都市去且僅去一次，最終確信是形成一個圈的結(jié)構(gòu)，這就導(dǎo)致了這十一個都市其中有的兩個都市是直接相連的，另外也有兩個都市是不連接的。這就能夠考慮設(shè)0-1

24、變量，假如兩個都市緊接著去旅游的則為1，否則為0。因為每個都市只去一次，因此其中任何一個都市的必有且僅有一條進(jìn)入路線和一條出的路線。我們引入0-1變量，若通過兩都市之間的路徑，則賦值為1；若不通過兩都市之間的路徑，則賦值為0。關(guān)于無向圖的最短時刻路徑問題，能夠如此理解，從點到點和點到點的邊，看成有向弧，其他各條邊均看成有不同方向的雙弧。使用lingo設(shè)計算法（代碼5），得到最優(yōu)解為（截取有通路部分）： Variable Value Reduced Cost X12 1.000000 322.0000 X16 1.000000 280.0000 X29 1.000000 110.0000 X35

25、 1.000000 100.0000 X311 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）：舟山武漢九江黃山北京洛陽徐州常州西安祁縣青島得 min=1966min 圖 3計時刻最短的行程表:依照以上線路，結(jié)合實際情況，設(shè)計出以下線路表，時刻最短為：184小時日期

26、時刻行程價格（元）5月1日07：3512：26乘坐列車T54（徐州常州）7012：2613：30乘坐出租車到常州恐龍公園4013：3017：30游玩常州恐龍公園19017：3018：60乘坐出租車到常州奔牛機(jī)場4018：3021：10休息021：1023：00乘坐飛機(jī)MU5638(常州西安)62323：0024：00乘坐出租車到秦始皇兵馬俑405月2日00:008：00住宿于西安美寶賓館后辛門店1388；0010：00游玩秦始皇兵馬俑15010：0011：00乘坐出租車西安咸陽飛機(jī)場4011：0011：35游玩西安市011：3512：50乘坐飛機(jī)GS4612（西安太原）41312：5014：0

27、0乘坐公交車到喬家大院4014：0017：00游玩喬家大院4017：0018：00乘坐出租車到西安咸陽飛機(jī)場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ī)場4015：0017：30游玩青島017：3018：55乘坐飛機(jī)HU7842（青島寧波）74318：5520：00乘坐出租車到普陀山風(fēng)景區(qū)4020：0008：00住宿于舟山華融大酒店1585月4日8：0014：00游玩普陀山

28、風(fēng)景區(qū)20014：0015：00乘坐出租車返回寧波櫟社飛機(jī)場4015：0020：40游玩寧波市020：4022：00乘坐飛機(jī)MU2532（寧波武漢）53622：0023：00乘坐出租車到黃鶴樓4023：0008：00住宿于武漢鄂鋼大酒店895月5日08：0010：00游玩黃鶴樓8010：0011：00乘坐出租車到武漢天河國際場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

29、：0016：15乘出租車到九江4016：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ī)場4016：0021：35游玩黃山市021：3523：35乘坐飛機(jī)CA1552（黃山北京）86523：3507;00住宿于北京佳號賓館1685月8日07:0008：00乘坐出租車到八達(dá)嶺長城4008：0011：00游玩八達(dá)嶺長城4511：0012：00乘坐出租車返回北京首都機(jī)場012：001

30、2：55游玩北京012：5514：40乘坐飛機(jī)MU5695（北京洛陽075614：4015：00乘坐出租車到龍門石窟4015：0018：00游玩龍門石窟12018：0018：32乘坐出租車返回洛陽站4018：3201：02乘坐列車K1132（洛陽徐州）70吃飯等其他費用480總旅游費8272總時刻（單位：小時）185第三問求解：在第一問的求解結(jié)果的基礎(chǔ)上，我們添加以下約束，旅游總經(jīng)費：同時把旅游景點的個數(shù)調(diào)整為動態(tài)的。首先，確定第一小問各個景點的總花費（如表4）和城際交通費用（如表5），列出下表：都市1234567891011花費（元）0311214734414428984292253326

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

32、九江）875月2日7：088：00乘坐公交到廬山風(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（武昌洛陽）926：277：30休息05月4日7：308：30乘坐81W公交到龍門石窟28

33、：3011：30游玩龍門石窟12011：3012：30乘坐43W返回洛陽站212：3017：15游玩洛陽市017：1522：47乘坐列車K388（洛陽西安）3222：4700：00乘坐306W公交車到秦始皇兵馬俑200：008：00住宿于西安美寶賓館后辛門店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：29

34、04：00乘坐列車2604（祁縣北京09404：0007：00休息007：0008:00乘坐地鐵2號線和919公交到八達(dá)嶺長城1408:0011:00游玩八達(dá)嶺4511：0012：00乘坐地鐵2號線和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乘坐列車111

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

36、9111065808580102318120105280 表7先把停留時刻最長的四個都市剔除，即西安、九江、舟山、青島，將剩下的都市計算得到最短花費時刻為4593min（不包括到達(dá)中斷都市的車程），遠(yuǎn)遠(yuǎn)小與7200min。把四個都市分不添加到里面去，通過計算，發(fā)覺添加青島到里面去時，結(jié)果較好?？紤]到祁縣的交通問題，把西安添加到里面去，再計算總時刻，結(jié)果不符合要求，最后，把黃山剔除，得到的結(jié)果符合要求。即得到最優(yōu)路線：8 4 6 1 2 9 5 3 即：武漢北京洛陽徐州常州西安祁縣青島具體行程表如下：日期時刻行程價格（元）5月1日07：3512：26乘坐列車T54（徐州常州）7012;2613:

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

38、安咸陽機(jī)場4018：0018：35游玩太原018：3519：55乘坐飛機(jī)SC4612（太原青島）63119：5521：00乘出租車到嶗山4021：008：00住宿于青島親天橋賓館885月3日8：0014：00游玩嶗山13014：0015：00乘公交返回青島流亭機(jī)場4015：0020：00游玩青島020：0021：55乘飛機(jī)HU9960（青島武漢0144521：5523：00乘出租車到黃鶴樓4023：0008：00住宿于武漢鄂鋼大酒店895月4日08：0010：00游玩黃鶴樓8010：0010：40乘出租車到武漢天河國際機(jī)場4010：4012：35乘坐飛機(jī)CA1334（武漢北京）94112：35

39、13;35乘出租到八達(dá)嶺長城4013:3516:35游玩八達(dá)嶺長城4516:3517：35乘出租返回北京首都機(jī)場4017：3519：20游玩北京019：2021：05乘坐飛機(jī)MU（北京洛陽074821：0522：00乘坐出租到洛陽東山賓館4022：0007：00住宿于東山賓館5585月5日07：0008;00乘出租到龍門石窟4008:0011:00游玩龍門石窟12011:0012:07乘出租到洛陽站4012:0718:23乘坐列車K1352（洛陽徐州）70吃飯等其他費用300總費用7469總時刻（單位：分鐘）6408第五問求解：考慮到此題是在時刻和花費上雙重約束，依照第三小問和第四小問所得到的

40、各個都市和各條路線的停留時刻和花費，首先，剔除停留時刻最長的四個和花費最多的四個，由于重復(fù)，最后剩下北京、祁縣、洛陽、武漢四個都市，通過計算，得知明顯還有時刻和費用，把青島添加到里面去，并結(jié)合實際情況，得到最后結(jié)果為： =1 6 8 5 4 3 即：徐州洛陽武漢祁縣北京青島設(shè)計出以下線路表：日期時刻行程價格（元）5月1日23：0005：26乘坐列車K560(徐州洛陽)705月2日05：2607：00休息007：0008：00乘坐81W公交到龍門石窟208：0011：00游玩龍門石窟12011：0012：07乘坐81W公交返回洛陽站212：0714：10乘坐列車D1003（洛陽西安）19014：

41、1015：10乘坐81W公交車到達(dá)秦始皇兵馬俑115：1017：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號線和919公交到八達(dá)嶺長城1408；0011：00游玩八達(dá)嶺長城4511：0012

42、：00乘坐地鐵2號線和919公交返回北京西站14123：0022：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吃飯等其它費用300總費用1848總時刻（單位：分鐘06142七、模型評價優(yōu)點 ：1、把最優(yōu)解問題看成是時刻與花費的函數(shù)，通過添加不同的約束條件來求解不同的問題，在一定的程度上，簡化了問題的解答過程； 2、用TSP問題的解答方法來確定最

43、優(yōu)路線，最后再依照實際設(shè)計行程表； 3、引入01變量，把最短路徑問題轉(zhuǎn)化為線性規(guī)劃問題，直接用lingo軟件即可求解； 4、能夠推廣到網(wǎng)絡(luò)優(yōu)化等問題，容易解決實際問題； 缺點 ：1、求解過程中出現(xiàn)深夜處于休息狀態(tài)而不是到旅館住宿，不符合實際情況，缺乏合理性； 2、在求解第五小問時沒有采納更精確的方法進(jìn)行預(yù)測，得到的只是較優(yōu)線路； 3、由于時刻和數(shù)據(jù)有限和網(wǎng)絡(luò)數(shù)據(jù)的不確定性，不具備足夠的講服力；八附錄：代碼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.0

44、7 39.92 37.36 34.7 30.19 30.52 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.97; % C 11個

45、都市的坐標(biāo)(經(jīng)緯度)，112的矩陣 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.4

46、907 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 7.1208 4.5796 8.4718 12.4102; 4.7803 8.0541 8.0081 6.5885 2.6623 0 7.2684 4.5792 3.5164 6.1124

47、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.3710 14.0254; 4.7133 4.4907 7.7110 10.2218 8.4718 6.1124 2.2225 1.8471 8.3710 0 6

48、.3353;6.6644 2.9724 6.4102 11.5372 12.4102 10.9358 4.1658 8.0089 14.0254 6.3353 0代碼3%用floyd算法求兩兩之間最短路徑矩陣及兩兩之間最短距離矩陣Da= 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.00

49、81 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 7.1208 4.5796 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.

50、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.3710 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

51、.9358 4.1658 8.0089 14.0254 6.3353 0;D,R=floyd(a)functionD,R=floyd(a)n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endendRfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end D Rend代碼4：差不多蟻群算法解決TSP問題的Matlab程序 m=11; %螞蟻個數(shù) Alpha=1; % Alpha 表征信息素重要程度的參數(shù) B

52、eta=5; % Beta 表征啟發(fā)式因子重要程度的參數(shù) Rho=0.1; % Rho 信息素蒸發(fā)系數(shù) NC_max=1000; % NC_max 最大迭代次數(shù) Q=100; % Q 信息素增加強(qiáng)度系數(shù) 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.97; % C n個都市的坐標(biāo)，n2的矩陣 c,d=size(C); D=zeros(c,c); for i=1:c

53、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 n=11; %n表示問題的規(guī)模（都市個數(shù)） Eta=1./D; %Eta為啟發(fā)因子，那個地點設(shè)為距離的倒數(shù) Tau=ones(11,11); %Tau為信息素矩陣 Tabu=zeros(11,11); %存儲并記錄路徑的生成 NC=1; %迭代計數(shù)器 R_best=zeros(NC_max,n); %各代最佳路線 L_best=inf.*ones(NC_max,1);%各代最佳路線的長度 L_ave=zeros(NC_ma

54、x,1); %各代路線的平均長度 while NC=rand); to_visit=J(Select(1); Tabu(i,j)=to_visit; end end if NC=2 Tabu(1,:)=R_best(NC-1,:); end %第四步：記錄本次迭代最佳路線 L=zeros(m,1); for i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1); end L(i)=L(i)+D(R(1),R(n); end L_best(NC)=min(L); pos=find(L=L_best(NC); R_best(NC,:)=T

55、abu(pos(1),:); L_ave(NC)=mean(L); NC=NC+1 %第五步：更新信息素 Delta_Tau=zeros(n,n); for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i); end Delta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i); end Tau=(1-Rho).*Tau+Delta_Tau; %第六步：禁忌表清零 Tabu=zeros(m,n

56、); end %第七步：輸出結(jié)果 Pos=find(L_best=min(L_best); Shortest_Route=R_best(Pos(1),:) Shortest_Length=L_best(Pos(1) 代碼5：確定都市之間到達(dá)的最短時刻矩陣 通過網(wǎng)上的相關(guān)資料，我們得到各個都市之間到達(dá)的最短時刻矩陣為： 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 120 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