求解帶容量約束車輛路徑問題的離散布谷鳥算法

向明尚， 張 強

( 東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318 )

0 引言

帶容量約束的車輛路徑問題(Capacitated Vehicle Routing Problem,CVRP)[1]是物流研究領域中一個具有很高的實際應用和理論研究價值的問題。為求解有容量車輛路徑問題,減少陷入局部最優的情況,張景玲等[2]提出一種基于強化學習的超啟發算法；黃戈文等[3]提出一種采用灰狼空間整數編碼和先路由后分組解決方案生成策略的自適應遺傳灰狼優化算法，用于求解帶容量約束的車輛路徑問題；何國強等[4]采用傳統遺傳算法求解帶容量約束的車輛路徑問題,存在早熟收斂、易陷入局部最優等問題,設計雙種群混合遺傳算法進行求解；為解決帶容量約束的車輛路徑問題,李陽等[5]提出一種混合變鄰域生物共棲搜索算法進行求解。

布谷鳥算法(Cuckoo Algorithm,CA)是一種模擬布谷鳥寄生育雛行為的仿生優化算法[6]。近年來，人們把布谷鳥搜索算法應用到實際工程優化問題中。對制造型企業生產項目調度優化,曹圣武等[7]提出一種基于自適應布谷鳥算法的調度策略；申志平等[8]設計一種基于Adam優化算法改進布谷鳥算法，解決傳統無線傳感器網絡隨機部署分布不均問題；對最小二乘法在求解未知節點位置過程中定位精度不足,李娜等[9]提出一種基于改進布谷鳥算法的WSN節點定位算法；為解決傳統傳感器網絡隨機部署分布不均問題,胡堅等[10]提出采用布谷鳥搜索算法進行節點部署優化。布谷鳥搜索算法主要用于解決連續性問題，并且在求解復雜工程問題時CA易陷入局部最優。為改善CA的優化性能，筆者提出一種離散布谷鳥算法 (Discrete Cuckoo Algorithm,DCA)，在DCA中利用輪盤賭機制，提高初始解的質量；重定義萊維飛行和寄生巢位置更新策略，利用新的位置更新策略對路徑進行優化，引入shift法和2—opt法增強最優解的局部開發能力，進一步提高算法的優化性能；對改進效果進行仿真驗證，并將DCA與BA、ACO、SA及PSO優化算法在求解文中建立的模型上進行對比。

1 數學模型

CVRP可描述為：一組車輛從配送中心出發對若干顧客進行服務，在配送貨物時要滿足車輛容量等約束條件，服務完一條路徑上的全部客戶后返回到配送中心，要求合理安排配送路徑，使總目標函數最小。為便于分析和研究，假設：

(1)配送中心與每個客戶節點之間是相互連通的道路，所有同種車型的配送車輛從配送中心出發，完成配送任務后返回配送中心；

(2)每輛車可以對多個客戶點進行配送，但每個客戶點有且僅有一輛配送車為其服務；

(3)每條配送路徑的貨物總需求量不超過配送車輛的最大裝載限制；

(4)每個客戶的需求量小于配送車輛的最大承載量。

(1)

其中

(2)

(3)

(4)

(5)

(6)

式中：minF為目標函數，F為配送車輛行駛總路徑長度。約束條件式(2)表示每輛車不得超過其最大的承載量Q；約束條件式(3)表示車輛從配送中心出發，服務完一條配送路徑后必須返回配送中心；約束條件式(4)、式(5)表示配送車輛服務完客戶i后，一定從客戶點i離開并前往客戶點j;約束條件式(6)保證每個客戶只能被一輛配送車輛服務一次。

2 算法設計

2.1 算法原理

在自然界中，布谷鳥通常采用巢寄生的方式繁育后代，通過對布谷鳥特殊的繁殖后代模擬，ARMACHESKA M等[11]提出一種新型元啟發式算法，即CA。該算法模擬布谷鳥選巢產蛋的繁殖習性，利用萊維飛行進行路徑搜索。在算法中需要設定3個理想狀態[12]：

(1)布谷鳥一次只產一枚蛋，并隨機選擇寄生巢穴孵化，每個蛋等同于一個優化問題的解；

(2)在隨機選擇的一組寄生巢中，當前擁有最優蛋的寄生巢將被保留到下一代繼續使用；

(3)可供選擇的寄生巢數量n固定，宿主鳥發現外來鳥蛋的概率Pa∈[0,1]，此時宿主鳥將丟棄布谷鳥的蛋，或者放棄該鳥巢，從而導致孵化失敗。標準的布谷鳥算法主要用于優化空間的連續變量，但CVRP問題中計算的變量是離散的。

2.2 個體編碼

在CVRP問題中配送中心和顧客點為離散的點，因此采用非負整數編碼。布谷鳥的一枚蛋等同于優化問題的一個解，即車輛的路徑方案。配送中心用0表示，顧客點為1,2,…,n，每輛車由配送中心出發，服務完一條路徑上的顧客后，再返回配送中心。對于解空間，根據配送車-輛的承載量約束可得如{0,2,1,5,0,7,3,9,8,0,4,6,10,0}的解，表示由3輛車進行配送，3輛車的配送路徑分別為{0,2,1,5,0}，{0,7,3,9,8,0}，{0,4,6,10,0}，解的結構見圖1。

圖1 解的結構

2.3 初始解構造

對隨機方法構造初始種群不均勻問題，使用輪盤賭機制增強初始解選擇的隨機性，提高初始種群的整體質量，使得各節點有概率被選中并被選擇的可能性與其適應度大小成正比，并保持發現新路徑的能力，避免算法陷入局部最優。設dij為i節點與j之間的距離，且dij=dji，操作步驟：

(1)所有車輛從配送中心出發，未加入路徑的節點集合為C，已訪問路徑的節點集合為S；在集合C中隨機選取一點作為第一個已訪問路徑的節點。

(3)隨機生成一個實數n∈[0,1]，令n分別減去各待訪問節點被選擇的概率Pij。當n-Pij≤0時，判斷是否滿足車輛的容量約束，若是，則轉步驟(4)；否則，轉步驟(1)。

(4)將顧客節點加入已訪問路徑中，重復執行(2-3)，直至集合中待訪問節點個數為0。

2.4 算法位置更新

標準布谷鳥優化算法用來求解具有連續性的問題，求解CVRP模型時，客戶節點編碼離散，需要重新定義布谷鳥優化算法的萊維飛行和巢寄生位置更新操作。為保持布谷鳥算法位置更新特點，在離散布谷鳥算法中，采用重新定義的萊維飛行和巢寄生交替搜索進行路徑的更新操作。

2.4.1 萊維飛行重定義

DCA中用exchange法和2—opt法取代CA中的萊維飛行位置更新行為。其中，exchange法是通過隨機選擇三條路徑中的三個節點(s、u、v)，將它們的位置相互交換后形成新的路徑組合。exchange法路徑結構見圖2。由圖2可見，交換s、u、v三個節點的位置后形成三條新路徑。2—opt法主要通過局部搜索使DCA保持局部開發的能力，隨機選擇一條路徑中的兩個節點u、v，將u、v之間的節點相互交換位置，形成一條新的路徑。2—opt法路徑結構見圖3。由圖3可見，交換u、v兩個節點之間的所有節點位置后形成一條新路徑。

圖2 exchange法路徑結構

2.4.2 巢寄生重定義

DCA中用reverse法和shift法取代CA中的巢寄生行為。其中，shift法的操作為隨機選擇兩條路徑中的兩個節點u、v，交換u、v兩個節點的位置，形成兩條新的路徑。shift法路徑結構(見圖4)中，u、v兩個節點互換位置后形成新的路徑結構；reverse法主要通過局部搜索增加種群的多樣性，隨機選擇一條路徑中的兩個節點u、v，將它們之間的節點序列根據原來的順序逆序排列，形成新的路徑結構(見圖5)。由圖5可見，將u、v兩個節點之間序列逆序操作后形成一條新路徑。

圖3 2—opt法路徑結構

圖4 shift法路徑結構

圖5 reverse法路徑結構

DCA主要分為三個階段：

(1)初始化種群階段。利用輪盤賭機制提高種群的初始質量，增強初始解選擇的隨機性。

(2)萊維飛行階段。通過exchange法進行路徑間搜索，增加種群的多樣性；采用2—opt法在鄰域范圍內進行局部搜索，避免算法陷入局部最優。

(3)巢寄生階段。通過shift法改進當前路徑，使算法逐步接近最優解；通過reverse法對最優解局部搜索，提高算法的收斂速度和計算精度。

因此，DCA在理論上具有較好的全局和局部尋優能力。

2.5 算法步驟

(1)定義目標函數，初始化各參數，設置初始巢穴個數。

(2)使用輪盤賭機制進行種群的初始化，計算每條路徑的適應度值，保留最優適應度值對應的路徑M。

(3)采用離散化萊維飛行和離散化巢寄生操作得到新的路徑W、X、Y、Z，分別計算它們適應度值。

(4)選擇W、X、Y、Z中適應度值最小與路徑M的適應度值進行比較。若結果優于M，則保留新路徑為當前最優解。

(5)重復步驟(3-4)，直至算法滿足終止條件(達到最大迭代次數或者其他終止準則等)。

3 實驗與分析

采用AUGERAT標準測試集進行仿真實驗，將DCA和粒子群算法[13](Particle Swarm Optimization,PSO)、模擬退火算法[14](Simulated Annealing, SA)、蝙蝠算法[15](Bat Algorithm,BA)，以及蟻群算法[16](Ant Colony Optimization,ACO)進行比較實驗。部分算例實驗結果見表1(NV為車輛數；TD為路徑總長度)。DCA參數設置：最大迭代次數為1 000，種群數為100。對每個問題獨立求解10次，取平均值，BA、PSO、ACO和SA的基本參數設置同DCA。

表1 部分算例實驗結果對比

由表1可見，DCA在求解A-n32-k5、A-n33-k5、A-n36-k5、A-n37-k6、A-n39-k6、A-n54-k7、A-n62-k8問題時，結果優于其他4種對比算法；在求解A-n32-k5、A-n33-k5、A-n36-k5、A-n37-k6、A-n39-k6、A-n54-k7問題時，求得的最優總距離優于現在已知最優解；在求解A-n32-k5、A-n33-k6、A-n36-k5、A-n37-k5、A-n54-k7時，求得的最優車輛數優于其他4種對比算法。DCA在求解不同類型和規模的CVRP問題時有較好的性能。DCA求解部分算例的最優路徑見圖6，DCA求解部分算例的路徑總長度迭代見圖7。

由圖7可見，在算法迭代初期，DCA引入輪盤賭機制對初始種群進行優化使得總路徑長度大幅下降，在短時間內快速趨近最優解，從而體現DCA具有良好的全局搜索能力；隨迭代次數的增加，DCA的局部搜索能力逐漸占主導地位，其中，DCA采用reverse法和2—opt進行鄰域搜索，避免算法在迭代后期陷入局部最優，能充分挖掘搜索空間。因此，DCA有較好的求解能力。

圖6 DCA求解部分算例的最優路徑

圖7 DCA求解部分算例的路徑總長度迭代

4 結論

(1)提出一種離散布谷鳥算法(DCA)，引入輪盤賭機制優化初始種群，對布谷鳥算法的萊維飛行和巢寄生操作重定義，可以更加高效求解CVRP，尋優質量優于BA、ACO、SA、PSO算法。

(2)DCA在求解CVRP模型前期具備較強的全局搜索能力，后期有較強的局部尋優能力，并且在求解大規模數據量的問題時，具有較好的尋優能力。