線路優(yōu)化設(shè)計

1、關(guān)于篩選最佳旅游線路的方案設(shè)計摘要隨著人們的生活水平不斷提高，旅游已成為人們享受生活的重要活動。但是旅游也會有以下限制，比如假期通常不會太長，且旅行的花費(fèi)也需提前計劃好，因此在規(guī)定的時間內(nèi)花最少的錢游覽最多的景點促成了優(yōu)化旅游這一名詞的誕生。旅游優(yōu)化，就是在旅游前，運(yùn)用數(shù)學(xué)方法，合理規(guī)劃路線，盡可能縮短旅行在途時間，既可提高時間利用效率、也可減輕旅途勞頓。本文研究的旅游路徑是一個封閉回路的數(shù)學(xué)模型。即在一個有多個城市的地圖網(wǎng)絡(luò)中，尋找一條從給定的起點到給定的終點沿途恰好經(jīng)過其他城市一次又回到出發(fā)城市的路徑路徑。這一問題涉及到平面上的點的遍歷問題，即要尋找一條行走路線最短（盡可能照顧花費(fèi)最少）但

2、又可以行遍圖上所有點的路徑。問題一時間不限，尋找出最佳的哈密頓回路，使費(fèi)用盡可能的少，把景點看成純數(shù)學(xué)的點，計算出任意兩點間的費(fèi)用，用軟件工具計算得此時旅游費(fèi)用至少為3041 元，具體旅行路線見表3；問題二旅游費(fèi)用不限，計算出在途時間，利用Floyd算法，求出最少用時149 小時即可游玩所有目標(biāo)景區(qū)，旅游路線見表4；問題三在旅游費(fèi)用為2000 元得情況下，利用圖論Hamilton圈原理求出：旅游目的地最多為7 個，具體路線見表5；問題四在旅游時間為5 天的情況下，旅游目的地最多為8 個，具體旅游路線見表6；問題五在旅游時間為5 天旅游費(fèi)用為2000 元的情況下，利用貪婪法求出旅游目的地最多為7

3、個，具體旅游路線見表7。本文通過建立各種模型和對模型的求解，得出在不同情形下的最優(yōu)旅游路徑的規(guī)劃方案，雖然基于較理想的假設(shè)，但也有一定的現(xiàn)實意義?？晒﹤€人或旅行團(tuán)參考。最后，本文對模型進(jìn)行了相關(guān)評價及誤差分析，使其能更好的應(yīng)用于實際生活中。關(guān)健詞：旅游路徑 Hamilton Floyd 算法蟻群算法 MATLAB§1 問題的提出1.1 問題背景及分析隨著人們的生活不斷提高，旅游已成為提高人們生活質(zhì)量的重要活動。江蘇徐州有一位旅游愛好者打算現(xiàn)在的今年的五月一日早上8 點之后出發(fā)，到全國一些著名景點旅游，最后回到徐州。由于跟團(tuán)旅游會受到若干限制，他(她)打算自己作為背包客出游。他預(yù)選了十

4、個省市旅游景點，如表1 所示。表1. 預(yù)選的十個省市旅游景點省市景點名稱在景點的最短停留時間江蘇常州市恐龍園4小時山東青島市嶗山6小時北京八達(dá)嶺長城3小時山西祁縣喬家大院3小時河南洛陽市龍門石窟3小時安徽黃山市黃山7小時湖北武漢市黃鶴樓2小時陜西西安市秦始皇兵馬俑2小時江西九江市廬山7小時浙江舟山市普陀山6小時本文的核心問題是在不同的約束條件下，建立起一個能用最少的時間和費(fèi)用瀏覽最多景點，最終要回到自己原地點的一個數(shù)學(xué)模型。§2 問題的分析2.1 要解決的問題(1) 如果時間不限，游客將十個景點全游覽完，至少需要多少旅游費(fèi)用？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅程表。(2) 如果旅游

5、費(fèi)用不限，游客將十個景點全游覽完，至少需要多少時間？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅程表。(3) 如果這位游客準(zhǔn)備2000元旅游費(fèi)用，想盡可能多游覽景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅程表。 (4) 如果這位游客只有5天的時間，想盡可能多游覽景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅程表。(5) 如果這位游客只有5天的時間和2000元的旅游費(fèi)用，想盡可能多游覽景點，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅程表。2.2 對應(yīng)的解決方法問題一：問題一中，我們采用flody算法算出最短路徑后，以此為基準(zhǔn)進(jìn)行路線的設(shè)計。為了盡量減少費(fèi)用，我們以火車為主要交通工具，并盡量避免住宿費(fèi)。這個過程涉及火車班次的靈活選擇。 問題二：問題二中，我

6、們同樣是在flody算法為基準(zhǔn)的條件下，盡量減少時間。由于旅游景點的時間是確定的，為此我們盡量減少旅行時間和盡量減少住宿。所以交通工具以飛機(jī)為主。問題三：問題三中，本問題的優(yōu)化目標(biāo)是在費(fèi)用的約束下旅游更多的景點。這個問題可以看成是問題一擴(kuò)展。優(yōu)化方法一樣，只不過少了要游完所有景點這一約束條件，多了費(fèi)用約束（費(fèi)用=2000）問題四：問題四中，本問題的優(yōu)化目標(biāo)是在時間的約束下旅游更多的景點。這個問題可以看成是問題二的擴(kuò)展。優(yōu)化方法一樣，只不過少了要游完所有景點這一約束條件，多了時間約束（時間=5*24=120）問題五：問題五可以說是所有問題的結(jié)合，時間約束和費(fèi)用約束同時存在。這里我們在三四問題的基

7、礎(chǔ)上盡量求出最優(yōu)解。 §3 模型的假設(shè)(A) 城際交通出行可以乘火車(含高鐵)、長途汽車或飛機(jī)（不允許包車或包機(jī)），并且車票或機(jī)票可預(yù)訂到。(B) 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(C) 旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點門票(第一門票)。晚上20：00至次日早晨7：00之間，如果在某地停留超過6小時，必須住宿，住宿費(fèi)用不超過200元/天。吃飯等其它費(fèi)用60元/天。(D) 假設(shè)景點的開放時間為8:00至18:00。(E)交通狀況良好，不出現(xiàn)堵車、晚班、晚點情況§4 定義與符號說明1、旅游景點的個數(shù)2、選擇第i條路線總費(fèi)用3、選擇第

8、i條路線總時間4個點可選擇路線的總數(shù)5、吃飯等其他費(fèi)用6、第i條路線到景點j 間的路費(fèi)7、第i條路線第j 個景點的門票8、第i條路線第j 個景點的住宿費(fèi)用9、第i條路線到第j 個景點的路上時間10、第i條路線第j 個景點的停留時間11、第i條路線第j 個景點的住宿時間12、其他時間，包括吃飯、等待時間等13、第i條路線第j 個景點是否需要住宿 (0-1 變量)§5 模型的建立與求解5.1 建立模型第一問是在時間充裕的情況下，設(shè)計一條路線，使得所用費(fèi)用盡可能的少，屬于單目標(biāo)優(yōu)化問題。十個景點中選擇n個景點，我們需要根據(jù)手頭資90料，理想化一些情況。設(shè)計出每條路徑的總費(fèi)用與總時間各自的表

9、達(dá)式。我們引入一變量=1 第條路線在第個景點需要住宿 0 第條路線在第個景點不需要住宿則：又引入函數(shù)k 來表示時間和費(fèi)用與景點個數(shù)間的函數(shù)關(guān)系我們將各種路況信息，收費(fèi)情況等收集并放到集合R（收集的信息過于龐大，故不在報告中顯示出來）中，將可選擇的路線放到集合I中。下面是每個題的解題過程：第一問：旅游費(fèi)用盡可能少作為目標(biāo)，時間無限制，只有一個約束條件（要游玩10個景點）可用下面模型來描述。根據(jù)R和I中數(shù)據(jù)確定最好的路線。第二問：時間為作為優(yōu)化的目標(biāo)，對費(fèi)用沒有要求，限制條件和第一問相同。可用下面模型來描述。限制條件：根據(jù)R和I中數(shù)據(jù)確定最好的路線。第三問：可旅游景點個數(shù)為優(yōu)化對象，這里對旅游費(fèi)用

10、作為約束條件。如下：根據(jù)R和I中數(shù)據(jù)確定最好的路線。第四問：這一問可以理解為在第三問的基礎(chǔ)上對時間進(jìn)行了約束，因為優(yōu)化目標(biāo)是相同的。如下:第五問:把每個旅游景點看做一個節(jié)點，各景點之間的距離長度看做對應(yīng)節(jié)點間的權(quán)長。旅游路線圖就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖Q，最佳旅游路線問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找使得總權(quán)（路程）最小，此即TSP 問題。對于本問題：設(shè)I1，I2，I3.，In是要旅游的景點，Ii 到Ij的路程為dij，現(xiàn)在求從I0（徐州）出發(fā)，游遍所有景點且只經(jīng)過一次的最短路程。我們將此問題類比著名的貨郎擔(dān)問題，建立如下動態(tài)規(guī)劃模型。設(shè)U表示從I0 到Ii 中間可能經(jīng)過的景點集合，U包含除I0 和

11、Ii 之外的其余點的集合，I點中的個數(shù)是隨不同問題而改變。為了表示行進(jìn)狀態(tài)，令坐標(biāo)（i，u)表示從I0 出發(fā)，經(jīng)過U集合中所有點一次最后到達(dá)Ii。用最優(yōu)指標(biāo)函數(shù)Mk(i，u)表示從I0 出發(fā)，經(jīng)過U集合中所有點一次最后到達(dá)Ii。則動態(tài)規(guī)劃的順序遞推關(guān)系為：Mki，u=minMkj，u+dijMoi，空=dijk，i=1,2,3n<=10且為整數(shù)，j屬于U。根據(jù)上述模型，我們只要輸入約束條件和優(yōu)化目標(biāo)就可以規(guī)劃出最優(yōu)的路線。5.2 模型求解模型建立中我們將路線選擇問題類比為貨郎擔(dān)問題，采用floyd算法求出通過所有景點路徑之和的最小值。問題一和問題二據(jù)此得到解決。為了便于下面的描述，我們給

12、每個景點進(jìn)行編號。當(dāng)然過程中將路線路程理想化。圖表如下：表2.景點門票和編號景點編號景點名稱景點門票價/元0徐州01常州市恐龍園1002青島市嶗山653八達(dá)嶺長城804祁縣喬家大院725洛陽市龍門石窟1086黃山市黃山1507武漢市黃鶴樓808西安市秦始皇兵馬俑1509九江市廬山18010舟山市普陀山160根據(jù)圖論的相關(guān)知識，TSP 問題套用最佳哈密爾頓回路的問題結(jié)論進(jìn)行求解。得到最佳旅游線路的近似算法。（1）用Floyd 算法求出圖中任意兩點之間的最短路，構(gòu)建一個完備圖G' ,點集仍為N ，每條邊(i, j)的權(quán)為點i和j在Q中最短路的長。（2）搜索圖Q的若干個H圈。（3）用二邊逐次

13、修正法對步驟二中的H 圈進(jìn)行優(yōu)化，得到理論上最佳H 圈。求解過程：任意兩坐標(biāo)點間的權(quán)值，也即兩點間的距離可用矩陣表示，如下：A=0 430 427 752 683 470 616 565 784 633 787430 0 611 1130 1077 834 319 661 1160 547 388427 611 0 700 862 835 807 983 1147 979 904752 1130 700 0 578 843 1304 1208 1088 1355 1438683 1077 862 578 0 364 1202 885 511 1053 1455470 834 835 843 3

14、64 0 846 557 338 765 1218616 319 807 1304 1202 846 0 507 1134 328 520 565 661 983 1208 885 557 507 0 750 245 958 784 1160 1147 1088 511 338 1134 750 0 989 1539633 547 979 1355 1053 765 328 245 989 0 769787 388 904 1438 1455 1218 520 958 1539 0用Floyd 算法求出圖中任意兩點之間的最短路，Mtalab源程序見附錄1：運(yùn)行結(jié)果：Columns 1 thro

15、ugh 110 2 3485 7 96101sum =427+700+578+511+388+557+245+328+520+430=4207根據(jù)結(jié)果得到最小的H 圈如下圖圖1我們對所得到的最佳H 圈繼續(xù)進(jìn)行驗證，得到了最佳旅游路線，跟算法得出的結(jié)果相同，即為：023485796101由于第一問對時間無限制，盡可能的減少旅游費(fèi)用。所以我們旅行工具采用火車為主。用最小行程的方法求解出路線。具體行程表如下：五一出行行程表（不限時間）時間行程5月1日乘火車(K68/K69)(22:30-次日6:53），乘公交車去嶗山風(fēng)景區(qū)游玩（7:00-11:30）5月2日乘坐火車（D338）去北京（14:30-1

16、9：46），住宿5月3日早上起游玩八達(dá)嶺長城（8：00-11:00），乘火車(K603)去山西祁縣（17：17-5:08）5月5日早上起去游玩喬家大院（8:00-11:00），晚上乘火車（1095）去陜西西安（20:29-次日6:56）5月6日早上去游玩秦始皇兵馬俑（8:00-10:00），然后乘火車（G2006）去洛陽（10:18-12:03）然后游玩龍門石窟（12:30-15:30）下午乘火車（G858/G855）去湖北武漢（16:50-19:40）晚上住宿。5月7日早上去游玩黃鶴樓（8:00-10:00）然后乘火車（D3223）去江西九江（11:12-13:00）住宿5月8日早上去游玩廬

17、江（8:00-15:00）5月9日凌晨乘火車（K26）去安徽（0:40-7:34）早上去游覽黃山（8:00-15:00）晚上乘火車（K820/K8417去南京站轉(zhuǎn)G7631）去浙江普陀山（21:33-次日9:53）5月10日早上去游玩普陀山（10:00-12:00）下午乘火車（G7582）去常州（17:14-20：30）。住宿5月11日早上去游玩常州恐龍園（8:00-12：00）晚上乘火車（G218）回徐州總費(fèi)用=乘車費(fèi)用+門票費(fèi)用+住宿費(fèi)用+其他費(fèi)用乘車費(fèi)用：103+186+110+104+98+115+58+68+78+114+106=1140（元）門票費(fèi)用：100+65+80+72+10

18、8+150+80+150+180+160=1145（元）住宿費(fèi)用：4*50=200（元）其他費(fèi)用：10*60=600（元）總費(fèi)用：1140+1145+200+600=3085（元）問題二求解：若使旅行時間最少，必須減少交通時間和住宿時間。交通時間的較少可以通過乘飛機(jī)或高鐵來實現(xiàn)，住宿時間的減少可以通過盡量在白天旅游，晚上趕路的方式實現(xiàn)。我們認(rèn)為旅客的使用時間由三部分組成,即在路上的時間，在景點停留的時間和可能住宿時間。所以我們定義：5.2.4 模型求解域結(jié)果分析：受floyd算法啟發(fā)，將任意兩個景點之間的時間看做權(quán)，即相鄰兩點的邊長，得出11*11 的時間矩陣，單位為分鐘。A=0 430 42

19、7 752 683 470 616 565 784 633 787430 0 611 1130 1077 834 319 661 1160 547 388427 611 0 700 862 835 807 983 1147 979 904752 1130 700 0 578 843 1304 1208 1088 1355 1438683 1077 862 578 0 364 1202 885 511 1053 1455470 834 835 843 364 0 846 557 338 765 1218616 319 807 1304 1202 846 0 507 1134 328 520 56

20、5 661 983 1208 885 557 507 0 750 245 958 784 1160 1147 1088 511 338 1134 750 0 989 1539633 547 979 1355 1053 765 328 245 989 0 769787 388 904 1438 1455 1218 520 958 1539 0利用floyd算法在所有可能的組合方式中求出唯一的一組方式，此方式使得行程時間最短， 小時，結(jié)果如下：徐州-八達(dá)嶺-祁縣-洛陽-西安-武漢-九江-黃山-舟山-常州-青島-徐州具體路線為：問題二表：問題三求解：在旅行費(fèi)用為2000 元的限制條件下，要盡可能多的

21、游覽景區(qū)就必須減少交通費(fèi)用以增加游覽景點的費(fèi)用。由此聯(lián)想到“蟻群算法”3（155-158）求最短路徑問題。用”蟻群算法”求R（R=1,2,3,4,5,6,7,8,9）個景點行程閉合路線的最短距離和，每個R 都對應(yīng)一個總費(fèi)用，則必存在唯一的一個最大R 值使得總費(fèi)用接近2000 元，此R 值即最多景點數(shù)，MATLAB 程序見附錄2由此算法得出的不同R 值閉合路徑如下：圖2R=6圖3R=7圖4R=8當(dāng)R=7 時，確定的旅游路線如下：表5：根據(jù)模型綜合考慮各種因素設(shè)計的行程表問題3第一種路線日期起點終點車次/航班發(fā)時到時住宿逗留（h）車票價門票價5.2徐州常州K13318：4913：19否469140

22、5.3常州黃山K841823：419：00否7722305.4黃山九江K70和218518:2223.322:197:14是7751805.5九江武漢K9212：047：31否250805.6武漢西安K86415：455:32否2128.5905.6西安洛陽T37410：1715：00否3541205.7洛陽祁縣1166和L782520：227：2611：50-12：38否399405.8祁縣徐州4612和155116:1117:2819:5310:45否0105問題四求解：本題所要實現(xiàn)的目標(biāo)是在5天內(nèi)游覽盡可能多的地方。顯然，時間最短和游覽的景點盡量多是該問題的兩個目標(biāo)。所以利用貪婪法從旅游

23、耗時、路程長短、住宿耗時幾方面綜合考慮，確定局部最優(yōu)解。首先，要使旅游景點的個數(shù)盡可能的多，可以除去交通和觀光時間比較長的景點，如青島市嶗山、黃山市黃山、九江市廬山、舟山市普陀山剩下的景點相對比較聚集且景點逗留時間較短，我們每一次都從與本地相鄰的幾個城市中選擇耗時最短并且滿足交通班次與景點逗留時間不產(chǎn)生矛盾的目的地，達(dá)到局部優(yōu)化時隙分配的目的。由于常州到青島的時間最長，而且在青島的觀光時間為6h,所以優(yōu)先考慮除去青島這一點。即在舟山市普陀山游玩后直接乘車回到徐州，這樣可以在5 天時間內(nèi)游覽8 個景點。具體路線行程為：表6：根據(jù)模型綜合考慮各種因素設(shè)計的行程表日期起點終點車次/航班發(fā)時到時住宿逗

24、留（h）5.1徐州常州G1779：2411：25是45.2常州舟山G75818：3511:47否65.3舟山武漢CZ378618：5020：35是25.3武漢洛陽G83211：3014：33是35.4洛陽西安D3066：408:46是25.5西安北京HU72388：059：45是35.6北京青島CA15697：309：05否65.6青島徐州G23316：3520：37問題五求解：如果這位游客只有5 天的時間和2000 元的旅游費(fèi)用，想盡可能多游覽景點，是在時間和費(fèi)用都受約束限制下的優(yōu)化問題，故問題五可以看作是問題三和問題四的“雙重約束”，可以在問題三與問題四的求解結(jié)果基礎(chǔ)上求解。最后達(dá)到三個目

25、標(biāo)，1、用時要少；2、費(fèi)用要低；3、選擇路線時時間和費(fèi)用都要達(dá)到最優(yōu)。問題三中交通工具選為火車，為了減少時間，部分距離近票價低的景點可以改乘更快的交通工具。問題四中交通工具選為飛機(jī)，為了減少費(fèi)用，部分距離長票價高的景點可以改乘火車。另外要優(yōu)先考慮景點門票路費(fèi)低的景點以增加旅游景點的個數(shù)，并規(guī)避住宿。時間t 和交通工具費(fèi)用p 關(guān)系分析：對于火車，p 小但t 大;對于飛機(jī),p 大但t 小。為了平衡，定義s=P*t,在兩個景點之間分別考慮火車和飛機(jī)的s 值，優(yōu)先選擇s 值小的方式。綜合各方面因素考慮，給出如下比較合理的旅游路線：日期起點-終點車次/航班發(fā)時到時住宿逗留（h）車票價門票5.1徐州常州K

26、1908:0013:32否4691405.2常州黃山K841823：41-9:00否7722305.3黃山武漢K70和K35118：2223：321：398：48否2122805.4武漢洛陽K79000:159:24否3861205.4洛陽西安G85213：1115：04否2174905.5西安北京T4419：008：29否3156455.6北京徐州146111:5422:3993費(fèi)用：火車票價（772）+門票價（705）+餐飲（300）+市內(nèi)交通（）=1777總費(fèi)用：190+50+（170+40）+（40+90）+（28+120）+（85+485）+（202+150）+50+（50+120+

27、90）+60*5=2023即在五天內(nèi)花費(fèi)2023元可旅行7個景點，此路線是最優(yōu)。§6 模型的評價與改進(jìn)6.1 模型評價在求解中，我們利用了Hamilton算法、floyd算法、蟻群算法等數(shù)模常用方法，準(zhǔn)確方便的求出最短路程，最少費(fèi)用并根據(jù)在時間和費(fèi)用性質(zhì)都有限制的情況下設(shè)計出最佳旅游路線，結(jié)果可靠性，靈活度較高，在現(xiàn)實生活中的其他方面如尋求最佳交通運(yùn)輸路徑時，也能得到很好的應(yīng)用。6.2 模型改進(jìn)（1）因數(shù)據(jù)資料搜集來自網(wǎng)上，從火車站到景點路程時間并不一定準(zhǔn)確，且建立模型時簡化了次要因素，會存在誤差。（2）本題的解決方案假設(shè)在理想化的基礎(chǔ)上，如沒考慮游客旅途休息，住宿及時性，排除迷路概

28、率，實際出行時會遇到各種各樣與假設(shè)有出入的情況，所以該文有一定的局限性。參考文獻(xiàn)1方冬云圖論在旅游線路選擇中的應(yīng)用 長春工業(yè)大學(xué) 2010.12 李士勇蟻群算法及其應(yīng)用哈爾濱工業(yè)大學(xué)出版社2004.93馮愛芬最佳旅游路線設(shè)計與算法20084附錄附錄1a; %輸入數(shù)據(jù)function D , path = floyd(a)n=size(a,1);D=a;path=zeros(n,n);fori=1:nfor j=1:nif D(i,j)=infpath(i,j)=j;endendendfor k=1:nfori=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j)D(i,

29、j)=D(i,k)+D(k,j);path(i,j)=path(i,k)endendendendD,path根據(jù)求出的最短距離矩陣，我們可得出最小距離圖求出最小距離矩陣后，再用Mtalab編程求出最佳H 圈和最小路程。Mtalab源程序如下：clc,clearfloyda;%輸入數(shù)據(jù)c1=1 2:21 22;L=length(c1);flag=1;while flag>0flag=0;for m=1:L-3for n=m+2:L-1ifa(c1(m),c1(n)+a(c1(m+1),c1(n+1)<a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;1 3c

30、1(m+1:n)=c1(n:-1:m+1);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1);endcircle=c1;sum=sum1;c1=1 22 2:21;%改變初始圈，該算法的最后一個頂點不動flag=1;while flag>0flag=0;for m=1:L-3for n=m+2:L-1if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<.a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);endendendendsum1

31、=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1);endif sum1<sumsum=sum1;circle=c1;endcircle,sum附錄2%蟻群算法求解TSP 問題的matlab程序clear allclose allclc%初始化蟻群m=5;%蟻群中螞蟻的數(shù)量，當(dāng)m 接近或等于城市個數(shù)n 時，本算法可以在最少的迭代次數(shù)內(nèi)找到最優(yōu)解C=2449 1715; 2701 1687;2544 1917;2215 1859;1880 1469;1978 1334;2590 14951 42244 1295;1719 1160;2442 1354;2923 1

32、688;%城市的坐標(biāo)矩陣Nc_max=200;%最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動的撥數(shù)（每撥螞蟻的數(shù)量當(dāng)然都是m）alpha=1;%螞蟻在運(yùn)動過程中所積累信息（即信息素）在螞蟻選擇路徑時的相對重要程度，alpha 過大時，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象beta=5;%啟發(fā)式因子在螞蟻選擇路徑時的相對重要程度rho=0.5;%0<rho<1,表示路徑上信息素的衰減系數(shù)（亦稱揮發(fā)系數(shù)、蒸發(fā)系數(shù)），1-rho表示信息素的持久性系數(shù)Q=100;%螞蟻釋放的信息素量，對本算法的性能影響不大a%變量初始化n=size(C,1)-（10-R）;%表示TSP 問題的規(guī)模，亦即城市的

33、數(shù)量D=ones(n,n);%表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離fori=1:nfor j=1:nifi<jD(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2);endD(j,i)=D(i,j);endendeta=1./D;%啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù)pheromone=ones(n,n);%信息素矩陣,這里假設(shè)任何兩個城市之間路徑上的初始信息素都為1tabu_list=zeros(m,n);%禁忌表，記錄螞蟻已經(jīng)走過的城市，螞蟻在本次循環(huán)中不能再經(jīng)過這些城市。當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來計算螞蟻當(dāng)前所建立的解決方案，即經(jīng)

34、過的路徑和路徑的長度Nc=0;%循環(huán)次數(shù)計數(shù)器routh_best=zeros(Nc_max,n);%各次循環(huán)的最短路徑length_best=ones(Nc_max,1);%各次循環(huán)最短路徑的長度length_average=ones(Nc_max,1);%各次循環(huán)所有路徑的平均長度whileNc<Nc_max%將m 只螞蟻放在n 個城市上rand_position=;fori=1:ceil(m/n)rand_position=rand_position,randperm(n);endtabu_list(:,1)=(rand_position(1:m)'%將螞蟻放在城市上之后的

35、禁忌表，第i行表示第i只螞蟻，第i行第一列元素表示第i只螞蟻所在的初始城市%m 只螞蟻按概率函數(shù)選擇下一座城市，在本次循環(huán)中完成各自的周游for j=2:nfori=1:mcity_visited=tabu_list(i,1:(j-1);%已訪問的城市city_remained=zeros(1,(n-j+1);%待訪問的城市1 5probability=city_remained;%待訪問城市的訪問概率cr=1;for k=1:n%for 循環(huán)用于求待訪問的城市。比如如果城市個數(shù)是5，而已訪問的城市city_visited=2 4,則經(jīng)過此for 循環(huán)后city_remanied=1 3 5i

36、f length(find(city_visited=k)=0city_remained(cr)=k;cr=cr+1;endend%狀態(tài)轉(zhuǎn)移規(guī)則*q0=0.5;if rand>q0for k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta;position=find(probability=max(probability);to_visit=city_remained(po

37、sition(1);endelsefor k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta;endprobability=probability/sum(probability);pcum=cumsum(probability);select=find(pcum>=rand);to_visit=city_remained(select(1);endtabu_list(i,

38、j)=to_visit;%*endendifNc>0tabu_list(1,:)=routh_best(Nc,:);%將上一代的最優(yōu)路徑（最優(yōu)解）保留下來，保證上一代中的最適應(yīng)個體的信息不會丟失end%記錄本次循環(huán)的最佳路線total_length=zeros(m,1);%m 只螞蟻在本次循環(huán)中分別所走過的路徑長度fori=1:mr=tabu_list(i,:);%取出第i只螞蟻在本次循環(huán)中所走的路徑for j=1:(n-1)1 6total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只螞蟻本次循環(huán)中從起點城市到終點城市所走過的路徑長度endt

39、otal_length(i)=total_length(i)+D(r(1),r(n);%最終得到第i只螞蟻在本次循環(huán)中所走過的路徑長度endlength_best(Nc+1)=min(total_length);%把m 只螞蟻在本次循環(huán)中所走路徑長度的最小值作為本次循環(huán)中最短路徑的長度position=find(total_length=length_best(Nc+1);%找到最短路徑的位置，即最短路徑是第幾只螞蟻或哪幾只螞蟻走出來的routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一個走出最短路徑的螞蟻在本次循環(huán)中所走的路徑作為本次循環(huán)中的最優(yōu)路徑length_average(Nc+1)=mean(total_length);%計算本次循環(huán)中m 只螞蟻所走路徑的平均長度Nc=Nc+1%更新信息素delta_pheromone=zeros(n,n);fori=1:mfor j=1:(