基于哈里斯鷹算法的兩級冷鏈配送路徑優化

摘 要：農產品供應鏈是農產品流通現代化的重要體現。隨著生活水平的提高，人們對生鮮農產品的需求逐漸增加，農產品供應鏈冷鏈配送壓力不斷增大，農產品包裝也隨之造成嚴重的環境污染。文章基于對包裝二次利用的考慮，以車輛固定成本、車輛運輸成本及制冷成本最小為目標，構建考慮客戶滿意度的兩級生鮮農產品冷鏈車輛路徑優化數學模型，融合變鄰域搜索機制的離散哈里斯鷹算法對該模型進行求解，使用迭代貪心算法和隨機方法生成初始解，然后使用設計的搜索算子尋優。通過仿真實驗對提出算法與其他算法和數字優化技術（CPLEX）進行對比，驗證了文章提出的改進哈里斯算法可行性、高效性及穩定性，對城市限行下農產品冷鏈配送路徑優化問題研究具有一定的意義。

關鍵詞：農產品配送；兩級車輛路徑優化；哈里斯鷹算法；變領域搜索

中圖分類號：TP18"""""" 文獻標志碼：A

0 引言

隨著電子商務、農產品直播帶貨、公益助農的 快速發展，越來越多的人選擇線上購買農產品，配 送量增加導致農產品供應鏈出現配送效率低、配送 不及時、農產品損耗大等問題[1-2] 。為促進農產品冷 鏈物流健康發展，健全農產品供應鏈體系建設，中 華人民共和國財政部、商務部明確要求在農產品供 應鏈現有體系建設工作基礎上，提升冷鏈物流質量 效率，建立健全暢通高效、貫通城鄉、安全規范的農 產品現代流通體系，重點抓住跨區域農產品批發市 場和銷地農產品冷鏈物流網絡，健全銷地冷鏈分撥 配送體系，創新面向消費的冷鏈物流模式，推動農 產品冷鏈物流高質量發展。因此，如何提升農產品 冷鏈配送效率及配送服務成為農產品供應鏈配送 車輛路徑規劃問題的研究方向之一。

1 理論研究

農產品配送路徑關系到配送系統的配送總成本和客戶滿意度[3-4] ，學者們針對農產品配送路徑優 化問題（Vehicle Routing Problem，VRP）研究頗多。其 中，夏揚坤等[5] 研究客戶分級和客戶需求可拆分的 車輛路徑問題，提出帶動態禁忌表的自適應禁忌搜 索算法。Chen等[6] 構建了考慮質量惡化和碳排放成 本的冷鏈配送路線優化模型，并結合禁忌算法與改 進的蟻群算法進行優化求解。Li和Li [7] 通過研究帶 混合時間窗的車輛路徑規劃問題，設計了單親遺傳 算法求解。Yao等[8] 針對海產品新鮮度，建立了多倉 庫的車輛路徑模型，并用蟻群優化算法優化。Song 和Ko[9] 以農產品新鮮度為客戶滿意度評價標準，建 立了多農產品的多車型路徑規劃問題。

受城市道路限行影響，農產品配送需在不同類型 車輛間中轉，由此延伸出兩級車輛路徑規劃問題（Twoecholon Vehicle Routing Problem，2E-VRP）[10- 11] 。葛 顯龍等[12] 提出了前置倉協作的兩級配送策略，并設 計了改進的遺傳算法優化。馬艷芳等[13] 建立考慮客 戶分類的兩級容量有限車輛路徑優化模型，并用遺 傳模擬退火算法和精確算法優化模型。Ji等[14] 考慮到碳排放、客戶時間窗和隨機需求，建立了兩級冷鏈車輛路徑問題。Govindan 等[15]考慮到經濟和環保問題，建立了多目標選址-路徑配送模型，并設計了混合變領域搜索算法的多目標粒子群算法（MH? PV）。學者們對2E-VRP 問題配送策略研究較多，但并未考慮取貨需求場景下的適用性。

2E-VRP 是非確定性多項式（NP-hard）問題，小規模問題可用精確算法求解，大規模常使用啟發式算法求解[16]。哈里斯鷹算法（Harris Hawk Optimiza? tion，HHO）[17]是一種基于群體智能優化算法，已被應用于VRP[18-19]問題中。

針對以上問題，文章考慮退貨、包裝回收和客戶滿意度的情況下，以車輛固定成本、運輸成本，以及制冷成本為目標函數，構建一種帶時間窗的考慮同時取送的兩級冷鏈配送路徑優化模型（A two-ech? elon cold chain vehicle routing problem with time win? dows considering simultaneous pickup and delivery，2E-CVRPTWSPD），并設計了一種融合變鄰域搜索機制的離散哈里斯鷹算法（Discrete Harris Hawk Op? timization，DHHO），然后通過仿真實驗驗證了 DH? HO 求解2E-CVRPTWSPD 的可行性和穩定性。

2 問題描述與建模

2.1 問題描述

文章對2E-CVRPTWSPD 進行研究，如圖1所示，在農產品配送網絡中，中心倉庫使用大型車輛運輸農產品到配送中心，再由配送中心使用小型車輛給客戶配送并收取退貨的農產品和回收包裝，最后由大型車輛從各個配送中心回收農產品至中心倉庫，需求取一組合理的兩級車輛配送路線，使得總成本最小。為方便求解問題，做以下假設：

（1）每個客戶都有被送貨和退貨的需求，考慮到因不滿意農產品而退貨的情況較少，所以文章中取貨量遠小于送貨量；

（2）中心倉庫不能直接向客戶配送。為提高客戶的滿意度，客戶的期許時間窗可視為硬性時間窗。由于有時間窗的限制，一級車輛可多次到達配送中心。

（3）在實際的配送路線中，任意兩點存在許多的線路，為簡化問題，文章將兩點的歐幾里得距離視為其路徑。

2.2 數學模型符號定義

考慮后續數學模型構建需要，在此對模型的主要參數統一定義及說明如下，見表1。

2.3成本變量分析

（1）車輛固定成本C1

車輛配送固定成本包含配送的大型車輛和小型車輛的費用，計算公式如下：

（2）車輛配送成本C2

車輛配送成本包括車輛折舊費用、維修保養費、燃油費，其主要與車輛配送路徑里程有關，計算公式如下：

（3）制冷成本C3

在車輛配送過程中，制冷成本主要與配送運輸過程中為保持低溫產生的成本，因此在文章中只考慮一級配送路線和二級路線的成本，計算公式如下：

2.4整數規劃模型

生鮮農產品配送問題的總成本 C 由3部分組成，分別為車輛固定成本 C1、車輛配送成本 C2和制冷成本 C3，以下為最小總成本為目標函數的數學模型。

目標函數定義為：minC=C1+C2+C3"" （4）

一級路線的流入流出平衡模型如下：

一級路線中每個偽配送中心只能被車輛服務一次，模型如下：

避免一級路線生成子回路的數學模型如下：

確保只有服務對應配送中心的大型車輛才能進行取貨和送貨的操作，模型如下：

大型車輛的載重限制模型如下

二級路線的流入流出平衡模型為：

確保每位客戶只被一輛車服務模型為：

確保每個偽配送中心只能被一個小型車輛服務模型為：

限制每個小型車輛只能調用一次模型為：

車輛在配送與回收農產品時載重變化的約束如下：

從中心倉庫到各個配送中心的農產品數量等于從配送中心送達客戶的農產品的數量，模型為：

從客戶收取的農產品到達配送中心的數量等于從配送中心送達中心倉庫的數量，模型為：

大型車輛服務時間與卸貨量的關系模型為：

每條二級路線上農產品的質量不超過小型車輛的容量，模型為：

農產品送達配送中心的到達時間模型為：

只有大型車輛離開中心倉庫才能送達到各個配送中心約束模型為：

當只有大型車輛將農產品送達配送中心，小型車輛才能去服務客戶約束模型為：

將農產品送達客戶的送達時間模型：

客戶的硬性時間窗限制模型：

3離散的哈里斯鷹算法

文章提出的2E-CVRPTWSPD 問題包含兩級配送路線，二級路線可視為有時間窗的車輛路徑規劃問題（Vehicle Routing Problem With Time Windows， VRPTW），一級路線分為一級配送路線和一級取貨路線，分別可視為有時間窗的車輛路徑規劃問題和容量限制的車輛路徑規劃問題（Capacitated Vehicle Routing Problem，CVRP）。標準的 HHO是用來求解連續優化問題的，無法直接求解2E-CVRPTWSPD 問題，文章根據問題特性設計了一種離散哈里斯鷹算法的搜索機制和開發機制，并為減緩哈里斯鷹算法過早收斂引入了變領域搜索機制。

3.1標準的哈里斯鷹算法

哈里斯鷹優化算法是通過模仿美國亞利桑那州的哈里斯鷹（栗翅鷹）協同捕獵兔子的行為，基于灰狼優化算法（Grey Wolf Optimizer，GWO）[20]框架改進而提出的一種群智能優化算法。標準的哈里斯鷹算法分為探索階段和開發階段，根據逃逸能量因子E 進行階段的選擇，E 是的逐漸下降。

式中：E0是（-1，1）之間的隨機初始能量值，T 為最大迭代次數，具體的優化機制見文獻[17]第3.2、3.3節。

3.2 DHHO 算法流程

通過初始化方法生成一個種群群體，規模為N，初始化最大迭代次數max_iter 等參數。計算每一個哈里斯鷹個體的適應度值，將最優個體賦予 Xrabbit 。然后計算逃逸能量E，如果|E|≥1，則算法會進行探索行為；否則根據E 和兔子逃脫的概率r 來進行相應開發行為。以下為 DHHO 算法解決兩級冷鏈配送路徑問題的偽代碼。

算法名稱：DHHO 算法

輸入：最大迭代次數max_iter，種群規模N，輸出：最小總成本C 和所對應的最優個體

隨機初始化種群個體 Xi（i =1，2，… ，N），每個個體對應一種解

for i=1 to max_iter

while（小于最大停滯迭代數）

計算種群中每個個體的適應度值，并將最優值賦予最優個體

for（每個個體）

更行逃逸能量E 根據式（2～3）

if（|E|≥1）進行探索操作，并每一次更新

隨機數q

if（q ≥0.5）Xi 和 Xrand 進行insert_1 if（q lt;0.5）Xi 和 Xrand 進行insert_3

else（|E|lt;1）進行局部開發，并每一次更新隨機數r

if（r≥0.5 and |E|≥0.5）Xi 進行 insert_2，Xi 和 Xrabbit 進行exchange_1

elseif（r≥0.5 and |E|lt;0.5）Xi 進行ex? change_2，Xi 和 Xrabbit 進行exchange_3

elseif（rlt;0.5 and |E|≥0.5）Xi 和 Xrabbit 進行exchange_4，insert_1

elseif（rlt;0.5 and |E|lt;0.5）Xi 和 Xrabbit 進行insert_3，insert_4

End if

End for

End while

End for

Return 總成本C

3.3 編解碼方式

采用自然數編碼的編碼方式。對于2E-CVRPT? WSPD 問題，使用0表示中心倉庫，1～s 表示各個配送中心，s+1～n 表示各個客戶。其中一級配送網絡的每條路線包含中心倉庫和至少1個分配中心，解中不同路線由中心倉庫0隔開。二級配送網絡的每條線路包含至少1個客戶點，解中不同路線由分配中心（1～s）隔開。假設有2個配送中心，則配送中心編號為1，2；需要服務7個客戶，則客戶編號為3，4，…，9。配送編碼如下：二級配送路線：4371962852；一級送貨路線：1020；一級取貨路線：120。按照解碼機制，則二級配送網絡包含3條路線，一級送貨網絡包含2條路線，一級取貨網絡包含1條線路，如圖2所示。

3.4 初始化策略

2E-CVRPTWSPD 問題的一級路線和二級路線的配送路線均影響各配送中心的配送量，因此兩級配送路線相互影響，存在耦合關系。考慮到兩級問題的特性，采用自底向上的方式獲得2E-CVRPT? WSPD 的多個初始可行解。初始解的質量影響算法求解的性能，客戶的分配決定這兩級路線的規劃，文章將采用最短客戶與配送中心距離優先，最短中心倉庫到配送中心距離與該配送中心到客戶距離的和優先，隨機分配這3種方式分配客戶，然后依次在配送中心找到左時間窗最小的客戶，在未超過車輛剩余裝載量的情況下，在此配送中心服務的客戶中選擇與當前位置最短的客戶為下一個被服務的客戶，如果客戶的時間窗滿足則加入，車輛裝載量不能再服務客戶時，則安排下一輛車，依此獲得二級路線 VRPTW 的可行性方案，據此計算配送中心的運輸量和時間窗，然后求得一級配送路線 VRPTW 和一級取貨路線 CVRP，最后獲得多個可行的初始可行解。

3.5搜索算子

結合問題的特性設計搜索算子能得到更好的求解方案，2E-CVRPTWSPD 問題就是減少使用車輛并降低車輛行駛距離，據此文章設計了8種算子，具體如下：

（1）二級路線搜索算子

①insert_1：將1個客戶點從一條線路中移除，插入另一條線路。

②insert_2：將1個客戶點從一條線路中的一個位置移除，插入其他位置。

③exchange_1：從2條路線中各取1個客戶點，交換其位置。

④exchange_2：從1條路線中選取2個客戶點，交換其位置。具體操作如圖3所示。

（2）一級路線搜索算子

⑤insert_3：一級送貨路線將1個配送中心從1條線路中移除，插入另1條線路。

⑥exchange_3：一級送貨路線中從2條路線中各取1個配送中心，交換其位置。

⑦insert_4：一級取貨路線將一個配送中心從1條線路中移除，插入另一條線路。

⑧exchange_4：一級取貨路線中從2條路線中各取1個配送中心，交換其位置。具體操作如圖4所示。

4實驗結果與分析

目前沒有關于 DHHO 算法的標準測試算例。忽略制冷成本與固定成本，采用文獻[21]設計算例對文章所提 DHHO 算法進行驗證并與文獻算法（VNS-TS）比較。算法是基于 JAVA SE11.0.1實現的，仿真在windows10系統，處理器為 AMD Ryzen 52500U，主頻為2.00 GHz，運行內存8 GB RAM 的PC 機上運行。設置算法的最大迭代次數為25000次，或者最大停滯迭代次數為2000，每個算法獨立運行10次，CPLEX用于求解小規模問題，運行1次。

表2和表3中 BKS 為目前求解該算例的最優解，Best 為算法求解所得最優值，Avg 為算法運行所得的平均值，Gap 為 DHHO算法與目前最優值之間的偏差。由表3可知，在對18個小規模測試算例求解中，DHHO算法能求解到17個算例的最優值，并且有4個算例求的最優值小于 VNS-TS。由表3可知，在18個大規模問題中，DHHO算法能求得10個算例得最優解，在均值方面13個算例優于對比算法，說明DHHO算法求解的穩定性。

由圖5可知除100-10規模問題 DHHO 求得最小值高于 VNS-TS，其他的均低于對比算法，說明 DHHO 求解性能強；最高值均低于對比算法，表明 DHHO算法求解精度高；除7規模和200-10規模的算例，箱體面積大于VNS-TS，其他規模問題均小于對比算法，表明DHHO算法的穩定性。

Wilcoxon 秩和檢驗是基于上述實驗結果，讓 DHHO 算法與 VNS-TS 比較之間的顯著差異，進一步統計檢驗本文提出的算法的性能。表4、表5是 DHHO 算法與對比算法在大小規模問題中的 Wil? coxon 秩和檢驗的結果，每種規模問題包含180個算例。其R+是DHHO 算法優于對比算法的秩平均值， R-則是 DHHO 算法次于對比算法的秩平均值，yes 代表在90%或95%的置信區間上，DHHO跟對比算法有顯著性差異；no則反之。由表4、表5可知在求解算例上DHHO 算法與VNS-TS 算法存在顯著性差異。

圖6展示了部分算例收斂曲線比較圖。由圖6可知，在尋優性能、收斂速度和初始解方面 DHHO均優于對比算法。

5 結語

文章提出了一種離散的哈里斯鷹算法求解兩級冷鏈配送路徑優化問題，通過仿真驗證可達到最小化總配送成本。在DHHO 算法中使用3種初始解的方式，提高了初始解的質量和多樣性，設計了不同的算子進行優化求解。通過對36個測試案例的實驗仿真及統計檢驗，表明DHHO 算法具有較好的求解性能和穩定性。研究可為多中心倉庫的兩級冷鏈配送路徑優化問題提供參考。

參考文獻：

[1] Liu Y. Design of dynamic programming model for multi- objective cold chain logistics deployment path based on meme algorithm[J]. Iranian Journal of Science and Technology，Transactions of Civil Engineering，2021，46（3）：2553-2560.

[2] Pratap S，Jauhar S K，Paul S K，et al. Stochastic optimi? zation approach for green routing and planning in per? ishable food production[J]. Journal of Cleaner Produc? tion，2022，333：130063.

[3] Chen C，Tian Z H，Yao B Z. Optimization of two-stage location-routing-inventory problem with time-windows in food distribution network[J]. Annals of Operations Research，2019，273（1）：111-134.

[4] Bianchessi N，Drexl M，Irnich S. The split delivery vehi? cle routing problem with time windows and customer inconvenience constraints[J]. Transportation Science，2019， 53（4）：1067-1084.

[5] 夏揚坤，鄧永東，龐燕，等.帶客戶分級和需求可拆分的生鮮車輛路徑問題[J].計算機集成制造系統，2021，27（4）：1238-1248.

[6] Chen J，Gui P，Ding T，et al. Optimization of transporta? tion routing problem for fresh food by improved ant colony algorithm based on tabu search[J]. Sustainabili? ty，2019， 11（23）：1-22.

[7] Li N，Li G. Hybrid partheno-genetic algorithm for multi- depot perishable food delivery problem with mixed time windows[J]. Annals of Operations Research，2022：1-32.

[8] Yao B，Chen C，Song X，et al. Fresh seafood delivery rout? ing problem using an improved ant colony optimization[J]. Annals Of Operations Research，2019，273（1-2）：163-186.

[9] Song B D，Ko Y D. A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery[J]. Journal of Food Engineering， 2016， 169（Jan）：61-71.

[10] Li H，Wang H，Chen J，et al. Two-echelon vehicle routing problem with time windows and mobile satellites[J]. Transportation Research Part B Methodological，2020， 138（C）：179-201.

[11] Zhou L，Baldacci R，Vigo D，et al. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution[J]. European Jour? nal of Operational Research，2018，265（2）：765-778.

[12]葛顯龍，張小曉，王博.考慮前置倉協作的兩級生鮮配送路徑優化研究[J].計算機工程與應用，2022，58（15）：330-340.

[13]馬艷芳，李保玉，楊屹夫，等.客戶分類下生鮮配送兩級路徑問題與算法研究[J].計算機工程與應用，2021，57（20）：287-298.

[14] Ji Y，Du J，Wu X，et al. Robust optimization approach to two-echelon agricultural cold chain logistics consid? ering carbon emission and stochastic demand[J]. Environ? ment Development and Sustainability，2021，23（9）：13731-13754.

[15] Govindan K，Jafarian A，Khodaverdi R，et al. Two-eche? lon multiple- vehicle location- routing problem with time windows for optimization of sustainable supply chain network of perishable food[J]. International Jour? nal of Production Economics，2014， 152：9-28.

[16] Hemmelmayr V C，Cordeau J F，Crainic T G. An adap? tive large neighborhood search heuristic for two-eche? lon vehicle routing problems arising in city logistics[J]. Computers and Operations Research，2012，39（12）：3215-3228.

[17] Heidari A A，Mirjalili S，Faris H，et al. Harris hawks op? timization：Algorithm and applications[J]. Future Genera? tion Computer Systems， 2019，97：849-872.

[18]李留留， 張惠珍， 羅詩琪.求解有服務順序限制的 MMOVRPTW 問題的 IHHO 算法[J].控制工程，2024，31（1）：142-152.

[19] Alweshah M，Almiani M，Almansour N，et al. Vehicle rout? ing problems based on Harris Hawks optimization[J]. Journal of Big Data，2022，9（1）：42-60.

[20] Mirjalili S，Mirjalili S M，Lewis A. Grey Wolf Optimiz? er[J]. Advances in Engineering Software，2014，69（3）：46-61.

[21] Zhou H，Qin H，Zhang Z，et al. Two-echelon vehicle rout? ing problem with time windows and simultaneous pick? up and delivery[J]. Soft Computing，2022，26（7）：3345-3360.

Two-echelon Cold Chain Distribution Path Optimization Based on HarrisHawk Algorithm

LIU Xiangyang， LIU Huan， ZHI Yongkun， QIN Lijing， ZHANG Jizhe

（College of Information Science and Technology， Gansu Agricultural University， Lanzhou Gansu 730070，China）

Abstract： The supply chain of agricultural products is an important manifestation of the modernization of agri? cultural product circulation. With the improvement of living standards， people ’s demand for fresh agricultural prod? ucts has gradually increased， the pressure of cold chain distribution of the agricultural products supply chains has continued to increase， and the packaging of agricultural products has also caused serious environmental pollution. Based on the consideration of secondary utilization of packaging， this paper constructs a two-level mathematical model of cold chain vehicle routing optimization for fresh agricultural products considering customer satisfaction by minimizing vehicle fixed cost， vehicle transportation cost and refrigeration cost. The model is solved by integrating the discrete Harris Hawk algorithm of variable neighborhood search mechanism， and the initial solution is generated by iterative greedy algorithm and random method， and then use the designed search operator to search for optimiza ? tion. Through experimental simulation， the proposed algorithm is compared with other algorithms such as CPLEX to verify the feasibility， efficiency and stability of the improved Harris algorithm， which is of some significance to the study of the cold chain distribution path optimization problem for agricultural products under urban traffic restric ? tions.

Key words： agricultural distribution; two-echelon vehicle routing problem; Harris hawks algorithm; variable neighborhood search