【摘要】：帶時(shí)間窗車輛路徑問題(Vehicle Routing Problems Wih Time Windows,簡稱VRPTW)是在基本車輛路徑問題(Vehicle Routing Problems,簡稱VRP)基礎(chǔ)上增加時(shí)間窗約束衍生而來的組合優(yōu)化問題。由于VRPTW已被證明是一個(gè)NP難問題,因此如何有效求解VRPTW是一個(gè)研究難點(diǎn)。人工蜂群算法(Artificial Bee Colony Algorithm,簡稱ABC算法)是一種模仿蜜蜂采蜜覓食等行為的群智能優(yōu)化算法,在求解NP難問題中有非常不錯(cuò)的效果。本文圍繞車輛數(shù)和車輛行駛距離這兩個(gè)目標(biāo)基于VRPTW對(duì)ABC算法做了大量改進(jìn)以及研究,主要工作如下:本文首先探討了ABC算法的理論基礎(chǔ),根據(jù)VRPTW的特點(diǎn)將標(biāo)準(zhǔn)ABC算法離散化。本文設(shè)計(jì)了一種新的數(shù)據(jù)結(jié)構(gòu),采用兩個(gè)方向的單鏈表,使用二維編碼方式表示每個(gè)解,重新定義了蜂群在對(duì)食物源進(jìn)行鄰域變換時(shí)的編碼更新公式,給出了建立初始種群以及產(chǎn)生偵查蜂的方法。由于標(biāo)準(zhǔn)離散ABC算法求解精度很差,本文對(duì)標(biāo)準(zhǔn)離散ABC算法做了改進(jìn),提出了改進(jìn)離散ABC算法。結(jié)合二維編碼的結(jié)構(gòu),算法在蜂群做鄰域搜索時(shí)采用了路徑間和路徑內(nèi)兩種搜索方向,并提出了一種最優(yōu)插入策略以提高插入操作的成功率。在偵查蜂階段本文引入了限制變量,設(shè)計(jì)了新的淘汰機(jī)制,增加產(chǎn)生新解的迭代次數(shù)以提高新解的競爭力。本文設(shè)置了公告欄,通過更新公告欄記錄全局最優(yōu)解,防止最優(yōu)解在迭代過程中被拋棄。通過與標(biāo)準(zhǔn)離散ABC算法、其他啟發(fā)式算法、數(shù)據(jù)庫中最優(yōu)解做對(duì)比,改進(jìn)離散ABC算法在能找到最佳車輛數(shù)的情況下保持很高的精度。為了進(jìn)一步探索改進(jìn)離散ABC算法種群收斂能力,本文從方差和熵兩個(gè)方面研究了該算法在求解VRPTW中的種群多樣性。通過實(shí)驗(yàn)數(shù)據(jù)證明改進(jìn)離散ABC算法在整個(gè)迭代過程中種群分布較廣,空間搜索能力很強(qiáng),一直維持一個(gè)比較高的種群多樣性。
【學(xué)位授予單位】：武漢輕工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP18
【圖文】：

第二章 理論基礎(chǔ)第 章 理論基礎(chǔ)本章是論文的理論基礎(chǔ)，介紹了 VRPTW 和 ABC 算法的基礎(chǔ)知識(shí)，為究做理論準(zhǔn)備。VRPTW 理論基礎(chǔ)本文研究的是單車場、單時(shí)間窗、硬時(shí)間窗、非時(shí)變的 VRPTW。如圖，該問題可描述為：從配送中心派送若干相同載重量的車輛，車輛在滿點(diǎn)時(shí)間窗約束、客戶服務(wù)唯一性約束、自身載重量約束等其他約束條件完所有客戶點(diǎn)之后，最后回到配送中心，使得所需車輛數(shù)最少和所有車總路程最短。二

圖 4.1 標(biāo)準(zhǔn)蜂群算法和改進(jìn)蜂群算法收斂對(duì)比結(jié)果分析，從圖 4.1 中我們可以看出，無論是標(biāo)準(zhǔn)離散 ABC 算法，還是改進(jìn)離散 ABC 算法，在求解 VRPTW 問題上的收斂速度都特別快，在很短的時(shí)間內(nèi)都可以搜尋到一個(gè)局部滿意解，這也是 ABC 算法的一大優(yōu)勢，從兩個(gè)算法的收斂對(duì)比中我們可以發(fā)現(xiàn)改進(jìn)離散 ABC 算法的搜索深度和局部搜索能力都比標(biāo)準(zhǔn)離散 ABC 算法更強(qiáng)，更容易跳出局部最優(yōu)，在解空間中繼續(xù)尋找更好的解，直至找到全局最優(yōu)解。下面我們根據(jù)不同的算例來對(duì)比分析標(biāo)準(zhǔn)離散 ABC 算法和改進(jìn)離散 ABC算法，見表 4.1。表 4.1 標(biāo)準(zhǔn)離散 ABC 算法和改進(jìn)離散 ABC 算法求解 VRPTW 結(jié)果比較標(biāo)準(zhǔn) ABC 算法 改進(jìn) ABC 算法算例車輛數(shù) 最優(yōu)值 平均數(shù) 車輛數(shù) 最優(yōu)值 平均數(shù)C101.100 17 1351.6 1415.6 10 828.9828.9C102.100 15 1266.2 1341.5 10 828.9830.7

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 歐陽普仁,楊叔子;一種改進(jìn)的Marple算法[J];南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年01期

2 黃小蓓;隆永紅;;分布式數(shù)據(jù)庫管理系統(tǒng)中的N&發(fā)控制——算法及其性能分析[J];計(jì)算技術(shù)與自動(dòng)化;1988年02期

3 馮成進(jìn);;0—1規(guī)劃新算法的改進(jìn)[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年02期

4 曾秀;魏振華;;猴群算法及其改進(jìn)綜述[J];電腦知識(shí)與技術(shù);2017年32期

5 許燦英;;算法合謀反競爭問題初探[J];合肥工業(yè)大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版);2019年02期

6 段艷明;肖輝輝;林芳;;新授粉方式的花授粉算法[J];計(jì)算機(jī)工程與應(yīng)用;2018年23期

7 肖海軍;王芬艷;盧常景;曹穎;;一種有效的多峰優(yōu)化鳥群算法[J];中南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2018年04期

8 覃遠(yuǎn)年;梁仲華;;蟻群算法研究與應(yīng)用的新進(jìn)展[J];計(jì)算機(jī)工程與科學(xué);2019年01期

9 肖輝輝;段艷明;林芳;;新搜索策略的花授粉算法[J];電子測量與儀器學(xué)報(bào);2019年07期

10 梁昔明;高超;龍文;;基于速度越界處理與高斯擾動(dòng)的改進(jìn)蝙蝠算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2019年19期

相關(guān)會(huì)議論文 前10條

1 苗強(qiáng);劉曉琳;王仲奇;;隨機(jī)球重疊判斷算法改進(jìn)研究工作進(jìn)展[A];中國原子能科學(xué)研究院年報(bào) 2013[C];2014年

2 殷凡;王海斌;李超;;改進(jìn)蝙蝠算法在DOA估計(jì)中的應(yīng)用[A];2019年全國聲學(xué)大會(huì)論文集[C];2019年

3 李超;余昭平;;基于矩陣的Apriori算法改進(jìn)研究[A];第二屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會(huì)議（NCIRCS-2005）論文集[C];2005年

4 王蓬;宋明玉;張林芳;王新遠(yuǎn);;廣義自適應(yīng)相干累積算法改進(jìn)及其在線譜增強(qiáng)中的應(yīng)用[A];中國聲學(xué)學(xué)會(huì)2007年青年學(xué)術(shù)會(huì)議論文集（上）[C];2007年

5 孫迪峰;方厚林;梁旭斌;趙天青;張亮永;;寬帶MUSIC算法中同步干擾研究[A];2019年全國聲學(xué)大會(huì)論文集[C];2019年

6 郝紅星;吳玲達(dá);宋漢辰;;一種殘損圖像修補(bǔ)算法改進(jìn)與實(shí)現(xiàn)[A];第18屆全國多媒體學(xué)術(shù)會(huì)議（NCMT2009）、第5屆全國人機(jī)交互學(xué)術(shù)會(huì)議（CHCI2009）、第5屆全國普適計(jì)算學(xué)術(shù)會(huì)議（PCC2009）論文集[C];2009年

7 解迎剛;王志良;鄭珊山;;基于LANDMARC及其算法改進(jìn)的RFID室內(nèi)定位研究[A];第二十九屆中國控制會(huì)議論文集[C];2010年

8 王篤俠;冷晟;周燕飛;;單件小批生產(chǎn)模式下的MRP算法改進(jìn)[A];全國先進(jìn)制造技術(shù)高層論壇暨第七屆制造業(yè)自動(dòng)化與信息化技術(shù)研討會(huì)論文集[C];2008年

9 鄒錦峰;;水面仿真研究及算法改進(jìn)[A];全國首屆數(shù)字（虛擬）科技館技術(shù)與應(yīng)用學(xué)術(shù)研討會(huì)論文集[C];2007年

10 林關(guān)成;李亞安;;一種支持向量機(jī)訓(xùn)練集選取算法改進(jìn)[A];2009’中國西部地區(qū)聲學(xué)學(xué)術(shù)交流會(huì)論文集[C];2009年

相關(guān)重要報(bào)紙文章 前2條

1 記者 宛霞;風(fēng)云衛(wèi)星云導(dǎo)風(fēng)算法改進(jìn)[N];中國氣象報(bào);2018年

2 記者 陳姝;深企為大橋定制人臉識(shí)別方案[N];深圳商報(bào);2018年

相關(guān)博士學(xué)位論文 前10條

1 周凌云;幾種典型群智能算法及其更新機(jī)制研究[D];武漢大學(xué);2018年

2 張代雨;多學(xué)科優(yōu)化算法及其在水下航行器中的應(yīng)用[D];西北工業(yè)大學(xué);2017年

3 鐘林峰;復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的挖掘算法研究[D];電子科技大學(xué);2018年

4 邱實(shí);多光譜衛(wèi)星遙感影像云及云陰影精準(zhǔn)檢測算法研究[D];電子科技大學(xué);2018年

5 孫寧;人工免疫優(yōu)化算法及其應(yīng)用研究[D];哈爾濱工業(yè)大學(xué);2006年

6 陸楠;關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D];吉林大學(xué);2007年

7 胡銦;基于單目視覺的運(yùn)動(dòng)目標(biāo)檢測與跟蹤算法研究[D];南京理工大學(xué);2008年

8 王玨;生物地理學(xué)優(yōu)化算法的研究及應(yīng)用[D];哈爾濱工程大學(xué);2013年

9 黃松;面向多應(yīng)用場景的粒子群優(yōu)化算法研究[D];江南大學(xué);2017年

10 安琦;信號(hào)偵收中的識(shí)別與分類理論與算法研究[D];電子科技大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 毛振平;云平臺(tái)下醫(yī)療大數(shù)據(jù)的FP-Growth算法的優(yōu)化研究[D];華北水利水電大學(xué);2019年

2 陳晨;面向林業(yè)小班的坡度、坡向及坡位提取算法研究[D];浙江農(nóng)林大學(xué);2019年

3 楊閏;改進(jìn)TLBO算法及其在天線優(yōu)化設(shè)計(jì)中的應(yīng)用[D];杭州電子科技大學(xué);2019年

4 李文靜;改進(jìn)花授粉算法及其在社交網(wǎng)絡(luò)中的應(yīng)用研究[D];江西理工大學(xué);2019年

5 陳朝威;基于密度的聚類算法研究[D];北京交通大學(xué);2019年

6 李桃;智能算法及其在圖像處理中的應(yīng)用[D];西華師范大學(xué);2019年

7 趙冠宇;基于進(jìn)化計(jì)算的車聯(lián)網(wǎng)路側(cè)單元部署優(yōu)化方法研究[D];吉林大學(xué);2019年

8 陳婧文;基于鏈接改進(jìn)的BIRCH算法的研究與應(yīng)用[D];吉林大學(xué);2019年

9 呂桂新;基于改進(jìn)多標(biāo)記分布學(xué)習(xí)算法的評(píng)分預(yù)測[D];吉林大學(xué);2019年

10 彭國雯;基于深度學(xué)習(xí)的場景文字檢測算法的融合技術(shù)研究[D];河南大學(xué);2019年

本文編號(hào)：2726231