基于帶容量約束Memetic算法的動態(tài)車輛調度問題研究

曹云+向鳳紅+毛劍琳+郭寧

摘要：針對物流配送過程中帶容量約束的動態(tài)車輛調度問題，提出一種Memetic算法，旨在最小化成本。Memetic算法中采用量子與遺傳算法混合進行全局搜索，并根據搜索點目標函數變化率，設計了一種自適應量子旋轉門更新方式，通過子代種群適應度變化確定量子旋轉角大小與方向，明確了種群進化方向，擴展了全局搜索范圍，引入了一種變異操作，使算法種群多樣性得以保持，提高全局搜索寬度，采用2opt法結合swap法增強算法局部搜索能力。仿真實驗驗證了所提算法的有效性與優(yōu)越性。

關鍵詞關鍵詞：動態(tài)車輛調度；Memetic算法；量子旋轉門；全局搜索；局部搜索

DOIDOI：10.11907/rjdk.171984

中圖分類號：TP319

文獻標識碼：A文章編號文章編號：16727800（2017）011012904

0引言

車輛調度問題（Vehicle Scheduling Problem， VSP）是典型NPhard問題，由Dantzing與Ramser[1]于1959年提出。動態(tài)車輛調度問題是指調度中心在優(yōu)化之前所有與之相關信息是隨時間變化的。由于動態(tài)車輛路徑問題（Dynamic Vehicle Routing Problem， DVRP）更貼近于實際生活，其模型及研究算法與靜態(tài)車輛調度有很大區(qū)別，近些年引起許多專家學者青睞。

帶容量約束的動態(tài)車輛調度問題（Capacitated Dynamic Vehicle Routing Problem，DCVRP）廣泛存在于物流配送行業(yè)。例如，快遞公司收發(fā)業(yè)務、出租車公司預約電話服務、外賣訂取以及垃圾收集等，隨時會有新客戶需求或原有客戶需求量變更的情況，這時配送中心需要根據配送車輛容量、運輸成本以及行駛路程進行配送。另外，為盡快達到配送要求，需實時調整配送路線。這個過程就是典型帶容量約束的動態(tài)車輛調度問題。其優(yōu)化目標主要包括最短行車路程、最小配送成本、最快完成時間以及最少配送車輛等。由于DVRP本身模型復雜性及求解難度，在理論以及應用上都有很高研究價值。

目前，用于解決DVRP的主流智能優(yōu)化算法主要包括遺傳算法（GA）[23]、模擬退火算法[45]、蟻群算法（ACA）[78]、粒子群算法（PSO）[9]、量子進化算法[1013]等。使用智能算法求解組合優(yōu)化問題，已成為智能計算領域研究熱點。

Memetic算法（ Memetic Algorithm，MA）是近年來進化計算領域一種新興算法，由Moscato與Norman等[14]在1992年正式提出，并成功應用于TSP求解問題。Memetic算法提出一種靈活框架，在這個框架下，采用不同搜索策略可構成不同Memetic算法。在Memetic算法框架內，進化算法（Evolutionary Algorithm，EA）算子被用于執(zhí)行廣域搜索，局域搜索（Local Search，LS）策略被用于對某些個體執(zhí)行局部改善，使得算法能夠在探索與開發(fā)能力之間保持較好平衡。Memetic算法非常適合求解靜態(tài)優(yōu)化問題，研究者現已在函數優(yōu)化問題、組合優(yōu)化問題、車間調度問題、物流與供應鏈、神經網絡訓練、模糊系統(tǒng)控制等領域取得了良好效果，但在動態(tài)車輛調度中應用還很少。鑒于Memetic算法具有很強自適應能力、靈活性、高效性、可移植、并行性、魯棒性、收斂性等特點，在研究動態(tài)問題上有很大優(yōu)勢。所以根據不同模型特點在模因算法框架內設計合適的進化迭代策略與局部搜索，提出有效解決方案非常有意義。

本文全局優(yōu)化算法選擇量子遺傳混合算法，作為一種新混合量子算法，沒有遺傳算法選擇、交叉、變異等操作，而是通過與種群中相鄰兩代優(yōu)秀個體進行對比，并依據變化率構造與更新調整策略，然后根據新調整策略產生新種群，從而引導算法搜索方向。相對于遺傳算法等傳統(tǒng)智能優(yōu)化算法，能從更宏觀角度對問題解空間進行搜索，具有較好全局搜索性能。其局部搜索是選擇了針對單條線路優(yōu)化的2opt法與針對多條線路優(yōu)化的swap算法，對初始狀態(tài)與實時狀態(tài)進行優(yōu)化。仿真實驗與算法比較驗證了算法有效性與優(yōu)越性。

1DCVRP問題描述及數學模型

一個車場有K輛車對m名客戶進行服務，每輛車最大載重量為Q，每個各戶需求量為qi，客戶間距離為cij。服務過程中，客戶需求實時動態(tài)變化，表現為新客戶出現及原有客戶需求量變化。優(yōu)化目標為最小配送成本。將問題分為2個階段解決，即預優(yōu)化階段與實時優(yōu)化階段，針對階段不同分別建立不同數學模型。決策變量如下：

swap法局部搜索：采用swap算法對2條線路進行改進。對當前解中2條不同路徑中的1點相互交換。若交換后解值相較原來解更優(yōu)，則以swap法形成的新路線為更優(yōu)解，否則以原行車路線為更優(yōu)解，原理如圖2所示。

圖2swap法原理

2.4適應度值計算

根據染色體解碼生成的調度路線，計算初始階段與實時優(yōu)化階段行車路程與運輸成本，若路線不滿足要求，即超出容量限制，則賦給fitness一個很大的值。

2.5Memetic算法步驟

Memetic算法步驟如下：

step1：種群初始化，隨機產生初始種群；

step2：染色體解碼得到車輛配送路線；

step3：2opt法結合swap法對路徑進行局部優(yōu)化；

step4：計算適應值，保留最優(yōu)個體；

step5：自適應量子門旋轉門更新；

step6：量子比特種群進行變異操作；

step7：如果達到最大迭代次數，則輸出最優(yōu)路徑，否則跳到step1。

由Memetic算法步驟可知，將量子旋轉門改進為自適應量子旋轉門，通過自適應量子旋轉門操作，使算法獲得更明確搜索方向與深度，提高算法全局搜索廣泛性；通過變異操作，有效保持種群多樣性，提高算法全局搜索寬泛性；通過引入針對單條線路優(yōu)化的2opt法與線路間優(yōu)化的swap法，提高了算法局部搜索能力。綜上所述，基于Memetic算法的QGA在全局探索方式與局部搜索策略上均作了有效改進，算法有希望取得DVRP的優(yōu)良解。endprint

3仿真實驗與算法比較

本文為了對算法性能進行驗證，將Memetic算法與量子遺傳算法以及遺傳算法作比較。所有算法程序均由MATLAB編碼實現。每種算法均獨立重復運行20次，每次最大迭代次數為100。

由于DVRP缺少標準測試實例庫，所以數據是在邊長為25km正方形區(qū)域內隨機產生的17個固定需求客戶，車場坐標為[18，70，15.29]，在t時刻隨機產生3個新需求客戶，其位置坐標與需求量分別為：C1（20.5，10.3），Q1=2；C2（23.0，15.0），Q2=3；C3（12.7，12.3），Q3=4。車場與17個客戶坐標及其需求信息如表1所示。

對初始客戶點進行求解，結果如表2所示。

t=5時，有3個新客戶要求服務。其坐標位置與需求量在上面已經給出，此時對線路進行重新優(yōu)化。由結果可知，車場已發(fā)出車5輛，分別位于11，10，15，7，12，除去已服務客戶點9、4、14，實時階段未服務客戶與新客戶是17個，根據第二階段實時優(yōu)化模型，計算結果如表3所示。

初始優(yōu)化路線與在t=5時實時優(yōu)化線路如圖3所示。

由表4可知，Memetic算法在最優(yōu)值、最劣值及平均值上都優(yōu)于QGA與GA兩種算法。求解DVRP時：①Memetic算法中自適應量子旋轉門更新機制求解效果更為明顯，因DVRP中不僅帶有容量約束，而且對行車距離加以限制；②Memetic算法中加入變異操作后，解質量得以提高；③加入2opt法與swap法局部搜索，使解質量得到進一步優(yōu)化。該算法表明采用改進全局搜索與有效局部搜索可獲得問題優(yōu)質解。

4結語

本文提出一種基于Memetic算法的量子遺傳算法，用于求解動態(tài)車輛調度問題。在算法改進上，采用一種新策略更新量子旋轉門，使算法搜索方向更明確；在此算法中引入了變異操作，種群多樣性得以保持；加入2opt法與swap法減少子路線以及路線間交叉，使算法收斂速度得以提高。通過仿真實驗比較驗證了所提算法求解DVRP有效性與優(yōu)越性。下一步研究將針對多車型動態(tài)車輛調度問題，設計有效全局搜索算法與局部搜索策略，并對其求解。

參考文獻參考文獻：

[1]G B DANTZIG， J H RAMSER.The truck dispatching problem[J].Management Science，1959（6）：8091.

[2]ALI HAGHANI，SOOJUNG JUNG.A dynamic vehicle routing problem with timedependent travel times[J].Computers & Operations Research，2005，32（11）：29592986.

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

[4]WANG BIN，SHANG XINCHUN，LI HAIFENG.Hybrid simulated annealing algorithm for solving vehicle routing problem[J].Computer Engineering and Design，2009，30（3）：651653.

[5]SHIH WEI LIN，YU V.E，SHUO YAH CHOU.Solving the truck and trailer routing problem based on a simulated annealing heuristic[J].Computers&Operations Research，2009，36（5）：16831689.

[6]施瑋.新型蟻群優(yōu)化算法在帶時間窗口的車輛路徑問題中的應用[D].合肥：中國科學技術大學，2015.

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

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

[9]張景玲，趙燕偉，王海燕.多車型動態(tài)需求車輛路徑問題建模及優(yōu)化[J].計算機集成制造系統(tǒng)，2010，16（3）：543551.

[10]張景玲，王萬良，趙燕偉.基于沿途補貨的多配送中心動態(tài)需求VRP[J].計算機集成制造系統(tǒng)，2013，19（4）：869878.

[11]王萬良，黃海鵬，趙燕偉，等.基于車輛共享的軟時間窗動態(tài)需求車輛路徑問題[J].計算機集成制造系統(tǒng)，2011，17（5）：162169.

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

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

[14]MOSCATO P，NORMAN M G.A memetic approach for the travelling salesman problem implementation of a computational ecology for combinatorial optimization on messagepassing systems[C]. Proceedings of the International Conference on Parallel Computing and Transport Applications，Amsterdam：IOS Press，1992：177186.

責任編輯（責任編輯：何麗）endprint