基于鯨魚算法的循環(huán)取貨路徑優(yōu)化研究

陳榮 王雯陽 卞東東

摘? 要：針對汽車零部件入場物流循環(huán)取貨路徑優(yōu)化的問題，考慮車載容量和時間窗等約束條件，構(gòu)建最小化物流成本的數(shù)學(xué)模型。首先，在鯨魚優(yōu)化算法的基礎(chǔ)上引入自適應(yīng)權(quán)重，提升算法尋優(yōu)速度;其次，利用變螺旋方式更新位置，提高算法全局搜索能力;最后結(jié)合模擬退火算法，改善算法的早熟現(xiàn)象有助于實現(xiàn)全局最優(yōu)。通過A企業(yè)入場物流數(shù)據(jù)進行仿真實驗，改進后的算法不僅減少了車輛數(shù)目還降低了總物流成本，可知改進后的鯨魚算法求解路徑問題時可以提供更優(yōu)化的方案。

關(guān)鍵詞：車載容量;軟時間窗;路徑優(yōu)化;改進鯨魚算法

中圖分類號：U116.2??? 文獻標(biāo)識碼：A

Abstract： Aiming at the problem of the optimization of the entry logistics cycle pick-up route for automobile parts， a mathematical model was built to minimize the logistics cost considering the constraints of vehicle capacity and time window. Firstly， introduce adaptive weights on the basis of the whale optimization algorithm to improve the algorithm optimization speed. Secondly， use the variable spiral method to update the position and improve the algorithm's global search ability. Finally， combined with the simulated annealing algorithm， improving the premature phenomenon of the algorithm is helpful to achieve globally optimal. Through the simulation experiment of A enterprise's entry logistics data， the improved algorithm not only reduces the number of vehicles but also reduces the total logistics cost. It can be seen that the improved whale optimization algorithm can provide a more optimal solution when solving the routing problem.

Key words： vehicle capacity; soft time window; path optimization; improved whale algorithm

0? 引? 言

近年來，隨著全球汽車制造企業(yè)的快速發(fā)展，汽車零部件入場物流逐漸成為汽車制造企業(yè)降本增效的重要環(huán)節(jié)。借鑒國內(nèi)外先進汽車制造企業(yè)的經(jīng)驗，通過循環(huán)取貨的方式可以有效地降低零部件入場物流的費用。現(xiàn)如今國內(nèi)外學(xué)者對于循環(huán)取貨的路線設(shè)計優(yōu)化主要側(cè)重于研究帶有車載容量限制的車輛路徑問題以及考慮時間窗的車輛路徑優(yōu)化問題，而本文綜合考慮車載容量和時間窗約束，使問題更貼近實際。

車輛路徑問題（VRP）最早由Dantizg于1959年提出，其基礎(chǔ)是考慮車載容量的車輛路徑問題（CVRP）;黃戈文等[1]針對CVRP，通過灰狼空間整數(shù)編碼以及先路由后分組的策略對灰狼優(yōu)化算法進行優(yōu)化并求解問題。Xiao-Fang Ji等[2]設(shè)計了一種自適應(yīng)貓群優(yōu)化（ACSO）的新型混合算法解決貨物取貨中的車輛路徑問題?？紤]時間窗的車輛路徑優(yōu)化問題（VRPTW）是在傳統(tǒng)的車輛路徑問題上增加了時間窗約束，孫滬增等[3]利用改進的蟻群算法進行求解VRPTW，并通過GIS物流取貨實例進行驗證;文展等[4]提出一種改進的基于集合的粒子群優(yōu)化算法求解VRPTW。李珺等[5]提出細菌覓食優(yōu)化算法與大鄰域搜索算法相結(jié)合的混合算法求解VRPTW;魏小迪等[6]針對花朵授粉算法的局限性進行改進求解VRPTW;Shuai Zhang等[7]設(shè)計了一種基于模糊仿真方法的ALNS算法對VRPTW進行求解。

隨著群智能優(yōu)化算法的發(fā)展，越來越多的算法被用來解決復(fù)雜的優(yōu)化問題。例如2016年Mirjalili等[8]提出的鯨魚優(yōu)化算法（WOA），它已被用于優(yōu)化各個領(lǐng)域。劉磊等[9]提出引入最優(yōu)鄰域擾動策略提高鯨魚優(yōu)化算法處理最優(yōu)問題時的全局搜索能力;蔡雨岑等[10]針對地面無人車路徑規(guī)劃的問題，利用和聲搜索策略和動態(tài)平衡策略相結(jié)合的平衡鯨魚優(yōu)化算法進行求解。然而目前文獻中未發(fā)現(xiàn)將鯨魚優(yōu)化算法用于循環(huán)取貨車輛路徑優(yōu)化問題中，因此本文采用控制參數(shù)少且易于實現(xiàn)的鯨魚優(yōu)化算法進行求解。

1? 問題描述

已知在一個循環(huán)取貨物流系統(tǒng)中，零部件制造商作為供應(yīng)方，A汽車制造企業(yè)作為零部件需求方，A企業(yè)委托第三方物流中心C公司進行零部件的取貨。在循環(huán)取貨流程中，第三方物流中心按照零部件需求訂單派遣車輛裝載空器具從物流中心出發(fā)，按照規(guī)定的時間窗、路線和需求訂單，前往各個零部件供應(yīng)商取貨，到達供應(yīng)商處后合理的安排空器具的卸載與零部件的裝載，完成取貨任務(wù)后返回物流中心。

2? 數(shù)學(xué)建模

2.1? 基本假設(shè)

本文針對循環(huán)取貨的數(shù)學(xué)模型，提出如下假設(shè)：

（1）物流中心與各個供應(yīng)商的距離已知，且各個供應(yīng)商之間的距離已知;

（2）各個供應(yīng)商的待取零部件體積均不超過車輛的最大裝載能力;

（3）車輛的固定成本已知，運輸成本與行駛距離成正比;

（4）不管車輛故障、交通堵塞、天氣等不可控因素，所有車輛都保持勻速行駛。

2.2? 參數(shù)設(shè)置和符號說明

其中：基于軟時間窗定義時間懲罰函數(shù)ct的具體表達式如下：

ct=

ca-t表示車輛早于供應(yīng)商時間窗要求的罰款成本，ct-b表示車輛晚于供應(yīng)商時間窗要求的罰款成本，在供應(yīng)商規(guī)定時間窗內(nèi)服務(wù)懲罰成本為零。

2.3? 數(shù)學(xué)模型

基于上述分析，本文的數(shù)學(xué)模型描述如下：

MinW=xf+xdC+cmaxa-t， 0+cmaxt-b， 0??????????????? （1）

s.t.

x=y， ？坌j∈V， ？坌k∈K?????????????????? ?????????????????????????????（2）

x=y， ？坌i∈V， ？坌k∈K??????????????????????????????????????????????? （3）

x≤S-1， ？坌k∈K， S≥2???????????????????????????????????????? （4）

x=x， ？坌k∈K??????????????????????????????????????????????????? （5）

yq≤Q， ？坌k∈K????????????????????????????????????????????????????? （6）

t+u+t≤t+M1-x， ？坌i， j∈V， ？坌k∈K????????????????????????????????? （7）

Q， q， u>0， i∈V， k∈K????????????????????????????????????????????????? （8）

約束條件：

目標(biāo)函數(shù)式（1）表示最小化循環(huán)取貨的物流成本，第一項表示車輛的固定啟動成本，第二項表示車輛的運輸成本，第三項表示取貨車輛違反供應(yīng)商時間窗要求的懲罰成本;式（2）表示在一次循環(huán)取貨中，車輛k最多只能從某取貨點發(fā)出一次;式（3）表示在一次循環(huán)取貨中，車輛k最多只能到達某取貨點一次;式（4）表示子回路消除約束，該約束保證了兩個供應(yīng)商之間只有一條路徑;式（5）閉環(huán)約束：表示所有的車輛都是從物流中心發(fā)出，完成任務(wù)后再回到物流中心;式（6）車載容量約束：指每輛車的載貨量不超過車輛的最大裝載容量;式（7）時間窗約束：表示車輛從上一個供應(yīng)商取貨到訪問下一個供應(yīng)商需滿足的時間約束;式（8）變量的非負約束。

3? 改進的WOA算法設(shè)計

3.1? WOA算法基本原理

WOA是2016年由Mirjalili提出的一種基于座頭鯨魚群體狩獵行為的新型群智能優(yōu)化算法。該算法通過對鯨魚的隨機搜索，氣泡網(wǎng)攻擊以及包圍捕食等行為進行優(yōu)化搜索，從而找到問題的最優(yōu)解。

3.2? WOA的改進

3.2.1? 變螺旋更新位置

WOA中，鯨魚進行螺旋氣泡網(wǎng)捕食時通過參數(shù)b控制螺旋形狀，該參數(shù)設(shè)置為常數(shù)時會導(dǎo)致鯨魚移動位置的方式比較單一。因此將該參數(shù)設(shè)置為隨著迭代次數(shù)變化的變量，從而動態(tài)調(diào)整鯨魚進行氣泡網(wǎng)捕食時的螺旋形狀。則變螺旋更新位置的公式如下：

Xj+1=wj·j+·e·cos2πl(wèi)?????????????????????????????????? （9）

其中：b=e。

3.2.2? 結(jié)合模擬退火算法

模擬退火階段重新定義一個新的初始種群，用于調(diào)整種群鯨魚個體的位置。該階段接受較差解的概率設(shè)置為：

p=exp

其中：fX是新種群中第s個鯨魚個體的適應(yīng)度值，fX-fX是新舊鯨魚個體的適應(yīng)度差值，概率p通過該差值進行調(diào)整。

3.3? 改進WOA算法的求解步驟

（1）初始化算法參數(shù)：鯨魚初始種群的規(guī)模N，問題維數(shù)dim及最大迭代次數(shù)T。

（2）隨機生成鯨魚的初始種群，計算種群的適應(yīng)度值并記錄最優(yōu)個體X，計算模擬退火的初始溫度t。

（3）計算并更新參數(shù)：a、C、A、l、p。

（4）若p<0.5且>1，則種群內(nèi)鯨魚個體按照公式j(luò)+1=wj·j-×更新當(dāng)前位置，否則（即≤1）鯨魚個體根據(jù)公式j(luò)+1=wj·-·更新位置;若p≥0.5，則種群內(nèi)個體依據(jù)公式（9）調(diào)整當(dāng)前位置。

（5）進入到模擬退火階段，重新定義一個新的鯨魚群體，隨機初始化新鯨魚群體的個體位置，計算群體的適應(yīng)度值。

（6）計算并比較更新后的新舊種群的適應(yīng)度值。若新種群個體適應(yīng)值優(yōu)于原種群則進行替代操作;如果新種群個體適應(yīng)度值比原種群低，則利用概率p判斷是否接受新種群中的鯨魚位置。

（7）退火操作：t=0.99*t。

（8）記錄最優(yōu)的鯨魚位置X以及適應(yīng)度值，若j

（9）輸出全局最優(yōu)個體X以及適應(yīng)度值。

4? 實例分析

4.1? 實例數(shù)據(jù)

已知在A汽車制造企業(yè)循環(huán)取貨過程中，第三方物流中心C公司派遣的是飛翼式卡車，該車型的最大裝載容量為61m3，平均速度為50km/h。其中該卡車的固定成本為300元/輛，卡車的單位時間運輸成本為10元/km，提前和延遲到達供應(yīng)商處的懲罰成本分別為20元/h和每小時30元/h。各供應(yīng)商的基本信息如表2所示，各個供應(yīng)商之間的距離如表3所示。

4.2? 實驗結(jié)果分析

針對上述實例使用基本的WOA算法和改進的WOA算法進行求解，實驗結(jié)果如圖1和圖2所示。

基本W(wǎng)OA算法求解的結(jié)果如表4所示。

改進的WOA算法求解的結(jié)果如表5所示。

通過結(jié)果對比發(fā)現(xiàn)，改進的WOA算法不僅減少了物流中心派遣車輛的數(shù)目，使原來9輛車減少到7輛車，載貨率還由原來的65%提升到84%，提高了19%，行駛總距離由2 367km變?yōu)? 889km，減少了20%，物流總成本由3 581元降為2 896元，優(yōu)化了19%。由此可以看出，改進的WOA算法在合理規(guī)劃循環(huán)取貨路徑以及優(yōu)化物流成本方面表現(xiàn)出明顯優(yōu)勢。

5? 結(jié)束語

針對汽車零部件入場物流中循環(huán)取貨路徑優(yōu)化問題，本文以A企業(yè)的汽車零部件入場物流的實際情況為例。以最小化入場物流的總物流費用為目標(biāo)，考慮車載容量和供應(yīng)商的時間窗等因素，建立單目標(biāo)數(shù)學(xué)模型。將WOA算法運用到模型中，首先使用變螺旋更新位置的方式使算法尋優(yōu)方式多樣化，其次結(jié)合模擬退火算法使算法跳出局部最優(yōu)解。通過A企業(yè)的實際數(shù)據(jù)驗證，改進后的WOA算法可以為循環(huán)取貨提供更優(yōu)化的路徑規(guī)劃方案，從而更節(jié)約物流成本。

參考文獻：

[1] 黃戈文，蔡延光，戚遠航，等. 自適應(yīng)遺傳灰狼優(yōu)化算法求解帶容量約束的車輛路徑問題[J]. 電子學(xué)報，2019，47（12）：2602

-2610.

[2]? Xiao-Fang Ji， Jeng-Shyang Pan， Shu-Chuan Chu， et al. Adaptive Cat Swarm Optimization Algorithm and Its Applications in Vehicle Routing Problems[J]. Mathematical Problems in Engineering， 2020，15（26）：1-14.

[3] 孫滬增，李章維，秦子豪，等. 帶時間窗車輛路徑規(guī)劃算法研究與實現(xiàn)[J]. 小型微型計算機系統(tǒng)，2020，41（5）：972-978.

[4] 文展，唐康健，李文藻. 一種改進粒子群優(yōu)化算法在車輛路徑問題的應(yīng)用研究[J]. 重慶郵電大學(xué)學(xué)報（自然科學(xué)版），2020，32（5）：891-897.

[5] 李珺，郝麗艷，何奕濤，等. 改進細菌覓食算法求解帶時間窗的車輛路徑優(yōu)化問題[J]. 計算機工程，2020，59（26）：5-8.

[6] 魏小迪，鄭洪清. 求解帶時間窗車輛路徑問題的改進離散花朵授粉算法[J]. 數(shù)學(xué)的實踐與認識，2020，50（2）：193-200.

[7]? Shuai Zhang， Mingzhou Chen， Wenyu Zhang， et al. Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations[J]. Expert Systems With Applications， 2020，145：113-123.

[8]? Seyedali Mirjalili， Andrew Lewis. The Whale Optimization Algorithm[J]. Advances in Engineering Software， 2016，16（8）：35-95.

[9] 劉磊，白克強，但志宏，等. 一種全局搜索策略的鯨魚優(yōu)化算法[J]. 小型微型計算機系統(tǒng)，2020，41（9）：1820-1825.

[10] 蔡雨岑，杜鵬楨. 基于平衡鯨魚優(yōu)化算法的無人車路徑規(guī)劃[J]. 控制與決策，2020，16（4）：1-9.