數(shù)學(xué)建模論文旅游線路的優(yōu)化設(shè)計(jì)

1、一、 問(wèn)題重述隨著人們的生活不斷提高，旅游已成為提高人們生活質(zhì)量的重要活動(dòng)。江蘇徐州有一位旅游愛(ài)好者打算在今年的五月一日早上8點(diǎn)之后出發(fā)，到全國(guó)一些著名景點(diǎn)旅游，最后回到徐州。由于跟團(tuán)旅游會(huì)受到若干限制，他(她)打算自己作為背包客出游。他預(yù)選了十個(gè)省市旅游景點(diǎn)，如附表1（見(jiàn)附錄i）所示。假設(shè)(a)城際交通出行可以乘火車(含高鐵)、長(zhǎng)途汽車或飛機(jī)（不允許包車或包機(jī)），并且車票或機(jī)票可預(yù)訂到。(b)市內(nèi)交通出行可乘公交車(含專線大巴、小巴)、地鐵或出租車。(c)旅游費(fèi)用以網(wǎng)上公布為準(zhǔn)，具體包括交通費(fèi)、住宿費(fèi)、景點(diǎn)門票(第一門票)。晚上20：00至次日早晨7：00之間，如果在某地停留超過(guò)6小時(shí)，必須

2、住宿，住宿費(fèi)用不超過(guò)200元/天。吃飯等其它費(fèi)用60元/天。(d)假設(shè)景點(diǎn)的開(kāi)放時(shí)間為8:00至18:00。問(wèn)題：根據(jù)以上要求，針對(duì)如下的幾種情況，為該旅游愛(ài)好者設(shè)計(jì)詳細(xì)的行程表，該行程表應(yīng)包括具體的交通信息(車次、航班號(hào)、起止時(shí)間、票價(jià)等)、賓館地點(diǎ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ì)旅游行程表

3、。(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)題假設(shè)1、忽略乘坐出租車時(shí)經(jīng)過(guò)收費(fèi)路段所交的費(fèi)用；2、在每個(gè)城市中停留時(shí)，難免會(huì)遇到等車、堵車等延時(shí)情況，在此問(wèn)題中我們不做考慮；3、所有旅館都未客滿，并且忽略從旅館到火車站或景點(diǎn)的時(shí)間；4、列車車次和飛機(jī)航班沒(méi)有晚點(diǎn)等情況發(fā)生；5、列車和飛機(jī)的票足夠，沒(méi)有買不到票的情況發(fā)生；6、景點(diǎn)的開(kāi)放，列車和航班的運(yùn)營(yíng)不受天氣的影響；7、繪圖時(shí)，經(jīng)線和緯線近似平行分布；8、將城市和路徑的關(guān)系

4、轉(zhuǎn)化為圖論問(wèn)題；9、在時(shí)間的認(rèn)識(shí)上，我們把當(dāng)天的8點(diǎn)至次日的8點(diǎn)作為一天。三、 符號(hào)說(shuō)明有向圖矩陣城市路徑要經(jīng)過(guò)的城市總數(shù)任意兩城市之間的距離是否經(jīng)過(guò)兩座城市路徑上的信息量啟發(fā)函數(shù)信息啟發(fā)式因子期望啟發(fā)式因子螞蟻在時(shí)刻由城市轉(zhuǎn)向城市的轉(zhuǎn)移概率第只螞蟻的禁忌搜索表信息素?fù)]發(fā)系數(shù)時(shí)刻螞蟻在路徑上留下的信息素量到目前為止所找到的全局最短路徑長(zhǎng)度螞蟻攜帶的信息素量本次循環(huán)中第只螞蟻所走的路程長(zhǎng)度螞蟻的總數(shù)量螞蟻的編號(hào)所記錄的循環(huán)次數(shù)最大循環(huán)次數(shù)四、 問(wèn)題分析4.1問(wèn)題一的分析針對(duì)問(wèn)題一，要求求出將旅游景點(diǎn)全游覽完，所需的最少旅游費(fèi)用。這和問(wèn)題,即旅行商問(wèn)題有些類似，所以本文將問(wèn)題向問(wèn)題進(jìn)行一定的轉(zhuǎn)化，

5、從而進(jìn)行求解。因?yàn)檫\(yùn)用傳統(tǒng)的動(dòng)態(tài)規(guī)劃解法，解法的空間復(fù)雜性和時(shí)間復(fù)雜性都十分龐大，不利于求解，所以采用蟻群算法，通過(guò)計(jì)算機(jī)軟件進(jìn)行編程得到路程最短的旅行路線。因題目要求時(shí)間不限，用最少的旅游費(fèi)用游覽全部景點(diǎn)，而考慮到不同交通工具的速度和票價(jià)都不相同，各個(gè)旅館的住宿費(fèi)用也不相同，所以我們對(duì)其行程進(jìn)行詳細(xì)的安排，盡量減少其在交通和住宿上的費(fèi)用，減少不必要的花費(fèi)。最后得出一個(gè)最少旅游費(fèi)用的旅游行程表。4.2問(wèn)題二的分析針對(duì)問(wèn)題二，要求求出將旅游景點(diǎn)全游覽完，所需的最少時(shí)間。因?yàn)榭紤]到交通工具的不同導(dǎo)致時(shí)間上的差異問(wèn)題，所以僅用問(wèn)題一的模型不能求解。但是由于任意兩座城市之間都能相連接起來(lái)，且每座城市只

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

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

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

9、向圖。其中稱為圖的頂點(diǎn)集，中的每一個(gè)元素稱為該圖的一個(gè)頂點(diǎn)，在該題中表示城市；稱為圖的弧集，中的每個(gè)元素稱為該圖的一條從到的弧，在此題中表示各個(gè)城市兩兩連線的集合。1設(shè)城市個(gè)數(shù)為，表示兩個(gè)城市與之間的距離，0或1（1表示走過(guò)城市到城市的路，0表示沒(méi)有選擇走這條路）。本題可以向問(wèn)題進(jìn)行轉(zhuǎn)化，則問(wèn)題的數(shù)學(xué)模型為：5.1.2建立螞蟻算法的數(shù)學(xué)模型(1)狀態(tài)轉(zhuǎn)移規(guī)則因?yàn)槲浵伈荒苤貜?fù)經(jīng)過(guò)一個(gè)城市，所以建立禁忌表來(lái)記錄螞蟻?zhàn)哌^(guò)的城市，禁忌表隨著時(shí)間做動(dòng)態(tài)變化。建立螞蟻由城市轉(zhuǎn)移到城市的狀態(tài)轉(zhuǎn)移概率如下： （1）上式中為信息啟發(fā)式因子，表示路徑的相對(duì)重要性，是對(duì)所積累的信息素影響作用的一個(gè)加權(quán)值；為期望啟發(fā)

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

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

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

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

14、：?jiǎn)栴}一行程表（其余答案參見(jiàn)附錄iii）日期時(shí)間行程價(jià)格（元）5月1日8:3015:45乘坐l8449次列車（徐州常州）3416:0021:00游覽常州市021:007:00住宿于常州藍(lán)色快舟營(yíng)銷人連鎖旅店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返回寧波站1616:0022:15乘坐k8500次列車（寧波宣城）

15、6322:151:30候車0并且得出最少的總旅游費(fèi)用為3438元。5.2問(wèn)題二的求解5.2.1模型的建立基于第一問(wèn)的模型，我們稍作改進(jìn)。因?yàn)榈诙?wèn)要求安排時(shí)間最短的旅游行程表，而費(fèi)用不限，由于飛機(jī)費(fèi)用過(guò)大，所以在第一問(wèn)我們未做考慮，但由于其時(shí)間比火車和汽車都要快的多，所以我們把飛機(jī)作為首要考慮對(duì)象加入第二問(wèn)中。第一問(wèn)的模型中，是把任意兩點(diǎn)之間的距離作為參數(shù)，從而進(jìn)行求解，得出最短路徑。在第二問(wèn)中，我們把任意兩點(diǎn)之間的所乘坐的交通工具的最短時(shí)間作為參數(shù)，建立時(shí)間最優(yōu)化模型,結(jié)合軟件（程序見(jiàn)附錄iii）求出經(jīng)過(guò)所有旅游景點(diǎn)的花費(fèi)時(shí)間最短的路線。5.2.2模型的解釋在模型中，我們引入0-1變量，若通

16、過(guò)兩城市之間的路徑，則賦值為1；若不通過(guò)兩城市之間的路徑，則賦值為0。對(duì)于無(wú)向圖的最短時(shí)間路徑問(wèn)題，可以這樣理解，從點(diǎn)到點(diǎn)和點(diǎn)到點(diǎn)的邊，看成有向弧，其他各條邊均看成有不同方向的雙弧，因此，可以按照前面介紹有向圖的最短時(shí)間路徑問(wèn)題來(lái)編程。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.0000x(5,3)1.000000100.0000x(6

17、,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即最短時(shí)間路徑：對(duì)上述結(jié)果進(jìn)行處理，根據(jù)城市編號(hào)求出最優(yōu)解為：徐州常州西安祁縣青島舟山武漢九江黃山北京洛陽(yáng)徐州由上面結(jié)果可以在中國(guó)地圖上模擬出最短路線，如下：圖三：?jiǎn)栴}二模擬路徑圖5.2.4設(shè)計(jì)旅游行程表和求出總費(fèi)用我們根據(jù)最優(yōu)化模型得出游覽全部景點(diǎn)的最短時(shí)間路徑，在得出的最短時(shí)間路徑的基礎(chǔ)上，我們通過(guò)查閱飛機(jī)票價(jià)、班次、運(yùn)營(yíng)時(shí)間，賓

18、館價(jià)格、名稱等大量資料和數(shù)據(jù)，盡可能的減少其在行程上的花費(fèi)，設(shè)計(jì)出如下旅游行程表：表二：?jiǎn)栴}二的行程表（其余答案參見(jiàn)附錄iii）日期時(shí)間行程價(jià)格（元）5月1日8:009:30整理行裝09:3015:30乘坐k55次列車（徐州常州）7015:3021:00游覽常州市021:007:00住宿于常州藍(lán)色快舟營(yíng)銷人連鎖旅店1205月2日7:008:00乘坐出租車到中華恐龍園408:0016:00游覽中華恐龍園16016:0017:00乘坐出租車返回4017:0021:00游覽常州市021:0023:00乘坐mu5638班次飛機(jī)（常州西安）111023:0024:00乘坐出租車到秦始皇兵馬俑405月3日

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

20、9935792洛陽(yáng)西安西安祁縣祁縣北京北京青島青島徐州55399415899由上表可以看出，黃山、普陀、九江和常州所花費(fèi)的經(jīng)費(fèi)占10個(gè)旅游景點(diǎn)的前4位，這四個(gè)景點(diǎn)的總經(jīng)費(fèi)大約為915元，所以先不考慮黃山、普陀、九江和常州這四個(gè)景點(diǎn)。然后使其從青島開(kāi)始出發(fā)，盡量避免這四個(gè)景點(diǎn)。對(duì)其余的景點(diǎn)根據(jù)最短路徑重新安排行程，避免住宿，減少不必要的花費(fèi)。表四：?jiǎn)栴}三行程估計(jì)表（其余數(shù)據(jù)參見(jiàn)附錄iv）日期時(shí)間行程價(jià)格（元）5月1日8:0023:30整理行裝023:308:00乘坐k1025次列車（徐州青島）705月2日8:009:00乘坐311w公交車到嶗山風(fēng)景區(qū)79:0017:00游覽嶗山15017:001

21、8:00乘坐311w公交車返回718:0020:00游覽青島市020:005:30乘坐t26次列車（青島北京）1165月3日5:307:00休息07:008:00乘坐地鐵2號(hào)線和公交車到八達(dá)嶺208:0013:00游覽八達(dá)嶺4513:0014:00乘坐地鐵2號(hào)線和公交車返回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)過(guò)計(jì)算，新的旅游行程所花費(fèi)的經(jīng)費(fèi)大約為1517元，與題目

22、給出的2000元還有很大的差距，所以我們重新旅游行程表進(jìn)行優(yōu)化，對(duì)黃山、普陀、九江和常州這四個(gè)旅游景點(diǎn)進(jìn)行分析，安排行程。發(fā)現(xiàn)只有添加九江這個(gè)景點(diǎn)旅游費(fèi)用不會(huì)超支，所以設(shè)計(jì)出如下行程表：表五：?jiǎn)栴}三行程表（其余答案參見(jiàn)附錄iii）日期時(shí)間行程價(jià)格（元）5月1日8:0023:30整理行裝023:308:00乘坐k1025次列車（徐州青島）705月2日8:009:00乘坐311w公交車到嶗山風(fēng)景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311w公交車返回718:0020:00游覽青島市020:005:30乘坐t26次列車（青島北京）1165月3日5:307:00休息07:008:

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

24、州常州西安太原青島舟山1.529.514719.521.5武漢九江黃山北京洛陽(yáng)2121.517.513.54徐州常州常州西安西安太原太原青島青島舟山舟山武漢620.751.251.52武漢九江九江黃山黃山北京北京洛陽(yáng)洛陽(yáng)徐州51021.57.5由上表可以看出，常州、舟山、九江和武漢所花費(fèi)的時(shí)間占10個(gè)旅游景點(diǎn)的前4位，這4個(gè)景點(diǎn)的總時(shí)間大約為93.5小時(shí)，但是根據(jù)路程上所花的時(shí)間來(lái)看，武漢所花的時(shí)間要少于黃山，所以先不考慮常州、黃山、九江、舟山這四個(gè)景點(diǎn)。然后，考慮到如果從洛陽(yáng)開(kāi)始出發(fā)，沒(méi)有飛機(jī)能夠直達(dá)，早上出發(fā)會(huì)遇到住宿的問(wèn)題，從而浪費(fèi)時(shí)間，然而從北京開(kāi)始出發(fā)能夠避免此問(wèn)題，所以從北京出發(fā)對(duì)

25、其余的景點(diǎn)根據(jù)最短路徑重新安排行程。表七：?jiǎn)栴}四行程估計(jì)表（其余數(shù)據(jù)參見(jiàn)附錄iv）日期時(shí)間行程價(jià)格（元）5月1日8:009:30整理行裝09:3010:45乘坐kn2904班次飛機(jī)（徐州北京）69010:4511:30乘坐出租車到八達(dá)嶺4011:3014:30游覽八達(dá)嶺4514:3015:15乘坐出租車返回4015:1516:40乘坐mu743班次飛機(jī)（北京青島）61816:4022:00游覽青島市022:007:00住宿于常州藍(lán)色快舟營(yíng)銷人連鎖旅店1205月2日7:008:00乘坐出租車到嶗山風(fēng)景區(qū)408:0014:00游覽嶗山15014:0015:00乘坐出租車返回4015:0016:40

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

27、達(dá)嶺4011:3014:30游覽八達(dá)嶺4514:3015:15乘坐出租車返回4015:1516:40乘坐mu743班次飛機(jī)（北京青島）61816:4022:00游覽青島市022:007:00住宿于常州藍(lán)色快舟營(yíng)銷人連鎖旅店1205月2日7:008:00乘坐出租車到嶗山風(fēng)景區(qū)408:0014:00游覽嶗山15014:0015:00乘坐出租車返回4015:0016:40乘坐sc4607班次飛機(jī)（青島太原）69016:4017:40乘坐出租車到達(dá)喬家大院4017:4022:00游覽祁縣0并得出旅游時(shí)間為110小時(shí)。由上面結(jié)果可以在中國(guó)地圖上模擬出最短路線，如下：圖五：?jiǎn)栴}四模擬路徑圖5.5問(wèn)題五的求

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

29、的路徑進(jìn)行優(yōu)化從洛陽(yáng)到祁縣再返回徐州。最后，再進(jìn)行優(yōu)化，設(shè)計(jì)出如下行程表：表九：?jiǎn)栴}五行程表（其余答案參見(jiàn)附錄iii）日期時(shí)間行程價(jià)格(元)5月1日8:0023:30整理行裝023:308:00乘坐k1025次列車（徐州青島）705月2日8:009:00乘坐311w公交車到嶗山風(fēng)景區(qū)79:0017:00游覽嶗山15017:0018:00乘坐311w公交車返回718:0020:00游覽青島市020:005:30乘坐t26次列車（青島北京）1165月3日5:307:00休息07:008:00乘坐地鐵2號(hào)線和公交車到八達(dá)嶺208:0012:00游覽八達(dá)嶺4512:0013:00乘坐出租車返回3013

30、:0014:30乘坐mu5695班次飛機(jī)（北京洛陽(yáng)）74914:3015:00乘坐出租車到達(dá)龍門石窟3015:0018:00游覽龍門石窟12018:0022:00游覽洛陽(yáng)市022:001:00休息05月4日1:006:30乘坐k245次列車（洛陽(yáng)西安）556:307:00休息07:008:00乘坐81w公交車到達(dá)秦始皇兵馬俑18:0014:00游覽秦始皇兵馬俑9014:0015:00乘坐公交車返回115:0021:00游覽西安市021:006:30乘坐2670次列車（西安祁縣）39并得出總旅游費(fèi)用為1995元，總旅游時(shí)間為115小時(shí)。由上面結(jié)果可以在中國(guó)地圖上模擬出最短路線，如下：圖六：?jiǎn)栴}五

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

32、007。3孫小軍，焦建民，一種求解最少時(shí)間最小費(fèi)用路問(wèn)題的算法，計(jì)算機(jī)工程與科學(xué)，07期：p20，2008。4金詩(shī)銘，魯斌，崔占森，走遍全中國(guó)，5參考網(wǎng)站：6參考網(wǎng)站：7參考網(wǎng)站：附錄附錄i附表1：預(yù)選的十個(gè)省市旅游景點(diǎn)省市景點(diǎn)名稱在景點(diǎn)的最短停留時(shí)間江蘇常州市恐龍園4小時(shí)山東青島市嶗山6小時(shí)北京八達(dá)嶺長(zhǎng)城3小時(shí)山西祁縣喬家大院3小時(shí)河南洛陽(yáng)市龍門石窟3小時(shí)安徽黃山市黃山7小時(shí)湖北武漢市黃鶴樓2小時(shí)陜西西安市秦始皇兵馬俑2小時(shí)江西九江市廬山7小時(shí)浙江舟山市普陀山6小時(shí)附表2：11座城市的經(jīng)緯坐標(biāo)地點(diǎn)經(jīng)度緯度徐州117.234.26常州119.9531.79青島120.3336.07北京116.

33、4639.92祁縣112.3337.36洛陽(yáng)112.4434.7黃山118.1430.19武漢114.3130.52西安108.9534.27九江115.9729.71舟山122.329.97附表3：相應(yīng)城市間的距離徐州常州青島北京祁縣洛陽(yáng)徐州0401.9388.2634.36620.33507.3常州401.90476.71977.941019.41862.64青島388.2476.710594.65857.51849.77北京634.36977.94594.650514.36715.7祁縣620.331019.41857.51514.360297.11洛陽(yáng)507.3862.64849.77

34、715.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.82518.9877.61523.41707.31常州266.66620.721205.61486.39305.56青島695.18890.72122

35、4.43846.73701.16北京1096.31069.851008.151136.461257.97祁縣1006.78791.23497.51935.471324.68洛陽(yáng)784.59506.59375.22670.21156.69黃山0407.991078.11235.64430.58武漢407.990709.48198.47838.37西安1078.11709.480905.661484.54九江235.64198.47905.660660.46舟山430.58838.371484.54660.460附錄ii基本蟻群算法解決問(wèn)題的程序m=11; %螞蟻個(gè)數(shù)alpha=1; % alph

36、a 表征信息素重要程度的參數(shù)beta=5; % beta 表征啟發(fā)式因子重要程度的參數(shù)rho=0.1; % rho 信息素蒸發(fā)系數(shù)nc_max=1000; % nc_max 最大迭代次數(shù)q=100; % q 信息素增加強(qiáng)度系數(shù)c=load(c:documents and settingsadministrator桌面jj.txt); % c n個(gè)城市的坐標(biāo)，n2的矩陣d=load(c:documents and settingsadministrator桌面att34.txt); %d 城市之間的參數(shù)（可以是距離、費(fèi)用、時(shí)間等）n=11; %n表示問(wèn)題的規(guī)模（城市個(gè)數(shù)）eta=1./d; %e

37、ta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)tau=ones(11,11); %tau為信息素矩陣tabu=zeros(11,11); %存儲(chǔ)并記錄路徑的生成nc=1; %迭代計(jì)數(shù)器r_best=zeros(nc_max,n); %各代最佳路線l_best=inf.*ones(nc_max,1);%各代最佳路線的長(zhǎng)度l_ave=zeros(nc_max,1); %各代路線的平均長(zhǎng)度while nc=rand);to_visit=j(select(1);tabu(i,j)=to_visit;endendif nc=2tabu(1,:)=r_best(nc-1,:);end%第四步：記錄本次迭代最佳路線l=

38、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 i=1:mfor j=1:(n-1)delta_tau(tabu(i,j),tabu(i,j+1)=delta_tau(tabu(i,j),tabu(

39、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_length=l_best(pos(1)subplot(1,2,1)drawroute(c,shortest_route)subplot(1,2,2)plot(

40、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解決問(wèn)題的程序model: sets: city / 1. 11/: u; ! u( i) = sequence no. of city; link( city, city): time, ! the

41、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 708575075105120110105135130 66011401007507019948065731960 280735914105701017504232706961320

42、6025831395120994175004671300484490 5622501151108042346707021575 521110110105652701300700967170 52884010151357316964842159670828 724272901309601320490751708280; enddata n = size( city); min = sum( link: time * x); for( city( k): ! it must be entered; sum( city( i)| i #ne# k: x( i, k) = 1; ! it must b

43、e 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) * ( 1 - x( k, j) + ( n - 3) * x( j, k) ); ); ! make the xs 0/1; for( link

44、: 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問(wèn)題一答案如下：日期時(shí)間行程價(jià)格（元）5月1日8:3015:45乘坐l8449次列車（徐州常州）3416:0021:00游覽常州市021:007:00住宿于常州藍(lán)色快舟營(yíng)銷人連鎖旅店1205月2日7:008:00乘坐公交去中華恐龍園48:0016:00游覽中華恐龍園16016:0017:00乘坐公交返回417:0022:30游覽常州市022:305:20乘坐k75次列

45、車（常州寧波）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乘坐公交去黃山風(fēng)景區(qū)158:0015:00游覽黃山23015:0016:00乘坐公交車返回黃山站1516:0018:30游覽黃山市018:3023:30乘坐k67次列車（黃山鷹潭）515月5日0:304:00乘坐k253次列車（鷹潭九江）424:007:00休息07:008:00乘坐公交車到廬山風(fēng)景區(qū)108:0018:00游覽廬山18018:0019:00乘坐公交車返回九江站1019:0024:00游覽九江市05月6日0:001:50休息01:506:30