考慮碳排放和時間窗的冷鏈物流配送路徑優(yōu)化研究

江云倩，楊慧敏，彭程，趙文

考慮碳排放和時間窗的冷鏈物流配送路徑優(yōu)化研究

江云倩，楊慧敏*，彭程，趙文

（東北林業(yè)大學(xué) 土木與交通學(xué)院，哈爾濱 150000）

確保生鮮農(nóng)產(chǎn)品在短時間內(nèi)完成從配送中心到客戶點(diǎn)的配送，提高配送效率，降低配送成本。綜合考慮溫度變化對卸貨過程中生鮮腐爛率的影響，運(yùn)輸過程和冷藏過程中的碳排放成本，以及違反時間窗的懲罰成本等因素，構(gòu)建配送成本最小化模型，引入碳稅機(jī)制定量分析碳排放成本，運(yùn)用改進(jìn)的自適應(yīng)遺傳算法進(jìn)行求解，并對碳排放價格進(jìn)行靈敏度分析。優(yōu)化后的總配送成本相較于優(yōu)化前減少了3.8%，碳排放成本相較于優(yōu)化前減少了27.8%，總配送時間相較于優(yōu)化前減少了3.3%。優(yōu)化后的遺傳算法在降低配送成本和碳排放成本上具有顯著效果，可以通過合理控制碳排放價格等手段來降低配送成本和碳排放成本。

冷鏈物流；路徑優(yōu)化；碳排放；遺傳算法

自2020 年中國提出“碳達(dá)峰、碳中和”以來，各行各業(yè)掀起了一波綠色發(fā)展的浪潮。交通運(yùn)輸業(yè)的碳排放量占全社會總碳排放量的比例較大，除了大力發(fā)展新能源，優(yōu)化物流和運(yùn)輸路線也是降低碳排放的有效途徑[1]。特別是優(yōu)化具有高能耗和高時間效率要求的冷鏈物流路徑，對于節(jié)約能源、減少碳排放、尋求可持續(xù)的經(jīng)濟(jì)和環(huán)境發(fā)展具有重要意義[2-3]。

為了解決冷鏈運(yùn)輸過程中高排放、高能耗的問題，Ning等[4]將碳排放成本引入基本配送成本中，建立了綜合成本最小化模型，從而提出一種改進(jìn)的量子細(xì)菌覓食優(yōu)化算法。Deng等[5]綜合考慮了冷藏車車門打開時冷熱空氣對流對產(chǎn)品腐壞率的影響，以及冷藏運(yùn)輸過程中產(chǎn)生的碳排放成本，利用改進(jìn)的遺傳算法求解，對不同客戶需求進(jìn)行了敏感性分析。從易腐食品的時效性和品質(zhì)角度出發(fā)，高浩然等[6]構(gòu)建了一個優(yōu)化易腐品配送路徑的模型，該模型以最小化配送成本為目標(biāo)函數(shù)，并在傳統(tǒng)遺傳算法的基礎(chǔ)上引入了局部搜索操作來解決該問題。鄒建成等[7-10]眾多學(xué)者都考慮到碳排放因素對車輛路徑選擇的影響，并將其納入數(shù)學(xué)模型中。

1959年，Ramser和Dantzig等[11]首次提出車輛路徑問題，自此越來越多學(xué)者聚焦于這一重要的研究領(lǐng)域。在優(yōu)化物流路徑時，通常只考慮車輛的固定成本和基本的運(yùn)輸成本，而忽略了其他潛在的成本因素。隨著現(xiàn)代經(jīng)濟(jì)技術(shù)的發(fā)展，以及人們對食品安全問題的日益重視，在生鮮農(nóng)產(chǎn)品冷鏈物流配送過程中越來越多地關(guān)注到時間因素的影響。Solomon和Desrosiers等[12]首次將帶有時間窗的約束條件應(yīng)用于車輛路徑，為未來生鮮物流車輛的路徑規(guī)劃提供了有益指引。在全面考慮運(yùn)輸成本、固定成本、貨損成本等多種因素的基礎(chǔ)上，葛顯龍等[13]構(gòu)建了帶有時間窗生鮮損耗的配送模型，并利用自適應(yīng)遺傳算法對其進(jìn)行了求解。在考慮新鮮度、多產(chǎn)品、多車型情景下的配送中心選址–路徑優(yōu)化問題時，劉琳等[14]提出了一個雙層規(guī)劃模型，并結(jié)合模型特點(diǎn)，運(yùn)用兩階段啟發(fā)式算法對其進(jìn)行求解。李澤華[15]、Zhu等[16]建立了帶有時間窗約束的路徑優(yōu)化模型。

在以往的研究中，很多學(xué)者只考慮了碳排放因素或時間窗約束，全面綜合考慮兩者共同的影響并建立數(shù)學(xué)模型的研究較少，文中從這個角度出發(fā)，構(gòu)建考慮時間窗和碳排放約束的配送成本最小化模型，采用優(yōu)化的遺傳算法進(jìn)行求解，并通過實(shí)際案例驗(yàn)證該模型的有效性。

1 問題描述與模型建立

1.1 問題描述與假設(shè)

這里研究的冷鏈物流路徑優(yōu)化問題是在傳統(tǒng)路徑優(yōu)化模型的基礎(chǔ)上引入時間窗和碳排放約束。該問題可描述為：由1個配送中心向多個客戶點(diǎn)配送貨物，客戶點(diǎn)的位置、需求量、時間窗等信息已知，車輛統(tǒng)一從配送中心出發(fā)，在滿足客戶需求、時間窗約束和車輛載重等約束條件的同時，將碳排放成本引入總成本，以總成本最小為目標(biāo)，合理規(guī)劃配送路線。文中提出以下假設(shè)：配送中心冷藏車輛的數(shù)量有限，冷藏車輛具有容量限制，且不得超載；考慮交通擁堵情況，車輛在不同時間段的行駛速度不同；隨著時間的推移，貨物的新鮮度下降，將產(chǎn)生一定的貨損成本；冷藏車輛的起點(diǎn)和終點(diǎn)都是配送中心。

1.2 符號和參數(shù)

1）集合。表示配送中心和客戶點(diǎn)集合，={0, 1, 2, ...,}；表示配送中心所有車輛的集合，={0, 1, 2, ...,}；、表示節(jié)點(diǎn)索引，,={1, 2, 3, ...,}；表示車輛索引，={1, 2, 3, ...,}。

1.3 數(shù)學(xué)模型

以總配送成本最小為目標(biāo)的數(shù)學(xué)模型見式（1）～（12）。

s.t.

如果車輛服務(wù)完客戶點(diǎn)后，則表示下一個客戶點(diǎn)，見式（13）。

式（1）為目標(biāo)函數(shù)，表示總配送成本最小。式（2）表示冷藏運(yùn)輸車輛的固定成本。式（3）表示車輛的運(yùn)輸成本。式（4）表示貨損成本。式（5）表示車輛制冷成本。式（6）表示懲罰成本。式（7）表示碳排放成本。式（8）表示配送車輛共有輛。式（9）表示車輛從配送中心出發(fā)，完成配送后回到配送中心。式（10）表示車輛行駛距離約束。式（11）表示客戶點(diǎn)的數(shù)量。式（12）表示車輛載重約束。式（13）表示配送過程是連續(xù)的。

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

為了能更有效地求解上述目標(biāo)函數(shù)，采用隨機(jī)遍歷抽樣選擇算子代替?zhèn)鹘y(tǒng)遺傳算法中的輪盤賭選擇，并引入自適應(yīng)的交叉變異算子。利用精英保留策略保護(hù)最優(yōu)解，改進(jìn)了遺傳過程中的交叉變異方式，相關(guān)算法流程如下。

2.1 染色體編碼

采用自然數(shù)編碼，編號0代表配送中心，編號1, 2, ...,為客戶點(diǎn)。當(dāng)客戶點(diǎn)數(shù)量為、冷藏車數(shù)量為時，染色體長度為++1。

2.2 種群初始化及適應(yīng)度函數(shù)

在通常情況下，種群的初始規(guī)模被設(shè)定在30～150之間。當(dāng)種群數(shù)量不足或較大時，均會降低算法的運(yùn)行效率。隨機(jī)函數(shù)生成法的種群生成速度較快、計(jì)算難度較小，所以這里采取此種方法生成初始種群規(guī)模為100的種群。

在遺傳算法中，適應(yīng)度函數(shù)是度量個體質(zhì)量好壞的標(biāo)準(zhǔn)之一，種群中個體的適應(yīng)度越高，則個體表現(xiàn)越好，因此這里將適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)，見式（14）。

式中：fitness()為染色體的適應(yīng)度函數(shù)；E為染色體的目標(biāo)函數(shù)；P為種群數(shù)目。

2.3 選擇算子

這里采用精英保留策略與隨機(jī)遍歷抽樣選擇法相結(jié)合的方法，如圖1所示。為了避免父代的優(yōu)良基因被后續(xù)的交叉變異操作破壞，運(yùn)用精英保留策略將每代的最優(yōu)值進(jìn)行存儲，防止優(yōu)秀解的流失，從而提高算法的運(yùn)行效率。

采用隨機(jī)遍歷抽樣選擇法，在選擇時可以同時使用多個選擇點(diǎn)，1次即可選出所有個體。每個選擇點(diǎn)之間都是等距的，每個選擇點(diǎn)之間的距離用累計(jì)適應(yīng)度除以需要選擇的個體數(shù)得到。起始點(diǎn)在[0,/]之間隨機(jī)產(chǎn)生，然后再等距離產(chǎn)生其他選擇點(diǎn)。

圖1 隨機(jī)遍歷選擇操作

2.4 交叉算子

在父代中，隨機(jī)設(shè)定2個交叉點(diǎn)，將2個個體交叉點(diǎn)之間的基因分別放到另一個個體的最前邊，然后刪除2個個體中與插入部分相同的基因，從而生成2個新個體。具體操作如圖2所示。在進(jìn)行交叉操作后，需要對新生成的子代進(jìn)行評估。若新生成的子代的適應(yīng)度優(yōu)于父代，則直接將交叉后的子代納入下一代種群；反之，則需進(jìn)行變異。

2.5 變異算子

將逆轉(zhuǎn)變異和插入變異2種策略相結(jié)合，具體操作如下。

1）在父代中隨機(jī)選取2個逆轉(zhuǎn)點(diǎn)，將它們之間的基因進(jìn)行逆向排序，如圖3所示。

圖2 交叉過程

圖3 逆轉(zhuǎn)變異操作

2）在父代中隨機(jī)挑選2個點(diǎn)、，將插到位置前面。具體操作如圖4所示。

圖4 插入變異操作

在進(jìn)行逆轉(zhuǎn)和插入變異后，比較變異后染色體的適應(yīng)度。若變異后染色體的適應(yīng)度優(yōu)于上一代的適應(yīng)度，則直接將其納入下一代種群，與其他適應(yīng)度較高的染色體共同構(gòu)成新的種群；反之，則保留上一代在交叉后得到的染色體。通過這種策略，可以確保每代種群都由適應(yīng)度較高的染色體組成，從而逐步優(yōu)化整個種群的適應(yīng)度水平。

3 實(shí)例驗(yàn)證

3.1 基礎(chǔ)數(shù)據(jù)

以山東省臨沂市某區(qū)某生鮮產(chǎn)品配送中心為研究對象，配送中心需向20個客戶點(diǎn)配送生鮮產(chǎn)品。配送中心和客戶點(diǎn)信息如表1所示，配送中心的坐標(biāo)為（39 020，396 178.5），配送中心共有10輛福田奧鈴冷藏運(yùn)輸車。參數(shù)設(shè)置：車輛的固定成本k=220元，冷藏車在7:30至8:30之間的速度=25 km/h，在其他時間段的車速為30 km/h[17]。車輛載質(zhì)量m=1 500 kg，生鮮產(chǎn)品的價格1=8元/kg，冷藏車單位制冷成本2=2元/h[18]，燃油價格3=6.8元/L，CO2排放系數(shù)=2.67 kg/L，車輛行駛單位距離產(chǎn)生的碳排放=0.007 5 kg/km，碳稅CO2=50元/t，車廂體裂化程度=0.08，車廂內(nèi)外溫度差Δ=20 ℃，懲罰成本1=40元/h，2=80元/h，車輛的燃料消耗0=0.13 L/km，γ=0.18 L/km，傳熱率=2.89 W/(m2·k)，車廂體受太陽輻射的面積=36 m2，車廂體積k=4 160 mm×2 180 mm× 2 180 mm，生鮮農(nóng)產(chǎn)品的腐壞率1=0.002，2=0.003，開門頻度系數(shù)=0.625。

表1 客戶信息

Tab.1 Customer information sheet

3.2 對比分析

采用Matlab R2020a軟件進(jìn)行編程，利用上述算例分別對優(yōu)化前后的遺傳算法進(jìn)行仿真試驗(yàn)。設(shè)置種群規(guī)模為100，交叉概率為0.9，變異概率為0.2，最大迭代次數(shù)為400。在仿真試驗(yàn)后，得到該算例在2種算法下的最優(yōu)規(guī)劃路徑。運(yùn)行結(jié)果如圖5、圖6所示，結(jié)果分析如表2、表3所示。

圖5 算法優(yōu)化前運(yùn)行結(jié)果

圖6 算法優(yōu)化后運(yùn)行結(jié)果

表2 算法優(yōu)化前、后最優(yōu)配送路線

Tab.2 Optimal delivery route before and after algorithm optimization

表3 算法優(yōu)化前后求解結(jié)果對比

Tab.3 Comparison of results before and after optimization

根據(jù)表2、表3可以看出，在算法優(yōu)化前后，配送中心向客戶配送貨物都需要派出6輛冷藏運(yùn)輸車，均未超出車輛上限，但算法在優(yōu)化前后的迭代次數(shù)和車輛路徑的安排上呈現(xiàn)出明顯差異：在迭代次數(shù)方面，優(yōu)化前的遺傳算法在迭代到240代左右開始收斂，而優(yōu)化后在170代左右便開始收斂，優(yōu)化后遺傳算法收斂過程更加平穩(wěn)、收斂速度更快、效率更高；不管是在總配送時間、總里程、碳排放成本，還是總成本上，優(yōu)化后路徑都優(yōu)于優(yōu)化前，優(yōu)化后的總成本減少了3.8%，碳排放成本減少了27.8%，車輛行駛的總路程減少了10.3%，總配送時間減少了3.3%。在車輛運(yùn)行時，使用固定速度和時變速度所耗費(fèi)的成本不同，分析結(jié)果如表4所示。

表4 不同速度的成本對比

Tab.4 Cost comparison of different speeds

由表4可知，在保證配送貨物準(zhǔn)點(diǎn)率的情況下，在冷藏車運(yùn)輸過程中采用時變速度的配送總成本相較于固定速度減少了3.2%，碳排放成本降低了21.2%。由此可見，采用時變速度降低碳排放成本和配送總成本更符合車輛在現(xiàn)實(shí)中的運(yùn)行狀況，更具有實(shí)際意義。

4 碳排放價格靈敏度分析

碳稅價格的變化會導(dǎo)致碳排放成本發(fā)生變化，碳排放成本的變化也會影響運(yùn)輸車輛的路徑安排。在求解文中模型時，設(shè)定碳稅價格為0.05元/kg，現(xiàn)將碳稅價格設(shè)計(jì)為0.01、0.03、0.08、0.1 元/kg等不同情況進(jìn)行求解，分別運(yùn)行5 次，取其平均值進(jìn)行分析，結(jié)果如表5、圖7所示。

首先，由圖7中的誤差線可以看出，總配送成本和碳排量的數(shù)據(jù)分布較均勻，離散程度較低，說明優(yōu)化后算法的穩(wěn)定性較好。其次，從表5、圖7可以看出，碳稅價格與配送總成本成正比，碳稅價格與碳排放量成反比。當(dāng)碳價格增長到0.05元/kg時，碳排放成本的增加幅度遠(yuǎn)大于碳排量的減少幅度。由此可以看出，隨著碳稅價格的攀升，企業(yè)所面臨的碳排放成本增加幅度遠(yuǎn)遠(yuǎn)超過了碳排放量的減少幅度，表明降低碳排放量并不能簡單地提高碳稅價格，而是需要在一定范圍內(nèi)進(jìn)行控制，合理的碳稅價格對于企業(yè)減少碳排放量、降低運(yùn)輸成本具有重要的價值和意義。

表5 碳稅價格對總配送成本和碳排放量的影響

Tab.5 Effect of carbon tax price on total cost and carbon emissions

圖7 總成本和碳排放量隨碳稅價格變化的趨勢

5 結(jié)語

隨著冷鏈物流行業(yè)的迅速發(fā)展，基于冷鏈物流高能耗和高時間效率要求的特性，研究了冷鏈物流路徑優(yōu)化問題。首先，在傳統(tǒng)路徑優(yōu)化模型的基礎(chǔ)上，引入時間窗和碳排放約束。其次，對碳排放成本進(jìn)行了定量分析，構(gòu)建了路徑優(yōu)化模型，將總成本最小化作為優(yōu)化目標(biāo)。最后，利用改進(jìn)的遺傳算法對該模型進(jìn)行求解。結(jié)果表明，與傳統(tǒng)遺傳算法相比，改進(jìn)后的遺傳算法對求解考慮碳排放和時間窗2個約束條件下的配送路徑優(yōu)化問題具有更好的適應(yīng)性和收斂性；縮短了配送時間，提高了配送效率，可以保證在客戶要求的時間窗內(nèi)完成配送任務(wù)，并進(jìn)一步降低了配送總成本和碳排放成本；時變速度可以在保證準(zhǔn)點(diǎn)率的情況下降低碳排放成本和配送總成本，可見文中研究更符合實(shí)際情況；在研究中引入碳稅制度定量分析碳排放成本，可以更好地衡量企業(yè)的碳排放成本，分析配送成本和碳排放量如何隨碳稅價格變化。

[1] XIE Y L, LI Y Y. Optimizing Method of Cold Link Path for Agricultural Products Transportation Facing Environmental Protection[J]. Ekoloji, 2019, 28(107): 2083-2095.

[2] SHEN Y. Optimization of Urban Logistics Distribution Path under Dynamic Traffic Network[J]. International Core Journal of Engineering, 2020, 6(1): 243-248.

[3] WANGJ X. Research on the Optimization of Path Information in the Process of Logistics Distribution by Improved Ant Colony Algorithm[J]. Italian Journal of Pure and Applied Mathematics, 2019, 2019(41): 343-352.

[4] NING T, AN L, DUAN X D. Optimization of Cold Chain Distribution Path of Fresh Agricultural Products under Carbon Tax Mechanism: A Case Study in China[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40(6): 10549-10558.

[5] DENG H X, WANG M, HU Y, et al. An Improved Distribution Cost Model Considering Various Temperatures and Random Demands: A Case Study of Harbin Cold-Chain Logistics[J]. IEEE Access, 2021, 9: 105521-105531.

[6] 高浩然, 張玉林, 張順順. 考慮時效性和品質(zhì)性滿意度約束的易腐品冷鏈物流配送研究[J].控制與決策, 2023, 38: 1-10.

GAO H R, ZHANG Y L, ZHANG S S. Study on Cold Chain Logistics Distribution of Perishable Products Considering Constraints of Timeliness and Quality Satisfaction[J]. Control and Decision, 2023, 38: 1-10.

[7] 鄒建城, 路正南. 考慮碳排放的生鮮農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J]. 物流科技, 2019, 42(8): 46-52.

ZOU J C, LU Z N. Optimization Research of Cold Chain Distribution Routes Based on Carbon Emissions for Fresh Agricultural Products[J]. Logistics Sci-Tech, 2019, 42(8): 46-52.

[8] FU Q M, LI J, CHEN H H. Resource Scheduling Method for Optimizing the Distribution Path of Fresh Agricultural Products under Low-Carbon Environmental Constraints[J]. Scientific Programming, 2022, 2022: 7692135.

[9] LIU Z, GUO H X, ZHAO Y J, et al. Research on the Optimized Route of Cold Chain Logistics Transportation of Fresh Products in Context of Energy-Saving and Emission Reduction[J]. Mathematical Biosciences and Engineering: MBE, 2021, 18(2): 1926-1940.

[10] 李想, 閔德權(quán), 張祺. 隨機(jī)需求下半開放式冷鏈物流車輛路徑優(yōu)化[J]. 包裝工程, 2022, 43(7): 160-169.

LI X, MIN D Q, ZHANG Q. Routing Optimization of Semi-Open Cold-Chain Logistics Vehicle under Random Demand[J]. Packaging Engineering, 2022, 43(7): 160-169.

[11] DANTZIG G B, RAMSER J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.

[12] SOLOMON M M, DESROSIERS J. Survey Paper—Time Window Constrained Routing and Scheduling Problems[J]. Transportation Science, 1988, 22(1): 1-13.

[13] 葛顯龍, 孔陽. 帶有時間窗的生鮮物流配送路徑優(yōu)化研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識, 2016, 46(12): 78-87.

GE X L, KONG Y. Research on the Vehicle Routing Problem of Fresh Logistics Distribution with Time Window[J]. Mathematics in Practice and Theory, 2016, 46(12): 78-87.

[14] 劉琳, 賈鵬, 高犇, 等. 新鮮度限制約束下物流配送中心選址-路徑優(yōu)化[J]. 包裝工程, 2022, 43(5): 232-241.

LIU L, JIA P, GAO B, et al. Location Routing Optimization of Logistics Distribution Center under Freshness Limitation[J]. Packaging Engineering, 2022, 43(5): 232-241.

[15] 李澤華. 帶時間窗約束的生鮮產(chǎn)品配送車輛路徑優(yōu)化問題研究[D]. 大連: 大連海事大學(xué), 2009: 21-31.

LI Z H. The Study on Vehicle Routing Problem with Time Windows for Fresh Product[D]. Dalian: Dalian Maritime University, 2009: 21-31.

[16] ZHU A Q, WEN Y Y. Green Logistics Location-Routing Optimization Solution Based on Improved GA A1gorithm Considering Low-Carbon and Environmental Protection[J]. Journal of Mathematics, 2021, 2021: 6101194.

[17] 林殿盛. 生鮮農(nóng)產(chǎn)品低碳冷鏈物流網(wǎng)絡(luò)優(yōu)化研究[D]. 廣州: 華南理工大學(xué), 2021: 71-124.

LIN D S. Research on Optimization of Low Carbon Cold Chain Distribution Network for Fresh Agricultural Products[D]. Guangzhou: South China University of Technology, 2021: 71-124.

[18] 白雪. 考慮碳交易與新能源車輛的多車型冷鏈物流配送優(yōu)化研究[D]. 北京: 北京交通大學(xué), 2021: 51-70.

BAI X. Research on Optimization of Multi-Vehicle Cold Chain Logistics Distribution Considering Carbon Trading and New Energy Vehicles[D]. Beijing: Beijing Jiaotong University, 2021: 51-70.

Optimization of Cold Chain Logistics Distribution Route Considering Carbon Emission and Time Window

JIANG Yunqian,YANG Huimin*,PENG Cheng,ZHAO Wen

(School of civil Engineering and Transportation, Northeast Forestry University, Harbin 150000, China)

The work aims to ensure that fresh agricultural products can be distributed from the distribution center to the customer site in a short time, improve the distribution efficiency and reduce the distribution cost. With comprehensively consideration to the influence of temperature change on the fresh decay rate during unloading, the carbon emission cost during transportation and refrigeration, and the cost of violating the time window, a minimum distribution cost model was constructed. The carbon tax mechanism was introduced to analyze the carbon emission cost quantitatively. The optimization genetic algorithm was used to solve the problem to analyze the sensitivity of carbon emission price. The results showed that the optimized distribution cost was reduced by 3.8%. Compared with that before optimization, the carbon emission cost was reduced by 27.8%. The delivery time was 3.3% shorter than that before optimization. The optimized genetic algorithm is effective in reducing distribution cost and carbon emission cost. Distribution cost and carbon emission cost can be reduced through reasonable control of carbon emission price and other means.

cold chain logistics; path optimization; carbon emissions; genetic algorithm

F252；TP18

A

1001-3563(2024)03-0262-07

10.19554/j.cnki.1001-3563.2024.03.030

2023-05-05

中央高校業(yè)務(wù)經(jīng)費(fèi)（2572016CB11）；校級教育教學(xué)研究項(xiàng)目（DGY2020-42）