基于溫區(qū)細(xì)化的多溫共配車(chē)輛路徑優(yōu)化

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

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

0 引言

生鮮產(chǎn)品隨外界溫度變化，品質(zhì)受較大影響，其保質(zhì)期與食品的特性、儲(chǔ)藏溫度和時(shí)間密切相關(guān)[1]。多溫共配車(chē)輛長(zhǎng)時(shí)間配送所處的環(huán)境溫度會(huì)有較大波動(dòng)，制冷機(jī)的能耗隨外界溫度變化而改變[2]。為探討外界溫度變化對(duì)配送車(chē)能耗的影響，提出溫區(qū)細(xì)化(指動(dòng)態(tài)環(huán)境溫度對(duì)制冷能耗的影響)的配送車(chē)溫控問(wèn)題。

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

1 問(wèn)題描述

配送流程中對(duì)溫度的控制不能得到保證，導(dǎo)致生鮮農(nóng)產(chǎn)品新鮮度衰減加快，造成不必要的浪費(fèi)和冷鏈成本提高。為有效控制整個(gè)冷鏈運(yùn)輸中的溫度變化，減少生鮮農(nóng)產(chǎn)品新鮮度損失速率，綜合考慮碳排放、客戶服務(wù)時(shí)間約束、制冷成本等因素，進(jìn)行合理運(yùn)輸調(diào)度。

具體假設(shè)如下：

(1)配送中心擁有一定數(shù)量且規(guī)格相同的配送車(chē)，每輛車(chē)的裝載量有限且大于單個(gè)客戶點(diǎn)的需求量。

(2)各節(jié)點(diǎn)位置、需求量、配送時(shí)間窗及服務(wù)時(shí)間確定。

(3)同一配送車(chē)可進(jìn)行不同節(jié)點(diǎn)配送，每個(gè)節(jié)點(diǎn)僅配送1次且滿足客戶需求。

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

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

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

表1 溫度變化Tab.1 Temperature change

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

(1)

式中，σl為車(chē)內(nèi)的環(huán)境溫度；σh為車(chē)外環(huán)境溫度。為方便計(jì)算，利用開(kāi)爾文溫度替代攝氏度，表示為σ(K)。開(kāi)爾文溫度與攝氏度σ轉(zhuǎn)化關(guān)系為：

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

(2)

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

圖1 溫度細(xì)化的制冷系數(shù)相關(guān)圖Fig.1 Correlation diagrams of refrigeration coefficient for temperature refinement

2 模型建立

對(duì)生鮮農(nóng)產(chǎn)品配送的問(wèn)題假設(shè)及場(chǎng)景進(jìn)行描述后，建立生鮮農(nóng)產(chǎn)品配送模型。包括變量的定義、約束條件及目標(biāo)函數(shù)。

2.1 變量定義

生鮮農(nóng)產(chǎn)品配送中有關(guān)變量參數(shù)的定義如表2所示。

2.2 成本分析

2.2.1固定成本FC

配送車(chē)從配送中心出發(fā)用于支付駕駛員工資、車(chē)輛維修等費(fèi)用。

(3)

2.2.2運(yùn)輸成本TC

配送車(chē)正常行駛過(guò)程中的費(fèi)用。

表2 已知參數(shù)Tab.2 Known parameters

(4)

式中α為單位距離成本。

2.2.3綠色成本GC

配送車(chē)的綠色成本包括負(fù)載狀態(tài)下，配送途中消耗的燃油成本及產(chǎn)生的碳排放對(duì)環(huán)境造成污染的成本。

(1)油耗成本

利用負(fù)載估計(jì)法對(duì)配送車(chē)配送過(guò)程的油耗量進(jìn)行計(jì)算，確定負(fù)載與能耗之間的關(guān)系[10]。其油耗關(guān)系式為：

(5)

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

油耗Oil和油耗成本OC的表達(dá)式為:

(6)

OC=H·Oil，

(7)

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

(2)碳排放成本

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

CC=β·γ·Oil，

(8)

GC=OC+CC

(9)

式中，β為碳稅；γ為碳排放系數(shù)。

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

(4)溫控成本TCC

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

①裝配前對(duì)配送車(chē)預(yù)冷成本PC

生鮮農(nóng)產(chǎn)品從產(chǎn)地采摘下來(lái)到分揀包裝運(yùn)上配送車(chē)前，根據(jù)車(chē)內(nèi)溫度與車(chē)外溫度，需對(duì)內(nèi)部進(jìn)行預(yù)冷操作，抑制其呼吸熱，延緩新鮮度衰減。

(10)

式中ησl,σh為車(chē)內(nèi)溫度σl與車(chē)外溫度σh相對(duì)應(yīng)的制冷系數(shù)。

②配送過(guò)程制冷成本DRC

配送車(chē)k從i到j(luò)的運(yùn)輸時(shí)間tijk內(nèi)車(chē)內(nèi)溫度σl與車(chē)外溫度σh變化所產(chǎn)生的制冷成本DRC為：

(11)

③裝卸過(guò)程制冷成本LRC

(12)

④溫控總成本TCC：

TCC=PC+DRC+LRC。

(13)

(5)貨損成本TL

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

Ω(t)=Ωoe-ωt，

(14)

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

新鮮度衰減系數(shù)通常與產(chǎn)品的呼吸熱、周?chē)鷾囟扔嘘P(guān)，在裝卸過(guò)程中車(chē)廂門(mén)打開(kāi)使車(chē)廂內(nèi)外溫差及氧氣含量變大，生鮮產(chǎn)品新鮮度衰減速率加快從而得知ω2>ω1。其貨損成本表達(dá)式為：

(15)

(16)

式中，SL為生鮮配送過(guò)程的損失成本；HL為裝卸過(guò)程的損失成本；ω1為貨物在配送過(guò)程中的新鮮度衰減系數(shù)；ω2為貨物在裝卸過(guò)程中的新鮮度衰減系數(shù)。衰減系數(shù)通常與產(chǎn)品的呼吸熱、周?chē)鷾囟扔嘘P(guān)，在裝卸過(guò)程中車(chē)廂門(mén)打開(kāi)使車(chē)廂內(nèi)外溫差及氧氣含量變大，生鮮產(chǎn)品新鮮度衰減速率加快，從而得知ω2>ω1，Wir為車(chē)輛離開(kāi)客戶點(diǎn)i時(shí)車(chē)上剩余貨物重量；Di為客戶i需求量；Ti為在客戶i的裝卸時(shí)間。

TL=SL+HL。

(17)

基于溫度細(xì)化的生鮮農(nóng)產(chǎn)品配送模型的目標(biāo)函數(shù)：

(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)表示各客戶點(diǎn)需求量之和不超過(guò)配送中心最大配送量，S為配送中心最大配送量；式(20)表示每個(gè)客戶點(diǎn)只能訪問(wèn)1次；式(21)表示每輛車(chē)的配送量不超過(guò)最大載重量；wi為各客戶點(diǎn)需求量；式(22)～(23)表示所有客戶的需求量得到滿足；式(24)表示車(chē)輛k從配送中心o出發(fā)，完成客戶點(diǎn)j配送任務(wù)后返回到配送中心；式(25)～(26)表示任意節(jié)點(diǎn)只允許車(chē)輛出發(fā)到達(dá)1次，Yjk為配送車(chē)k為客戶點(diǎn)j服務(wù)；式(27)表示配送車(chē)輛達(dá)到時(shí)間必須為最大容忍時(shí)間窗內(nèi)；式(28)表示消除子回路，L為任兩點(diǎn)間的回路總數(shù)；式(29)表示配送的過(guò)程是連續(xù)的，Tj為到達(dá)客戶點(diǎn)j的時(shí)間，Ti為到達(dá)客戶i的時(shí)間，Tij為兩點(diǎn)間行駛時(shí)間；式(30)為其約束條件。

3 算法設(shè)計(jì)

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

圖2 ALNS優(yōu)化流程圖Fig.2 Flowchart of ALNS optimization

3.1 初始解的構(gòu)造

為提高生鮮配送模型優(yōu)化效率，采用貪心算法構(gòu)造初始解。以時(shí)間窗和配送容量為約束，通過(guò)初始化的距離矩陣，尋找距離節(jié)點(diǎn)i+1最近節(jié)點(diǎn)i直至遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)得到VRPTW初始解。

3.2 算子移除操作

通過(guò)不同方法對(duì)初始解配送路線中節(jié)點(diǎn)進(jìn)行移除。

(1)隨機(jī)移除：選擇一定數(shù)量節(jié)點(diǎn)移除，增加搜索過(guò)程多樣性。

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

(3)Shaw移除[15]：考慮相關(guān)度高的節(jié)點(diǎn)，r(i,j)為任兩點(diǎn)p和q間的相關(guān)程度；θ1，θ2，θ3，θ4分別為節(jié)點(diǎn)間距離d、時(shí)間T、載重量G、配送車(chē)輛k的權(quán)重系數(shù)。若相關(guān)程度越高，則移除該組節(jié)點(diǎn)的可能性越大，在后續(xù)重新構(gòu)造更優(yōu)解時(shí)增加多樣性和隨機(jī)性，如式(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)隨機(jī)插入：相似于隨機(jī)移除，選擇一定數(shù)量節(jié)點(diǎn)進(jìn)行插入，增加多樣性。

(2)貪心插入：不斷將被移除節(jié)點(diǎn)插入到使目標(biāo)函數(shù)值最小的位置上，與構(gòu)造初始解的方法相同。

(3)最少成本插入：Δfi為客戶i插入到第i′個(gè)節(jié)點(diǎn)后，目標(biāo)成本增加的變化量為Δfi=max(fi-f′i)。

3.4 最優(yōu)解篩選

利用輪盤(pán)賭法對(duì)不同算子表現(xiàn)情況所占的比例概率進(jìn)行選擇[16]。τ1為產(chǎn)生新的全局最優(yōu)解；τ2為產(chǎn)生新解但對(duì)應(yīng)的目標(biāo)函數(shù)值劣于當(dāng)前解；τ3為產(chǎn)生非改進(jìn)解但被接受。分?jǐn)?shù)排序?yàn)棣?>τ2>τ3。對(duì)各組算子對(duì)應(yīng)解的情況，新的最優(yōu)解概率最高，非改進(jìn)解概率最低。采用模擬退火算法的接受準(zhǔn)則對(duì)候選解進(jìn)行判斷，若目標(biāo)函數(shù)適應(yīng)度值Δf(x)<0，則更新當(dāng)前最優(yōu)解x，否則以概率exp(Δf(x)/T)接受X′作為新的當(dāng)前解[17]。

4 結(jié)果分析

4.1 算法檢驗(yàn)

利用Solomon算例，將禁忌搜索法(TS)[18]、大規(guī)模鄰域搜索法(LNS)與自適應(yīng)大規(guī)模鄰域搜索法(ALNS)進(jìn)行對(duì)比。得出每組車(chē)輛調(diào)度總配送路程結(jié)果，如表3所示。根據(jù)各算法結(jié)果表明LNS與ALNS計(jì)算優(yōu)于TS，ALNS的計(jì)算普遍結(jié)果優(yōu)于LNS計(jì)算，可得知使用ALNS算法對(duì)于求解VRPTW問(wèn)題具有一定的可行性。

表3 算法檢驗(yàn)Tab.3 Algorithm checking

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

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

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

4.2 成本分析

算法通過(guò)Win10系統(tǒng)的Eclipse(4.15.0)編程實(shí)現(xiàn)。得到不同規(guī)模的生鮮產(chǎn)品配送成本、制冷成本、貨損成本與綠色成本，如表5所示。配送成本包括固定成本與運(yùn)輸成本，由表5可得。調(diào)度中花費(fèi)比例占據(jù)最大為配送成本，最小為制冷成本。配送成本主要費(fèi)用為配送車(chē)配送的里程油耗及駕駛?cè)藛T工資，綠色成本涉及負(fù)載貨物配送造成的油耗，所占比例較大。隨著規(guī)模的增加，各項(xiàng)成本也呈倍數(shù)增加，綠色成本和貨損成本的增長(zhǎng)幅度更高，隨著客戶點(diǎn)規(guī)模擴(kuò)大，對(duì)于貨物需求量增大，其配送中出現(xiàn)不可避免的增加車(chē)次、載重油耗、運(yùn)輸油耗、駕駛員開(kāi)資等費(fèi)用。

表5 ALNS各算例結(jié)果Tab.5 Result of each example by ALNS

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

圖3 成本分析Fig.3 Cost analysis

各規(guī)模配送方案的迭代次數(shù)如圖4所示。在前50次，配送成本迅速收斂，1 000節(jié)點(diǎn)配送方案最先趨于穩(wěn)定，800節(jié)點(diǎn)其次，400節(jié)點(diǎn)最后。在迭代450次之后，各規(guī)模配送成本趨于穩(wěn)定。

圖4 收斂曲線Fig.4 Convergence curves

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

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

5 結(jié)論

以天津市生鮮配送為研究背景，結(jié)合大規(guī)模鄰域搜索算法，考慮路徑優(yōu)化與配送成本，建立了以時(shí)間、路程、能耗最小為優(yōu)化目標(biāo)的車(chē)輛調(diào)度模型，并通過(guò)輪盤(pán)賭法與模擬退火算法的接受準(zhǔn)則進(jìn)行優(yōu)化求解，得到以下結(jié)論：

(1)生鮮電商產(chǎn)地直銷(xiāo)模式的興起，使得生鮮產(chǎn)品配送規(guī)模不斷擴(kuò)大，由此考慮外界環(huán)境溫度變化下制冷能耗的變動(dòng)情況，為冷鏈運(yùn)輸中的溫度控制提供一定幫助，豐富了生鮮配送路徑優(yōu)化的研究?jī)?nèi)容。

(2)在需求點(diǎn)規(guī)模龐大的路徑優(yōu)化問(wèn)題上，針對(duì)LNS在搜索過(guò)程中易陷入局部解的缺陷，用ALNS對(duì)于不同操作的算子進(jìn)行概率選擇，經(jīng)Metropolis接受準(zhǔn)則得到全局最優(yōu)解，求得不同客戶點(diǎn)規(guī)模的調(diào)度路線。

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

(4)從路徑優(yōu)化的收斂曲線與算子使用情況來(lái)看，迭代次數(shù)前200次解的優(yōu)化效果最為明顯，這表明ALNS對(duì)處理大規(guī)模的車(chē)輛調(diào)度問(wèn)題有一定可行性。Greedy插入算子使用率最高表明初始解構(gòu)造的好壞對(duì)最終結(jié)果有一定影響。

本研究為基于溫區(qū)細(xì)化的大規(guī)模生鮮配送提供了理論基礎(chǔ)，但僅考慮了外部環(huán)境溫度的變化，未考慮路網(wǎng)擁堵情況的影響，這將是今后本研究的努力方向。