蟻群算法解決旅游線路問(wèn)題.doc

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

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

3、達(dá)到費(fèi)用最小。結(jié)合實(shí)際，得出最優(yōu)路線：徐州-常州-舟山-黃山-廬山-武漢-洛陽(yáng)-西安-祁縣-北京-青島-徐州，得到行程表和旅游最小費(fèi)用3551元。針對(duì)問(wèn)題（2），采用銜接最得當(dāng)，城市間交通時(shí)間和最少的交通方式，由此找出交通方式的時(shí)間最優(yōu)化配置，進(jìn)而得到最優(yōu)路線：徐州-舟山-黃山-武漢-九江-常州-洛陽(yáng)-西安-祁縣-青島-北京-徐州，并得到行程表和最短旅游時(shí)間9天。針對(duì)問(wèn)題（3）在問(wèn)題（1）的基礎(chǔ)上，對(duì)每個(gè)旅游景區(qū)最短停留時(shí)間，門(mén)票費(fèi)用加權(quán)賦值建立權(quán)向量。運(yùn)用層次分析法，分別求出權(quán)重。根據(jù)權(quán)重，分別求出每個(gè)景點(diǎn)綜合花銷。在2000元旅費(fèi)的限制下，在最短路線上刪除耗時(shí)長(zhǎng)，費(fèi)用高的城市。重新查找刪去

4、城市后城市間的交通費(fèi)，得到旅游行程表和最多旅游景點(diǎn)7個(gè)，旅行線路：徐州-青島-北京-祁縣-西安-洛陽(yáng)-武漢-九江。針對(duì)問(wèn)題（4），在基于問(wèn)題（2）的結(jié)果下，首先，將問(wèn)題（2）中停留時(shí)間（離開(kāi)時(shí)刻與到達(dá)時(shí)刻之差）較長(zhǎng)的城市從路線中刪除，直到滿足小于5天為止。重新查找刪去城市后城市間的交通時(shí)間，對(duì)路線進(jìn)行微調(diào)后，得到旅游行程表和最多旅游景點(diǎn)7個(gè)，分別是：徐州-北京-青島-祁縣-西安-洛陽(yáng)-武漢-常州-徐州。針對(duì)問(wèn)題（5），對(duì)問(wèn)題（3）和問(wèn)題（4）綜合考慮，找出其中時(shí)間相對(duì)長(zhǎng)，旅游費(fèi)用相對(duì)大的城市，進(jìn)行排名并逐個(gè)剔除，并做適當(dāng)調(diào)整。當(dāng)滿足條件時(shí)，得出行程表和費(fèi)時(shí)5天、總費(fèi)用1798元的結(jié)論，具體路線

5、：徐州-北京-青島-祁縣-西安-洛陽(yáng)-常州-徐州。最后，對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了分析，提出改進(jìn)方案。關(guān)鍵字：TSP問(wèn)題 蟻群 lingo 最優(yōu)1 問(wèn)題重述江蘇徐州有一位旅游愛(ài)好者打算現(xiàn)在的今年的五月一日早上8點(diǎn)之后出發(fā)，到全國(guó)一些著名景點(diǎn)旅游，最后回到徐州。他預(yù)選了十個(gè)省市旅游景點(diǎn)，如表1所示。省市景點(diǎn)名稱在景點(diǎn)的最短停留時(shí)間江蘇常州市恐龍園4小時(shí)山東青島市嶗山6小時(shí)北京八達(dá)嶺長(zhǎng)城3小時(shí)山西祁縣喬家大院3小時(shí)河南洛陽(yáng)市龍門(mén)石窟3小時(shí)安徽黃山市黃山7小時(shí)湖北武漢市黃鶴樓2小時(shí)陜西西安市秦始皇兵馬俑2小時(shí)江西九江市廬山7小時(shí)浙江舟山市普陀山6小時(shí)問(wèn)題：根據(jù)以上要求，針對(duì)如下的幾種情況，為該旅游愛(ài)好者設(shè)

6、計(jì)詳細(xì)的行程表，該行程表應(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)用，想盡可能多游

7、覽景點(diǎn)，請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程表。2 問(wèn)題分析2.1 問(wèn)題(1)游客旅游費(fèi)用包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門(mén)票、飲食其他費(fèi)用三個(gè)方面。首先，每個(gè)景點(diǎn)的門(mén)票費(fèi)用與路線選取無(wú)關(guān)。通過(guò)考慮路程最短，可以讓城市之間的交通費(fèi)用達(dá)到最小，同時(shí)可以縮小旅游時(shí)間，由此減少住宿費(fèi)用。旅游路線的費(fèi)用與旅游路線的長(zhǎng)度正相關(guān)，因此選取最短的旅游路線和離每個(gè)景點(diǎn)最近的火車站，可以令交通費(fèi)用最少。其次，在距離景點(diǎn)一定范圍內(nèi)，選取最便宜的旅館入住，盡量減少住宿費(fèi)。且規(guī)定，游客在晚上12點(diǎn)之前不能坐上離開(kāi)城市的交通工具，則住宿，在旅客不能在早上6點(diǎn)之后到達(dá)下一個(gè)城市，則在該城市住宿。因此，運(yùn)用蟻群算法，將旅游路線規(guī)劃為最

8、短；查找離景區(qū)一定距離范圍內(nèi)最便宜的旅館入住，達(dá)到旅游費(fèi)用最少。2.2 問(wèn)題(2)影響旅游時(shí)間的因素主要是城市之間的交通時(shí)間和在城市內(nèi)停留的時(shí)間。要想實(shí)現(xiàn)城市交通時(shí)間最短，可以在最短旅游距離，最快交通工具，可以在對(duì)端旅游路線下，盡可能通過(guò)選擇時(shí)間匹配的快捷交通方式飛機(jī)、高鐵，來(lái)節(jié)約旅行時(shí)間。2.3 問(wèn)題(3)想要限制費(fèi)用在2000元下，進(jìn)可能多的游覽多的景點(diǎn)，首先要去考慮刪去停留時(shí)間長(zhǎng)，門(mén)票費(fèi)用高的城市。因?yàn)橥Ａ魰r(shí)間長(zhǎng)，必定會(huì)增加食宿等費(fèi)用。然而，時(shí)間和旅費(fèi)不能統(tǒng)一進(jìn)行比較，因此，針對(duì)每一個(gè)旅游景區(qū)，以旅游費(fèi)用為目標(biāo)，時(shí)間和門(mén)票費(fèi)用為決策層，利用層次分析法，得到每個(gè)景區(qū)的綜合費(fèi)用，由此排除花銷

9、相對(duì)大的城市。對(duì)于總體而言，旅游時(shí)間影響食宿等費(fèi)用，旅行的路線越長(zhǎng)，則旅游天數(shù)就越多，隨之，食宿費(fèi)用就越多。并且城市之間的交通費(fèi)用也會(huì)增加。因此，仍然采用問(wèn)題（1）中得最短路線，在最短路的基礎(chǔ)上，刪去排除在外的城市。重新查找路線上相鄰城市已經(jīng)改變的城市間的車費(fèi)，對(duì)旅游路線作最后微調(diào)。2.4 問(wèn)題(4)旅游路線、交通方式影響旅游時(shí)間的兩個(gè)重要因素。因此，該問(wèn)題可以基于問(wèn)題（2）在最短路線下最優(yōu)的交通乘坐方式下再根據(jù)時(shí)間限定尋找最多旅游城市。首先，將問(wèn)題（2）中停留時(shí)間（離開(kāi)時(shí)刻-到達(dá)時(shí)刻）較長(zhǎng)的城市從路線中刪除，知道基本滿足時(shí)間5天為止。最后重新查找刪去城市后城市間的交通時(shí)間，對(duì)路線進(jìn)行微調(diào)。2

10、.5 問(wèn)題(5)該題同時(shí)考慮到時(shí)間以及費(fèi)用的限制。可以基于問(wèn)題（3）和問(wèn)題（4），對(duì)問(wèn)題進(jìn)行綜合考慮。因既要時(shí)間在5天內(nèi)，又要旅游費(fèi)用2000元以內(nèi)的條件條設(shè)計(jì)旅游行程，不妨找出其中時(shí)間相對(duì)長(zhǎng)，旅游費(fèi)用相對(duì)大的城市，進(jìn)行排名并逐個(gè)剔除，并做適當(dāng)調(diào)整。知道滿足條件為止。3 模型假設(shè)和符號(hào)說(shuō)明3.1模型的假設(shè)1. 城際交通出行可以乘火車(含高鐵)、長(zhǎng)途汽車或飛機(jī)（不允許包車或包機(jī)），并且車票或機(jī)票可預(yù)訂到。2. 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。3. 旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門(mén)票(第一門(mén)票)。晚上20：00至次日早晨7：00之間，如果在某地停留超

11、過(guò)6小時(shí)，必須住宿，住宿費(fèi)用不超過(guò)200元/天。吃飯等其它費(fèi)用60元/天。4. 假設(shè)景點(diǎn)的開(kāi)放時(shí)間為8:00至18:00。5. 假設(shè)除去乘坐汽車，公交，旅游的時(shí)間，旅游者在每個(gè)城市尋找站點(diǎn)以及吃飯等其他因素引起的逗留時(shí)間算與停留時(shí)間內(nèi)。3.2 符號(hào)說(shuō)明；是的Euclidean距離；表示t時(shí)刻位于元素i的螞蟻數(shù)目；為t時(shí)刻路徑(i, j)上的信息量；表示TSP規(guī)模，即城市數(shù)；為蟻群中螞蟻總數(shù)；，(k=1,2,m)表示第k螞蟻只螞蟻；表示記錄螞蟻k的11階1方正矩陣的禁忌表；表示信息素強(qiáng)度；表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度；4 建模前準(zhǔn)備4.1蟻群算法模型蟻群算法是模擬蟻群在不知道食物在

12、什么地方下需找食物的過(guò)程。當(dāng)有每只螞蟻找到食物時(shí)會(huì)釋放信息素吸引更多螞蟻。當(dāng)一些另辟蹊徑的螞蟻找到更短的路會(huì)逐漸吸引更多螞蟻過(guò)來(lái)，如此往復(fù)，找到最短路。在蟻群需找食物的過(guò)程中，每只螞蟻在只關(guān)心的范圍內(nèi)遍歷空間上的點(diǎn)，要以適當(dāng)?shù)牡匦味惚苷系K，計(jì)算所有可能路徑并比較它們。因此，蟻群算法包括： 范圍，螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。 環(huán)境，螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的

13、信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。 覓食規(guī)則，在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過(guò)去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過(guò)它對(duì)窩的信息素做出反應(yīng)，而對(duì)食物信息素沒(méi)反應(yīng)。 移動(dòng)規(guī)則，每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒(méi)有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過(guò)了哪些點(diǎn)，如

14、果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過(guò)了，它就會(huì)盡量避開(kāi)。避障規(guī)則，如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。播撒信息素規(guī)則，每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來(lái)越少。根據(jù)這幾條規(guī)則，螞蟻之間并沒(méi)有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過(guò)信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來(lái)了。比如，當(dāng)一只螞蟻找到了食物，它并沒(méi)有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過(guò)它附近的時(shí)候，就會(huì)感覺(jué)到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。4.2 數(shù)據(jù)的預(yù)處理 實(shí)現(xiàn)

15、運(yùn)用谷歌地圖將11各城市的經(jīng)緯度坐標(biāo)并對(duì)11個(gè)城市見(jiàn)費(fèi)用最小、耗費(fèi)時(shí)間最短的交通方式和消耗進(jìn)行查閱對(duì)城市間無(wú)交通的進(jìn)行預(yù)處理。5 模型建立與求解5.1.1 模型的建立1) 對(duì)城市建立圖論模型設(shè)：是的Euclidean距離，即G=(C, L)是一個(gè)有向圖，TSP的目的是從有向圖G中尋出長(zhǎng)度最短的Hamilton圈，即一條對(duì)C=c1, c2, , cn中個(gè)元素（城市）訪問(wèn)且只訪問(wèn)一次的最短封閉曲線，存在(n-1)!/2條不同閉合路徑2) 蟻群模型設(shè)表示t時(shí)刻位于元素i的螞蟻數(shù)目，為t時(shí)刻路徑(i, j)上的信息量，n表示TSP規(guī)模，m為蟻群中螞蟻總數(shù)則是t時(shí)刻集合C中元素（城市）兩兩連接上殘留信息

16、量的集合，在初始時(shí)刻各條路徑上的信息量相等，并設(shè) =const, 基本蟻群算法通過(guò)有向圖g=(C, L, )尋找優(yōu)化路線。螞蟻k(k=1,2,m)在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。這里用禁忌表tabuk來(lái)記錄螞蟻k當(dāng)前所走過(guò)的城市，集合隨著tabuk進(jìn)化過(guò)程做動(dòng)態(tài)調(diào)整。在搜索過(guò)程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來(lái)計(jì)算狀態(tài)轉(zhuǎn)移概率。在t時(shí)刻螞蟻k由元素（城市）i轉(zhuǎn)移到元素（城市）j的狀態(tài)轉(zhuǎn)移概率： （1）其中allowedk=C-tabuk表示螞蟻k下一步允許選擇的城市；為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過(guò)程中積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起的作用

17、，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過(guò)的路徑，螞蟻之間的協(xié)作性越強(qiáng)；為期望啟發(fā)式因子，表示能見(jiàn)度的相對(duì)重要性，反映螞蟻在運(yùn)動(dòng)過(guò)程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則:為啟發(fā)函數(shù); 對(duì)螞蟻k而言,越小，則越大，也就越大。顯然，該啟發(fā)函數(shù)表示螞蟻從元素（城市）i轉(zhuǎn)移到元素（城市）j的期望程度。為了避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)城市的遍歷(也即一個(gè)循環(huán)結(jié)束)后，要對(duì)殘留信息進(jìn)行更新處理。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存人大腦的同時(shí)，存儲(chǔ)在大腦中的舊信息隨著時(shí)間的推移逐漸淡化，甚至

18、忘記。由此，t+n時(shí)刻在路徑(i, j)上的信息量可按如下規(guī)則進(jìn)行調(diào)整 (2) (3)上式中，表示信息素?fù)]發(fā)系數(shù)，則1-表示信息素殘留因子，為了防止信息的無(wú)限積累，的取值范圍為0，1),ij(t)表示本次循環(huán)中路徑(i, j)上的信息素增量，初始時(shí)刻表示第k只螞蟻在本次循環(huán)中留在路徑(i, j)上的信息量。 （4）Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。3) TSP的蟻群算法步驟輸出程序計(jì)算結(jié)果按式（2）和式（3）進(jìn)行信息量更新修改禁忌表按式（1）選擇下一元素螞蟻k=1循環(huán)次數(shù)Nc Nc+1初始化開(kāi)始結(jié)束Km滿足結(jié)束條件螞蟻k=k+1

19、NYYN上圖步驟闡述：(1)參數(shù)初始化。令時(shí)間t=0和循環(huán)次數(shù)Nc=0，設(shè)置最大循環(huán)次數(shù)Ncmax, 將m個(gè)螞蟻置于n個(gè)元素(城市)上，令有向圖上每條邊(i, j)的初始化信息量ij(t)=const, 其中const表示常數(shù)，且初始時(shí)刻(0)=0(2)循環(huán)次數(shù)Nc Nc+1。(3)螞蟻的禁忌表索引號(hào)k=1。(4)螞蟻數(shù)目 kk+1。(5)螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式(1)計(jì)算的概率選擇元素(城市) j 并前進(jìn)，jC - tabuk。(6)修改禁忌表指針，即選擇好之后將螞蟻移動(dòng)到新的元素(城市)，并把該元素(城市)移動(dòng)到該螞蟻個(gè)體的禁忌表中。(7)若集合C中元素(城市)未遍歷完，即km，則跳轉(zhuǎn)

20、到第(4)步，否則執(zhí)行第(8)步。(8)根據(jù)公式(2)和式(3)更新每條路徑上的信息量。(9)若滿足結(jié)束條件，即如果循環(huán)次數(shù)Nc Ncmax 則循環(huán)結(jié)束并輸出程序計(jì)算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第(2)步。4）對(duì)約束條件下旅游城市的選擇針對(duì)每個(gè)景點(diǎn)，按對(duì)目標(biāo)旅游費(fèi)用的影響程度，分別對(duì)對(duì)停留時(shí)間和景點(diǎn)門(mén)票分別賦予權(quán)值1和3。建立層次結(jié)構(gòu)模型：旅游費(fèi)用停留時(shí)間門(mén)票費(fèi)用目標(biāo)層準(zhǔn)則層根據(jù)權(quán)，構(gòu)造矩陣B：用matlab計(jì)算得到矩陣最大特征根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.1

21、2 (查表)；一致性比率CR=0/1.12=00.1,通過(guò)一致性檢驗(yàn)。設(shè)停留時(shí)間向量T，賦權(quán)后的值為Y；門(mén)票費(fèi)用為向量P，賦權(quán)后的值為P,則：T=0.3161*T； P=0.9487*P將權(quán)重向量相加T+P=（0，115.1088，77.7932，43.6401，38.8966，114.7926，220.4144，76.5284，86.0154，172.9794，191.6372）。根據(jù)用費(fèi)2000元的限制，刪除向量中值較大的分量所對(duì)應(yīng)的城市：浙江，江西，安徽。重新查找刪去城市后城市間的交通費(fèi)，稍做調(diào)節(jié)，得到行程表。5.2.問(wèn)題的結(jié)論問(wèn)題（1）的結(jié)論根據(jù)所建立的模型，在matlab中設(shè)計(jì)程序并

22、運(yùn)行，得到出游閉合的局部最優(yōu)路線，并經(jīng)過(guò)lingo檢驗(yàn)確保結(jié)論全局最優(yōu)性。得到路線圖:根據(jù)路線圖，查取各城市的鐵路，汽車信息等交通信息，再根據(jù)路線圖、在景點(diǎn)停留時(shí)間和住宿等信息選擇車次，最后給出如下行程安排表：日期時(shí)間交通信息及行程安排住行費(fèi)（元）景點(diǎn)門(mén)票5.18:20-10:49乘坐D5431次火車（徐州常州）14211:00-18：00乘公交去中華恐龍園，游玩中華恐龍園81205.4-5.221：01-10：02乘坐k75/k78次火車（常州-寧波東）13010:02-12：00乘長(zhǎng)途客運(yùn)（寧波-普陀）去普陀山302005.2-5.320:00-6:00在普陀山附近住舟山昌源大酒店1685

23、.3-5.46:10-15:00乘坐長(zhǎng)途客運(yùn)車（定海-沈家門(mén)-杭州客運(yùn)中心-黃山景區(qū)） 18023022:07-5:45乘坐k434/k431（黃山-南昌）705.47：00-8：01乘坐D6342次列車（南昌-九江）428:10-20：00在九江乘公交車去廬山41805.4-5.520:10-6：30在廬山附近住廬山夏都賓館1805.57：00-10：30在九江乘坐長(zhǎng)途客運(yùn)車（九江-武漢）7210：30-14：30在武漢乘公交車去黃鶴樓48015：30-23：44乘坐k864/k861c次列車（武漢-洛陽(yáng)）875.5-5.623：50-8：00在洛陽(yáng)火車站住洛陽(yáng)凌守快捷酒店1008：00-1

24、5：00在洛陽(yáng)乘坐公交車到龍門(mén)石窟41205.617:15-22:47乘坐k134/k131次列車(洛陽(yáng)-西安)335.6-5.722:50-8:00在西安火車站附近住西安陜西出版賓館1588:00-19:00在西安火車站乘坐公交車到秦始皇兵馬俑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

25、:10-18:00乘車到嶗山游玩4805.10-1119:28-04:52乘坐k60/k67次火車（青島-徐州）回到徐州99共10天總計(jì)：（元）17461185最小費(fèi)用統(tǒng)計(jì)如下：項(xiàng)目項(xiàng)目費(fèi)用合計(jì)交通費(fèi)用1766景點(diǎn)門(mén)票1185吃飯費(fèi)用600費(fèi)用總計(jì)（元）3551問(wèn)題(2) 的結(jié)論在各城市間交通時(shí)間為價(jià)值矩陣的程序得出時(shí)間最優(yōu)路線的結(jié)論下，通過(guò)查找個(gè)城市航班、高鐵時(shí)間信息，得到以下行程安排表：旅游行程表：日期時(shí)間信息5.1-5.210：10-11：31乘坐航班（徐州-舟山） FM924212：00-18：00游覽普陀山19：00-8：00在普陀山附近住宿舟山昌源大酒店5.28：55-10：45乘

26、坐航班（舟山-黃山）MU942411：00-18：00游覽黃山22：00-24：00乘坐航班（黃山-武漢） PN63015.39:00-11:00游覽黃鶴樓15：20-20：17乘坐列車（武漢-九江） K7525.4-5.58:00-15:00游覽廬山15：30-18：00乘坐列車（九江-常州） G36719:00-8:00在常州附近住宿常州世紀(jì)大公館5.58：00-13：00常州市恐龍園14：00-20：00乘坐航班（常州-洛陽(yáng)） CA45905.6-5.78：00-12：00游覽龍門(mén)石窟14：31-16：15乘坐航班（洛陽(yáng)-西安 ）CZ336417:00-8:00在西安機(jī)場(chǎng)附近住宿西安申鵬

27、酒店5.78：00-10：00游覽兵馬俑1：50-12：00乘坐列車（西安-太原 ）267012：00-13：00乘坐的士（太原-祁縣） 13：30-16：30游覽喬家大院16：30-17：00乘坐的士（祁縣-太原） 18：15-19：35乘坐航班（太原-北京） HU73715.88：00-11：00游覽八達(dá)嶺長(zhǎng)城16：45-18：00乘坐航班（北京-青海） CA15175.98：00-14：00游覽嶗山16：35-20：37乘坐列車（青島-徐州） G236由表可知，游覽完10個(gè)景區(qū)旅行時(shí)間為最少為9天。問(wèn)題(3) 的結(jié)論 在問(wèn)題（1）的結(jié)論下，剔除部分花費(fèi)較多的旅游城市后經(jīng)過(guò)matlab得出

28、路線吐下：路線圖：在查閱相關(guān)交通信息后得到行程表：日期（月.日）時(shí)間交通信息及行程安排住行費(fèi)用（元）門(mén)票（元）每日花銷（元）5.1-5.222:36-06:53乘坐k68/k69次列車（徐州-青島）99607:00-15:00乘坐公交車到嶗山旅游48017:25-22:36乘坐D60次列車（青島-北京南站）2505.2-5.322:40-7:00在北京南站住北京輕聯(lián)富潤(rùn)飯店60607:00-20:00乘公交車到八達(dá)嶺長(zhǎng)城游玩8455.3-5.423:42-13:41乘坐2602次列車（北京-祁縣）946014:00-18:00乘公交車到喬家大院游玩4405.4-5.520:29-7:05乘坐1

29、095次列車（祁縣-西安）41607:10-12:00乘坐公交車到秦始皇兵馬俑游玩49012:45-14:45乘坐D1012次列車（西安北-洛陽(yáng)龍門(mén)）12014:50-18:00乘坐公交車到龍門(mén)石窟游玩41205.5-5.622:20-7:11乘坐k792/k789次列車（洛陽(yáng)-武漢）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次列車（九江-徐州）回家

30、86即在2000元內(nèi)，最多可以游覽7個(gè)景點(diǎn)。問(wèn)題(4) 的結(jié)論在問(wèn)題（2）在結(jié)論下經(jīng)過(guò)適當(dāng)處理肯程序驗(yàn)證得到以下路線：行程表：日期時(shí)間行程5.19：:4-12.40乘坐火車（徐州-北京） G10413.00-16.00游玩長(zhǎng)城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游

31、玩秦始皇兵馬俑12.05-13.36乘坐列車（西安-洛陽(yáng) ）G20615.00-18.00游玩龍門(mén)石窟22.00-7.11乘坐列車（洛陽(yáng)-武漢） K7925.58.00-11.00游覽黃鶴樓17.39-21.5乘坐（武漢-常州） D307014.00-18.00游玩常州恐龍園20.42-23.01乘坐列車（常州-徐州） D5432問(wèn)題(5) 的結(jié)論利用問(wèn)題3）及問(wèn)題4）的結(jié)論，考慮到時(shí)間以費(fèi)用的限制，首先將費(fèi)用較多的城市：北京，九江，黃山，舟山去除后，得出結(jié)論為：五天可旅游完其余城市且費(fèi)用為1368與費(fèi)用上限2000差距較遠(yuǎn)，故考慮增加一個(gè)城市。因?yàn)榈谝惶斐霭l(fā)時(shí)間為晚上故增加北京，經(jīng)過(guò)計(jì)算后，

32、總費(fèi)用1798元且在第五天夜間回到徐州，滿足題意，得到旅行路線和行程表。路線圖：行程表：日期（月.日時(shí)間交通信息及行程安排交通費(fèi)用及住宿費(fèi)用（元）門(mén)票（元）每日花銷（元）5.18.58-13.55乘坐列車（徐州-北京） D2162156015.00-18.00乘公交到長(zhǎng)城游玩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

33、:29-7:05乘坐1095次列車（祁縣-西安）43607:10-12:00乘坐公交車到秦始皇兵馬俑游玩49012:45-14:45乘坐D1012次列車（西安北-洛陽(yáng)龍門(mén)）12014:50-18:00乘坐公交車到龍門(mén)石窟游玩41205.4-5.521.20-10.17乘坐列車（洛陽(yáng)-常州） K7361296011.30-15.30乘公交車到中華恐龍園游玩412016.28-18.16乘坐列車（常州-徐州） G44回家2146 模型的評(píng)價(jià)及改進(jìn)6.1 問(wèn)題的優(yōu)缺點(diǎn)在解決問(wèn)題（1）中認(rèn)為城市間交通費(fèi)用與距離成正比或?qū)⒊鞘虚g交通時(shí)間、費(fèi)用作為權(quán)向量，運(yùn)用蟻群算法得出局部最優(yōu)值，后經(jīng)lingo遍歷所有

34、可行點(diǎn)后得到全局最優(yōu)解與蟻群算法所得最優(yōu)解相一致，驗(yàn)證了結(jié)論的正確性。 在解決解決問(wèn)題（3）（4）（5）時(shí)運(yùn)用問(wèn)題（1）（2）已有結(jié)論，在特定約束下，將部分耗費(fèi)（時(shí)間、費(fèi)用）較多的城市事先剔除結(jié)合實(shí)際交通狀況做出檢驗(yàn)后迭代最終得出最優(yōu)結(jié)論。在解決約束性條件較多的問(wèn)題時(shí)，將對(duì)結(jié)論影響較大的城市預(yù)先剔除時(shí)具有較強(qiáng)的主觀性。并且在交通工具的選擇時(shí)難免會(huì)有失誤，得到的交通路線可能不是最優(yōu)。參考文獻(xiàn)1黨林立,孫曉群.數(shù)學(xué)建模簡(jiǎn)明教程.西安電子科技大學(xué).20092姜啟源.數(shù)學(xué)模型（第三版）,高等教育出版社.20033唐煥文,賀明峰.數(shù)學(xué)模型引論.高等教育出版社.20034謝金星,薛毅.優(yōu)化建模與LINDO

35、/LINGO軟件.清華大學(xué)出版社，北京20065李志林,歐宜貴.數(shù)學(xué)建模及典型案例分析.化學(xué)工業(yè)出版社,北京20066吳孟達(dá),成禮智.數(shù)學(xué)建模的理論與實(shí)踐.國(guó)防科技大學(xué)出版社.20027徐全智,楊晉浩.數(shù)學(xué)建模入門(mén).電子科技大學(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.4

36、3 11 122.06 30.012. 蟻群算法matlab程序%function = Shortest( )%UNTITLED2 Summary of this function goes here%Detailed explanation goes heretic;%preparation of ant agorithm:path=0; %A=load(city.m); %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

37、 113 218 150 182 172 191 175 214106 140 113 0 94 106 182 281 150 165 322107.5 240 218 94 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

38、 322 160 209 76 246 194 94 0; time=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 9

39、94 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;%Step 1:%for i=1:CityNumber for j=i:CityNumber %solve two points distance distance(i,j)=(A(i,3)-A(j,3)2+(A(i,

40、2)-A(j,3)2)(1/2); if i=j % 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; %eita=eita+eita; % %Step 1_01:%r=1; %Information heuristic factorbeta=2; %Heuristic factor expectedbestpath=1000000000;%rou=0.7;tao=ones(City

41、Number); %initlitalize every paths informationdeta_tao=zeros(CityNumber); %Step 2:%NumMax=1; %The problems to be the number of iterationsAntNumber=50;for i=1:NumMax %Step 2_01: % Info=ones(CityNumber); % for j=1:CityNumber for k=1:CityNumber % Info(j,k)=(tao(j,k)r)*(eita(j,k)beta); %Information between any two cities end end AntPath=ones(AntNumber,CityNumber); % for ant=1:AntNumber % % StartCity=round(1+rand*(CityNumber-1); % City=StartCity; PathLength=0; tabu=ones(CityNumber); %Initialize each element of taboo list p=zeros(CityNumber); % %Step 2_02: % tabu(:,City)=0; % Count=1; % Ant