蟻群算法解決旅游線路問題參考模板

1、2011年第八屆蘇北數(shù)學(xué)建模聯(lián)賽承 諾 書我們仔細(xì)閱讀了第八屆蘇北數(shù)學(xué)建模聯(lián)賽的競賽規(guī)則。我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與本隊(duì)以外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們愿意承擔(dān)由此引起的一切后果。我們的參賽報名號為： 參賽組別（研究生或本科或?qū)？疲罕究平M參賽隊(duì)員 (簽名) ：隊(duì)

2、員1：唐文輝隊(duì)員2：徐玲隊(duì)員3：涂杰 獲獎證書郵寄地址： 1 / 28摘要本文就旅游線路的優(yōu)化設(shè)計問題，根據(jù)旅游者在旅行中的旅游時間，旅游費(fèi)用，旅游地點(diǎn)，交通狀況，住宿等因素的約束，借助圖論，蟻群算法，建立最優(yōu)化數(shù)學(xué)模型。在最短路路線的基礎(chǔ)上，綜合考慮交通，用費(fèi)，時間對問題（2）、（3）、（4）、（5）的影響，給出旅游路線，并用lingo程序?qū)Y(jié)論進(jìn)行檢驗(yàn)，確保結(jié)論的全局最優(yōu)性。針對問題（1），首先，由城市經(jīng)緯度建立城市和城市之間距離的有向圖圖論模型，在建立圖論模型的基礎(chǔ)上，建立在城市之間距離矩陣，采用蟻群算法，得到一條最短閉合路線。根據(jù)最短路線，查找合適時間的車次，距車站或景點(diǎn)一定范圍內(nèi)的最

3、便宜的賓館，達(dá)到費(fèi)用最小。結(jié)合實(shí)際，得出最優(yōu)路線：徐州->常州->舟山->黃山->廬山->武漢->洛陽->西安->祁縣->北京->青島->徐州，得到行程表和旅游最小費(fèi)用3551元。針對問題（2），采用銜接最得當(dāng)，城市間交通時間和最少的交通方式，由此找出交通方式的時間最優(yōu)化配置，進(jìn)而得到最優(yōu)路線：徐州->舟山->黃山->武漢->九江->常州->洛陽->西安->祁縣->青島->北京->徐州，并得到行程表和最短旅游時間9天。針對問題（3）在問題（1）的基礎(chǔ)上，對每個旅游

4、景區(qū)最短停留時間，門票費(fèi)用加權(quán)賦值建立權(quán)向量。運(yùn)用層次分析法，分別求出權(quán)重。根據(jù)權(quán)重，分別求出每個景點(diǎn)綜合花銷。在2000元旅費(fèi)的限制下，在最短路線上刪除耗時長，費(fèi)用高的城市。重新查找刪去城市后城市間的交通費(fèi)，得到旅游行程表和最多旅游景點(diǎn)7個，旅行線路：徐州->青島->北京->祁縣->西安->洛陽->武漢->九江。針對問題（4），在基于問題（2）的結(jié)果下，首先，將問題（2）中停留時間（離開時刻與到達(dá)時刻之差）較長的城市從路線中刪除，直到滿足小于5天為止。重新查找刪去城市后城市間的交通時間，對路線進(jìn)行微調(diào)后，得到旅游行程表和最多旅游景點(diǎn)7個，分別是：徐州

5、->北京->青島->祁縣->西安->洛陽->武漢->常州->徐州。針對問題（5），對問題（3）和問題（4）綜合考慮，找出其中時間相對長，旅游費(fèi)用相對大的城市，進(jìn)行排名并逐個剔除，并做適當(dāng)調(diào)整。當(dāng)滿足條件時，得出行程表和費(fèi)時5天、總費(fèi)用1798元的結(jié)論，具體路線：徐州->北京->青島->祁縣->西安->洛陽->常州->徐州。最后，對模型的優(yōu)缺點(diǎn)進(jìn)行了分析，提出改進(jìn)方案。關(guān)鍵字：TSP問題 蟻群 lingo 最優(yōu)1 問題重述江蘇徐州有一位旅游愛好者打算現(xiàn)在的今年的五月一日早上8點(diǎn)之后出發(fā)，到全國一些著名景點(diǎn)旅

6、游，最后回到徐州。他預(yù)選了十個省市旅游景點(diǎn)，如表1所示。省市景點(diǎn)名稱在景點(diǎn)的最短停留時間江蘇常州市恐龍園4小時山東青島市嶗山6小時北京八達(dá)嶺長城3小時山西祁縣喬家大院3小時河南洛陽市龍門石窟3小時安徽黃山市黃山7小時湖北武漢市黃鶴樓2小時陜西西安市秦始皇兵馬俑2小時江西九江市廬山7小時浙江舟山市普陀山6小時問題：根據(jù)以上要求，針對如下的幾種情況，為該旅游愛好者設(shè)計詳細(xì)的行程表，該行程表應(yīng)包括具體的交通信息(車次、航班號、起止時間、票價等)、賓館地點(diǎn)和名稱，門票費(fèi)用，在景點(diǎn)的停留時間等信息。(1) 如果時間不限，游客將十個景點(diǎn)全游覽完，至少需要多少旅游費(fèi)用？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(

7、2) 如果旅游費(fèi)用不限，游客將十個景點(diǎn)全游覽完，至少需要多少時間？請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(3) 如果這位游客準(zhǔn)備2000元旅游費(fèi)用，想盡可能多游覽景點(diǎn)，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(4) 如果這位游客只有5天的時間，想盡可能多游覽景點(diǎn)，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。(5) 如果這位游客只有5天的時間和2000元的旅游費(fèi)用，想盡可能多游覽景點(diǎn)，請建立相關(guān)數(shù)學(xué)模型并設(shè)計旅游行程表。2 問題分析2.1 問題(1)游客旅游費(fèi)用包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門票、飲食其他費(fèi)用三個方面。首先，每個景點(diǎn)的門票費(fèi)用與路線選取無關(guān)。通過考慮路程最短，可以讓城市之間的交通費(fèi)用達(dá)到最小，同時可

8、以縮小旅游時間，由此減少住宿費(fèi)用。旅游路線的費(fèi)用與旅游路線的長度正相關(guān)，因此選取最短的旅游路線和離每個景點(diǎn)最近的火車站，可以令交通費(fèi)用最少。其次，在距離景點(diǎn)一定范圍內(nèi)，選取最便宜的旅館入住，盡量減少住宿費(fèi)。且規(guī)定，游客在晚上12點(diǎn)之前不能坐上離開城市的交通工具，則住宿，在旅客不能在早上6點(diǎn)之后到達(dá)下一個城市，則在該城市住宿。因此，運(yùn)用蟻群算法，將旅游路線規(guī)劃為最短；查找離景區(qū)一定距離范圍內(nèi)最便宜的旅館入住，達(dá)到旅游費(fèi)用最少。2.2 問題(2)影響旅游時間的因素主要是城市之間的交通時間和在城市內(nèi)停留的時間。要想實(shí)現(xiàn)城市交通時間最短，可以在最短旅游距離，最快交通工具，可以在對端旅游路線下，盡可能通

9、過選擇時間匹配的快捷交通方式飛機(jī)、高鐵，來節(jié)約旅行時間。2.3 問題(3)想要限制費(fèi)用在2000元下，進(jìn)可能多的游覽多的景點(diǎn)，首先要去考慮刪去停留時間長，門票費(fèi)用高的城市。因?yàn)橥Ａ魰r間長，必定會增加食宿等費(fèi)用。然而，時間和旅費(fèi)不能統(tǒng)一進(jìn)行比較，因此，針對每一個旅游景區(qū)，以旅游費(fèi)用為目標(biāo)，時間和門票費(fèi)用為決策層，利用層次分析法，得到每個景區(qū)的綜合費(fèi)用，由此排除花銷相對大的城市。對于總體而言，旅游時間影響食宿等費(fèi)用，旅行的路線越長，則旅游天數(shù)就越多，隨之，食宿費(fèi)用就越多。并且城市之間的交通費(fèi)用也會增加。因此，仍然采用問題（1）中得最短路線，在最短路的基礎(chǔ)上，刪去排除在外的城市。重新查找路線上相鄰城

10、市已經(jīng)改變的城市間的車費(fèi)，對旅游路線作最后微調(diào)。2.4 問題(4)旅游路線、交通方式影響旅游時間的兩個重要因素。因此，該問題可以基于問題（2）在最短路線下最優(yōu)的交通乘坐方式下再根據(jù)時間限定尋找最多旅游城市。首先，將問題（2）中停留時間（離開時刻-到達(dá)時刻）較長的城市從路線中刪除，知道基本滿足時間5天為止。最后重新查找刪去城市后城市間的交通時間，對路線進(jìn)行微調(diào)。2.5 問題(5)該題同時考慮到時間以及費(fèi)用的限制?？梢曰趩栴}（3）和問題（4），對問題進(jìn)行綜合考慮。因既要時間在5天內(nèi)，又要旅游費(fèi)用2000元以內(nèi)的條件條設(shè)計旅游行程，不妨找出其中時間相對長，旅游費(fèi)用相對大的城市，進(jìn)行排名并逐個剔除，

11、并做適當(dāng)調(diào)整。知道滿足條件為止。3 模型假設(shè)和符號說明3.1模型的假設(shè)1. 城際交通出行可以乘火車(含高鐵)、長途汽車或飛機(jī)（不允許包車或包機(jī)），并且車票或機(jī)票可預(yù)訂到。2. 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。3. 旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門票(第一門票)。晚上20：00至次日早晨7：00之間，如果在某地停留超過6小時，必須住宿，住宿費(fèi)用不超過200元/天。吃飯等其它費(fèi)用60元/天。4. 假設(shè)景點(diǎn)的開放時間為8:00至18:00。5. 假設(shè)除去乘坐汽車，公交，旅游的時間，旅游者在每個城市尋找站點(diǎn)以及吃飯等其他因素引起的逗留時間算與停留時間內(nèi)。

12、3.2 符號說明；是的Euclidean距離；表示t時刻位于元素i的螞蟻數(shù)目；為t時刻路徑(i, j)上的信息量；表示TSP規(guī)模，即城市數(shù)；為蟻群中螞蟻總數(shù)；，(k=1,2,m)表示第k螞蟻只螞蟻；表示記錄螞蟻k的11階1方正矩陣的禁忌表；表示信息素強(qiáng)度；表示第k只螞蟻在本次循環(huán)中所走路徑的總長度；4 建模前準(zhǔn)備4.1蟻群算法模型蟻群算法是模擬蟻群在不知道食物在什么地方下需找食物的過程。當(dāng)有每只螞蟻找到食物時會釋放信息素吸引更多螞蟻。當(dāng)一些另辟蹊徑的螞蟻找到更短的路會逐漸吸引更多螞蟻過來，如此往復(fù)，找到最短路。在蟻群需找食物的過程中，每只螞蟻在只關(guān)心的范圍內(nèi)遍歷空間上的點(diǎn)，要以適當(dāng)?shù)牡匦味惚苷?/p>

13、礙，計算所有可能路徑并比較它們。因此，蟻群算法包括： 范圍，螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。 環(huán)境，螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。 覓食規(guī)則，在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地

14、方走，并且每只螞蟻都會以小概率犯錯誤，從而并不是往信息素最多的點(diǎn)移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。 移動規(guī)則，每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時候，螞蟻會按照自己原來運(yùn)動的方向慣性的運(yùn)動下去，并且，在運(yùn)動的方向有一個隨機(jī)的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過了，它就會盡量避開。避障規(guī)則，如果螞蟻要移動的方向有障礙物擋住，它會隨機(jī)的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。播撒信息素規(guī)則，每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并

15、隨著它走遠(yuǎn)的距離，播撒的信息素越來越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實(shí)際上把各個螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。4.2 數(shù)據(jù)的預(yù)處理 實(shí)現(xiàn)運(yùn)用谷歌地圖將11各城市的經(jīng)緯度坐標(biāo)并對11個城市見費(fèi)用最小、耗費(fèi)時間最短的交通方式和消耗進(jìn)行查閱對城市間無交通的進(jìn)行預(yù)處理。5 模型建立與求解5.1.1 模型的建立1) 對城市建立圖論模型設(shè)：是的Euclidean距離，即G=(C,

16、L)是一個有向圖，TSP的目的是從有向圖G中尋出長度最短的Hamilton圈，即一條對C=c1, c2, , cn中個元素（城市）訪問且只訪問一次的最短封閉曲線，存在(n-1)!/2條不同閉合路徑2) 蟻群模型設(shè)表示t時刻位于元素i的螞蟻數(shù)目，為t時刻路徑(i, j)上的信息量，n表示TSP規(guī)模，m為蟻群中螞蟻總數(shù)則是t時刻集合C中元素（城市）兩兩連接上殘留信息量的集合，在初始時刻各條路徑上的信息量相等，并設(shè) =const, 基本蟻群算法通過有向圖g=(C, L, )尋找優(yōu)化路線。螞蟻k(k=1,2,m)在運(yùn)動過程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。這里用禁忌表tabuk來記錄螞蟻k當(dāng)前

17、所走過的城市，集合隨著tabuk進(jìn)化過程做動態(tài)調(diào)整。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計算狀態(tài)轉(zhuǎn)移概率。在t時刻螞蟻k由元素（城市）i轉(zhuǎn)移到元素（城市）j的狀態(tài)轉(zhuǎn)移概率： （1）其中allowedk=C-tabuk表示螞蟻k下一步允許選擇的城市；為信息啟發(fā)式因子，表示軌跡的相對重要性，反映了螞蟻在運(yùn)動過程中積累的信息在螞蟻運(yùn)動時所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)；為期望啟發(fā)式因子，表示能見度的相對重要性，反映螞蟻在運(yùn)動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則:為啟發(fā)函數(shù); 對螞

18、蟻k而言,越小，則越大，也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從元素（城市）i轉(zhuǎn)移到元素（城市）j的期望程度。為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪λ衝個城市的遍歷(也即一個循環(huán)結(jié)束)后，要對殘留信息進(jìn)行更新處理。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存人大腦的同時，存儲在大腦中的舊信息隨著時間的推移逐漸淡化，甚至忘記。由此，t+n時刻在路徑(i, j)上的信息量可按如下規(guī)則進(jìn)行調(diào)整 (2) (3)上式中，表示信息素?fù)]發(fā)系數(shù)，則1-表示信息素殘留因子，為了防止信息的無限積累，的取值范圍為0，1),ij(t)表示本次循環(huán)中路徑(i, j)上的信息素

19、增量，初始時刻表示第k只螞蟻在本次循環(huán)中留在路徑(i, j)上的信息量。 （4）Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。3) TSP的蟻群算法步驟輸出程序計算結(jié)果按式（2）和式（3）進(jìn)行信息量更新修改禁忌表按式（1）選擇下一元素螞蟻k=1循環(huán)次數(shù)Nc Nc+1初始化開始結(jié)束Km滿足結(jié)束條件螞蟻k=k+1NYYN上圖步驟闡述：(1)參數(shù)初始化。令時間t=0和循環(huán)次數(shù)Nc=0，設(shè)置最大循環(huán)次數(shù)Ncmax, 將m個螞蟻置于n個元素(城市)上，令有向圖上每條邊(i, j)的初始化信息量ij(t)=const, 其中const表示常數(shù)，且初始時

20、刻(0)=0(2)循環(huán)次數(shù)Nc Nc+1。(3)螞蟻的禁忌表索引號k=1。(4)螞蟻數(shù)目 kk+1。(5)螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式(1)計算的概率選擇元素(城市) j 并前進(jìn)，jC - tabuk。(6)修改禁忌表指針，即選擇好之后將螞蟻移動到新的元素(城市)，并把該元素(城市)移動到該螞蟻個體的禁忌表中。(7)若集合C中元素(城市)未遍歷完，即k<m，則跳轉(zhuǎn)到第(4)步，否則執(zhí)行第(8)步。(8)根據(jù)公式(2)和式(3)更新每條路徑上的信息量。(9)若滿足結(jié)束條件，即如果循環(huán)次數(shù)Nc Ncmax 則循環(huán)結(jié)束并輸出程序計算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第(2)步。4）對約束條件下旅游城

21、市的選擇針對每個景點(diǎn)，按對目標(biāo)旅游費(fèi)用的影響程度，分別對對停留時間和景點(diǎn)門票分別賦予權(quán)值1和3。建立層次結(jié)構(gòu)模型：旅游費(fèi)用停留時間門票費(fèi)用目標(biāo)層準(zhǔn)則層根據(jù)權(quán)，構(gòu)造矩陣B：用matlab計算得到矩陣最大特征根l=2；n=2權(quán)向量(特征向量)w =（0.3162，0.9487)；一致性指標(biāo)CI=(l-n)/(n-1) CI=(2-2)/4=0；隨機(jī)一致性指標(biāo) ：RI=1.12 (查表)；一致性比率CR=0/1.12=0<0.1,通過一致性檢驗(yàn)。設(shè)停留時間向量T，賦權(quán)后的值為Y；門票費(fèi)用為向量P，賦權(quán)后的值為P,則：T=0.3161*T； P=0.9487*P將權(quán)重向量相加T+P=（0，115

22、.1088，77.7932，43.6401，38.8966，114.7926，220.4144，76.5284，86.0154，172.9794，191.6372）。根據(jù)用費(fèi)2000元的限制，刪除向量中值較大的分量所對應(yīng)的城市：浙江，江西，安徽。重新查找刪去城市后城市間的交通費(fèi)，稍做調(diào)節(jié)，得到行程表。5.2.問題的結(jié)論問題（1）的結(jié)論根據(jù)所建立的模型，在matlab中設(shè)計程序并運(yùn)行，得到出游閉合的局部最優(yōu)路線，并經(jīng)過lingo檢驗(yàn)確保結(jié)論全局最優(yōu)性。得到路線圖:根據(jù)路線圖，查取各城市的鐵路，汽車信息等交通信息，再根據(jù)路線圖、在景點(diǎn)停留時間和住宿等信息選擇車次，最后給出如下行程安排表：日期時間交

23、通信息及行程安排住行費(fèi)（元）景點(diǎn)門票5.18:20-10:49乘坐D5431次火車（徐州常州）14211:00-18：00乘公交去中華恐龍園，游玩中華恐龍園81205.4-5.221：01-10：02乘坐k75/k78次火車（常州-寧波東）13010:02-12：00乘長途客運(yùn)（寧波-普陀）去普陀山302005.2-5.320:00-6:00在普陀山附近住舟山昌源大酒店1685.3-5.46:10-15:00乘坐長途客運(yùn)車（定海-沈家門-杭州客運(yùn)中心-黃山景區(qū)） 18023022:07-5:45乘坐k434/k431（黃山-南昌）705.47：00-8：01乘坐D6342次列車（南昌-九江）4

24、28:10-20：00在九江乘公交車去廬山41805.4-5.520:10-6：30在廬山附近住廬山夏都賓館1805.57：00-10：30在九江乘坐長途客運(yùn)車（九江-武漢）7210：30-14：30在武漢乘公交車去黃鶴樓48015：30-23：44乘坐k864/k861c次列車（武漢-洛陽）875.5-5.623：50-8：00在洛陽火車站住洛陽凌守快捷酒店1008：00-15：00在洛陽乘坐公交車到龍門石窟41205.617:15-22:47乘坐k134/k131次列車(洛陽-西安)335.6-5.722:50-8:00在西安火車站附近住西安陜西出版賓館1588:00-19:00在西安火車

25、站乘坐公交車到秦始皇兵馬俑8905.7-5.820:46-6:19乘坐2670次（西安-祁縣）397:00-18:00在祁縣乘坐公交車到東觀即可到喬家大院4405.8-5.922:05-10:23乘坐1164次（祁縣-北京）火車8110：40-20：00在火車站乘坐公交車到八達(dá)嶺成城游玩4455.9-5.1022:22-10:08乘坐k712/k709(北京西-青島)11310:10-18:00乘車到嶗山游玩4805.10-1119:28-04:52乘坐k60/k67次火車（青島-徐州）回到徐州99共10天總計：（元）17461185最小費(fèi)用統(tǒng)計如下：項(xiàng)目項(xiàng)目費(fèi)用合計交通費(fèi)用1766景點(diǎn)門票1

26、185吃飯費(fèi)用600費(fèi)用總計（元）3551問題(2) 的結(jié)論在各城市間交通時間為價值矩陣的程序得出時間最優(yōu)路線的結(jié)論下，通過查找個城市航班、高鐵時間信息，得到以下行程安排表：旅游行程表：日期時間信息5.1-5.210：10-11：31乘坐航班（徐州-舟山） FM924212：00-18：00游覽普陀山19：00-8：00在普陀山附近住宿舟山昌源大酒店5.28：55-10：45乘坐航班（舟山-黃山）MU942411：00-18：00游覽黃山22：00-24：00乘坐航班（黃山-武漢） PN63015.39:00-11:00游覽黃鶴樓15：20-20：17乘坐列車（武漢-九江） K7525.4-5

27、.58:00-15:00游覽廬山15：30-18：00乘坐列車（九江-常州） G36719:00-8:00在常州附近住宿常州世紀(jì)大公館5.58：00-13：00常州市恐龍園14：00-20：00乘坐航班（常州-洛陽） CA45905.6-5.78：00-12：00游覽龍門石窟14：31-16：15乘坐航班（洛陽-西安 ）CZ336417:00-8:00在西安機(jī)場附近住宿西安申鵬酒店5.78：00-10：00游覽兵馬俑1：50-12：00乘坐列車（西安-太原 ）267012：00-13：00乘坐的士（太原-祁縣） 13：30-16：30游覽喬家大院16：30-17：00乘坐的士（祁縣-太原） 1

28、8：15-19：35乘坐航班（太原-北京） HU73715.88：00-11：00游覽八達(dá)嶺長城16：45-18：00乘坐航班（北京-青海） CA15175.98：00-14：00游覽嶗山16：35-20：37乘坐列車（青島-徐州） G236由表可知，游覽完10個景區(qū)旅行時間為最少為9天。問題(3) 的結(jié)論 在問題（1）的結(jié)論下，剔除部分花費(fèi)較多的旅游城市后經(jīng)過matlab得出路線吐下：路線圖：在查閱相關(guān)交通信息后得到行程表：日期（月.日）時間交通信息及行程安排住行費(fèi)用（元）門票（元）每日花銷（元）5.1-5.222:36-06:53乘坐k68/k69次列車（徐州-青島）99607:00-15

29、:00乘坐公交車到嶗山旅游48017:25-22:36乘坐D60次列車（青島-北京南站）2505.2-5.322:40-7:00在北京南站住北京輕聯(lián)富潤飯店60607:00-20:00乘公交車到八達(dá)嶺長城游玩8455.3-5.423:42-13:41乘坐2602次列車（北京-祁縣）946014:00-18:00乘公交車到喬家大院游玩4405.4-5.520:29-7:05乘坐1095次列車（祁縣-西安）41607:10-12:00乘坐公交車到秦始皇兵馬俑游玩49012:45-14:45乘坐D1012次列車（西安北-洛陽龍門）12014:50-18:00乘坐公交車到龍門石窟游玩41205.5-5

30、.622:20-7:11乘坐k792/k789次列車（洛陽-武漢）87607:30-14:00乘坐公交車到黃鶴樓游玩4805.6-5.715:16-20:17乘坐k752/k753次列車（武漢-九江）516020:30-7;00在九江附近九江玉淵賓館608:00-16:00乘公交車去廬山游玩41805.7-5.817:02-5:23乘坐k612/k613次列車（九江-徐州）回家86即在2000元內(nèi)，最多可以游覽7個景點(diǎn)。問題(4) 的結(jié)論在問題（2）在結(jié)論下經(jīng)過適當(dāng)處理肯程序驗(yàn)證得到以下路線：行程表：日期時間行程5.19：:4-12.40乘坐火車（徐州-北京） G10413.00-16.00游

31、玩長城22.20-3.40乘坐航班（北京-青島） SC46005.28.00-14.0游玩嶗山15.25-17.05乘坐航班（青島-太原） SC460719.14-20.27乘坐列車（太原-祁縣） 109520.30-8.00這住宿祁縣5.38.00-11.00游玩喬家大院20.29-7.05乘坐列車（祁縣-西安） 10957.10-8.00住宿西安5.48.00-10.00游玩秦始皇兵馬俑12.05-13.36乘坐列車（西安-洛陽 ）G20615.00-18.00游玩龍門石窟22.00-7.11乘坐列車（洛陽-武漢） K7925.58.00-11.00游覽黃鶴樓17.39-21.5乘坐（武漢

32、-常州） D307014.00-18.00游玩常州恐龍園20.42-23.01乘坐列車（常州-徐州） D5432問題(5) 的結(jié)論利用問題3）及問題4）的結(jié)論，考慮到時間以費(fèi)用的限制，首先將費(fèi)用較多的城市：北京，九江，黃山，舟山去除后，得出結(jié)論為：五天可旅游完其余城市且費(fèi)用為1368與費(fèi)用上限2000差距較遠(yuǎn)，故考慮增加一個城市。因?yàn)榈谝惶斐霭l(fā)時間為晚上故增加北京，經(jīng)過計算后，總費(fèi)用1798元且在第五天夜間回到徐州，滿足題意，得到旅行路線和行程表。路線圖：行程表：日期（月.日時間交通信息及行程安排交通費(fèi)用及住宿費(fèi)用（元）門票（元）每日花銷（元）5.18.58-13.55乘坐列車（徐州-北京）

33、D2162156015.00-18.00乘公交到長城游玩4455.1-5.222.22-10.08乘坐k712（徐州-青島）1136011:00-17:00乘坐公交車到嶗山旅游4805.2-5.319.38-7:03乘坐列車（青島-太原） K882120607.40-8.47乘坐列車（太原-祁縣） K868 159.00-12.00乘公交車到喬家大院游玩4405.3-5.420:29-7:05乘坐1095次列車（祁縣-西安）43607:10-12:00乘坐公交車到秦始皇兵馬俑游玩49012:45-14:45乘坐D1012次列車（西安北-洛陽龍門）12014:50-18:00乘坐公交車到龍門石窟

34、游玩41205.4-5.521.20-10.17乘坐列車（洛陽-常州） K7361296011.30-15.30乘公交車到中華恐龍園游玩412016.28-18.16乘坐列車（常州-徐州） G44回家2146 模型的評價及改進(jìn)6.1 問題的優(yōu)缺點(diǎn)在解決問題（1）中認(rèn)為城市間交通費(fèi)用與距離成正比或?qū)⒊鞘虚g交通時間、費(fèi)用作為權(quán)向量，運(yùn)用蟻群算法得出局部最優(yōu)值，后經(jīng)lingo遍歷所有可行點(diǎn)后得到全局最優(yōu)解與蟻群算法所得最優(yōu)解相一致，驗(yàn)證了結(jié)論的正確性。 在解決解決問題（3）（4）（5）時運(yùn)用問題（1）（2）已有結(jié)論，在特定約束下，將部分耗費(fèi)（時間、費(fèi)用）較多的城市事先剔除結(jié)合實(shí)際交通狀況做出檢驗(yàn)后迭

35、代最終得出最優(yōu)結(jié)論。在解決約束性條件較多的問題時，將對結(jié)論影響較大的城市預(yù)先剔除時具有較強(qiáng)的主觀性。并且在交通工具的選擇時難免會有失誤，得到的交通路線可能不是最優(yōu)。參考文獻(xiàn)1黨林立,孫曉群.數(shù)學(xué)建模簡明教程.西安電子科技大學(xué).20092姜啟源.數(shù)學(xué)模型（第三版）,高等教育出版社.20033唐煥文,賀明峰.數(shù)學(xué)模型引論.高等教育出版社.20034謝金星,薛毅.優(yōu)化建模與LINDO/LINGO軟件.清華大學(xué)出版社，北京20065李志林,歐宜貴.數(shù)學(xué)建模及典型案例分析.化學(xué)工業(yè)出版社,北京20066吳孟達(dá),成禮智.數(shù)學(xué)建模的理論與實(shí)踐.國防科技大學(xué)出版社.20027徐全智,楊晉浩.數(shù)學(xué)建模入門.電子

36、科技大學(xué)出版社.2003【1】附錄：1. matlab中城市經(jīng)緯度文件 city.m1 117.11 4.15 2 117.11 31.47 3 120.18 36.03 4 116.24 39.55 5 112.51 35.30 6 112.27 34.41 7 118.18 29.43 8 114.17 30.35 9 108.57 34.17 10 115.58 29.43 11 122.06 30.012. 蟻群算法matlab程序%function = Shortest( )%UNTITLED2 Summary of this function goes here%Detailed

37、explanation goes heretic;%preparation of ant agorithm:path=0; %³õʼ»¯×î¶Ì·¾¶µÄ³¤¶ÈA=load('city.m'); %ÔØÈë¸÷¸ö³ÇÊеÄ×

38、ø±êCityNumber=size(A,1); %ËùÇó³ÇÊеĸöÊýmoney=0 70 70 106 107.5 51 76 95 95 50 13070 0 455 140 240 125 73 223 165 87 7370 455 0 113 218 150 182 172 191 175 214106 140 113 0 94 106 182 281 150 165 322107.5 240 218 94

39、 0 52 271 140 41 151 26651 125 150 106 52 0 80 87 49 72 20976 73 182 182 271 80 0 71 170 43 7695 223 172 281 140 87 71 0 137 41 24695 165 191 150 41 49 170 137 0 96 19450 87 175 165 151 72 43 41 96 0 94130 73 214 322 160 209 76 246 194 94 0; time=0 322 320 70 660 280 602 562 521 528 724 322 0 944 85

40、 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

41、 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;%Step 1:%Çó½â³öÈÎÒâÁ½¸ö³ÇÊеľàÀëÒÔ¼°Ã¿¶&#

42、206;·¾¶ÉϵÄÆô·¢ÐÅÏ¢ËØfor i=1:CityNumber for j=i:CityNumber %solve two point's distance distance(i,j)=(A(i,3)-A(j,3)2+(A(i,2)-A(j,3)2)(1/2); if i=j %¼ÆËã¸÷¶ÎÂ

43、83;¾¶µÄÆô·¢ÐÅÏ¢Öµ eita(i,j)=0; else eita(i,j)=1/distance(i,j); %eita(i,j)=1/money(i,j); %eita(i,j)=1/time(i,j); end endenddistance=distance+distance' %ÈÎÒâÁ½¸ö³ÇÊÐ

44、14;®¼äµÄ¾àÀë¾ØÕóeita=eita+eita' %¼ÆËã¸÷¶Î·¾¶µÄÆô·¢ÐÅÏ¢Öµ %Step 1_01:%³õʼ·¾

45、;¶ÉϵÄÐÅÏ¢Á¿ÒÔ¼°×îÓÅ·¾¶³¤¶Èr=1; %Information heuristic factorbeta=2; %Heuristic factor expectedbestpath=1000000000;%³õʼ»¯×î

46、ÓÅ·¾¶±äÁ¿rou=0.7;tao=ones(CityNumber); %initlitalize every path's informationdeta_tao=zeros(CityNumber); %Step 2:%Çó½âËùÓеijÇÊеãÖ®¼äµÄ

47、;Ò»Ìõ×î¶Ì·¾¶NumMax=1; %The problems to be the number of iterationsAntNumber=50;for i=1:NumMax %Step 2_01: %Çó³öÈÎÒâÁ½¸ö³ÇÊеãÖ®¼ä

48、µÄ·¾¶µÄÐÅÏ¢Á¿ Info=ones(CityNumber); %ÿ¶Î¾àÀëÉϵijõʼÐÅÏ¢Á¿ for j=1:CityNumber for k=1:CityNumber %ÇóÎ&

49、#180;×ß¹ýµÄ³ÇÊеÄÐÅÏ¢Á¿µÄºÍ Info(j,k)=(tao(j,k)r)*(eita(j,k)beta); %Information between any two cities end end AntPath=ones(AntNumber,CityNumber); %ÿֻÂìÒ

50、ϵÄ·¾¶µÄ³õʼ»¯ for ant=1:AntNumber %Çó½âÿֻÂìÒϵÄËù×ßµÄÒ»Ìõ·¾¶ %³õÊ

51、¼»¯Ã¿Ö»ÂìÒϵĻù±¾ÐÅÏ¢ StartCity=round(1+rand*(CityNumber-1); %Ëæ»úµÄÑ¡ÔñÂìÒϵÄÒ»¸ö³ö&

52、#183;¢³ÇÊÐ City=StartCity; PathLength=0; tabu=ones(CityNumber); %Initialize each element of taboo list p=zeros(CityNumber); %³õʼÂìÒϵÄÑ¡Ôñ³ÇÊеãµÄ×´Ì

53、¬×ªÒƸÅÂÊ %Step 2_02: %̽Ë÷ÿֻÂìÒÏËù×ß¹ýµÄ·¾¶ tabu(:,City)=0; %Ð޸Ľû¼É±íµ

54、6;Öµ£¬¶ÔÓÚ³ö·¢³ÇÊеã Count=1; %¶ÔÿֻÂìÒÏ×ß¹ýµÄ³ÇÊеãµÄÊýÄ¿µÄ

55、;¼ÆÊý AntPath(ant,Count)=StartCity; %¼Ç¼ÂìÒϵijö·¢³ÇÊеã while Count<CityNumber %Step 2_03: %¸ù¾Ý״̬תÒƸÅ

56、;ÂʵļÆËãµÃµ½ÂìÒϵĵ½´ïµÄÏÂÒ»¸ö³ÇÊе㲢Ð޸Ľû¼É±í ProbNum=ra

57、nd; %Ëæ»úµÄ²úÉúÒ»¸ö¸ÅÂÊÖµ AntTotalInfo=sum(Info,2); %ÿ¸ö³ÇÊе㵽ÆäËûËùÓеãµÄ

58、08;ÅÏ¢Á¿µÄºÍ for k=1:CityNumber %ÇóÈÎÒâÁ½¸ö³ÇÊеÄ״̬תÒƸÅÂÊ prob(City,k)=Info(City,k)/AntTotalInfo(City,1); if ta

59、bu(City,k)=0 %±êÃ÷¸Ã³ÇÊÐÒÑ×ß¹ý prob(City,k)=0; else if k>1 %¸ÅÂʵÄÀÛ¼Ó prob(City,k)=prob(City,k)+prob(City,k-1); end if(prob(City,k)>ProbNum) %Ñ¡Ô

60、41;ÏÂÒ»¸ö³ÇÊÐ PathLength=PathLength+distance(City,k); tabu(:,k)=0; %Ð޸Ľû¼É±í City=k; AntPath(ant,Count+1)=City; for q=1:Count+1 tabu(City,AntPath(ant,q)=0; end Count=Count+1; break; end end %¼&

61、#236;Ñé½û¼É±í end %Çó״̬תÒƸÅÂʵÄÑ­»·½áÊø end %Ò»Ö»ÂìÒϵÄ·¾¶Ò&

62、#209;½áÊø %Step 2_04: %¼Ç¼³öÂìÒÏÅÀÐеÄ×î¶Ì·¾¶ºÍ·¾¶³¤¶È PathLength=PathLength+distance(City,StartCity); if(P

63、athLength<bestpath) %¼Ç¼×î¶Ì·¾¶µÄÂìÒϵÄ·¾¶ bestpath=PathLength; bestroad=AntPath(ant,:); end %Step 2_05: %¼Ç¼ÏÂÿֻÂ&#

64、236;ÒÏÔÚËù×ß·¾¶ÉÏÁôϵÄÐÅÏ¢Á¿ for k=1:CityNumber-1 %ÿֻÂìÒϵÄÐÅÏ¢Á¿µÄ»

65、53;ÀÛ deta_tao(AntPath(ant,k),AntPath(ant,k+1)=deta_tao(AntPath(ant,k),AntPath(ant,k+1)+100/PathLength; end deta_tao(AntPath(ant,k+1),StartCity)=deta_tao(AntPath(ant,k+1),StartCity)+100/PathLength; end %Step 2_06: %ËùÓеÄÂìÒÏ×ß

66、05;êÒ»´Îʱ£¬¶Ô·¾¶ÉϵÄÐÅÏ¢Á¿µÄ¸üРfor Count=1:CityNumber %ÐÅÏ¢Á¿µÄ¸üРfor k=1:CityN

67、umber tao(Count,k)=(1-rou)*tao(Count,k)+deta_tao(Count,k); end endend %Step 3:%»æÖƳö³ÇÊеãÖ®¼äµÄ×î¶Ì·¾¶µÄͼfor i=1:CityNumber %»æÖ

68、98;³ö×î¶Ì·¾¶µÄ·Ïßͼ x(1,i)=A(bestroad(1,i),2); y(1,i)=A(bestroad(1,i),3);endx(1,CityNumber+1)=A(bestroad(1,1),2);y(1,CityNumber+1)=A(bestroad(1,1),3);plot(x(1,1),y(1,1),'b');hold onplot(x,y,'->

69、r');hold onplot(x(1,CityNumber+1),y(1,CityNumber+1),'b'); bestpathbestroad toc;%end3. lingo檢驗(yàn)程序MODEL: SETS:  CITY / 1. 11/: U; ! U( I) = sequence no. of city;  LINK( CITY, CITY):       TIME,  ! The TIME matrix;          X;  ! X( I, J) = 1 if we use link I, J; ENDSETS DATA: