基于改進(jìn)麻雀搜索算法的冷鏈物流路徑優(yōu)化

馬青宇,邵松帥,劉博旭,孫 哲,龔光富,孫知信*

(1.南京郵電大學(xué) 江蘇省郵政大數(shù)據(jù)技術(shù)與應(yīng)用工程研究中心,江蘇 南京 210023;2.南京郵電大學(xué) 國(guó)家郵政局郵政行業(yè)技術(shù)研發(fā)中心(物聯(lián)網(wǎng)技術(shù)),江蘇 南京 210023;3.安徽郵谷快遞智能科技有限公司,安徽 蕪湖 241300)

0 引 言

近年來(lái),隨著經(jīng)濟(jì)的高速發(fā)展,冷鏈物流的成本和時(shí)效性逐漸成為討論的話題,目前已經(jīng)有學(xué)者對(duì)冷鏈物流的車輛路徑規(guī)劃開展研究[1-3]。冷鏈物流不僅要考慮車輛的行駛路線,還需要充分考慮各個(gè)客戶的服務(wù)時(shí)間窗口,以及車輛的容量、裝載限制等因素,以達(dá)到最優(yōu)化的配送效果。改進(jìn)大規(guī)模車輛路徑規(guī)劃算法不僅能夠提高物流配送的效率,降低物流成本,也能夠提高客戶的滿意度和物流企業(yè)的競(jìng)爭(zhēng)力。

帶時(shí)間窗的城市間冷鏈物流路徑規(guī)劃屬于VRPTW(Vehicle Routing Problem with Time Windows),是在VRP(Vehicle Routing Problem)的基礎(chǔ)上引入每個(gè)城市期望送達(dá)的時(shí)間窗約束得到的,這體現(xiàn)了對(duì)冷鏈物流時(shí)效的高要求。VRPTW是NP-hard問題,求解方法可以分為精確求解算法和啟發(fā)式算法。精確算法主要包括分支定界法[4]、列生成法[5]和動(dòng)態(tài)規(guī)劃算法[6]等。這類算法通過建立數(shù)學(xué)模型可以求得最優(yōu)解,但是其求解所需的時(shí)間會(huì)隨著問題規(guī)模的擴(kuò)大而爆炸性增長(zhǎng)[7]。這限制了精確算法在大規(guī)模問題上的應(yīng)用。啟發(fā)式算法主要包括蟻群算法[8]、遺傳算法[9]、粒子群優(yōu)化算法[10]和禁忌搜索算法[11]等。啟發(fā)式搜索算法的優(yōu)勢(shì)是可以在合理的時(shí)間內(nèi)求出較優(yōu)的解,并且可以通過控制迭代次數(shù)平衡運(yùn)算時(shí)間和運(yùn)算精度?？偟膩?lái)說,求解大規(guī)模VRPTW時(shí),選擇啟發(fā)式算法相較于精確求解算法有著較強(qiáng)的魯棒性與可行性。

麻雀搜索算法是一種新型群智能優(yōu)化算法,與其他具有代表性的算法相比有著較強(qiáng)的收斂速度與收斂精度,但是在求解一些復(fù)雜問題時(shí),會(huì)陷入局部最優(yōu)解,搜索停滯。針對(duì)麻雀搜索算法的不足,一些學(xué)者對(duì)其進(jìn)行了改進(jìn)。易華輝等[12]通過引入Tent混沌映射初始化種群、精英策略和自適應(yīng)周期收斂因子在一定程度上防止算法陷入局部最優(yōu)。嚴(yán)浩洲等[13]通過優(yōu)化發(fā)現(xiàn)者與加入者的移動(dòng)策略和引入柯西-高斯變異有效地提高了算法的收斂精度、穩(wěn)定性和收斂速度。

目前,麻雀搜索算法在車輛路徑規(guī)劃問題,尤其是大規(guī)模VRPTW的應(yīng)用較少,而且其算法本身也存在一些不足。基于此,該文對(duì)麻雀搜索算法進(jìn)行了改進(jìn),并將改進(jìn)算法應(yīng)用于冷鏈物流路徑優(yōu)化問題的求解。

1 帶時(shí)間窗的大規(guī)模城市間冷鏈物流的數(shù)學(xué)模型

1.1 問題描述

該文研究的問題可以具體表述為：有一個(gè)配送中心,多個(gè)城市,每個(gè)城市的位置、冷鏈商品需求,卸貨所需時(shí)間已知,并且每個(gè)城市都有期望送達(dá)的時(shí)間窗,超出時(shí)間窗就要有一定的懲罰成本。每輛冷鏈物流運(yùn)輸車從配送中心出發(fā),依次服務(wù)其所負(fù)責(zé)的城市,最后回到配送中心。在配送的過程中,冷鏈物流運(yùn)輸車服務(wù)城市的總需求量不得超過車輛最大載重量。在滿足上述約束的條件下,合理規(guī)劃每輛冷鏈物流運(yùn)輸車的配送路線,使得運(yùn)輸時(shí)間與懲罰成本的和最小[14]。

1.2 模型假設(shè)

為了簡(jiǎn)化模型,做出如下假設(shè)。

(1)假設(shè)每輛冷鏈物流運(yùn)輸車的型號(hào)載重量、速度一致,最大行駛里程不限。

(2)假設(shè)冷鏈物流運(yùn)輸車在城市間移動(dòng)所需的時(shí)間為城市間的歐幾里得距離。

(3)假設(shè)每個(gè)城市只能由一輛冷鏈物流運(yùn)輸車服務(wù),且只能服務(wù)一次。

(4)假設(shè)每個(gè)城市的時(shí)間窗不存在沖突。

(5)假設(shè)冷鏈物流運(yùn)輸車不存在空閑等待,即總時(shí)間僅由車輛運(yùn)行時(shí)間和卸貨時(shí)間組成。

1.3 符號(hào)說明

模型符號(hào)說明如表1所示。

表1 模型符號(hào)說明

1.4 模型表示

模型的目標(biāo)函數(shù)、約束條件由如下公式表示：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式1和式2表示兩個(gè)參數(shù)的計(jì)算公式;式3表示最小化路徑代價(jià)與時(shí)間窗偏移代價(jià)的和;式4約束了每個(gè)城市只能被服務(wù)一次;式5約束了每輛車攜帶貨物不得超過最大載重;式6表示每個(gè)城市只能被一輛車服務(wù);式7表示表示每輛車的起點(diǎn)和終點(diǎn)都是配送中心(0號(hào)城市);式8表示每輛車除配送中心的路徑是一棵樹(不存在環(huán))。

2 麻雀搜索算法

2.1 標(biāo)準(zhǔn)麻雀搜索算法

麻雀搜索算法(SSA)是一種元啟發(fā)式算法,由Xue等人于2020年提出[15]。該算法通過引入發(fā)現(xiàn)者-加入者模型,模擬了麻雀在自然界覓食與躲避天敵的行為。發(fā)現(xiàn)者是種群中能量值較高(適應(yīng)度較高)的個(gè)體,在種群中引導(dǎo)加入者進(jìn)行搜索。發(fā)現(xiàn)者和加入者中有一部分起到躲避天敵作用的警戒者。

發(fā)現(xiàn)者、加入者和警戒者的行為可以用以下公式表示[16]：

發(fā)現(xiàn)者：

(9)

加入者：

(10)

預(yù)警者：

(11)

式中,t代表當(dāng)前的迭代次數(shù),xi,j代表第i只麻雀第j維的值,iter_max代表最大迭代次數(shù),Q是符合正態(tài)分布的隨機(jī)數(shù),r∈(0,1]代表預(yù)警值,ST∈[0.5,1]代表安全值。x_gworstj代表所有麻雀中適應(yīng)度最差的個(gè)體第j維的值,x_gbestj代表所有麻雀中適應(yīng)度最優(yōu)的個(gè)體第j維的值,x_bestj代表發(fā)現(xiàn)者麻雀中適應(yīng)度最優(yōu)的個(gè)體第j維的值。X是正態(tài)分布隨機(jī)數(shù),且X～N(0,1)。fi代表第i只麻雀的適應(yīng)度,fg_worst和fg_best分別代表所有麻雀中適應(yīng)度最差和最優(yōu)個(gè)體的適應(yīng)度。

2.2 麻雀搜索算法的離散化

麻雀搜索算法針對(duì)的是連續(xù)問題,而VRPTW的解空間是離散的,所以需要將麻雀搜索算法離散化。在文中,連接離散空間與連續(xù)空間的橋梁是浮點(diǎn)數(shù)組的排序序列,離散化的具體過程如下：

假設(shè)一共有10個(gè)城市,3輛冷鏈物流運(yùn)輸車。圖1是利用浮點(diǎn)數(shù)組進(jìn)行離散化的過程。首先隨機(jī)生成12個(gè)隨機(jī)數(shù),計(jì)算出數(shù)組中的排序,其中1～10代表城市編號(hào),11和12是車輛分隔符。分隔符將不同車輛的配送路徑分隔開,這個(gè)序列可以代表生成的路徑。生成的路徑如圖2所示。

圖1 浮點(diǎn)數(shù)組的離散化

圖2 離散化后生成的路徑

2.3 改進(jìn)的麻雀搜索算法

標(biāo)準(zhǔn)麻雀搜索算法在求解VRPTW時(shí)出現(xiàn)了收斂精度不夠,易于陷入局部最優(yōu)解的缺點(diǎn)。該文引入基于維度的鄰域?qū)W習(xí)策略和包含動(dòng)態(tài)因子的發(fā)現(xiàn)者位置更新公式,以提高算法的收斂精度和收斂速度。

2.3.1 基于維度的鄰域?qū)W習(xí)策略

基于維度的鄰域?qū)W習(xí)策略使得麻雀的信息來(lái)源不再拘泥于原有的麻雀層次體系,而是根據(jù)選擇的鄰域劃分,接收多樣化的信息,加強(qiáng)了麻雀之間的信息交流[17]。鄰域的定義如圖3所示。首先隨機(jī)選擇一只麻雀作為中心麻雀的鄰域臨界麻雀,其與中心麻雀的距離記為R,所有與中心麻雀距離小于等于R的麻雀稱為鄰域內(nèi)麻雀,所有與中心麻雀距離大于R的麻雀稱為鄰域外麻雀。

圖3 麻雀的鄰域模型示意圖

通過計(jì)算每個(gè)麻雀的鄰域,選擇鄰域內(nèi)的麻雀進(jìn)行信息交換,提高了子代麻雀信息來(lái)源的多樣性,提高算法的收斂精度。

信息交流的公式如下：

Xi,j=

(12)

式中,Xw,j是被選中麻雀w在j維的值。

2.3.2 包含動(dòng)態(tài)因子的發(fā)現(xiàn)者位置更新公式

發(fā)現(xiàn)者是整個(gè)種群的核心,是領(lǐng)導(dǎo)者。發(fā)現(xiàn)者的位置決定了種群的搜索方向。為了平衡種群的開發(fā)和勘探,該文在發(fā)現(xiàn)者的位置更新公式中引入了動(dòng)態(tài)因子λ：

(13)

文中取lb=0.3,ub=0.7。動(dòng)態(tài)因子的引入使得改進(jìn)的麻雀搜索算法在前期注重于開發(fā),后期注重于勘探,有利于加快收斂速度,提高收斂精度。改進(jìn)后的發(fā)現(xiàn)者位置更新公式為：

(14)

2.3.3 改進(jìn)算法的偽代碼

改進(jìn)麻雀搜索算法的偽代碼如下所示：

Algorithm Improved-SSA

Input：

Max_iter：最大迭代次數(shù);PD：發(fā)現(xiàn)者數(shù)量;SD：預(yù)警者數(shù)量;ST：預(yù)警值;N：麻雀種群數(shù)量

Output：

X_best,f_curve

1.初始化種群

2.while (t

3. 對(duì)種群適應(yīng)度排序,選出最優(yōu)個(gè)體和最差個(gè)體

4. fori=1：PD

5. 使用式14更新發(fā)現(xiàn)者位置

6. fori=(PD+1)：N

7. 使用式10更新加入者位置

8. fori=1：SD

9. 使用式11更新預(yù)警者位置

10. fori=1：N

11. 選擇鄰域邊界麻雀,計(jì)算鄰域半徑R

12. 篩選出鄰域內(nèi)的麻雀,隨機(jī)選擇一只,使用式12進(jìn)行信息交流

13. 如果麻雀在新位置的適應(yīng)度優(yōu)于原位置,則更新麻雀位置,否則位置不變

14.t=t+1

15. end while

16. ReturnX_best,f_curve

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

該文使用23個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)的麻雀搜索算法進(jìn)行測(cè)試,以衡量改進(jìn)算法的搜索能力。同時(shí),使用6個(gè)標(biāo)準(zhǔn)VRPTW數(shù)據(jù)集進(jìn)行測(cè)試,以考察改進(jìn)算法在冷鏈物流路徑優(yōu)化問題的求解效果。

3.1.1 標(biāo)準(zhǔn)測(cè)試函數(shù)

為了驗(yàn)證改進(jìn)SSA算法的有效性,該文使用23個(gè)常用測(cè)試函數(shù)將改進(jìn)SSA與標(biāo)準(zhǔn)SSA,GWO[18],PSO[19],SCA[20],IGWO22F[21],VW-GWO[22],wdGWO24F[21]進(jìn)行比較。23個(gè)測(cè)試函數(shù)取自Mirjalili等所作實(shí)驗(yàn)[18],其中f1～f7是單峰基準(zhǔn)函數(shù),用于測(cè)試算法的開發(fā)能力。f8～f13是多峰基準(zhǔn)函數(shù),用于測(cè)試算法的勘探能力。f14～f23是符合基準(zhǔn)函數(shù),用于測(cè)試算法開發(fā)與勘探的平衡能力。為確保公平,該文對(duì)每種算法的參數(shù)統(tǒng)一設(shè)定：種群數(shù)量N=50,最大迭代次數(shù)Max_iter=500。

該文對(duì)23個(gè)測(cè)試函數(shù)分別進(jìn)行30次獨(dú)立重復(fù)實(shí)驗(yàn),所得每個(gè)算法在每個(gè)測(cè)試函數(shù)上的平均值和方差如表2所示。實(shí)驗(yàn)結(jié)果表明,改進(jìn)的SSA算法在15個(gè)測(cè)試函數(shù)上,求解的平均值排名第一,占比65%,求解結(jié)果也有較強(qiáng)的穩(wěn)定性。特別是在f21～f23這種復(fù)雜函數(shù)上,改進(jìn)的SSA算法有著絕對(duì)優(yōu)勢(shì)?？偟膩?lái)說,改進(jìn)的SSA算法相較于標(biāo)準(zhǔn)SSA算法和其他元啟發(fā)式算法有較強(qiáng)的競(jìng)爭(zhēng)力,驗(yàn)證了改進(jìn)的有效性。

表2 30次獨(dú)立重復(fù)實(shí)驗(yàn)所得結(jié)果的平均值和方差

3.1.2 標(biāo)準(zhǔn)VRPTW數(shù)據(jù)集

該文選取了6組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對(duì)比,分別是C101[23],RC2_2_2[24],RC1_4_1[25],R1_6_2[25],R1_8_1[25],R1_10_1[25]。每個(gè)數(shù)據(jù)集包括城市坐標(biāo)、貨物需求量、送達(dá)時(shí)間窗、卸貨時(shí)間。

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

該文的評(píng)價(jià)指標(biāo)是所有車輛的運(yùn)行時(shí)間、卸貨時(shí)間與超出時(shí)間窗的懲罰成本之和。

采用Matlab2022b對(duì)改進(jìn)后的麻雀搜索算法進(jìn)行對(duì)比,使用6個(gè)測(cè)試數(shù)據(jù)集對(duì)算法的性能進(jìn)行評(píng)估,為了方便比較,圖4是改進(jìn)的SSA算法與標(biāo)準(zhǔn)SSA算法在其中2個(gè)測(cè)試數(shù)據(jù)集(RC2_2_2,R1_6_2)上的適應(yīng)度迭代曲線。從圖中可以看出,改進(jìn)后的SSA算法在迭代前期有較大的收斂速度,在迭代后期的收斂精度也有較大的優(yōu)勢(shì)。

圖4 改進(jìn)SSA與標(biāo)準(zhǔn)SSA迭代曲線對(duì)比

(1)收斂分析。

如圖4所示,標(biāo)準(zhǔn)SSA算法在前期的收斂速度不理想,并且后期容易陷入局部最優(yōu),導(dǎo)致搜索停滯。改進(jìn)后的SSA算法不僅在前期的收斂速度十分出色,在后期也有一定的概率突破局部最優(yōu)解。相較于其他典型算法,改進(jìn)后的SSA算法也有收斂速度快、收斂精度高的特點(diǎn)。由實(shí)驗(yàn)結(jié)果可以看出,該文提出的改進(jìn)策略可以有效提高算法的收斂速度和收斂精度。

(2)穩(wěn)定性分析。

為了進(jìn)一步評(píng)估改進(jìn)的SSA算法,對(duì)兩種算法在6個(gè)測(cè)試數(shù)據(jù)集上分別進(jìn)行30次獨(dú)立重復(fù)實(shí)驗(yàn),每次獨(dú)立重復(fù)實(shí)驗(yàn)取迭代次數(shù)為300。所得平均值與方差如表3所示。從表中數(shù)據(jù)可以看出,在75%的數(shù)據(jù)集上改進(jìn)的SSA算法求解結(jié)果的平均值為最優(yōu),體現(xiàn)出較強(qiáng)的搜索性能。但是在求解結(jié)果的穩(wěn)定性方面還有一定的改進(jìn)空間。

表3 經(jīng)過30次獨(dú)立測(cè)試所得最優(yōu)解適應(yīng)度的平均值與方差

為便于可視化展示算法規(guī)劃路徑的效果,該文生成了小規(guī)模測(cè)試數(shù)據(jù)(n=15)并進(jìn)行對(duì)比實(shí)驗(yàn)。測(cè)試過程中,超出時(shí)間窗懲罰系數(shù)為k=0.1。

測(cè)試所得的路徑規(guī)劃圖如圖5所示,其中不同樣式的虛線代表不同冷鏈物流運(yùn)輸車的路徑。其中標(biāo)準(zhǔn)SSA算法生成路徑為：車輛1：0→6→7→10→11→12→13→14→0,車輛2：0→1→2→3→4→5→8→9→15→0,總花費(fèi)(總時(shí)間與懲罰成本之和)為163.820 8;改進(jìn)SSA算法生成的路徑為：車輛1：0→1→2→3→4→5→0,車輛2：0→8→9→7→6→10→0,車輛3：0→12→11→15→13→14→0,總花費(fèi)(總時(shí)間與懲罰成本之和)為117.266 6。從結(jié)果可以看出,改進(jìn)的SSA算法在求解文中模型時(shí)可以得出更優(yōu)的解,進(jìn)一步驗(yàn)證了改進(jìn)算法的有效性。

圖5 規(guī)劃路徑對(duì)比圖

4 結(jié)束語(yǔ)

針對(duì)城市間冷鏈物流的高時(shí)效要求,建立了帶時(shí)間窗的城市間冷鏈物流的數(shù)學(xué)模型。針對(duì)這個(gè)模型,提出了一種改進(jìn)的離散麻雀搜索算法,通過引入基于維度的鄰域?qū)W習(xí)策略和動(dòng)態(tài)因子更新公式提高麻雀搜索算法的收斂速度和收斂精度,并且通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的有效性。最后使用小規(guī)模數(shù)據(jù)集可視化對(duì)比了改進(jìn)SSA算法與標(biāo)準(zhǔn)SSA算法的路徑規(guī)劃結(jié)果。另外,該算法還有很大的改進(jìn)空間,今后可以在VRPTW的基礎(chǔ)上引入更多的約束條件,例如不同型號(hào)冷鏈物流運(yùn)輸車在時(shí)速和最大載重量的差異、動(dòng)態(tài)的超出時(shí)間窗懲罰因子等,以提升模型的應(yīng)用廣度。