孟慶永+張啟慧

摘 要：將一種新型的智能優(yōu)化算法——布谷鳥算法（Cuckoo Search Algorithm，CS）用于車輛路徑問題的求解。針對基本CS算法種群多樣性差、尋優(yōu)精度低等不足，提出一種動態(tài)交叉算子來豐富種群多樣性，避免種群個體陷入局部最優(yōu)，增強算法的全局尋優(yōu)能力。通過對比試驗驗證了算法在求解VRP問題時具有尋優(yōu)精度高、性能穩(wěn)定等特點，是求解VRP問題的一種有效的算法。

關鍵詞：車輛路徑問題；布谷鳥算法；動態(tài)交叉

中圖分類號：G4 文獻標識碼：A doi：10.19311/j.cnki.1672-3198.2016.33.171

0 引言

車輛路徑問題（the vehicle routing problem，VRP）源于旅行商問題（TSP），最初由Dangzig等于1959年提出，用于解決運輸車隊在一個煉油廠和多個加油站之間最優(yōu)路徑問題，后來逐漸演化成經(jīng)典的VRP問題，又叫基本VRP問題或有容量約束的VRP（CVRP）。VRP問題可以簡單描述為一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，由若干隸屬于同一中心倉庫的車輛進行配送，在車輛容量有約束的前提下，尋找一組最優(yōu)行車路線，目標是使客戶需求得到滿足的同時，資源（路程、成本、時間等）消耗最小。車輛路徑問題是重要的組合優(yōu)化問題，其成果可以直接應用于物流配送調度優(yōu)化，也可為諸多實際問題如垃圾收集、街道清潔、公交路線等領域的優(yōu)化提供了解決思路。所以車輛路徑問題一直以來都是組合優(yōu)化領域的研究熱點。

文獻詳細調查了近年來VRP問題的算法研究，結果顯示求解VRP的算法主要可以歸納為三類：精確算法、啟發(fā)式算方法和元啟發(fā)式算法，其中元啟發(fā)式算法占比達65%-80%。這與VRP問題性質有關，由于VRP問題是NP-hard問題，隨著問題規(guī)模的增長，VRP問題的可行解會出現(xiàn)“組合爆炸”現(xiàn)象，精確算法和經(jīng)典啟發(fā)式算法在求解該類問題時，計算復雜度高，計算開銷大，甚至無法獲得可行解，而元啟發(fā)式算法具有快速的尋優(yōu)的性能，使其成為求解VRP問題的主要算法。目前，求解VRP問題的元啟發(fā)式算法可以大致歸納如下：（1）遺傳算法（GA）；（2）蟻群算法（ACO）；（3）模擬退火算法（SA）；（4）可變領域搜索（VNS）；（5）禁忌搜索算法（TS）；（6）局部搜索算法（LS）；（7）人工蜂群算法（ABC）；（8）粒子群算法（PSO）；（9）其他新興元啟發(fā)式算法，如蛙跳算法、蝙蝠算法、螢火蟲算法等以及各種改進版本，更多關于VRP問題的元啟發(fā)式算法參見文獻。

雖然已有大量優(yōu)秀的算法，但追求更高效的算法是VRP及其它組合優(yōu)化問題一個重要的研究方向。本文將引入一種新興元啟發(fā)算法——布谷鳥算法（Cuckoo Search，CS），對其改進后用于VRP問題的求解。CS算法是由劍橋大學學者Yang和Deb于2009年提出的一種仿生智能算法。該算法的思想主要基于兩個策略：一是布谷鳥通過lévy飛行機制尋找寄生巢，二是丟棄被發(fā)現(xiàn)的鳥巢并通過偏好隨機游走的方式更新鳥巢位置。這種尋優(yōu)方式結合了lévy飛行的全局搜索和隨機游走的局部搜索，是一種簡潔高效的尋優(yōu)模式。根據(jù)文獻，CS算法在連續(xù)型優(yōu)化領域有著廣泛的研究，涉及多目標優(yōu)化、神經(jīng)網(wǎng)絡優(yōu)化、工程設計、交通流量預測以及圖像處理等，但在離散型組合優(yōu)化領域的研究并不多見，主要集中于二進制CS算法求解經(jīng)典NP難題（0/1背包問題、TSP問題）、生產(chǎn)調度優(yōu)化以及無線網(wǎng)絡優(yōu)化，鮮見將CS算法應用于求解VRP問題的研究?？紤]到CS算法求解優(yōu)化問題的突出優(yōu)勢，本文將其應用于基本VRP問題的求解，針對VRP問題的特性，提出一種帶有動態(tài)交叉策略的布谷鳥算法（CSDC），其核心思想是：引入遺傳算法、微分算法等進化算法中的交叉變異思想，在種群經(jīng)過lévy飛行和偏好隨機游走兩個環(huán)節(jié)后，對種群進行交叉選擇操作，豐富種群的多樣性，避免陷入局部最優(yōu)，進一步提高CS算法的尋優(yōu)性能。

1 VRP問題描述及數(shù)學模型

基本VRP問題可描述為：設點集V={0，1，2，…，k}表示k個客戶和一個中心倉庫，其中{0}表示倉庫，設客戶i的貨物需求量為gi，i∈V-{0}，中心倉庫有m輛載重量為q（q>gi）的車向k個客戶配送貨物，cij表示從客戶i到客戶j的成本（時間、路程、花費等），求一組可行的運輸路線，使得所有客戶需求得到滿足的情況下，所用車輛數(shù)和總運輸成本（路程）最小，其中每個客戶只能由一輛車配送，且每輛車的運輸量不得超過容量上限。首先定義變量：

其中，（2）為車輛容量約束；（3）表示每個需求點運輸任務僅由一輛車完成；（4）和（5）保證了到達和離開某個需求點的車輛有且僅有1輛。

2 基本CS算法

CS算法通過模擬布谷鳥尋找寄生鳥巢的行為尋找最優(yōu)解，其尋優(yōu)過程如下：

步驟1：在目標函數(shù)的解空間內(nèi)隨機生成n個鳥巢N={X1，X2，…，XN}，Xi是第i個鳥巢的位置，對應于目標函數(shù)解空間的一個隨機可行解，如果解的維數(shù)是k，則第i個鳥巢的位置Xi={xi1，xi2，…，xik}；計算每個鳥巢位置的適應值f（Xi），i∈{1，2，…，n}，找出適應值最好的鳥巢X，其中f（X）是目標函數(shù)，對于最小化問題，目標函數(shù)值越小適應值越好。

步驟4：評估所有鳥巢位置，找出最優(yōu)鳥巢及其適應值，并將新的鳥巢位置放入步驟（2）中繼續(xù)迭代，直到滿足停止條件為止，然后輸出最優(yōu)鳥巢（最優(yōu)解）及適應值。

3 車輛路徑問題的改進CS算法

3.1 構造解向量

基本CS算法用來求解連續(xù)域函數(shù)優(yōu)化問題的，對于離散組合優(yōu)化如VRP問題，必須根據(jù)問題特點合理構造解向量的編碼方式，使其適用于CS算法。本文借鑒文獻的編碼思想，采用實數(shù)編碼方式，將離散域問題轉換為連續(xù)域問題。

對于m輛車，k個客戶的VRP問題，構造一個k+m-1維實數(shù)向量，該向量包含一個VRP問題解的完整信息：X=（x1，x2，…，xk+m-1），xi∈[1，k+m-1]，其解碼過程如下：

假設有一6個客戶，3輛車的VRP問題，對其客戶進行編號：{1，2，3，4，5，6，0，0}，其中{0}代表中心倉庫，其數(shù)量為車輛數(shù)減1。按上述編碼規(guī)則產(chǎn)生一個解向量X={5.2，4.6，7.8，1.2，6.4，4.9，2.3，71}，對X進行整數(shù)排序，并與客戶編號對應。

客戶編號：{1，2，3，4，5，6，0，0}，X：{5，3，8，1，6，4，2，7}

將X視作客戶編號的下標，按照下標大小順序對客戶編號進行排列，得到一組行車路徑：4-0-2-6-1-5-0-3.每輛車的行車路徑為：車1：0-4-0；車2：0-2-6-1-5-0；車3：0-3-0。上述解的構造方式可以確保每個客戶有且僅有一輛車為其提供配送服務，且到達或離開某一客戶的車輛有且僅有一輛。

3.2 構造適應值函數(shù)

適應值函數(shù)是評價一組解優(yōu)劣的標準，對于無約束優(yōu)化問題，目標函數(shù)即適應值函數(shù)，但基本VRP問題是帶有車輛容量約束的優(yōu)化問題，為編程方便，簡化計算過程，可以通過罰函數(shù)將車輛約束整合到目標函數(shù)中，構建新的適應值函數(shù)：

其中：R是罰系數(shù)，可以設置為一個足夠大的正數(shù)，將其與總過載量相乘。這樣，超出車輛容量限制的不可行解會被賦予很大適應值，在迭代中會被淘汰掉。

3.3 帶動態(tài)交叉操作的CS算法

本文在基本CS算法的基礎上，引入遺傳算法、微分算法等進化算法普遍使用的解的交叉思想，提出一種帶動態(tài)交叉操作的CS算法（CSwith Dynamic Crossover Operation，CSDC）。通過交叉操作提高種群的多樣性，避免種群陷入局部最優(yōu)，提高算法的尋優(yōu)性能。

CSDC算法的基本思想是：基本CS算法在經(jīng)過lévy飛行后產(chǎn)生一個新位置Xt1i，丟棄部分被發(fā)現(xiàn)的鳥巢又產(chǎn)生一個新位置Xt2i，此時，Xt2i不是直接進入t+1次的迭代，而是將Xt1i、Xt2i各維分量進行隨機重組生成新的交叉向量Xti，Xti作為鳥巢的最新位置進入t+1次迭代，其j維分量的值通過下面公式生成：

式中，rand是[0，1]間的隨機數(shù)；CR是范圍在[0，1]間的常數(shù)，稱為交叉常量。CR取值越大，Xt2i中分量被選擇的機會越大，Xti位置越接近Xt2i，反之則Xti越接近Xt1i。CR較好的取值范圍是0.3到0.9之間，比較好的選取值是0.5。本文根據(jù)VRP問題的特點，動態(tài)選取0.7和0.35兩個值作為交叉常量，如果位置Xt2i（解向量）違反了車輛容量約束，選取CR=0.35，即Xti更多地選取Xt1i中的分量構建新位置；反之，選取CR=0.7。通過適應值可以判斷Xt2i是否違反容量約束。通過上述交叉操作，一是豐富了種群的多樣性，避免陷入局部最優(yōu)，提高算法的尋優(yōu)性能；二是通過動態(tài)選取交叉常量，加速了算法的收斂速度。

CSDC算法的具體實施步驟如下：

步驟1：初始化種群。設置種群大小N，最大迭代次數(shù)MaxIter，發(fā)現(xiàn)概率pa，交叉常量CR。按照上述構造解向量的規(guī)則，隨機產(chǎn)生N個鳥巢位置，超出邊界值的分量取邊界值，得N個初始鳥巢位置：X（0）={X01，X02，…，X0N}。

步驟2：根據(jù)式（11）計算每個鳥巢位置的適應值fitness，記錄最優(yōu)值及相應最優(yōu)鳥巢的位置。

步驟3：保留上代最優(yōu)鳥巢位置，按照式（8）、（9）通過lévy飛行機制更新鳥巢位置，并對更新后的鳥巢位置做越界處理。

步驟4：利用式（11）計算步驟3生成的新鳥巢位置適應值，找出最優(yōu)值；對比上一代鳥巢位置的最優(yōu)值，若優(yōu)，則替換上一代最優(yōu)值，并更新相應最優(yōu)鳥巢位置，確定當前最優(yōu)鳥巢位置及最優(yōu)值。

步驟5：按照式（10）隨機改變被發(fā)現(xiàn)的鳥巢位置，得到一組新鳥巢位置。

步驟6：將步驟4和步驟5獲得的鳥巢位置按式（12）作交叉操作，得到一組新鳥巢位置。

步驟7：評價步驟6產(chǎn)生的鳥巢位置適應值，確定當前最優(yōu)鳥巢位置及最優(yōu)值。

步驟8：進入下一次迭代。判斷是否滿足結束條件，滿足則退出迭代，輸出最優(yōu)值及最優(yōu)鳥巢位置，否則轉步驟3繼續(xù)迭代。

4 實驗結果與分析

4.1 實驗1

為驗證本文提出的算法在求解VRP問題時的性能，我們采用MATLAB（2014a）分別編寫了求解VRP問題的局部粒子群算法（Particle Swarm Optimization，PSO）、基本布谷鳥算法（Cuckoo Search，CS）和帶動態(tài)交叉操作的布谷鳥算法（Cuckoo Search with Dynamic Crossover Operation，CSDC）。采用文獻提供的算例，將上述算法應用于8個客戶，1個中心倉庫，3輛車的基本VRP問題，已知問題的最優(yōu)里程數(shù)為67.5，最優(yōu)路徑為0-4-7-6-0-1-3-5-8-2-0。實驗環(huán)境為Windows7平臺+Intel酷睿5i CUP+4G內(nèi)存，算法相關參數(shù)設置如下：

PSO算法：慣性權重ω=0.729，學習因子C1=C2=1.49，領域結構采用環(huán)形結構，子群數(shù)是3；CS算法：發(fā)現(xiàn)概率pa=0.2，步長控制因子α=0.01×randn；CSDC算法：發(fā)現(xiàn)概率和步長控制因子同CS算法，動態(tài)交叉概率CR1=0.35，CR2=0.7，適應值fitness>105時，交叉概率取CR1，否則取CR2。上述三種算法的種群數(shù)N=25，罰系數(shù)R=108，最大迭代次數(shù)MaxIter=200，每種算法連續(xù)獨立運行20次。測試結果如表1所示。

從測試結果可以看出，上述3種算法均能找到已知最優(yōu)解，其中CSDC的尋優(yōu)成功率遠高于PSO和CS算法，反映出CSDC具有良好的全局收斂性。從平均值和標準差兩個指標來看，CSDC所求最優(yōu)里程的質量也遠高于PSO和CS算法，且CSDC求得最優(yōu)里程的標準差很小，表明CSDC對初始值具有較強的魯棒性，顯示出其在離散空間良好的尋優(yōu)性能。由于增加了動態(tài)交叉操作，CSDC的平均運算時間略高于CS算法。從平均值的進化曲線（圖1）和具有代表性的單次進化曲線（圖2）可以直觀看出，對于上述VRP問題，PSO和CS容易收斂于局部最優(yōu)解，而CSDC的收斂速度與精度均高于其他兩種算法，表明通過動態(tài)交叉操作豐富解的多樣性，可以提高算法跳出局部最優(yōu)的可能性同時提高了收斂速度。

為進一步驗證CSDC算法求解小規(guī)模VRP的效率，選取文獻中的算例作對比試驗。文獻采用蝙蝠算法（Bat Algorithm，BA）求解7個客戶、3輛車的VRP問題，本文將CSDC算法用于同一問題的求解，迭代次數(shù)，種群數(shù)設置與文獻相同，其它參數(shù)與上述設置相同，連續(xù)運行20次，結果如表2。

由表2可知，CSDC連續(xù)運行20次，達到最優(yōu)路徑20次，運行時間為35.59秒，運行時間及獲得最優(yōu)解的成功率均高于BA，表明CSDC在求解小規(guī)模VRP問題上有較高的效率。

4.2 實驗2

實驗2選用文獻中的算例，進一步驗證CSDC算法在解決較大規(guī)模VRP問題時的性能。該算例是20個客戶、5輛車的VRP問題，每輛車載重8t，配送中心坐標是（14.5，13.0），各客戶坐標及需求量見表3，求一組最小運輸路徑。

由于客戶規(guī)模增大，解向量的維數(shù)也相應增多，為提高尋優(yōu)的效率，將步長控制因子α設置為1.5×randn，發(fā)現(xiàn)概率設置為0.7，最大迭代次數(shù)為2000次（與文獻設置相同）。將CSDC求解結果與文獻提出的量子遺傳算法（QGA）、混合量子遺傳算法（HQGA）求解結果進行比較，如表4所示。

由表4可以看出，3種算法獨立運行5次，CSDC所得結果優(yōu)于QGA和HQGA，獲得最優(yōu)解里程為108.6，對應車輛路徑為：車輛1：0-3-17-11-20-18-0；車輛2：0-4-0；車輛3：0-6-13-16-15-19-8-0；車輛4：0-1-7-10-9-12-2-14-5-0。上述實驗結果表明，CSDC算法用于VRP問題的求解是行之有效的，對于規(guī)模較大的VRP問題，可以適當增大lévy飛行的步長控制因子及發(fā)現(xiàn)概率，以便算法能夠在更大維度的解空間上尋優(yōu)，降低陷入局部最優(yōu)的概率，提高尋優(yōu)質量。

5 結論

本文將CS算法應用于求解離散空間的VRP問題，針對基本CS算法局部搜索能力不強，收斂精度不高等特點，引入動態(tài)交叉算子，提出一種帶動態(tài)交叉操作的CS算法。該算法在進化過程中，經(jīng)過CS算法兩個基本步驟后，不會直接進入下一次迭代，而是將兩個步驟產(chǎn)生的位置向量根據(jù)適應值大小進行交叉操作，豐富解的多樣性，避免陷入局部最優(yōu)。實驗結果表明，用該算法求解VRP問題可以取得不錯的收斂精度，但動態(tài)交叉操作要計算新位置的適應值，一定程度上影響了運行速度，這是后續(xù)研究需要改進的地方。

參考文獻

[1]Dan tzing G，RAMSER J.The truck dispatching problem[J].Management Science，1959，10（6）：80-911.

[2]Braekers K，Ramaekers K，Nieuwenhuyse I V.The vehicle routing problem：State of the art classification and review[J].Computers & Industrial Engineering，2016：1-49.

[3]Eksioglu B，Vural A V，Reisman A.The vehicle routing problem： A taxonomic review[J].Computers & Industrial Engineering，2009，57（4）：1472-1483.

[4]Montoya-Torres J R，F(xiàn)ranco J L，Isaza S N，et al.A literature review on the vehicle routing problem with multiple depots[J].Computers & Industrial Engineering，2014，79：115-129.

[5]Yang X S，Deb S.Cuckoo Search via Lévy flights[C].Nature & Biologically Inspired Computing，2009. NaBIC 2009.World Congress on.IEEE，2009：210-214.

[6]Fister I，Yang X S，F(xiàn)ister D，et al.Firefly Algorithm：A Brief Review of the Expanding Literature[M].Cuckoo Search and Firefly Algorithm，2014：347-360.

[7]蘭少峰，劉升.布谷鳥搜索算法研究綜述[J].計算機工程與設計，2015，（04）：1063-1067.

[8]Ouaarab A，Ahiod B，Yang X S.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing & Applications，2014，24（7-8）：1659-1669.

[9]張晶，吳虎勝.改進二進制布谷鳥搜索算法求解多維背包問題[J].計算機應用，2015，35（01）：183-188.

[10]Yao Y，Chunming Y E，Business S O.Solving job-shop scheduling problem by cuckoo search algorithm[J].Computer Engineering & Applications，2015.

[11]Wang H，Wang W，Sun H，et al.A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems[J].Soft Computing，2016：1-11.

[12]Alazzawi M K，Luo J，Li R，et al.Multiple Node Selection Aimed to Optimum Data Delivery Route Using Discrete Cuckoo Search Algorithm for Wireless Sensor Networks[J].Journal of Computational & Theoretical Nanoscience，2015，12（2）：316-325.

[13]Mantegna R N.Fast，accurate algorithm for numerical simulation of Lévy stable stochastic processes[J].Physical Review E Statistical Physics Plasmas Fluids & Related Interdisciplinary Topics，1994，49（5）：4677-4683.

[14]肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進微粒群優(yōu)化算法[J].計算機集成制造系統(tǒng)，2005，11（04）：577-581.

[15]段海濱.仿生智能計算[M].北京：科學出版社，2011：109-111.

[16]馬祥麗，張惠珍，馬良.蝙蝠算法在物流配送車輛路徑優(yōu)化問題中的應用[J].數(shù)學的實踐與認識，2015，（24）：80-86.

[17]蔡蓓蓓，張興華.混合量子遺傳算法及其在VRP中的應用[J].計算機仿真，2010，27（07）：267-270.