最佳旅行路線設(shè)計(jì)(值得細(xì)讀)-圖論

最正確旅行線路設(shè)計(jì)摘要：新疆地域廣闊，旅游資源繁多，本文以節(jié)約費(fèi)用或時(shí)間為目標(biāo)，分別為自助游、考察等具體情況安排了旅游線路，并為“五一旅游黃金周”設(shè)計(jì)線路，緩解景區(qū)客流頂峰及提高接待質(zhì)量。我們采集了全疆共33個(gè)景點(diǎn)景區(qū)的數(shù)據(jù)，其中不乏有十分接近的，故我們按地理位置將它們進(jìn)行聚類，最終得到20大景區(qū)。接著，建立在交通費(fèi)用與路線長(zhǎng)度成正比、不同景點(diǎn)的住宿費(fèi)用相等、車輛行駛于公路鐵路的時(shí)速恒定等假設(shè)條件下，我們先用Floyd算法求出了景區(qū)兩兩間的最短路徑，接著用蟻群算法估計(jì)了遍歷所有景區(qū)所花費(fèi)的時(shí)間總和，為下文設(shè)計(jì)合理的線路做準(zhǔn)備。對(duì)第一問，通過簡(jiǎn)單計(jì)算我們發(fā)現(xiàn)，單位時(shí)間內(nèi)游覽景區(qū)的花費(fèi)要小于往返景區(qū)途中的花費(fèi)，亦即：花最少的錢與游盡可能多的地方這兩個(gè)目標(biāo)在此題中是統(tǒng)一的。為此，我們提出了一個(gè)以確定一條游覽盡可能多景區(qū)的旅游線路為目標(biāo)、游覽總時(shí)間為約束的0-1整數(shù)規(guī)劃模型，利用LINGO軟件估計(jì)了解的下限，用遺傳算法求得了最優(yōu)解：兩人一個(gè)月時(shí)間花費(fèi)約6100元游覽17個(gè)景區(qū)。對(duì)第二問，根據(jù)蟻群算法的結(jié)果可知，只要適當(dāng)安排我們便可以在2個(gè)月內(nèi)完成對(duì)新疆所有景區(qū)的游覽。為此我們從兩種思考的角度，建立了不同的模型來求解交通費(fèi)用的最省問題。首先我們以兩次旅游的路程長(zhǎng)度之和為適應(yīng)度函數(shù)用遺傳算法求出了包含所有景區(qū)的兩條路徑，并使它們的路徑長(zhǎng)之和最短。接著，我們利用景點(diǎn)分布圖固有的特點(diǎn)，從簡(jiǎn)化圖的角度將20個(gè)點(diǎn)的連通圖化為一個(gè)只包含6個(gè)頂點(diǎn)的圖，并用枚舉法將可能的5種結(jié)果逐一計(jì)算，求得最正確線路。在處理考察任務(wù)問題時(shí)，由于考察景區(qū)所花費(fèi)的時(shí)間遠(yuǎn)大于在景區(qū)間往返的時(shí)間，所以我們首先忽略路程上的花費(fèi)，將如何安排三個(gè)考察組抽象成一個(gè)線性規(guī)劃問題，以最小化三個(gè)考察小組的最長(zhǎng)耗時(shí)為目標(biāo)并用LINGO軟件求解，得到一些目標(biāo)函數(shù)值相同但考察景區(qū)不同的最優(yōu)解，在此根底上，我們將路程耗時(shí)納入考慮之列，再一次使用遺傳算法，目的是求得更精確的解。對(duì)第四問，即設(shè)計(jì)“五一黃金周”旅游線路問題，我們以錯(cuò)開游客頂峰、景區(qū)利用率盡量高、同一線路的景區(qū)跨越盡可能小、線路多且豐富等條件作為安排線路的目標(biāo)來設(shè)計(jì)算法，在給出14條黃金游線路的同時(shí)，又對(duì)問題加以進(jìn)一步完善，即利用剩余資源開辟了一些5-6天的短途游線路，以充分利用旅游資源并滿足不同游客的不同要求。在模型與軟件的展望局部，我們闡述了規(guī)劃模型、蟻群模型與遺傳算法模型等的特點(diǎn)及其他應(yīng)用領(lǐng)域，也將文章中運(yùn)用的四種軟件：馬克威分析系統(tǒng)、LINGO、Excel以及MATLAB軟件的特點(diǎn)和擴(kuò)展做了逐一的介紹。本文的優(yōu)點(diǎn)是充分將規(guī)劃與遺傳算法相結(jié)合，突出規(guī)劃模型意義的同時(shí)也發(fā)揮了遺傳算法高效的特點(diǎn)。同時(shí)，較好的數(shù)據(jù)預(yù)處理與蟻群算法的環(huán)游估計(jì)都為解決問題做了鋪墊。另外，設(shè)計(jì)黃金周旅游線路時(shí)，我們不僅考慮了豐富多彩10日以上旅游線路，也輔之以一些中短規(guī)模的旅游路線，為游客提供了更多的選擇余地。值得一提的是，本文還綜合運(yùn)用了四種軟件。關(guān)鍵字：聚類、最短路、蟻群算法、遺傳算法、線性規(guī)劃、枚舉法、馬克威分析系統(tǒng)、LINGO、Excel、MATLAB。一、問題的重述：隨著近年來旅游業(yè)的不斷開展，我國新疆的天池、達(dá)坂城、吐魯番、樓蘭古城、伊犁等等的異域風(fēng)情，越來越吸引著廣闊的游客。在本文中，我們要完成以下幾個(gè)關(guān)于旅游路線設(shè)計(jì)的問題：1．在科學(xué)估算旅游費(fèi)用的根底上，以總本錢盡量小為目標(biāo)，設(shè)計(jì)一條在一個(gè)月〔計(jì)30天〕的時(shí)間里，游盡可能多的地方的旅游路線。〔吃飯費(fèi)用不計(jì)〕2．以在各景點(diǎn)間的交通費(fèi)用盡量小為目標(biāo)，設(shè)計(jì)兩條互不重疊的旅游路線，路線各為期一個(gè)月，且其合集包含新疆所有景點(diǎn)。3．設(shè)計(jì)三條互不重疊的旅游考察路線，在每個(gè)景點(diǎn)考察的時(shí)間是旅游觀光時(shí)間的四倍，用于交通的時(shí)間那么不變，要求三條考察路線各自所用時(shí)間的最大值盡可能小。4．設(shè)計(jì)假設(shè)干條為期十二天的黃金周旅游路線，以分散游客，提高景點(diǎn)的接待質(zhì)量，設(shè)參加這些旅游路線的游客人數(shù)與整條路線的接待能力成比例。5.〔對(duì)題目的進(jìn)一步完善〕對(duì)于上面第4個(gè)問題，考慮到新疆旅游實(shí)際問題的復(fù)雜性，除了設(shè)計(jì)一些為期12天的旅游路線外，還可以適當(dāng)?shù)脑O(shè)計(jì)一些短期的旅游線路，這樣既可以方便游客、給他們提供了更多的選擇，又可以充分利用各景區(qū)的旅游資源，防止其閑置。二、問題的分析在收集新疆各個(gè)主要旅游景點(diǎn)之間的路程、各個(gè)景點(diǎn)的最正確逗留時(shí)間等信息的根底上，我們將問題做以如下的分析和抽象：因?yàn)樾陆穆糜尉包c(diǎn)眾多，所處的地理位置也不相同，從旅游路線設(shè)計(jì)的實(shí)際出發(fā)，顯然要考慮到哪些景點(diǎn)相距較近，可以同時(shí)游覽，因而，我們需要將新疆境內(nèi)的所有主要的旅游景點(diǎn)按照經(jīng)緯度及是否可以直接連通予以分組。所以本文中我們首先采用聚類分析的方法，運(yùn)用馬克威軟件將各景點(diǎn)歸為假設(shè)干景區(qū)，以便于下一步的分析。另外，由于路程、時(shí)間、價(jià)格三者因素之間關(guān)系錯(cuò)綜復(fù)雜，我們希望能得到一個(gè)統(tǒng)一的標(biāo)準(zhǔn)，所以，我們把路程都化為時(shí)間和價(jià)格，并尋找后兩者的關(guān)系，使問題簡(jiǎn)化。對(duì)于第一小題，這一“最值”是某一固定時(shí)間內(nèi)的最小費(fèi)用，景區(qū)數(shù)那么不要求遍歷而只是越多越好。為此可以建立一個(gè)考慮逗留時(shí)間和路途時(shí)間的規(guī)劃問題，目標(biāo)是希望遍歷的景點(diǎn)盡量多，而約束那么是限定一個(gè)月的時(shí)間。而第二小題與第三小題可以說是第一小題中同時(shí)考慮逗留時(shí)間與路途時(shí)間的引申。在第二小題中由于有要求兩個(gè)暑假游覽所有的景點(diǎn)，那么景點(diǎn)上的花費(fèi)一定，我們只需要考慮使路途時(shí)間最少〔即交通費(fèi)用最小〕，這樣也使得總費(fèi)用最小。而第三小題，由于逗留時(shí)間遠(yuǎn)遠(yuǎn)大于路途時(shí)間，我們簡(jiǎn)化時(shí)可以只考慮逗留時(shí)間。當(dāng)然，為了進(jìn)一步求解更精確的解，在只考慮逗留時(shí)間的簡(jiǎn)化模型之后，我們還應(yīng)將路途時(shí)間參加。第四小題的處理方法那么有些不同，因?yàn)樵黾恿艘恍┬碌募s束類型，考慮到景區(qū)所能夠承受的游客流量，同一時(shí)刻不能有過多的游客游覽同一景點(diǎn)，我們所要做的就是盡量錯(cuò)開游客的旅行線路，使每一時(shí)刻，各景點(diǎn)都接待其承受能力之內(nèi)的游客，并盡可能豐富地設(shè)計(jì)旅游線路?？傊?，對(duì)于旅游線路的規(guī)劃問題，我們?cè)谝欢ǔ潭壬隙伎梢詫⑵涑橄蟪梢粋€(gè)求最短“路”的問題，只不過這里的路常常不單指路程，而還包括時(shí)間，費(fèi)用等等方面。不同的問題，可以通過添加不同的約束條件予以描述。將實(shí)際問題抽象成一個(gè)規(guī)劃模型的方法在某種程度上是很相似的，但是，對(duì)于抽象出的這些規(guī)劃問題，具體的求解方法，那么是多種多樣的。三、根本假設(shè)1、為了盡量節(jié)約費(fèi)用，由于飛機(jī)的價(jià)格要遠(yuǎn)高于鐵路和公路，而后兩者根本相同。所以在新疆境內(nèi)的交通費(fèi)用，以鐵路票價(jià)為主，沒有開通鐵路的線路，那么以公路票價(jià)為主；2、對(duì)于公路的收費(fèi)沒有明確標(biāo)價(jià)的路段，以兩個(gè)旅游點(diǎn)之間的公路里程〔km〕除以平均時(shí)速〔60km/h〕進(jìn)行估算。對(duì)于少數(shù)公路也欠興旺的地區(qū)，那么以速度折半為30km/h估算；3、假設(shè)在新疆的所有景點(diǎn)中，對(duì)任何的A、B兩個(gè)景點(diǎn)，從A到B所需花在路上的時(shí)間與從B到A的相同，即忽略例如由于列車?？空静煌斐傻倪\(yùn)行時(shí)間上的一些差異；4、暑假的一個(gè)月為31天，考慮到往返新疆的時(shí)間，故花費(fèi)在新疆境內(nèi)的旅游時(shí)間以30天計(jì)；5、在新疆境內(nèi)各旅游景區(qū)的住宿費(fèi)用均為一個(gè)定值：RMB150/標(biāo)準(zhǔn)間〔兩人〕/天；6、設(shè)旅游途中的休息調(diào)整時(shí)間合并在每個(gè)景點(diǎn)的觀光逗留時(shí)間之內(nèi)，不再予以單獨(dú)的計(jì)算；7、不考慮交通費(fèi)用在白天和夜晚的區(qū)別，〔如火車硬座與臥鋪價(jià)格上的差異等〕均以最低價(jià)格即硬座票價(jià)計(jì)算。8、對(duì)于旅行社推出的旅游線路的設(shè)計(jì)，與自助游不同，我們認(rèn)為其主要目標(biāo)不在于節(jié)省費(fèi)用而在于多游覽美景和旅途的舒適，因此假設(shè)在新疆省內(nèi)白天的時(shí)間都用來游玩，景區(qū)間的行程那么采用飛機(jī)〔時(shí)間短故可忽略〕連接或在晚間乘車抵達(dá)。9、假設(shè)鐵路和公路交通費(fèi)用的票價(jià)，與行駛的里程近似成線性關(guān)系，而又因?yàn)榱熊嚮蚱嚂r(shí)速也是一定的，這樣，某一段路程需要的交通費(fèi)用也與其時(shí)間呈近似的線性關(guān)系，這樣，求最小費(fèi)用，也即求最短路線。注：假設(shè)9的依據(jù)：我們對(duì)局部景點(diǎn)間往返的時(shí)間和費(fèi)用進(jìn)行采樣，并作回歸分析如下頁圖所示：〔R平方為0.9819，F(xiàn)值為595.6604，說明兩者呈很強(qiáng)的線性關(guān)系。幾乎可以認(rèn)為交通費(fèi)用與路程成正比?！场矆D1：價(jià)格—距離采樣關(guān)系圖〕數(shù)據(jù)預(yù)處理及問題的初步探究1、數(shù)據(jù)采集及由景點(diǎn)向景區(qū)的聚類[新疆境內(nèi)的33個(gè)旅游景點(diǎn)名稱及其相應(yīng)的觀光逗留時(shí)間，經(jīng)、緯度等數(shù)據(jù)，見附錄1]我們先用聚類分析方法將上述33個(gè)旅游景點(diǎn)予以分組。所謂聚類分析，就是把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成假設(shè)干個(gè)不同的數(shù)據(jù)對(duì)象的集合，這里，我們將它作為接下來的蟻群算法的一個(gè)數(shù)據(jù)預(yù)處理步驟。因?yàn)榫垲愂且环N無監(jiān)督分類法，并沒有預(yù)先指定的類別，因此，采用聚類分析，我們可以更加客觀地了解各個(gè)景點(diǎn)的分布狀況，并對(duì)新疆的這些旅游景點(diǎn)進(jìn)行分組和歸類。以上述1至33的景點(diǎn)為分類單元，根據(jù)它們的經(jīng)緯度，運(yùn)用馬克威軟件進(jìn)行聚類[1]，可得到一分組結(jié)果如下列圖：〔圖2：聚類結(jié)果圖〕除了烏魯木齊、阿圖什、喀什等大城市不受分類限制，將以獨(dú)立身份計(jì)入旅游景區(qū)外，其余的旅游景點(diǎn)按照上圖中分割線左側(cè)的聚類方案，可以組合成20個(gè)景區(qū)。例如，序號(hào)分別為27、29、30、31的蘇丹·沙圖克麻扎、喀什、香妃墓、艾提尕清真寺這4處景點(diǎn)，按照上圖中的聚類可以歸在一處用喀什景區(qū)來代表，等等。這樣，我們就可以將33個(gè)景點(diǎn)歸結(jié)為20個(gè)景區(qū)，合并后各景區(qū)的觀光時(shí)間等詳細(xì)信息可列表如下：景區(qū)景區(qū)逗留時(shí)間1阿勒泰2.52塔城13克拉瑪依0.54博樂45石河子16昌吉17烏魯木齊1.58天山19伊犁1.510天鵝湖0.511吐魯番1.512哈密213庫車大寺114庫爾勒115阿克蘇116樓蘭517阿圖什0.7518喀什2.2519尼雅遺址320和田1〔表1：20個(gè)景區(qū)逗留時(shí)間一覽〕這20個(gè)景區(qū)的地理位置分布和相互間的道路連通情況可以如下列圖所示，其中各個(gè)標(biāo)明序號(hào)的結(jié)點(diǎn)上方的墨綠色數(shù)字表示在該景區(qū)的逗留時(shí)間?！矆D3：景點(diǎn)分布及逗留時(shí)間圖〕2、用蟻群算法初步求得的遍歷時(shí)間盡管上述所示的景區(qū)道路圖是連通圖，但并不是任意兩個(gè)景區(qū)間都存在直接連通的。因?yàn)樾枰?jì)算的是在景區(qū)內(nèi)的逗留時(shí)間和路上的消耗時(shí)間，所以，我們希望得到任意兩個(gè)景區(qū)間的最短通路，這樣，當(dāng)需要跨越某一景區(qū)而到達(dá)相對(duì)較遠(yuǎn)的另一景區(qū)時(shí)，可以有直接的通路，這將使問題更直觀和簡(jiǎn)便。因此，我們運(yùn)用Floyd算法，首先要做的是將這20個(gè)景區(qū)之間兩兩的最短時(shí)間計(jì)算出來，得到一個(gè)20*20的時(shí)間矩陣如下所示。根據(jù)我們前面的假設(shè)3，這是一個(gè)對(duì)稱矩陣，矩陣元素的單位為小時(shí)。[矩陣見附錄2]根據(jù)上述的景區(qū)間最短時(shí)間矩陣，運(yùn)用帶精英螞蟻的蟻群算法[2]編制程序，我們可以求得要遍歷所有的景區(qū)，需要在路上花費(fèi)的最小時(shí)間。以此，再結(jié)合各個(gè)景區(qū)的觀光逗留時(shí)間，那么可以得到遍歷所有景區(qū)的總時(shí)間，根據(jù)它我們可以估算假設(shè)要游覽新疆的全部各個(gè)旅游景點(diǎn)，需要花費(fèi)的時(shí)間是多少，為此題后面的處理做一估計(jì)。蟻群算法的運(yùn)行圖示如下：最終可得到如下的結(jié)果：通過2.859000秒的計(jì)算，我們得到最少環(huán)游時(shí)間：292.44小時(shí)=12.18天。與其相對(duì)應(yīng)的最短環(huán)路是：161411128765312410913151718201916而游覽所有聚類后的景區(qū)總時(shí)間為一定值：33天，所以：總時(shí)間=最短環(huán)游時(shí)間+逗留時(shí)間=12.18+33=45.18天這個(gè)結(jié)果的意義在于，它告訴我們要想在一個(gè)月即30天內(nèi)遍歷所有的景區(qū)是不可能實(shí)現(xiàn)的，并給出了一個(gè)十分有參考價(jià)值的數(shù)據(jù)。因此對(duì)于第一問，我們要選擇適宜的線路，從而可以游覽盡量多的景區(qū)。而由于總時(shí)間小于60天，也即我們是可以在2個(gè)月內(nèi)完成對(duì)所有景區(qū)的考察，第二問也就自然會(huì)有可行解。再注意到，如果逗留時(shí)間是33天的4倍，即132天，那么考察時(shí)間就將會(huì)是環(huán)游所需總時(shí)間的10倍以上。這就啟發(fā)我們對(duì)于第三問，可以先忽略環(huán)游時(shí)間計(jì)算一個(gè)近似最優(yōu)解，再在此根底上逐步地加以完善。模型的建立與求解模型一：通過比擬各種交通費(fèi)用，我們可以發(fā)現(xiàn)，在新疆境內(nèi)選擇飛機(jī)出游的花費(fèi)要遠(yuǎn)高于鐵路和公路的費(fèi)用，出于節(jié)約費(fèi)用的目的，并且考慮到許多景點(diǎn)都是遠(yuǎn)離機(jī)場(chǎng)的，飛機(jī)的優(yōu)勢(shì)也并不明顯，為此，我們首先擯棄乘坐飛機(jī)。此外，選擇鐵路的性價(jià)比要略高于選擇公路，但新疆境內(nèi)的鐵路很有限。所以，假設(shè)兩景點(diǎn)之間同時(shí)存在鐵路和公路將它們相連通，那么選擇鐵路，而假設(shè)僅有公路那么只能選擇公路。另一方面，通過計(jì)算公路交通的費(fèi)用，結(jié)合公路里程、客車行駛時(shí)間和可以發(fā)現(xiàn)，如果某天24小時(shí)都花費(fèi)在往返假設(shè)干城市的路途上，那么兩個(gè)人的花費(fèi)要超過330元，但是如果某天是停留在某個(gè)景點(diǎn)游玩的話，日均游玩費(fèi)與住宿費(fèi)之和大約只有280元，所以從這個(gè)角度來考慮問題的話，花最少的錢實(shí)際上去游盡可能多的景點(diǎn)是一致的。我們的目標(biāo)就是防止在途中過多的耽誤時(shí)間，從而使游玩時(shí)間減少。建立在總費(fèi)用=住宿游覽費(fèi)用+路程開支的根本假設(shè)之上，我們建立了如下的線性規(guī)劃模型：對(duì)于聚類后得到的20個(gè)景區(qū)的問題，我們引入一個(gè)的矩陣，其中的元素為0-1變量，當(dāng)時(shí)表示我們制定的路線包含從景區(qū)直接到景區(qū)，否那么不包含景區(qū)直接到，我們希望整個(gè)游覽線路包含盡量多的城市，也即最大化目標(biāo)函數(shù)：。對(duì)于約束條件，約束條件1：由于每個(gè)景點(diǎn)最多參觀一次，所以，矩陣的每行與每列之和均為0或者1；約束條件2：當(dāng)而為了保證整條鏈的連通性，即使出現(xiàn)兩條以上不相連通的鏈，我們要求每行之和與每列之和相等。約束條件3：為了滿足總的時(shí)間小于一個(gè)月，還需要增加時(shí)間上約束條件。故，完整的線性規(guī)劃模型為：(其中是第j個(gè)景區(qū)的逗留時(shí)間)我們用Lingo軟件對(duì)其進(jìn)行求解[5]，但是很遺憾，由于較多的變量及復(fù)雜的約束，程序無法在短時(shí)間內(nèi)完成。好在隱枚舉方法給了我們啟示，發(fā)現(xiàn)可以找到一條至少包含17個(gè)城市的鏈，所以，根據(jù)這一啟發(fā)，我們下面運(yùn)用擅長(zhǎng)處理NP完全問題的遺傳算法來重新求解這一問題。算法的思想是：通過模擬自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任一初始種群出發(fā)，通過隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來越好的區(qū)域，這樣一代代地不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體，求得問題的最優(yōu)解。既然線性規(guī)劃模型已經(jīng)告訴我們，至少可以找到一條包含17個(gè)景區(qū)的鏈，那么我們只需從N=17開始找一條包含N個(gè)景區(qū)的最小耗時(shí)鏈，假設(shè)對(duì)于某一N()，最小耗時(shí)鏈的總長(zhǎng)大于720分鐘，那么一個(gè)月內(nèi)最多可游覽的景區(qū)即為N-1。下面，我們對(duì)遺傳算子進(jìn)行設(shè)計(jì)：定義個(gè)體：我們以一個(gè)1行20列的行向量為一個(gè)個(gè)體。其中，前N列表示一個(gè)月內(nèi)所遍歷的景區(qū)的鏈；后20-N列表示剩下的未遍歷的景區(qū)。假設(shè)干個(gè)這樣的個(gè)體組成一個(gè)種群。選擇運(yùn)算：根據(jù)適應(yīng)度的上下進(jìn)行優(yōu)勝劣汰的選擇。在這里，遍歷前N個(gè)景區(qū)道的路上的花費(fèi)時(shí)間以及停留在這N個(gè)景區(qū)的逗留時(shí)間之和越短，適應(yīng)度越高。對(duì)不同適應(yīng)度分配一個(gè)被進(jìn)化的概率。適應(yīng)度越高，被選擇進(jìn)化到下一代的概率也越大。交叉運(yùn)算：交叉的方法有很多種，在這里我們對(duì)兩兩個(gè)體以一定概率pm〔0.6~0.95〕決定是否進(jìn)行交叉運(yùn)算，假設(shè)進(jìn)行，那么采取CX方法[4]，假設(shè)否，那么保存這兩個(gè)個(gè)體。變異運(yùn)算：變異的方法也有許多種，在這里，我們分別考察每一個(gè)個(gè)體，并以一個(gè)小概率pc〔0.05~0.15〕決定是否進(jìn)行變異運(yùn)算，假設(shè)進(jìn)行，那么采取倒位變異，假設(shè)否，那么保存該個(gè)體。適應(yīng)度計(jì)算：以游覽景區(qū)個(gè)數(shù)多少來評(píng)價(jià)適應(yīng)度，游覽的景區(qū)越多那么適應(yīng)度越高。模型的結(jié)果與分析：屢次調(diào)整參數(shù)，運(yùn)行遺傳算法程序，我們得到一條遍歷17個(gè)景區(qū)的鏈：78652131091315171820141112而另三個(gè)景區(qū)4、19、16那么不訪問。遍歷這條鏈的總時(shí)間花費(fèi)為642.5700小時(shí)，大約27天?！矆D4：遺傳算法性能追蹤圖〕我們?cè)賴L試N=18的情況，但是，遺傳算法的結(jié)果告訴我們，無法找到一條遍歷18個(gè)景區(qū)的鏈，使總的時(shí)間開支小于720小時(shí)。所以，兩個(gè)人在暑假一個(gè)月內(nèi)花最少的錢最多可以游17個(gè)景區(qū)。費(fèi)用：交通費(fèi)用：717景點(diǎn)住宿費(fèi)用：21*150景點(diǎn)游玩費(fèi)用：1120*2那么總費(fèi)用：6107/兩人模型二：2.1遺傳算法的求解根據(jù)第一小題的結(jié)果，我們發(fā)現(xiàn)，如果以與之前相同的出行方式顯然不能在一個(gè)月之內(nèi)遍歷所有的20個(gè)景區(qū)，但是，在引言局部，我們也計(jì)算出，遍歷所有景區(qū)與往返景區(qū)路途中的總時(shí)間是45.18天，這說明分兩個(gè)月完成游覽是完全可以的。由于兩個(gè)月之內(nèi)，我們會(huì)遍歷所有的景區(qū)，所以在景區(qū)上的開支是恒定的，所以，如何安排兩個(gè)月所分別游覽的景區(qū)，使交通費(fèi)用最省也即是使總費(fèi)用最省。受第一小題的啟發(fā)，我們依然想到運(yùn)用遺傳算法進(jìn)行求解。選擇、交叉、變異函數(shù)不變，適應(yīng)度函數(shù)定義為兩次游覽的總交通費(fèi)用的倒數(shù)，這樣，用于交通的費(fèi)用越少，適應(yīng)度就越高，個(gè)體就越能遺傳到下一代。由于景區(qū)總數(shù)只有20個(gè)，所以，我們下面采用一種分類遺傳的方法，這樣可以使結(jié)果更精確也可以使計(jì)算效率提高。做法是：將20個(gè)城市分為兩局部，第一個(gè)暑假考察N個(gè)景區(qū)，第二個(gè)暑假考察20-N個(gè)景區(qū)，N從3開始到17〔如果N小于3的話會(huì)導(dǎo)致不滿足約束條件，即出現(xiàn)一個(gè)暑假游覽所花費(fèi)的時(shí)間大于30天〕，同時(shí)考慮到烏魯木齊是省會(huì)，很多游覽天山、昌吉等景區(qū)的旅行線路都是以烏魯木齊為出發(fā)點(diǎn)的，所以為更切合實(shí)際，在這里我們也要求第一個(gè)暑假從烏魯木齊出發(fā)〔當(dāng)然，這不是必要條件，我們后面采用的方法即不需要滿足此條件〕。對(duì)每一個(gè)給定的N用一次遺傳算法。最后將每個(gè)N對(duì)應(yīng)的交通上花費(fèi)的時(shí)間作比擬，我們發(fā)現(xiàn)，N從7到13所花費(fèi)的時(shí)間較其他更少一些，故，作的柱狀圖如下：〔圖5：景區(qū)數(shù)量安排與耗時(shí)關(guān)系圖〕模型的結(jié)果與分析：從上圖的結(jié)果，我們可以看到：當(dāng)兩個(gè)月各訪問10個(gè)景點(diǎn)，并且按照我們列出的順序訪問，路上時(shí)間最少，而路途耗時(shí)與交通費(fèi)幾乎成正比，從而交通費(fèi)也最省。我們給出一組最優(yōu)線路：第一個(gè)暑假78654910132第二個(gè)暑假12111413151718201916遺傳算法的效果和求解能力都能到達(dá)我們所期望的，但是對(duì)于這一問題固有的特性，我們也可以直接從圖的角度來建立模型：2.2從圖的角度直觀求解兩次暑假遍歷所有的景區(qū)，也即是將原來20個(gè)景區(qū)的連通圖分割成兩個(gè)子圖，并找出兩條互不重疊的旅游路線。針對(duì)問題的特殊性，我們分如下幾步來處理問題：第一步，不斷地剪去圖中所有度為1的頂點(diǎn)，即編號(hào)為：2、8、9、11、12、16、19的點(diǎn)〔11是因?yàn)榧羧?2后它成為了度為1的頂點(diǎn)〕。因?yàn)槲覀儏⒂^這類景區(qū)的時(shí)候，進(jìn)出必然沿同一條線路，花費(fèi)在這些路上的時(shí)間是不可縮減的。所以，在我們的最節(jié)約時(shí)間方案中一定會(huì)包含這些路徑，故尋找最短路徑的時(shí)候可以暫時(shí)將其從圖上去除。第二步，我們將度為2的頂點(diǎn)去除，但保存原來的路，即編號(hào)為：1、4、6、15、17、18、20的點(diǎn)。原因與第一步類似，因?yàn)閷?duì)于這類頂點(diǎn)，一般來說，游覽它們的時(shí)候，是從頂點(diǎn)的一條邊進(jìn)入而從另一條邊離開，所以，通過這類頂點(diǎn)的路徑也是確定的，對(duì)我們所需要尋找的最短路徑不會(huì)產(chǎn)生影響，可以暫時(shí)將其從圖上去除。執(zhí)行這兩步之后，得到如下結(jié)果：〔圖6：簡(jiǎn)化后的景點(diǎn)圖〕我們發(fā)現(xiàn)，余下的頂點(diǎn)的度數(shù)都大于等于3。我們把被去除的頂點(diǎn)“附屬于”某一個(gè)度數(shù)大于等于3的頂點(diǎn)，即如果我們到達(dá)某個(gè)頂點(diǎn)x，我們就要遍歷它的“附屬”點(diǎn)。要分割原先的圖，并找出不重疊的兩條路線就要選擇如何分割這些度數(shù)大于等于3的頂點(diǎn)。模型的結(jié)果與分析：由于數(shù)據(jù)量較少，我們用枚舉的方式得出了五種較為合理的分組方式。分組情況一情況二情況三情況四情況五Group11—101—12、141—81—8、11、12、141—6、9、10Group211—2013、15—209—209101315—207,8,11—20情況一：Group123178654109Group212111413151718201916情況二：Group121391045678141112Group213151718201916情況三：Group123187654Group212111413109151718201916情況四：Group121345678141112Group291013151718201916情況五：Group1213564109Group21211147813151718201916由上面五組游覽方案，我們分別計(jì)算它們的游覽時(shí)間以及所需的路費(fèi)，可以得到如下表的結(jié)果：?jiǎn)挝弧残r(shí)〕情況一情況二情況三情況四情況五Group157.37107.0345.1791.8953.41Group2103.364.15126.5176.95130.75總時(shí)間160.7171.18171.68168.84184.16價(jià)格〔元〕一二三四五Group1292.3573.4220.1511.8270Group2694.3465.9845.7541.6841.3Sum986.61039.31065.81053.41111.3由上表，我們發(fā)現(xiàn)，情況一中所消耗的時(shí)間最短，所需的費(fèi)用相應(yīng)也最少。因此，我們認(rèn)為，安排兩個(gè)月的旅游線路最正確的分配方式由情況一的分組給出，具體的線路圖可以表示如下：〔圖7：最正確線路安排圖〕模型三：3.1簡(jiǎn)化的模型由于考察分三組進(jìn)行，故我們可以把整個(gè)西藏的景區(qū)分為三局部，三個(gè)考察小組各考察一個(gè)局部，設(shè)他們考察所花費(fèi)的時(shí)間分別為，完成整個(gè)考察工作是指三個(gè)小組都完成各自的考察任務(wù)，所以，盡早的完成考察也就是使三個(gè)小組完成考察時(shí)間的最大值最小，即：。引言中，我們已經(jīng)通過蟻群算法計(jì)算出環(huán)游全部景區(qū)時(shí)，所消耗在路上的時(shí)間約12天，現(xiàn)在分三組進(jìn)行，花費(fèi)在路上的時(shí)間更會(huì)小于12天。而現(xiàn)在各景區(qū)停留考察花費(fèi)的時(shí)間是原先的4倍，即天，兩者相差一個(gè)數(shù)量級(jí)。故，我們先考慮一個(gè)簡(jiǎn)化的模型，即忽略路上所花費(fèi)的時(shí)間。現(xiàn)在，問題就轉(zhuǎn)化為一個(gè)簡(jiǎn)單的規(guī)劃問題：其中表示三組考察的線路，表示20個(gè)景區(qū)，那么表示第組是否考察第個(gè)景區(qū)，假設(shè)考察，那么，否那么。而第一個(gè)約束條件表示每個(gè)景點(diǎn)當(dāng)且僅當(dāng)被一個(gè)小組考察。目標(biāo)函數(shù)中的表示考察每個(gè)景區(qū)所花費(fèi)的時(shí)間，表示第組考察隊(duì)伍所花費(fèi)的考察時(shí)間，三組隊(duì)伍的最大值表示花費(fèi)的總時(shí)間，我們希望這個(gè)值盡可能的小。模型的結(jié)果與分析：下面我們用LINGO軟件對(duì)問題進(jìn)行求解，最優(yōu)解中，矩陣的值不唯一，但是目標(biāo)函數(shù)的值是唯一的，都是44，由于總共用于所有景區(qū)的考察時(shí)間為132天，很容易得出三個(gè)考察組在各景區(qū)所花費(fèi)的時(shí)間都為44天。這與我們從直觀上理解——盡量使三個(gè)小組的考察時(shí)間平均——是一致的。簡(jiǎn)化的線性規(guī)劃模型的好處是不言而喻的，但是也存在著一些缺乏，從解的分布來看，三個(gè)考察組遍歷景點(diǎn)所花費(fèi)時(shí)間都為44天的情況有許多種，盡管用于往返景區(qū)途中的時(shí)間遠(yuǎn)小于逗留在景區(qū)內(nèi)的時(shí)間，但是為了區(qū)分各組解并求得更精確的解，我們需要將路程上的時(shí)間消耗列入考慮的范圍之內(nèi)。對(duì)于Lingo計(jì)算出的假設(shè)干組最優(yōu)解，我們將路程時(shí)間納入考慮，對(duì)于其中最優(yōu)的一組：第一組2318654第二組910131517182019第三組121114716我們計(jì)算得，三組停留在景區(qū)與往返于景區(qū)路上所花費(fèi)的總時(shí)間的最大值為1138.09小時(shí)〔47.42天〕但是，由于最優(yōu)值對(duì)應(yīng)的分布較多，通過Lingo屢次計(jì)算不考慮路程的最優(yōu)解再將路程消耗參加，從而比擬，這樣的做法略顯煩瑣，也不能保證枚舉到所有可能的結(jié)果。為此，我們?cè)僖淮芜\(yùn)用遺傳算法。3.2遺傳算法的求解這一問題遺傳算法的選擇、交叉、變異運(yùn)算并沒有實(shí)質(zhì)的區(qū)別，但是適應(yīng)度函數(shù)方面我們做了比擬大的改良：我們根據(jù)三個(gè)小組遍歷的景區(qū)計(jì)算他們各自在景區(qū)逗留和往返景區(qū)間的時(shí)間消耗和，并將適應(yīng)度取為三組完成時(shí)間的最大值的倒數(shù)，這樣，根據(jù)優(yōu)勝劣汰的準(zhǔn)那么，耗時(shí)最長(zhǎng)的一組所消耗的時(shí)間越短，那么被遺傳到下一代的概率越大。以此逐代進(jìn)化，最終得到最優(yōu)解：第一二組1358671112第三組1519201416這樣，經(jīng)過1120.21小時(shí)〔合46.6754天〕，三個(gè)小組將全部完成考察任務(wù)，這比之前所使用枚舉法的1138.09小時(shí)〔合47.42天〕的結(jié)果要好一些，進(jìn)一步說明了遺傳算法處理復(fù)雜問題的優(yōu)勢(shì)。模型四：根據(jù)20個(gè)景區(qū)各自的最正確逗留時(shí)間，我們可以算出在黃金周12天時(shí)間內(nèi)每個(gè)景區(qū)接待顧客流的數(shù)量。顯然，游客在某一景區(qū)逗留的時(shí)間越短，景區(qū)可以接待游客的批次就越多。由于各景區(qū)的接待能力大相徑庭，且同一時(shí)間每一景區(qū)接待的游客數(shù)量是有限的。我們希望安排盡量多的游客在不同的時(shí)刻游覽不同的景區(qū)，錯(cuò)開某一景區(qū)的人流頂峰，從而提高旅游質(zhì)量。因此，我們的目標(biāo)就是盡可能多地設(shè)計(jì)10天以上的旅游線路，也就是使任意時(shí)刻閑置的景區(qū)數(shù)量盡量地少，這樣整個(gè)新疆旅游區(qū)可以接待更多的游客。值得一提的是，為了使游客花費(fèi)在路上的時(shí)間盡量地節(jié)約，我們?cè)O(shè)計(jì)的線路時(shí)也考慮使訪問的相臨兩個(gè)景區(qū)在可能的情況下盡量地接近。然而即使如此安排，我們依然不能保證每一時(shí)候所有景區(qū)都處于飽和狀態(tài)，某些景區(qū)必然會(huì)有一定的時(shí)間出現(xiàn)游客數(shù)量稀少的情況?？紤]到這一情況，為了充分利用新疆的旅游資源，我們?cè)诒ＷC長(zhǎng)旅游線路的前提下，對(duì)于那些無法再構(gòu)成一條10天以上旅游線路的景區(qū)，盡也可能地安排它們組成了一些短程旅游線路，這樣，不僅使游客有了更多的選擇空間，也可以使更多的游客瀏覽祖國西部的奇山異景。為此，以半天為一個(gè)時(shí)間單位，將12天的時(shí)間劃分為24個(gè)單位。并將每一個(gè)景區(qū)以劃分成假設(shè)干區(qū)段，使每個(gè)區(qū)段包含的單位數(shù)正好等于一批游客的逗留時(shí)間。我們?cè)O(shè)計(jì)了如下的算法：表示在第個(gè)城市的逗留時(shí)間；表示時(shí)間軸的變化，；為一的矩陣，表示任一單位時(shí)刻，景區(qū)是否已經(jīng)被安排接待某批游客，假設(shè)已經(jīng)有接待任務(wù)，那么，否那么。第一步：置；在時(shí)刻1，我們隨意選擇一個(gè)空閑的景區(qū)a作為起點(diǎn)，，。第二步：從時(shí)刻開始，列舉下一時(shí)刻段沒有安排接待任務(wù)的景區(qū)，從中選擇與上一個(gè)城市最近的景區(qū)為下一個(gè)訪問對(duì)象，直到或者下一時(shí)間段沒有可供選擇的城市。第三步，記錄遍歷的景區(qū)編號(hào)和總共需要花費(fèi)的時(shí)間數(shù)。置重新執(zhí)行前兩步，直到無初始景區(qū)可供選擇。模型的結(jié)果與分析：由于這一算法在初始時(shí)的選擇存在隨機(jī)性，故每次運(yùn)行的結(jié)果并不完全相同，我們運(yùn)用上述算法每次都可以得到20條不同的線路，并且在任意時(shí)候，不同線路的游客不會(huì)參觀同一景點(diǎn)。我們將一次結(jié)果羅列如下，其中，14條線路是10天以上幾乎覆蓋整個(gè)黃金周的旅游，而另6條那么是中短途旅游線路，也可供特殊要求的游客參考：長(zhǎng)線：10.5天神秘天山宗教十日游9-冰山水域王陵十日探險(xiǎn)1-18-2-8-10-3-1211天玉邑絲路11日游3-10-13-14-20-17-15-9-11-7尼雅雙湖文化之旅19-13-15-17-20-14-3-10-911.5天西域風(fēng)土民俗游8-6-5-3-10-4-13新疆內(nèi)陸景觀游17-15-13-10-3-5-6-7-9-8-14火焰山千佛洞神奇之旅11-7-6-8-5-3-10-13-15-17-20尼雅博湖佛寺探秘之旅15-17-20-19-14-6-5-3-10-13疆內(nèi)城市風(fēng)情環(huán)游7-3-6-5-10-9-13-15-17-20-8疆內(nèi)文化古跡環(huán)游5-3-10-15-17-20-18-7-6-2博樂天鵝湖周邊城市游4-6-8-5-3-10-14-13-15天山玉邑民俗游13-10-9-15-14-20-17-8-6-11-3邊疆寶藏探秘之旅10-3-8-2-7-11-12-20-14-512天遠(yuǎn)古文明之旅16-14-19-5-6-3〔圖8：景點(diǎn)線路參考圖〕短線：9天環(huán)疆山水絲路九日游20-14-8-2-3-7-15-17-108天西疆邊境八日游18-10-9-3-17天疆北風(fēng)情七日游2-5-3-1-13-106天全疆六日環(huán)游6-2-17-11-10-35.5天天山天鵝湖六日游12-10-3-8-24.5天哈密和田庫爾勒五日游14-20-12以玉邑絲路11日游為例，我們可以安排具體行程如下：7-11-9-15-17-20-14-13-10-3烏市、吐魯番、伊犁、阿克蘇、阿圖什、和田、庫樂勒、克孜樂千佛洞、天鵝湖、克拉瑪依雙飛十一日行程安排：第一天：烏魯木齊市接機(jī)、入住酒店，游覽城市風(fēng)光，逛夜市，宿于烏魯木齊市。第二天：中午乘車前往吐魯番，當(dāng)日宿于吐魯番。第三天：從吐魯番去火焰山，游覽。晚上去伊犁，宿于伊犁。第四天：游覽伊犁景點(diǎn)，體驗(yàn)草原民俗風(fēng)情。第五天：中午飛往阿克蘇。第六天：游覽阿克蘇，上午去阿圖什。第七天：早上赴和田，白天游覽。當(dāng)晚乘飛機(jī)去庫樂勒。宿于庫樂勒。第八天：游覽庫樂勒，當(dāng)晚乘飛機(jī)去庫車。宿于庫車。第九天：游覽庫車大寺和克孜樂千佛洞。宿于當(dāng)?shù)?。第十天：乘車去天鵝湖，游覽，黃昏乘車去最近的機(jī)場(chǎng)，然后乘飛機(jī)去克拉瑪依。第十一天：游覽克拉瑪依。飛機(jī)返程。其他均可做類似安排，不再詳述。六、模型的評(píng)價(jià)：模型的優(yōu)點(diǎn)：1、本文以規(guī)劃模型為根底，以遺傳算法作為求解工具，既取了規(guī)劃模型的優(yōu)點(diǎn)，即目標(biāo)函數(shù)與約束條件的意義都十分清晰，而輔之的遺傳算法又克服了線性規(guī)劃由于變量過多而導(dǎo)致的計(jì)算效率下降等問題，從而使每一個(gè)模型根本上都能得到最優(yōu)解。2、本文使用的模型和方法較為廣泛，前三個(gè)問題都建立了兩個(gè)模型或使用了兩種方法，這樣既豐富了文章的內(nèi)容，也通過模型之間的相互比擬和互相結(jié)合更好地完成了要求的任務(wù)。3、對(duì)于第四問，我們提出的算法思路不僅求得了多條黃金周旅游線路，同時(shí)還給出了一些有價(jià)值的短程游路線。參加這一完善結(jié)果，可以更充分地利用各景區(qū)的旅游資源，而且也同時(shí)滿足了更多游客，讓具有不同旅游需求的游客都可以領(lǐng)略新疆絢麗的風(fēng)采，可以說取得了一種錦上添花的效果。4、本文綜合運(yùn)用了MATLAB、馬克威分析系統(tǒng)、LINGO、EXCEL等多種軟件，發(fā)揮其各自的特長(zhǎng)，在提高編譯和求解效率的同時(shí)，也使文章圖文并茂，更直觀更具有可讀性。模型的缺乏及進(jìn)一步探索：1、本文的模型均建立在速度、單位行程的費(fèi)用等都為恒定的根底假設(shè)之上，而實(shí)際上，對(duì)于不同的道路，時(shí)速以及費(fèi)用都會(huì)略有波動(dòng)，如果在模型中能參加一些隨機(jī)因素，應(yīng)該可以更接近現(xiàn)實(shí)生活。2、模型處理復(fù)雜問題的求解上，根本都采用了遺傳算法。但是，由于遺傳算法的進(jìn)化是基于一定的概率，所以單純的遺傳算法有時(shí)并不能保證求得最優(yōu)解，或者雖然能求得最優(yōu)解卻要消耗相當(dāng)多的時(shí)間，而這與我們的初衷是相違背的。如果能將遺傳算法與模擬退火算法、局部搜索等相結(jié)合，將會(huì)取得更好的效果。3、在第四問中我們僅考慮了錯(cuò)開景點(diǎn)旅游頂峰，即僅從理性的角度分析籌劃了旅游線路，但沒有考慮游客對(duì)各景點(diǎn)的偏好程度，即未參加感性的一些元素，而這些對(duì)于現(xiàn)實(shí)問題還是很有影響的，因此，如果將游客的一些特定需要添加到模型的約束中，將會(huì)更符合實(shí)際。4、本模型第一步對(duì)景點(diǎn)進(jìn)行了聚類，這樣在為后面的分析帶來了許多方便的同時(shí)，也造成了一旦選擇游覽某個(gè)景區(qū)也即游覽了此景區(qū)的所有景點(diǎn)的約束。而事實(shí)上，尤其是在一條線路旅游的最后階段，有可能出現(xiàn)時(shí)間上不允許游覽某個(gè)景區(qū)，但卻足夠游覽一兩個(gè)景點(diǎn)的情況。而我們的模型會(huì)直接將整個(gè)景區(qū)排除，這是我們線路設(shè)計(jì)模型的一個(gè)略有缺乏之處。七、模型及軟件的前景展望：1、蟻群算法模型：本文中我們運(yùn)用蟻群算法估計(jì)游遍新疆境內(nèi)所有景區(qū)在途中所花費(fèi)的最少時(shí)間，從而為合理安排行程做了鋪墊。事實(shí)上，蟻群優(yōu)化算法最初用于解決與本文問題相類似的旅行商問題。之后又陸續(xù)滲透到諸如圖的著色問題、大規(guī)模集成電路設(shè)計(jì)、通訊網(wǎng)絡(luò)中的路由問題以及平衡問題、車輛調(diào)度問題等其他領(lǐng)域中。蟻群優(yōu)化算法在處理復(fù)雜優(yōu)化問題，尤其是離散優(yōu)化問題方面顯現(xiàn)出較強(qiáng)的優(yōu)越性。對(duì)蟻群而言，在根本原理已經(jīng)明確的條件下，重要的就是開發(fā)出求解問題的算法模型，使求解問題更加切實(shí)有效。2、遺傳算法模型：基于遺傳算法的使用領(lǐng)域很廣且算法效率高，本文多處運(yùn)用遺傳算法求解復(fù)雜優(yōu)化問題。這是一種模擬自然選擇和遺傳的隨機(jī)搜索算法，它最初被應(yīng)用于研究自然系統(tǒng)的適應(yīng)過程和設(shè)計(jì)具有自適應(yīng)性能的軟件。它也是一種高級(jí)最優(yōu)化技術(shù)，可以用來解決函數(shù)優(yōu)化、組合優(yōu)化、自動(dòng)控制、圖像處理、遺傳編程、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等。遺傳算法不單純是一種算法，也同樣是一種思考問題的方式，所以它有很多代擴(kuò)展的方向，如：遺傳算法的數(shù)學(xué)理論、分布并行遺傳算法、分類系統(tǒng)、遺傳神經(jīng)網(wǎng)絡(luò)、進(jìn)化算法、人工生命等。3、線性規(guī)劃模型：規(guī)劃問題是運(yùn)籌學(xué)中重要的分支，許多復(fù)雜問題都可以被抽象為線性、非線性、整數(shù)、0-1規(guī)劃等。本文兩處運(yùn)用線性規(guī)劃均取得一定的進(jìn)展，除此之外，它還可以處理包括下料問題、配料問題、選址問題、指派問題、投資問題、裝箱問題、最短路問題、最小生成樹和最優(yōu)連線問題等諸多看似一籌莫展的課題。4、馬克威分析系統(tǒng)馬克威分析系統(tǒng)是一款我國技術(shù)人員自行開發(fā)的軟件，主要功能有：統(tǒng)計(jì)分析、數(shù)據(jù)挖掘、統(tǒng)計(jì)圖表制作。其操作十分方便，且結(jié)果顯示清晰，利用馬克威分析系統(tǒng)，可以編制分布數(shù)列、繪制統(tǒng)計(jì)圖、計(jì)算描述統(tǒng)計(jì)指標(biāo)；實(shí)現(xiàn)區(qū)間估計(jì)、參數(shù)檢驗(yàn)、非參數(shù)檢驗(yàn)、方差分析、相關(guān)與偏相關(guān)分析、回歸分析、時(shí)間序列分析、聚類分析、判別分析、主成分分析、因子分析等功能。5、LINGO軟件LINGO語言以其簡(jiǎn)潔、易于擴(kuò)展、“集合”特色等特點(diǎn)，在規(guī)劃方面獨(dú)樹一幟。它既能求解線性規(guī)劃問題，也有較強(qiáng)的求解非線性規(guī)劃問題的能力。LINGO軟件不僅運(yùn)行速度快、計(jì)算能力強(qiáng)而且內(nèi)置建模語言，提供幾十個(gè)內(nèi)部函數(shù)，從而能減少語句，較直觀的方式描述較大規(guī)模的優(yōu)化模型。它的運(yùn)用范圍很廣，可以用于解決各種線性、非線性規(guī)劃、多目標(biāo)規(guī)劃等復(fù)雜問題甚至實(shí)現(xiàn)非線性曲線擬合。6、Excel軟件Excel是MicrosoftOffice套件中的電子表格軟件，它的應(yīng)用很廣泛。Excel無需編程就可以實(shí)現(xiàn)其他軟件需要變成才能完成的復(fù)雜計(jì)算，能進(jìn)行各種數(shù)據(jù)的統(tǒng)計(jì)、運(yùn)算、處理和繪制統(tǒng)計(jì)圖形。Excel的數(shù)據(jù)功能主要有計(jì)算功能和數(shù)據(jù)分析功能兩大塊，前者指Excel有強(qiáng)大的計(jì)算能力，它提供了300多個(gè)內(nèi)部函數(shù)給用戶使用，還允許自定義函數(shù)。后者指Excel提供了“數(shù)據(jù)分析”工具包，內(nèi)含方差分析、回歸分析、協(xié)方差和相關(guān)系數(shù)、傅里葉分析、t檢驗(yàn)等分析工具。7、MATLAB軟件MATLAB是一種高效的工程計(jì)算語言，它將計(jì)算、可視化、編程等功能集于一個(gè)易于使用環(huán)境。其典型應(yīng)用包括數(shù)學(xué)計(jì)算、算法開發(fā)、數(shù)據(jù)采集、系統(tǒng)建模和仿真、數(shù)據(jù)分析和可視化、科學(xué)和工程繪圖以及應(yīng)用軟件開發(fā)等。MATLAB的一個(gè)重要特色就是它有一個(gè)套程序擴(kuò)展系統(tǒng)和一組稱之為工具箱的特殊應(yīng)用子程序——工具箱，每一個(gè)工具箱都是為某一類學(xué)科專業(yè)和應(yīng)用定制的，主要包括信號(hào)處理、控制系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、模糊邏輯、小波分析、系統(tǒng)仿真等方面的應(yīng)用。此外，MATLAB應(yīng)用程序接口〔API〕支持對(duì)C、JAVA、Fortran語言的交互編寫，使用戶能更加自如地解決實(shí)際的問題。本文中的蟻群算法、遺傳算法以及安排黃金周線路時(shí)都使用了MATLAB編程，其代碼簡(jiǎn)潔、可視化等特點(diǎn)已可見一斑。參考文獻(xiàn)：[1] 曾五一等，統(tǒng)計(jì)學(xué)，北京：北京大學(xué)出版社，2006年。[2] 李士勇，蟻群算法及其應(yīng)用，哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004年。[3] 雷英杰等，MATLAB遺傳算法工具箱及應(yīng)用，西安：西安電子科技大學(xué)出版社，2005年。[4] 周明等，遺傳算法原理及應(yīng)用，北京：國防工業(yè)出版社，1999年。[5] 袁新生等，LINGO和Excel在數(shù)學(xué)建模中的應(yīng)用，北京：科學(xué)出版社，2007年。[6] 求是科技，MATLAB7.0從入門到精通，北京：人民郵電出版社，2006年。[7] NirwanAnsar，EdwinHou著，李軍，邊肇祺譯，用于最優(yōu)化的計(jì)算智能，北京：清華大學(xué)出版社，1999年。[8] 國道距離信息，://crane88/road.asp?myid=312，2007年[9] 公路客運(yùn)，://china-holiday/online/skb/qhdh.asp?qhsm=新疆，2007年[10] 鐵路票價(jià)，://china-holiday/online/skb/skb.asp?xs=cc&cc=P8871/8874，2007年[11] 經(jīng)緯度查詢，://hjqing/find/jingwei/index.asp，2007年[12] 旅館住宿價(jià)格查詢，://zjxc/lixingshe3/szlxs186，2007年[13] 景點(diǎn)逗留時(shí)間：哈納斯湖,://xjx.cc/kanas/jpxl/guanguang.htm額爾齊斯河,:///asp/line/xianlu.htm阿勒泰,://soochina/article/articleshow.asp?ID=18257塔城,:///Article/ShowArticle.asp?ArticleID=1758克拉瑪依,://auyou/auyou/lyxlinfo.asp?auto_id=5088怪石溝,://bozhounews/2006-09/19/content_8079338.htm博爾塔拉,://bozhounews/2006-09/19/content_8079338.htm博樂,://bozhounews/2006-09/19/content_8079338.htm石河子,://soochina/article/articleshow.asp?ID=18253昌吉,://soochina/article/articleshow.asp?ID=18252烏魯木齊,://xjtstc/news/mj.asp?id=A20072121548535693364天山,://xjtstc/news/mj.asp?id=A2007281050373903767伊犁,://gotoxj/xianl/zj3.htm昭蘇邊境的乾隆格登碑,://travel.163/04/0830/17/0V25VKL900061DPB.html吐魯番,://xjtstc/news/mj.asp?id=A20072121548535693364哈密,:///travel/index.htm巴音布魯克天鵝湖,://uu97/jd_2450.html火焰山,://1/Travel_line/20069/Travel_line_1300.html回王陵,://tvtour/tour/lvj/hami/interest/08.htm克孜爾千佛洞,:///1ashjuku/lv/index.htm庫爾勒,://ylnet/travel/yllxs/ylxl3.htm博斯騰湖,://ylnet/travel/yllxs/ylxl3.htm阿克蘇,://1/Travel_line/20069/Travel_line_1300.html庫車大寺,://xjhy/line_detail.asp?id=1羅布泊,://auyou/auyou/lyxlinfo.asp?auto_id=1102樓蘭,:///tanxian.htm蘇丹·沙圖克麻扎,://26/kzly/_private/kz201.htm阿圖什,://26/kzly/_private/kz201.htm喀什,:///xinjiangsankeyou/kashidawakuyou.htm香妃墓,://lvyou114/line/line_show.asp?LineID=1578艾提尕清真寺,://lvyou114/line/line_show.asp?LineID=1578尼雅遺址,://visitxinjiang/xj/Article_Print.asp?ArticleID=3126和田,:///plans/plan.php?id=2949，2007年附錄：1、新疆境內(nèi)的33個(gè)旅游景點(diǎn)名稱及其相應(yīng)的觀光逗留時(shí)間，經(jīng)、緯度如下表所示：序號(hào)景點(diǎn)名稱景點(diǎn)觀光時(shí)間經(jīng)度緯度1哈納斯湖187.248.22額爾齊斯河0.586.947.83阿勒泰188.1547.866674塔城182.9666746.755克拉瑪依0.584.7666745.66怪石溝18345.27博爾塔拉281458博樂182.144.933339石河子185.9544.2666710昌吉187.244.211烏魯木齊1.587.6833343.7666712天山188.443.713伊犁181.843.914昭蘇邊境的乾隆格登碑0.58143.215吐魯番189.242.916哈密193.442.817巴音布魯克天鵝湖0.584.143.118火焰山0.590.243.619回王陵192.743.820克孜爾千佛洞0.582.741.821庫爾勒0.586.0666741.6833322博斯騰湖0.586.5333341.9523阿克蘇180.241.124庫車大寺0.582.941.625羅布泊490.441.626樓蘭688.841.627蘇丹·沙圖克麻扎0.2575.939.628阿圖什0.7576.1166739.7333329喀什175.939.430香妃墓0.576.239.531艾提尕清真寺0.575.939.232尼雅遺址682.63833和田179.937.12、景點(diǎn)間最短路矩陣：T=[0.0021.006.7315.979.9012.0211.0312.9718.9113.7121.000.0014.2723.5117.4419.5620.6322.5726.4521.256.7314.270.009.243.175.296.368.3012.186.9815.9723.519.240.006.078.199.2611.2012.207.009.9017.443.176.070.002.123.195.1315.3510.1512.0219.565.298.192.120.001.073.0117.4712.2711.0320.636.369.263.191.070.001.9418.5413.3412.9722.578.3011.205.133.011.940.0020.4815.2818.9126.4512.1812.2015.3517.4718.5420.480.005.2013.7121.256.987.0010.1512.2713.3415.285.200.0047.2656.8642.5945.4939.4237.3036.2338.1744.0141.2352.8162.4148.1451.0444.9742.8541.7843.7249.5646.7821.3128.8514.5814.6017.7519.8720.9422.8810.387.6026.0635.6621.3924.2918.2216.1015.0316.9722.8120.0328.9636.5022.2322.2525.4027.5228.5930.5318.0315.2551.3460.9446.6749.5743.5041.3840.3142.2548.0945.3135.9843.5229.2529.2732.4234.5435.6137.5525.0522.2736.5844.1229.8529.8733.0235.1436.2138.1525.6522.8737.4947.0932.8235.7229.6527.5326.4628.4034.2431.4639.1448.7434.4737.3731.3029.1828.1130.0534.3231.5447.2652.8121.3126.0628.9651.3435.9836.5837.4939.1456.8662.4128.8535.6636.5060.9443.5244.1247.0948.7442.5948.1414.5821.3922.2346.6729.2529.8532.8234.4745.4951.0414.6024.2922.2549.5729.2729.8735.7237.3739.4244.9717.7518.2225.4043.5032.4233.0229.6531.3037.3042.8519.8716.1027.5241.3834.5435.1427.5329.1836.2341.7820.9415.0328.5940.3135.6136.2126.4628.1138.1743.7222.8816.9730.5342.2537.5538.1528.4030.0544.0149.5610.3822.8118.0348.0925.0525.6534.2434.3241.2346.787.6020.0315.2545.3122.2722.8731.4631.540.005.5533.6321.2041.2846.4843.5542.9532.6334.285.550.0039.1821.2046.8352.0349.1048.5038.1839.8333.6339.180.0012.437.6537.7114.6715.2723.8623.9421.2026.7512.430.0020.0825.2822.3521.7511.4313.0841.2846.837.6520.080.0045.367.027.6221.0716.2946.4852.0337.7125.2845.360.0045.4944.8935.4336.2243.5549.1014.6722.357.0245.490.000.6014.059.2742.9548.5015.2721.757.6244.890.600.0013.458.6732.6338.1823.8611.4321.0735.4314.0513.450.004.7834.2839.8323.9413.0816.2936.229.278.674.780.00]。3、主要程序：程序1：Floyd算法求最短路：function[zita,GA]=Floyed(C)%%程序說明：%本程序?yàn)橛肍loyed算法求最短路路徑%%變量說明：%輸入變量：%C；鄰接矩陣；%輸出變量：%zita：逆向追蹤法矩陣；%GA：最短路徑矩陣；%%GA=C;%GA為記錄最短路徑距離之陣；M=10000;n=length(C);line=[1:n]';zita=zeros(n,n);%初始化逆向追蹤矩陣；fori=1:nzita(:,i)=line;endzita0=zita;fork=1:nfori=1:nforj=1:n%每行每列比擬，假設(shè)新距離小于舊距離，那么替換；ifi~=k&&j~=k&&i~=jifGA(i,k)+GA(k,j)<GA(i,j)&&GA(i,k)+GA(k,j)<M/2GA(i,j)=GA(i,k)+GA(k,j);zita(i,j)=zita0(k,j);endendendendzita0=zita;%更新逆向追蹤矩陣；end程序2：精英蟻群算法求解遍歷最短路function[TM,LM]=ASPSP(C)%%程序說明：%本程序?yàn)橛脦Ь⑽浵伈呗郧蠼饴眯猩虇栴}。%%變量說明：%輸入變量：%C：城市坐標(biāo)；%輸出變量：%TM：近似最優(yōu)路徑；%LM：近似最短距離；%%tic;D=C;alpha=1;beta=5;rho=0.5;Q=100;Tao0=1e-6;e=5;Maxtime=200;n=length(D);m=n;Ta=Tao0*ones(n,n)-Tao0*eye(n);TM=[];LM=100000;ant=zeros(m,n+1);ata=zeros(m,n);fori=1:mforj=i+1:nata(i,j)=1/D(i,j);ata(j,i)=ata(i,j);endendfortime=1:Maxtimefork=1:mcity(k,:)=1:n;ends=1;fori=1:mant(i,s)=unidrnd(n);ant(i,n+1)=ant(i,s);city(i,ant(i,s))=0;endwhiles<np=zeros(m,n);fori=1:mA(i)=0;forj=1:nifcity(i,j)~=0A(i)=A(i)+(Ta(ant(i,s),j)^alpha)*(ata(ant(i,s),j)^beta);endendforj=1:nifcity(i,j)~=0p(i,j)=(Ta(ant(i,s),j)^alpha)*(ata(ant(i,s),j)^beta)/A(i);endendpp=unifrnd(0,1);j=1;whilepp>0pp=pp-p(i,j);j=j+1;endj=j-1;ant(i,s+1)=j;fork=1:nifcity(i,k)==j;city(i,k)=0;break;endendends=s+1;endL=compu(ant,D);[Lmin,t]=min(L);ifLmin<LMLM=Lmin;TM=ant(t,:);enddeltaTa=zeros(m,n);fori=1:mforj=1:n-1deltaTa(ant(i,j),ant(i,j+1))=deltaTa(ant(i,j),ant(i,j+1))+Q/L(i);endendforj=1:n-1deltaTa(TM(j),TM(j+1))=deltaTa(TM(j),TM(j+1))+Q/LM;endfori=1:mforj=1:nTa(i,j)=rho*Ta(i,j)+deltaTa(i,j);endendtrace(time)=LM;endfigure(1);plot(trace);toc;functionD=Distance(C)n=length(C);D=zeros(n,n);fori=1:nforj=i+1:nD(i,j)=norm(C(:,i)-C(:,j));D(j,i)=D(i,j);endendfunctionL=compu(ant,D);fori=1:length(D)L(i)=0;forj=1:length(ant)-1L(i)=L(i)+D(ant(i,j),ant(i,j+1));endend程序3：?jiǎn)栴}一的MATLAB遺傳算法程序function[y,road]=GATSP1%程序說明：%本程序?yàn)檫z傳算法求解旅行商問題%%變量說明：%輸入：%D：城市位置矩陣n*2。%輸出：%y：近似最短路徑的總長(zhǎng)度；%road：近似最短路徑。%ticD=[0.00 6.73 15.97 9.90 12.02 11.03 12.97 18.91 13.71 21.31 26.06 28.96 35.98 36.58 37.49 39.146.73 0.00 9.24 3.17 5.29 6.36 8.30 12.18 6.98 14.58 21.39 22.23 29.25 29.85 32.82 34.4715.97 9.24 0.00 6.07 8.19 9.26 11.20 12.20 7.00 14.60 24.29 22.25 29.27 29.87 35.72 37.379.90 3.17 6.07 0.00 2.12 3.19 5.13 15.35 10.15 17.75 18.22 25.40 32.42 33.02 29.65 31.3012.02 5.29 8.19 2.12 0.00 1.07 3.01 17.47 12.27 19.87 16.10 27.52 34.54 35.14 27.53 29.1811.03 6.36 9.26 3.19 1.07 0.00 1.94 18.54 13.34 20.94 15.03 28.59 35.61 36.21 26.46 28.1112.97 8.30 11.20 5.13 3.01 1.94 0.00 20.48 15.28 22.88 16.97 30.53 37.55 38.15 28.40 30.0518.91 12.18 12.20 15.35 17.47 18.54 20.48 0.00 5.20 10.38 22.81 18.03 25.05 25.65 34.24 34.3213.71 6.98 7.00 10.15 12.27 13.34 15.28 5.20 0.00 7.60 20.03 15.25 22.27 22.87 31.46 31.5421.31 14.58 14.60 17.75 19.87 20.94 22.88 10.38 7.60 0.00 12.43 7.65 14.67 15.27 23.86 23.9426.06 21.39 24.29 18.22 16.10 15.03 16.97 22.81 20.03 12.43 0.00 20.08 22.35 21.75 11.43 13.0828.96 22.23 22.25 25.40 27.52 28.59 30.53 18.03 15.25 7.65 20.08 0.00 7.02 7.62 21.07 16.2935.98 29.25 29.27 32.42 34.54 35.61 37.55 25.05 22.27 14.67 22.35 7.02 0.00 0.60 14.05 9.2736.58 29.85 29.87 33.02 35.14 36.21 38.15 25.65 22.87 15.27 21.75 7.62 0.60 0.00 13.45 8.6737.49 32.82 35.72 29.65 27.53 26.46 28.40 34.24 31.46 23.86 11.43 21.07 14.05 13.45 0.00 4.7839.14 34.47 37.37 31.30 29.18 28.11 30.05 34.32 31.54 23.94 13.08 16.29 9.27 8.67 4.78 0.00];NIND=100;%種群數(shù)量；MAXGEN=500;%最大遺傳代數(shù)；pc=0.8;%交叉概率；pm=0.1;%變異概率；N=length(D(:,1));%求城市數(shù)量%隨機(jī)生成初始種群fori=1:NINDB(i,:)=manu(N);F(i)=Distance(B(i,:),N,D);endSelCh=B;F=F';FitnV=(10000./F);%計(jì)算適應(yīng)度forgen=1:MAXGENfort=1:floor(NIND/30)%尋找每代的一局部最優(yōu)群種以便遺傳給下一代fori=1:NINDifF(i)==min(F)bestSelCh(t,:)=SelCh(i,:);bestFit(t)=F(i);break;endendendSelCh=select('rws',SelCh,FitnV);%選擇fori=1:0.1*NIND%生成一局部子代Chrom(i,:)=manu(N);C(i)=Distance(Chrom(i,:),N,D);G(i)=10000/C(i);endSelCh=reins(SelCh,Chrom,1,1,F,G');%插入SelCh=Crossover(SelCh,N,NIND,pc);%交叉SelCh=Muta(SelCh,N,NIND,pm);%變異fori=1:NINDF(i)=Distance(SelCh(i,:),N,D);endfort=1:floor(NIND/30)%遺傳的最優(yōu)個(gè)體替換適應(yīng)度最差的新個(gè)體fori=1:NINDifF(i)==max(F)SelCh(i,:)=bestSelCh(t,:);F(i)=bestFit(t);break;endendendFitnV=(10000./F);%計(jì)算適應(yīng)度trace(gen,1)=min(F);%尋找每一代的最優(yōu)值fori=1:NINDifF(i)==trace(gen,1)key=SelCh(i,:);break;endendtrace(gen,2)=mean(F);%尋找每一代的平均值ifgen==1y=trace(gen,1);road=key;elseify>trace(gen,1)y=trace(gen,1);road=key;%尋找當(dāng)前最優(yōu)路徑endendendtoc%作圖，觀察遺傳代數(shù)與路徑長(zhǎng)度的關(guān)系figure(2);holdon;plot(trace(:,1));plot(trace(:,2),'r');title('性能追蹤');xlabel('進(jìn)化代數(shù)');ylabel('目標(biāo)值');legend('最正確值','平均值');grid;holdoff%交叉函數(shù)，使用CX方法functionBB=Crossover(B,N,NIND,pc)tem=B(:,1);B(:,1)=[];fori=1:2:NIND-1ifunifrnd(0,1,1,1)<pcc1=B(i,:);c2=B(i+1,:);k=1;FLAG=0;FLAG(k)=1;STOP=0;fort