基于改進(jìn)鯨魚算法的長江經(jīng)濟(jì)帶配送問題研究

朱光福 朱云波

(重慶城市管理職業(yè)學(xué)院商學(xué)院 重慶 401331)

0 引 言

長江經(jīng)濟(jì)帶統(tǒng)轄11個省市，覆蓋長三角、長江中游和成渝三大城市群，橫跨東部、中部和西部三大經(jīng)濟(jì)區(qū)，不僅幅員面積占國土面積21%，經(jīng)濟(jì)總量占全國45%，而且貨運量占全國53%，在我國物流發(fā)展中具有顯著地位[1-2]。從某種程度上講，長江經(jīng)濟(jì)帶物流配送問題直接影響著我國物流成本和企業(yè)競爭力。

近年來，學(xué)者們紛紛對物流配送問題進(jìn)行深入研究，提出了大量求解算法。比如，文獻(xiàn)[3]和文獻(xiàn)[4]分別提出了求解配送路徑優(yōu)化問題的遺傳算法(GA)和粒子群算法(PSO)，文獻(xiàn)[5]則根據(jù)配送路徑優(yōu)化問題的特點，對傳統(tǒng)植物算法進(jìn)行改進(jìn)優(yōu)化，提高了算法求解性能。分析可知，上述文獻(xiàn)提出的智能算法，雖然一定程度上優(yōu)化了配送方案，但仍然存在不足，比如：GA計算量較大，PSO進(jìn)化后期容易陷入局部最優(yōu)解，而且過度依賴于參數(shù)設(shè)置，這些都會對配送方案的高效性造成影響。

鯨魚算法(Whale Optimization Algorithm,WOA)是模擬鯨魚捕食機(jī)制而設(shè)計的一種新型智能群算法，最初由Mirjalili于2016年提出[6-7]，其優(yōu)點在于搜索機(jī)制簡單，能夠大大減少算法計算量，加快算法收斂速度；控制參數(shù)少，且參數(shù)設(shè)置情況不會對算法最終求解結(jié)果造成過大影響。其缺點在于，由于尋優(yōu)機(jī)制簡單，導(dǎo)致算法在處理一些規(guī)模較大的非線性優(yōu)化問題時容易陷入局部最優(yōu)解。

基于上述分析，本文對長江經(jīng)濟(jì)帶物流配送問題的求解算法進(jìn)行研究。在標(biāo)準(zhǔn)WOA中分別引入混沌機(jī)制、自適應(yīng)慣性權(quán)重、蛙跳算法和模擬退火算法，提出了求解配送問題的IWOA，并利用長江經(jīng)濟(jì)帶企業(yè)配送實例和國際標(biāo)準(zhǔn)算例對算法求解性能進(jìn)行驗證，為改善配送方案提供了新的思路。

1 長江經(jīng)濟(jì)帶配送問題的數(shù)學(xué)模型

長江經(jīng)濟(jì)帶配送問題可以描述為[8]：已知位于長江經(jīng)濟(jì)帶的物流公司位置、配送車輛載重量、客戶位置及需求量，需要在滿足以下假設(shè)條件的情況下，合理安排配送線路使總體配送成本最小。

假設(shè)1：每個客戶都有且只有一輛車輛進(jìn)行配送。

假設(shè)2：每輛車輛均不能超載。

假設(shè)3：車輛油耗與車輛載重成正比。

假設(shè)4：物流公司擁有足夠的同類型配送車輛。

pi=qi/Q

(1)

式中：qi表示車輛第i段運輸路徑上的實際載重；Q表示車輛最大載重；式(1)為車輛在第i段運輸路徑上的實載率。

(2)

式中：e1表示車輛空載情況下行駛單位距離的油耗成本；e2表示車輛滿載情況下行駛單位距離的油耗成本。式(2)為第i段運輸路徑上車輛行駛單位距離的油耗成本。

C=si[e1+pi(e2-e1)]

(3)

式中：si表示運輸距離。式(3)為車輛的總油耗成本。

根據(jù)車輛載重量和企業(yè)需求量可以預(yù)先估計為：

(4)

式中：m表示完成配送任務(wù)需要車輛數(shù)；[]表示取整函數(shù)；n表示客戶數(shù)量；gi表示客戶i的需求量；?表示車輛裝載系數(shù)，與裝車復(fù)雜程度和車輛約束條件有關(guān)。

根據(jù)企業(yè)配送實際情況，構(gòu)建以車輛固定使用成本和油耗成本最小為優(yōu)化目標(biāo)的車輛調(diào)度模型，設(shè)決策變量為：

則有：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

xijk(xijk-1)=0

(12)

yik(yik-1)=0

(13)

X=(xijkr)∈S

(14)

式中：0表示物流公司；F表示車輛固定使用成本；sij表示客戶i到j(luò)的距離；pijk表示車輛k從客戶i到j(luò)的載重率；S表示支路消去約束集合。

式(5)表示總體配送成本最小的目標(biāo)函數(shù)；式(6)表示車輛k從客戶i到j(luò)的載重率；式(7)表示車輛載重約束；式(8)表示每個客戶由且只由一輛車配送；式(9)配送中心約束；式(10)和式(11)表示兩個變量之間的關(guān)系；式(12)和式(13)表示0-1變量約束；式(14)表示消除不完整的子路徑集合。

2 標(biāo)準(zhǔn)鯨魚算法

在WOA中，鯨魚按照螺旋方式進(jìn)行捕食，主要包括包圍獵物、螺旋捕獵和隨機(jī)搜索三個階段[9-10]。

2.1 包圍獵物

如式(15)-式(16)所示，鯨魚在捕食時首先會包圍獵物。

D1=|CX*(t)-X(t)|

(15)

X(t+1)=X*(t)-A·D1

(16)

式中：t表示當(dāng)前迭代次數(shù)；X*(t)表示歷史最優(yōu)鯨魚位置向量；X(t)表示當(dāng)前鯨魚位置向量；A、C表示學(xué)習(xí)因子。

A=2α×rand-α

(17)

C=2×rand

(18)

α=2-2×t/T

(19)

式中：rand表示(0,1)之間的隨機(jī)數(shù)；T表示最大迭代次數(shù)；α表示[0,2]之間線性下降的控制參數(shù)。

2.2 螺旋捕獵

鯨魚包圍獵物后，通常以螺旋方式進(jìn)行捕食，對應(yīng)數(shù)學(xué)模型為：

X(t+1)=X*(t)+D2·eb·rand′·cos(2π·rand′)

(20)

D2=|X*(t)-X(t)|

(21)

式中：D2表示鯨魚和獵物之間的距離；b表示螺線形狀的常數(shù)；rand′表示(-1,1)之間的隨機(jī)數(shù)。實際上，鯨魚螺旋捕獵的同時，還在不斷縮小包圍圈，兩者是一個同步行為。如式(22)所示，假設(shè)有pi的概率選擇縮小包圍圈，則選擇螺旋捕獵的概率則為1-pi，通常取pi=0.5。

(22)

分析可知，鯨魚越靠近獵物，α的值就越小，A也就隨之減小。由于α從2到0線性下降，所以A取值在[-α,α]之間。當(dāng)A在[-1,1]之間時，鯨魚下一個位置可以是它現(xiàn)在位置和獵物位置之間的任意位置。

2.3 搜索獵物

如式(23)-式(24)所示，標(biāo)準(zhǔn)WOA中，鯨魚通過隨機(jī)個體來搜索獵物：

D3=|CXrand-X(t)|

(23)

X(t+1)=Xrand-A·D3

(24)

式中：Xrand表示隨機(jī)生成的位置向量。為增強(qiáng)算法全局尋優(yōu)能力，當(dāng)A≥1時，算法將隨機(jī)搜索一個鯨魚個體，并通過該個體更新其他鯨魚位置，從而使算法跳出當(dāng)前獵物，尋找更加優(yōu)秀的獵物。

3 改進(jìn)鯨魚算法在長江經(jīng)濟(jì)帶配送問題中的應(yīng)用

3.1 構(gòu)造解向量

對m輛車配送n個客戶的路徑優(yōu)化問題，用m+n-1維實數(shù)向量X=(x1,x2,…,xm+n-1)表示鯨魚個體，具體解碼方式如下：

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

為方便算法編程，本文將車輛不能超載的約束條件整合到路徑最短的目標(biāo)函數(shù)中，得到算法適應(yīng)度函數(shù)為：

(25)

式中：M表示非常大的正實數(shù)。分析可知，如果有任一配送車輛超載，則適應(yīng)度函數(shù)值會變得很大，在算法進(jìn)化過程中自然會被淘汰。

3.3 引入混沌機(jī)制

根據(jù)文獻(xiàn)[11]可知，初始種群質(zhì)量直接影響算法收斂速度和最終求解精度。標(biāo)準(zhǔn)WOA通過隨機(jī)方式生成初始種群，不能保證鯨魚個體在解空間均勻分布，對算法求解性能造成一定影響。對此，本文采取Logistic混沌映射隨機(jī)生成初始鯨魚個體，提高算法初始種群隨機(jī)性和遍歷性，具體公式如下所示：

Xn+1=μXn(1-Xn)n=0,1,2… 0≤μ≤4

(26)

3.4 引入自適應(yīng)慣性權(quán)重

根據(jù)文獻(xiàn)[12]可知，較大的慣性權(quán)重有利于提高算法全局搜索能力，較小的慣性權(quán)重有利于增強(qiáng)算法局部搜索能力。理想的慣性權(quán)重應(yīng)該隨著算法進(jìn)化由大變小，這樣就能夠較好地平衡算法全局探索和局部開采能力。標(biāo)準(zhǔn)WOA中，慣性權(quán)重始終為1，一定程度降低了算法效率。因此，本文引入自適應(yīng)慣性權(quán)重ω如下：

(27)

式中：f(X)表示鯨魚X的適應(yīng)度值；f(X*(1))表示第1次迭代中最優(yōu)鯨魚個體適應(yīng)度值。改進(jìn)后的鯨魚個體更新公式為：

(28)

3.5 引入蛙跳算法

蛙跳算法是Eusuff和Lansey模擬青蛙覓食過程而提出的一種智能亞啟發(fā)式算法[13-14]，引入到標(biāo)準(zhǔn)WOA中能夠有效增強(qiáng)算法局部尋優(yōu)能力。核心思想在于，將鯨魚種群隨機(jī)分成L個子群，各子群個體根據(jù)式(29)-式(31)進(jìn)行局部搜索，直到達(dá)到子群最大迭代代數(shù)為止。然后，所有子群重新融合。

Step=rand×(Xbl-Xwl)

(29)

Xwl_new=Xwl+Step

(30)

-Smax

(31)

式中：Xbl、Xwl分別表示第l個子群中的最優(yōu)和最差鯨魚個體；Step表示鯨魚局部搜索半徑；Smax表示鯨魚最大跳動步長。局部搜索后，如果f(Xwl_new)

3.6 引入模擬退火算法

模擬退火算法是Metropolis根據(jù)固體退火降溫機(jī)制而設(shè)計的一種隨機(jī)尋優(yōu)算法，最大特征在于能夠以一定概率接受劣質(zhì)解，進(jìn)而幫助算法跳出局部最優(yōu)解，提高全局尋優(yōu)能力[15]。所以，本文在標(biāo)準(zhǔn)WOA中針對性引入模擬退火思想，以進(jìn)一步提高WOA的全局搜索能力。

根據(jù)Metropolis準(zhǔn)則，當(dāng)物體溫度為Γ時，物體達(dá)到平衡的概率為exp(-ΔE/KΓ)。其中：E表示物體內(nèi)能，ΔE表示內(nèi)能變化量，K表示玻爾茲曼常數(shù)。根據(jù)WOA特點，本文將鯨魚個體達(dá)到平衡的概率設(shè)置為：

(32)

式中：f(X(t))表示第t次迭代中鯨魚個體的適應(yīng)度值；Γ表示第t次迭代的溫度，初始溫度為初始鯨魚種群最大適應(yīng)度值與最小適應(yīng)度值之差。當(dāng)f(X(t+1))θ，則接受X(t+1)，反之則拒絕X(t+1)。

3.7 改進(jìn)鯨魚算法在長江經(jīng)濟(jì)帶配送問題中的實現(xiàn)步驟

根據(jù)前文所述，IWOA求解長江經(jīng)濟(jì)帶配送問題的流程如下：

設(shè)置種群規(guī)模N、最大迭代次數(shù)T、子群最大迭代次數(shù)T1、最大跳動步長Smax等參數(shù);

隨機(jī)生成一個(0,1)之間的n+m-1維鯨魚個體，并根據(jù)式(26)和式(27)生成其他N-1個個體，組成初始鯨魚種群{X1,X2,…，Xi,…,XN}；

根據(jù)式(25)計算種群所有個體適應(yīng)度值，將種群最優(yōu)個體記為歷史最優(yōu)個體，同時記錄模擬退火算法初始溫度；

while(t

fori=1 toN

根據(jù)式(17)至式(19)計算A的值。

如果A≥1，根據(jù)式(23)和式(24)更新個體i位置；否則，根據(jù)式(15)、式(21)、式(27)和式(28)更新個體i位置；

end for

將鯨魚種群隨機(jī)劃分為規(guī)模相同的L個子群體；

forl=1 toL

forq=1 toT1

選出第l個子群的最優(yōu)個體Xbl和最差個體Xwl；

根據(jù)式(29)-式(31)計算得到Xwl_new；如果f(Xwl_new)

end for

end for

將所有子群融合；

fori=1 toN

end for

按照Γ=0.99Γ進(jìn)行退溫操作；

計算種群所有個體適應(yīng)度值，對比種群最優(yōu)和歷史最優(yōu)個體適應(yīng)度值，擇優(yōu)更新歷史最優(yōu)個體位置。

t=t+1

end while

輸出歷史最優(yōu)個體，即為最優(yōu)調(diào)度方案。

4 實例分析

為驗證IWOA性能，本文分別采用長江經(jīng)濟(jì)帶企業(yè)配送實例和國際標(biāo)準(zhǔn)算例進(jìn)行仿真測試。IWOA參數(shù)為：種群規(guī)模N=100、最大迭代次數(shù)T=60、子群個數(shù)L=5、子群最大迭代次數(shù)T1=20、最大跳動步長Smax=1。WOA、GA和PSO參數(shù)按相應(yīng)文獻(xiàn)設(shè)置。

4.1 長江經(jīng)濟(jì)帶企業(yè)配送實例

已知位于張家界的物流公司(經(jīng)度110.550 42°，緯度29.345 89°)要向長江經(jīng)濟(jì)帶其他30個城市進(jìn)行配送服務(wù)，各城市地理位置和需求量如表1所示。配送車輛為最大載重180 t的大型掛車，固定使用費用為F=1 230元/次，空載情況下行駛單位距離油耗成本為e1=0.56元/(km·t)，滿載情況下行駛單位距離油耗成本為e2=1.58元/(km·t)。

表1 長江經(jīng)濟(jì)帶配送網(wǎng)絡(luò)

利用IWOA對上述實例進(jìn)行50次求解，最終配送方案如表2所示。

表2 IWOA最終配送方案

由表2可知，完成配送任務(wù)需要8輛車，其中車輛1為長沙市、贛州市和衡陽市3個城市服務(wù)；車輛2為武漢市、合肥市、宿遷市和亳州市4個城市服務(wù)；車輛3為安慶市、南通市、杭州市、臺州市、上饒市和撫州市6個城市服務(wù)；車輛4為涼山州、麗江市和昆明市3個城市服務(wù)；車輛5為阿壩州、成都市和自貢市3個城市服務(wù)；車輛6為文山州、西雙版納、保山市和六盤水4個城市服務(wù)；車輛7為懷化市、遵義市和昭通市3個城市服務(wù)；車輛8為廣安市、巴中市、十堰市和荊門市4個城市服務(wù)。所有車輛均從張家界物流公司出發(fā)，配送完成后全部返回物流公司，整體配送成本為7.91萬元。

為對比驗證IWOA求解性能，分別采用WOA[10]、GA[3]和PSO[4]對上述實例進(jìn)行50次求解，求得最終配送方案如表3、表4和表5所示。分析可知，WOA、GA和PSO均需要8輛車才能完成配送任務(wù)，最終配送成本分別為11.01萬元、10.87萬元和11.22萬元，均大于IWOA求解結(jié)果。如圖1所示，IWOA在第27代時收斂，WOA在第45代收斂，PSO在第32代時收斂，而GA在第40代時收斂。由此可知，WOA全局尋優(yōu)能力優(yōu)于PSO，但也非常容易陷入局部最優(yōu)解，且收斂速度慢于GA和PSO。經(jīng)過本文改進(jìn)后，IWOA全局尋優(yōu)能力和收斂速度全面提升，均優(yōu)于PSO和GA。

表3 WOA最終配送方案

表4 GA算法最終配送方案

表5 PSO算法最終配送方案

續(xù)表5

圖1 各算法收斂對比圖

統(tǒng)計各算法50次求解的最終解(FS)、平均值(AS)、平均收斂代數(shù)(AD)和標(biāo)準(zhǔn)差(SD)等指標(biāo)如表6所示。

表6 各算法求解結(jié)果對比 (單位：萬元)

根據(jù)表6，IWOA的平均值和標(biāo)準(zhǔn)差最小，分別為8.52萬元和2.36萬元；GA次之，分別為13.43萬元和6.24萬元；WOA較大，分別為14.98萬元和6.58萬元；PSO最大，取值為15.27萬元和6.75萬元。由此可知，WOA穩(wěn)定性優(yōu)于PSO但弱于GA。經(jīng)過本文改進(jìn)，IWOA穩(wěn)定性有效提升，依次優(yōu)于GA、WOA和PSO算法。

4.2 標(biāo)準(zhǔn)算例

為進(jìn)一步驗證IWOA的求解性能，分別利用IWOA、WOA、GA和PSO對VRP國際標(biāo)準(zhǔn)算例進(jìn)行50次求解，統(tǒng)計求得最終解(FS)、平均值(AS)和平均運行時間(AT)如表7所示，IWOA求得最終配送方案如表8所示。

表7 各算法標(biāo)準(zhǔn)算例仿真結(jié)果

表8 IWOA最終配送方案

如表7所示，IWOA能夠求得小規(guī)模算例A-n37-k5最優(yōu)解，更新算例B-n31-k5最優(yōu)解，且求得最終解與大規(guī)模算例A-n63-k10、B-n66-k9最優(yōu)解相差僅為1.4%和1.1%，而GA、WOA和PSO不能求得任一算例最優(yōu)解。IWOA平均運行時間最短，PSO和GA次之，而WOA運行最慢。同時，IWOA求得平均值最小，GA和WOA次之，而PSO求得平均值最大。

綜上分析可知，WOA全局尋優(yōu)能力和穩(wěn)定性優(yōu)于PSO、弱于GA，且收斂速度最慢。但經(jīng)過本文改進(jìn)后，IWOA在全局尋優(yōu)能力、收斂速度和穩(wěn)定性方面大幅度提升，明顯優(yōu)于WOA、GA和PSO。所以，雖然IWOA在參數(shù)設(shè)置難度上有所增加，但卻能夠大幅提高算法求解性能，進(jìn)而大規(guī)模降低企業(yè)配送成本，這對于以利潤最大化為追求的企業(yè)來說顯然是值得的。

5 結(jié) 語

本文主要對長江經(jīng)濟(jì)帶配送問題的求解算法進(jìn)行了研究。針對標(biāo)準(zhǔn)WOA容易陷入局部最優(yōu)解的問題，本文首先采用混沌機(jī)制生成WOA初始種群，然后先后引入自適應(yīng)慣性權(quán)重、蛙跳算法和模擬退火算法對WOA進(jìn)行改進(jìn)，進(jìn)而提出了求解長江經(jīng)濟(jì)帶配送問題的IWOA。基于長江經(jīng)濟(jì)帶配送實例和國際標(biāo)準(zhǔn)算例的仿真實驗表明，改進(jìn)后的IWOA求解性能優(yōu)于標(biāo)準(zhǔn)WOA、GA和PSO，為長江經(jīng)濟(jì)帶配送問題的求解提供了一種新思路。