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

向明尚， 張 強(qiáng)

( 東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318 )

0 引言

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

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

1 數(shù)學(xué)模型

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

(1)配送中心與每個(gè)客戶節(jié)點(diǎn)之間是相互連通的道路，所有同種車型的配送車輛從配送中心出發(fā)，完成配送任務(wù)后返回配送中心；

(2)每輛車可以對(duì)多個(gè)客戶點(diǎn)進(jìn)行配送，但每個(gè)客戶點(diǎn)有且僅有一輛配送車為其服務(wù)；

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

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

(1)

其中

(2)

(3)

(4)

(5)

(6)

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

2 算法設(shè)計(jì)

2.1 算法原理

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

(1)布谷鳥一次只產(chǎn)一枚蛋，并隨機(jī)選擇寄生巢穴孵化，每個(gè)蛋等同于一個(gè)優(yōu)化問題的解；

(2)在隨機(jī)選擇的一組寄生巢中，當(dāng)前擁有最優(yōu)蛋的寄生巢將被保留到下一代繼續(xù)使用；

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

2.2 個(gè)體編碼

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

圖1 解的結(jié)構(gòu)

2.3 初始解構(gòu)造

對(duì)隨機(jī)方法構(gòu)造初始種群不均勻問題，使用輪盤賭機(jī)制增強(qiáng)初始解選擇的隨機(jī)性，提高初始種群的整體質(zhì)量，使得各節(jié)點(diǎn)有概率被選中并被選擇的可能性與其適應(yīng)度大小成正比，并保持發(fā)現(xiàn)新路徑的能力，避免算法陷入局部最優(yōu)。設(shè)dij為i節(jié)點(diǎn)與j之間的距離，且dij=dji，操作步驟：

(1)所有車輛從配送中心出發(fā)，未加入路徑的節(jié)點(diǎn)集合為C，已訪問路徑的節(jié)點(diǎn)集合為S；在集合C中隨機(jī)選取一點(diǎn)作為第一個(gè)已訪問路徑的節(jié)點(diǎn)。

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

(4)將顧客節(jié)點(diǎn)加入已訪問路徑中，重復(fù)執(zhí)行(2-3)，直至集合中待訪問節(jié)點(diǎn)個(gè)數(shù)為0。

2.4 算法位置更新

標(biāo)準(zhǔn)布谷鳥優(yōu)化算法用來求解具有連續(xù)性的問題，求解CVRP模型時(shí)，客戶節(jié)點(diǎn)編碼離散，需要重新定義布谷鳥優(yōu)化算法的萊維飛行和巢寄生位置更新操作。為保持布谷鳥算法位置更新特點(diǎn)，在離散布谷鳥算法中，采用重新定義的萊維飛行和巢寄生交替搜索進(jìn)行路徑的更新操作。

2.4.1 萊維飛行重定義

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

圖2 exchange法路徑結(jié)構(gòu)

2.4.2 巢寄生重定義

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

圖3 2—opt法路徑結(jié)構(gòu)

圖4 shift法路徑結(jié)構(gòu)

圖5 reverse法路徑結(jié)構(gòu)

DCA主要分為三個(gè)階段：

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

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

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

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

2.5 算法步驟

(1)定義目標(biāo)函數(shù)，初始化各參數(shù)，設(shè)置初始巢穴個(gè)數(shù)。

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

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

(4)選擇W、X、Y、Z中適應(yīng)度值最小與路徑M的適應(yīng)度值進(jìn)行比較。若結(jié)果優(yōu)于M，則保留新路徑為當(dāng)前最優(yōu)解。

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

3 實(shí)驗(yàn)與分析

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

表1 部分算例實(shí)驗(yàn)結(jié)果對(duì)比

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

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

圖6 DCA求解部分算例的最優(yōu)路徑

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

4 結(jié)論

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

(2)DCA在求解CVRP模型前期具備較強(qiáng)的全局搜索能力，后期有較強(qiáng)的局部尋優(yōu)能力，并且在求解大規(guī)模數(shù)據(jù)量的問題時(shí)，具有較好的尋優(yōu)能力。