曹云+向鳳紅+毛劍琳+郭寧+趙培瑤

摘要：

針對物流配送客戶需求動態(tài)變化，車場車型不是唯一特點，建立基于時間軸的多車型動態(tài)需求數(shù)學(xué)模型，根據(jù)客戶動態(tài)需求將動態(tài)配送問題轉(zhuǎn)換成一系列靜態(tài)配送問題。設(shè)計了一種將分布估計算法與并行節(jié)約算法混合的算法實時優(yōu)化模型。引入重定位法與2opt法局部搜索算法局部調(diào)整線路內(nèi)子路徑及線路間路徑，進(jìn)一步提高算法收斂速度。仿真實驗與算法驗證了所提算法的有效性與優(yōu)越性。

關(guān)鍵詞：

動態(tài)需求車輛調(diào)度問題；混合分布估計算法；多車型；重定位法；2opt法

DOIDOI：10.11907/rjdk.172020

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）001006806

Abstract：Aiming at the dynamic changes of customer requirements，vehicles diversification in the dynamic vehicle routing problem（DVRP）， the mathematical model of dynamic demand of multivehicle based on time axis is established，according to the dynamic demand information， the dynamic distribution problem is transformed into a series of static distribution problems.An algorithm combining the distributed estimation algorithm and the parallel saving algorithm is designed for realtime ptimization of the dynamic model. The local search algorithm of relocation and 2opt methods are used to adjust the subpaths in the line and the path between the lines to further improve the convergence speed of the algorithm. Combining with a simulated example， the model and algorithm is tested， which achieve good results.

Key Words：dynamic demand vehicle scheduling problem； hybrid distributed estimation algorithm； multivehicle type；relocation method；2opt method

0引言

1959年，Dantzig[1]首次提出車輛調(diào)度問題源于現(xiàn)實生活公路運輸問題。依據(jù)顧客相關(guān)信息可知性車輛調(diào)度問題主要分為靜態(tài)車輛調(diào)度問題（Static vehicle routing problem，SVRP）與動態(tài)車輛調(diào)度問題（Dynamic Vehicle Routing Problem，DVRP），靜態(tài)VRP問題中顧客信息一直不變，但現(xiàn)實生活中，顧客信息隨時可變化，因此動態(tài)車輛調(diào)度更貼近實際并尤為重要。

近年，由于現(xiàn)代物流快速發(fā)展，專家學(xué)者結(jié)合實際深入研究動態(tài)車輛調(diào)度問題。文獻(xiàn)[2]研究了基于動態(tài)需求與旅行時間的動態(tài)車輛調(diào)度問題，但未對動態(tài)旅行時間與求解算法作明確說明；文獻(xiàn)[3]用遺傳算法解決了動態(tài)網(wǎng)絡(luò)車輛路徑問題；文獻(xiàn)[4]提出了對單車型的混合量子遺傳算法求解隨機(jī)需求車輛調(diào)度問題；文獻(xiàn)[5]研究了對單

車型的動態(tài)車輛調(diào)度，設(shè)計了兩階段求解策略；文獻(xiàn)[6]建立了基于沿途多點補(bǔ)貨策略的開放式車輛路徑問題模型，但未考慮隨機(jī)需求對路徑優(yōu)化影響；文獻(xiàn)[7]研究了一類隨機(jī)需求VRP問題，利用基于Inverover操作的粒子群算法，并將動態(tài)規(guī)劃算法嵌入粒子群算法求解；文獻(xiàn)[8]應(yīng)用混合粒子群算法成功解決了大型VRP問題；文獻(xiàn)[9]研究了城市擁堵情況下公交調(diào)度問題；文獻(xiàn)[10]提出了一種種群增量學(xué)習(xí)算法解決VRPTW問題。

分布估計算法（Estimation of Distribution Algorithms，EDA）是一種基于統(tǒng)計的進(jìn)化模式，利用概率模型描述候選種群問題解空間分布，通過統(tǒng)計學(xué)習(xí)手段構(gòu)建一個描述解分布的概率模型，對該模型進(jìn)行隨機(jī)采用產(chǎn)生新種群，如此反復(fù)實現(xiàn)對問題解空間的搜索。該算法能利用已獲得的較優(yōu)解構(gòu)建概率模型，較合理地確定算法搜索區(qū)域或方向，近年得到廣泛關(guān)注。武燕等[11]提出一種自適應(yīng)的PBIL用于求解一類動態(tài)優(yōu)化問題，用2個動態(tài)優(yōu)化問題進(jìn)行仿真實驗，表明其算法可快速跟蹤最優(yōu)解變化。袁利永等[12]設(shè)計了基于PBIL的物流中心選址優(yōu)化算法，進(jìn)行了算法實現(xiàn)與測試。謝勇[13]等提出了一種改進(jìn)PBIL用于求解帶軟時間窗的車輛調(diào)度問題，仿真實驗證明了所提算法的有效性。

經(jīng)文獻(xiàn)調(diào)研可知，基于分布估計算法求解動態(tài)車輛調(diào)度優(yōu)化問題的研究還很少。本文在文獻(xiàn)[4]基礎(chǔ)上，根據(jù)新增客戶信息變化的時間順序變化，基于時間軸建立數(shù)學(xué)模型，根據(jù)客戶動態(tài)需求信息把動態(tài)配送問題轉(zhuǎn)換成一系列靜態(tài)配送問題，并在此基礎(chǔ)上考慮了車型變化。設(shè)計了一種將分布估計算法與并行節(jié)約算法混合的算法求解此問題。仿真實驗驗證了所提算法的有效性。

1概述

設(shè)有一個配送中心，負(fù)責(zé)配送整個網(wǎng)絡(luò)顧客，且配送中心車型不是唯一，顧客配送需求隨時變化。某個時間段內(nèi)，根據(jù)顧客是否提前訂貨與訂貨計劃是否有變，將配送網(wǎng)絡(luò)中顧客分為靜態(tài)顧客與動態(tài)顧客，其中靜態(tài)顧客信息（顧客位置坐標(biāo)，顧客需求量）為已知。配送網(wǎng)絡(luò)中未出現(xiàn)動態(tài)顧客信息（靜態(tài)顧客需求量變化與動態(tài)顧客需求）時，配送中心依據(jù)已知信息進(jìn)行路徑規(guī)劃與車輛配送；隨著時間變化，有動態(tài)顧客產(chǎn)生時，配送中心調(diào)度系統(tǒng)需要改變原先路線或增加新車輛以滿足動態(tài)顧客需求。endprint

由于動態(tài)需求多車型車輛調(diào)度顧客信息隨時間變化，因此引入時間軸概念，如圖1所示。動態(tài)需求調(diào)度環(huán)境下，建立一個時間軸，每個新顧客需求產(chǎn)生時間為t，在t時刻時，動態(tài)顧客信息與靜態(tài)顧客信息均為已知，因此可將動態(tài)配送網(wǎng)絡(luò)通過時間t看成普通靜態(tài)配送網(wǎng)絡(luò)。

在時刻t時，根據(jù)車輛所處位置將所有顧客大致分為4類：①已完成配送顧客；②正在被配送顧客或車輛正要前往配送顧客；③未完成配送顧客；④產(chǎn)生新需求顧客。其中第二類配送過程中不可更改，這類顧客點是配送網(wǎng)絡(luò)關(guān)鍵點，如圖1的顧客點2、4、8?？芍须S機(jī)需求車輛調(diào)度問題都可根據(jù)時間軸概念轉(zhuǎn)化成一系列靜態(tài)車輛調(diào)度問題，其中靜態(tài)調(diào)度網(wǎng)絡(luò)關(guān)鍵點識別非常重要，調(diào)度中心可根據(jù)關(guān)鍵點位置、車輛容載量及未完成顧客信息安排調(diào)度方案。

3.3種群初始化

種群初始化階段，首先令gen表示當(dāng)前進(jìn)化代數(shù)，pop表示種群規(guī)模，GM表示算法最大運行代數(shù)，r是隨機(jī)變量，取值范圍為[0，1]，r0是控制車輛選擇顧客j的參數(shù)，取值范圍同r。隨機(jī)產(chǎn)生一個概率r，若r

Step 1隨機(jī)產(chǎn)生一個r；

Step 2若r

Step 3輪盤賭選擇客戶過程：假設(shè)確定pathi中第j個值pathi [j]，即車輛中第j個可服務(wù)客戶，則從概率矩陣αgenijk進(jìn)行輪盤賭選擇。αgenijk為第i輛車服務(wù)第j個客戶的概率，k代表子路徑中第k個客戶；

Step 4將選擇客戶加入pathi中，判斷第i輛車是否滿足容量要求，若滿足則加入pathi中，否則派出下一輛車，即k+1輛車，并將客戶j加入pathi+1中，跳轉(zhuǎn)步驟1。

3.5基于重定位與2opt的局部搜索

EDA算法進(jìn)化過程中，極易對解空間分布出現(xiàn)過擬合情況，導(dǎo)致構(gòu)造的概率模型不能有效表達(dá)解空間信息，算法陷入早熟收斂。為保證算法有效性，加入局部搜索操作，以解決分布估計算法劣勢，保持種群多樣性。

所提算法主要是改進(jìn)線路間局部搜索，包括針對單條線路的 2opt法，即將線路內(nèi)2條邊與另外2條邊交換，如圖3所示，將該線路內(nèi)邊（i，i+1）與（j+1，j）用邊（i，j）與（i+1，j+1）替換，形成一條新路徑。若新線路目標(biāo)函數(shù)比原線路更優(yōu)，用新個體代替原來個體。

針對多條線路的優(yōu)化重定位法，即將一個顧客從一條線路轉(zhuǎn)移到另一條線路，如圖4所示，將結(jié)點i由線路r1移動到線路r2中j與j+1間，形成兩條新線路。采用重定位是隨機(jī)選取一個顧客結(jié)點重定位到其余線路每個位置上，從中選擇最優(yōu)線路代替原線路。

3.6混合分布估計算法

根據(jù)動態(tài)需求車輛調(diào)度問題特點，設(shè)計了針對該問題的混合分布估計算法，該算法基本思想是：采用分布估計算法對已知靜態(tài)車輛信息進(jìn)行路徑規(guī)劃，有隨機(jī)顧客提出請求時，統(tǒng)計此時配送網(wǎng)絡(luò)關(guān)鍵點及未完成配送顧客，采用并行節(jié)約插入算法，將隨機(jī)需求顧客信息插入到已規(guī)劃好靜態(tài)路線。由混合的分布估計算法完成靜態(tài)顧客與隨機(jī)需求顧客配送。

3.6.1傳統(tǒng)并行節(jié)約法

傳統(tǒng)并行節(jié)約法生成配送路線，具體操作如下：

靜態(tài)車輛調(diào)度配送線路構(gòu)造：①將所有需求顧客分別與配送中心相連；②計算需求顧客之間是否滿足連接條件，如車載容量限制，若滿足，計算節(jié)約值；③選取節(jié)約值最大的2個顧客進(jìn)行連接。重復(fù)②、③步驟，直到所有需求顧客均連接完畢，輸出最優(yōu)值。

動態(tài)需求車輛調(diào)度配送路線構(gòu)造：①靜態(tài)車輛調(diào)度配送路線基礎(chǔ)上，有隨機(jī)顧客提出服務(wù)請求時，調(diào)度中心檢查當(dāng)前車輛位置及路線，判斷配送網(wǎng)絡(luò)所有關(guān)鍵點；②依次判斷隨機(jī)任務(wù)是否滿足插入條件，并計算所有可能插入點的配送成本，選取配送成本最小的2個顧客，將隨機(jī)需求顧客插入該線路。

3.6.2混合算法

采用兩階段算法求解隨機(jī)需求車輛調(diào)度問題，第一階段利用分布估計算法求解靜態(tài)車輛調(diào)度模型；第二階段采用并行節(jié)約算法實將隨機(jī)需求顧客插入配送網(wǎng)絡(luò)?；旌纤惴ň唧w步驟如下：

Step 1給定初始參數(shù)，如顧客需求信息（動態(tài)顧客與靜態(tài)顧客）、車輛裝載量及車輛位置信息；

Step 2根據(jù)初始信息，利用改進(jìn)的分布估計算法對靜態(tài)顧客進(jìn)行路徑規(guī)劃；

Step 3配送中心檢查是否有隨機(jī)顧客提出配送請求，若沒有，則輸出優(yōu)化結(jié)果；否則轉(zhuǎn)入步驟4；

Step 4統(tǒng)計該時刻配送網(wǎng)絡(luò)所有關(guān)鍵點與未完成配送顧客信息；

Step 5依據(jù)配送網(wǎng)絡(luò)關(guān)鍵點信息與未完成配送顧客信息，將隨機(jī)顧客服務(wù)請求由并行節(jié)約算法實現(xiàn)動態(tài)插入，并轉(zhuǎn)到步驟2。

4仿真實驗與結(jié)果分析

本文提出了一種HEDA算法求解動態(tài)需求多車型車輛調(diào)度問題，對其進(jìn)行實驗仿真。所用算法與測試程序均在Matlab 2014仿真環(huán)境進(jìn)行仿真。

4.1單車型動態(tài)需求車輛調(diào)度問題仿真實驗

為驗證本文所提HEDA算法可行性，對單車型動態(tài)需求車輛調(diào)度問題進(jìn)行仿真。實驗1測試數(shù)據(jù)為Matlab隨機(jī)生成數(shù)據(jù)，包含一個配送中心（編號為0）與20個需要服務(wù)的顧客，其中靜態(tài)顧客15個（編號為1，2，3，…），動態(tài)顧客5個（編號為D1，D2，D3，…）。各顧客點需求量及坐標(biāo)見表1、表2。由配送中心出發(fā)的每輛車裝載量均為6t。

設(shè)置種群數(shù)pop=30，最大迭代次數(shù)GM=100，求解隨機(jī)需求車輛調(diào)度問題，結(jié)果見表3、表4。

由表4可知，HEDA能解決動態(tài)需求車輛調(diào)度問題，并取得了較好結(jié)果。

4.2多車型動態(tài)需求車輛調(diào)度問題仿真實驗

由于隨機(jī)數(shù)據(jù)偶然因素較大，因此采用文獻(xiàn)[15]實驗數(shù)據(jù)。配送中心共有3種車型，所有車輛均無最遠(yuǎn)行駛距離限制，3種車型費用參數(shù)設(shè)置見表5。一個配送中心（編號為0）坐標(biāo)為（40km，71km）、30個靜態(tài)顧客（編號為1，2，3，…，30）及5個動態(tài)顧客（編號為D1，D2，…，D5），靜態(tài)顧客位置坐標(biāo)與需求量見表6，動態(tài)顧客位置坐標(biāo)與需求量見表7。要求安排合理配送路線，使所需費用達(dá)到最小。

設(shè)置種群數(shù)pop=30，最大迭代次數(shù)GM=100，對靜態(tài)顧客進(jìn)行線路規(guī)劃，產(chǎn)生初始規(guī)劃路線見表8。

動態(tài)調(diào)度路線見表9。

由表9可看出，對于動態(tài)需求多車型車輛調(diào)度問題，車輛使用應(yīng)以裝載率為依據(jù)，滿載時車輛費用最低。本文首次提出應(yīng)用HEAD算法解決此問題，并取得了良好結(jié)果。

為驗證算法優(yōu)越性，對于實驗2例子，分別采用粒子群算法，遺傳算法與本章HEDA算法進(jìn)行對比分析，收斂情況如圖5所示。

由圖5可知，遺傳算法與粒子群算法均在25代左右收斂，基于混合分布估計算法在16代左右即可收斂，這得益于混合分布估計算法具有較好全局搜索能力，同時又對優(yōu)秀個體使用了局部搜索方法。

5結(jié)語

本文針對動態(tài)需求多車型車輛調(diào)度問題，將動態(tài)需求問題轉(zhuǎn)化為兩階段靜態(tài)車輛調(diào)度問題，根據(jù)問題特點首次將分布估計算法與最大并行節(jié)約算法結(jié)合。通過Matlab仿真試驗，結(jié)果表明，該算法有效提高搜索成功率，驗證了算法可行性。

參考文獻(xiàn)：

[1]DANTZIGC RAMSERJ.The truck dispatching problem[J].Management Science，1959（6）：8091.

[2]JEANYVES POTVIN，YING XU，ILHAM BENYAHIA. Vehicle routing and scheduling with dynamic travel times[J].Computers & Operations Research，2006，33（4）：11291137.

[3]肖增敏.動態(tài)網(wǎng)絡(luò)車輛路徑問題研究[D].成都：西南交通大學(xué)，2005.

[4]葛顯龍，王旭，代應(yīng).基于混合量子遺傳算法的隨機(jī)需求車輛調(diào)度問題[J].系統(tǒng)工程，2011，29（3）：5359.

[5]王旭，葛顯龍，代應(yīng).基于兩階段求解算法的動態(tài)車輛調(diào)度問題研究[J].控制與決策，2012，27（2）：175181.

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

[7]彭勇. 變需求車輛路線問題建模及基于Inverover操作的PSODP算法[J]. 系統(tǒng)工程理論與實踐，2008，（10）：7681.

[8]MARINAKIS Y， MARINAKIS M， DOUNIAS G. A hybrid particle swarm optimization algorithm for the vehicle routing problem [J]. Engineering Applications of Artificial Intelligence，2010，23（4）：463472.

[9]陳磊.基于隨機(jī)需求的城市公交車輛調(diào)度問題的研究[D].北京：北京交通大學(xué)，2011.

[10]孟祥虎，胡蓉，錢斌.求解帶時間窗車輛路徑問題的有效混合PBIL算法[J].系統(tǒng)工程理論與實踐，2014，（10）： 239247.

[11]武燕，王宇平，劉小雄.自適應(yīng)PBIL 算法求解一類動態(tài)優(yōu)化問題[J].吉林大學(xué)學(xué)報：工學(xué)版，2008，38（6）：136140.

[12]袁利永，金炳堯，曹振新.PBIL算法求解物流中心選址優(yōu)化問題[J].計算機(jī)系統(tǒng)應(yīng)用，2010，19（ 11） ：242245.

[13]謝勇，胡蓉，錢斌，等.一種改進(jìn)的種群增量學(xué)習(xí)算法求解帶軟時間窗的車輛路徑優(yōu)化問題[J].南京理工大學(xué)學(xué)報，2016，40（1）：110116.

[14]蹇潔，王旭，葛顯龍.云自適應(yīng)遺傳算法有能力約束的車輛調(diào)度優(yōu)化[J].重慶大學(xué)學(xué)報，2013（8）：4046.

[15]葛顯龍，王旭，邢樂斌.動態(tài)需求的多車型車輛調(diào)度問題及云遺傳算法[J].系統(tǒng)工程學(xué)報，2012（6）：823832.

（責(zé)任編輯：何麗）endprint