基于蟻群算法的車輛路徑規(guī)劃問題的研究

《基于蟻群算法的車輛路徑規(guī)劃問題的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、巧姑字種乂麟圍碩±學(xué)位論文?。増A磯基于蟻群算法的車輛路徑規(guī)劃問題的研究－目記篇陽庶２Ｌ薩Ｓｈ企幽導(dǎo)師姓名、職賴馬岸英研究員Ｚｌ！申請(qǐng)學(xué)位類別工程碩±圓西安電子科技大學(xué)學(xué)位論文獨(dú)創(chuàng)性（或創(chuàng)新性）聲巧秉承學(xué)校嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)和優(yōu)良的科學(xué)道德，本人聲明所呈交的論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加＾＾＾標(biāo)注和致謝中所羅列的內(nèi)容レッ外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研充成果；也不包含為獲得西安電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料＾同王。與我作的同事對(duì)本研究所做的任何貢

2、獻(xiàn)均已在論文中作了明確的說明并表示了謝意。一學(xué)位論文若有不實(shí)之處，本人承擔(dān)切法律責(zé)任。辦Ｉ＞巷建愛日ｉ王）：：本人簽名期西安電子科技大學(xué)關(guān)于論文使用授權(quán)的說明本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，目Ｐ；研究生在校攻讀學(xué)位期間論文了作的知識(shí)產(chǎn)權(quán)屬于西安電子科技乂學(xué)。學(xué)校有權(quán)保留送交論文、的復(fù)印件，允許查閱借閱論文；學(xué)校可Ｗ公布論文的全部或部分內(nèi)容，允許采用影印、縮印或其它復(fù)制手段保存論文。同時(shí)本人保證，結(jié)合學(xué)位論文研究成果完成的論文、保發(fā)密明專利等成果，署名單位為西安電子科技大學(xué)。本人的簽學(xué)位論文在＿年解密后適用本

3、授權(quán)書。？＞名：老挺娃ｆ導(dǎo)師簽名；日期：ＶＩＶ日期：學(xué)校代碼10701學(xué)號(hào)1301120650分類號(hào)TP301.6密級(jí)公開西安電子科技大學(xué)碩士學(xué)位論文基于蟻群算法的車輛路徑規(guī)劃問題的研究作者姓名：李建軍領(lǐng)域：電子與通信工程學(xué)位類別：工程碩士學(xué)校導(dǎo)師姓名、職稱：欒英姿副教授企業(yè)導(dǎo)師姓名、職稱：馬岸英研究員學(xué)院：通信工程學(xué)院提交日期：2015年11月ResearchonthevehicleroutingproblembasedonantcolonyalgorithmAthesissubmittedtoXIDIANUNIVERSITYinpartial

4、fulfillmentoftherequirementsforthedegreeofMasterinElectronicsandCommunicationsEngineeringByLiJianjunSupervisor:LuanYingziAssociateProfessorMaAnyingResearchFellowNovember2015摘要摘要車輛路徑規(guī)劃問題（VehicleRoutingProblem，VRP）是現(xiàn)代物流配送過程中的關(guān)鍵環(huán)節(jié)，而且其在眾多領(lǐng)域中都有廣泛的應(yīng)用，因此它的提出引起了不同學(xué)科的專家和物流管理者的極大重視,目前VRP已經(jīng)成為研究的熱點(diǎn)。但是如何找到

5、一種高效的算法使其在較短的時(shí)間內(nèi)找到比較滿意的全局解仍然是研究的重點(diǎn)。本文主要從以下幾個(gè)方面進(jìn)行闡述。（1）詳細(xì)介紹和比較分析了國(guó)內(nèi)外求解VRP問題的研究現(xiàn)狀和求解方法，重點(diǎn)闡述了基本蟻群算法（AntSystem，AS）的工作原理、數(shù)學(xué)模型和實(shí)現(xiàn)旅行商問題（TravelingSalesmanProblem，TSP）的求解過程，剖析了蟻群算法的復(fù)雜度、特征以及重要參數(shù)的設(shè)置對(duì)算法性能的影響情況。但是，如何在蟻群算法求解TSP問題的基礎(chǔ)上把其改造成適合求解VRP問題的算法是本文研究的主要內(nèi)容，而從此問題出發(fā)可以有兩個(gè)不同的方向：直接法和轉(zhuǎn)化法。（2）本文首先從直接法出發(fā)提出了兩種改進(jìn)蟻

6、群算法的技術(shù)。技術(shù)方案一（簡(jiǎn)稱ImproAS_VRP_ACSTSP）是先運(yùn)用初步改造好的蟻群算法得到一個(gè)VRP可行解，然后在這個(gè)解的基礎(chǔ)上分多段運(yùn)用蟻群TSP算法以對(duì)該VRP解進(jìn)行改善。技術(shù)方案二（簡(jiǎn)稱OutsideAdvancedAS_InsideACSTSP）不僅對(duì)蟻群算法進(jìn)行了充分的完善而且采用了兩次蟻群算法，外部的蟻群算法只是為了得到多種不同的分組方案，而內(nèi)部的蟻群算法則是為該分組規(guī)劃出較短路線并指導(dǎo)螞蟻按此路線行走。然后又從轉(zhuǎn)化法出發(fā)提出了一種新型改進(jìn)技術(shù)方案三（簡(jiǎn)稱MutationSweep_ACSTSP），它是在之前順序掃描算法的基礎(chǔ)上增加了變異操作，并將變異算子用于

7、掃描過程中，既可保證得到VRP解依舊是可行的又可使不同的分組之間距離較接近，這樣就可得到多個(gè)較合理的分組，然后在每個(gè)分組內(nèi)部實(shí)現(xiàn)路內(nèi)次序的再優(yōu)化，最后就可以得到VRP問題的最優(yōu)解。（3）利用Matlab在VRPLIB數(shù)據(jù)集上進(jìn)行仿真測(cè)試，記錄三種改進(jìn)算法找到的最優(yōu)目標(biāo)函數(shù)值及運(yùn)行時(shí)間，比較和分析得到的仿真結(jié)果，驗(yàn)證和評(píng)價(jià)這些改進(jìn)技術(shù)方案的合理性和有效性。關(guān)鍵詞：車輛路徑規(guī)劃問題，蟻群算法，旅行商問題，掃描法，VRPLIBIABSTRACTABSTRACTThevehi