最新蘇北數(shù)學(xué)建模競賽B題解答

1、精品文檔數(shù)學(xué)建模王迪B09010601通信工程鄭佳佳B09010603通信工程孟天舒B09010604通信工程旅游線路的優(yōu)化設(shè)計摘要本題為典型的旅行商問題(TSP ,是組合數(shù)學(xué)中一個古老而又困難的問題，它易于 描述卻難以完全解決，屬于 NP完全問題。對于規(guī)模較小的旅行商問題，可以通過窮舉 得到最優(yōu)解，但隨著問題規(guī)模的增大空間復(fù)雜度急劇增加，需要通過啟發(fā)式算法求解。由意大利學(xué)者M(jìn).Dorigo于1992年首先提出的蟻群系統(tǒng)(AntColonySystem, ACS)是 一種新生的仿生進(jìn)化算法，適用于求解復(fù)雜組合優(yōu)化問題，在解決TSP問題方面取得 了較為理想的效果。在此，我們以改進(jìn)的蟻群算法為基礎(chǔ)

2、建立數(shù)學(xué)模型來設(shè)計這些旅游 者在五一開始的路線，試圖能得到一些合理的結(jié)論。(1) 第一問是典型的費(fèi)用TSP問題。對于此問題我們套用基本蟻群算法，查找到城市坐標(biāo)以及旅游費(fèi)用，并建立求解矩陣。通過MATLAB件的模擬，求出若干優(yōu)化解，取相對最優(yōu)解作為計算結(jié)果。所求得的路線為徐州出發(fā)一一洛陽 市龍門石窟一一西安市秦兵馬俑一一山西祁縣喬家大院一一青島市嶗山一 北京八達(dá)嶺長城江西九江廬山黃山市黃山常州中華恐龍園 舟山市普陀山一一武漢市黃鶴樓一一返回徐州，共計3201元。(2) 第二問為時間TSP問題。由于時間在具體操作上的波動性，根據(jù)數(shù)據(jù)所得結(jié)論將時間的TSP轉(zhuǎn)化為距離TSP問題。求解出的路線為：徐州出

3、發(fā)一一常州中 華恐龍園舟山市普陀山黃山市黃山九江市廬山武漢市黃 鶴樓一一洛陽市龍門石窟一一西安市秦始皇兵馬俑一一祁縣喬家大院一一 北京市八達(dá)嶺長城一一青島市嶗山一一返回徐州，總計用時11天12小時20分。(3) 第三問為有費(fèi)用約束下的TSP問題。對于此問題利用了試探法和最小元素得到近似解，再用基本蟻群算法進(jìn)行優(yōu)化。求解出的路線為：徐州一一西安一一 山西一一武漢一一黃山一一北京一一洛陽一一徐州，所花費(fèi)用1839元，游覽了 5個景點(diǎn)。(4) 第四問是在時間約束條件下的TSP問題。解法與前一問類似，求解出的路線為：徐州一一北京一一洛陽一一西安一一武漢一一祁縣一一常州一一徐州，總時長為4天21小時48

4、分。(5) 第五問尋求綜合因素優(yōu)化的問題，通過計算給出評價模型，將價格和費(fèi)用整合到一個無量綱描述矩陣中。再通過試探法得出最優(yōu)的方案。最佳路線為：徐 州一一北京一一青島一一西安一一祁縣一一武漢一一徐州，總時長 4天21 小時23分，花費(fèi)1823元。聯(lián)系實(shí)際情況可知，結(jié)果是合理可行的。關(guān)鍵詞：旅行商問題(TSP，蟻群算法，動態(tài)分析，試探法精品文檔精品文檔一、問題的重述旅游線路的優(yōu)化設(shè)計隨著人們的生活不斷提高，旅游已成為提高人們生活質(zhì)量的重要活動。江蘇徐州 有一位旅游愛好者打算現(xiàn)在的今年的五月一日早上 8點(diǎn)之后出發(fā)，到全國一些著名景點(diǎn) 旅游，最后回到徐州。由于跟團(tuán)旅游會受到若干限制，他(她)打算自己

5、作為背包客出游。 他預(yù)選了十個省市旅游景點(diǎn)。省市景點(diǎn)名稱在景點(diǎn)的最短停留時間江蘇常州市恐龍園4小時山東青島市嶗山6小時北京八達(dá)嶺長城3小時山西祁縣喬家大院3小時河南洛陽市龍門石窟3小時安徽黃山市黃山7小時湖北武漢市黃鶴樓2小時陜西西安市秦始皇兵馬俑2小時江西九江市廬山7小時浙江舟山市普陀山6小時假設(shè)：(A) 城際交通出行可以乘火車(含高鐵)、長途汽車或飛機(jī)(不允許包車或包機(jī))，并且車 票或機(jī)票可預(yù)訂到。(B) 市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(C) 旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門票 (第一門票)。晚上 20： 00至次日早晨7： 00之間，如果

6、在某地停留超過6小時，必須住宿，住宿費(fèi)用不超 過200元/天。吃飯等其它費(fèi)用60元/天。(D) 假設(shè)景點(diǎn)的開放時間為8:00至18:00。問題：根據(jù)以上要求，針對如下的幾種情況，為該旅游愛好者設(shè)計詳細(xì)的行程表，該行程表應(yīng) 包括具體的交通信息(車次、航班號、起止時間、票價等)、賓館地點(diǎn)和名稱，門票費(fèi)用， 在景點(diǎn)的停留時間等信息。(1) 如果時間不限，游客將十個景點(diǎn)全游覽完，至少需要多少旅游費(fèi)用？請建立相關(guān)數(shù) 學(xué)模型并設(shè)計旅游行程表。(2) 如果旅游費(fèi)用不限，游客將十個景點(diǎn)全游覽完，至少需要多少時間？請建立相關(guān)數(shù) 學(xué)模型并設(shè)計旅游行程表。(3) 如果這位游客準(zhǔn)備2000元旅游費(fèi)用，想盡可能多游覽景

7、點(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è)計旅游行程表。模型假設(shè)與符號說明精品文檔2.1模型的基本假設(shè)精品文檔精品文檔Nmax最大循環(huán)次數(shù)（1）每個景點(diǎn)僅經(jīng)過一次。（2）只考慮問題中提供的11個旅游景點(diǎn)，不考慮其他中轉(zhuǎn)地點(diǎn)作為TSP的需求點(diǎn)（3）為使問題一定程度上簡約化，將城市與路徑抽象成點(diǎn)與直線的圖論問題。在 問題（2）中承認(rèn)旅行中的車旅費(fèi)用以及時間與兩景點(diǎn)之間距離成正比，以距 離的TSP替代時間的

8、TSP不考慮繞路等特殊情況。在建模時認(rèn)為兩地之間往 返的費(fèi)用時間差異可忽略。（4）在求解費(fèi)用最少問題時，模型假設(shè)時認(rèn)為住宿，門票，車旅及餐費(fèi)都必須包 含在內(nèi)。（5）認(rèn)為網(wǎng)上公布的機(jī)票與車票均可以在任意時刻獲得，且班次誤點(diǎn)等特殊情況不 予考慮，忽略轉(zhuǎn)站中的不合理因素。（6）不考慮天氣原因?qū)x擇交通工具的影響。（7）關(guān)于兩地間距離僅作比較參考，一切以路徑為準(zhǔn)。2.2符號說明符號名稱G 賦權(quán)圖矩陣C圖中的元素（景點(diǎn)）n景點(diǎn)的個數(shù)D賦權(quán)圖的描述矩陣T訪問順序集合L最優(yōu)解（最小費(fèi)用或最短路程）dti,ti+i時間t i到t i+1的TSP描述m螞蟻的總數(shù)量k螞蟻的編號b(t)t時刻位于城市i的螞蟻數(shù)目T

9、 j(t)t時刻路徑（i,j ）上的信息量rt時刻C中兩兩景點(diǎn)之間的殘留信息素濃度集合p初始時刻各路徑上的信息素量g(c,L, r) 1尋優(yōu)有向圖tabu k第k只螞蟻的禁忌搜索表pkj (t)螞蟻k在t時刻由i城市轉(zhuǎn)向j城市的轉(zhuǎn)移概率a信息啟發(fā)式因子B期望啟發(fā)式因子n j (t)啟發(fā)函數(shù)p信息素?fù)]發(fā)系數(shù) t kj (t)t時刻k螞蟻在路徑ij上留下的信息素量Q螞蟻攜帶的信息素量Lk本次循環(huán)中第k只螞蟻所走的路程長度Nt所記錄的循環(huán)次數(shù)三模型的建立與求解3.1基本蟻群算法求解權(quán)值不變時單一目標(biāo)值TSP問題的最優(yōu)化模型3.1.1 TSP問題的圖論闡述將旅游景點(diǎn)圖優(yōu)化成完全帶權(quán)圖，問題即可抽象成圖

10、論問題：令賦權(quán)圖為G=(C,L)，其中C=C,C2,C為節(jié)點(diǎn)，表示各個景點(diǎn)的集合；L=Lj|Ci ,Cj_C表示各個景點(diǎn)之間的路徑，每兩個景點(diǎn)間的路徑lj都有相關(guān)的權(quán)值dj與之對應(yīng)， 從而建立起一個D=(dj )矩陣，權(quán)值可以表示距離、費(fèi)用、路徑等。由于題目的相關(guān)要 求可以抽象出一個典型旅行商問題的數(shù)學(xué)模型：pn d tiiti + 1minL二_ 13.1.2基本的蟻群算法模型基本思想：蟻群算法是一種通過模擬自然界螞蟻尋徑的行為的進(jìn)化算法。螞蟻群找 到食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑 時會在路徑上釋放出一種特殊的信息素，當(dāng)它們碰到一個還沒有走過的路口

11、時，就隨機(jī)地挑選一條路徑前行，與此同時釋放出與路線長度有關(guān)的信息素，路徑越長，釋放的激素濃度越低，當(dāng)后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率就會相對較大，這樣形成了一個正反饋。最優(yōu)路徑上的激素濃度越來越大，而其它的路徑上激素濃度卻會隨著時間的流逝而消減。這樣，整個蟻群最終會找出最優(yōu)路徑。用bi(t)表示城市i的螞蟻數(shù)目，ij表示t時段路徑(i，j )上的信息量，n表示 景點(diǎn)的個數(shù)，m為螞蟻的總數(shù)量，則 m 初試時刻，各條路徑上信息量相等，均為 P， ij (0) =P。又因為螞蟻不能重復(fù)經(jīng) 過同一個城市，因此建立禁忌表(或記錄未走過的路徑 Jk) tabu k(k取正整數(shù))來

12、記錄螞 蟻?zhàn)哌^的城市，并隨時間做動態(tài)調(diào)整。被隨機(jī)分散在n個節(jié)點(diǎn)的m只螞蟻同時出發(fā)，按照下面的概率公式逐次訪問各個城 市節(jié)點(diǎn)：螞蟻k以概率Pjk訪問下一個節(jié)點(diǎn)：精品文檔精品文檔精品文檔精品文檔ijij，JkPiJl Jk iJiJ精品文檔精品文檔精品文檔精品文檔0在這里，有iJ表示邊L(i, J)上的信息素強(qiáng)度iJ表示由節(jié)點(diǎn)i到節(jié)點(diǎn)J的啟發(fā)函數(shù)，顯然距離越長期望度越低，所以在此將iJ設(shè)為1/ diJ。隨著時間的推移，可能會出現(xiàn)兩種情況：之前各螞蟻留下的信息素逐漸消失； 經(jīng)過多次循環(huán)后，路徑上的殘留信息素過多，淹沒了期望程度對螞蟻選擇路徑的影響。 為了避免這兩種情況，在每一只螞蟻完成一次循環(huán)后，我

13、們對引入?yún)?shù) 對殘留的信息 素進(jìn)行更新。為信息素的揮發(fā)速率，是在0,1 間取值的可變量，用于控制兩種信息素 的比重。設(shè)經(jīng)過x個時間單位后，螞蟻完成一次循環(huán)，各路徑上的信息素的量根據(jù)以下式 子作出調(diào)整：iJ(t x) (1)ij(t)m kiJiJk 19 ：螞蟻在本次循環(huán)中留在路徑 L(i, J)上的信息素強(qiáng)度。ijk：螞蟻k留在路徑L(i, J)上的信息素強(qiáng)度。當(dāng)蟻群完成了所有的節(jié)點(diǎn)的訪問后，在原路返回的過程中，根據(jù)所得的解的好壞去 修改路徑上的信息素強(qiáng)度，以此來引導(dǎo)其他螞蟻對該路徑的選擇，從而達(dá)到群體協(xié)作的 目的，最后判斷系統(tǒng)是否滿足停止的條件(停止條件可以是最大的迭代次數(shù)，計算機(jī)運(yùn) 行時

14、間，或者是達(dá)到系統(tǒng)所要達(dá)到的數(shù)據(jù)精度等)，如果條件不滿足，則蟻群又重新開 始搜索路徑，建立新的解；否則，系統(tǒng)將退出運(yùn)行，將所得的結(jié)果輸出。從上面可以看 出，蟻群優(yōu)化算法的基本思想就是質(zhì)量越好的解和距離越短的路徑就越能吸引更多的螞 蟻。蟻群正是通過這種反復(fù)記憶和學(xué)習(xí)的過程，得到了最短路徑，即全局最優(yōu)解。我們將各城市的經(jīng)緯度通過球面坐標(biāo)系的轉(zhuǎn)化分別投影到一個二維平面上點(diǎn)的橫縱坐標(biāo)，在求解的時候可直接求出兩地的直線距離，即為diJ3.1.3基本蟻群算法的算法流程在本題中，基本蟻群算法的具體實(shí)現(xiàn)步驟如下：1. 參數(shù)初始化：令 t=0 ；設(shè)置最大循環(huán)次數(shù)N6ax，循環(huán)次數(shù)Nc=0;將m只螞蟻置于n個節(jié)點(diǎn)

15、上，在每個節(jié)點(diǎn)i放置bi(t)只螞蟻; 精品文檔初始化每條邊(i,j)上的信息素量j(O)=c為一個常量，初始時刻j k(0)=0 ;初始化禁忌表tabu k和路徑表Lk。2. 設(shè)置索引號s=1，對k=1mB螞蟻k的起始城市放入禁忌表中，并重復(fù)以下步驟直至 禁忌表填充完整：對k=im利用公式計算轉(zhuǎn)移概率pj，根據(jù)偽隨機(jī)比例規(guī)則選擇下一景點(diǎn)，將螞蟻 k移 動到下一景點(diǎn)j并將其填入禁忌表，同時記錄螞蟻 k的路線，索引號自增。3. 對k=im根據(jù)Lk的記錄計算螞蟻k所走循環(huán)路徑的總長度，找到最佳路線4. 計算每只螞蟻的信息素增量At kij (t)5. 更新每條路徑上的信息素量At kij (t+n

16、)6. 清空禁忌表及路線表。Nc+，若NcvNCax,返回步驟2,否則，循環(huán)結(jié)束。精品文檔精品文檔3.2蟻群算法的模型求解3.2.1問題（1）費(fèi)用TSP問題的求解 精品文檔精品文檔精品文檔根據(jù)蟻群算法的解題思路，編寫 MATLAB?序。將各個景點(diǎn)的經(jīng)緯度坐標(biāo)轉(zhuǎn)化為高斯坐 標(biāo)，便于MATLAB勺作圖。建立文本輸入?yún)?shù)，其中權(quán)值為兩兩景點(diǎn)之間的車費(fèi)，旅游 景點(diǎn)門票，住宿費(fèi)以及餐費(fèi)等。在車費(fèi)的選擇上在兩景點(diǎn)擁有的航班，列車以及長途客 運(yùn)之中選擇費(fèi)用最低的?？紤]到住宿的不確定性，以最壞的情況假設(shè)每天都需要住宿。首先對參數(shù)進(jìn)行初始化。時間t=0，循環(huán)次數(shù)NC=Q最大循環(huán)次數(shù)NCMAX=20O螞蟻所 攜帶

17、的信息素量為100，初始時刻At kj (0)=0，螞蟻數(shù)量m=11景點(diǎn)數(shù)n=11，信息啟 發(fā)式因子為1，期望啟發(fā)式因子為5，信息素?fù)]發(fā)系數(shù)為0.7，程序運(yùn)行5次，取相對最 優(yōu)解。MATLAB!行結(jié)果為：Shortest_Route=11 8 1 6 9 5 3 4 10 7 2Shoetest_Le ngth=750.53 75對運(yùn)行結(jié)果的數(shù)據(jù)進(jìn)行處理，可以得到以下結(jié)論：(1)最省錢的旅行方案為：徐州出發(fā)一一洛陽市龍門石窟一一西安市秦兵馬俑一一山西祁縣喬家大院青島市嶗山北京八達(dá)嶺長城江西九江廬山黃山市黃山常州中華恐龍園舟山市普陀山武漢市黃鶴樓返回徐州,反向亦可。(2)具體行程：時間事件費(fèi)用5

18、.1 13:40-5.119:25從徐州出發(fā)，乘1085普快(硬座)到達(dá) 洛陽34元5.1 19:25-5.28:00入住于洛陽東宣假日酒店198兀+60兀(吃飯等其 他費(fèi)用)5.2 8:00-5.211:00在洛陽市龍門石窟游玩3小時120元5.2 17:55-5.223:06從洛陽出發(fā)，乘1184/1181普快(硬座) 到達(dá)西安28元5.2 23:06-5.308:00入住于西安西安華清豪泰商務(wù)會所130元+60元5.3 08:00-5.310:00在西安市秦始皇兵馬俑游玩2個小時90元5.3 20:52-5.4從西安出發(fā)，乘2670普快（硬座）到達(dá)45元07:45太原5.4 08:30-

19、5.4從太原出發(fā)，乘L7815 （硬座）到達(dá)祁縣13元09:445.4 09:44-5.4在祁縣喬家大院游玩3個小時40元+60元12:445.4 14:55-5.4從祁縣出發(fā)，乘4626次列車（硬座）返7元16:08回太原5.4 21:36-5.5從太原出發(fā)，乘K884/K881 K-快速（硬r 120 元08:45座）到達(dá)青島5.5 08:45-5.5在青島市嶗山游玩6個小時100元+60元14:455.5 20:07-5.6從嶗山出發(fā)，乘T26 T-特快（硬座）到116元05:38達(dá)北京5.6 08:00-5.6在北京八達(dá)嶺長城游玩3個小時45元+60元11:005.6 12:14-5.

20、7從北京出發(fā)，乘坐1453普快（硬座）到145元04:14達(dá)九江5.7 08:00-5.7在九江市廬山游玩7個小時180元+60元15:005.7 19:42-5.7從廬山出發(fā)，乘坐K13/K12 K-快速（硬41元23:07座）到鷹潭5.7 23:11-5.8從鷹潭出發(fā)，乘坐K156 K-快速（硬座）51元04:08到黃山5.8 08:00-5.8在黃山市黃山游玩7個小時230元+60元15:005.8 19:10-5.9從黃山出發(fā)，乘K8420/K8417 K-快速（硬73元04:46座）到常州5.9 08:00-5.9在常州市恐龍園游玩4個小時160元+60元12:005.9 22:30

21、-5.10從常州出發(fā)，乘坐K57/K78 K-快速（硬73元05:19座）到寧波5.10 06:30-5.10從寧波出發(fā)，乘坐大巴+快艇到達(dá)普陀山70元08:405.10 08:40-5.10在舟山市普陀山游玩6個小時160元+60元14:405.10 14:40-5.10從普陀山出發(fā)，乘坐大巴+快艇返回寧波70元16:505.10 21:28-5.11從寧波出發(fā)，乘坐Z32/Z33 Z-直特（硬143元07:16臥）到武昌5.11 08:00-5.11在武漢市黃鶴樓游玩2個小時80元+60元10:005.11 16:54-5.1204:13從漢口出發(fā)，乘坐2614/2615普快（硬座） 返回

22、徐州39元總計：3201元表1問題1的具體行程322問題（2）時間TSP問題的求解在本問題這一經(jīng)典的TSP問題模型中，通過對于模型之中城市的集合 L= Lj Q ,C|二|C, 可以建立一個與之對應(yīng)的描述矩陣 D=（dj）描述。由于問題中的限制條件以及時間的不可控性， 在假設(shè)中選擇使用距離的TSP替代時間的 TSP根據(jù)網(wǎng)絡(luò)上的數(shù)據(jù)可知，若選擇單一交通工具，旅途中的時間與旅途的長度成正 比，而在本題的情況下可以乘坐的航班較少，在不考慮費(fèi)用的情況下，可以近似認(rèn)為選 擇的交通工具只有長途汽車與火車兩種，且不同車種和班次之間的速度差異可以忽略。那么，仍然根據(jù)蟻群算法的解題思路，使用各個城市的經(jīng)緯度，轉(zhuǎn)

23、化為高斯坐標(biāo)進(jìn)行定 位，而兩兩景點(diǎn)之間的有向線段的權(quán)值用城市之間的距離表示，根據(jù)一些既定的班次并 對距離做了調(diào)整（可參見附錄）。在MATLA算法中對參數(shù)初始化后運(yùn)行程序，運(yùn)行 5次得相對最優(yōu)解如下：Shortest_Route=1 2 11 7 10 8 6 9 5 4 3 1Shortest_le ngth=作圖結(jié)果如下:5179圖2 MATLAB運(yùn)行結(jié)果IH對程序運(yùn)行結(jié)果進(jìn)行處理，可以得到以下結(jié)論：（1）按地理經(jīng)緯度考慮，在蟻群算法循環(huán) 200次的結(jié)果下，給旅游者提供以下相對最 優(yōu)的方案：徐州出發(fā)一一常州中華恐龍園一一舟山市普陀山一一黃山市黃山一一 九江市廬山一一武漢市黃鶴樓一一洛陽市龍門

24、石窟一一西安市秦始皇兵馬俑一 祁縣喬家大院北京市八達(dá)嶺長城青島市嶗山返回徐州，反向旅行一樣不再贅述。(2)按照此結(jié)果，畫出地圖上的仿真模擬圖:圖3旅行路線仿真模擬圖(3)根據(jù)原題中的假設(shè)，制定具體的旅游計劃如下:時間事件費(fèi)用5.109:35-5.115:19從徐州出發(fā)，乘K58/K55 (硬座)到達(dá)常州70元5.115:19-5.208:00入住于常州福蘭特連鎖旅店晉陵店189元+60元(吃飯等其他費(fèi)用)5.208:00-5.212:00在常州市恐龍園游玩4小時160元5.214:40-5.216:25從常州出發(fā)，乘東方航空公司 MU5692到達(dá)北京960元5.219:10-5.221:15從

25、北京機(jī)場換乘中國南方航空股份有限公司CZ3185到達(dá)寧波1180 元5.221:15-5.308:00入住于寧波格調(diào)時尚賓館148元5.306:30-5.308:40從寧波出發(fā)，乘坐大巴+快艇到達(dá)普陀山70元5.308:40-5.314:40在舟山市普陀山游玩6個小時200元+60元5.3從普陀山出發(fā)，乘坐大巴+快艇返回寧波70元14:40-5.316:505.316:50-5.409:02入住于寧波格調(diào)時尚賓館148元5.409:02-5.418:25從寧波出發(fā)，乘K8498K-快速（硬座），中轉(zhuǎn)K70/K67K-快速（硬座）到達(dá)黃山92元5.418:25-5.508:00入住黃山宏村清和丹

26、客棧60元5.508:00-5.515:00在黃山市黃山游玩7個小時230元+60元5.518:28-5.603:02從黃山市出發(fā)，乘K70/K67（硬座），中轉(zhuǎn)1586/1587普快（硬座）到達(dá)廬山92元5.608:00-5.615:00在九江市廬山游玩7個小時180元+60元5.619:33-5.621:46從廬山出發(fā)，乘坐D3230 D-動車（二等軟座）到達(dá)漢 口80元5.621:46-5.708:00入住于武漢尚果創(chuàng)意酒店169元5.708:00-5.710:00在武漢市黃鶴樓游玩2個小時80元+60元5.710:10-5.716:35從武漢出發(fā)，乘中國南方航空公司CZ8189中轉(zhuǎn)杭州

27、，轉(zhuǎn)乘G52717到達(dá)洛陽1620 元5.716:35-5.808:00入住于洛陽東宣假日酒店198元5.808:00-5.811:00游玩3個小時在洛陽市龍門石窟120元+60元5.811:01-5.8從洛陽出發(fā)，乘坐K1130/K1131 K-快速（硬座）到 達(dá)西安55元16:055.816:05-5.908:00入住于西安華清豪泰商務(wù)會所130元5.908:00-5.910:00在西安市秦始皇兵馬俑游玩2個小時90元+60元5.910:50-5.912:00從西安出發(fā)，乘坐中國南方航空公司CZ6319到達(dá)太原310元5.912:27-5.913:41從太原出發(fā)，乘坐2602/2603到達(dá)

28、祁縣（硬座）13元5.913:41-5.916:41在祁縣喬家大院游玩3個小時40元+60元5.916:49-5.918:07從祁縣出發(fā)，乘坐L7816 （硬座）到達(dá)太原7元5.918:15-5.919:35從太原出發(fā)，乘坐中國海南航空公司HU737倒達(dá)北京300元5.919:35-5.1008:00入住于北京新宇橋賓館188元5.1008:00-5.1011:00在八達(dá)嶺長城游玩3個小時45元+60元5.1013:45-5.1015:05從北京出發(fā)，乘坐中國國際航空公司CA1575到達(dá)青島651元5.1015:05-5.1108:00入住于青島海利鑫鳳凰山莊180元5.1108:00-5.1

29、114:00在青島市嶗山游玩6小時100元5.1115:25-5.1120:20從青島出發(fā)，乘坐山東航空股份有限公司 SC4823中轉(zhuǎn)徐州，乘坐中國四川航空公司 3U8814到達(dá)徐州1390 元表2問題2的具體行程3.2試探法求解權(quán)值不變時有約束條件 TSP問題的最優(yōu)化模型3.2.1在約束條件下TSP問題的模型建立在問題3、4中增加了 “費(fèi)用在兩千元以內(nèi)”和“時間在5天以內(nèi)”的約束條件，問題轉(zhuǎn)化為求解漢密爾頓圖子集在給定條件下的最優(yōu)解，使得問題復(fù)雜度增加 與無約束條件的單一權(quán)值問題相同，首先建立以圖為基礎(chǔ)的模型。其中：（DllDlnaVf4能1Dnn丿I為加權(quán)描述矩陣；fxll +Mli*xn

30、njX=為決策的0-1矩陣對于（3）（4）問之中對于游覽景點(diǎn)數(shù)最多的要求，0-1規(guī)劃矩陣及其子集規(guī)模龐大，因 此必須具體問題具體分析，結(jié)合本題實(shí)際情況，尋找行之有效的算法。由于約束條件， 應(yīng)該先依據(jù)權(quán)值分配每個景點(diǎn)的優(yōu)先級，再依據(jù)優(yōu)先級對TSP問題進(jìn)行動態(tài)分析，選取優(yōu)先級高的景點(diǎn)試探滿足一定條件之下的最優(yōu)路線，并由蟻群算法得出固定的子集的路徑最優(yōu)解。322模型的求解1問題（3）存在費(fèi)用約束條件下的最優(yōu)解本題先用最小元素法進(jìn)行估計，再由蟻群算法得到最優(yōu)解，并用試探法驗證合理性。（1）改進(jìn)的最小元素法最小元素法的宗旨是每一步都取當(dāng)前的最優(yōu)值。算法步驟為對費(fèi)用矩陣D做n次下列循環(huán)：在D中找到一個最小

31、值Dij，令xij=1:;將D的第i列所有數(shù)據(jù)改為無窮大，如果二n,可將D的i行數(shù)據(jù)全部改為正無窮大。在循環(huán)過程中記錄滿足條件的xij和Xij的個數(shù)。由貪婪法，可得滿足條件的最優(yōu)解為徐州一一北京一一祁縣一一西安一一洛陽一一武漢徐州，最小費(fèi)用為1913元?？梢越普J(rèn)為滿足條件時最多的游覽景點(diǎn)數(shù)為5.由于存在時間上的不確定導(dǎo)致費(fèi)用的波動，將子集的元素個數(shù)從5個可以擴(kuò)大至6個。根據(jù)每個景點(diǎn)的費(fèi)用，為每個景點(diǎn)加權(quán)值，選擇其中權(quán)值最低的5至6個景點(diǎn)，用蟻群算法模擬出最優(yōu)化的解。各個景點(diǎn)的權(quán)值可以簡化為：（2）調(diào)整優(yōu)化調(diào)整優(yōu)化指的是將一個離最優(yōu)解很近的初始解調(diào)整到調(diào)整算法下無法更優(yōu)的程度。調(diào)整法主要是用試

32、探法對子集的個數(shù)進(jìn)行優(yōu)化， 也可以通過對蟻群算法的設(shè)置優(yōu)化圖形的路 線。采用試探法可以列舉出游覽不同個數(shù)個景點(diǎn)時的費(fèi)用變化。確定子集個數(shù)時的算法仍然由蟻群算法實(shí)現(xiàn)。其結(jié)果如下: Shortest_Route二4 1 7 3 6 5 2Shortest_Le ngth二2390x d o圖3 MATLAB運(yùn)行結(jié)果對所得的數(shù)據(jù)進(jìn)行處理，可得以下結(jié)果：（1）具體行程：時間事件費(fèi)用5.1 14:05-5.2:從徐州出發(fā)，乘K1354/K1351 （硬座）到達(dá)02:05常州113元5.208:00-5.2.10:090兀+60兀（吃飯等其0在西安市秦始皇兵馬俑游玩2個小時他費(fèi)用）5.2 20:52-5.

33、3:從西安出發(fā)，乘2670 （硬座）到達(dá)山西祁06:19縣39元5.3 08:00-5.311:00在山西祁縣喬家大院游玩3個小時40元+60元5.3 13:47-5.3從山西出發(fā)，乘K237/K240 （硬座）到達(dá)武21:29漢67元5.3 21:19-5.408:00入住于武漢尚果創(chuàng)意酒店169元5.4 08:00-5.410:00在武漢市黃鶴樓游玩2個小時80元+60元5.4 12:47-5.4從武漢出發(fā)，乘動車D3024/D3021 （二等軟15:02座）到達(dá)合肥112元5.4 15:17-5.4從合肥出發(fā)，乘2025普快（硬座）到達(dá)黃21:10I 山49元5.4 21:10-5.50

34、8:00入住于黃山宏村清和丹客棧60元5.5 08:00-5.515:00在黃山市黃山游玩7個小時230元+60元5.5 15:00-5.609:00入住于黃山宏村清和丹客棧69元5.6 09:21-5.7從黃山出發(fā)，乘K46快車（硬座）至U達(dá)北05:07京182元5.7 08:00-5.711:00在八達(dá)嶺長城游玩3個小時45元+60元5.7 16:55-5.8從北京出發(fā)，乘T231特快列車（硬座）到01:55達(dá)洛陽106元5.6 08:00-5.611:00在洛陽市龍門石窟游玩3個小時120元+60元5.6 12:47-5.6從洛陽出發(fā)，乘1086列普快（硬座）返回18:43徐州34元總計

35、：1839元表3問題3的具體行程2問題（4）存在時間約束條件下的最優(yōu)解本題與問題（3）類似，仍然是先根據(jù)貪婪法求得子集中元素個數(shù)的近似解，依據(jù)加權(quán) 后每個景點(diǎn)的優(yōu)先級篩選優(yōu)先級高的景點(diǎn)。用蟻群算法實(shí)現(xiàn)最優(yōu)解。其結(jié)果如下：圖4 MATLAB運(yùn)行結(jié)果時間事件費(fèi)用5.1 09:35-5.110:45從徐州出發(fā)，乘KN2904航班到達(dá)北京550元5.1 12:00-5.115:00在八達(dá)嶺長城游玩3個小時45兀+60兀（吃飯等其他 費(fèi)用）5.1 19:20-5.121:05從北京出發(fā)，乘MU569到達(dá)洛陽機(jī)場787元5.1 22:00-5.208:00入住于洛陽東宣假日酒店198元5.2 08:00-

36、5.211:00在洛陽市龍門石窟游玩3個小時120元+60元5.2 14:53-5.220:13從洛陽出發(fā)，乘K128/125快車（硬座）到 達(dá)西安55元5.2 21:00-5.3130元08:00入住于西安華清豪泰商務(wù)會所5.3 08:00-5.390元+60元10:00在西安市秦始皇兵馬俑處游玩2個小時5.3 11:50-5.312:55從西安咸陽機(jī)場，乘MF8218航班到達(dá)武漢 天河機(jī)場608元5.3 14:00-5.316:00在武漢市黃鶴樓游玩2個小時90元+60元5.3 22:20-5.323:40從武漢天河機(jī)場出發(fā)，乘MU2364亢班到達(dá) 太原武宿機(jī)場540元5.4 05:00-

37、5.406:08從太原出發(fā)，乘2462/2463普快（硬座） 到達(dá)祁縣7元5.4 08:00-5.411:00在祁縣喬家大院游玩3個小時40元+60元5.4 12:29-5.413:47從祁縣出發(fā)，乘1096普快（硬座）到達(dá)太 原7元5.4 17:53-5.512:58從太原出發(fā)，乘K374/371快車（軟臥）到 達(dá)常州458元5.5 14:00-5.518:00在常州恐龍園游玩3個小時160元+60元5.6 00:09-5.605:48從常州出發(fā)，乘K76/77快車（硬座）返回 徐州70元表4問題4的具體行程3.3求解多目標(biāo)TSP問題3.3.1多目標(biāo)TSP問題的模型建立為綜合衡量費(fèi)用TSP與

38、時間TSP問題，建立以下模型評價：（1）確定多目標(biāo)TSP問題的優(yōu)化模型，本題中只考慮費(fèi)用與時間兩個因素的優(yōu)化；（2） 給定各個目標(biāo)因素的優(yōu)先級。本題中，以費(fèi)用為第一優(yōu)先級，時間為第二優(yōu)先級（3）對給定的指標(biāo)進(jìn)行無量綱化處理，使得各個指標(biāo)具有可比性。 由費(fèi)用和時間兩個描述矩陣，給定無量綱處理為：D =D/dmin其中，D為處理過后的無量綱矩陣，dmin為描述矩陣中的最小元素。（4）對費(fèi)用與時間兩個矩陣，取相同位置坐標(biāo)的無量綱量進(jìn)行整合形成一個新的無量 綱量，定為求解矩陣。（5） 用最小元素法確定在滿足費(fèi)用以及時間同時約束時，有向圖包涵的原圖的子集的 元素個數(shù)。給定各個景點(diǎn)的優(yōu)先級，用試探法選取可

39、能為最優(yōu)的路徑。其中每個景點(diǎn)的權(quán)值為：3.3.2問題（5）多目標(biāo)TSP問題模型求解精品文檔精品文檔精品文檔處理數(shù)據(jù)后用MATLABS行模擬，所得相對最優(yōu)解如下:圖5 MATLAB運(yùn)行結(jié)果具體行程如下:時間事件費(fèi)用5.1 09:35-5.110:45從徐州出發(fā)，乘坐中國聯(lián)合航空公司 KN2904航班到 達(dá)北京550元5.1 10:45-5.113:46在北京八達(dá)嶺長城游玩3個小時45元+60元5.1 22:48-5.207:38從北京出發(fā)，乘坐T25 T-特快（硬座）到達(dá)青島116元5.2 08:00-5.214:00在青島市嶗山游玩6個小時100 元 +60元5.2 15:16-5.305:2

40、8從青島出發(fā)，乘坐1112/1113普快（硬坐）到達(dá)中轉(zhuǎn) 站鄭州123元5.3 06:02-5.312:42從中轉(zhuǎn)站鄭州出發(fā)，乘坐 K1363K-快速（硬坐）到達(dá) 西安73元5.3 12:24-5.314:24在西安市秦始皇兵馬俑游玩2個小時90元+60元5.3 18:20-5.403:32從西安出發(fā)，乘坐T42 T-特快（硬座）到達(dá)太原站103元5.4 05:00-5.406:08從太原出發(fā)，乘2462/2463普快（硬座）到達(dá)祁縣7元5.4 08:00-5.411:00在祁縣喬家大院游玩3小時40+60 元5.4 12:29-5.413:47從祁縣出發(fā)，乘坐1096普快返回太原7元5.4

41、18:01-5.5從太原出發(fā)，乘K520/K521 K-特快（硬坐）到達(dá)武漢150元09:445.5 09:44-5.511:44在武漢市黃鶴樓游玩2個小時80元+60元5.5 18:40-5.604:23從武漢出發(fā)，乘2614/2615普快(硬坐)返回徐州39元總計：1823元表5問題5的具體行程四模型的評價4.1模型的優(yōu)點(diǎn) 算法表示借助了 MATLA語言，分析精度高，節(jié)約時間，簡介形象;(2) 蟻群算法與遺傳算法，F(xiàn)loyd算法相比，準(zhǔn)確度高；(3) 給出的方案具體，詳實(shí)并且可行。4.2模型的缺點(diǎn)(1) 算法具有一定局限性；(2) 未詳細(xì)考慮旅途中的安排與時間的銜接問題；(3) 蟻群算法耗

42、時較長。參考文獻(xiàn)1 徐莉.基于改進(jìn)遺傳算法的多目標(biāo)TSP可題研究D.武漢：武漢理工大學(xué)2 李 聞.蟻群優(yōu)化算法及其應(yīng)用研究D.長沙：湖南大學(xué)，2005.3 朱 杰.蟻群算法解決TSP可題的淺析J.上海：同濟(jì)大學(xué)，2008； 10093044(2008)22- 724-02.4 夏國成，趙佳寶.智能螞蟻算法求解多目標(biāo)TSP可題的改進(jìn)研究.南京：南京大學(xué)， 2006. 游道明，陳堅.用螞蟻算法解決多目標(biāo)TSP可題J.上海,2003(10) 1808 0.6 燕忠，袁春偉.用蟻群優(yōu)化算法求解中國旅行商問題J.南京：東南大學(xué).7 汪林林.對“貨郎擔(dān)問題”的研究.重慶：重慶郵電學(xué)院.8 劉峙麟，李臣，王

43、露.基于層次分析和圖論模型的旅游線路設(shè)計及其評估.南京：南京大學(xué).9 周康，強(qiáng)小利，同小軍，許進(jìn).求解TSP算法.武漢：華中科技大學(xué).10 李敏，吳浪，張開碧.求解旅行商問題的幾種算法的比較研究.重慶：重慶郵電大 學(xué).11 王宇平,李英華.求解TSP勺量子遺傳算法J.計算機(jī)學(xué)報,2007, 30 (5): 7482755.12 馬良，蔣馥多目標(biāo)旅行售貨員問題的螞蟻算法求解系統(tǒng)程理論方法應(yīng)用，1999； 8(4) : 232713 楊忠，鮑明，張阿舟.求解中國旅行商問題的新結(jié)果J. 數(shù)據(jù)采集與處理，1993, 8(3): 177-184.14 唐建清，鄒國霞.基于Floyd算法的旅游路徑智能選擇

44、系統(tǒng).上海：華東師范大學(xué)15 許峰，杜軍平 .改進(jìn)蟻群算法在旅游線路規(guī)劃中的應(yīng)用研究 . 北京：北京郵電大學(xué) 16 楊志江，李國欣，張敏 . 管道訂購與運(yùn)輸問題 . 徐州：中國礦業(yè)大學(xué)附錄1. 基本蟻群算法的MATLA實(shí)現(xiàn)2. m=11;3. Alpha=1;4. Beta=5;5. Rho=0.7;6. NC_max=200;7. Q=100;8. C=load( D:ZB.txt);9. D=load( D:JL.txt);10. n=11;11. Eta=1./D;12. Tau=ones(n,n);13. Tabu=zeros(m,n);14. NC=1;15. R_best=zero

45、s(NC_max,n);16. L_best=inf.*ones(NC_max,1);17. L_ave=zeros(NC_max,1);18. while NC=rand);46.to_visit=J(SeIect(1);47.Tabu(i,j)=to_visit;48.end49.end50.if NC=251.Tabu(1,:)=R_best(NC-1,:);52.end53.%record the best route54.L=zeros(m,1);55.for i=1:m56.R=Tabu(1,:);57.for j=1:(n-1)58.L(i)=L(i)+D(R(j),R(j+1)

46、;59.end60.L(i)=L(i)+D(R(1),R(n);61.end62.L_best(NC)=min(L);63.pos=find(L=L_best(NC);64.R_best(NC,:)=Tabu(pos(1),:);65.L_ave(NC)=mean(L);66.NC=NC+1;67.%refresh68.DeIta_Tau=zeros(n,n);69.for i=1:m;70.for j=1:(n-1);71.DeIta_Tau(Tabu(i,j),Tabu(i,j+1)=DeIta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i)72.end73.DeIta_

47、Tau(Tabu(i,n),Tabu(i,1)=DeIta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);74.end75.Tau=(1-Rho).*Tau+DeIta_Tau;76.%empty tabu77.Tabu=zeros(m,n);78.end精品文檔精品文檔79.Pos=fi nd(L_best=mi n( L_best);80.shortest_Route=R_best(Pos(1),:)81.Shorest_Le ngth=L_best(Pos(1)82.subplot(1,2,1)83.N=le ngth(R);84.scatter(C(:,1),C(:,2);85.hold on86.plot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)87.for ii=2:N88.plot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)89.holdon90.end91.subplot(1,2,2)92.plot(L_best)93.hold on94.plot(L_ave)2.各個景點(diǎn)的高斯坐標(biāo)（3分度）江蘇徐州39518419.343793326.773常州中華恐龍園40495265.04 :3519739.016青島市嶗山40