本文關鍵詞：PBIL算法求解車輛路徑優(yōu)化問題

  更多相關文章： 車輛路徑問題 PBIL算法 全局搜索 局部搜索

【摘要】：物流產(chǎn)業(yè)是國民經(jīng)濟發(fā)展的第三重要源泉,特別是進入21世紀以來,大力提倡發(fā)展現(xiàn)代物流產(chǎn)業(yè),而車輛路徑問題是現(xiàn)代物流的關鍵環(huán)節(jié),對車輛路徑問題的研究具有重要的理論及經(jīng)濟意義。1959年Dantzing和Ramser首次提出車輛路徑問題(Vehicle Routing Problem, VRP),自提出以來,VRP問題一直是眾多專家在運籌學、應用數(shù)學及計算機應用等學科領域的研究熱點。根據(jù)約束條件的不同可以將VRP問題劃分為多個調(diào)度問題。研究最早的是非對稱TSP問題(Asymmetric Traveling Salesman Problem, ATSP);研究較多是的帶容量約束車輛路徑問題(Capacitated Vehicle Routing Problem, CVRP);研究中與實際結合緊密的是帶軟時間窗約束車輛路徑問題(Vehicle Routing Problem with Soft Time Windows, VRPSTW)。VRP問題已經(jīng)被證明具有NP-hard屬性,在應用和理論上都有較高的研究意義。傳統(tǒng)的精確算法不能對大規(guī)模的此類問題求解,因此需要用智能算法求得較優(yōu)解。種群增量學習算法(Population-based Incremental Learning Algorithm, PBIL)是分布估計算法(Estimation of Distribution Algorithms,EDA)的一種,其特有的概率模型可以引導算法在優(yōu)質(zhì)解空間中的細致搜索。本文主要用種群增量學習算法對ATSP、CVRP、VRPSTW問題進行求解。(1)針對ATSP問題,提出了一種新的PBIL算法,將傳統(tǒng)PBIL算法中的二進制編碼方式改進為十進制的編碼方式,減少編碼的轉(zhuǎn)換過程,設計新的學習概率矩陣更新方式,提高了算法的搜索效率。(2)針對帶容量約束的問題,改進(1)中PBIL算法里的學習概率矩陣更新方式,使得全局搜索更加精確有效,和局部算法相結合,增強了算法的魯棒性。(3)針對軟時間窗問題,將(2)PBIL算法中融入均勻分布和輪盤賭兩種選擇方式,并加入2-opt和Insert局部搜索,將概率矩陣設計為三維,平衡全局搜索和局部搜索,提高算法的有效性和高效性。本文最后都用仿真實驗和算法比較的方式,證明了上述所提出算法的有效性。
【關鍵詞】：車輛路徑問題 PBIL算法 全局搜索 局部搜索
【學位授予單位】：昆明理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：U116.2;F252
【目錄】：

• 摘要5-6
• ABSTRACT6-11
• 第一章 緒論11-25
• 1.1 車輛路徑優(yōu)化問題背景及意義11
• 1.2 車輛路徑問題描述11-18
• 1.2.1 車輛路徑問題構成與分類11-14
• 1.2.2 車輛路徑問題數(shù)學模型描述14-15
• 1.2.3 車輛路徑優(yōu)化問題國內(nèi)外研究現(xiàn)狀15-18
• 1.3 求解車輛路徑優(yōu)化問題算法概述18-22
• 1.3.1 精確算法18
• 1.3.2 啟發(fā)式算法18-22
• 1.4 本文主要的研究工作22-25
• 第二章 PBIL算法求解非對稱TSP問題25-35
• 2.1 引言25-26
• 2.2 ATSP的數(shù)學模型26
• 2.3 NPBIL算法26-31
• 2.3.1 解的表示26-27
• 2.3.2 學習概率矩陣簡介27
• 2.3.3 解的生成27-28
• 2.3.4 學習概率矩陣的更新28-29
• 2.3.5 NPBIL的局部搜索29-30
• 2.3.6 NPBIL的算法步驟30-31
• 2.4 實驗仿真與比較31-32
• 2.4.1 實驗設置31
• 2.4.2 NPBIL算法與其他算法的比較31-32
• 2.5 本章小結32-35
• 第三章 PBIL算法求解帶容量約束的VRP問題35-49
• 3.1 引言35-36
• 3.2 帶容量約束VRP問題的模型36-37
• 3.3 混合的PBIL算法37-44
• 3.3.1 解的表示37-38
• 3.3.2 學習概率矩陣模型38
• 3.3.3 解的生成38-40
• 3.3.4 學習概率矩陣的更新40
• 3.3.5 HPBIL的局部搜索40-42
• 3.3.6 HPBIL的算法步驟42-44
• 3.4 實驗仿真與比較44
• 3.4.1 實驗設置44
• 3.4.2 HPBIL算法與其他算法的比較44
• 3.5 本章小結44-49
• 第四章 PBIL算法求解帶軟時間窗的VRP問題49-61
• 4.1 引言49-50
• 4.2 帶軟時間窗的VRP問題模型50-52
• 4.3 改進的PBIL算法52-56
• 4.3.1 解的編碼52
• 4.3.2 全局搜索52-55
• 4.3.3 局部搜索55
• 4.3.4 IPBIL的算法步驟55-56
• 4.4 仿真實驗與比較56-57
• 4.5 本章小結57-61
• 第五章 總結與展望61-63
• 5.1 論文總結61-62
• 5.2 研究展望62-63
• 致謝63-65
• 參考文獻65-71
• 附錄A 攻讀碩士期間研究成果71

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 高麗萍;彭敦陸;鄧桂英;陳慶奎;;面向企業(yè)應用的“算法設計與分析”課程建設改革探索[J];中國電力教育;2011年20期

2 姜楓;;“算法設計與分析”課程教學改革探索[J];中國電力教育;2013年26期

3 蘇安婕;吳志剛;;關鍵步分解法在算法設計與描述中的應用[J];成組技術與生產(chǎn)現(xiàn)代化;2011年03期

4 雷小園;;排列組合的算法設計與C++實現(xiàn)[J];中國新技術新產(chǎn)品;2010年10期

5 肖建華,何宏,陳展,歐陽湘江;算法中數(shù)學策略的應用與研究[J];湖南工程學院學報(自然科學版);2004年02期

6 余嶸華,張霆,張云;票證結存算法設計[J];合肥工業(yè)大學學報(自然科學版);2000年S1期

7 馮平;黃名選;;由頻繁項集生成關聯(lián)規(guī)則的算法設計和實現(xiàn)[J];廣西工學院學報;2007年01期

8 王卿;路曉偉;;高等院校學分制教學排考問題算法設計[J];上海理工大學學報;2007年06期

9 劉永廣;葉梧;馮穗力;莊宏成;;基于蟻群算法的無線Mesh網(wǎng)公平路由算法[J];華南理工大學學報(自然科學版);2009年01期

10 邢春峰,柳重堪;聯(lián)想記憶系統(tǒng)的學習算法設計(I)[J];北京聯(lián)合大學學報;1998年03期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 雷詠梅;;橢圓曲線密碼體制的算法設計與實現(xiàn)[A];西部大開發(fā) 科教先行與可持續(xù)發(fā)展——中國科協(xié)2000年學術年會文集[C];2000年

2 楊盤洪;朱軍祥;趙建安;楊靜;;機動目標跟蹤的模糊變結構交互多模算法[A];2007'中國儀器儀表與測控技術交流大會論文集（二）[C];2007年

3 徐子珊;;《算法設計與分析》課程中的工程教育[A];2005年全國理論計算機科學學術年會論文集[C];2005年

4 王輝;劉治昌;;用一種新算法設計的安全系統(tǒng)[A];2007年中國智能自動化會議論文集[C];2007年

5 舒輝;柳清峰;杜祝平;周蓓;;實踐教學模式在本科專業(yè)課程教學中的應用[A];中國電子教育學會高教分會2010年論文集[C];2010年

6 彭小宏;陽東升;劉忠;;基于聚類算法的組織協(xié)作網(wǎng)設計[A];2006中國控制與決策學術年會論文集[C];2006年

7 李皓;羅熊;;云存儲部署優(yōu)化的進化算法設計[A];2013年中國智能自動化學術會議論文集（第三分冊）[C];2013年

8 羅長政;李熙瑩;王鎮(zhèn)波;羅東華;;一種大流量交叉路口的背景提取與更新算法[A];第十五屆全國圖象圖形學學術會議論文集[C];2010年

9 楊利;李霖;昌月樓;陽國貴;;對稱位向量及啟發(fā)式并行散列連接算法[A];數(shù)據(jù)庫研究與進展95——第十三屆全國數(shù)據(jù)庫學術會議論文集[C];1995年

10 張晉;;嵌入式電腦鼠運行算法的研究[A];全國第20屆計算機技術與應用學術會議（CACIS·2009）暨全國第1屆安全關鍵技術與應用學術會議論文集（上冊）[C];2009年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 ;算法設計的策略[N];電腦報;2003年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 江立輝;基于干擾對齊的多用戶無線傳輸優(yōu)化方法研究[D];哈爾濱工業(yè)大學;2015年

2 史亞;多核學習算法與應用研究[D];西安電子科技大學;2015年

3 薛菲;基于蝙蝠算法的啟發(fā)式智能優(yōu)化研究與應用[D];北京工業(yè)大學;2016年

4 谷偉哲;齊次光滑算法及其應用[D];天津大學;2010年

5 龍海俠;進化算法及其在生物信息中的應用[D];江南大學;2010年

6 譚躍;具有混沌局部搜索策略的粒子群優(yōu)化算法研究[D];中南大學;2013年

7 尤海峰;求解隱式目標優(yōu)化問題的交互式進化算法研究[D];中國科學技術大學;2011年

8 張常淳;基于MapReduce的大數(shù)據(jù)連接算法的設計與優(yōu)化[D];中國科學技術大學;2014年

9 郭崇慧;地區(qū)中長期發(fā)展規(guī)劃若干定量模型、算法及應用研究[D];大連理工大學;2002年

10 蔣蔚;粒子濾波改進算法研究與應用[D];哈爾濱工業(yè)大學;2010年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 李欣園;基于選擇偏好的組合聚類算法研究與實現(xiàn)[D];內(nèi)蒙古大學;2015年

2 楊瀟;界約束非線性最小二乘問題的無導數(shù)算法[D];上海交通大學;2015年

3 王曉璐;基于Zynq的LS-SVM算法加速器設計[D];哈爾濱工業(yè)大學;2015年

4 樓磊磊;醫(yī)療保險數(shù)據(jù)異常行為檢測算法和系統(tǒng)[D];浙江大學;2015年

5 齊海龍;基于改進人工蜂群算法的非線性系統(tǒng)辨識方法研究[D];北京化工大學;2015年

6 蔡平梅;結構化稀疏信號的恢復算法研究[D];上海大學;2015年

7 趙晨陽;基于蟻群算法的高階圖匹配方法研究[D];西安電子科技大學;2014年

8 茍清松;多目標粒子濾波檢測前跟蹤算法研究[D];電子科技大學;2015年

9 李枝勇;蝙蝠算法及其在函數(shù)優(yōu)化中的應用研究[D];上海理工大學;2013年

10 李蓮;基于蜂群和粗糙集的聚類算法研究[D];長沙理工大學;2014年

，

本文編號：863189