求解車輛路徑問題的改進(jìn)布谷鳥算法

孟慶永+張啟慧

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

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

中圖分類號：G4 文獻(xiàn)標(biāo)識碼：A doi：10.19311/j.cnki.1672-3198.2016.33.171

0 引言

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

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

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

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

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

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

2 基本CS算法

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

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

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

3 車輛路徑問題的改進(jìn)CS算法

3.1 構(gòu)造解向量

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

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

假設(shè)有一6個客戶，3輛車的VRP問題，對其客戶進(jìn)行編號：{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進(jìn)行整數(shù)排序，并與客戶編號對應(yīng)。

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

將X視作客戶編號的下標(biāo)，按照下標(biāo)大小順序?qū)蛻艟幪栠M(jìn)行排列，得到一組行車路徑：4-0-2-6-1-5-0-3.每輛車的行車路徑為：車1：0-4-0；車2：0-2-6-1-5-0；車3：0-3-0。上述解的構(gòu)造方式可以確保每個客戶有且僅有一輛車為其提供配送服務(wù)，且到達(dá)或離開某一客戶的車輛有且僅有一輛。

3.2 構(gòu)造適應(yīng)值函數(shù)

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

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

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

本文在基本CS算法的基礎(chǔ)上，引入遺傳算法、微分算法等進(jìn)化算法普遍使用的解的交叉思想，提出一種帶動態(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不是直接進(jìn)入t+1次的迭代，而是將Xt1i、Xt2i各維分量進(jìn)行隨機(jī)重組生成新的交叉向量Xti，Xti作為鳥巢的最新位置進(jìn)入t+1次迭代，其j維分量的值通過下面公式生成：

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

CSDC算法的具體實(shí)施步驟如下：

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)1

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

PSO算法：慣性權(quán)重ω=0.729，學(xué)習(xí)因子C1=C2=1.49，領(lǐng)域結(jié)構(gòu)采用環(huán)形結(jié)構(gòu)，子群數(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，適應(yīng)值fitness>105時，交叉概率取CR1，否則取CR2。上述三種算法的種群數(shù)N=25，罰系數(shù)R=108，最大迭代次數(shù)MaxIter=200，每種算法連續(xù)獨(dú)立運(yùn)行20次。測試結(jié)果如表1所示。

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

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

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

4.2 實(shí)驗(yàn)2

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

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

由表4可以看出，3種算法獨(dú)立運(yùn)行5次，CSDC所得結(jié)果優(yōu)于QGA和HQGA，獲得最優(yōu)解里程為108.6，對應(yīng)車輛路徑為：車輛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。上述實(shí)驗(yàn)結(jié)果表明，CSDC算法用于VRP問題的求解是行之有效的，對于規(guī)模較大的VRP問題，可以適當(dāng)增大lévy飛行的步長控制因子及發(fā)現(xiàn)概率，以便算法能夠在更大維度的解空間上尋優(yōu)，降低陷入局部最優(yōu)的概率，提高尋優(yōu)質(zhì)量。

5 結(jié)論

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

參考文獻(xiàn)

[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].計算機(jī)工程與設(shè)計，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ìn)二進(jìn)制布谷鳥搜索算法求解多維背包問題[J].計算機(jī)應(yīng)用，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]肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進(jìn)微粒群優(yōu)化算法[J].計算機(jī)集成制造系統(tǒng)，2005，11（04）：577-581.

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

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

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