混合分布估計算法求解動態需求多車型車輛調度問題

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

摘要：

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

關鍵詞：

動態需求車輛調度問題；混合分布估計算法；多車型；重定位法；2opt法

DOIDOI：10.11907/rjdk.172020

中圖分類號：TP312

文獻標識碼：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]首次提出車輛調度問題源于現實生活公路運輸問題。依據顧客相關信息可知性車輛調度問題主要分為靜態車輛調度問題（Static vehicle routing problem，SVRP）與動態車輛調度問題（Dynamic Vehicle Routing Problem，DVRP），靜態VRP問題中顧客信息一直不變，但現實生活中，顧客信息隨時可變化，因此動態車輛調度更貼近實際并尤為重要。

近年，由于現代物流快速發展，專家學者結合實際深入研究動態車輛調度問題。文獻[2]研究了基于動態需求與旅行時間的動態車輛調度問題，但未對動態旅行時間與求解算法作明確說明；文獻[3]用遺傳算法解決了動態網絡車輛路徑問題；文獻[4]提出了對單車型的混合量子遺傳算法求解隨機需求車輛調度問題；文獻[5]研究了對單

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

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

經文獻調研可知，基于分布估計算法求解動態車輛調度優化問題的研究還很少。本文在文獻[4]基礎上，根據新增客戶信息變化的時間順序變化，基于時間軸建立數學模型，根據客戶動態需求信息把動態配送問題轉換成一系列靜態配送問題，并在此基礎上考慮了車型變化。設計了一種將分布估計算法與并行節約算法混合的算法求解此問題。仿真實驗驗證了所提算法的有效性。

1概述

設有一個配送中心，負責配送整個網絡顧客，且配送中心車型不是唯一，顧客配送需求隨時變化。某個時間段內，根據顧客是否提前訂貨與訂貨計劃是否有變，將配送網絡中顧客分為靜態顧客與動態顧客，其中靜態顧客信息（顧客位置坐標，顧客需求量）為已知。配送網絡中未出現動態顧客信息（靜態顧客需求量變化與動態顧客需求）時，配送中心依據已知信息進行路徑規劃與車輛配送；隨著時間變化，有動態顧客產生時，配送中心調度系統需要改變原先路線或增加新車輛以滿足動態顧客需求。endprint

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

在時刻t時，根據車輛所處位置將所有顧客大致分為4類：①已完成配送顧客；②正在被配送顧客或車輛正要前往配送顧客；③未完成配送顧客；④產生新需求顧客。其中第二類配送過程中不可更改，這類顧客點是配送網絡關鍵點，如圖1的顧客點2、4、8。可知，所有隨機需求車輛調度問題都可根據時間軸概念轉化成一系列靜態車輛調度問題，其中靜態調度網絡關鍵點識別非常重要，調度中心可根據關鍵點位置、車輛容載量及未完成顧客信息安排調度方案。

3.3種群初始化

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

Step 1隨機產生一個r；

Step 2若r

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

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

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

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

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

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

3.6混合分布估計算法

根據動態需求車輛調度問題特點，設計了針對該問題的混合分布估計算法，該算法基本思想是：采用分布估計算法對已知靜態車輛信息進行路徑規劃，有隨機顧客提出請求時，統計此時配送網絡關鍵點及未完成配送顧客，采用并行節約插入算法，將隨機需求顧客信息插入到已規劃好靜態路線。由混合的分布估計算法完成靜態顧客與隨機需求顧客配送。

3.6.1傳統并行節約法

傳統并行節約法生成配送路線，具體操作如下：

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

動態需求車輛調度配送路線構造：①靜態車輛調度配送路線基礎上，有隨機顧客提出服務請求時，調度中心檢查當前車輛位置及路線，判斷配送網絡所有關鍵點；②依次判斷隨機任務是否滿足插入條件，并計算所有可能插入點的配送成本，選取配送成本最小的2個顧客，將隨機需求顧客插入該線路。

3.6.2混合算法

采用兩階段算法求解隨機需求車輛調度問題，第一階段利用分布估計算法求解靜態車輛調度模型；第二階段采用并行節約算法實將隨機需求顧客插入配送網絡。混合算法具體步驟如下：

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

Step 2根據初始信息，利用改進的分布估計算法對靜態顧客進行路徑規劃；

Step 3配送中心檢查是否有隨機顧客提出配送請求，若沒有，則輸出優化結果；否則轉入步驟4；

Step 4統計該時刻配送網絡所有關鍵點與未完成配送顧客信息；

Step 5依據配送網絡關鍵點信息與未完成配送顧客信息，將隨機顧客服務請求由并行節約算法實現動態插入，并轉到步驟2。

4仿真實驗與結果分析

本文提出了一種HEDA算法求解動態需求多車型車輛調度問題，對其進行實驗仿真。所用算法與測試程序均在Matlab 2014仿真環境進行仿真。

4.1單車型動態需求車輛調度問題仿真實驗

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

設置種群數pop=30，最大迭代次數GM=100，求解隨機需求車輛調度問題，結果見表3、表4。

由表4可知，HEDA能解決動態需求車輛調度問題，并取得了較好結果。

4.2多車型動態需求車輛調度問題仿真實驗

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

設置種群數pop=30，最大迭代次數GM=100，對靜態顧客進行線路規劃，產生初始規劃路線見表8。

動態調度路線見表9。

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

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

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

5結語

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

參考文獻：

[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]肖增敏.動態網絡車輛路徑問題研究[D].成都：西南交通大學，2005.

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

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

[6]張景玲，王萬良，趙燕偉.基于沿途補貨的多配送中心動態需求VRP建模及優化[J].計算機集成制造系統，2013，（04）：869878.

[7]彭勇. 變需求車輛路線問題建模及基于Inverover操作的PSODP算法[J]. 系統工程理論與實踐，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]陳磊.基于隨機需求的城市公交車輛調度問題的研究[D].北京：北京交通大學，2011.

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

[11]武燕，王宇平，劉小雄.自適應PBIL 算法求解一類動態優化問題[J].吉林大學學報：工學版，2008，38（6）：136140.

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

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

[14]蹇潔，王旭，葛顯龍.云自適應遺傳算法有能力約束的車輛調度優化[J].重慶大學學報，2013（8）：4046.

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

（責任編輯：何麗）endprint