B題最佳旅游路線(xiàn)設(shè)計(jì)

1、2011年第八屆蘇北數(shù)學(xué)建模聯(lián)賽承 諾 書(shū)我們仔細(xì)閱讀了第八屆蘇北數(shù)學(xué)建模聯(lián)賽的競(jìng)賽規(guī)則。我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話(huà)、電子郵件、網(wǎng)上咨詢(xún)等）與本隊(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)為： 2795 參賽組別：本科參賽隊(duì)員 (簽名) ：隊(duì)員1：隊(duì)員2：

2、隊(duì)員3：2011年第八屆蘇北數(shù)學(xué)建模聯(lián)賽編 號(hào) 專(zhuān) 用 頁(yè)參賽隊(duì)伍的參賽號(hào)碼：競(jìng)賽統(tǒng)一編號(hào)（由競(jìng)賽組委會(huì)送至評(píng)委團(tuán)前編號(hào)）：競(jìng)賽評(píng)閱編號(hào)（由競(jìng)賽評(píng)委團(tuán)評(píng)閱前進(jìn)行編號(hào)）：2011年第八屆蘇北數(shù)學(xué)建模聯(lián)賽題 目 旅游線(xiàn)路的優(yōu)化設(shè)計(jì) 摘要隨著我國(guó)全面建設(shè)小康社會(huì)的推進(jìn)，人民的生活質(zhì)量不斷提高，旅行游覽活動(dòng)作為一種新型的高級(jí)社會(huì)消費(fèi)形式逐步受到人們的親睞。旅游作為一種經(jīng)濟(jì)活動(dòng)，游客如何在時(shí)間和費(fèi)用有限的情況下最大程度的享受旅游的樂(lè)趣顯得尤其重要。本文從實(shí)際情況出發(fā)，建立了離散型目標(biāo)優(yōu)化模型和動(dòng)態(tài)規(guī)劃模型，對(duì)模型進(jìn)行了全方面的論述，并針對(duì)本題不同的要求設(shè)計(jì)出相應(yīng)的旅游行程表。建模過(guò)程中，首先用科學(xué)分析的

3、方法，確定主要因素并對(duì)其作數(shù)學(xué)抽象，再針對(duì)各因素綜合運(yùn)用多種數(shù)學(xué)方法進(jìn)行分析求解。第一，我們用主要目標(biāo)法建立了“離散型單目標(biāo)優(yōu)化模型”，并分別確定了五個(gè)問(wèn)題的目標(biāo)函數(shù)以及約束條件；第二，我們將旅游景點(diǎn)看作地圖中的點(diǎn)，利用圖論中著名的哈密頓回路問(wèn)題和順序遞推的方法建立了“動(dòng)態(tài)優(yōu)化模型”；第三，通過(guò)查詢(xún)數(shù)據(jù)，并利用數(shù)理統(tǒng)計(jì)的方法求解模型中的參數(shù)，從而得出一個(gè)與實(shí)際接近的完整數(shù)學(xué)模型。求解問(wèn)題過(guò)程中，首先把路途時(shí)間（路費(fèi)）、景點(diǎn)停留時(shí)間（門(mén)票）、住宿時(shí)間（住宿費(fèi)用）和其它時(shí)間（其它費(fèi)用）綜合考慮，借鑒歷史上著名的貨郎擔(dān)問(wèn)題的解法巧妙的將路程優(yōu)化問(wèn)題轉(zhuǎn)化旅游時(shí)間和旅游費(fèi)用的優(yōu)化問(wèn)題，在利用“Floyd

4、算法”時(shí)分別將旅游時(shí)間和旅游費(fèi)用作為權(quán)成功解決問(wèn)題一與問(wèn)題二。然后采用“蟻群算法”在景點(diǎn)個(gè)數(shù)不確定的條件下求解出任意景點(diǎn)個(gè)數(shù)的優(yōu)化路線(xiàn)，并與約束條件校核，確定出最多可以旅行景點(diǎn)數(shù)目的行程，從而解決問(wèn)題三、問(wèn)題四和問(wèn)題五。最后對(duì)模型進(jìn)行優(yōu)缺點(diǎn)分析，為提高模型的可靠性和模型的改進(jìn)提供依據(jù)。關(guān)鍵詞 離散型目標(biāo)優(yōu)化 動(dòng)態(tài)規(guī)劃模型 貨郎擔(dān)問(wèn)題 Floyd算法 蟻群算法 一、問(wèn)題的重述隨著人們的生活不斷提高，旅游已成為提高人們生活質(zhì)量的重要活動(dòng)。江蘇徐州有一位旅游愛(ài)好者打算現(xiàn)在的今年的五月一日早上8點(diǎn)之后出發(fā)，到全國(guó)一些著名景點(diǎn)旅游，最后回到徐州。由于跟團(tuán)旅游會(huì)受到若干限制，他(她)打算自己作為背包客出游

5、。他預(yù)選了十個(gè)省市旅游景點(diǎn)，如下表所示。預(yù)選的十個(gè)省市旅游景點(diǎn)省市景點(diǎn)名稱(chēng)在景點(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è)計(jì)詳細(xì)的行程表，該行程表應(yīng)包括具體的交通信息(車(chē)次、航班號(hào)、起止時(shí)間、票價(jià)等)、賓館地點(diǎn)和名稱(chēng)，門(mén)票費(fèi)用，在景點(diǎn)的停留時(shí)間等信息。(1) 如果時(shí)間不限，游客將十個(gè)景點(diǎn)全游覽完，至少需要多少旅游費(fèi)用？請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程

6、表。(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)用，想盡可能多游覽景點(diǎn)，請(qǐng)建立相關(guān)數(shù)學(xué)模型并設(shè)計(jì)旅游行程表。二、問(wèn)題的分析 此問(wèn)題是在一定約束條件下的離散型目標(biāo)優(yōu)化問(wèn)題，即從旅游時(shí)間、旅游費(fèi)用、以及旅游景點(diǎn)數(shù)目這三個(gè)因素來(lái)優(yōu)化旅游線(xiàn)路。 旅游時(shí)間由交通時(shí)間、景點(diǎn)停留時(shí)間、住宿時(shí)間以及其他時(shí)間組

7、成。旅游費(fèi)用由交通費(fèi)用、門(mén)票費(fèi)用、住宿費(fèi)用以及其他費(fèi)用組成。將各個(gè)旅游景點(diǎn)視為平面上不同位置的點(diǎn)，從徐州出發(fā)最后回到徐州形成一閉合回路，從而利用圖論的相關(guān)知識(shí)求解。旅游景點(diǎn)的平面圖各景點(diǎn)門(mén)票價(jià)格表景點(diǎn)恐龍園嶗山長(zhǎng)城喬家大院龍門(mén)石窟黃山黃鶴樓兵馬俑廬山普陀山票價(jià)1509050401202005090180200問(wèn)題一是在時(shí)間不限游覽10個(gè)景點(diǎn)的條件下最少費(fèi)用，由于門(mén)票費(fèi)用和其他費(fèi)用固定，我們主要考慮交通費(fèi)用和住宿費(fèi)用的影響，忽略其他次要因素的影響。問(wèn)題二是在旅游費(fèi)用不限游覽10個(gè)景點(diǎn)的條件下求最少時(shí)間，我們假設(shè)各個(gè)景點(diǎn)的游覽時(shí)間和市內(nèi)乘車(chē)固定，將城際交通時(shí)間和住宿時(shí)間作為最主要因素設(shè)計(jì)旅游路線(xiàn)。

8、問(wèn)題三是在費(fèi)用為2000元的限制條件下對(duì)旅游景點(diǎn)個(gè)數(shù)進(jìn)行優(yōu)化，我們主要考慮交通方式為列車(chē)和住宿費(fèi)用的影響。問(wèn)題四是在旅行時(shí)間為5天的約束條件下對(duì)旅游景點(diǎn)個(gè)數(shù)進(jìn)行優(yōu)化，我們主要考慮交通方式為飛機(jī)和住宿時(shí)間的影響問(wèn)題五是在費(fèi)用為2000元和旅行時(shí)間為5天的雙重約束下對(duì)旅游景點(diǎn)個(gè)數(shù)進(jìn)行優(yōu)化，因此必須綜合考慮交通方式、住宿時(shí)間和住宿費(fèi)用的影響。問(wèn)題四可以在問(wèn)題二的求解基礎(chǔ)上加以求解，而問(wèn)題五可以在問(wèn)題三和問(wèn)題四的求解基礎(chǔ)上求解。問(wèn)題的基本假設(shè)(A) 城際交通出行可以乘火車(chē)(含高鐵)、長(zhǎng)途汽車(chē)或飛機(jī)（不允許包車(chē)或包機(jī)），并且車(chē)票或機(jī)票可預(yù)訂到。(B) 市內(nèi)交通出行可乘公交車(chē)(含專(zhuān)線(xiàn)大巴、小巴)、地鐵或出

9、租車(chē)。(C) 旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門(mén)票(第一門(mén)票)。晚上20：00至次日早晨7：00之間，如果在某地停留超過(guò)6小時(shí)，必須住宿，住宿費(fèi)用不超過(guò)200元/天。吃飯等其它費(fèi)用60元/天。(D) 假設(shè)景點(diǎn)的開(kāi)放時(shí)間為8:00至18:00。（E）忽略地域差異，假設(shè)市內(nèi)乘車(chē)時(shí)間和費(fèi)用相同并以平均值計(jì)算，住宿費(fèi)用相同設(shè)為50元/夜。（F)假設(shè)所有城市交通狀況良好，不出現(xiàn)堵車(chē)、晚點(diǎn)情況。 三、符號(hào)說(shuō)明C 旅游景點(diǎn)的個(gè)數(shù) 選擇第i條路線(xiàn)總費(fèi)用 選擇第i條路線(xiàn)總時(shí)間 c+1 個(gè)點(diǎn)可選擇路線(xiàn)的總數(shù)a 吃飯等其他費(fèi)用 第i條路線(xiàn)到景點(diǎn)j間的路費(fèi) 第條路線(xiàn)第個(gè)景點(diǎn)的門(mén)票 第條路線(xiàn)第個(gè)景點(diǎn)

10、的住宿費(fèi)用 第條路線(xiàn)到第個(gè)景點(diǎn)的路上時(shí)間 第條路線(xiàn)第個(gè)景點(diǎn)的停留時(shí)間 第條路線(xiàn)第個(gè)景點(diǎn)的住宿時(shí)間u 其他時(shí)間，包括吃飯、等待時(shí)間等 第i條路線(xiàn)第j個(gè)景點(diǎn)是否需要住宿 (0-1變量)以上時(shí)間的單位均為小時(shí)，費(fèi)用的單位均為元四、 基本模型的建立模型一 離散型單目標(biāo)優(yōu)化模型經(jīng)分析，此題屬于單目標(biāo)優(yōu)化問(wèn)題，一到五問(wèn)要求在不同的約束條件下對(duì)不同的目標(biāo)進(jìn)行優(yōu)化，考慮到實(shí)際問(wèn)題，我們可以建立離散型目標(biāo)優(yōu)化模型來(lái)解決問(wèn)題。我們從十個(gè)景點(diǎn)中選擇C個(gè)景點(diǎn)，首先寫(xiě)出第i 條路線(xiàn)的總費(fèi)用與總時(shí)間的表達(dá)式我們引入住宿決策變量則 i = 1,2,3,4···我們引入函數(shù)h來(lái)描述時(shí)間和費(fèi)用與可

11、以選擇旅游景點(diǎn)個(gè)數(shù)的關(guān)系由于旅游的路費(fèi)和路上時(shí)間是由交通方式的選取和實(shí)際中的交通系統(tǒng)有關(guān)的，我們將這些信息收集并放到集合W 中，將可選擇的路線(xiàn)放到集合V中。下面我們結(jié)合一到五問(wèn)中的問(wèn)題分別確定優(yōu)化目標(biāo)和約束條件。第一問(wèn)以旅游總費(fèi)用為作為優(yōu)化目標(biāo)，要求它越小越好，而要求將10個(gè)景點(diǎn)旅游玩，對(duì)時(shí)間沒(méi)有限制?？捎孟旅婺Ｐ蛠?lái)描述。 最終在集合W和V中確定最優(yōu)的i 與交通方式。第二問(wèn)以旅游總時(shí)間為作為優(yōu)化目標(biāo)，要求它越小越好，而要求將10個(gè)景點(diǎn)旅游玩，對(duì)旅游總費(fèi)用沒(méi)有限制?？捎孟旅婺Ｐ蛠?lái)描述。 最終在集合W和V中確定最優(yōu)的i 與交通方式。第三問(wèn)以可以旅游的景點(diǎn)個(gè)數(shù)為優(yōu)化目標(biāo)，要求它越大越好，而要求旅游總

12、費(fèi)用不超過(guò)2000元，對(duì)旅游總時(shí)間沒(méi)有限制?？捎孟旅婺Ｐ蛠?lái)描述。 最終在集合W和V中確定所有滿(mǎn)足條件的i 與交通方式。第四問(wèn)與第三問(wèn)有相同的優(yōu)化目標(biāo)，但是要求旅游總時(shí)間不超過(guò)五天，而對(duì)旅游總費(fèi)用沒(méi)有要求。模型可以改寫(xiě)如下 第五問(wèn)則是三四問(wèn)的綜合，模型如下 模型二 動(dòng)態(tài)規(guī)劃模型 把每個(gè)旅游景區(qū)景點(diǎn)看做途中的一個(gè)節(jié)點(diǎn)，各景區(qū)景點(diǎn)之間的公路看做途中對(duì)應(yīng)節(jié)點(diǎn)間的邊，相對(duì)應(yīng)的行程距離看做對(duì)應(yīng)邊上的權(quán)，所給各景區(qū)景點(diǎn)間的交通路線(xiàn)網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖G，遍游各個(gè)景區(qū)景點(diǎn)的最佳旅游路線(xiàn)問(wèn)題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定出發(fā)點(diǎn)出發(fā)，行遍所有頂點(diǎn)至少一次且只有一次再回到定點(diǎn)，使得總權(quán)（路程）最小，此即TS

13、P問(wèn)題。對(duì)于本問(wèn)題： 設(shè)V1，V2，V3.，Vc是要旅游的景點(diǎn)，景點(diǎn)Vi到景點(diǎn)Vj的距離為dij，現(xiàn)在求從V0（徐州）出發(fā)，經(jīng)各景點(diǎn)一次且僅一次返回V0的最短路程，這讓我們聯(lián)想到著名的貨郎擔(dān)問(wèn)題，可以建立如下動(dòng)態(tài)規(guī)劃模型。 設(shè)S表示從V0到Vi中間可能經(jīng)過(guò)的景點(diǎn)集合，S實(shí)際上是包含除V0和Vi兩個(gè)點(diǎn)之外的其余點(diǎn)的集合，但S點(diǎn)中的個(gè)數(shù)是隨問(wèn)題改變的。 用狀態(tài)變量（i，s)表示從V0出發(fā)，經(jīng)過(guò)S集合中所有點(diǎn)一次最后到達(dá)Vi。 用最優(yōu)指標(biāo)函數(shù)fk(i，s)表示從V0出發(fā)，經(jīng)過(guò)S集合中所有點(diǎn)一次最后到達(dá)Vi。 決策變量Pk (i，s) 表示從V0經(jīng)K個(gè)中間城鎮(zhèn)的S集合到Vi城鎮(zhèn)的最短路線(xiàn)上鄰接Vi的前

14、一個(gè)城鎮(zhèn)，則動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為： j 屬于SC<=10 且C為整數(shù)根據(jù)上述的遞推模型，我們只要提供一個(gè)輸入就可以規(guī)劃出最優(yōu)的路線(xiàn)。五、 問(wèn)題解答根據(jù)實(shí)際情況，每個(gè)旅游景點(diǎn)只能去一次，而且要求所有景點(diǎn)距離之和最小，即按照最短路徑方式設(shè)計(jì)旅游路線(xiàn)。由此我們聯(lián)想到貨郎擔(dān)問(wèn)題，并采用圖論相關(guān)知識(shí)和floyd算法求出通過(guò)所有景點(diǎn)路徑之和的最小值，也即最短路徑以解決問(wèn)題一和問(wèn)題二。把每個(gè)旅游景區(qū)景點(diǎn)看做途中的一個(gè)節(jié)點(diǎn)，各景區(qū)景點(diǎn)之間的公路看做途中對(duì)應(yīng)節(jié)點(diǎn)間的邊，相對(duì)應(yīng)的行程距離看做對(duì)應(yīng)邊上的權(quán)，所給各景區(qū)景點(diǎn)間的交通路線(xiàn)網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖G，遍游各個(gè)景區(qū)景點(diǎn)的最佳旅游路線(xiàn)問(wèn)題就轉(zhuǎn)化為在給定的

15、加權(quán)網(wǎng)絡(luò)圖中尋找從給定出發(fā)點(diǎn)出發(fā)，行遍所有頂點(diǎn)至少一次且只有一次再回到定點(diǎn)，使得總權(quán)（路程）最小，此即TSP問(wèn)題。對(duì)于本問(wèn)題： 首先把所給的地圖、數(shù)據(jù)進(jìn)行簡(jiǎn)化（刪除不可能走的明顯偏遠(yuǎn)路，對(duì)于很靠近旅游景區(qū)的景點(diǎn)，我們把它劃分到一個(gè)景區(qū)，只考慮景點(diǎn)的最佳逗留時(shí)間的和），并對(duì)景區(qū)景點(diǎn)編號(hào)，如下圖景點(diǎn)恐龍園嶗山長(zhǎng)城喬家大院龍門(mén)石窟黃山黃鶴樓兵馬俑廬山普陀山徐州編號(hào)123456789100門(mén)票15090504012020050901802000由圖論的結(jié)論，TSp問(wèn)題可轉(zhuǎn)化成最佳哈密爾頓回路的問(wèn)題。因此可得到最佳旅游線(xiàn)路的近似算法。步驟一，用Floyd算法求出圖中任意兩點(diǎn)之間的最短路，構(gòu)建一個(gè)完備圖,

16、點(diǎn)集仍為，每條邊的權(quán)為點(diǎn)和在中最短路的長(zhǎng)。步驟二，隨機(jī)搜索圖的若干個(gè)H圈，或者找出它的任意一個(gè)初始的H圈。步驟三，用二邊逐次修正法對(duì)步驟二中的H圈進(jìn)行優(yōu)化，從而得到近似的最佳H圈。步驟四，比較上述H圈，找出權(quán)值最小的一個(gè)，即為要求的最佳H圈的近似解。 求解過(guò)程：首先將任意兩景點(diǎn)間的距離用矩陣表示，如下：A=0 484 712 814 881 473 831 885 860 682 792 484 0 1196 1297 1418 957 506 655 1344 586 380 712 1196 0 888 988 962 1543 1577 1349 1394 1016 814 1297 8

17、88 0 815 813 1533 1225 1200 1314 1544 881 1418 988 815 0 878 1361 1243 593 1695 1568 473 957 962 813 878 0 1113 0 625 672 714 464 831 506 1543 1533 1361 1113 0 625 672 714 464 885 655 1577 1225 1243 660 625 0 1024 252 1017 860 1344 1349 1200 593 387 672 1024 0 1102 1609 682 586 1394 1314 1695 964 71

18、4 252 1102 0 779 792 380 1016 1544 1568 1298 464 1017 1609 779 0用Floyd算法求出圖中任意兩點(diǎn)之間的最短路， Mtalab源程序如下：a; %輸入數(shù)據(jù)function D , path = floyd(a)n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,

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

20、)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endcircle=c1;sum=sum1;c1=1 22 2:21;%改變初始圈，該算法的最后一個(gè)頂點(diǎn)不動(dòng)flag=1;while flag>0 flag=0; for m=1:L-3 for n=m+2:L-1 if 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); end end en

21、dendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1<sum sum=sum1; circle=c1;endcircle,sum結(jié)果為：Columns 1 through 11 0 2 1 10 6 9 7 5 8 4 3 sum = 6987根據(jù)結(jié)果得到最小的H圈如下圖由于要游覽10個(gè)旅游景點(diǎn)，我們對(duì)所得到的最佳H圈繼續(xù)進(jìn)行修正，最終得到了最佳旅游路線(xiàn)，與上述路線(xiàn)相符，即0211069758430問(wèn)題一求解：若時(shí)間無(wú)限制，要使旅行總費(fèi)用最少，其他費(fèi)用不變的情況下，則必須選最便宜的交通方式，這樣才能使總費(fèi)用盡可能的少，按照

22、最小路徑給出旅游路線(xiàn)。具體行程表如下：根據(jù)模型綜合考慮各種因素設(shè)計(jì)的行程表5月1日10：5220:39乘坐K174/171從徐州到青島（在青島休息）5月2日08:0014:00游覽青島嶗山5月2日14:135月3日05:57乘坐列車(chē)K296/293至常州5月3日08:0012:00游覽恐龍園5月3日14:0018:30乘坐列車(chē)K119/116至舟山（在舟山休息）5月4日08:0014:00游覽普陀山5月4日16:00-20:15乘坐列車(chē)K217/270至黃山（在黃山休息）5月5日08:0015:00游覽黃山5月5日18:29-5月6日03:27乘坐列車(chē)K308/305至九江（在九江休息）5月6

23、日08:0015:00游覽廬山5月6日17:00-21:30乘坐列車(chē)K115/118至武漢（在武漢休息）5月7日08:0010:00游覽黃鶴樓5月7日13:00-21:00乘坐列車(chē)K337/224至洛陽(yáng)（在洛陽(yáng)休息）5月8日08:0011:00游覽龍門(mén)石窟5月9日01:18-06:29乘坐至列車(chē)K624/621至西安5月9日08:0010:00游覽秦始皇兵馬俑5月9日10:15-13:55乘坐列車(chē)K128/125至祁縣5月9日15:0018:00游覽喬家大院5月9日19:0023:30乘坐列車(chē)K158/155至北京（在北京休息）5月11日08:0011:00游覽八達(dá)嶺長(zhǎng)城5月11日12:41-

24、23:52乘坐列車(chē)1477返回徐州結(jié)束旅行總費(fèi)用=乘車(chē)費(fèi)用+門(mén)票費(fèi)用+住宿費(fèi)用+其他費(fèi)用乘車(chē)費(fèi)用=99+120+80+65+30+50+90+55+76+150+106 =921門(mén)票費(fèi)用=150+90+50+40+120+200+50+90+180+200 =1170住宿費(fèi)用=7*50 =350其他費(fèi)用=10*60 =600總費(fèi)用=921+1170+350+600 =3041問(wèn)題二求解：若使旅行時(shí)間最少，必須減少交通時(shí)間和住宿時(shí)間。交通時(shí)間的較少可以通過(guò)乘飛機(jī)來(lái)實(shí)現(xiàn)，住宿時(shí)間的減少可以通過(guò)盡量在白天旅游，晚上趕路的方式實(shí)現(xiàn)。受floyd算法啟發(fā)，將任意兩個(gè)景點(diǎn)之間的時(shí)間看做權(quán)，即相鄰兩點(diǎn)的邊長(zhǎng)

25、，得出11*11的時(shí)間矩陣，單位為分鐘。c = 0 484 712 814 881 473 831 885 860 682 792484 0 1196 1297 1418 957 506 655 1344 586 380712 1196 0 888 988 962 1543 1577 1349 1394 1016814 1297 888 0 815 813 1533 1225 1200 1314 1544881 1418 988 815 0 878 1361 1243 593 1695 1568473 957 962 813 878 0 1113 660 387 714 464831 506

26、1543 1533 1361 1113 0 625 672 714 464885 655 1577 1225 1243 660 625 0 1024 252 1017860 1344 1349 1200 593 387 672 1024 0 1102 1609682 586 1394 1314 1695 964 714 252 1102 0 779792 380 1016 1544 1568 1298 464 1017 1609 779 0利用floyd算法在所有可能的組合方式中求出唯一的一組方式，此方式使得行程時(shí)間最短，結(jié)果如下（已考慮轉(zhuǎn)站問(wèn)題）：徐州八達(dá)嶺 祁縣 洛陽(yáng)西安 武漢 九江 黃山

27、 舟山 常州 青島 徐州具體路線(xiàn)為：根據(jù)模型綜合考慮各種因素設(shè)計(jì)的行程表5月1日12:00-14:05從徐州乘坐航班JR2110航班至祁縣5月1日15:00-18:00游覽祁縣喬家大院5月1日20:10-21:40乘航班KC1150至洛陽(yáng)（在洛陽(yáng)休息）5月2日08:00-11:00游覽龍門(mén)石窟5月2日12:10-13:20乘坐航班KJ1250至西安5月2日14:00-16:00游覽秦始皇兵馬俑5月2日20:30-21:40乘坐航班CZ3890至武漢（在武漢休息）5月3日08:00-10:00游覽黃鶴樓5月3日10:30-11:20乘坐航班C2360至九江5月3日12:00-18:00在廬山游覽

28、6h后住宿休息5月4日09:10-10:40乘坐航班KC2130至黃山5月4日11:00-18:00游覽黃山7h后在黃山休息5月5日04:30-05:50乘坐C2118航班至舟山。5月5日08:00-14:00游覽舟山5月5日18:10-19:25乘坐航班CZ2120）至常州(在常州休息)5月6日08:00-12:00游覽恐龍園5月6日16:25-18:10乘坐航班CA1826至青島（在青島休息）5月7日08:00-12:00游覽嶗山5月7日15:20-16:45乘坐航班MV7432回到徐州結(jié)束全部旅程問(wèn)題三求解：在旅行費(fèi)用為2000元的限制條件下，要盡可能多的游覽景區(qū)就必須減少交通費(fèi)用以增加

29、游覽景點(diǎn)的費(fèi)用。 由此聯(lián)想到“蟻群算法”3（155-158）求最短路徑問(wèn)題。用”蟻群算法”求R（R=1,2,3,4,5,6,7,8,9）個(gè)景點(diǎn)行程閉合路線(xiàn)的最短距離和，每個(gè)R都對(duì)應(yīng)一個(gè)總費(fèi)用，則必存在唯一的一個(gè)最大R值使得總費(fèi)用接近2000元（也可略高于2000元），此R值即最多景點(diǎn)數(shù)。%蟻群算法求解TSP問(wèn)題的mat lab程序clear allclose allclc%初始化蟻群m=5;%蟻群中螞蟻的數(shù)量，當(dāng)m接近或等于城市個(gè)數(shù)n時(shí)，本算法可以在最少的迭代次數(shù)內(nèi)找到最優(yōu)解C=2449 1715; 2701 1687;2544 1917;2215 1859;1880 1469;1978 13

30、34;2590 1495 2244 1295;1719 1160;2442 1354;2923 1688;%城市的坐標(biāo)矩陣Nc_max=200;%最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動(dòng)的撥數(shù)（每撥螞蟻的數(shù)量當(dāng)然都是m）alpha=1;%螞蟻在運(yùn)動(dòng)過(guò)程中所積累信息（即信息素）在螞蟻選擇路徑時(shí)的相對(duì)重要程度，alpha過(guò)大時(shí)，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象beta=5;%啟發(fā)式因子在螞蟻選擇路徑時(shí)的相對(duì)重要程度rho=0.5;%0<rho<1,表示路徑上信息素的衰減系數(shù)（亦稱(chēng)揮發(fā)系數(shù)、蒸發(fā)系數(shù)），1-rho表示信息素的持久性系數(shù)Q=100;%螞蟻釋放的信息素量，對(duì)本算法的性能

31、影響不大a%變量初始化n=size(C,1)-（10-R）;%表示TSP問(wèn)題的規(guī)模，亦即城市的數(shù)量 D=ones(n,n);%表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離for i=1:n for j=1:n if i<j D(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2); end D(j,i)=D(i,j); endendeta=1./D;%啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù)pheromone=ones(n,n);%信息素矩陣,這里假設(shè)任何兩個(gè)城市之間路徑上的初始信息素都為1tabu_list=zeros(m,n);%禁忌表，記錄螞蟻已經(jīng)

32、走過(guò)的城市，螞蟻在本次循環(huán)中不能再經(jīng)過(guò)這些城市。當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來(lái)計(jì)算螞蟻當(dāng)前所建立的解決方案，即經(jīng)過(guò)的路徑和路徑的長(zhǎng)度Nc=0;%循環(huán)次數(shù)計(jì)數(shù)器routh_best=zeros(Nc_max,n);%各次循環(huán)的最短路徑length_best=ones(Nc_max,1);%各次循環(huán)最短路徑的長(zhǎng)度length_average=ones(Nc_max,1);%各次循環(huán)所有路徑的平均長(zhǎng)度while Nc<Nc_max %將m只螞蟻放在n個(gè)城市上 rand_position=; for i=1:ceil(m/n) rand_position=rand_position,randpe

33、rm(n); end tabu_list(:,1)=(rand_position(1:m)'%將螞蟻放在城市上之后的禁忌表，第i行表示第i只螞蟻，第i行第一列元素表示第i只螞蟻所在的初始城市 %m只螞蟻按概率函數(shù)選擇下一座城市，在本次循環(huán)中完成各自的周游 for j=2:n for i=1:m city_visited=tabu_list(i,1:(j-1);%已訪(fǎng)問(wèn)的城市 city_remained=zeros(1,(n-j+1);%待訪(fǎng)問(wèn)的城市 probability=city_remained;%待訪(fǎng)問(wèn)城市的訪(fǎng)問(wèn)概率 cr=1; for k=1:n%for循環(huán)用于求待訪(fǎng)問(wèn)的城市。

34、比如如果城市個(gè)數(shù)是5，而已訪(fǎng)問(wèn)的城市city_visited=2 4,則經(jīng)過(guò)此for循環(huán)后city_remanied=1 3 5 if length(find(city_visited=k)=0 city_remained(cr)=k; cr=cr+1; end end %狀態(tài)轉(zhuǎn)移規(guī)則* q0=0.5; if rand>q0 for k=1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(

35、k)beta; position=find(probability=max(probability); to_visit=city_remained(position(1); end else for k=1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; end probability=probability/sum(probability); pcum=cumsum(prob

36、ability); select=find(pcum>=rand); to_visit=city_remained(select(1); end tabu_list(i,j)=to_visit; %* end end if Nc>0 tabu_list(1,:)=routh_best(Nc,:);%將上一代的最優(yōu)路徑（最優(yōu)解）保留下來(lái)，保證上一代中的最適應(yīng)個(gè)體的信息不會(huì)丟失 end %記錄本次循環(huán)的最佳路線(xiàn) total_length=zeros(m,1);%m只螞蟻在本次循環(huán)中分別所走過(guò)的路徑長(zhǎng)度 for i=1:m r=tabu_list(i,:);%取出第i只螞蟻在本次循環(huán)中所

37、走的路徑 for j=1:(n-1) total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只螞蟻本次循環(huán)中從起點(diǎn)城市到終點(diǎn)城市所走過(guò)的路徑長(zhǎng)度 end total_length(i)=total_length(i)+D(r(1),r(n);%最終得到第i只螞蟻在本次循環(huán)中所走過(guò)的路徑長(zhǎng)度 end length_best(Nc+1)=min(total_length);%把m只螞蟻在本次循環(huán)中所走路徑長(zhǎng)度的最小值作為本次循環(huán)中最短路徑的長(zhǎng)度 position=find(total_length=length_best(Nc+1);%找到最短路徑的位置

38、，即最短路徑是第幾只螞蟻或哪幾只螞蟻?zhàn)叱鰜?lái)的 routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一個(gè)走出最短路徑的螞蟻在本次循環(huán)中所走的路徑作為本次循環(huán)中的最優(yōu)路徑 length_average(Nc+1)=mean(total_length);%計(jì)算本次循環(huán)中m只螞蟻所走路徑的平均長(zhǎng)度 Nc=Nc+1 %更新信息素 delta_pheromone=zeros(n,n); for i=1:m for j=1:(n-1) delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)=delta_pheromone(ta

39、bu_list(i,j),tabu_list(i,j+1)+Q/total_length(i);%total_length(i)為第i只螞蟻在本次循環(huán)中所走過(guò)的路徑長(zhǎng)度（蟻周系統(tǒng)區(qū)別于蟻密系統(tǒng)和蟻量系統(tǒng)的地方） end delta_pheromone(tabu_list(i,n),tabu_list(i,1)=delta_pheromone(tabu_list(i,n),tabu_list(i,1)+Q/total_length(i);%至此把第i只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經(jīng)累加上去 end%至此把m只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經(jīng)累加上去 pheromone=

40、(1-rho).*pheromone+delta_pheromone;%本次循環(huán)后所有路徑上的信息素 %禁忌表清零，準(zhǔn)備下一次循環(huán)，螞蟻在下一次循環(huán)中又可以自由地進(jìn)行選擇 tabu_list=zeros(m,n);end%輸出結(jié)果，繪制圖形position=find(length_best=min(length_best);shortest_path=routh_best(position(1),:)shortest_length=length_best(position(1)%繪制最短路徑figure(1)set(gcf,'Name','Ant Colony Opti

41、mizationFigure of shortest_path','Color','r')N=length(shortest_path);scatter(C(:,1),C(:,2),50,'filled');hold onplot(C(shortest_path(1),1),C(shortest_path(N),1),C(shortest_path(1),2),C(shortest_path(N),2)set(gca,'Color','g')hold onfor i=2:N plot(C(shortest_

42、path(i-1),1),C(shortest_path(i),1),C(shortest_path(i-1),2),C(shortest_path(i),2) hold onend%繪制每次循環(huán)最短路徑長(zhǎng)度和平均路徑長(zhǎng)度f(wàn)igure(2)set(gcf,'Name','Ant Colony OptimizationFigure of length_best and length_average','Color','r')plot(length_best,'r')set(gca,'Color',&#

43、39;g')hold onplot(length_average,'k') 由此算法得出的不同R值閉合路徑如下： R=6 R=7 R=8當(dāng)R=7時(shí)，確定的旅游路線(xiàn)如下：根據(jù)模型綜合考慮各種因素設(shè)計(jì)的行程表5月1日10：5220:39乘坐K174/171從徐州到青島（在青島休息）5月2日08:0014:00游覽青島嶗山5月2日14:135月3日05:57乘坐列車(chē)K296/293至常州5月3日08:0012:00游覽恐龍園5月3日14:445月4號(hào)00:27乘坐k421/k423次列車(chē)到黃山（在黃山休息）5月4日08:0015:00游覽黃山5月4日17:0023:48乘坐k

44、381/k378次列車(chē)到武漢（在武漢休息）5月5日08:0010:00游覽黃鶴樓5月5日10:3620:26乘k1296/k1297次列車(chē)到洛陽(yáng)(在洛陽(yáng)休息)5月6日08:0011:00游覽龍門(mén)石窟5月6日11:3619:55乘k1130/k1131次列車(chē)到祁縣（在祁縣休息）5月7日08:0011:00游覽喬家大院5月7日13:335月8日04:00乘坐2601/2604次列車(chē)到北京5月8日08:0011:00游覽八達(dá)嶺5月8日11:3921:21乘坐k45次列車(chē)到達(dá)徐州，結(jié)束全部旅程問(wèn)題四求解：?jiǎn)栴}四可以在問(wèn)題二的基礎(chǔ)上求解，因?yàn)閱?wèn)題二中已求出旅游10個(gè)景點(diǎn)的最少時(shí)間為7天，現(xiàn)在旅游時(shí)間限制

45、為5天，要使旅游景點(diǎn)的個(gè)數(shù)盡可能的多，可以出去交通和觀(guān)光時(shí)間比較長(zhǎng)的景點(diǎn)，如青島市嶗山、黃山市黃山、九江市廬山、舟山市普陀山等等。由于常州到青島的時(shí)間最長(zhǎng)，而且在青島的觀(guān)光時(shí)間為6h,所以?xún)?yōu)先考慮除去青島這一點(diǎn)。即在舟山市普陀山游玩后直接乘車(chē)回到徐州，這樣可以在5天時(shí)間內(nèi)游覽8個(gè)景點(diǎn)。具體路線(xiàn)行程為：根據(jù)模型綜合考慮各種因素設(shè)計(jì)的行程表5月1日12:00-14:05從徐州乘坐航班JR2110航班至祁縣5月1日15:00-18:00游覽祁縣喬家大院5月1日20:10-21:40乘航班KC1150至洛陽(yáng)（在洛陽(yáng)休息）5月2日08:00-11:00游覽龍門(mén)石窟5月2日12:10-13:20乘坐航班KJ1250至西安5月2日14:00-16:00游覽秦始皇兵馬俑5月2日20:30-21:40乘坐航班CZ3890至武漢（在武漢休息）5月3日08:00-10:00游覽黃鶴樓5月3日10:30-11:20乘坐航班C2360至九江5月3日12:00-18