基于溫區細化的多溫共配車輛路徑優化

唐 燕，許 睿，黃鍇迪，孟令清

(天津理工大學 管理學院，天津 300384)

0 引言

生鮮產品隨外界溫度變化，品質受較大影響，其保質期與食品的特性、儲藏溫度和時間密切相關[1]。多溫共配車輛長時間配送所處的環境溫度會有較大波動，制冷機的能耗隨外界溫度變化而改變[2]。為探討外界溫度變化對配送車能耗的影響，提出溫區細化(指動態環境溫度對制冷能耗的影響)的配送車溫控問題。

在生鮮產品配送方面，國內外相關學者主要在約束變量設置上進行了研究，如時間窗、貨損值、顧客滿意度等方面。Stellingwerf[3]提出負載目標約束最小的車輛路徑模型，對溫控環境下的碳排放量做出詳細研究。Bottani[4]探討了食品冷藏供應鏈的經濟和環境可持續問題，發現交付過程對環境影響最大。為提升溫控運輸系統效率，王勇等[5]將不同溫度控制下生鮮貨物的價值損失進行比較分析，構建了包含配送成本與貨物價值損失的目標優化模型。方文婷等[6]利用遺傳算法求解負載與卸載順序的綠色車輛路徑問題。付焯等[7]對風險與貨損進行分析，構建了生鮮農產品供應鏈風險決策模型。吳芳蕓[8]將資源與需求集中化，提出軸輻式冷鏈物流網絡模型對于冷鏈物流溫控成本的計算僅僅定義于車輛的運行時間、車廂門開關次數、卸貨時間等因素，忽略了外界溫度對配送車制冷能耗的影響。本研究將VRPTW問題結合大規模訂單，構建基于溫區細化的ALNS生鮮產品配送模型，使之更符合實際配送情況。

1 問題描述

配送流程中對溫度的控制不能得到保證，導致生鮮農產品新鮮度衰減加快，造成不必要的浪費和冷鏈成本提高。為有效控制整個冷鏈運輸中的溫度變化，減少生鮮農產品新鮮度損失速率，綜合考慮碳排放、客戶服務時間約束、制冷成本等因素，進行合理運輸調度。

具體假設如下：

(1)配送中心擁有一定數量且規格相同的配送車，每輛車的裝載量有限且大于單個客戶點的需求量。

(2)各節點位置、需求量、配送時間窗及服務時間確定。

(3)同一配送車可進行不同節點配送，每個節點僅配送1次且滿足客戶需求。

(4)配送車僅進行配送和裝卸任務，不接受任何其他配送服務且完成配送任務后返回到配送中心。

(5)配送過程中車輛勻速行駛，忽略道路擁擠情況。

生鮮配送過程對溫度要求較為嚴格，其中外部環境溫度變化也對配送車溫控的能耗產生影響[9]。根據我國氣象數據，收集天津市夏季平均氣溫每小時溫度(如表1所示)，最低溫度與最高溫度在時刻3和時刻13差值可達13.6 ℃。

表1 溫度變化Tab.1 Temperature change

不同種類產品對溫度的要求不同，配送車需對產品特性進行溫度控制。為計算溫度與能耗之間的關系，用COP表示熱量和能量間轉化比率，如式(1)所示：

(1)

式中，σl為車內的環境溫度；σh為車外環境溫度。為方便計算，利用開爾文溫度替代攝氏度，表示為σ(K)。開爾文溫度與攝氏度σ轉化關系為：

σ(K)=273+σ(℃)。

(2)

根據能量轉化關系，以車外25.8 ℃、車內零下5 ℃的冷卻單位成本來計算車廂內外不同溫度對應的制冷系數，得出制冷系數矩陣。利用MATLAB的CFTOOL工具進行薄板樣條法插值，擬合得到配送車內外溫度與制冷系數間的變化關系，擬合優度R2為0.98。由圖1(a)可得，在車外溫度為22～26 ℃，制冷系數較高，對應能耗隨之增大，圖1(b)更直觀地反映了制冷系數在不同溫區間的變化情況。

圖1 溫度細化的制冷系數相關圖Fig.1 Correlation diagrams of refrigeration coefficient for temperature refinement

2 模型建立

對生鮮農產品配送的問題假設及場景進行描述后，建立生鮮農產品配送模型。包括變量的定義、約束條件及目標函數。

2.1 變量定義

生鮮農產品配送中有關變量參數的定義如表2所示。

2.2 成本分析

2.2.1固定成本FC

配送車從配送中心出發用于支付駕駛員工資、車輛維修等費用。

(3)

2.2.2運輸成本TC

配送車正常行駛過程中的費用。

表2 已知參數Tab.2 Known parameters

(4)

式中α為單位距離成本。

2.2.3綠色成本GC

配送車的綠色成本包括負載狀態下，配送途中消耗的燃油成本及產生的碳排放對環境造成污染的成本。

(1)油耗成本

利用負載估計法對配送車配送過程的油耗量進行計算，確定負載與能耗之間的關系[10]。其油耗關系式為：

(5)

式中，ρ(G)為當前載重G噸貨物時造成的油耗；ρ0和ρ1分別為空載和滿載時的油耗系數；W為配送車最大載重量。

油耗Oil和油耗成本OC的表達式為:

(6)

OC=H·Oil，

(7)

式中，H為單位油耗成本；ρ(Wij)為載重量W的配送車從i到j的單位距離油耗量；dij為客戶i到j的行駛距離。

(2)碳排放成本

碳排放量與油耗量呈一定線性關系，建立油耗模型[11]。

CC=β·γ·Oil，

(8)

GC=OC+CC

(9)

式中，β為碳稅；γ為碳排放系數。

綠色成本等于油耗成本與碳排放成本之和。

(4)溫控成本TCC

在生鮮產品配送中要使溫度保持恒定，由此產生的能耗作為制冷成本。在裝車前預冷及配送過程中，制冷能耗與外界溫度、車廂表面積、太陽輻射面積等有關[12]，這里主要分析配送車外部環境中的溫度變化與制冷能耗的關系。

①裝配前對配送車預冷成本PC

生鮮農產品從產地采摘下來到分揀包裝運上配送車前，根據車內溫度與車外溫度，需對內部進行預冷操作，抑制其呼吸熱，延緩新鮮度衰減。

(10)

式中ησl,σh為車內溫度σl與車外溫度σh相對應的制冷系數。

②配送過程制冷成本DRC

配送車k從i到j的運輸時間tijk內車內溫度σl與車外溫度σh變化所產生的制冷成本DRC為：

(11)

③裝卸過程制冷成本LRC

(12)

④溫控總成本TCC：

TCC=PC+DRC+LRC。

(13)

(5)貨損成本TL

式(14)為生鮮農產品新鮮度衰減函數，表示在一定溫度下的腐化比例[13]：

Ω(t)=Ωoe-ωt，

(14)

式中，Ω(t)表示貨物在t時的新鮮度；Ωo為貨物出發時的新鮮度。

新鮮度衰減系數通常與產品的呼吸熱、周圍溫度有關，在裝卸過程中車廂門打開使車廂內外溫差及氧氣含量變大，生鮮產品新鮮度衰減速率加快從而得知ω2>ω1。其貨損成本表達式為：

(15)

(16)

式中，SL為生鮮配送過程的損失成本；HL為裝卸過程的損失成本；ω1為貨物在配送過程中的新鮮度衰減系數；ω2為貨物在裝卸過程中的新鮮度衰減系數。衰減系數通常與產品的呼吸熱、周圍溫度有關，在裝卸過程中車廂門打開使車廂內外溫差及氧氣含量變大，生鮮產品新鮮度衰減速率加快，從而得知ω2>ω1，Wir為車輛離開客戶點i時車上剩余貨物重量；Di為客戶i需求量；Ti為在客戶i的裝卸時間。

TL=SL+HL。

(17)

基于溫度細化的生鮮農產品配送模型的目標函數：

(18)

約束條件：

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

a(i)≤Ti≤b(i),(i∈N)，

(27)

(28)

Tj=Ti+Tij, ?i,j∈N，

(29)

Xijk,Yik=0或1, ?i,j,k。

(30)

式(19)表示各客戶點需求量之和不超過配送中心最大配送量，S為配送中心最大配送量；式(20)表示每個客戶點只能訪問1次；式(21)表示每輛車的配送量不超過最大載重量；wi為各客戶點需求量；式(22)～(23)表示所有客戶的需求量得到滿足；式(24)表示車輛k從配送中心o出發，完成客戶點j配送任務后返回到配送中心；式(25)～(26)表示任意節點只允許車輛出發到達1次，Yjk為配送車k為客戶點j服務；式(27)表示配送車輛達到時間必須為最大容忍時間窗內；式(28)表示消除子回路，L為任兩點間的回路總數；式(29)表示配送的過程是連續的，Tj為到達客戶點j的時間，Ti為到達客戶i的時間，Tij為兩點間行駛時間；式(30)為其約束條件。

3 算法設計

大規模鄰域搜索(LNS)通過構造初始可行解將多個具有相關性節點進行重組操作，探索解決問題的鄰域[14]。但隨著鄰域規模的增加，數據處理較為復雜。在此基礎上，自適應大規模鄰域搜索(ALNS)對于同一搜索中節點移除和插入的操作采用多種方法進行塑造，避免了LNS易陷入局部最優的問題。其流程圖如圖2所示。

圖2 ALNS優化流程圖Fig.2 Flowchart of ALNS optimization

3.1 初始解的構造

為提高生鮮配送模型優化效率，采用貪心算法構造初始解。以時間窗和配送容量為約束，通過初始化的距離矩陣，尋找距離節點i+1最近節點i直至遍歷網絡中所有節點得到VRPTW初始解。

3.2 算子移除操作

通過不同方法對初始解配送路線中節點進行移除。

(1)隨機移除：選擇一定數量節點移除，增加搜索過程多樣性。

(2)最差移除：在改進解的過程中，對成本最大節點進行移除。定義成本為：c(i,s)=f(s)-f-i(s)，其中f-i(s)為移除節點i的成本，將c(i,s)的值進行排序，靠前的節點被選擇概率最大。將差值較大的節點移除重新插入到其他位置，從而構造更優解。

(3)Shaw移除[15]：考慮相關度高的節點，r(i,j)為任兩點p和q間的相關程度；θ1，θ2，θ3，θ4分別為節點間距離d、時間T、載重量G、配送車輛k的權重系數。若相關程度越高，則移除該組節點的可能性越大，在后續重新構造更優解時增加多樣性和隨機性，如式(31)所示：

r(i,j)=θ1[dp(i),p(j)+dq(i),q(j)]+θ2(|Tp(i)-

Tp(j)|+|Tq(i)-Tq(j)|)+θ3|Gi-Gj|+θ4

(31)

3.3 算子插入操作

(1)隨機插入：相似于隨機移除，選擇一定數量節點進行插入，增加多樣性。

(2)貪心插入：不斷將被移除節點插入到使目標函數值最小的位置上，與構造初始解的方法相同。

(3)最少成本插入：Δfi為客戶i插入到第i′個節點后，目標成本增加的變化量為Δfi=max(fi-f′i)。

3.4 最優解篩選

利用輪盤賭法對不同算子表現情況所占的比例概率進行選擇[16]。τ1為產生新的全局最優解；τ2為產生新解但對應的目標函數值劣于當前解；τ3為產生非改進解但被接受。分數排序為τ1>τ2>τ3。對各組算子對應解的情況，新的最優解概率最高，非改進解概率最低。采用模擬退火算法的接受準則對候選解進行判斷，若目標函數適應度值Δf(x)<0，則更新當前最優解x，否則以概率exp(Δf(x)/T)接受X′作為新的當前解[17]。

4 結果分析

4.1 算法檢驗

利用Solomon算例，將禁忌搜索法(TS)[18]、大規模鄰域搜索法(LNS)與自適應大規模鄰域搜索法(ALNS)進行對比。得出每組車輛調度總配送路程結果，如表3所示。根據各算法結果表明LNS與ALNS計算優于TS，ALNS的計算普遍結果優于LNS計算，可得知使用ALNS算法對于求解VRPTW問題具有一定的可行性。

表3 算法檢驗Tab.3 Algorithm checking

參數設置：東風配送車規格為7.2×2.3×2.7 m，實際載重7 t/45 m3，生鮮供應客戶點數分別為400，800，1 000點，如圖3所示。配送車8：00從配送中心出發，額定行駛速度為60 km/h，生鮮市場價5元/kg，冷藏溫度在0～5 ℃，配送車固定成本為單次運輸150元。正常行駛下空載和滿載的油耗系數分別為0.18和0.41，配送車配送狀態的制冷系數和裝卸系數為5元/h和12元/h，由此產生的生鮮新鮮度衰減系數分別為0.03和0.06，柴油價格為5.09元/L，配送車碳排放量為2.669 kg/L，碳稅30 元/t，迭代次數為500次，更新選擇算子的間隔迭代次數30 次。

為貼近城市實際行駛路徑，將各配送點標記在二維的經緯度網格平面上，利用曼哈頓距離法計算各配送點間距離。小數點后6位精度約為1 m。由于整體數據龐大，部分配送訂單信息如表4所示。

表4 需求訂單信息Tab.4 Order demand information

4.2 成本分析

算法通過Win10系統的Eclipse(4.15.0)編程實現。得到不同規模的生鮮產品配送成本、制冷成本、貨損成本與綠色成本，如表5所示。配送成本包括固定成本與運輸成本，由表5可得。調度中花費比例占據最大為配送成本，最小為制冷成本。配送成本主要費用為配送車配送的里程油耗及駕駛人員工資，綠色成本涉及負載貨物配送造成的油耗，所占比例較大。隨著規模的增加，各項成本也呈倍數增加，綠色成本和貨損成本的增長幅度更高，隨著客戶點規模擴大，對于貨物需求量增大，其配送中出現不可避免的增加車次、載重油耗、運輸油耗、駕駛員開資等費用。

表5 ALNS各算例結果Tab.5 Result of each example by ALNS

不同規模的成本組成分析如圖3所示。各成本隨總距離的增加而增加，綠色成本里包含油耗使得占有總成本的最高比例。

圖3 成本分析Fig.3 Cost analysis

各規模配送方案的迭代次數如圖4所示。在前50次，配送成本迅速收斂，1 000節點配送方案最先趨于穩定，800節點其次，400節點最后。在迭代450次之后，各規模配送成本趨于穩定。

圖4 收斂曲線Fig.4 Convergence curves

ALNS算法執行中各算子的使用情況如表6所示。destroy和repair各類型算子中Random Destroy算子和Greedy Repair算子被選擇概率最高，Random Destroy算子對于路徑的重組作用較為全面，可獲得更客觀的當前解，避免所得解陷入局部最優，Greedy Repair算子對于更全面的當前解進行優化，其改進效果明顯優于Random Repair算子和Regret Repair算子。

表6 各算子使用情況(單位：%)Tab.6 Usage of each operator (unit: %)

5 結論

以天津市生鮮配送為研究背景，結合大規模鄰域搜索算法，考慮路徑優化與配送成本，建立了以時間、路程、能耗最小為優化目標的車輛調度模型，并通過輪盤賭法與模擬退火算法的接受準則進行優化求解，得到以下結論：

(1)生鮮電商產地直銷模式的興起，使得生鮮產品配送規模不斷擴大，由此考慮外界環境溫度變化下制冷能耗的變動情況，為冷鏈運輸中的溫度控制提供一定幫助，豐富了生鮮配送路徑優化的研究內容。

(2)在需求點規模龐大的路徑優化問題上，針對LNS在搜索過程中易陷入局部解的缺陷，用ALNS對于不同操作的算子進行概率選擇，經Metropolis接受準則得到全局最優解，求得不同客戶點規模的調度路線。

(3)在路徑優化的算法檢驗中，ALNS的配送成本明顯低于LNS與TS算法，證實了ALNS在配送時間、配送距離、配送能耗等方面均有較好的結果，并利用提出的車輛調度模型解決了天津市某生鮮電商產品配送問題。

(4)從路徑優化的收斂曲線與算子使用情況來看，迭代次數前200次解的優化效果最為明顯，這表明ALNS對處理大規模的車輛調度問題有一定可行性。Greedy插入算子使用率最高表明初始解構造的好壞對最終結果有一定影響。

本研究為基于溫區細化的大規模生鮮配送提供了理論基礎，但僅考慮了外部環境溫度的變化，未考慮路網擁堵情況的影響，這將是今后本研究的努力方向。