旅游線路的優(yōu)化設(shè)計001

1、 .DOC資料. 旅游線路的優(yōu)化設(shè)計001-作者：-日期： HYPERLINK /問題重述隨著人們的生活不斷提高，旅游已成為提高人們生活質(zhì)量的重要活動。江蘇徐州有一位旅游愛好者打算在今年的五月一日早上8點之后出發(fā)，到全國一些著名景點旅游，最后回到徐州。由于跟團旅游會受到若干限制，他(她)打算自己作為背包客出游。他預(yù)選了十個省市旅游景點，如附表1（見附錄I）所示。假設(shè)(A)城際交通出行可以乘火車(含高鐵)、長途汽車或飛機（不允許包車或包機），并且車票或機票可預(yù)訂到。(B)市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(C)旅游費用以網(wǎng)上公布為準，具體包括交通費、住宿費、景點門票(第一

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

3、備2000元旅游費用，想盡可能多游覽景點，請建立相關(guān)數(shù)學模型并設(shè)計旅游行程表。(4) 如果這位游客只有5天的時間，想盡可能多游覽景點，請建立相關(guān)數(shù)學模型并設(shè)計旅游行程表。(5) 如果這位游客只有5天的時間和2000元的旅游費用，想盡可能多游覽景點，請建立相關(guān)數(shù)學模型并設(shè)計旅游行程表。問題假設(shè)1、忽略乘坐出租車時經(jīng)過收費路段所交的費用；2、在每個城市中停留時，難免會遇到等車、堵車等延時情況，在此問題中我們不做考慮；3、所有旅館都未客滿，并且忽略從旅館到火車站或景點的時間；4、列車車次和飛機航班沒有晚點等情況發(fā)生；5、列車和飛機的票足夠，沒有買不到票的情況發(fā)生；6、景點的開放，列車和航班的運營不受

4、天氣的影響；7、繪圖時，經(jīng)線和緯線近似平行分布；8、將城市和路徑的關(guān)系轉(zhuǎn)化為圖論問題；9、在時間的認識上，我們把當天的8點至次日的8點作為一天。符號說明有向圖矩陣城市路徑要經(jīng)過的城市總數(shù)任意兩城市之間的距離是否經(jīng)過兩座城市路徑上的信息量啟發(fā)函數(shù)信息啟發(fā)式因子期望啟發(fā)式因子螞蟻在時刻由城市轉(zhuǎn)向城市的轉(zhuǎn)移概率第只螞蟻的禁忌搜索表信息素揮發(fā)系數(shù)時刻螞蟻在路徑上留下的信息素量到目前為止所找到的全局最短路徑長度螞蟻攜帶的信息素量本次循環(huán)中第只螞蟻所走的路程長度螞蟻的總數(shù)量螞蟻的編號所記錄的循環(huán)次數(shù)最大循環(huán)次數(shù)問題分析4.1問題一的分析針對問題一，要求求出將旅游景點全游覽完，所需的最少旅游費用。這和問題,

5、即旅行商問題有些類似，所以本文將問題向問題進行一定的轉(zhuǎn)化，從而進行求解。因為運用傳統(tǒng)的動態(tài)規(guī)劃解法，解法的空間復(fù)雜性和時間復(fù)雜性都十分龐大，不利于求解，所以采用蟻群算法，通過計算機軟件進行編程得到路程最短的旅行路線。因題目要求時間不限，用最少的旅游費用游覽全部景點，而考慮到不同交通工具的速度和票價都不相同，各個旅館的住宿費用也不相同，所以我們對其行程進行詳細的安排，盡量減少其在交通和住宿上的費用，減少不必要的花費。最后得出一個最少旅游費用的旅游行程表。4.2問題二的分析針對問題二，要求求出將旅游景點全游覽完，所需的最少時間。因為考慮到交通工具的不同導(dǎo)致時間上的差異問題，所以僅用問題一的模型不能

6、求解。但是由于任意兩座城市之間都能相連接起來，且每座城市只經(jīng)過一次，所以將任意兩座城市之間的路程轉(zhuǎn)變?yōu)闀r間，建立最優(yōu)化模型，通過計算機軟件進行編程，到時間最短的旅游路線。然后，根據(jù)題目要求，再對其行程進行詳細的安排，盡量避免不必要的時間。最后得出一個最短時間的旅游行程表。4.3問題三的分析針對問題三，題目給出了限制條件，旅游費用不超過2000元。只用2000元游覽完全部景點是不可能的，所以我們對其行程進行優(yōu)化。首先，將問題一的旅游行程根據(jù)旅游景點和交通路線劃分成21個部分（包括10個景點和11條交通線路），并計算出每一個部分所要花費的旅游費用。然后，對旅游行程進行優(yōu)化計算，為了簡化運算，我們假

7、設(shè)交通線路上花費的費用只是簡單相加。通過除去旅游景點計算出2000元以下的費用最優(yōu)解。最后得出一個2000元以下的旅游行程表。4.4問題四的分析針對問題四，題目也給出了限制條件，旅游時間不超過5天。只用5天游覽完全部景點是不可能的，所以我們對其行程進行優(yōu)化。解法與問題三大致相同。首先，對問題二的旅游行程也根據(jù)旅游景點和交通路線劃分成21部分（包括10個景點和11條交通線路），并計算出每一個部分所要花費的時間。然后，對旅游行程進行優(yōu)化計算，為了簡化運算，我們假設(shè)交通線路上花費的時間只是簡單相加。通過除去旅游景點計算出5天以內(nèi)的時間最優(yōu)解。最后得出一個5天以內(nèi)的旅游行程表4.5問題五的分析針對問題

8、五，題目給出了兩個限制條件，旅游費用不超過2000元，并且旅游時間在5天以內(nèi)。只用5天和2000元游覽完10個景點是不可能的，所以我們對其進行優(yōu)化。由于飛機價格非常高，所以我們基于第三問，并且結(jié)合第四問的數(shù)據(jù)對其進行優(yōu)化。首先，對旅游行程也根據(jù)旅游景點和交通路線劃分成21部分（包括10個景點和11條交通線路），并計算出每一部分所要花費的時間和費用。然后，對旅游行程進行優(yōu)化計算，為了簡化運算，我們假設(shè)交通線路上花費的時間和費用只是簡單相加。通過除去旅游景點計算出2000元以下和5天以內(nèi)的時間最優(yōu)解。最后得出一個最優(yōu)旅游行程表。模型的建立與求解5.1問題一的求解5.1.1建立圖論的數(shù)學模型將各個旅

9、游景點之間的關(guān)系轉(zhuǎn)化為圖論問題，并做以下分析：建立有向圖。其中稱為圖的頂點集，中的每一個元素稱為該圖的一個頂點，在該題中表示城市；稱為圖的弧集，中的每個元素稱為該圖的一條從到的弧，在此題中表示各個城市兩兩連線的集合。1設(shè)城市個數(shù)為，表示兩個城市與之間的距離，0或1（1表示走過城市到城市的路，0表示沒有選擇走這條路）。本題可以向問題進行轉(zhuǎn)化，則問題的數(shù)學模型為：5.1.2建立螞蟻算法的數(shù)學模型(1)狀態(tài)轉(zhuǎn)移規(guī)則因為螞蟻不能重復(fù)經(jīng)過一個城市，所以建立禁忌表來記錄螞蟻走過的城市，禁忌表隨著時間做動態(tài)變化。建立螞蟻由城市轉(zhuǎn)移到城市的狀態(tài)轉(zhuǎn)移概率如下： （1）上式中為信息啟發(fā)式因子，表示路徑的相對重要性

10、，是對所積累的信息素影響作用的一個加權(quán)值；為期望啟發(fā)式因子，表示能見度的相對重要性；每只螞蟻必須依據(jù)以城市距離和連接邊上信息素的數(shù)量為變量的概率函數(shù)，決定選擇下一個城市的概率。每只螞蟻必須根據(jù)禁忌表和概率函數(shù)尋找下一個城市，以保證該螞蟻從起點出發(fā)經(jīng)過所有城市有且只有一次，并且最終返回到起點。(2)信息素的全局更新規(guī)則當只螞蟻成功的完成一次尋徑過程之后，將選出目標函數(shù)值最小的路徑，用以完成全局信息素的更新，使得較優(yōu)解保留下來，對后繼螞蟻產(chǎn)生影響，加快收斂到最優(yōu)解的速度。設(shè)，為兩個相連接點，則有： （2）其中，變量是在時刻，節(jié)點之間路上信息素的增加量是位于0,1上的“激素”揮發(fā)因子；為到目前為止所

11、找到全局最短路徑長度。(3)信息素的局部更新對于第只螞蟻，在建立一個解得過程中也同時進行激素跡的更新，如果節(jié)點是它所選擇路徑上的兩個相鄰節(jié)點，規(guī)則如下：否則，不更新。其中，是各條路上的信息素的初始值，通常取同一值，表示同一環(huán)境。信息素的更新策略有很多種方法，每種更新策略的主要差別體現(xiàn)在的求法上。我們規(guī)定螞蟻在完成一個循環(huán)后更新所有路徑上的信息素，其方程式為： （3）上式中表示螞蟻攜帶信息素的量，其值的大小影響算法的收斂速度；表示第只螞蟻在本次循環(huán)中所走的路程總長度。5.1.3基于蟻群算法的實現(xiàn)步驟2本題基于蟻群算法的實現(xiàn)步驟如下：初始化。時間，循環(huán)次數(shù)，設(shè)置最大循環(huán)次數(shù)為，；：循環(huán)次數(shù)；：螞蟻

12、個數(shù)；：螞蟻選擇可以到達的城市，按照狀態(tài)轉(zhuǎn)移規(guī)則移動到下一個城市；：對于城市，由于已經(jīng)到達，所以添加到禁忌表中；：判斷所有城市是否都經(jīng)過，若未完全經(jīng)過，表明螞蟻個數(shù)沒有達到，則轉(zhuǎn)向執(zhí)行，否則執(zhí)行； ：由于信息素改變，要求按照公式（2）（3）更新最短路徑信息素，使得較優(yōu)解保留，加快收斂到最優(yōu)解的速度；：若表明沒有滿足終止條件，即轉(zhuǎn)向執(zhí)行，否則執(zhí)行；：輸出最優(yōu)結(jié)果。5.1.4模型的求解(1)求解城市之間的距離首先，假設(shè)經(jīng)線和緯線近似平行分布，根據(jù)附表2（見附錄I）可知11座城市的經(jīng)緯坐標。建立直角坐標系，以緯度最低的城市所在的緯線為軸，以經(jīng)度最小的城市所在的經(jīng)線為軸，計算11座城市的坐標。將城市進

13、行編號，計算相應(yīng)城市間的距離得到附表3（見附錄I），得到編程數(shù)據(jù)（見附錄II）。(2)求解最短路徑利用上述蟻群算法的步驟，使用附錄II的數(shù)據(jù)，編寫程序，得出以下結(jié)果：Shortest_Route =6 9 5 4 3 1 2 11 7 10 8圖一：模擬圖對上述結(jié)果進行處理，根據(jù)城市編號求出最優(yōu)解為：徐州常州舟山黃山九江武漢洛陽西安祁縣北京青島徐州由上面結(jié)果可以在中國地圖上模擬出最短路線，如下：圖二：問題一模擬路徑圖5.1.5設(shè)計旅游行程表和求出總費用我們根據(jù)蟻群算法得出游覽全部景點的最短路徑，在得出的最短路徑的基礎(chǔ)上，我們通過查閱火車票價、車次、運營時間，賓館價格、名稱等大量資料和數(shù)據(jù)，盡可

14、能的減少其在行程上的花費，設(shè)計出如下旅游行程表：表一：問題一行程表（其余答案參見附錄III）日期時間行程價格（元）5月1日8:3015:45乘坐L8449次列車（徐州常州）3416:0021:00游覽常州市021:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐公交去中華恐龍園48:0016:00游覽中華恐龍園16016:0017:00乘坐公交返回417:0022:30游覽常州市022:305:20乘坐K75次列車（常州寧波）735月3日5:308:00乘坐758W公交到白峰碼頭乘坐船到普陀山168:0014:00游覽普陀山20014:0016:00返回寧波站16

15、16:0022:15乘坐K8500次列車（寧波宣城）6322:151:30候車0并且得出最少的總旅游費用為3438元。5.2問題二的求解5.2.1模型的建立基于第一問的模型，我們稍作改進。因為第二問要求安排時間最短的旅游行程表，而費用不限，由于飛機費用過大，所以在第一問我們未做考慮，但由于其時間比火車和汽車都要快的多，所以我們把飛機作為首要考慮對象加入第二問中。第一問的模型中，是把任意兩點之間的距離作為參數(shù)，從而進行求解，得出最短路徑。在第二問中，我們把任意兩點之間的所乘坐的交通工具的最短時間作為參數(shù)，建立時間最優(yōu)化模型,結(jié)合軟件（程序見附錄III）求出經(jīng)過所有旅游景點的花費時間最短的路線。5

16、.2.2模型的解釋在模型中，我們引入0-1變量，若通過兩城市之間的路徑，則賦值為1；若不通過兩城市之間的路徑，則賦值為0。對于無向圖的最短時間路徑問題，可以這樣理解，從點到點和點到點的邊，看成有向弧，其他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短時間路徑問題來編程。35.2.3模型的求解利用上述算法的步驟，使用附錄II的數(shù)據(jù)，編寫程序，得出以下結(jié)果：VariableValueReduced CostX(1,2)1.000000322.0000X(2,9)1.000000110.0000X(3,11)1.00000090.00000X(4,6)1.000000105.000

17、0X(5,3)1.000000100.0000X(6,1)1.000000280.0000X(7,4)1.000000120.0000X(8,10)1.000000215.0000X(9,5)1.00000065.00000X(10,7)1.000000484.0000X(11,8)1.00000075.00000即最短時間路徑：對上述結(jié)果進行處理，根據(jù)城市編號求出最優(yōu)解為：徐州常州西安祁縣青島舟山武漢九江黃山北京洛陽徐州由上面結(jié)果可以在中國地圖上模擬出最短路線，如下：圖三：問題二模擬路徑圖5.2.4設(shè)計旅游行程表和求出總費用我們根據(jù)最優(yōu)化模型得出游覽全部景點的最短時間路徑，在得出的最短時間路

18、徑的基礎(chǔ)上，我們通過查閱飛機票價、班次、運營時間，賓館價格、名稱等大量資料和數(shù)據(jù)，盡可能的減少其在行程上的花費，設(shè)計出如下旅游行程表：表二：問題二的行程表（其余答案參見附錄III）日期時間行程價格（元）5月1日8:009:30整理行裝09:3015:30乘坐K55次列車（徐州常州）7015:3021:00游覽常州市021:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐出租車到中華恐龍園408:0016:00游覽中華恐龍園16016:0017:00乘坐出租車返回4017:0021:00游覽常州市021:0023:00乘坐MU5638班次飛機（常州西安）111023

19、:0024:00乘坐出租車到秦始皇兵馬俑405月3日0:008:00住宿于西安美寶賓館后宰門店1388:0010:00游覽秦始皇兵馬俑9010:0011:00乘坐出租車返回4011:0013:00游覽西安0并且得出最少的總旅游時間為210小時。5.3問題三的求解基于第一問得出的旅游行程表，我們對其進行優(yōu)化。由于題目給出了約束條件，旅游經(jīng)費不超過2000元，所以我們將行程劃分為21部分（包括10個景點和11條線路）。然后統(tǒng)計出每一部分所要花費的經(jīng)費，如下表所示：表三：各地花費經(jīng)費表（單位：元）徐州常州舟山黃山九江武漢016823226020084洛陽西安祁縣北京青島124944485164徐州常

20、州常州寧波寧波黃山黃山九江九江武漢武漢洛陽347389935792洛陽西安西安祁縣祁縣北京北京青島青島徐州55399415899由上表可以看出，黃山、普陀、九江和常州所花費的經(jīng)費占10個旅游景點的前4位，這四個景點的總經(jīng)費大約為915元，所以先不考慮黃山、普陀、九江和常州這四個景點。然后使其從青島開始出發(fā)，盡量避免這四個景點。對其余的景點根據(jù)最短路徑重新安排行程，避免住宿，減少不必要的花費。表四：問題三行程估計表（其余數(shù)據(jù)參見附錄IV）日期時間行程價格（元）5月1日8:0023:30整理行裝023:308:00乘坐K1025次列車（徐州青島）705月2日8:009:00乘坐311W公交車到嶗山

21、風景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311W公交車返回718:0020:00游覽青島市020:005:30乘坐T26次列車（青島北京）1165月3日5:307:00休息07:008:00乘坐地鐵2號線和公交車到八達嶺208:0013:00游覽八達嶺4513:0014:00乘坐地鐵2號線和公交車返回2014:0022:00游覽北京市022:0023:30休息023:3013:30乘坐2603次列車（北京祁縣）945月4日13:3014:30乘坐公交車到喬家大院214:3018:00游覽喬家大院4018:0019:00乘坐公交車返回219:0020:30游覽祁縣0經(jīng)過計

22、算，新的旅游行程所花費的經(jīng)費大約為1517元，與題目給出的2000元還有很大的差距，所以我們重新旅游行程表進行優(yōu)化，對黃山、普陀、九江和常州這四個旅游景點進行分析，安排行程。發(fā)現(xiàn)只有添加九江這個景點旅游費用不會超支，所以設(shè)計出如下行程表：表五：問題三行程表（其余答案參見附錄III）日期時間行程價格（元）5月1日8:0023:30整理行裝023:308:00乘坐K1025次列車（徐州青島）705月2日8:009:00乘坐311W公交車到嶗山風景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311W公交車返回718:0020:00游覽青島市020:005:30乘坐T26次列車（青島北

23、京）1165月3日5:307:00休息07:008:00乘坐地鐵2號線和公交車到八達嶺208:0013:00游覽八達嶺4513:0014:00乘坐地鐵2號線和公交車返回2014:0022:00游覽北京市022:0023:30休息023:3013:30乘坐2603次列車（北京祁縣）94并且得出旅行費用為1994元。由上面結(jié)果可以在中國地圖上模擬出最短路線，如下：圖四：問題三模擬路徑圖5.4問題四的求解基于第二問得出的旅游行程表。我們對其進行優(yōu)化。由于題目給出了約束條件，旅游時間不超過5天，也就是120小時，所以我們將行程劃分為21部分（包括10個景點和11條線路）。然后統(tǒng)計出每一部分所要花費的時

24、間，如下表所示：表六：各地花費時間表（單位：小時）徐州常州西安太原青島舟山1.529.514719.521.5武漢九江黃山北京洛陽2121.517.513.54徐州常州常州西安西安太原太原青島青島舟山舟山武漢620.751.251.52武漢九江九江黃山黃山北京北京洛陽洛陽徐州51021.57.5由上表可以看出，常州、舟山、九江和武漢所花費的時間占10個旅游景點的前4位，這4個景點的總時間大約為93.5小時，但是根據(jù)路程上所花的時間來看，武漢所花的時間要少于黃山，所以先不考慮常州、黃山、九江、舟山這四個景點。然后，考慮到如果從洛陽開始出發(fā)，沒有飛機能夠直達，早上出發(fā)會遇到住宿的問題，從而浪費時間

25、，然而從北京開始出發(fā)能夠避免此問題，所以從北京出發(fā)對其余的景點根據(jù)最短路徑重新安排行程。表七：問題四行程估計表（其余數(shù)據(jù)參見附錄IV）日期時間行程價格（元）5月1日8:009:30整理行裝09:3010:45乘坐KN2904班次飛機（徐州北京）69010:4511:30乘坐出租車到八達嶺4011:3014:30游覽八達嶺4514:3015:15乘坐出租車返回4015:1516:40乘坐MU743班次飛機（北京青島）61816:4022:00游覽青島市022:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐出租車到嶗山風景區(qū)408:0014:00游覽嶗山15014:

26、0015:00乘坐出租車返回4015:0016:40乘坐SC4607班次飛機（青島太原）69016:4017:40乘坐出租車到達喬家大院4017:4022:00游覽祁縣022:008:00住宿于平遙怡興驛同?？蜅?8經(jīng)過計算，新的旅游行程所花費的時間大約為91小時，與題目給出的120小時還有很大的差距，所以我們重新旅游行程表進行優(yōu)化，對常州、舟山、九江和黃山這四個旅游景點進行分析，安排行程。發(fā)現(xiàn)只有添加常州這個景點對時間安排最合理，所以設(shè)計出如下行程表：表八：問題四行程表（其余答案參見附錄III）日期時間行程價格（元）5月1日8:009:30整理行裝09:3010:45乘坐KN2904班次飛機

27、（徐州北京）69010:4511:30乘坐出租車到八達嶺4011:3014:30游覽八達嶺4514:3015:15乘坐出租車返回4015:1516:40乘坐MU743班次飛機（北京青島）61816:4022:00游覽青島市022:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐出租車到嶗山風景區(qū)408:0014:00游覽嶗山15014:0015:00乘坐出租車返回4015:0016:40乘坐SC4607班次飛機（青島太原）69016:4017:40乘坐出租車到達喬家大院4017:4022:00游覽祁縣0并得出旅游時間為110小時。由上面結(jié)果可以在中國地圖上模擬出最

28、短路線，如下：圖五：問題四模擬路徑圖5.5問題五的求解基于第三問得出的旅游行程表，結(jié)合第四問的數(shù)據(jù)，對其進行優(yōu)化。由于題目給出了約束條件，旅游經(jīng)費不超過2000元和旅游時間不超過5天，也就是120小時，所以我們將行程劃分為21部分（包括10個景點和11條線路）。根據(jù)表三和表六的數(shù)據(jù)，先不考慮花費經(jīng)費最大的四個景點和花費時間最長的四個景點，其中有重復(fù)，發(fā)現(xiàn)還剩下五個景點，即西安、北京、祁縣、洛陽和青島。若根據(jù)第四問的行程表從北京開始出發(fā)所花費的經(jīng)費太大，不能合理安排路徑，所以根據(jù)第三問的行程，從青島開始出發(fā)。然后根據(jù)北京和洛陽的在景點的最短停留時間，并且這兩座城市之間有合適的班機，所以我們決定將

29、北京往祁縣的路線改為由北京飛往洛陽，然后再根據(jù)第三問的路徑進行優(yōu)化從洛陽到祁縣再返回徐州。最后，再進行優(yōu)化，設(shè)計出如下行程表：表九：問題五行程表（其余答案參見附錄III）日期時間行程價格(元)5月1日8:0023:30整理行裝023:308:00乘坐K1025次列車（徐州青島）705月2日8:009:00乘坐311W公交車到嶗山風景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311W公交車返回718:0020:00游覽青島市020:005:30乘坐T26次列車（青島北京）1165月3日5:307:00休息07:008:00乘坐地鐵2號線和公交車到八達嶺208:0012:00游覽

30、八達嶺4512:0013:00乘坐出租車返回3013:0014:30乘坐MU5695班次飛機（北京洛陽）74914:3015:00乘坐出租車到達龍門石窟3015:0018:00游覽龍門石窟12018:0022:00游覽洛陽市022:001:00休息05月4日1:006:30乘坐K245次列車（洛陽西安）556:307:00休息07:008:00乘坐81W公交車到達秦始皇兵馬俑18:0014:00游覽秦始皇兵馬俑9014:0015:00乘坐公交車返回115:0021:00游覽西安市021:006:30乘坐2670次列車（西安祁縣）39并得出總旅游費用為1995元，總旅游時間為115小時。由上面結(jié)

31、果可以在中國地圖上模擬出最短路線，如下：圖六：問題五模擬路徑圖模型評價與改進6.1模型的優(yōu)點1)在解題過程中，使用軟件進行編程，在分析和運算方面有較高的精度，時間大大縮短，使答案更加明了。2)合理恰當?shù)氖褂昧吮砀窈蛨D形，使數(shù)據(jù)的體現(xiàn)和意思的表達更加清晰。3)答案詳細、具體，并且接近實際，具有較強的可操作性。6.2模型的缺點1)沒有根據(jù)實際路況來解題，與實際存在很大的差異。 2)大多數(shù)數(shù)據(jù)來自于網(wǎng)絡(luò)，數(shù)據(jù)缺乏準確性。3)對問題五沒有采用更精確的方法進行預(yù)測，缺乏合理性。參考文獻1費浦生，數(shù)學建模及其基礎(chǔ)知識詳解，武漢：武漢大學出版社，2006.2程世娟，盧偉，陳虬，基于蟻群算法的最短路徑搜索方法

32、研究，科學技術(shù)與工程，21期：P63，2007。3孫小軍，焦建民，一種求解最少時間最小費用路問題的算法，計算機工程與科學，07期：P20，2008。4金詩銘，魯斌，崔占森，走遍全中國，/view/c6a3fd136c175f0e7cd13735.html，2011年5月1日。5參考網(wǎng)站：/train/7參考網(wǎng)站：/travel/附錄附錄I附表1：預(yù)選的十個省市旅游景點省市景點名稱在景點的最短停留時間江蘇常州市恐龍園4小時山東青島市嶗山6小時北京八達嶺長城3小時山西祁縣喬家大院3小時河南洛陽市龍門石窟3小時安徽黃山市黃山7小時湖北武漢市黃鶴樓2小時陜西西安市秦始皇兵馬俑2小時江西九江市廬山7小時

33、浙江舟山市普陀山6小時附表2：11座城市的經(jīng)緯坐標地點經(jīng)度緯度徐州117.234.26常州119.9531.79青島120.3336.07北京116.4639.92祁縣112.3337.36洛陽112.4434.7黃山118.1430.19武漢114.3130.52西安108.9534.27九江115.9729.71舟山122.329.97附表3：相應(yīng)城市間的距離徐州常州青島北京祁縣洛陽徐州0401.9388.2634.36620.33507.3常州401.90476.71977.941019.41862.64青島388.2476.710594.65857.51849.77北京634.3697

34、7.94594.650514.36715.7祁縣620.331019.41857.51514.360297.11洛陽507.3862.64849.77715.7297.110黃山462.82266.66695.181096.31006.78784.59武漢518.9620.72890.721069.85791.23506.59西安877.611205.611224.431008.15497.51375.22九江523.41486.39846.731136.46935.47670.2舟山707.31305.56701.161257.971324.681156.69黃山武漢西安九江舟山徐州462.

35、82518.9877.61523.41707.31常州266.66620.721205.61486.39305.56青島695.18890.721224.43846.73701.16北京1096.31069.851008.151136.461257.97祁縣1006.78791.23497.51935.471324.68洛陽784.59506.59375.22670.21156.69黃山0407.991078.11235.64430.58武漢407.990709.48198.47838.37西安1078.11709.480905.661484.54九江235.64198.47905.66066

36、0.46舟山430.58838.371484.54660.460附錄II基本蟻群算法解決問題的程序m=11; %螞蟻個數(shù)Alpha=1; % Alpha 表征信息素重要程度的參數(shù)Beta=5; % Beta 表征啟發(fā)式因子重要程度的參數(shù)Rho=0.1; % Rho 信息素蒸發(fā)系數(shù)NC_max=1000; % NC_max 最大迭代次數(shù)Q=100; % Q 信息素增加強度系數(shù)C=load(C:Documents and SettingsAdministrator桌面jj.txt); % C n個城市的坐標，n2的矩陣D=load(C:Documents and SettingsAdministr

37、ator桌面att34.txt); %D 城市之間的參數(shù)（可以是距離、費用、時間等）n=11; %n表示問題的規(guī)模（城市個數(shù)）Eta=1./D; %Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(11,11); %Tau為信息素矩陣Tabu=zeros(11,11); %存儲并記錄路徑的生成NC=1; %迭代計數(shù)器R_best=zeros(NC_max,n); %各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的長度L_ave=zeros(NC_max,1); %各代路線的平均長度while NC=rand);to_visit=J(Select(1);Ta

38、bu(i,j)=to_visit;endendif NC=2Tabu(1,:)=R_best(NC-1,:);end%第四步：記錄本次迭代最佳路線L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_best(NC)=min(L);pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1%第五步：更新信息素Delta_Tau=zeros(n,n);for

39、i=1:mfor j=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%第六步：禁忌表清零Tabu=zeros(m,n);end%第七步：輸出結(jié)果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:)Shortest_Lengt

40、h=L_best(Pos(1)subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2)plot(L_best)hold onplot(L_ave)% 畫路線圖的子函數(shù)N=length(R);scatter(C(:,1),C(:,2);hold onplot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)hold onfor ii=2:Nplot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)hold onend解決問題的程序MODEL: SETS: CITY /

41、 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: !TIME matrix, it need not be symmetric; TIME = 032232070660280602562521528724 3220944851140735583250110840272 3209440751009141395115110101590 70857507510512011

42、0105135130 66011401007507019948065731960 280735914105701017504232706961320 6025831395120994175004671300484490 5622501151108042346707021575 521110110105652701300700967170 52884010151357316964842159670828 724272901309601320490751708280; ENDDATA N = SIZE( CITY); MIN = SUM( LINK: TIME * X); FOR( CITY( K

43、): ! It must be entered; SUM( CITY( I)| I #NE# K: X( I, K) = 1; ! It must be departed; SUM( CITY( J)| J #NE# K: X( K, J) = 1; ! Weak form of the subtour breaking constraints; ! These are not very powerful for large problems; FOR( CITY( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2

44、) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); ! Make the Xs 0/1; FOR( LINK: BIN( X); ! For the first and last stop we know.; FOR( CITY( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );附錄III問題一答案如下：日期時間行程價格（元）5月1日8:3015:45乘坐L8449次列車（徐州常州）3416:0021:00游覽常州市021:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐公交

45、去中華恐龍園48:0016:00游覽中華恐龍園16016:0017:00乘坐公交返回417:0022:30游覽常州市022:305:20乘坐K75次列車（常州寧波）735月3日5:308:00乘坐758W公交到白峰碼頭乘坐船到普陀山168:0014:00游覽普陀山20014:0016:00返回寧波站1616:0022:15乘坐K8500次列車（寧波宣城）6322:151:30候車05月4日1:305:00乘坐2521次列車（宣城黃山）265:006:30休息06:307:30乘坐公交去黃山風景區(qū)158:0015:00游覽黃山23015:0016:00乘坐公交車返回黃山站1516:0018:30

46、游覽黃山市018:3023:30乘坐K67次列車（黃山鷹潭）515月5日0:304:00乘坐K253次列車（鷹潭九江）424:007:00休息07:008:00乘坐公交車到廬山風景區(qū)108:0018:00游覽廬山18018:0019:00乘坐公交車返回九江站1019:0024:00游覽九江市05月6日0:001:50休息01:506:30乘坐K924次列車（九江武漢）516:309:00游覽武漢市09:009:15乘坐D3221次列車（武漢武昌）69:1510:30乘坐43W公交車到黃鶴樓210:3012:30游覽黃鶴樓8012:3013:45乘坐43W公交車返回213:4515:30游覽武昌

47、市015:3024:30乘坐K244次列車（武昌洛陽）925月7日0:307:00住宿于洛陽家佳公寓酒店807:008:00乘坐81W公交車到龍門石窟28:0014:00游覽龍門石窟12014:0015:00乘坐81W公交車返回215:0020:00乘坐K128次列車（洛陽西安）5520:0021:00乘坐306W公交車到秦始皇兵馬俑221:008:00住宿于西安美寶賓館后宰門店1385月8日8:0015:00游覽秦始皇兵馬俑9015:0016:00乘坐306W公交車返回216:0021:00游覽西安市021:006:30乘坐2670次列車（西安祁縣）395月9日7:008:00乘坐公交車到喬

48、家大院28:0012:00游覽喬家大院4012:0013:00乘坐公交車返回213:304:00乘坐2604次列車（祁縣北京）945月10日4:007:00休息07:008:00乘坐地鐵2號線和公交車到八達嶺208:0012:00游覽八達嶺4512:0013:00乘坐地鐵2號線和公交車返回2013:0022:00乘坐長途汽車（北京青島）15822:006:45住宿于青島多維空間精品套房1025月11日6:458:00乘坐311W公交車到嶗山風景區(qū)78:0015:00游覽嶗山15016:0016:15乘坐311W公交車返回716:151:15乘坐K208次列車（青島徐州）99吃飯等其它費用660

49、總旅游費用3438總時間257小時問題二答案如下：日期時間行程價格（元）5月1日8:009:30整理行裝09:3015:30乘坐K55次列車（徐州常州）7015:3021:00游覽常州市021:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐出租車到中華恐龍園408:0016:00游覽中華恐龍園16016:0017:00乘坐出租車返回4017:0021:00游覽常州市021:0023:00乘坐MU5638班次飛機（常州西安）111023:0024:00乘坐出租車到秦始皇兵馬俑405月3日0:008:00住宿于西安美寶賓館后宰門店1388:0010:00游覽秦始皇兵

50、馬俑9010:0011:00乘坐出租車返回4011:0013:00游覽西安013:0013:45乘坐CZ6470班次飛機（西安太原）119013:4515:00乘坐出租車到喬家大院4015:0018:00游覽喬家大院4018:0019:00乘坐出租車返回4019:0020:45游覽太原020:4522:00乘坐CA4608班次飛機（太原青島）66622:0023:00乘坐出租車到達嶗山風景區(qū)4023:008:00住宿于青島新天橋賓館885月4日8:0016:30游覽嶗山15016:3017:30乘坐出租車返回4017:3019:00乘坐HU7842班次飛機（青島寧波）35519:0021:00

51、乘坐出租車到普陀山風景區(qū)4021:008:00住宿于舟山華融大酒店1585月5日8:0014:30游覽普陀山16014:3016:30乘坐出租車返回4016:3018:30乘坐CZ3336班次飛機（寧波武漢）65718:3022:00游覽武漢市022:007:00住宿于武漢鄂鋼大酒店895月6日7:009:00乘坐出租車到黃鶴樓409:0013:30游覽黃鶴樓8013:3015:30乘坐出租車返回4015:3020:30乘坐K752次列車（武漢九江）5120:307:00住宿于九江悠然快捷酒店1185月7日7:008:00乘坐出租車到廬山風景區(qū)408:0015:00游覽廬山風景區(qū)18015:0

52、016:00乘坐出租車返回4016:0018:00游覽九江市018:0021:30乘坐K665次列車（九江鷹潭）4421:3023:30候車023:304:00乘坐K156次列車（鷹潭黃山）515月8日4:007:00休息07:008:00乘坐出租車到黃山風景區(qū)408:0018:00游覽黃山23018:0019:00乘坐出租車返回4019:0021:30游覽黃山市021:3023:30乘坐CA1152班次飛機（黃山北京）109023:307:00住宿于北京佳號賓館1685月9日7:008:00乘坐出租車八達嶺408:0012:00游覽八達嶺4512:0013:00乘坐出租車返回4013:001

53、4:30乘坐MU5695班次飛機（北京洛陽）74914:3015:00乘坐出租車到龍門石窟4015:0018:00游覽龍門石窟12018:0018:30乘坐出租車返回4018:302:00乘坐K1132次列車（洛陽徐州）70吃飯等其它費用540總旅游費用9577總時間210小時問題三的答案如下：日期時間行程價格（元）5月1日8:0023:30整理行裝023:308:00乘坐K1025次列車（徐州青島）705月2日8:009:00乘坐311W公交車到嶗山風景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311W公交車返回718:0020:00游覽青島市020:005:30乘坐T26

54、次列車（青島北京）1165月3日5:307:00休息07:008:00乘坐地鐵2號線和公交車到八達嶺208:0013:00游覽八達嶺4513:0014:00乘坐地鐵2號線和公交車返回2014:0022:00游覽北京市022:0023:30休息023:3013:30乘坐2603次列車（北京祁縣）945月4日13:3014:30乘坐公交車到喬家大院214:3018:00游覽喬家大院4018:0019:00乘坐公交車返回219:0020:30游覽祁縣020:307:30乘坐1095次列車（祁縣西安）415月5日7:308:30乘坐306W公交車到秦始皇兵馬俑28:3015:30游覽秦始皇兵馬俑901

55、5:3016:30乘坐306W公交車返回216:3022:00游覽西安市022:0024:30休息05月6日0:305:00乘坐T198次列車（西安洛陽）555:007:00休息07:008:00乘坐81W公交車到龍門石窟28:0013:00游覽龍門石窟12013:0014:00乘坐81W公交車返回215:0022:30游覽洛陽市022:307:00乘坐K792次列車（洛陽武昌）875月7日7:008:00乘坐43W公交車到黃鶴樓28:0012:00游覽黃鶴樓8012:0013:00乘坐43W公交車返回213:0015:30游覽武昌市015:3020:30乘坐K752次列車(武昌九江)5120

56、:3021:30乘坐公交車到廬山風景區(qū)1021:308:00住宿于九江悠然快捷酒店1185月8日8:0016:00游覽廬山18016:0017:00乘坐公交車返回1017:005:30乘坐K612次列車（九江徐州）87吃飯等其它費用480總旅游費用1994總時間189小時問題四的答案如下：日期時間行程價格（元）5月1日8:009:30整理行裝09:3010:45乘坐KN2904班次飛機（徐州北京）69010:4511:30乘坐出租車到八達嶺4011:3014:30游覽八達嶺4514:3015:15乘坐出租車返回4015:1516:40乘坐MU743班次飛機（北京青島）61816:4022:00

57、游覽青島市022:007:00住宿于常州藍色快舟營銷人連鎖旅店1205月2日7:008:00乘坐出租車到嶗山風景區(qū)408:0014:00游覽嶗山15014:0015:00乘坐出租車返回4015:0016:40乘坐SC4607班次飛機（青島太原）69016:4017:40乘坐出租車到達喬家大院4017:4022:00游覽祁縣022:008:00住宿于平遙怡興驛同?？蜅?85月3日8:0011:00游覽喬家大院4011:0012:00乘坐出租車返回4012:0013:30乘坐CZ6288班次飛機（太原武漢）73813:3014:00游覽武漢市014:0015:00乘坐出租車到達黃鶴樓4015:00

58、17:00游覽黃鶴樓8017:0018:00乘坐出租車返回4018:0019:30乘坐CZ3889班次飛機（武漢西安）60519:3021:00游覽西安市021:0022:00乘坐出租車到達秦始皇兵馬俑4022:008:00住宿于西安美寶賓館后宰門店1385月4日8:0010:30游覽秦始皇兵馬俑9010:3011:30乘坐出租車返回4011:3013:30乘坐G2018次列車（西安洛陽）18413:3014:00游覽洛陽市014:0015:00乘坐出租車到達龍門石窟4015:0018:00游覽龍門石窟12018:0019:00乘坐出租車返回4019:0021:00游覽洛陽市021:009:3

59、0乘坐K736次列車（洛陽常州）1255月5日9:3010:00乘坐出租車到達中華恐龍園4010:0014:30游覽中華恐龍園16014:3015:00乘坐出租車返回4015:0022:00乘坐K294次列車（常州徐州）70吃飯等其它費用300總旅游費用5621總時間110小時問題五的答案如下：日期時間行程價格(元)5月1日8:0023:30整理行裝023:308:00乘坐K1025次列車（徐州青島）705月2日8:009:00乘坐311W公交車到嶗山風景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311W公交車返回718:0020:00游覽青島市020:005:30乘坐T26次列車（青島北京）1165月3日5:307:00休息07:008:00乘坐地鐵2號線和公交車到八達嶺208:0012:00游覽八達嶺4512:0013:00乘坐出租車返回3013:0014:30乘坐MU5695班次飛機（北京洛陽）74914: