發(fā)布時(shí)間：2020-07-26 20:33

【摘要】：車(chē)輛路徑問(wèn)題(Vehicle Routing Problem,VRP)是城市交通改善和物流配送管理等實(shí)際應(yīng)用中常見(jiàn)的問(wèn)題。本文主要求解多目標(biāo)的帶時(shí)間窗車(chē)輛路徑問(wèn)題(Vehicle Routing Problem with Time Window,VRPTW),同時(shí)最小化車(chē)輛配送數(shù)量和車(chē)輛行駛距離這兩個(gè)目標(biāo)。通過(guò)返回一個(gè)非支配解的集合而非單一的解,給決策者提供更強(qiáng)大的決策支持。多目標(biāo)VRPTW是典型的NP-Hard組合優(yōu)化問(wèn)題,現(xiàn)有的啟發(fā)式優(yōu)化算法難以獲得問(wèn)題的全局最優(yōu)解。智能優(yōu)化算法具有杰出的全局搜索能力,越來(lái)越多的被用以求解多目標(biāo)VRPTW。本文圍繞求解多目標(biāo)VRPTW的離散螢火蟲(chóng)膜優(yōu)化算法進(jìn)行了深入研究,主要做了以下方面的工作:(1)本文首先針對(duì)多目標(biāo)VRPTW這一具有重要現(xiàn)實(shí)意義的NP-Hard問(wèn)題,利用螢火蟲(chóng)算法本身多目標(biāo)尋優(yōu)的特性,提出一種基于時(shí)間窗劃分的改進(jìn)離散型螢火蟲(chóng)算法(MDGSO-TWD)。在算法中,首先根據(jù)時(shí)間窗對(duì)客戶(hù)點(diǎn)進(jìn)行分類(lèi),并由此設(shè)計(jì)了螢火蟲(chóng)個(gè)體的生成方式。為了更加真實(shí)有效地反映螢火蟲(chóng)算法的進(jìn)化機(jī)制,本文重新定義和設(shè)計(jì)了螢火蟲(chóng)算法的運(yùn)動(dòng)規(guī)則。在搜索過(guò)程中,使用隨機(jī)個(gè)體來(lái)替代種群中的重復(fù)個(gè)體以維持種群的多樣性。同時(shí),為了加快搜索速度,彌補(bǔ)算法局部搜索能力的不足,提出了一種基于時(shí)間窗分類(lèi)的模因鄰域搜索技術(shù)和自適應(yīng)螢火蟲(chóng)飛行步長(zhǎng)的概念來(lái)增強(qiáng)算法的局部搜索能力,并在搜索過(guò)程中采用精英策略記錄全局最優(yōu)解以防止算法退化。由于多目標(biāo)問(wèn)題的不可評(píng)估性,引入Pareto支配的概念來(lái)評(píng)估螢火蟲(chóng)個(gè)體的優(yōu)劣,并對(duì)生成Pareto非支配解集的方式進(jìn)行了重新設(shè)計(jì)。最后,通過(guò)仿真實(shí)驗(yàn)和對(duì)比實(shí)驗(yàn),驗(yàn)證了所提算法的可行性和有效性。(2)在改進(jìn)離散型螢火蟲(chóng)算法的基礎(chǔ)上,提出了一個(gè)度為3的組織P系統(tǒng)。通過(guò)分析膜計(jì)算模型的三個(gè)要素:對(duì)象、反應(yīng)規(guī)則和膜結(jié)構(gòu),建立了基于膜計(jì)算的螢火蟲(chóng)膜優(yōu)化算法(PDVA)。該算法不僅保留了常規(guī)膜計(jì)算系統(tǒng)的基本特征,還吸收了螢火蟲(chóng)算法的研究成果。在該系統(tǒng)中,以螢火蟲(chóng)編碼作為進(jìn)化對(duì)象,采用離散型螢火蟲(chóng)進(jìn)化機(jī)制和變鄰域進(jìn)化機(jī)制作為子算法對(duì)對(duì)象進(jìn)行進(jìn)化。使用細(xì)胞通訊規(guī)則對(duì)系統(tǒng)內(nèi)的對(duì)象進(jìn)行信息傳遞與共享。為了擴(kuò)大解空間的搜索區(qū)域,提高算法求解精度,在算法之中改進(jìn)了變鄰域進(jìn)化機(jī)制。最后,通過(guò)仿真實(shí)驗(yàn)和對(duì)比實(shí)驗(yàn),驗(yàn)證了所提算法的有效性和高效性。
【學(xué)位授予單位】：武漢輕工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：TP18;U491
【圖文】：

牛物計(jì)算樟型

本文根據(jù)客戶(hù)的服務(wù)時(shí)間窗，將客戶(hù)分為不同的類(lèi)，這有助于減群初始化和鄰域搜索算法。首先，將客戶(hù)分到不同的類(lèi)，然后將分類(lèi)結(jié)果用于種始化和鄰域搜索，我們可以對(duì)不同類(lèi)別的客戶(hù)采取不同的操作，在種群初始化階段為客戶(hù)類(lèi)別之間是互斥的，因此我們只需要選取不同類(lèi)別的客戶(hù)組成新的路徑，鄰域搜索階段，因?yàn)橥活?lèi)別的客戶(hù)擁有相似的服務(wù)時(shí)間窗口，因此我們只需要一類(lèi)別的客戶(hù)采取鄰域操作，相比于盲目搜索，這將有效的縮短算法搜索時(shí)間。服務(wù)時(shí)間窗口對(duì)客戶(hù)進(jìn)行分類(lèi)是 MDGSO-TWD 算法的基礎(chǔ)�？蛻�(hù)分類(lèi)的詳細(xì)步驟如算法 3.1 所示。首先，計(jì)算倉(cāng)庫(kù)的開(kāi)放時(shí)間窗口，并將為 K 個(gè)子類(lèi)，如圖 3.2 所示。第二，假如客戶(hù) c 的服務(wù)時(shí)間窗為[ec, lc]，對(duì)于某客戶(hù)類(lèi)別 j，如果[ec, lc] [e0+j*T/K, e0+(j+1)*T/K] ≠ ，那么客戶(hù) c 就被劃分戶(hù)類(lèi)別 j 中。重復(fù)這個(gè)過(guò)程直到所有的客戶(hù)都被分類(lèi)。在圖 3.2 中，K 為車(chē)輛數(shù)估計(jì)值。e0是倉(cāng)庫(kù)的最早開(kāi)放時(shí)間，0l 是倉(cāng)庫(kù)的最晚開(kāi)放時(shí)間，00T = l e。

for i=1 to K, T = ldepot- edepot3: for ( c ∈C) do4: C ←C/{c}5: for ( j=1; j≤K; j++) do6: if ([ec,lc] Timewindow(class(j)) ≠ ) then7: class(j)←class(j) {c}8: end if9: end for10: end for11: return class(i), for i=1 to K面舉例說(shuō)明這個(gè)過(guò)程。例如，如圖 3.3 所示，假設(shè)劃分的某兩個(gè)時(shí)間段為[10,30]，而客戶(hù) i 和 j 的服務(wù)時(shí)間窗口分別為[15,25]和[21,28]，則將客戶(hù) i 歸并到[10,20]和[20,30]的時(shí)間窗集合內(nèi)，將客戶(hù) j 歸并到時(shí)間段為[20,30]的時(shí)間窗

【相似文獻(xiàn)】

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

1 陳宇;;基于軟時(shí)間窗的物流配送VRPTW優(yōu)化模型研究[J];今日南國(guó)(理論創(chuàng)新版);2009年05期

2 王君;李波;;基于多目標(biāo)優(yōu)化的模糊需求VRPTW動(dòng)態(tài)管理[J];管理學(xué)報(bào);2013年02期

3 張建同;丁燁;;變鄰域模擬退火算法求解速度時(shí)變的VRPTW問(wèn)題[J];運(yùn)籌與管理;2019年11期

4 劉德昌;范才康;張南新;鐘小鳳;;利用模擬退火算法求解VRPTW問(wèn)題的研究[J];鐵道運(yùn)營(yíng)技術(shù);2017年04期

5 賈順平;尹相勇;;基于VRPTW模型與合理化判斷的貨物配送流程研究[J];物流技術(shù);2007年03期

6 馬立肖;;求VRPTW問(wèn)題的并行協(xié)同混合差異演化算法[J];電腦知識(shí)與技術(shù);2012年20期

7 幸海瓊;閔華清;;改進(jìn)型自適應(yīng)遺傳算法在VRPTW中的應(yīng)用[J];現(xiàn)代計(jì)算機(jī)(專(zhuān)業(yè)版);2011年20期

8 魏百鑫,史海波;基于整車(chē)配送的多倉(cāng)庫(kù)開(kāi)路VRPTW問(wèn)題的研究與實(shí)現(xiàn)[J];信息與控制;2005年03期

9 于殿祥;孫騫沖;代連弟;王鵬;;基于VRPTW模型的軍用物資配送流程研究[J];物流技術(shù);2009年10期

10 馬雪晶;趙一飛;;基于膜計(jì)算的VRPTW啟發(fā)式算法研究[J];武漢理工大學(xué)學(xué)報(bào);2013年02期

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

1 王介生;劉暢;張穎;;改進(jìn)蜂群進(jìn)化遺傳算法在VRPTW問(wèn)題中的應(yīng)用[A];第二十九屆中國(guó)控制會(huì)議論文集[C];2010年

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

1 董文波;求解多目標(biāo)VRPTW的離散螢火蟲(chóng)膜算法研究[D];武漢輕工大學(xué);2018年

2 劉志偉;解決多目標(biāo)VRPTW的和聲搜索算法計(jì)算性能的研究[D];武漢輕工大學(xué);2019年

3 高珊珊;改進(jìn)遺傳算法在多配送中心VRPTW中的應(yīng)用[D];蘭州財(cái)經(jīng)大學(xué);2015年

4 張嚴(yán)鴿;對(duì)生鮮農(nóng)產(chǎn)品VRPTW的研究[D];重慶大學(xué);2017年

5 田宇;基于系統(tǒng)仿真模擬退火算法的VRPTW研究[D];河北工程大學(xué);2011年

6 牛君;VRPTW中車(chē)輛受損問(wèn)題建模及多車(chē)救援策略[D];大連理工大學(xué);2007年

7 張雪;基于聚類(lèi)的改進(jìn)蟻群算法對(duì)VRPTW問(wèn)題的應(yīng)用研究[D];遼寧工程技術(shù)大學(xué);2009年

8 楊嬋;基于蟻群算法的A企業(yè)配送路徑研究[D];大連理工大學(xué);2012年

9 梁阿密;嵌套分割算法求解VRPTW混合干擾問(wèn)題[D];大連理工大學(xué);2010年

10 何昌武;雙種群混合遺傳算法的研究及應(yīng)用[D];廣西大學(xué);2013年

本文編號(hào)：2771252