隨著現(xiàn)代經(jīng)濟(jì)飛速發(fā)展,尤其是電子商務(wù)平臺的快速崛起,使物流配送成為其不可或缺的一部分,人們對物流配送服務(wù)的需求也日益增加,而車輛路徑規(guī)劃問題作為物流配送行業(yè)的重要問題,自提出以來就吸引了運(yùn)籌學(xué)和組合優(yōu)化等領(lǐng)域工作者的廣泛研究。隨著客戶日趨嚴(yán)格的及時交付要求,帶硬時間窗車輛路徑問題越來越突出,而該問題的研究由于自身的復(fù)雜性目前還沒有得到很好的解決。因此,本文基于此開展研究,具體研究內(nèi)容如下:1.針對帶硬時間窗車輛路徑問題提出了一種改進(jìn)型煙花算法進(jìn)行求解,該算法能夠利用信息交互進(jìn)行資源分配。首先在傳統(tǒng)煙花算法的基礎(chǔ)上結(jié)合構(gòu)造算法產(chǎn)生初始煙花和路徑解決方案,然后對傳統(tǒng)煙花算法的爆炸算子進(jìn)行改進(jìn),使得煙花種群中適應(yīng)度值最優(yōu)煙花的爆炸搜索半徑能夠根據(jù)個體適應(yīng)度值自適應(yīng)地調(diào)整,增強(qiáng)算法后期局部搜索能力,再利用交叉重組完成爆炸火花的鄰域搜索,并通過變異操作來增強(qiáng)種群多樣性,最后通過煙花算法的分布式信息共享機(jī)制來避免算法早熟。2.針對改進(jìn)型煙花算法在求解客戶聚類測試集時存在行駛總距離較長問題,提出了一種基于模因算法的求解方法�？紤]到初始解的好壞影響算法的收斂速度,首先通過模糊聚類生成初始可行解以保證種群多樣性和算法后期的收斂性,然后對進(jìn)化模塊的進(jìn)化算子進(jìn)行改進(jìn),采用邊緣交叉重組算子進(jìn)行全局搜索以產(chǎn)生更多較優(yōu)個體,最后在局部優(yōu)化模塊采用節(jié)點(diǎn)交換和k-opt作為模因算子,對較優(yōu)個體進(jìn)行局部優(yōu)化以快速收斂到最優(yōu)解。3.Solomon標(biāo)準(zhǔn)測試集作為當(dāng)前國際通用的車輛路徑規(guī)劃問題參考標(biāo)準(zhǔn),方便各算法的集中比較,本文基于該測試集對上述主要研究方法開展相關(guān)實(shí)驗(yàn)研究,對所獲結(jié)果與當(dāng)前已公布最優(yōu)解進(jìn)行比較,以驗(yàn)證所提算法的有效性和可行性。4.最后,以順豐快遞蘭州集散中心為各營業(yè)點(diǎn)配送快遞為例,本文基于Flexsim仿真軟件進(jìn)行仿真實(shí)驗(yàn)研究,實(shí)驗(yàn)結(jié)果表明所提出的算法對求解帶硬時間窗車輛路徑問題具有一定的理論意義和應(yīng)用價值。
【學(xué)位單位】：蘭州理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：U463.6
【部分圖文】：

節(jié)約算法示意圖

帶硬時間窗的車輛路徑問題求解算法研究8圖 2.1 節(jié)約算法示意圖圖 2.2 節(jié)約算法求解路徑圖2.2.2 插入啟發(fā)式算法插入算法(Insertion Heuristic)作為典型的構(gòu)造啟發(fā)式算法，主要分為順序插入和并行插入兩類。順序插入算法是每一次只構(gòu)建一條路徑，開始時隨機(jī)選擇一個客戶構(gòu)建一條路徑，然后將未安排的客戶迭代地插入到當(dāng)前路徑中，直到滿足車載容量或違反時間窗約束，算法的核心在于確定下一個被插入到路徑的客戶和客戶插入的最佳位置。并行插入算法是同時構(gòu)造幾條路徑，在插入之前首先確定插入的路徑數(shù)量，然后構(gòu)建幾條初始路徑，計(jì)算將待插入客戶插入到現(xiàn)有路徑位置后產(chǎn)生的距離增加值，最后按照距離增加值遞增順序依次插入客戶直到所有客戶都被插入可行路徑。選取 Solomon25 個客戶的 R101 測試數(shù)據(jù)集對并行插入算法進(jìn)行測試，過程如圖 2.3 所示。種子客戶首先構(gòu)建兩條初始路徑，路徑外的點(diǎn)代表未安排的客戶，然后根據(jù)距離增加值將未安排的客戶依次插入到初始路徑中，最后在滿足車載容

圖 2.3 插入算法示意圖通過上述測試與分析發(fā)現(xiàn)：構(gòu)造啟發(fā)式算法將客戶插入到初始路徑中時，在插入前均需對約束進(jìn)行檢驗(yàn)，插入效率較低；當(dāng)客戶違反約束條件不能插入時則會構(gòu)建新的路徑，并且問題規(guī)模增加變復(fù)雜后，容易產(chǎn)生冗余路徑。2.3 經(jīng)典元啟發(fā)式算法簡介相比構(gòu)造啟發(fā)式算法，經(jīng)典元啟發(fā)式算法在算法設(shè)計(jì)上比較復(fù)雜，并且參數(shù)設(shè)置對算法性能影響較大，但采取全局搜索方式可以跳出局部最優(yōu)并獲得滿意解。2.3.1 遺傳算法遺傳算法是由美國的 J.Holland 教授和他的學(xué)生于 1975 年借鑒生物界物競天擇適者生存的進(jìn)化規(guī)律提出的一種隨機(jī)化搜索方法，算法具體流程如下圖 2.4 所示。遺傳算法廣泛應(yīng)用于組合優(yōu)化、信號處理和自適應(yīng)控制等領(lǐng)域，其主要特點(diǎn)是可以直接對對象進(jìn)行操作；具有良好的并行性和全局尋優(yōu)能力；概率化的尋優(yōu)
【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

9 肖輝輝;段艷明;;基于改進(jìn)花授粉算法的移動機(jī)器人路徑規(guī)劃研究[J];軟件導(dǎo)刊;2018年11期

10 莫海淼;趙志剛;曾敏;石靜;溫泰;;具有自適應(yīng)步長與協(xié)同尋優(yōu)的蝙蝠煙花混合算法[J];小型微型計(jì)算機(jī)系統(tǒng);2019年07期

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

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

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

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

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

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

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

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

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

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

10 周瑞紅;基于群智能優(yōu)化理論的聚類改進(jìn)方法及應(yīng)用研究[D];吉林大學(xué);2017年

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

1 朱昌龍;面向三維游戲場景的動態(tài)尋路算法的研究與應(yīng)用[D];武漢工程大學(xué);2018年

2 劉曉紅;改進(jìn)的AP-SVM算法研究及其在字母識別的應(yīng)用[D];廈門大學(xué);2017年

3 何逸凡;基于深度學(xué)習(xí)的視頻動作時空檢測算法研究[D];北京郵電大學(xué);2019年

4 林婉瑩;圖書推薦系統(tǒng)中提升Top-N列表多樣性算法研究[D];北京郵電大學(xué);2019年

5 董靜;基于主題模型和聚類算法的網(wǎng)絡(luò)熱點(diǎn)話題發(fā)現(xiàn)[D];河北大學(xué);2019年

6 牛群;帶硬時間窗的車輛路徑問題求解算法研究[D];蘭州理工大學(xué);2019年

7 李佩茜;一種高效的基于教與學(xué)的社區(qū)發(fā)現(xiàn)算法的研究[D];廈門大學(xué);2018年

8 裴華欣;自適應(yīng)密度峰劃分聚類算法研究及應(yīng)用[D];浙江工業(yè)大學(xué);2018年

9 朱炎亮;基于深度學(xué)習(xí)的人員異常操作視覺檢測算法[D];浙江工業(yè)大學(xué);2018年

10 曾辰子;改進(jìn)差分進(jìn)化算法及其收斂性分析[D];武漢理工大學(xué);2018年

本文編號：2850426