基于改進鯨魚算法的黔北地區(qū)農(nóng)產(chǎn)品配送問題研究

史文濤 周林榮

(遵義師范學院管理學院 貴州 遵義 563006)

0 引 言

作為全國脫貧攻堅的主戰(zhàn)場，貴州省扶貧工作一定程度決定著全面建成小康社會的進展和成效[1]。近年來，貴州省狠抓電子商務迅速發(fā)展的機遇，結(jié)合自身生態(tài)環(huán)境和農(nóng)業(yè)生產(chǎn)優(yōu)勢，探索實施了“電子商務+農(nóng)產(chǎn)品”的扶貧模式，取得了良好成效。特別是黔北地區(qū)，農(nóng)產(chǎn)品種類多、產(chǎn)量大，每年都有大批農(nóng)產(chǎn)品銷往全國，有效促進了群眾增收。但隨著農(nóng)產(chǎn)品規(guī)模的持續(xù)增加，物流運輸規(guī)模也飛速增長，企業(yè)物流費用大幅提升，嚴重影響了企業(yè)核心競爭力。

由實踐可知，科學的配送方案有助于降低企業(yè)配送成本[2]。因此，學者們對物流配送問題進行了深入研究，提出了大量優(yōu)化算法。文獻[3-4]分別設計了求解帶時間窗物流配送問題的遺傳算法(GA)和粒子群算法(PSO)。結(jié)果表明，經(jīng)過GA和PSO優(yōu)化的配送方案，產(chǎn)生的運輸成本更低。文獻[5]提出了求解帶能力約束物流配送問題的禁忌搜索算法，同樣取得了較好效果。雖然現(xiàn)有智能算法能夠?qū)ξ锪髋渌蛦栴}進行求解，但如何進一步提高算法性能、更大程度降低企業(yè)配送成本仍然是學者們關(guān)注的重要方向。

鯨魚算法(WOA)是Mirjalili等模擬鯨魚捕食機制于2016年提出的一種新型群體啟發(fā)式智能算法，具有參數(shù)較少、原理簡單等優(yōu)點[6]，廣泛應用于圖形優(yōu)化、連續(xù)函數(shù)求解、參數(shù)訓練等領(lǐng)域。文獻[7-8]通過WOA對預測網(wǎng)絡參數(shù)進行了有效訓練，文獻[9]則根據(jù)多閾值圖像分割的特點提出了一種改進WOA，但WOA同樣存在容易早熟、穩(wěn)定性不強等缺點，嚴重影響了問題求解的質(zhì)量。

基于上述分析，本文主要對求解黔北地區(qū)農(nóng)產(chǎn)品配送問題的改進WOA(IWOA)進行了研究。首先，對WOA編碼和解碼方式進行改進，并通過混沌方式生成初始種群。然后，分別引入反向?qū)W習、信息反饋和自適應權(quán)重等機制，進而提出IWOA。最后，采用黔北地區(qū)配送實例和國際標準算例進行仿真測試。實驗結(jié)果表明，IWOA綜合求解性能較好，有助于降低企業(yè)配送成本。

1 配送成本模型

1.1 問題描述

黔北地區(qū)農(nóng)產(chǎn)品配送問題可以描述為[10]：某個位于黔北地區(qū)的配送中心需要對客戶群體進行農(nóng)產(chǎn)品配送，客戶位置和需求量已知，要求在滿足以下4個條件的前提下科學規(guī)劃配送方案，使整體配送成本最?。?1)所有客戶需求均被滿足，且一個客戶且只有一輛車進行服務；(2)配送車輛不能超載，且必須在客戶規(guī)定時間進行配送，早于或者晚于客戶規(guī)定時間均會產(chǎn)生懲罰成本；(3)配送車輛配送時按照相同速度勻速行駛；(4)配送中心擁有足夠的同類型車輛。

1.2 成本分析

根據(jù)企業(yè)配送實際可知，農(nóng)產(chǎn)品配送成本主要包括車輛運輸成本、農(nóng)產(chǎn)品貨損成本和時間懲罰成本。

(1)車輛運輸成本。車輛運輸成本指運營成本和行駛成本，計算方式為：

(1)

(2)農(nóng)產(chǎn)品貨損成本。實際上，農(nóng)產(chǎn)品容易受溫度、時間的影響產(chǎn)生腐爛，進而產(chǎn)生貨損成本。但由于生鮮農(nóng)產(chǎn)品通常采用冷藏車進行配送，故可以忽略溫度變化的因素，將貨損成本表示為：

(2)

(3)時間懲罰成本。時間窗包括硬時間窗和軟時間窗，前者不允許車輛在規(guī)定時間范圍外配送，后者則允許車輛在規(guī)定時間范圍外配送，但需要支付一定懲罰成本，且距離規(guī)定時間越久懲罰成本越高。根據(jù)企業(yè)實際情況，配送要求多為軟時間窗，懲罰成本函數(shù)如下：

(3)

圖1 時間窗懲罰成本示意圖

1.3 模型構(gòu)建

(4)

約束條件為：

(5)

(6)

(7)

(8)

(9)

(10)

式(5)表示車輛達到客戶j的時間，設t0=0；式(6)和式(7)表示車輛從配送中心出發(fā)，配送完成后又返回配送中心；式(8)和式(9)表示每個客戶且只有一輛車配送；式(10)表示配送車輛不能超載。

2 鯨魚優(yōu)化算法

2.1 包圍獵物

WOA中，設定最優(yōu)解為目標獵物，其他鯨魚個體均通過目標獵物進行自我更新，對應公式為[6]：

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

(11)

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

(12)

式中：D表示鯨魚與獵物相隔距離；t表示當前迭代次數(shù)；X*(t)表示目標獵物位置；X(t)表示鯨魚個體當前位置；A、C為系數(shù)向量。

A=2αr1-α

(13)

C=2r2

(14)

(15)

式中：r1和r2表示[0,1]之間的隨機數(shù)；α表示收斂因子；T表示最大迭代次數(shù)。

2.2 氣泡攻擊

捕食時，鯨魚會發(fā)出氣泡包圍獵物，并同步朝著獵物移動[9]。該過程主要包括收縮包圍和螺旋更新2個機制，收縮包圍如2.1節(jié)所述，螺旋更新鯨魚個體位置的方法如下：

X(t+1)=Deblcos(2πl(wèi))+X*(t)

(16)

式中：b表示常數(shù)；l表示[-1,1]之間的隨機數(shù)。

2.3 尋找獵物

經(jīng)過包圍和氣泡攻擊后，鯨魚個體便可以對包圍圈范圍內(nèi)的獵物進行搜索，公式為：

D=|CXrand(t)-X(t)|

(17)

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

(18)

式中：Xrand(t)表示隨機選取的鯨魚個體。當|A|≥1時，鯨魚個體隨機向遠處搜索，尋找算法全局最優(yōu)解；|A|<1時，鯨魚個體向目標獵物處搜索，尋找算法局部最優(yōu)解。

3 改進鯨魚算法

3.1 編碼與解碼

對鯨魚個體進行解碼時，首先，比較各維向量大小，按從小到大的順序獲取各維向量在個體中的位置數(shù)值。例如，在個體[0.21,0.38,0.13,0.42,0.44,0.36]中，按照從小到大的順序，0.36排列第3，則其位置數(shù)值為3。如圖2所示，當位置數(shù)值大于客戶數(shù)時，令對應數(shù)值為0，且當0相鄰時，刪除多余的0，即可得到配送方案。例如，上述個體[0.21,0.38,0.13,0.42,0.44,0.36]解碼后為[2,0,1,0,3]，則表示該配送方案共需要3輛車，車輛1配送路徑為0-2-0，車輛2配送路徑為0-1-0，車輛3配送路徑為0-3-0。

圖2 鯨魚個體解碼示意圖

3.2 混沌序列初始化

(19)

3.3 逐維小孔成像反向?qū)W習

WOA求解高維度問題時，鯨魚個體各維度之間相互影響較大，容易導致算法陷入局部最優(yōu)解。根據(jù)文獻[12]可知，智能算法和反向?qū)W習有效結(jié)合，能夠提高算法全局尋優(yōu)能力?；谠撍枷?，本文參考光學定律，提出一種逐維小孔成像反向?qū)W習策略，希望通過該策略降低鯨魚個體不同維度的相互干擾，避免算法陷入局部最優(yōu)解，具體原理如圖3所示。

圖3 逐維小孔成像示反向?qū)W習示意圖

(20)

(21)

分析式(21)可知，與傳統(tǒng)逐維反向?qū)W習策略不同，本文提出的逐維小孔成像反向?qū)W習策略通過改變接收屏和小孔屏的距離即可調(diào)整ξ取值，使得算法能夠在更大范圍內(nèi)尋找優(yōu)秀反向解，進而更大程度地提高個體質(zhì)量和多樣性，降低算法陷入局部最優(yōu)解的可能性。當ξ=1時，可得：

(22)

即為一般反向?qū)W習策略。

在WOA的每次迭代中，都采用式(21)對最優(yōu)鯨魚個體進行位置篩選，某一維度的向量經(jīng)過小孔成像反向?qū)W習后與其他維度的向量組成新個體，然后比較不同個體適應度值，進而確定最優(yōu)個體。

3.4 信息反饋機制

WOA中，鯨魚通過更新自身位置來靠近獵物，運動方式比較單一，一定程度上影響了算法收斂速度。對此，本文提出一種信息反饋機制，每次迭代中讓最優(yōu)和最差鯨魚個體進行信息交流，引導距離獵物較遠的個體迅速靠近獵物，進而加快算法收斂。具體公式如下：

(23)

式中:X*、X*分別表示當前種群最優(yōu)和最差個體；ζ表示[0,1]之間均分分布的隨機數(shù)。

3.5 非線性收斂因子和自適應權(quán)重策略

由文獻[6]可知，WOA求解性能也受系數(shù)向量A的影響。分析式(13)，A的取值由收斂因子α決定，α隨著算法進化逐步遞減，且呈現(xiàn)線性趨勢，這在一定程度上影響了算法求解性能。對此，本文提出一種收斂因子非線性變化策略，計算公式如下：

(24)

式中：μ表示控制常數(shù)，本文設置為2。由式(24)可知，收斂因子在保持遞減趨勢的情況下，在算法前期迭代中遞減速率較慢，有效擴大了算法搜索空間；在算法后期迭代中遞減速率較快，有助于加快算法收斂。

同時，為進一步平衡WOA全局尋優(yōu)能力和局部搜索能力，本文提出一種自適應權(quán)重系數(shù)w：

(25)

用w改進鯨魚個體更新公式：

X(t+1)=w(t)·X*(t)-A·D

(26)

X(t+1)=Deblcos(2πl(wèi))+(1-w(t))X*(t)

(27)

X(t+1)=w(t)Xrand(t)-A·D

(28)

由上述公式可知，慣性權(quán)重隨著算法迭代次數(shù)增加而由大到小變化，較好地平衡算法全局和局部尋優(yōu)能力。

3.6 適應度函數(shù)

為便于計算機編程計算，本文將式(10)融入到目標函數(shù)，得到算法適應度函數(shù)如下[13-15]：

(29)

3.7 算法步驟

IWOA求解農(nóng)產(chǎn)品配送問題的步驟主要包括：

步驟1設置初始種群大小Num、最大迭代次數(shù)T等參數(shù)。

步驟4根據(jù)式(13)、式(14)和式(24)更新系數(shù)向量A，根據(jù)式(25)更新自適應權(quán)重因子w。

步驟5生成(0,1)之間的隨機數(shù)rand。如果rand<0.5且|A|<1，則根據(jù)式(11)和式(26)更新鯨魚個體；若rand<0.5且|A|≥1，則根據(jù)式(17)和式(28)更新鯨魚個體；若rand≥0.5，則根據(jù)式(27)更新鯨魚個體。

步驟6根據(jù)式(29)計算鯨魚個體適應度值，選出當代種群最優(yōu)個體X*和最差個體X*。

步驟8根據(jù)式(23)更新種群最差個體X*。

步驟9判斷算法是否達到最大迭代次數(shù)。達到，則輸出最優(yōu)個體X*，即為最優(yōu)調(diào)度方案；反之，則返回步驟4。

具體流程如圖4所示。

圖4 IWOA求解農(nóng)產(chǎn)品配送問題示意圖

4 仿真實驗

為驗證IWOA有效性，以黔北地區(qū)生鮮農(nóng)產(chǎn)品配送實例和國際標準算例為測試數(shù)據(jù)，在Windows 7，Intel i5-6300HQ，4 GB內(nèi)存環(huán)境下，用MATLAB R2016a平臺編程仿真，對比分析WOA[6]、IWOA、GA[3]和PSO[4]的求解結(jié)果。

4.1 黔北地區(qū)配送實例

表1 配送網(wǎng)絡參數(shù)表

利用WOA、IWOA、GA和PSO求解該實例，可得到對應最好配送方案和收斂情況，如圖5和圖6所示?？梢钥闯觯琁WOA求得配送方案需要配送車輛3輛，最好配送成本最低，為1 317.33元，在21代左右收斂；GA需要配送車輛3輛，最好配送成本次之，為1 319.45元，在40代左右收斂；PSO需要配送車輛3輛，最好配送成本較高，為1 330.23元，在35代左右收斂。WOA需要配送車輛4輛，最好配送成本最高，為1 350.39元，在30代左右收斂。由此可見，IWOA全局尋優(yōu)能力和收斂速度均為最優(yōu)。

(a)IWOA

圖6 各算法最好配送方案收斂情況

為進一步對比驗證IWOA求解性能，分別采用上述算法對該實例進行60次求解，統(tǒng)計相關(guān)指標如圖7和圖8所示。分析可知，IWOA最好、最差以及平均配送成本最小，說明IWOA算法全局尋優(yōu)能力最強，且算法最為穩(wěn)定；WOA最好、最差和平均配送成本最大，說明WOA全局尋優(yōu)能力最差，且算法不穩(wěn)定。GA和PSO對應的最好、最差和平均配送成本處于IWOA和WOA之間，說明兩個算法的全局尋優(yōu)能力和穩(wěn)定性居中，且GA優(yōu)于PSO。同時，IWOA平均運行時間最短為7.2 s，WOA(8.2 s)和PSO(8.9 s)次之，GA最長為12.3 s，說明IWOA、WOA、PSO和GA收斂速度依次變慢。

圖7 最好、最差配送成本對比示意圖

圖8 平均配送成本和運行時間對比示意圖

4.2 國際標準算例

為驗證IWOA求解大規(guī)模網(wǎng)絡的性能，以C101、C201、R101、R201、RC108和RC208等6個客戶規(guī)模為100的國際標準算例為測試集，分別采用上述算法進行60次仿真實驗，統(tǒng)計算例已知最優(yōu)解BK、求得最好解BC、平均解AC和平均運行時間AT如表2所示。

表2 國際標準算例仿真結(jié)果對比表

由表2可知，IWOA能夠求得C101和C201算例的已知最優(yōu)解，且對于R101、R201、RC108和RC208算例，IWOA求得最好解明顯優(yōu)于WOA、GA和PSO，說明IWOA全局尋優(yōu)能力最強，求得各算例最好配送方案分別如圖9、圖10和表3所示。同時，IWOA求得各算例平均值和平均運行時間都優(yōu)于其他算法，說明IWOA穩(wěn)定性和收斂速度也是最優(yōu)。這主要得益于混沌序列初始化增加初始鯨魚種群多樣性，逐維小孔成像反向?qū)W習降低最優(yōu)鯨魚個體不同維度的相互干擾，非線性收斂因子和自適應權(quán)重較好地平衡算法全局和局部尋優(yōu)能力，進而提高算法綜合求解性能。

圖9 C101算例最好配送方案示意圖

圖10 C201算例最好配送方案示意圖

表3 國際標準算例最好配送方案表

綜上分析，IWOA求解性能明顯優(yōu)于WOA、GA和PSO，能夠很好地適用于大規(guī)模農(nóng)產(chǎn)品配送問題的求解。

5 結(jié) 語

本文主要對黔北地區(qū)農(nóng)產(chǎn)品配送問題的求解算法進行研究。針對WOA容易早熟、收斂較慢等缺點，首先改進鯨魚個體編碼和解碼方式，然后利用混沌方式生成初始種群，并引入反向?qū)W習、信息反饋和自適應權(quán)重等機制，提出IWOA。對黔北地區(qū)農(nóng)產(chǎn)品配送實例和國際標準算例的仿真實驗表明，與WOA、GA和PSO相比，IWOA能夠更好地規(guī)劃配送方案，有效降低企業(yè)配送成本。