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

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

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

DOIDOI：10.11907/rjdk.171984

中圖分類號：TP319

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

0引言

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

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

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

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

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

1DCVRP問題描述及數(shù)學(xué)模型

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

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

圖2swap法原理

2.4適應(yīng)度值計(jì)算

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

2.5Memetic算法步驟

Memetic算法步驟如下：

step1：種群初始化，隨機(jī)產(chǎn)生初始種群；

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

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

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

step5：自適應(yīng)量子門旋轉(zhuǎn)門更新；

step6：量子比特種群進(jìn)行變異操作；

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

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

3仿真實(shí)驗(yàn)與算法比較

本文為了對算法性能進(jìn)行驗(yàn)證，將Memetic算法與量子遺傳算法以及遺傳算法作比較。所有算法程序均由MATLAB編碼實(shí)現(xiàn)。每種算法均獨(dú)立重復(fù)運(yùn)行20次，每次最大迭代次數(shù)為100。

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

對初始客戶點(diǎn)進(jìn)行求解，結(jié)果如表2所示。

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

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

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

4結(jié)語

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

參考文獻(xiàn)參考文獻(xiàn)：

[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)網(wǎng)絡(luò)車輛路徑問題研究[D].成都：西南交通大學(xué)，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)化算法在帶時(shí)間窗口的車輛路徑問題中的應(yīng)用[D].合肥：中國科學(xué)技術(shù)大學(xué)，2015.

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

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

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

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

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

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

[13]王旭，葛顯龍，代應(yīng).基于兩階段求解算法的動態(tài)車輛調(diào)度問題研究[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.

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