蟻群算法與模擬退火算法對(duì)旅游路線問(wèn)題的探究(附matlab程序)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上蟻群算法與模擬退火算法對(duì)旅游路線問(wèn)題的探究張煊 張恒偉 徐曉輝摘要： 本文針對(duì)旅游中國(guó)34個(gè)城市的路線最優(yōu)化問(wèn)題，收集各城市經(jīng)緯度坐標(biāo)和實(shí)際城市間火車(chē)票與飛機(jī)票，在此大量數(shù)據(jù)的基礎(chǔ)之上，采用蟻群算法和模擬退火算法進(jìn)行啟發(fā)式搜索，就實(shí)際問(wèn)題給出了合理最優(yōu)的旅行路線和訂票方案。按照問(wèn)題要求，首先建立了城市旅行網(wǎng)絡(luò)，同時(shí)對(duì)網(wǎng)絡(luò)圖賦權(quán)，對(duì)數(shù)據(jù)進(jìn)行了收集和簡(jiǎn)單的處理，得到了經(jīng)緯度坐標(biāo)、火車(chē)票矩陣、飛機(jī)票矩陣及其對(duì)應(yīng)的時(shí)間矩陣。對(duì)于問(wèn)題（1），我們根據(jù)各城市經(jīng)緯度坐標(biāo)，利用經(jīng)緯度知識(shí)和球體的幾何知識(shí)，計(jì)算出各城市之間的距離，得到各個(gè)城市之間的距離矩陣，分別采用蟻群算法與模擬退火算

2、法搜索，將結(jié)果比較得到最短旅行路線為：哈爾濱長(zhǎng)春沈陽(yáng)天津北京呼和浩特太原石家莊濟(jì)南鄭州西安銀川蘭州西寧烏魯木齊拉薩昆明成都重慶貴陽(yáng)南寧?？趶V州澳門(mén)香港臺(tái)北福州南昌長(zhǎng)沙武漢合肥南京杭州上海哈爾濱，旅行路線總長(zhǎng)為1.6013萬(wàn)千米。在問(wèn)題（2）的求解中，首先用城市旅行網(wǎng)絡(luò)的車(chē)費(fèi)價(jià)格代替城市之間距離，重新賦權(quán)，在模型的基礎(chǔ)上，利用最小費(fèi)用矩陣，采用蟻群算法和模擬退火算法搜索，比較計(jì)算結(jié)果得到最經(jīng)濟(jì)的訂票方案為：哈爾濱1489長(zhǎng)春1416天津1416濟(jì)南1462南京1462上海1374杭州2002福州1216南昌K162合肥D3024武漢MU517臺(tái)北CZ6997澳門(mén)MU2790西寧1282拉薩K91

3、8蘭州1043烏魯木齊1043西安2612鄭州T201?？赥201廣州T99香港T98長(zhǎng)沙2514南寧2058昆明1236貴陽(yáng)1248重慶1271成都1718銀川2636呼和浩特2464太原2610石家莊4410北京1138沈陽(yáng)1122哈爾濱，費(fèi)用7212元。針對(duì)問(wèn)題（3）中所述的經(jīng)濟(jì)、省時(shí)又方便的原則，我們建立了旅行路線評(píng)價(jià)指標(biāo)Q，綜合考慮各方面因素，并以人為本修正指標(biāo)參數(shù)，最終得到指標(biāo)表達(dá)式Q=0.6M+8t，并以此為權(quán)，處理數(shù)據(jù)得到指標(biāo)矩陣，在模型的基礎(chǔ)上得到最優(yōu)旅行路線：哈爾濱2096長(zhǎng)春1490天津1394濟(jì)南1085鄭州1150西安1085蘭州T27拉薩T21西寧MU2790澳門(mén)C

4、Z6997臺(tái)北CA4912武漢D3024合肥D3020南京D5401上海D5655杭州D3107福州1216南昌T147長(zhǎng)沙T98香港T99廣州T201?？贕S7441南寧2058昆明1236貴陽(yáng)K9518重慶D5111成都K452烏魯木齊SC4912銀川1718呼和浩特2462太原2610石家莊4408北京D25沈陽(yáng)K19哈爾濱，Q值為6532,總費(fèi)用為8092元。本文綜合采用了蟻群算法和模擬退火算法，計(jì)算得到的最優(yōu)路線能滿(mǎn)足問(wèn)題的需要。就周先生的外出旅行提供了參考方案，搜集了大量的數(shù)據(jù)，緊密的與實(shí)際相結(jié)合，得到的方案可行性強(qiáng)，能很好地解決旅行方案的優(yōu)化問(wèn)題及類(lèi)似的組合優(yōu)化問(wèn)題，并可以廣泛的

5、應(yīng)用于其它領(lǐng)域。關(guān)鍵詞： 模擬退火算法 蟻群算法 旅行路線評(píng)價(jià)指標(biāo) 1.問(wèn)題重述計(jì)算從哈爾濱走遍全國(guó)34個(gè)城市的最短距離，設(shè)計(jì)出合理算法規(guī)劃出不同約束條件下的不同最優(yōu)方案：1首先在不考慮外部因素的情況下，利用地球的經(jīng)緯度，計(jì)算各個(gè)城市之間距離，建立數(shù)學(xué)模型，并規(guī)劃出最優(yōu)游遍34座城市的最短路線。2若2010年5月1日從哈爾濱市出發(fā)，在每個(gè)城市停留3天，利用航空、鐵路（快車(chē)臥鋪或動(dòng)車(chē)）交通工具，考慮到車(chē)次、航班情況，設(shè)計(jì)出游遍34座城市的最經(jīng)濟(jì)的旅行互聯(lián)網(wǎng)上訂票方案。3在綜合實(shí)際情況下考慮省錢(qián)、省時(shí)又方便，設(shè)定出相應(yīng)的評(píng)價(jià)準(zhǔn)則和指標(biāo)，建立相應(yīng)改進(jìn)后的數(shù)學(xué)模型，并在此前提下修訂上述兩種方案。4對(duì)本

6、文所用到的算法作復(fù)雜性、可行性及誤差分析。5針對(duì)旅行商問(wèn)題提出對(duì)自己所采用的算法的理解及評(píng)價(jià)。2 模型假設(shè)與符號(hào)說(shuō)明 2.1 模型假設(shè)（1） 近期內(nèi)火車(chē)票視為定值；（2） 飛機(jī)票的取值均取自打折后的；（3） 飛機(jī)票均取自近期內(nèi)的；（4） 估算城市之間的距離時(shí)忽略地形如丘陵盆地等自然因素對(duì)估算結(jié)果的影響； 2.2 符號(hào)說(shuō)明A、B兩市之間的距離加權(quán)圖定點(diǎn)（城市）的集合賦權(quán)邊的集合緯度經(jīng)度第i個(gè)城市到第j個(gè)城市的距離i個(gè)城市構(gòu)成的環(huán)路矩陣第k時(shí)刻的溫度（k=1,2, ，m）a溫度控制系數(shù)L退火算法內(nèi)循環(huán)循環(huán)次數(shù) （k=1，2，m ）禁忌表，記錄螞蟻k當(dāng)前已走過(guò)的城市表示城市i轉(zhuǎn)移到城市j的期望程度m

7、蟻群算法中，螞蟻總數(shù)表示t時(shí)刻在路徑（i，j）連線上殘留的信息量蟻群算法的循環(huán)次數(shù)第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度M旅行費(fèi)用t旅行時(shí)間Q旅行評(píng)價(jià)指標(biāo)3. 問(wèn)題分析 該問(wèn)題是一個(gè)旅行路徑的組合優(yōu)化問(wèn)題，其形式化描述為：用節(jié)點(diǎn)來(lái)表示34個(gè)城市,連接兩節(jié)點(diǎn)之間的邊表示旅行路線,并將路線的長(zhǎng)度等屬性表示為該邊的權(quán)值,那么就可以把城市旅行網(wǎng)絡(luò)抽象為一個(gè)帶權(quán)有向圖。給定一個(gè)帶權(quán)有向圖G為二元組G=(V,E),其中V是包含n個(gè)節(jié)點(diǎn)的集合,E是包含h條邊(弧段)的集合,（i, j）是E 中從節(jié)點(diǎn)i 至j 的邊,是邊（i,j）的非負(fù)權(quán)值。設(shè)S,T 分別為 V中的起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn),則最優(yōu)路徑問(wèn)題就是指在帶

8、權(quán)有向圖G中,尋找從指定起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條具有最小權(quán)值總和的路徑。，則最優(yōu)路徑問(wèn)題就是指在帶權(quán)有向圖G中,尋找從指定起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的一條具有最小權(quán)值總和的路徑。在不同需求條件的影響下，城市旅行路線網(wǎng)不僅有道路路線等物理屬性,同時(shí)也具有路線長(zhǎng)度、旅行時(shí)間、車(chē)票價(jià)格等各種其它邏輯屬性，因而改變著旅行的最優(yōu)路線。問(wèn)題（1）中，我們根據(jù)實(shí)際的地理位置經(jīng)緯度，利用幾何知識(shí)計(jì)算出每?jī)蓚€(gè)城市之間的距離，并以距離為權(quán)，進(jìn)而建立模型，求解。設(shè)定出游遍34座城市的最優(yōu)旅行路線。問(wèn)題（2）中，設(shè)定方案針對(duì)各個(gè)城市之間交通條件的不同，考慮實(shí)際情況，通過(guò)互聯(lián)網(wǎng)上的票務(wù)查詢(xún)得到近期城市間的火車(chē)票價(jià)與飛機(jī)票價(jià)，并

9、以?xún)r(jià)格為權(quán)，建立相應(yīng)數(shù)學(xué)模型得到有關(guān)費(fèi)用最低的最優(yōu)旅行路線。問(wèn)題（3）中，在問(wèn)題（1）、（2）分析的基礎(chǔ)之上，建立經(jīng)濟(jì)、省時(shí)又方便的評(píng)價(jià)準(zhǔn)則，提出自己觀點(diǎn)，以此修訂最優(yōu)旅行方案。問(wèn)題（4）中，對(duì)所用算法進(jìn)行復(fù)雜性、可行性及誤差分析討論；問(wèn)題（5）中，關(guān)于旅行商問(wèn)題提出求解所采用的相應(yīng)算法的理解及評(píng)價(jià)。 本問(wèn)題屬于旅行商（TSP）的一類(lèi)問(wèn)題，可以采用模擬退火算法和蟻群算法來(lái)對(duì)數(shù)據(jù)進(jìn)行搜索解決，得到合理的優(yōu)化路線。4.模型的建立與求解4.1 模型的建立與求解根據(jù)問(wèn)題分析，我們首先創(chuàng)建城市旅行網(wǎng)絡(luò)圖，給定加權(quán)圖，其中表示頂點(diǎn)（城市）的集合表示為：。為賦權(quán)邊(表示兩個(gè)城市間的距離)的集合，即兩地間距離

10、（km）。表示為。Hamilton路徑圖可以表示為：；其中 ，且對(duì)，有。記為中所有Hamilton回路的集合，定義；目的是要尋找一條最短的Hamilton回路， 使得。分別利用蟻群算法和模擬退火式算法對(duì)所得數(shù)據(jù)進(jìn)行搜索計(jì)算。4.1.1 城市間距離的估算34個(gè)城市經(jīng)緯度具體數(shù)值（如表1）所示：表1 各個(gè)城市經(jīng)緯度編號(hào)省會(huì)緯度(北緯)經(jīng)度(東經(jīng))1哈爾濱2烏魯木齊3長(zhǎng)春4沈陽(yáng)5呼和浩特6北京7天津8銀川9石家莊10太原11濟(jì)南12西寧13蘭州14鄭州15西安16南京17合肥18上海19武漢20成都21杭州22重慶23拉薩24南昌25長(zhǎng)沙26貴陽(yáng)27福州28昆明29臺(tái)北30廣州31南寧32香港33澳

11、門(mén)34?？赟（南極）首子午線緯線赤道經(jīng)線N(北極)圖1. 地球幾何解析圖首先把地球看成是標(biāo)準(zhǔn)球體，球心為點(diǎn)O，把任意兩個(gè)城市看成是A 、B兩點(diǎn)，則地球上的兩個(gè)點(diǎn)A、 B在赤道面上的投影點(diǎn)分別為、 。假設(shè)地球平均半徑為R，A點(diǎn)北緯，東經(jīng)，B點(diǎn)北緯，東經(jīng)，基于球體幾何知識(shí)因此可以得到：， （1） 投影下來(lái)的 = （2）OZYXBA1BA圖2 地球經(jīng)緯度利用余弦定理可得到： （3） （4）利用勾股定理得到： （5）將（3）、（4）代入（5）式中：= （6）令A(yù)OB為，同樣利用余弦定理可得到： （7）化簡(jiǎn)得： （8）則地球上兩點(diǎn)AB之間距離即AB弧長(zhǎng)為 （9）即為兩地之間的實(shí)際路徑。因此我們根據(jù)表一中

12、所示的各城市經(jīng)緯度經(jīng)過(guò)計(jì)算得到各城市間的距離（詳見(jiàn)附錄1）。4.1.2 蟻群算法建立模型蟻群覓食的過(guò)程與此組合優(yōu)化問(wèn)題的求解相似，找到一條只經(jīng)過(guò)每個(gè)城市一次且回到起點(diǎn)的、最短路徑的回路。設(shè)城市i和j之間的距離為。求解中，假設(shè)蟻群算法中的每只螞蟻是具有下列特征的簡(jiǎn)單智能體。（1）每次周游，每只螞蟻在其經(jīng)過(guò)的支路（i，j）上都留下信息素。（2）螞蟻選擇城市的概率與城市之間的距離和當(dāng)前連接支路上所包含的信息素余量有關(guān)。（3）為了強(qiáng)制螞蟻進(jìn)行合法的周游，知道一次周游完成后，才允許螞蟻游走已訪問(wèn)過(guò)的城市（這可由禁忌表來(lái)控制）。蟻群算法中的基本變量和常數(shù)有：m，蟻群中螞蟻的總數(shù)；n，TSP問(wèn)題中城市的個(gè)數(shù)

13、；為城市i和j之間的距離，其中；，表示t時(shí)刻在路徑（i，j）連線上殘留的信息量。在初始時(shí)刻各條路徑上信息量相等，并設(shè)=const（const為常數(shù)）。 螞蟻k（k=1，2，m ）在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。表示在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率，根據(jù)各條路徑上殘留的信息量及路徑的啟發(fā)信息來(lái)計(jì)算的，如（10）所示。表示螞蟻在選擇路徑時(shí)會(huì)盡量選擇離自己距離較近且信息素濃度較大的方向。= （10） 式中，表示在t時(shí)刻螞蟻k下一步允許選擇的城市（即還沒(méi)有訪問(wèn)的城市）； （k=1，2，m ）表示禁忌表，記錄螞蟻k當(dāng)前已走過(guò)的城市； 信息啟發(fā)式因子，反映了蟻群在運(yùn)動(dòng)過(guò)

14、程中所殘留信息量相對(duì)重要程度； 表示期望啟發(fā)式因子，反應(yīng)了期望值的相對(duì)重要程度； 表示城市i轉(zhuǎn)移到城市j的期望程度，具體計(jì)算公式如下 （11）對(duì)螞蟻k而言，越小，則越大，也就越大。 為了避免殘留信息素過(guò)多而淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)城市的遍歷后，要對(duì)殘留信息素進(jìn)行更新處理。（t+n）時(shí)刻在路徑（i，j）上信息量可按式（3）和式（4）所示的規(guī)則進(jìn)行調(diào)整。 （12） （13） 式中，表示信息素?fù)]發(fā)系數(shù)。模仿人類(lèi)記憶特點(diǎn)，舊的信息將逐步忘卻、削弱。為了防止信息的無(wú)限積累，的取值范圍為0，1），用1表示信息的殘留系數(shù)。 表示本次循環(huán)中路徑（i，j）上的信息量增量，初始時(shí)刻。表示

15、第k只螞蟻在本次循環(huán)中留在路徑（i，j）上的信息量。根據(jù)信息素更新策略 （14）表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。這里的基本蟻群算法具體算法步驟為：第1步：初始化參數(shù)。時(shí)間t=0，循環(huán)次數(shù)，設(shè)置最大循環(huán)次數(shù)，令路徑（i，j）的初始化信息量=const，初始時(shí)刻。第2步：將m只螞蟻隨機(jī)放在n個(gè)城市上。第3步：循環(huán)次數(shù)。第4步：令螞蟻禁忌表索引號(hào)k=1。第5步：k=k+1。 第6步：根據(jù)狀態(tài)轉(zhuǎn)移概率計(jì)算螞蟻選擇城市j的概率，。第7步：選擇最大狀態(tài)轉(zhuǎn)移概率城市，將螞蟻移動(dòng)，把該城市計(jì)入禁忌表中。第8步：若沒(méi)有訪問(wèn)完集合C中的所有城市，即，跳轉(zhuǎn)至第5步；否則，轉(zhuǎn)第9步。第9步：根據(jù)式（13）

16、和式（14）更新每條路徑上的信息量。第10步：若滿(mǎn)足結(jié)束條件，循環(huán)結(jié)束輸出計(jì)算結(jié)果；否則清空禁忌表并跳轉(zhuǎn)到第3步。YNNY開(kāi)始參數(shù)初始化，=0； k=1k=k+1計(jì)算狀態(tài)轉(zhuǎn)移概率，選擇下一個(gè)轉(zhuǎn)移城市修改禁忌表km更新每條路徑上的信息量滿(mǎn)足條件？輸出結(jié)果結(jié)束圖（6） 基本蟻群算法的算法框圖根據(jù)以上算法我們利用matlab軟件編程（程序見(jiàn)附錄5），得到最優(yōu)旅行路徑為哈爾濱長(zhǎng)春沈陽(yáng)天津北京呼和浩特太原石家莊濟(jì)南鄭州西安銀川蘭州西寧烏魯木齊拉薩昆明成都重慶貴陽(yáng)南寧海口廣州澳門(mén)香港臺(tái)北福州南昌長(zhǎng)沙武漢合肥南京杭州上海哈爾濱，旅行路線總長(zhǎng)為1.6013萬(wàn)千米。圖 8 蟻群算法的最優(yōu)路線圖圖 7 蟻群算法的

17、路徑演化過(guò)程圖413模擬退火算法模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其緩慢降溫（即退火），使之達(dá)到能量最低點(diǎn)。反之，如果急速降溫（即淬火）則不能達(dá)到最低點(diǎn)。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而緩慢降溫時(shí)粒子漸趨有序，在每個(gè)溫度上都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為，其中E為溫度T時(shí)的內(nèi)能，e為其改變量，b為Boltzman常數(shù)。應(yīng)用到本問(wèn)題中，優(yōu)化問(wèn)題的一條旅行途徑route及目標(biāo)函數(shù)f（route）分別可以看成物體的一個(gè)狀態(tài)和物體的能量函數(shù)，而其最優(yōu)解就是最低能量狀態(tài)。因而對(duì)應(yīng)的設(shè)定的

18、初始溫度、基于Metropolis準(zhǔn)則的搜索和控制溫度參數(shù)t控制的下降過(guò)程也就相當(dāng)于物理退火過(guò)程的加溫、等溫和冷卻過(guò)程。等溫的過(guò)程中，我們采用Metropolis準(zhǔn)則鄰域搜索移動(dòng)方法，也就是說(shuō)根據(jù)一定概率決定當(dāng)前解是否移向新解。由初始解由初始假設(shè)路徑和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)產(chǎn)生“新解計(jì)算目標(biāo)函數(shù)差接受或舍棄”的迭代，并逐步衰減t的值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于Metropolis的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表控制，包括控制參數(shù)的初值t及其衰減因子，每個(gè)t值時(shí)的迭代次數(shù)L和控制溫度系數(shù)a，因而我們所以我們可以通過(guò)上面的思想寫(xiě)出解決最短路徑的模擬退火算

19、法。算法步驟如下：(1)初始化：初始溫度（充分大），初始解狀態(tài)（隨機(jī)選取一條旅行路線，算出走完此路線的長(zhǎng)度作為目標(biāo)函數(shù)，這是算法迭代的起點(diǎn)），每個(gè)T值的迭代次數(shù)L；(2)對(duì)k=1至k=L最第(3)至第(6)步;(3)產(chǎn)生新解 (利用矩陣翻轉(zhuǎn)來(lái)產(chǎn)生新的路徑)；(4)計(jì)算增量，其中為目標(biāo)函數(shù)； (5)若則接受作為新的當(dāng)前解，否則以概率exp（）接受作為新當(dāng)前解；(6)如果滿(mǎn)足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法；(7)逐漸衰減，因而趨于最低溫度，然后轉(zhuǎn)第2步運(yùn)算。如下圖所示（模擬退火算法框圖）：圖3 模擬退火算法框圖NYNYNN開(kāi)始Exp（

20、）產(chǎn)生is，k=0，初始溫度設(shè)定，L=0產(chǎn)生js，LL+1計(jì)算i=jkk+1,降溫結(jié)束YY圖4 退火算法迭代運(yùn)算圖根據(jù)以上算法我們利用matlab軟件編程（程序見(jiàn)附錄6），得到最優(yōu)旅行路徑為：哈爾濱長(zhǎng)春沈陽(yáng)北京天津濟(jì)南石家莊太原呼和浩特銀川西寧蘭州成都重慶西安鄭州武漢長(zhǎng)沙南昌合肥南京上海杭州福州臺(tái)北香港澳門(mén)廣州海口南寧貴陽(yáng)昆明拉薩烏魯木齊哈爾濱，旅行路線總長(zhǎng)為1.6676萬(wàn)千米。圖5 退火算法求得的最佳路徑圖4.2 模型的建立與求解首先，我們利用火車(chē)票網(wǎng)查詢(xún)到每?jī)蓚€(gè)城市之間的最經(jīng)濟(jì)火車(chē)票矩陣與最經(jīng)濟(jì)的飛機(jī)票矩陣，將二者每個(gè)對(duì)應(yīng)元素取最小組成新的費(fèi)用矩陣。（如附錄2所示）對(duì)問(wèn)題（2）所求的最優(yōu)訂

21、票方案在一定程度上相似于模型的所得的最短路徑，所以我們利用原有的旅行網(wǎng)絡(luò)的城市之間車(chē)費(fèi)的邏輯屬性代替原有的城市之間的路線長(zhǎng)度的物理屬性。所以在城市旅行網(wǎng)絡(luò)加權(quán)圖上，我們將賦權(quán)邊改為表示兩個(gè)城市間的最經(jīng)濟(jì)的旅行方式的費(fèi)用，表示為：； Hamilton路徑可以表示為：；其中，且對(duì)，有。記為中所有Hamilton回路的集合，定義；目的是要尋找一條最短的Hamilton回路， 使得，即可得到旅行價(jià)格最經(jīng)濟(jì)的訂票方案。圖 9 退火算法總費(fèi)用計(jì)算圖在模擬退火算法與蟻群算法的基礎(chǔ)上，我們利用新的矩陣計(jì)算得到最經(jīng)濟(jì)的旅行互聯(lián)網(wǎng)上的訂票方案，即為：哈爾濱1489長(zhǎng)春1416天津1416濟(jì)南1462南京1462上

22、海1374杭州2002福州1216南昌K162合肥D3024武漢臺(tái)北澳門(mén)西寧1282拉薩K918蘭州1043烏魯木齊1043西安2612鄭州T201?？赥201廣州T99香港T98長(zhǎng)沙2514南寧2058昆明1236貴陽(yáng)1248重慶1271成都1718銀川2636呼和浩特2464太原2610石家莊4410北京1138沈陽(yáng)1122哈爾濱，總費(fèi)用為7212元。圖 10 問(wèn)題2中最佳旅行路線圖4.3 模型 的建立與求解我們針對(duì)綜合省錢(qián)、省時(shí)又方便的條件，建立旅行評(píng)價(jià)指標(biāo)。首先我們考慮方便的原則，在通過(guò)互聯(lián)網(wǎng)查詢(xún)每個(gè)車(chē)次航班時(shí)，優(yōu)先考慮直達(dá)火車(chē)與直飛航班，避免在旅途中可能出現(xiàn)的轉(zhuǎn)機(jī)與轉(zhuǎn)車(chē)，在最大限度上

23、確保旅途中的方便性原則。在此基礎(chǔ)上得到，城市之間的費(fèi)用矩陣與旅行時(shí)間矩陣。然后在經(jīng)濟(jì)與省時(shí)的考慮下，我們假設(shè)出旅行指標(biāo)Q=fM+qt （15）其中： f為費(fèi)用啟發(fā)因子，反映了旅行中所花費(fèi)的車(chē)費(fèi)的相對(duì)重要程度； q為時(shí)間啟發(fā)因子，反映了旅行中所花費(fèi)的時(shí)間的相對(duì)重要程度；根據(jù)部分實(shí)際的火車(chē)票的旅行時(shí)間和車(chē)票費(fèi)用，我們得到下表：表 2 部分火車(chē)車(chē)票價(jià)格與行時(shí)對(duì)應(yīng)表車(chē)次發(fā)站到站車(chē)票價(jià)錢(qián)歷時(shí)票價(jià)時(shí)間2008哈爾濱長(zhǎng)春5402：4819.29K339北京沈陽(yáng)北17209：1418.63T164上海蘭州41020：3919.85T253天津鄭州19509：0321.55T118西安南京26312：2421.

24、21由上表大致可以得到f與q比值約為20.0，即在一定程度上一個(gè)小時(shí)與20元是等價(jià)的。因而我們得到旅行評(píng)價(jià)指標(biāo)=M+20t （16） 可理解為對(duì)于A城與B城的一種旅行方案，旅行指標(biāo)越小，對(duì)于周先生來(lái)說(shuō)，就越有價(jià)值，越可能選擇。假設(shè)一個(gè)退休的旅行者，由于收入的制約，旅行費(fèi)用會(huì)相對(duì)重視一點(diǎn)，所以我們對(duì)原有的指標(biāo)進(jìn)行修訂，因而我們?cè)谠械馁M(fèi)用啟發(fā)因子與時(shí)間啟發(fā)因子的基礎(chǔ)上分別乘以0.6與0.4的平衡系數(shù)得到新的費(fèi)用啟發(fā)因子與時(shí)間啟發(fā)因子，最終得到旅行評(píng)價(jià)指標(biāo)QQ=0.6M+8t （17） 在旅行評(píng)價(jià)指標(biāo)的基礎(chǔ)之上，我們將賦權(quán)邊改為表示兩市之間最小的旅行費(fèi)用指標(biāo)，并根據(jù)公式（17）得到指標(biāo)矩陣(見(jiàn)附表

25、3），表示為：； Hamilton路徑可以表示為：；其中，且對(duì)，有。記為中所有Hamilton回路的集合，定義；目的是要尋找一條最短的Hamilton回路， 使得，求解結(jié)果即為旅行經(jīng)濟(jì)、省時(shí)又方便的訂票方案。 優(yōu)化方案為：哈爾濱2096長(zhǎng)春1490天津1394濟(jì)南1085鄭州1150西安1085蘭州T27拉薩T21西寧MU2790澳門(mén)CZ6997臺(tái)北CA4912武漢D3024合肥D3020南京D5401上海D5655杭州D3107福州1216南昌T147長(zhǎng)沙T98香港T99廣州T201?？贕S7441南寧2058昆明1236貴陽(yáng)K9518重慶D5111成都K452烏魯木齊SC4912銀川171

26、8呼和浩特2462太原2610石家莊4408北京D25沈陽(yáng)K19哈爾濱，Q值為6532,總費(fèi)用為8092元。圖 11 問(wèn)題3中優(yōu)化旅行方案圖5模型的復(fù)雜性與可行性分析51 復(fù)雜度分析模型、模型、模型都是在蟻群算法與模擬退火算法的基礎(chǔ)上，全國(guó)34個(gè)城市旅行條件下建立的TSP問(wèn)題的模型。假設(shè)此問(wèn)題通過(guò)枚舉的辦法得到最優(yōu)解，但是將以大量的時(shí)間為代價(jià)，造成理論上的可解而實(shí)際上的不可解。本題中的可行路徑共有條，若以路經(jīng)比較為基本操作，則需次比較才可獲得最優(yōu)解，可能會(huì)需要上百年的時(shí)間。作為比較，以下我們對(duì)蟻群算法與模擬退火算法的復(fù)雜性進(jìn)行分析。5.1.1蟻群算法的復(fù)雜度分析蟻群算法的復(fù)雜度分析是在理論上對(duì)

27、蟻群算法的算法效率的分析。對(duì)于上述模型中的蟻群算法，34個(gè)城市是TSP的規(guī)模，m為螞蟻的數(shù)量，為算法的循環(huán)次數(shù)，從蟻群的算法過(guò)程我們得到各環(huán)節(jié)的時(shí)間復(fù)雜度，如下表所示：Step內(nèi)容T(n)1初始化：set t=0；set =0set = const，=0；2設(shè)置螞蟻禁忌表 set s=0；for k= 1 to m do 置第k個(gè)螞蟻的起始城市到禁忌表O(m)3每只螞蟻單獨(dú)構(gòu)造解循環(huán)計(jì)算直到禁忌表滿(mǎn)set s=s+1；for k= 1 to m do根據(jù)轉(zhuǎn)移概率選擇下一個(gè)城市將城市序號(hào)j加入禁忌表O()4解的評(píng)價(jià)和軌跡更新量的計(jì)算將第k只螞蟻在從禁忌表轉(zhuǎn)移到 計(jì)算第k只螞蟻在本次循環(huán)中的路徑長(zhǎng)

28、度更新最優(yōu)路徑計(jì)算各條路徑的信息數(shù)反饋量O()5信息數(shù)軌跡濃度的更新計(jì)算各條路徑在下一輪循環(huán)前的信息數(shù)強(qiáng)度set t =t+n; set =+1O()6判定是否達(dá)到終止條件如果,且搜索出現(xiàn)停止現(xiàn)象 清空全部禁忌表 返回step2否則 輸出最短路徑結(jié)束O(nm)5.1.2模擬退火算法的復(fù)雜度分析模擬退火算法的復(fù)雜度分析是在理論上對(duì)模擬退火算法的算法效率的分析。對(duì)于上述模型中的模擬退火算法，34個(gè)城市是TSP的規(guī)模,每個(gè)t值時(shí)的迭代次數(shù)L是內(nèi)循環(huán)的循環(huán)次數(shù)，由降溫過(guò)程我們得到控溫循環(huán)次數(shù)，從模擬退火的算法過(guò)程我們得到各環(huán)節(jié)的時(shí)間復(fù)雜度，如下表所示：STEP內(nèi)容T（n）1初始化：設(shè)定初始溫度 ，終止

29、溫度;set k =0 =;O(1)2每個(gè)t值時(shí)的迭代次數(shù)L;for j=1 to L do；O(m)3翻轉(zhuǎn)矩陣得到新的路徑;計(jì)算;若則接受作為新的當(dāng)前解，否則以概率exp（）接受作為新當(dāng)前解；O(L)4判斷是否滿(mǎn)足內(nèi)循環(huán)終止條件L若滿(mǎn)足，則跳出循環(huán)；若不滿(mǎn)足，則回到step2;O()5降溫過(guò)程：=a； k=k+1;O() 6判斷是否達(dá)到終止溫度如果沒(méi)有滿(mǎn)足或搜索沒(méi)有出現(xiàn)停止現(xiàn)象返回step2否則 打印最短路徑 O()5.2 可行性分析旅行路線最優(yōu)化問(wèn)題是一種TSP問(wèn)題，不存在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解。蟻群算法和模擬退火算法是解決組合優(yōu)化問(wèn)題的有效方法，本文分別采用蟻群算法和模擬退火算法來(lái)解決3

30、4個(gè)城市的TSP問(wèn)題。（1）模擬退火算法的可行性模擬退火算法用于解決組合優(yōu)化問(wèn)題的想法，是基于物理中固體的退火過(guò)程與一般組合優(yōu)化問(wèn)題間的相似性。在對(duì)固體物質(zhì)進(jìn)行退火處理時(shí)，通常先將它加溫溶化，使其中的粒子可自由運(yùn)動(dòng)。然后隨著溫度的逐漸下降，粒子也逐漸形成了低能態(tài)的晶格。若在凝結(jié)點(diǎn)附近的溫度下降速度足夠慢，則固體物質(zhì)一定會(huì)形成最低能量的基態(tài)。對(duì)于組合優(yōu)化問(wèn)題來(lái)說(shuō)，它也有這樣類(lèi)似的過(guò)程。組合優(yōu)化問(wèn)題解空間中的每一點(diǎn)都代表一個(gè)解，不同的解有著不同的成本函數(shù)值，所謂優(yōu)化，就是在解空間中尋找成本函數(shù)值最?。ɑ蜃畲螅┑慕?。模擬退火算法是一種通用、高效、健壯、可行的擬物行隨機(jī)近似算法，并且可以叫容易地并行實(shí)

31、現(xiàn)以進(jìn)一步提高運(yùn)行效率，適合求解大規(guī)模組合優(yōu)化問(wèn)題特別是NP完全問(wèn)題（如本文中旅行路線最優(yōu)化問(wèn)題），因此具有很大的實(shí)用價(jià)值。經(jīng)過(guò)計(jì)算可以發(fā)現(xiàn)模擬退火算法在瀕臨算法結(jié)束時(shí)，多次發(fā)現(xiàn)不錯(cuò)的解，又多次接受惡化。所以，降低接受解的惡化的概率或許可以取得更好的解。但是，事實(shí)上也可能因?yàn)樘绲叵萑刖植孔顑?yōu)而取得更壞的解。所以，模擬退火算法在搜索過(guò)程中需要精確調(diào)整接受退化結(jié)果的條件才可能取得較優(yōu)解。（2）蟻群算法的可行性蟻群算法是受自然界中真實(shí)蟻群的集體行為的啟發(fā)而提出的一種基于群體的模擬進(jìn)化算法，屬于隨機(jī)搜索算法。它是一種并行算法，所有螞蟻（ 智能體）獨(dú)立行動(dòng)，沒(méi)有監(jiān)督機(jī)構(gòu)，從而使其避開(kāi)局部最優(yōu)；它是一種

32、協(xié)作算法，每一只螞蟻選擇路徑時(shí)，有較多信息素的路徑被選中的可能性要比較少信息素的路徑大得多，由于采用了正反饋機(jī)制，加快了該算法的收斂速度；它是一種構(gòu)造性的貪婪算法，能在搜索的早期階段找到較好的可接受解；它是一種魯棒算法，因?yàn)橹灰獙?duì)算法作小小的修改，就可以運(yùn)用于別的組合優(yōu)化問(wèn)題。我們充分利用了蟻群搜索食物的過(guò)程與旅行路線最優(yōu)化問(wèn)題之間的相似性，通過(guò)人工模擬蟻群搜索食物的行為（即螞蟻個(gè)體之間通過(guò)間接通訊與相互協(xié)作最終找到從蟻穴到食物源的最短路徑）來(lái)求解TSP問(wèn)題。像螞蟻這類(lèi)群居動(dòng)物，雖然個(gè)體的行為極其簡(jiǎn)單，但由這些簡(jiǎn)單的個(gè)體所組成的蟻群卻表現(xiàn)出極其復(fù)雜的行為特征，能夠完成復(fù)雜的任務(wù)；不僅如此，螞蟻

33、還能夠適應(yīng)環(huán)境的變化，如在蟻群運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)，螞蟻能夠很快地重新找到最優(yōu)路徑。蟻群算法已在組合優(yōu)化、計(jì)算機(jī)網(wǎng)絡(luò)路由、連續(xù)函數(shù)優(yōu)化、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘、電網(wǎng)優(yōu)化等領(lǐng)域取得了突出的成果。6 誤差分析基于蟻群算法和模擬退火算法的模型、模型、模型的誤差主要體現(xiàn)在兩個(gè)方面，一個(gè)是數(shù)據(jù)搜集方面，另一個(gè)是算法程序方面。6.1基于數(shù)據(jù)收集的誤差分析首先在數(shù)據(jù)收集方面，上文中各城市的經(jīng)緯度精確到小數(shù)點(diǎn)后4位，地球半徑取自地球平均半徑，由于地球橢球體的特征和地球表面丘陵和盆地等地貌，估算出的城市之間的距離與實(shí)際距離存在2%的誤差。火車(chē)票數(shù)據(jù)均由相關(guān)火車(chē)票查詢(xún)網(wǎng)站得到，不考慮臨時(shí)變動(dòng)，誤差不會(huì)太大

34、?？紤]到實(shí)際情況中飛機(jī)票存在不可忽略的折扣情況，且隨時(shí)間的變化存在一定的不確定性，因此我們?cè)诳紤]飛機(jī)票時(shí)，根據(jù)近期內(nèi)的票價(jià)波動(dòng)曲線獲得，在最大限度內(nèi)減小誤差。6.2 基于算法程序的誤差分析（1）有關(guān)模擬退火算法的誤差分析1.溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。2.退火速度問(wèn)題模擬退火算法全局搜索性能也與退火速度密切相關(guān)。一般來(lái)說(shuō)，同一溫度下的“充分”搜索（退火）是相當(dāng)必要的，但這需要計(jì)算時(shí)間。3.溫度管理問(wèn)題溫度管理問(wèn)題也是模擬退火算法難以處理的

35、問(wèn)題之一。在實(shí)際應(yīng)用中，由于必須考慮計(jì)算復(fù)雜度的切實(shí)可行性等問(wèn)題，常采用如下所示的降溫方式： 式中為正的略小于1.00的常數(shù)，t為降溫的次數(shù)。因此為保證迭代次數(shù)，減小誤差，我們?nèi)?.99 以下是改變相關(guān)參數(shù)時(shí)收斂性變化的比較： 圖 12 退火算法在不同參數(shù)下比較收斂性對(duì)比（2）有關(guān)蟻群算法的誤差分析蟻群算法中容易出現(xiàn)停滯現(xiàn)象，出現(xiàn)早熟收斂。也就是當(dāng)搜索到一定時(shí)間后，所有螞蟻個(gè)體所發(fā)現(xiàn)的解完全一致，不能對(duì)解進(jìn)行搜索，所以不利于發(fā)現(xiàn)更好的解。由于改進(jìn)了基本螞蟻算法的信息素更新方式，對(duì)最優(yōu)螞蟻經(jīng)過(guò)的路徑的信息素進(jìn)行更新新，加快了算法收斂的速度。7 算法與模型評(píng)價(jià)7.1旅行商問(wèn)題簡(jiǎn)述旅行商問(wèn)題(Tr

36、aveling Salesman Problem,TSP),也稱(chēng)為貨郎擔(dān)問(wèn)題,由愛(ài)爾蘭數(shù)學(xué)家Sir William Rowan Hamilton和英國(guó)數(shù)學(xué)家Thomas Penyngton Kirkman在19世紀(jì)提出的數(shù)學(xué)問(wèn)題，它是指給定n個(gè)城市并給出每?jī)蓚€(gè)城市之間的距離,旅行商必須以最短路徑訪問(wèn)所有的城市一次且僅一次,并回到原出發(fā)地,現(xiàn)已證明它屬于NP難題。歷史上的第一個(gè)正式用來(lái)解決TSP問(wèn)題的算法誕生于1954年，它被用來(lái)計(jì)算49個(gè)城市的TSP問(wèn)題。到現(xiàn)在為止，運(yùn)用目前最先進(jìn)的計(jì)算機(jī)技術(shù)可解決找出游歷24978個(gè)城市的TSP問(wèn)題。由于該問(wèn)題的描述簡(jiǎn)單, 而其實(shí)際模型在印刷電路板的鉆孔路線

37、方案、連鎖店的貨物配送、網(wǎng)絡(luò)布線等優(yōu)化問(wèn)題中又有著廣泛的應(yīng)用, 故長(zhǎng)期以來(lái)一直吸引著國(guó)內(nèi)外許多研究人員進(jìn)行研究, 他們嘗試著用各種算法來(lái)求解TSP問(wèn)題, 歸納起來(lái)有: 近似解法、局部搜索法、神經(jīng)網(wǎng)絡(luò)、遺傳算法、克隆算法、模擬退火算法、混合遺傳算法等。7.2 算法的理解與評(píng)價(jià) 從圖論的角度看，該問(wèn)題實(shí)質(zhì)是在一個(gè)帶權(quán)完全無(wú)向圖中，找一個(gè)權(quán)值最小的Hemilton回路。本文嘗試著采用模擬退火算法和蟻群算法來(lái)求解TSP問(wèn)題。螞蟻算法的生物基礎(chǔ)是生物界中螞蟻的尋食規(guī)律。其優(yōu)點(diǎn)在于：強(qiáng)啟發(fā)式，能在早期的尋優(yōu)中迅速找到合適的解決方案；搜索能力強(qiáng)、魯棒性好，易與其他方法結(jié)合。模擬退火算法的核心思想來(lái)自熱力學(xué)原

38、理，是解決大規(guī)模組合優(yōu)化問(wèn)題的通用、有效的全局優(yōu)化方法。7.2.1 蟻群算法蟻群算法是一種原理相對(duì)簡(jiǎn)單的新興仿生進(jìn)化算法，在眾多領(lǐng)域中已展現(xiàn)出它的特點(diǎn)和魅力，但蟻群算法理論與遺傳算法、禁忌搜索算法等理論相比還遠(yuǎn)不成熟，實(shí)際應(yīng)用也遠(yuǎn)未挖掘出其真正潛力還有許多亟待解決的課題。加強(qiáng)蟻群算法的基礎(chǔ)理論研究，進(jìn)一步發(fā)展新的數(shù)學(xué)分析和建模工具，尤其對(duì)算法的基礎(chǔ)理論研究非常重要，包括對(duì)解決不同優(yōu)化問(wèn)題時(shí)收斂性和收斂速度的估計(jì)、避免陷入局部最優(yōu)值、魯棒性分析以及參數(shù)的設(shè)計(jì)。目前尚未發(fā)現(xiàn)有關(guān)合理選擇螞蟻數(shù)量已經(jīng)算法運(yùn)行時(shí)間數(shù)學(xué)分析的論述?？蓪⑾伻核惴ㄅc其他類(lèi)型方法綜合使用以開(kāi)發(fā)混合優(yōu)化方法，進(jìn)而發(fā)展思想更先進(jìn)、

39、功能更強(qiáng)大、解決更復(fù)雜系統(tǒng)的智能行為。蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題時(shí)具有快速性、分布式和全局優(yōu)化的特征。其中，尋找最優(yōu)解的快速性是通過(guò)信息素的正反饋機(jī)制來(lái)完成的，而其分布式計(jì)算的特征又避免了算法的早熟性收斂。同時(shí)，具有貪婪啟發(fā)式搜索特征的蟻群系統(tǒng)又能在搜索過(guò)程的早期就找到可接受的解。從復(fù)雜系統(tǒng)和復(fù)雜性科學(xué)的角度看，蟻群系統(tǒng)是一個(gè)復(fù)雜系統(tǒng)。蟻群系統(tǒng)尋找蟻穴到食物源最短路徑的過(guò)程，是整個(gè)蟻群之間相互作用、相互影響、相互聯(lián)系、相互協(xié)調(diào)的結(jié)果。蟻群算法本質(zhì)上具有概率搜索的特征。對(duì)于蟻群算法理論問(wèn)題的深入研究，可以為推廣蟻群算法的應(yīng)用領(lǐng)域奠定重要的理論基礎(chǔ)。比如機(jī)器人系統(tǒng)、圖像處理、制造系統(tǒng)、車(chē)輛路徑系統(tǒng)

40、、通信系統(tǒng)等領(lǐng)域。7.2.2 模擬退火算法模擬退火算法的隨機(jī)優(yōu)化思想，算法實(shí)現(xiàn)的質(zhì)量和效率是與城市的坐標(biāo)、城市之間的距離以及城市的個(gè)數(shù)密切相關(guān)的，要根據(jù)具體的情況選擇合適的參數(shù)(初始溫度、溫度迭代參數(shù)、溫度終止條件、內(nèi)層循環(huán)次數(shù)、城市個(gè)數(shù)等)，然后對(duì)參數(shù)進(jìn)行合理的優(yōu)化，才能得到最理想的結(jié)果。可以說(shuō)，這些參數(shù)的設(shè)置才是算法好壞的關(guān)鍵。本文主要是對(duì)模擬退火算法中的幾個(gè)重要參數(shù)做了比較研究，并選擇了經(jīng)典的TSP問(wèn)題作為求解對(duì)象得出了一組比較有效的參數(shù)組合。 大量實(shí)踐表明模擬退火算法非常適合求解組合優(yōu)化問(wèn)題。它在一定程度上解決了旅游商問(wèn)題，值得指出，模擬退火算法以二個(gè)引入注目的特性躋身于眾多優(yōu)化算法之

41、中，并獨(dú)樹(shù)一幟。 （1）模擬退火方法不“貪婪”，它在解優(yōu)化問(wèn)題的過(guò)程中，解點(diǎn)可以在問(wèn)題的局部極小的附近游蕩，正因?yàn)槿绱耍惴ú粫?huì)被容易找到但不能滿(mǎn)足的局部極小點(diǎn)所蒙蔽，從而找到整體極小點(diǎn)。 （3）解點(diǎn)的決定具有邏輯傾向性，當(dāng)控制參數(shù)T值大時(shí)，優(yōu)于新解的當(dāng)前解被新解替代的可能性大，隨著T的減小，這種可能性隨之減小，特別當(dāng)時(shí)，這種可能性趨向于0.模擬退火算法并不完善，雖然它具有較強(qiáng)的局部搜索能力，并能使搜索過(guò)程避免陷入局部最優(yōu)解，但其的運(yùn)行效率不高，如果把模擬退火算法和其他算法融合，將是提高運(yùn)行效率和求解質(zhì)量的有效手段。并且由于它是一種隨機(jī)優(yōu)化近似算法，一般只能求出近似最優(yōu)解，且性能受到所用隨機(jī)數(shù)

42、序列的影響，這一缺點(diǎn)是模擬方式帶來(lái)的，目前尚無(wú)法徹底解決?？傊?，雖然模擬退火算法還不完善，但在無(wú)法得到實(shí)際問(wèn)題精確最優(yōu)解的情況下，無(wú)論從存儲(chǔ)空間還是計(jì)算效率考慮，模擬退火算法都不失為一種優(yōu)越的近似方法，特別是對(duì)解大規(guī)模NP難道問(wèn)題更是如此。在問(wèn)題規(guī)模較小時(shí)，螞蟻算法和模擬退火算法都能取得不錯(cuò)的結(jié)果。在本文34個(gè)城市的TSP問(wèn)題中，模擬退火算法的解的質(zhì)量甚至優(yōu)于螞蟻算法；但是，隨著問(wèn)題規(guī)模的增大，模擬退火算法的解開(kāi)始惡化，這與模擬退火算法參數(shù)的選擇有關(guān)。7.3 模型的評(píng)價(jià)本文分別對(duì)兩個(gè)算法進(jìn)行了編程計(jì)算與比較。計(jì)算所得到的最優(yōu)解能很好的滿(mǎn)足問(wèn)題的需要。對(duì)于周先生的外出旅行提供了良好的參考方案。模

43、型的優(yōu)點(diǎn)：（1） 搜集了大量的數(shù)據(jù)，緊密的與實(shí)際相結(jié)合，得到的方案可行性強(qiáng)，能很好的解決旅行方案的優(yōu)化問(wèn)題。（2） 能較好的解決類(lèi)似的組合優(yōu)化問(wèn)題。（3） 對(duì)模型稍加修改，就可以應(yīng)用于印刷電路板的鉆孔路線方案、連鎖店的貨物配送、網(wǎng)絡(luò)布線等其他問(wèn)題。（4） 綜合采用了蟻群算法與模擬退火算法，并進(jìn)行收斂性與計(jì)算結(jié)果上的比較分析，改進(jìn)了算法的性能，提高了求解精度。模型的缺點(diǎn)：（1） 對(duì)于大規(guī)模優(yōu)化問(wèn)題，算法需要較長(zhǎng)的搜索時(shí)間。（2） 容易出現(xiàn)局部最優(yōu)的情況參考文獻(xiàn)1 韓忠庚.數(shù)學(xué)建模競(jìng)賽.北京:科學(xué)出版社，2007. 2 姜啟源，謝金星，葉俊.北京:高等教育出版社,2005.3 鄭寶東.線性代數(shù)與空

44、間解析幾何.北京:高等教育出版社,2003.4 張志涌，楊祖櫻.matlab教程.北京：北京航空航天大學(xué)出版社,2006. 5 葉其孝.大學(xué)生數(shù)學(xué)建模輔導(dǎo)教材.長(zhǎng)沙：湖南教育出版社，1993.6 韓中庚.實(shí)用運(yùn)籌學(xué).北京：清華大學(xué)出版社，2007.附錄附錄1（34個(gè)城市任意兩地距離km）：哈爾濱烏魯木齊長(zhǎng)春沈陽(yáng)呼和浩特北京哈爾濱03057.659229.2761506.51041323.8811051.705烏魯木齊3057.65902999.5982908.7052001.2152412.133長(zhǎng)春229.27612999.5980278.67291170.237858.3496沈陽(yáng)506.

45、51042908.705278.67290985.7115625.1615呼和浩特1323.8812001.2151170.237985.71150412.3302北京1051.7052412.133858.3496625.1615412.33020天津1074.2482511.585866.8073611.3712511.2822122.4083銀川1856.0181667.0151700.4741502.224532.3225888.861石家莊1319.052337.2191119.416870.9716393.2382270.655太原1453.0942189.8311262.7131

46、024.81334.5909404.3859濟(jì)南1287.0692602.2231067.426794.0775650.8628365.0478西寧2296.181439.5262142.9581942.888973.82881324.883蘭州2200.4961614.6362035.651822.152878.96091198.305鄭州1637.4842441.8711423.7511155.487692.7576622.4047西安1962.1952114.711765.2231514.599763.5625910.4911南京1668.9413007.7321439.6661165.

47、0781165.014905.4264合肥1737.7082901.7921509.0831231.2551112.236898.5974上海1671.8513267.6791446.2511187.5591379.6131068.572武漢1994.2092762.2331768.8131490.4621159.9461055.586成都2573.6012048.3832378.9322128.5321321.851522.558杭州1808.3743228.4781580.7491315.0991398.8251125.893重慶2448.3552289.8182241.631978.64

48、1278.0261402.227拉薩3565.1531596.5673408.63198.0842242.0042573.821南昌2116.1393020.6181887.2781609.8531403.1071251.824長(zhǎng)沙2285.7552843.6512060.0041781.511404.2551338.547貴陽(yáng)2762.72568.6552547.9682276.8761645.5451732.594福州2288.363467.352061.371796.9581789.3661570.582昆明3139.9432494.5082932.2762667.3611944.126

49、2093.541臺(tái)北2350.1513704.8482128.111876.4211978.4091725.226廣州2800.893288.862572.0362294.5671984.5221904.6南寧3037.7413004.8052814.2142536.5592026.2882050.335香港2899.5183556.2922670.3792397.12184.4332064.1澳門(mén)2888.4523528.9542659.2492385.4252163.32046.73?？?225.4533379.6442997.6192719.1342316.4662289.241天津銀川石家莊太原濟(jì)南西寧哈爾濱1074.2481856.0181319.051453.0941287.0692296.18烏魯木齊2511.585