基于改進鯨魚算法的長江經濟帶配送問題研究

朱光福 朱云波

(重慶城市管理職業學院商學院 重慶 401331)

0 引 言

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

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

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

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

1 長江經濟帶配送問題的數學模型

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

假設1：每個客戶都有且只有一輛車輛進行配送。

假設2：每輛車輛均不能超載。

假設3：車輛油耗與車輛載重成正比。

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

pi=qi/Q

(1)

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

(2)

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

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

(3)

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

根據車輛載重量和企業需求量可以預先估計為：

(4)

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

根據企業配送實際情況，構建以車輛固定使用成本和油耗成本最小為優化目標的車輛調度模型，設決策變量為：

則有：

(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的距離；pijk表示車輛k從客戶i到j的載重率；S表示支路消去約束集合。

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

2 標準鯨魚算法

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

2.1 包圍獵物

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

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

(15)

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

(16)

式中：t表示當前迭代次數；X*(t)表示歷史最優鯨魚位置向量；X(t)表示當前鯨魚位置向量；A、C表示學習因子。

A=2α×rand-α

(17)

C=2×rand

(18)

α=2-2×t/T

(19)

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

2.2 螺旋捕獵

鯨魚包圍獵物后，通常以螺旋方式進行捕食，對應數學模型為：

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

(20)

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

(21)

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

(22)

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

2.3 搜索獵物

如式(23)-式(24)所示，標準WOA中，鯨魚通過隨機個體來搜索獵物：

D3=|CXrand-X(t)|

(23)

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

(24)

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

3 改進鯨魚算法在長江經濟帶配送問題中的應用

3.1 構造解向量

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

3.2 構造適應度函數

為方便算法編程，本文將車輛不能超載的約束條件整合到路徑最短的目標函數中，得到算法適應度函數為：

(25)

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

3.3 引入混沌機制

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

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

(26)

3.4 引入自適應慣性權重

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

(27)

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

(28)

3.5 引入蛙跳算法

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

Step=rand×(Xbl-Xwl)

(29)

Xwl_new=Xwl+Step

(30)

-Smax

(31)

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

3.6 引入模擬退火算法

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

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

(32)

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

3.7 改進鯨魚算法在長江經濟帶配送問題中的實現步驟

根據前文所述，IWOA求解長江經濟帶配送問題的流程如下：

設置種群規模N、最大迭代次數T、子群最大迭代次數T1、最大跳動步長Smax等參數;

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

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

while(t

fori=1 toN

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

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

end for

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

forl=1 toL

forq=1 toT1

選出第l個子群的最優個體Xbl和最差個體Xwl；

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

end for

end for

將所有子群融合；

fori=1 toN

end for

按照Γ=0.99Γ進行退溫操作；

計算種群所有個體適應度值，對比種群最優和歷史最優個體適應度值，擇優更新歷史最優個體位置。

t=t+1

end while

輸出歷史最優個體，即為最優調度方案。

4 實例分析

為驗證IWOA性能，本文分別采用長江經濟帶企業配送實例和國際標準算例進行仿真測試。IWOA參數為：種群規模N=100、最大迭代次數T=60、子群個數L=5、子群最大迭代次數T1=20、最大跳動步長Smax=1。WOA、GA和PSO參數按相應文獻設置。

4.1 長江經濟帶企業配送實例

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

表1 長江經濟帶配送網絡

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

表2 IWOA最終配送方案

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

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

表3 WOA最終配送方案

表4 GA算法最終配送方案

表5 PSO算法最終配送方案

續表5

圖1 各算法收斂對比圖

統計各算法50次求解的最終解(FS)、平均值(AS)、平均收斂代數(AD)和標準差(SD)等指標如表6所示。

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

根據表6，IWOA的平均值和標準差最小，分別為8.52萬元和2.36萬元；GA次之，分別為13.43萬元和6.24萬元；WOA較大，分別為14.98萬元和6.58萬元；PSO最大，取值為15.27萬元和6.75萬元。由此可知，WOA穩定性優于PSO但弱于GA。經過本文改進，IWOA穩定性有效提升，依次優于GA、WOA和PSO算法。

4.2 標準算例

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

表7 各算法標準算例仿真結果

表8 IWOA最終配送方案

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

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

5 結 語

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