陳榮 王雯陽(yáng) 卞東東

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

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

中圖分類號(hào)：U116.2??? 文獻(xiàn)標(biāo)識(shí)碼：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? 引? 言

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

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

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

1? 問(wèn)題描述

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

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

2.1? 基本假設(shè)

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

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

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

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

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

2.2? 參數(shù)設(shè)置和符號(hào)說(shuō)明

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

ct=

ca-t表示車輛早于供應(yīng)商時(shí)間窗要求的罰款成本，ct-b表示車輛晚于供應(yīng)商時(shí)間窗要求的罰款成本，在供應(yīng)商規(guī)定時(shí)間窗內(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)取貨的物流成本，第一項(xiàng)表示車輛的固定啟動(dòng)成本，第二項(xiàng)表示車輛的運(yùn)輸成本，第三項(xiàng)表示取貨車輛違反供應(yīng)商時(shí)間窗要求的懲罰成本;式（2）表示在一次循環(huán)取貨中，車輛k最多只能從某取貨點(diǎn)發(fā)出一次;式（3）表示在一次循環(huán)取貨中，車輛k最多只能到達(dá)某取貨點(diǎn)一次;式（4）表示子回路消除約束，該約束保證了兩個(gè)供應(yīng)商之間只有一條路徑;式（5）閉環(huán)約束：表示所有的車輛都是從物流中心發(fā)出，完成任務(wù)后再回到物流中心;式（6）車載容量約束：指每輛車的載貨量不超過(guò)車輛的最大裝載容量;式（7）時(shí)間窗約束：表示車輛從上一個(gè)供應(yīng)商取貨到訪問(wèn)下一個(gè)供應(yīng)商需滿足的時(shí)間約束;式（8）變量的非負(fù)約束。

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

3.1? WOA算法基本原理

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

3.2? WOA的改進(jìn)

3.2.1? 變螺旋更新位置

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

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

其中：b=e。

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

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

p=exp

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

3.3? 改進(jìn)WOA算法的求解步驟

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

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

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

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

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

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

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

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

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

4? 實(shí)例分析

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

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

4.2? 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5? 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 黃戈文，蔡延光，戚遠(yuǎn)航，等. 自適應(yīng)遺傳灰狼優(yōu)化算法求解帶容量約束的車輛路徑問(wèn)題[J]. 電子學(xué)報(bào)，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] 孫滬增，李章維，秦子豪，等. 帶時(shí)間窗車輛路徑規(guī)劃算法研究與實(shí)現(xiàn)[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2020，41（5）：972-978.

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

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

[6] 魏小迪，鄭洪清. 求解帶時(shí)間窗車輛路徑問(wèn)題的改進(jìn)離散花朵授粉算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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] 劉磊，白克強(qiáng)，但志宏，等. 一種全局搜索策略的鯨魚(yú)優(yōu)化算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2020，41（9）：1820-1825.

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