強化學習結合大規模鄰域求解多能源車輛冷鏈路徑優化問題

摘 要：冷鏈物流迅速發展，導致燃油冷藏車的碳排放增加。然而，電動冷藏車的續航里程限制了冷鏈配送的時效性，給企業冷鏈物流發展造成了不利影響。為解決能源消耗和配送成本問題，文章建立了基于多能源車輛和充電、換電模式選擇的冷鏈路徑優化數學模型。同時，提出一種強化學習結合自適應大規模鄰域搜索的算法（RL-ALNS）。通過策略梯度法訓練數據，采用擾動和改進算子提升可行解的廣度，設計具有針對性的碳排放、時效性算子來提高解的精度，并對充電、換電模式進行優化。通過仿真實驗發現，多能源車輛配送更加符合當前冷鏈物流發展。并且與其他傳統算法相比，RL-ALNS算法求解的成本更低，也表明強化學習與啟發式算法相結合可以應用于較復雜的車輛路徑優化問題中。

關鍵詞：冷鏈物流；多能源車；強化學習；碳排放；時間窗

中圖分類號：F252；U121 文獻標志碼：A DOI：10.13714/j.cnki.1002-3100.2024.12.040

Abstract： The rapid development of cold chain logistics has led to an increase in carbon emissions from fuel refrigerated vehicles. However， the range of electric refrigerated trucks limits the timeliness of cold chain delivery， which has a negative impact on the development of enterprise cold chain logistics. To solve the problems of energy consumption and distribution costs， this paper establishes a mathematical model for optimizing cold chain paths based on multi-energy vehicles and charging and battery swapping mode selection. Meanwhile， the paper proposes an algorithm combining reinforcement learning with adaptive large-scale neighborhood search （RL-ALNS）. By using the strategy gradient method to train data， the paper uses perturbation and improvement operators to enhance the breadth of feasible solutions， designs targeted carbon emission and timeliness operators to improve solution accuracy， and optimizes charging and battery swapping modes. Through simulation experiments， it is found that the distribution of multi-energy vehicles is more in line with the current development of cold chain logistics. Compared with other traditional algorithms， the RL-ALNS algorithm has lower solving costs， indicating that the combination of reinforcement learning and heuristic algorithms can be applied to more complex vehicle path optimization problems.

Key words： cold chain logistics; multi-energy vehicles; reinforcement learning; carbon emissions; time window

隨著人們對食品生鮮要求的不斷提高，冷鏈物流市場持續擴大，當前冷鏈物流中采用的傳統燃油冷藏車配送模式與生態環境之間的矛盾日益突出。已有不少國內外學者在燃油汽車的冷鏈物流方面展開了研究。杜琛等[1]針對燃油冷藏車冷鏈配送的最小油耗和客戶滿意度來構建數學模型，并提出一種改進鄰域解產生方法的模擬退火算法進行求解。Suzuki[2]考慮通過減少燃油使用，最大限度降低污染排放來建立油耗最小化模型。電動冷藏車具備的低能耗、低污染的特點，有利于緩解碳排放，實現綠色生態環境建設，因此不少企業開始使用電動冷藏車代替傳統的燃油冷藏車進行冷鏈配送。但受限于目前技術條件，電動冷藏車存在充電、換電站不完善導致充電時間長、電池不耐用等問題，因此，提高冷鏈時效性成為電動冷藏車應用于冷鏈配送的關鍵。張瑾等[3]在構建模型時，將時效性和最小化成本作為目標，構建多目標模型以解決冷鏈配送優化問題；林長通[4]研究充電、換電模式的物流車城市配送。電動車換電模式，成為解決電動車充電時間過長的一種方式。但是換電過多會導致配送成本增加，因此在配送過程中如何選擇合理的充電、換電的補電模式是影響配送時效性的主要問題。因此，本文為了在節能減排的同時提高冷鏈配送時效性從而降低冷鏈物流企業配送成本，構建了以電動冷藏車兼具充電、換電服務的多能源車輛總配送成本為最小目標的冷鏈優化模型。

1" " 數學模型

1.1" " 問題描述

某城市的生鮮冷鏈配送中心利用傳統燃油冷藏車和電動冷藏車進行冷鏈物流配送，每輛冷藏車配送服務的總需求量與其最大載重相關，電動冷藏車的電池容量約束其行駛里程。

基本假設如下。

車輛從配送中心出發時，燃油冷藏車處于滿油狀態；電動冷藏車處于充滿電狀態，中途可充電、換電多次；在換電時無需等待。

需要充電的電動冷藏車到達服務站時無需等待，可以即刻充電；

冷藏車制冷所消耗電能與時間成正比；

車輛消耗電能與里程成正比；

配送路徑上的服務站為兼具充電和換電模式的綜合服務站。

1.2" " 模型構建

0，N+1：冷鏈配送中心；

V：客戶集合；

V0=V∪{0}；

VN+1=V∪{N+1}；

Ke：電動車輛集合；

Kc：燃油車輛集合；

K=Ke∪Kc，所有車輛集合；

F：充電、換電服務站集合；

I=F∪{0}；

V'=V∪F；

V'0=V'∪{0}；

V'N+1=V'∪{N+1}；

V'0，N+1=V'∪{0}∪{N+1}；

qi：客戶點i的需求；

E：電池最大容量；

Qe/Qc：電動車/燃油車最大載重；

si：客戶點i的服務時間；

v1：車輛行駛速度；

g：充電速度；

dij：節點i與j之間的距離；

tij：節點i到j的車輛行駛時間；

ei，li：節點i最早/晚接受服務時間；

ce，cl：車輛在需求點的單位等待/延遲時間成本；

β：車輛單位行駛成本；

s：車輛運輸單位時間內的碳排放成本；

λ：服務站進行服務成本；

ski：車輛k在電站i的充電時間；

E1ik：車輛k到達節點i的電量；

E2ik：車輛k離開節點i的電量；

B：為滿電狀態；

Eki：車輛k在節點i的充電/消耗量；

ti：到達節點i的時刻；

tkwi：車輛k提前到節點i的等待時間；

tkdi：車輛k晚到節點i的延誤時間；

h：單位行駛路程所消耗電能。

決策變量定義為：，根據以上目標函數和約束條件的分析，建立多能源車輛冷鏈路徑規劃模型。

其中，式（1）表示冷藏車配送服務總成本最小；式（2）表示每個客戶只服務一次；式（3）表示每輛車從配送中心發出，完成配送任務之后返回；式（4）表示車輛服務需求總量在其合理載重之內；式（5）表示電動車充電時所消耗時間；式（6）表示電動車的充電量；式（7）表示車輛在節點早到的時間；式（8）表示車輛在節點遲到的時間；式（9）—式（11）表示車輛從某個節點出發并訪問客戶后有足夠電量到達其他節點；式（12）表示車輛在服務站進行充電、換電后有足夠電量回到配送中心；式（13）表示每輛車都要在可接受時間窗內到達。

2" " 算法設計

2.1" " RL-ALNS算法

模型中時效性、碳排放等因素對多能源車輛冷鏈配送問題的影響較為顯著，且客戶規模較大時，傳統啟發式算法難以在有效時間內獲得最優解方案。基于此，本文設計了一種強化學習結合自適應大規模鄰域搜索算法（RL-ALNS），在設置最大代數T步之后停止，經過算法求解，選擇最優解作為最終解。第一階段基于設定的規則，通過強化學習嘗試不同的方法尋優。即通過策略網絡訓練數據，根據算子歷史動作效果及注意力網絡特征，饋送至兩個完全連接層的網絡中，產生動作概率向量來選取擾動和改進算子提升可行解的廣度，改善ALNS算法陷入局部最優的困境，形成最優算法模型；第二階段根據建立的數學模型設計具有針對性的碳排放、時效性算子改進ALNS算法，對第一階段輸出的解進行進一步優化，進行pu次破壞、修復尋求最優解，并對充電、換電模式進行優化。

2.2" " 編碼與解碼

根據2.1節得到模型求解，每一條路徑由一輛冷藏車進行配送。例如，某配送任務是：10個客戶點由一個配送中心進行服務，其中有2個服務站可以為電動冷藏車提供充電、換電服務。編號0為配送中心；編碼1—4為不同服務站的不同服務，一個服務站編碼由奇數和偶數表示，奇數為充電服務，偶數為換電服務，如表1所示；編碼5—14為客戶點。

通過RL-ALNS算法求解為[0，5，9，12，1，6，0]，[0，14，8，2，11，0]，[0，13，10，7，0]以及確定服務站在路徑中的位置。進行解碼：路徑1（電動冷藏車1），配送中心0—客戶5—客戶9—客戶12—服務站1進行充電—客戶6—配送中心0；路徑2（電動冷藏車2），配送中心0—客戶14—客戶8—服務站2進行換電—客戶11—配送中心0；路徑3（燃油冷藏車1）配送中心0—客戶13—客戶10—客戶7—配送中心0。

2.3" " 破壞與修復算子

2.3.1" " 破壞算子

本文采用相關ALNS算法的隨機移除客戶節點算子、最差成本移除算子。此外，針對本文模型設計最差碳排放成本移除算子和最差時效性移除算子。

隨機破壞算子：從現有的路徑中隨機移除若干個客戶節點。

最差成本破壞算子：移除使當前可行解中增加成本最大的部分客戶節點，即如果移除這些客戶點，能夠顯著降低當前可行解的成本。

最差碳排放成本破壞算子：從可行解的燃油冷藏車路徑中移除導致增加碳排放成本最大的部分客戶節點，即若移除這些節點，能夠顯著降低當前可行解的碳排放成本。

最差時效性破壞算子：客戶節點有時間窗要求，晚到會產生相應的延誤成本，造成冷鏈配送時效性下降且這部分成本較高。因此，從解方案的車輛路徑中移除增加懲罰成本最多的若干客戶節點，即移除這些節點，能夠使當前解的冷鏈配送時效大幅度提高。

2.3.2" " 修復算子

隨機修復算子：在滿足初始解的條件下，將被移除的客戶節點插入已有的路徑中。

成本貪婪修復算子：基于被移除的客戶節點可能插入已有路徑中的位置，根據成本增大程度，依次選擇程度最小的客戶節點與插入位置組合，直到所有被移除的客戶節點都重新插入為止。

后悔值修復算子：先計算被移除客戶點重新插入路徑中n個次優節點時其目標函數值與最優節點的差之和，最后選擇差之和最大的客戶節點及其最優節點。

2.4" " 激勵策略

依據每個客戶的位置和需求，計算其之前和之后訪問的相鄰節點及相關距離。設置激勵RF1：最小碳排放激勵。計算每條路徑的碳排放成本，能使碳排放成本降低的算子得分，否則不變，選取碳排放得分最低的路徑進行破壞。激勵RF2：最小時效性成本激勵。計算每條路徑的違反時間窗成本，能使時間窗成本降低的算子得分，否則不變，選取違反時間窗成本最高的路徑進行破壞。激勵RF3，將冷鏈配送總成本最小化作為目標，采用不同算子進行迭代，將每次迭代期間取得的總成本與歷史最優解之間的差作為激勵。具體來說，如果破壞、修復算子改進了當前可行解，則對應算子得分獎勵+1，否則-1。例如，at-h表示當前步驟t采取的h步動作的得分，如果當前動作可以使總成本減少，則at-h為+1，否則為-1，其中1≤h≤H（采取的總步驟數）。

2.5" " 策略網絡

采用Williams的REINFORCE算法使用基線函數b（s）來更新策略梯度。

策略網絡輸出一個動作概率列表，每個動作對應一個概率。將節點信息：客戶需求量、車輛載重作為輸入特征被轉換為長度為D=64嵌入，該嵌入被饋送到由Vaswani所提出具有64個輸出單元的注意力層上。注意力網絡的輸出與一系列最近的動作及其效果（當Hgt;0時）連接在一起。最后將連接值反饋至兩個完全連接層的網絡中，其中第一層使用64個單元和Relu激活函數，第二層使用Softmax，產生|A|動作概率，其中A是動作集合。

3" " 算例分析

為了驗證本文提出的RL-ALNS算法求解多能源車輛的效果，本節算例由Goeke經典算例調整而來。程序利用Pytorch1.0.2進行編寫，運行于單塊 Nvidia GeForce GTX 1 050 Ti上。

3.1" " 參數設置

相關參數與Nazari等的研究保持一致。為了訓練策略網絡，將嵌入層的節點數設為64，解碼器采用LSTM，隱層節點數設為64，采用ADAM優化，學習率為0.001。訓練數據集的大小為20 000，對應的驗證集大小為2 000。模型參數取值如表2所示，其中rho表示算子權重衰減系數，pu為破壞、修復次數；T為迭代次數。

3.2" " 仿真實驗

3.2.1" " 算法有效性

為了驗證本文模型及提出RL-ALNS算法的有效性，本節分別用標準ALNS算法和RL-ALNS算法對聚類分布（C）、隨機分布（R）和二者混合分布（RC）的三種不同客戶分布、服務時間等情況進行求解。分別獨立運行10次選取最優值，其實驗結果如表3所示。其中，第1列為客戶點具體分布類型，第2—7列為總成本最優解、平均解和最差解，第7、8列分別給出程序運行時間。AVG表示算法對三類問題的平均表現。

從實驗結果的數據可以看出，通過對三類不同客戶需求分布的配送方案進行求解，RL-ALNS算法求得的結果都比ALNS算法求得的更優；就平均值來看，RL-ALNS算法的結果同樣更勝一籌。ALNS算法求解的最小配送總成本平均值為11 178.307，而RL-ALNS算法的平均最小值為8 834.286，相比之前節約了20.96%。將強化學習與ALNS算法結合形成RL-ALNS算法的平均運行時間與傳統ALNS算法運行時間相差不大。因此，本文提出的模型及算法能有效求解大規模客戶問題，同時對不同的客戶分布和客戶服務時間長度能夠顯著提升求解質量，對復雜問題具有較好的求解性能。

3.2.2" " 模型有效性

以R101算例為例，以考慮碳排放與時效性的配送總成本為最小目標。程序運行10次，進行100次迭代，得到最優解。滿足客戶配送需求最少需要8輛車進行配送，其中包含5輛燃油車和3輛電動車，總配送成本僅有7 621.075元。車輛最優路徑如表4所示。其中，0為配送中心，1—42為服務站（單數為充電模式、雙數為換電模式），43—142為配送客戶，1—5車為燃油冷藏車，6—8車為電動冷藏車。

將配送任務分別用燃油冷藏車、電動冷藏車和多能源混合冷藏車進行配送，不同車輛配比均進行10次實驗選取最優結果，用RL-ALNS算法求解最優方案配送總成本。結果橫向對比如表5所示，ffe為配送總成本，ff為燃油冷藏車配送總成本，fe為電動冷藏車配送總成本，t為算法運行時間。

從實驗結果來看，將多能源車輛應用于冷鏈配送的總成本8 263.821比傳統燃油冷藏車配送總成本13 369.483減少38.19%，比電動冷藏車配送總成本11 701.401降低29.37%。由此可見，多能源冷藏車應用于冷鏈配送中可以在節能減排的同時提高冷鏈配送時效性，從而降低冷鏈物流企業配送總成本。在實際冷鏈物流運輸過程中，企業可以根據服務站數量、運輸距離等實際問題對電動冷藏車在車隊中的占比進行合理調整。

4" " 結" " 語

為更好地應對當前冷鏈物流綠色發展，實現企業降本增效的目標，本文基于現實環境考量，針對電動冷藏車在服務站進行充電、換電選擇優化，考慮碳排放、時效性、時間窗約束的多能源車輛冷鏈配送問題，建立了以總成本最小化為目標的數學模型。實驗表明，采用多能源車輛進行冷鏈配送有助于企業在降低碳排放實現綠色發展的同時提高企業運營利潤。

對于提出的復雜多能源車輛冷鏈路徑優化模型，設計的基于強化學習框架改進自適應大規模鄰域搜索算法（RL-ALNS），通過仿真實驗驗證該算法求解多能源車輛路徑優化問題的有效性。與ALNS算法相比較，該算法求解精度更高，也進一步表明，強化學習與啟發式算法相結合可以應用于較復雜的車輛路徑優化問題中，從而為之后的研究提供參考。

參考文獻：

[1] 杜琛，李怡靖．基于客戶滿意度和最小損耗的冷鏈配送路徑問題研究[J]．工業工程與管理，2020，25（6）：163-171.

[2] SUZUKI Y.A new truck-routing approach for reducing fuel consumption and pollutants emission[J].Transportation

Research Part D-Transport and Environment， 2011（1）：73-77.

[3] 張瑾，畢國通，戴二壯．雙目標冷鏈物流車輛路徑問題及其遺傳蟻群求解[J]．科學技術與工程，2020，20（18）：7413-7421.

[4] 林長通．基于充換電模式的電動物流車城市配送路徑優化研究[D]．北京：北京交通大學，2021.