基于改進麻雀搜索算法的冷鏈物流路徑優化

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

(1.南京郵電大學 江蘇省郵政大數據技術與應用工程研究中心,江蘇 南京 210023;2.南京郵電大學 國家郵政局郵政行業技術研發中心(物聯網技術),江蘇 南京 210023;3.安徽郵谷快遞智能科技有限公司,安徽 蕪湖 241300)

0 引 言

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

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

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

目前,麻雀搜索算法在車輛路徑規劃問題,尤其是大規模VRPTW的應用較少,而且其算法本身也存在一些不足?；诖?該文對麻雀搜索算法進行了改進,并將改進算法應用于冷鏈物流路徑優化問題的求解。

1 帶時間窗的大規模城市間冷鏈物流的數學模型

1.1 問題描述

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

1.2 模型假設

為了簡化模型,做出如下假設。

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

(2)假設冷鏈物流運輸車在城市間移動所需的時間為城市間的歐幾里得距離。

(3)假設每個城市只能由一輛冷鏈物流運輸車服務,且只能服務一次。

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

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

1.3 符號說明

模型符號說明如表1所示。

表1 模型符號說明

1.4 模型表示

模型的目標函數、約束條件由如下公式表示：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

2 麻雀搜索算法

2.1 標準麻雀搜索算法

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

發現者、加入者和警戒者的行為可以用以下公式表示[16]：

發現者：

(9)

加入者：

(10)

預警者：

(11)

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

2.2 麻雀搜索算法的離散化

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

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

圖1 浮點數組的離散化

圖2 離散化后生成的路徑

2.3 改進的麻雀搜索算法

標準麻雀搜索算法在求解VRPTW時出現了收斂精度不夠,易于陷入局部最優解的缺點。該文引入基于維度的鄰域學習策略和包含動態因子的發現者位置更新公式,以提高算法的收斂精度和收斂速度。

2.3.1 基于維度的鄰域學習策略

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

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

通過計算每個麻雀的鄰域,選擇鄰域內的麻雀進行信息交換,提高了子代麻雀信息來源的多樣性,提高算法的收斂精度。

信息交流的公式如下：

Xi,j=

(12)

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

2.3.2 包含動態因子的發現者位置更新公式

發現者是整個種群的核心,是領導者。發現者的位置決定了種群的搜索方向。為了平衡種群的開發和勘探,該文在發現者的位置更新公式中引入了動態因子λ：

(13)

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

(14)

2.3.3 改進算法的偽代碼

改進麻雀搜索算法的偽代碼如下所示：

Algorithm Improved-SSA

Input：

Max_iter：最大迭代次數;PD：發現者數量;SD：預警者數量;ST：預警值;N：麻雀種群數量

Output：

X_best,f_curve

1.初始化種群

2.while (t

3. 對種群適應度排序,選出最優個體和最差個體

4. fori=1：PD

5. 使用式14更新發現者位置

6. fori=(PD+1)：N

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

8. fori=1：SD

9. 使用式11更新預警者位置

10. fori=1：N

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

12. 篩選出鄰域內的麻雀,隨機選擇一只,使用式12進行信息交流

13. 如果麻雀在新位置的適應度優于原位置,則更新麻雀位置,否則位置不變

14.t=t+1

15. end while

16. ReturnX_best,f_curve

3 實驗分析

3.1 實驗數據集

該文使用23個標準測試函數對改進的麻雀搜索算法進行測試,以衡量改進算法的搜索能力。同時,使用6個標準VRPTW數據集進行測試,以考察改進算法在冷鏈物流路徑優化問題的求解效果。

3.1.1 標準測試函數

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

該文對23個測試函數分別進行30次獨立重復實驗,所得每個算法在每個測試函數上的平均值和方差如表2所示。實驗結果表明,改進的SSA算法在15個測試函數上,求解的平均值排名第一,占比65%,求解結果也有較強的穩定性。特別是在f21～f23這種復雜函數上,改進的SSA算法有著絕對優勢?？偟膩碚f,改進的SSA算法相較于標準SSA算法和其他元啟發式算法有較強的競爭力,驗證了改進的有效性。

表2 30次獨立重復實驗所得結果的平均值和方差

3.1.2 標準VRPTW數據集

該文選取了6組數據集進行實驗對比,分別是C101[23],RC2_2_2[24],RC1_4_1[25],R1_6_2[25],R1_8_1[25],R1_10_1[25]。每個數據集包括城市坐標、貨物需求量、送達時間窗、卸貨時間。

3.2 實驗結果分析

該文的評價指標是所有車輛的運行時間、卸貨時間與超出時間窗的懲罰成本之和。

采用Matlab2022b對改進后的麻雀搜索算法進行對比,使用6個測試數據集對算法的性能進行評估,為了方便比較,圖4是改進的SSA算法與標準SSA算法在其中2個測試數據集(RC2_2_2,R1_6_2)上的適應度迭代曲線。從圖中可以看出,改進后的SSA算法在迭代前期有較大的收斂速度,在迭代后期的收斂精度也有較大的優勢。

圖4 改進SSA與標準SSA迭代曲線對比

(1)收斂分析。

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

(2)穩定性分析。

為了進一步評估改進的SSA算法,對兩種算法在6個測試數據集上分別進行30次獨立重復實驗,每次獨立重復實驗取迭代次數為300。所得平均值與方差如表3所示。從表中數據可以看出,在75%的數據集上改進的SSA算法求解結果的平均值為最優,體現出較強的搜索性能。但是在求解結果的穩定性方面還有一定的改進空間。

表3 經過30次獨立測試所得最優解適應度的平均值與方差

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

測試所得的路徑規劃圖如圖5所示,其中不同樣式的虛線代表不同冷鏈物流運輸車的路徑。其中標準SSA算法生成路徑為：車輛1：0→6→7→10→11→12→13→14→0,車輛2：0→1→2→3→4→5→8→9→15→0,總花費(總時間與懲罰成本之和)為163.820 8;改進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,總花費(總時間與懲罰成本之和)為117.266 6。從結果可以看出,改進的SSA算法在求解文中模型時可以得出更優的解,進一步驗證了改進算法的有效性。

圖5 規劃路徑對比圖

4 結束語

針對城市間冷鏈物流的高時效要求,建立了帶時間窗的城市間冷鏈物流的數學模型。針對這個模型,提出了一種改進的離散麻雀搜索算法,通過引入基于維度的鄰域學習策略和動態因子更新公式提高麻雀搜索算法的收斂速度和收斂精度,并且通過實驗驗證了改進算法的有效性。最后使用小規模數據集可視化對比了改進SSA算法與標準SSA算法的路徑規劃結果。另外,該算法還有很大的改進空間,今后可以在VRPTW的基礎上引入更多的約束條件,例如不同型號冷鏈物流運輸車在時速和最大載重量的差異、動態的超出時間窗懲罰因子等,以提升模型的應用廣度。