基于改進(jìn)的鯨魚優(yōu)化算法的物流車輛配送路徑規(guī)劃

唐 彥，張進(jìn)軍

(安徽警官職業(yè)學(xué)院，安徽 合肥 230001)

帶容量約束的車輛路徑問(wèn)題(Capacitated Vehicle Routing Problem，CVRP)的主要特征是車輛有最大容量限制、各客戶需求點(diǎn)有貨物配送需求，該問(wèn)題是一種典型的NP-Hard組合優(yōu)化問(wèn)題[1]。傳統(tǒng)算法很難求解CVRP問(wèn)題，近年來(lái)很多研究人員將群智能算法應(yīng)用于CVRP問(wèn)題求解。文獻(xiàn)2將混合變鄰域生物共棲搜索算法應(yīng)用于CVRP問(wèn)題求解[2]。文獻(xiàn)3將多種群人工蜂群算法用來(lái)求解帶重新路由策略的CVRP問(wèn)題[3]。文獻(xiàn)4提出了一種基于改進(jìn)的粒子群優(yōu)化算法的車輛路徑優(yōu)化方法[4]。

鯨魚優(yōu)化算法[5](Whale Optimization Algorithm，WOA)具有控制參數(shù)少、收斂速度快和計(jì)算簡(jiǎn)單等優(yōu)點(diǎn)，是一種模仿座頭鯨捕食行為而衍生出的新型群體智能搜索算法。該算法已在機(jī)器學(xué)習(xí)、函數(shù)尋優(yōu)、數(shù)據(jù)挖掘、電力調(diào)度、控制器設(shè)計(jì)調(diào)優(yōu)等方面得到廣泛應(yīng)用[6-7]。目前應(yīng)用鯨魚優(yōu)化算法求解CVRP的文獻(xiàn)較少，因此本文提出一種基于改進(jìn)的鯨魚優(yōu)化算法的物流配送車輛路徑優(yōu)化方法。研究結(jié)果表明，與WOA、PSO和GA相比，改進(jìn)鯨魚優(yōu)化算法可以有效降低物流配送成本和減少配送距離，為車輛路徑規(guī)劃提供了新的方法。

1 改進(jìn)的WOA算法

在標(biāo)準(zhǔn)的WOA算法中，座頭鯨包括包圍獵物、狩獵行為和隨機(jī)搜索獵物等3種行為，每一只座頭鯨的位置為一個(gè)可行解。

1.1 包圍獵物

座頭鯨發(fā)現(xiàn)獵物后能夠快速包圍式(1)所示的所發(fā)現(xiàn)的獵物并更新位置：

(1)

(2)

式(2)中，M為最大迭代次數(shù)；a和r為隨機(jī)數(shù)，a∈[2,0]，r∈[0,1]。

1.2 狩獵行為

座頭鯨狩獵采用如式(3)所示的螺旋運(yùn)動(dòng)方式：

(3)

式(3)中，l∈[-1,1]的隨機(jī)數(shù)；b為螺旋形狀的常數(shù)。

在座頭鯨的狩獵行為中，鯨魚位置更新的過(guò)程中將以50%的概率包圍如式(4)所示的獵物或進(jìn)行螺旋式狩獵：

(4)

1.3 隨機(jī)搜索獵物

當(dāng)A>1或A<-1時(shí)，鯨魚群體離獵物遠(yuǎn)去，隨機(jī)搜索更為合適的獵物，數(shù)學(xué)模型為式(5)所示：

D=|C·Xrand(t)-X|，X(t+1)=Xrand-A·D

(5)

式(5)中，Xrand為隨機(jī)選擇的鯨魚位置。

針對(duì)鯨魚算法容易陷入局部最優(yōu)和“早熟”問(wèn)題，將非線性收斂因子引入標(biāo)準(zhǔn)WOA算法，提出一種改進(jìn)的鯨魚優(yōu)化算法(Improved Whale Optimization Algorithm，IWOA)，其改進(jìn)策略為：

收斂因子a數(shù)值大小直接影響WOA算法的搜索能力和尋優(yōu)能力。在基本W(wǎng)OA算法中，收斂因子a搜索前期較大，后期較小，導(dǎo)致其后期容易陷入局部最優(yōu)，本文為解決該問(wèn)題，提出一種隨迭代次數(shù)非線性變化的收斂因子，其更新公式為式(6)：

(6)

式(6)中，astart和aend分別為a的初始值和終止值；μ為調(diào)節(jié)系數(shù)，文中取μ=25。

2 物流車輛配送路徑規(guī)劃

車輛配送路徑規(guī)劃問(wèn)題可表述為[8-9]：假設(shè)配送中心配備有K輛物流運(yùn)輸車，車輛載重容量為qk(k=1,2,3,…,K)，配送需求點(diǎn)有L個(gè)，第i個(gè)需求點(diǎn)的需求量為gi(max(gi)≤max(qi))，完成需求點(diǎn)任務(wù)i貨物裝載或卸貨的時(shí)間為Ti，其中任務(wù)i必須在時(shí)間段[ETi,LTi]內(nèi)完成。ETi、LTi分別為任務(wù)i的最早開始時(shí)間和最遲開始時(shí)間。若配送車輛早于ETi到達(dá)需求點(diǎn)，則配送車輛等待；否則，任務(wù)將被延遲。車輛物流配送示意圖如圖1所示。

圖1 車輛物流配送示意圖

根據(jù)問(wèn)題描述將貨物需求點(diǎn)編號(hào)為1,2,3，…,L，物流配送中心編號(hào)為0，任務(wù)和配送中心編號(hào)為i=(0,1,2,3,…L)，則決策變量為[10]：

(7)

(8)

綜合所述，物流車輛配送路徑數(shù)學(xué)規(guī)劃模型為：

(9)

(10)

(11)

(12)

式(9)～(12)中，si為配送車輛到達(dá)需求點(diǎn)i的時(shí)間；cij為需求點(diǎn)i到需求點(diǎn)j的運(yùn)輸成本；pE、pL分別為配送車輛提前到達(dá)需求點(diǎn)i的或者滯后到達(dá)需求點(diǎn)i的單位時(shí)間內(nèi)的等待成本以及懲罰成本。該數(shù)學(xué)模型中每個(gè)需求點(diǎn)均有車輛配送，且每個(gè)需求點(diǎn)只能由一輛物流配送車輛配送；與此同時(shí)，同一配送路徑上的需求點(diǎn)的需求量之和應(yīng)小于等于物流配送車輛的最大載重。

為實(shí)現(xiàn)物流配送車輛路徑的最優(yōu)規(guī)劃，解決該問(wèn)題的關(guān)鍵是構(gòu)造合適的最佳鯨魚位置表達(dá)方式。參考文獻(xiàn)11-12構(gòu)造一個(gè)2L維空間對(duì)應(yīng)L個(gè)需求點(diǎn)任務(wù)的物流配送車輛路徑規(guī)劃問(wèn)題，保證需求點(diǎn)任務(wù)為2維[11-12]。若需求點(diǎn)任務(wù)為7，配送車輛為3，需求點(diǎn)任務(wù)編號(hào)為[1 2 3 4 5 6 7]。此時(shí)最佳鯨魚位置向量X如圖2所示，其中最佳鯨魚位置對(duì)應(yīng)物流配送車輛的編號(hào)和行駛路徑。

圖2 車輛和路徑編號(hào)

由圖2車輛和路徑編號(hào)可知，最佳鯨魚位置對(duì)應(yīng)的物流車輛配送路徑為：(1)車輛1∶0→1→0；(2)車輛2∶0→4→5→3→2→0；(3)車輛3∶0→7→6→0。

基于IWOA的車輛配送物流路徑優(yōu)化算法步驟具體描述如下：

Step1：設(shè)定IWOA算法參數(shù)：種群規(guī)模N、最大迭代次數(shù)Maxgen、當(dāng)前迭代次數(shù)t以及螺旋形狀常數(shù)b，并且隨機(jī)初始化鯨魚群體初始位置Xi(i=1,2,…,n)；

Step2：按式(13)計(jì)算每個(gè)鯨魚個(gè)體的適應(yīng)度，并對(duì)適應(yīng)度進(jìn)行排序，找到適應(yīng)度最小時(shí)所對(duì)應(yīng)的鯨魚個(gè)體即最佳鯨魚個(gè)體X*并保存；

(13)

Step3：如果t≤Maxgen，則更新參數(shù)a、A、C、l和p；

Step4：當(dāng)p<0.5時(shí)，如果|A|<1，按式(1)更新當(dāng)前鯨魚個(gè)體的空間位置；當(dāng)|A|≥1時(shí)，則隨機(jī)選擇鯨魚個(gè)體位置Xrand，并且按式(5)更新當(dāng)前鯨魚個(gè)體的空間位置；

Step5：當(dāng)p≥0.5時(shí)，按式(4)更新當(dāng)前鯨魚個(gè)體的空間位置；

Step6：限制和修正鯨魚個(gè)體搜索空間；

Step7：按式(13)計(jì)算每個(gè)鯨魚個(gè)體的適應(yīng)度，并對(duì)適應(yīng)度進(jìn)行排序，找到適應(yīng)度最小時(shí)所對(duì)應(yīng)的鯨魚個(gè)體即最佳鯨魚個(gè)體X*并保存；

Step8：判斷算法終止條件：如果t≥Maxgen，則轉(zhuǎn)到步驟Step9；反之，重復(fù)步驟Step3～Step7；

Step9：輸出最優(yōu)鯨魚個(gè)體的空間位置X*及其適應(yīng)度，即輸出車輛物流配送路徑。

3 仿真試驗(yàn)與結(jié)果分析

為了驗(yàn)證IWOA進(jìn)行物流配送車輛路徑規(guī)劃的有效性和可靠性，選擇參考文獻(xiàn)13中實(shí)例為研究對(duì)象[13]，各需求點(diǎn)的坐標(biāo)位置以及用戶需求和中心倉(cāng)庫(kù)數(shù)據(jù)信息如表1和表2所示。

表1 配送中心和需求點(diǎn)坐標(biāo)

表2 配送中心和用戶需求

將IWOA和WOA、PSO、GA進(jìn)行對(duì)比，不同算法參數(shù)設(shè)置如下：(1)WOA參數(shù)：種群規(guī)模N=50、最大迭代次數(shù)Maxgen=500。(2)粒子群算法(particle swarm optimization algorithm，PSO)：種群規(guī)模N=50、最大迭代次數(shù)Maxgen=500、學(xué)習(xí)因子c1=c2=2、慣性權(quán)重w=0.2。(3)遺傳算法(genetic algorithm，GA)：種群大小N=50、最大迭代次數(shù)Maxgen=500交叉概率Pc=0.7和變異概率Pm=0.1，對(duì)比結(jié)果如圖3～圖7所示。

圖3 IWOA配送路徑圖

圖4 WOA配送路徑圖

圖5 PSO配送路徑圖

圖6 GA配送路徑圖

圖7 尋優(yōu)對(duì)比曲線

由表3可知，GA、PSO和GA進(jìn)行物流車輛配送路徑規(guī)劃時(shí)，GA的平均行駛成本和行駛里程分別為603.0031元和139.5906km，PSO的平均行駛成本和行駛里程分別為565.8001元和138.9368km，WOA的平均行駛成本和行駛里程分別為359.3838元和130.2608km，而改進(jìn)的IWOA的平均行駛成本和行駛里程分別為337.6755元和129.1333km。與WOA、PSO和GA相比，在行駛里程和平均行駛成本方面，IWOA進(jìn)行車輛路徑規(guī)劃的成本最低且行駛里程最短。由圖7尋優(yōu)對(duì)比曲線可知，IWOA進(jìn)行車輛路徑規(guī)劃尋優(yōu)具有更快的收斂速度和更低的平均行駛成本。通過(guò)綜合對(duì)比驗(yàn)證了IWOA進(jìn)行物流車輛配送路徑優(yōu)化的有效性和可靠性。

表3 IWOA、WOA、PSO和GA對(duì)比結(jié)果

4 結(jié)論

本文運(yùn)用改進(jìn)的鯨魚優(yōu)化算法求解物流配送路徑規(guī)劃問(wèn)題。研究結(jié)果表明，與WOA、PSO和GA相比，在搜索時(shí)間和平均行駛成本方面，IWOA進(jìn)行車輛路徑規(guī)劃的配送成本最低且行駛里程最少，為物流配送車輛路徑優(yōu)化提供了新的方法。