【摘要】：隨著科學(xué)技術(shù)的發(fā)展,物流的專業(yè)水平不斷提高,客戶對(duì)于服務(wù)質(zhì)量和實(shí)效性的要求越來越高,越來越多的企業(yè)將物流作為提高市場(chǎng)競(jìng)爭(zhēng)力與核心競(jìng)爭(zhēng)水平的一個(gè)重要手段。隨著時(shí)間的變化,車輛調(diào)度問題中會(huì)出現(xiàn)客戶需求的變化,新客戶的增加,原有客戶的減少,原有客戶需求的修改等多種動(dòng)態(tài)事件。這就需要制定實(shí)時(shí)的調(diào)度方案,設(shè)計(jì)合適的算法,從而使系統(tǒng)目標(biāo)更優(yōu)。物流配送中的車輛調(diào)度問題屬于典型的NP-hard問題,一般的精確算法求解動(dòng)態(tài)車輛調(diào)度問題時(shí)難度較為復(fù)雜,當(dāng)前,智能優(yōu)化算法越來越受到各界學(xué)者的關(guān)注與青睞。Memetic算法是進(jìn)化算法和某些局域搜索算法的靈活結(jié)合體。主要結(jié)構(gòu)是由進(jìn)化模塊和局部搜索模塊組成,這也是Memetic算法的核心組成部分。Memetic算法提出的是一種靈活的框架,可根據(jù)不同的問題模型,選擇合適的搜索策略,從而構(gòu)成不同的Memetic算法。由于它有很好的自適應(yīng)能力、靈活性、高效性、可移植性等特點(diǎn),近些年來得到了廣泛的關(guān)注和發(fā)展,成功的應(yīng)用于各個(gè)領(lǐng)域,并取得了很好的效果。鑒于此算法有很大的發(fā)展空間,所以論文采用此算法針對(duì)動(dòng)態(tài)車輛調(diào)度問題的三個(gè)不同問題模型,進(jìn)行了改進(jìn),并分別采用改進(jìn)的算法進(jìn)行仿真來驗(yàn)證算法的有效性。論文的工作內(nèi)容主要包括以下幾部分:首先,對(duì)于帶容量約束的動(dòng)態(tài)車輛調(diào)度問題(Capacitated Dynamic Vehicle Routing Problem,DVRP),構(gòu)造了兩階段的數(shù)學(xué)模型。根據(jù)模型特點(diǎn),設(shè)計(jì)了一種用于最小化運(yùn)輸總費(fèi)用的Memetic算法。所采用Memetic算法的全局搜索為改進(jìn)量子遺傳算法,局部搜索為2-opt法和swap法。其次,對(duì)于多車型動(dòng)態(tài)車輛調(diào)度問題(Heterogenous Fleet Dynamic Vehicle Rounting Problem,HFDVRP),將最小車輛數(shù)和最少運(yùn)輸費(fèi)用作為優(yōu)化目標(biāo),并將問題分為兩個(gè)階段來進(jìn)行求解。針對(duì)其模型特點(diǎn),設(shè)計(jì)了一種新的Memetic算法。該算法中全局搜索的第一個(gè)階段采用改進(jìn)分布估計(jì)算法,第二個(gè)階段采用改進(jìn)量子遺傳算法。局部搜索采用客戶節(jié)點(diǎn)重置和2-opt法。通過兩個(gè)仿真實(shí)驗(yàn)來表明所提算法的有效性和優(yōu)越性。最后,針對(duì)有客戶需求和時(shí)間窗變化的動(dòng)態(tài)需求車輛調(diào)度問題,采用了一種基于Memetic算法的干擾管理的擾動(dòng)恢復(fù)策略,所選用Memetic算法在上一部分改進(jìn)分布估計(jì)算法基礎(chǔ)上,根據(jù)問題模型特點(diǎn),將車輛的時(shí)間窗因素引入采樣概率選擇函數(shù)中,最后通過仿真實(shí)驗(yàn)來驗(yàn)證了算法的有效性。 【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：U492.22

【圖文】：

昆明理工大學(xué)碩士學(xué)位論文 18 圖 3.1 動(dòng)態(tài)車輛調(diào)度問題求解流程圖3.1.3 DVRP 數(shù)學(xué)模型將 DVRP 問題分為兩個(gè)階段進(jìn)行求解，并針對(duì)不同的階段建立相應(yīng)的數(shù)學(xué)模型。在客戶需求沒有發(fā)生變化時(shí)，客戶的需求以及位置均是已知的，這個(gè)階段屬于預(yù)優(yōu)化階段，建立的數(shù)學(xué)模型如下，首先給出決策變量10=ijkk i jx ，，車輛 從用戶 到，其他（3-1）0=1iki ky ，用戶 由車輛 配送，其他（3-2）（1）建立預(yù)優(yōu)化階段模型目標(biāo)函數(shù)：1 0 0minK m mijk ijk i jZ x c （3-3）約束條件：1mi ikiq y Q k ， （3-4）11Kikiy i ， （3-5）

圖 3.2 DVRP 求解策略流程圖子遺傳算法的基本思想的車輛調(diào)度問題來說，較為常用的算法是遺傳算法應(yīng)性強(qiáng)、魯棒性強(qiáng)且易于其他算法混合等優(yōu)點(diǎn)。但收斂速度慢等不足。所以常將遺傳算法和其他一些求解動(dòng)態(tài)車輛調(diào)度問題中，量子遺傳算法近年來受此同時(shí)，由于問題本身的不確定性，為得到更好進(jìn)。改進(jìn)的量子遺傳算法通過量子旋轉(zhuǎn)角的大小進(jìn)化方向。設(shè)計(jì)了一種量子旋轉(zhuǎn)門更新機(jī)制，即根定量子旋轉(zhuǎn)角的大小和方向。法

【參考文獻(xiàn)】

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

1 沙林秀;賀昱曜;;一種新的自適應(yīng)量子遺傳算法[J];計(jì)算機(jī)工程;2013年09期

2 崔麗;王笑叢;;需求驅(qū)動(dòng)下的城市配送車輛動(dòng)態(tài)調(diào)度研究[J];計(jì)算機(jī)工程與應(yīng)用;2015年02期

3 張景玲;王萬良;趙燕偉;;基于沿途補(bǔ)貨的多配送中心動(dòng)態(tài)需求VRP建模及優(yōu)化[J];計(jì)算機(jī)集成制造系統(tǒng);2013年04期

4 王圣堯;王凌;方晨;許燁;;分布估計(jì)算法研究進(jìn)展[J];控制與決策;2012年07期

5 王旭;葛顯龍;代應(yīng);;基于兩階段求解算法的動(dòng)態(tài)車輛調(diào)度問題研究[J];控制與決策;2012年02期

6 王萬良;黃海鵬;趙燕偉;張景玲;;基于車輛共享的軟時(shí)間窗動(dòng)態(tài)需求車輛路徑問題[J];計(jì)算機(jī)集成制造系統(tǒng);2011年05期

7 葛顯龍;王旭;代應(yīng);;基于混合量子遺傳算法的隨機(jī)需求車輛調(diào)度問題[J];系統(tǒng)工程;2011年03期

8 張景玲;趙燕偉;王海燕;介婧;王萬良;;多車型動(dòng)態(tài)需求車輛路徑問題建模及優(yōu)化[J];計(jì)算機(jī)集成制造系統(tǒng);2010年03期

9 王旭坪;楊德禮;許傳磊;;有顧客需求變動(dòng)的車輛調(diào)度干擾管理研究[J];運(yùn)籌與管理;2009年04期

10 王斌;尚新春;李海峰;;解決車輛路徑問題的混合模擬退火算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2009年03期

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

1 武燕;分布估計(jì)算法研究及在動(dòng)態(tài)優(yōu)化問題中的應(yīng)用[D];西安電子科技大學(xué);2009年

2 謝秉磊;隨機(jī)車輛路徑問題研究[D];西南交通大學(xué);2003年

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

1 潘挺雷;基于改進(jìn)蟻群算法的區(qū)域車輛配送路徑優(yōu)化方法研究[D];浙江理工大學(xué);2016年

2 施瑋;新型蟻群優(yōu)化算法在帶時(shí)間窗口的車輛路徑問題中的應(yīng)用[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

3 曹高立;基于求解車輛路徑問題的混合智能優(yōu)化算法研究[D];昆明理工大學(xué);2015年

4 李文;物流配送同時(shí)取送貨低碳車輛調(diào)度模型及其QEA研究[D];浙江工業(yè)大學(xué);2015年

5 張紅豆;基于蟻群算法的物流系統(tǒng)配送車輛路徑優(yōu)化問題研究[D];昆明理工大學(xué);2015年

6 許傳磊;物流配送客戶時(shí)間窗變動(dòng)干擾管理研究[D];大連理工大學(xué);2009年

7 劉英;應(yīng)急狀態(tài)下航班運(yùn)行的干擾管理研究[D];武漢理工大學(xué);2008年

本文編號(hào)：2712352