多配送中心半開放式冷鏈物流配送路徑優(yōu)化

摘要： 為了解決冷鏈物流服務(wù)的成本、質(zhì)量以及運輸產(chǎn)生的碳排放等問題，構(gòu)建多中心半開放式冷鏈物流路徑優(yōu)化模型，并將各種動態(tài)變化融入該模型中。設(shè)計一種改進的NSGA-II算法并利用標(biāo)準(zhǔn)測試函數(shù)證實該算法具有較好的收斂性與多樣性。通過算例實驗，結(jié)果表明：與不考慮碳排放方案相比，考慮碳排放方案的配送成本增加了19.00%，運輸距離減少了5.16%，碳排放成本降低了13.03%；與初始配送方案相比，實時優(yōu)化方案的配送成本下降了29.78%，碳排放成本下降了23.19%，客戶滿意度增幅14.49%；與單配送中心模式相比，多配送中心模式的配送成本降低了27.30%，碳排放成本降低了48.89%，客戶滿意度提高了13.11%，從而為冷鏈物流企業(yè)帶來一定的管理啟示。

關(guān)鍵詞： 冷鏈物流；多配送中心；動態(tài)路徑優(yōu)化；改進的NSGA-II算法

中圖分類號： U116.2;F542文獻標(biāo)識碼： A

Optimization of Multi-depot Half-open Cold Chain Logistics Distribution Path

JIANG Yuyan， YIN Li， WANG Fuyu

（School of Management Science and Engineering， Anhui University of Technology， Ma’anshan 243002， China）

Abstract：With the rapid development of the cold chain logistics industry， enterprises are paying more attention to the cost， quality of logistics services and carbon emissions generated by transportation. In order to solve this problem， a multi- depot half-open cold chain logistics routing optimization model is constructed， and various dynamic changes are integrated into the model. An improved NSGA-II algorithm is designed and the standard test function is used to prove that the algorithm has good convergence and diversity. The results show that， compared with the scheme without considering carbon emission， the distribution cost of the scheme with considering carbon emission increases by 19.00%， the transportation distance decreases by 5.16%， and the carbon emission cost decreases by 13.03%. Compared with the initial distribution scheme， the distribution cost of the real-time optimization scheme decreased by 29.78%， the carbon emission cost decreased by 23.19%， and the customer satisfaction increased by 14.49%. Compared with the single distribution center mode， the distribution cost of the multi-depot mode is reduced by 27.30%， the carbon emission cost is reduced by 48.89%， and the customer satisfaction is increased by 13.11%， which brings certain management enlightenment for cold chain logistics enterprises.

Keywords： cold chain logistics; multi-depot; dynamic path optimization; improved NSGA-II algorithm

0 引言

2020年9月，習(xí)近平總書記在第七十五屆聯(lián)合國大會上提出中國要力爭實現(xiàn)“雙碳”目標(biāo)。與一般物流不同，除了車輛行駛產(chǎn)生碳排放，制冷設(shè)備燃料消耗也會產(chǎn)生部分碳排放，故冷鏈配送產(chǎn)生的碳排放較多。為了實現(xiàn)“雙碳”目標(biāo)，政府和有關(guān)部門制定了碳稅政策，對冷鏈物流企業(yè)的低碳行為建立獎懲機制，比如低碳補貼、超額碳排放罰款等，這為企業(yè)在配送等環(huán)節(jié)進行有效的碳減排活動提供了長效的動力機制。因此，在“雙碳”背景的新發(fā)展格局下，追求可持續(xù)的、節(jié)能減耗的綠色物流將是冷鏈物流行業(yè)未來發(fā)展的新趨勢。

對冷鏈物流車輛路徑問題的研究一直受到眾多學(xué)者關(guān)注。Leng等［1］基于冷鏈物流，創(chuàng)建了考慮物流成本和車輛等待時間的低碳車輛路徑優(yōu)化數(shù)學(xué)模型。Liu G等［2］建立了一個考慮碳稅政策的聯(lián)合分銷綠色車輛路徑問題模型。Lian J［3］在冷鏈物流車輛路徑問題中考慮了模糊時間窗以及多個目標(biāo)函數(shù)。李倩等［4］建立了冷鏈物流配送路徑優(yōu)化模型，并采用NSGA-II算法對其求解。任騰等［5］在建立的冷鏈車輛路徑優(yōu)化模型中考慮了道路擁堵狀況，同時加入了客戶滿意度函數(shù)。白秦洋等［6］基于城市復(fù)雜的道路網(wǎng)與實時交通情況，構(gòu)建了考慮路網(wǎng)中實時交通的多目標(biāo)冷鏈物流路徑優(yōu)化模型。方文婷等［7］創(chuàng)建了包含綠色成本的冷鏈物流路徑優(yōu)化模型。

隨著越來越多的城市物流配送系統(tǒng)中出現(xiàn)多個配送中心，眾多學(xué)者把目光轉(zhuǎn)向多配送中心車輛路徑問題（Multi-Depot Vehicle Routing Problem，MDVRP）的研究上。Brando J等［8］選取迭代局部搜索算法解決多站點開放式車輛路徑問題。Yong W等［9］建立了一個多目標(biāo)兩級協(xié)作多站點多時段車輛路徑規(guī)劃模型。Fan H等［10］針對時變路網(wǎng)下的多站點車輛路徑問題，提出了總成本最小的整數(shù)規(guī)劃模型。隨著MDVRP研究的不斷深入，為了滿足客戶的時間窗要求，學(xué)者們開始研究了帶時間窗的MDVRP（Multi-Depot Vehicle Routing Problem with Time Windows，MDVRPTW）。廖列法等［11］建立了考慮客戶滿意度的多配送站低碳物流路徑規(guī)劃模型。范厚明等［12］通過混合遺傳算法解決了多配送中心開放式同時配集貨需求可拆分車輛路徑問題。王萬良等［13］設(shè)計了多配送中心車輛路徑問題的多智能體深度強化學(xué)習(xí)問題模型。針對是否為閉環(huán)，車輛路徑可分為封閉式車輛路徑問題和開放式車輛路徑問題（Open Vehicle Routing Problem，OVRP），封閉式是指車輛完成配送任務(wù)后必須返回原配送中心，OVRP是指車輛可根據(jù)需要選擇是否返回出發(fā)點，若返回則必須返回原配送中心。在OVRP中，又包含半開放式車輛路徑問題（Half Open Vehicle Routing Problem，HOVRP），其特點為車輛可就近駛回任一配送中心，不需要返回原配送中心，這樣可以減少運輸距離，降低產(chǎn)品損耗。張穎鈺等［14］構(gòu)建了以車輛配送距離最短為目標(biāo)的多中心半開放式送取需求可拆分的數(shù)學(xué)模型。

綜合來看，在實際物流配送環(huán)節(jié)中，不可避免地會發(fā)生交通擁堵、客戶需求變化等情況，而許多現(xiàn)有文獻并未綜合考慮各種動態(tài)事件的發(fā)生；同時關(guān)于半開放式多配送中心冷鏈物流車輛路徑問題的研究成果相對較少。因此，本文在多中心半開放式車輛路徑問題中，綜合考慮客戶時間窗變動、需求量變化、客戶訂單的刪除和新增以及交通中斷等多種動態(tài)因素，使模型更加貼近現(xiàn)代冷鏈物流企業(yè)配送活動的實際。同時，在冷鏈物流配送中建立多中心半開放式配送模式可快速響應(yīng)客戶需求，提高配送服務(wù)水平。此外，在傳統(tǒng)冷鏈物流配送模型的基礎(chǔ)上考慮客戶滿意度和碳排放，響應(yīng)綠色物流的發(fā)展理念，有利于冷鏈物流企業(yè)的可持續(xù)發(fā)展。為了求解所建模型，結(jié)合粒子群算法生成種群方式，設(shè)計一種改進的NSGA-II算法，經(jīng)過標(biāo)準(zhǔn)測試函數(shù)驗證，該算法具有較好的收斂性與多樣性。

1 問題描述與模型構(gòu)建

1.1 問題描述

研究問題可描述為：某冷鏈配送企業(yè)存在多個配送中心，且都配有一定數(shù)量的冷藏車輛，在不超過最大載貨量的前提下，根據(jù)配送途中可能出現(xiàn)的客戶時間窗變化、需求量變化、配送路徑發(fā)生交通中斷等信息變化動態(tài)調(diào)整配送路線，最終實現(xiàn)總配送成本最小、碳排放成本（碳稅與碳排放的乘積）最小以及客戶滿意度最大的目標(biāo)。

模型假設(shè)：1）配送中心不存在冷藏車輛不夠使用的情況；2）已知車輛的最大載重量等信息，且只有一種車型；3）車輛將貨物送達后可以到最近的配送中心添加貨物，繼續(xù)為下一客戶提供配送服務(wù)；4）車輛的行駛速度全程保持不變；5）配送中心和需求點的信息已知；6）每個客戶只能由一輛車配送一次。

相關(guān)參數(shù)說明：M=1，2，…，Kh：配送冷藏車輛的集合；

N=1，2，…，n：需要服務(wù)的客戶數(shù)的集合；

H=n+1，n+2，…，n+H：配送中心數(shù)量集合；

U=i，j：弧集合；

Khh=1，2，…H：每個配送中心的冷藏車數(shù)量；

Qk：配送車輛k的容量；

dij：客戶i與客戶j之間的歐式距離，dij=∞表示客戶i與客戶j之間的交通發(fā)生中斷；

ck：第k輛車的單位運輸成本；

Gk：第k輛車的固定成本；

Di：第i個客戶的需求量；

whijk：配送中心h的車輛k從i到j(luò)地的運輸量；

σi：需求點i處的生鮮品貨損率；

pi：需求點i處訂單的生鮮品價值；

λ∈0，1：時間敏感調(diào)節(jié)因子；

t′：車輛在客戶處完成配送的單位作業(yè)時間；

Ti：車輛到達客戶點j處時剩余產(chǎn)品保鮮時間；

T：生鮮品保質(zhì)期；

Tki：第k輛冷藏車到達需求點i的時刻；

ei：客戶i滿意的最早服務(wù)時間；

li：客戶i滿意的最晚服務(wù)時間；

e′i：客戶i能接受的最早服務(wù)時間；

l′i：客戶i能接受的最晚服務(wù)時間；

α1：制冷設(shè)備在運輸中每單位時間的燃料消耗量；

ρ0：車輛空載時單位距離燃油量；

ρ*：車輛滿載時單位距離燃油量；

α2：制冷設(shè)備在卸載期間每單位時間的燃油消耗量；

v1：車輛行駛速度；

v2：卸載速度；

M4：燃料的單價；

M5：因提前到達導(dǎo)致的等待成本；

M6：因遲到而造成的懲罰費用；

xhijk當(dāng)配送中心h的車輛k由客戶i駛向客戶j時，xhijk等于1，否則為0；

yhk當(dāng)配送中心h發(fā)出車輛k時，yhk等于1，否則為0；

C0：單位碳排放費用；

γ：二氧化碳排放系數(shù)。

1.2 目標(biāo)函數(shù)分析

1）假設(shè)每輛車的固定成本相同，則固定成本為

Z1=∑Khk=1∑Hh=1Gkyhk（1）

2）運輸成本為

Z2=∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1ckdijxhijk（2）

3）與一般物流配送的產(chǎn)品不同，生鮮品具有易損耗特性，因此本文考慮的貨損成本為

Z3=∑ni=1pi×σi（3）

σi為生鮮品損耗系數(shù)，由式（4）計算所得，其中不同的λ值代表不同的生鮮品種類。

σi=t′Tiλ（4）

Ti=T－Tki（5）

4）由于生鮮的儲存環(huán)境需要在低溫狀態(tài)下，因此冷鏈配送需要消耗一定的制冷成本，制冷成本由以下兩種能源消耗成本組成：

（1）運輸過程中能源消耗的成本Z41為

Z41=M4∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1（6）

（2）卸貨過程中額外能耗的成本Z42為

Z42=M4∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα2Div2（7）

因此，總制冷成本Z4為

Z4=Z41+Z42=M4∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1+α2Div2（8）

5）如果配送時間不能滿足客戶期望的時間窗，則產(chǎn)生的罰款成本為

Z6=M5∑ni=1∑Khk=1∑Hh=1maxei－Tki，0，Tkilt;ei0，ei≤Tki≤liM6∑ni=1∑Khk=1∑Hh=1maxTki－li，0，Tkigt;li=∑ni=1∑Khk=1∑Hh=1M5maxei－Tki，0+∑ni=1∑Khk=1∑Hh=1M6maxTki－li，0（9）

6）碳排放主要指消耗燃油產(chǎn)生的CO2排放量，與一般物流配送不同的是，冷鏈配送不僅要考慮車輛行駛所消耗的燃料產(chǎn)生的碳排放，也要考慮制冷設(shè)備所消耗的燃料產(chǎn)生的碳排放。冷鏈物流中產(chǎn)生的油耗由以下兩部分組成：

（1）根據(jù)Xiao等［15］收集相關(guān)統(tǒng)計數(shù)據(jù)進行回歸分析，設(shè)X為貨物重量，單位距離的油耗可表示為

ρ（X）=ρ0+（ρ－ρ0）Qk×X（10）

因此，車輛行駛的燃料消耗量為

FC1=∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkρ0+ρ*－ρ0Qkwhijkdij（11）

（2）制冷設(shè)備的油耗已在前文中討論過，即：

FC2=∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1+α2Djv2（12）

因此，總?cè)剂舷牧繛?/p>

FC=FC1+FC2=∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkρ0+ρ*－ρ0Qwhijkdij+∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1+α2Djv2（13）

由碳排放成本=碳稅×碳排放量公式，冷鏈物流環(huán)節(jié)產(chǎn)生的碳排放成本A為

A=C0γ∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkρ0+ρ*－ρ0Qwhijkdij+C0γ∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1+α2Djv2（14）

7）客戶滿意度是指客戶對配送時間的要求，客戶滿意度越高，說明車輛盡可能地在客戶期待的時間窗內(nèi)到達，貨物的在途時間越少，損耗越小。本文應(yīng)用張建勇等［16］提出的客戶滿意度與服務(wù)時間之間的函數(shù)關(guān)系（能夠更好地體現(xiàn)出客戶i的客戶滿意度）。

f（Tki）=0Tkilt;e′iTki-e′iei-e′i×100/%e′i≤Tkilt;ei1ei≤Tki≤lil′i-Tkil′i-li×100/%lilt;Tki≤l′i0Tkigt;l′i（15）

客戶i的滿意度函數(shù)f（Tki）如式（15）所示，所有客戶滿意度的平均值F，如式（16）所示：

F=1n∑ni=1f（Tki）（16）

1.3 建立模型

在動態(tài)事件發(fā)生之前，配送車輛已為部分客戶完成配送服務(wù)，且處于客戶點位置，當(dāng)動態(tài)事件發(fā)生后，車輛將無法對未完成配送服務(wù)的客戶和發(fā)生動態(tài)變化的客戶進行直接調(diào)度，需要重新對客戶及車輛進行編號。因此本研究建立兩階段優(yōu)化模型：

1）第1階段初始配送模型。

本文構(gòu)建考慮碳排放和客戶滿意度的動態(tài)冷鏈配送路徑優(yōu)化模型，其中為了算法在求解過程中計算方向統(tǒng)一，將客戶滿意度取負(fù)值變?yōu)榍笞钚?，因此，?階段初始配送數(shù)學(xué)模型為

目標(biāo)函數(shù)：

Min－F=1n∑ni=1fi（ti）（17）

MinZ=Z1+Z2+Z3+Z4+Z5=∑Khk=1∑Hh=1Gkyhk+∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1ckdijxhijk+∑ni=1pi×σi+M4∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1+α2Div2+∑ni=1∑Khk=1∑Hh=1M5maxei－Tki，0+∑ni=1∑Khk=1∑Hh=1M6maxTki－li，0（18）

MinA=C0γ∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkρ0+ρ*－ρ0Qwhijkdij+C0γ∑n+Hi=1∑n+Hj=1∑Khk=1∑Hh=1xhijkα1dijv1+α2Djv2（19）

約束條件：

∑ni=1∑n+Hj=1Dixhijk≤Qk，h∈H，k∈M（20）

∑nj=1∑Khk=1xhijk≤Kh，i=h∈H（21）

∑n+Hj=1∑Khk=1∑Hh=1xhijk=1，i∈N（22）

∑n+Hi=1∑Khk=1∑Hh=1xhijk=1，j∈N（23）

whijk=xhijkQk，i∈H，j∈N，h∈H，k∈M（24）

∑n+Hi=1xhijkwhijk－Dj≥0，j∈N，h∈H，k∈M（25）

∑n+Hi=1xhijkwhijk－Dj=∑n+Hi=1xhjikwhjik，j∈N，h∈H，k∈M（26）

∑n+Hi=1xhijkwhijk≤Di+1，i∈N，h∈H，k∈M（27）

∑n+Hi=n+1∑n+Hj=n+1xhijk=0，h∈H，k∈M（28）

∑n+Hi=n+1∑nj=1xhijk=∑ni=1∑n+Hj=n+1xhijk，h∈H，k∈M（29）

Tkj=Tki+dijv1+Div2（30）

其中，式（20）表示車輛的載重限制。式（21）表示配送中心的車輛總數(shù)與該配送中心提供服務(wù)的車輛數(shù)之間的關(guān)系。式（22）和式（23）含義為每個客戶只有一輛車提供配送。式（24）含義為車輛滿載出發(fā)，它是式（25）、式（26）及式（27）的基礎(chǔ)。式（25）表示車輛的載貨量要滿足每個客戶的需求量。式（26）表示車輛通過客戶點時運輸量發(fā)生變化的關(guān)系式。式（27）表示車輛進入配送中心添加貨物量的條件。式（28）是為了防止車輛從一個配送中心到另一個配送中心。式（29）表示車輛完成配送服務(wù)后可就近返回任一配送中心。式（30）表明交付過程是連續(xù)的。

2）第2階段實時優(yōu)化模型。

在動態(tài)事件發(fā)生后，第2階段需要及時更新道路交通情況（當(dāng)dij=∞時，即道路交通發(fā)生中斷）、客戶所在位置及需求量、配送時間窗、車輛狀態(tài)等信息。本文將車輛所在的客戶點設(shè)為虛擬配送中心，虛擬配送中心編號為S+H+1，S+H+2，…，S+H+Rh，原配送中心編號為S+1，S+2，…，S+H，有關(guān)符號說明：S，初始階段未完成配送的客戶與第2階段新增客戶的總數(shù)量；Rh，初始階段已經(jīng)行駛的車輛數(shù)；Qhzh=1，2，…，H，z=1，2，…，Rh，已經(jīng)行駛車輛的剩余載貨量；Rh，虛擬配送中心數(shù)量；Th（k=Rh+1，Rh+2，…，Rh+Th），第2階段新出發(fā)的車輛數(shù)。第2階段實時優(yōu)化模型為

目標(biāo)函數(shù)：

Min－F′=1S∑Si=1fi（ti）（31）

MinC=C1+C2+C3+C4+C5=∑Rh+Thk=Rh+1∑Hh=1Gkyhk+∑S+H+Rhi=1∑S+H+Rhj=1∑Rhk=1∑Hh=1ckdijxhijk+∑S+H+Rhi=1∑S+H+Rhj=1∑Rh+Thk=Rh+1∑Hh=1ckdijxhijk+∑Si=1pi×σi+M4∑n+Hi=1∑n+Hj=1∑Rhk=1∑Hh=1xhijkα1dijv1+α2Div2+M4∑n+Hi=1∑n+Hj=1∑Rh+ThRh=1∑Hh=1xhijkα1dijv1+α2Div2+∑Si=1∑Rh+Thk=1∑Hh=1M5maxei－Tki，0∑Si=1∑Rh+Thk=1∑Hh=1M6maxTki－li，0（32）

MinB=C0γ∑n+Hi=1∑n+Hj=1∑Rhk=1∑Hh=1xhijkρ0+ρ*－ρ0Qwhijkdij+C0γ∑n+Hi=1∑n+Hj=1∑Rhk=1∑Hh=1xhijkα1dijv1+α2Djv2+C0γ∑n+Hi=1∑n+Hj=1∑Rh+Thk=Rh+1∑Hh=1xhijkρ0+ρ*－ρ0QwhijkdijC0γ∑n+Hi=1∑n+Hj=1∑Rh+Thk=Rh+1∑Hh=1xhijkα1dijv1+α2Djv2（33）

約束條件：

∑Si=1∑S+H+Rhj=1Dixhijk≤Qhz，h∈S+1，S+2，…，S+H+Rh，k∈1，2，…，Rh（34）

∑Sj=1∑Rh+Thk=1xhijk≤Kh，i=h∈S+1，S+2，…，S+H+Rh（35）

∑S+H+Rhj=1∑Rh+Thk=1∑Hh=1xhijk=1，i∈1，2，…，S（36）

∑S+H+Rhi=1∑Rh+Thk=1∑Hh=1xhijk=1，j∈1，2，…，S（37）

whijk=xhijkQk，i∈S+1，S+2，…，S+H+Rh（38）

j∈1，2，…，S，h∈S+1，S+2，…，S+H+Rh，k∈Rh+1，Rh+2，…，Rh+Th

∑S+H+Rhi=1xhijkwhijk－Dj≥0（39）

j∈1，2，…，S，h∈S+1，S+2，…，S+H+Rh，k∈1，2，…，Rh，Rh+1，Rh+2，…，Rh+Th

∑S+H+Rhi=1xhijkwhijk－Dj=∑S+H+Rhi=1xhjikwhjik（40）

j∈1，2，…，S，h∈S+1，S+2，…，S+H+Rh，k∈1，2，…，Rh，Rh+1，Rh+2，…，Rh+Th

∑S+H+Rhi=1xhijkwhijk≤Di+1（41）

i∈1，2，…，S，h∈S+1，S+2，…，S+H+Rh，k∈1，2，…，Rh，Rh+1，Rh+2，…，Rh+Th

∑S+H+Rhi=S+1∑S+H+Rhj=S+1xhijk=0（42）

h∈S+1，S+2，…，S+H+Rh，k∈1，2，…，Rh，Rh+1，Rh+2，…，Rh+Th

∑S+Hi=S+1∑Sj=1xhijk=∑Si=1∑S+Hj=S+1xhijk（43）

h∈S+1，S+2，…，S+H，k∈1，2，…，Rh，Rh+1，Rh+2，…，Rh+Th

Tkj=Tki+dijv1+Div2（44）

其中，式（31）表示第2階段客戶滿意度相反數(shù)的最小值。式（32）表示第2階段總配送成本。式（33）表示第2階段碳排放成本。式（34）表示車輛容量限制。式（35）表示配送中心的車輛總數(shù)與該配送中心為客戶提供服務(wù)的車輛數(shù)之間的關(guān)系。式（36）和（37）含義為任一客戶只有一輛車提供貨物配送服務(wù)。式（38）表示車輛滿載出發(fā)，它是式（39）、式（40）及式（41）的初始條件。式（39）表示車輛的載貨量要滿足客戶的需求量。式（40）表示配送車輛經(jīng)過客戶點后運輸量發(fā)生改變的關(guān)系式。式（41）表示車輛進入配送中心補貨的條件。式（42）表示兩個配送中心之間的路徑是中斷的。式（43）表示冷藏車輛完成配送任務(wù)后可就近返回任意配送中心。式（44）表明交付過程是連續(xù)的。

2 模型求解

2.1 求解策略

由于配送過程中可能出現(xiàn)的各種動態(tài)變化，在一定程度上會影響初始配送方案，因此對所建模型，采用兩階段求解策略對其求解。在初始配送階段中，企業(yè)根據(jù)接收的客戶訂單信息，利用INSGA-II算法產(chǎn)生車輛的初始配送方案。更新配送信息，檢查是否接收到客戶變化、交通狀況等動態(tài)事件，按照近鄰優(yōu)先原則動態(tài)添加新客戶，利用INSGA-II算法動態(tài)優(yōu)化路徑，得到最終的車輛配送方案。

2.2 改進的NSGA-II算法

1）編碼及初始種群的生成。

本文對全體客戶采用自然數(shù)編碼，客戶的排列順序即為車輛配送順序。為了提高第一輪子代種群Q0的質(zhì)量以及種群收斂速度，假設(shè)種群個體大小為N，設(shè)置初始化種群的個體數(shù)目為1.5N至2N。

2）適應(yīng)度函數(shù)。

適應(yīng)度值一般是求取最大值，個體適應(yīng)度值越大，表明個體越優(yōu)良。根據(jù)參考文獻［17］，適應(yīng)度函數(shù)通常是由目標(biāo)函數(shù)經(jīng)過數(shù)學(xué)變換得到，本文選取目標(biāo)函數(shù)值的倒數(shù)為適應(yīng)度函數(shù)。

3）遺傳操作。

（1）選擇算子。

為了提高解集分布性，在選擇操作時引入概率操作。在種群進化前期，以較大概率排除當(dāng)前選出的最優(yōu)個體進而選擇其他個體，在種群進化末期，以較小的概率排除當(dāng)前選出的最優(yōu)個體。概率操作的計算公式為

P=11+e－wg（45）

其中，w為概率選擇算子，g為進化代數(shù)。

（2）交叉算子。

本文選擇的交叉方式為部分匹配交叉（Partially-Matched Crossover，PMX），保證了在一個染色體中沒有重復(fù)的基因。

（3）變異算子。

變異算子采用高斯變異，在局部搜索方面優(yōu)勢顯著。個體χi，ηi在高斯變異算子作用下變?yōu)棣帧鋓，η′i。

η′i=ηiexpτ′N0，1+τNj0，1χ′i=χi+η′iN0，1（46）

其中，τ′和τ為算子集參數(shù)，表示整體和個體步長，τ′=2n－1（n為變量個數(shù)），τ=2N－1（N為種群大?。?。

4）子代種群生成方式。

為了提高NSGA-II進化的方向性和適應(yīng)性，擴大搜索空間，具體操作如下：在利用NSGA-II算法合并新父種群后，NSGA-II算法經(jīng)過快速非支配排序、擁擠度計算以及一系列遺傳操作后，生成子代種群1。同時，利用粒子群算法的更新種群方式生成子代種群2，最后將兩個子代種群合并，執(zhí)行下一步操作。

2.3 算法性能評估

為了評價改進算法的收斂性與多樣性，通過多目標(biāo)測試函數(shù)進行算法對比，4種算法分別在迭代次數(shù)為50和100時獨立運行20次，將HV以及IGD的結(jié)果值進行平均，從表1可以看出，INSGA-II算法的HV指標(biāo)基本高于MOEAD、NSGA-II以及MOPSO，表明INSGA-II求解得到的Pareto解集能夠較好地收斂到理想的Pareto前沿面。同時，從表2可以看出，改進后的NSGA-II算法的IGD指標(biāo)低于其他算法，表明INSGA-II算法的收斂性與多樣性較為良好。

3 算例驗證及分析

3.1 算例設(shè)計

某市生鮮冷鏈企業(yè)設(shè)有4個配送中心，每個配送中心擁有10輛同類型，且載重量為10噸的冷藏車，在配送開始前，該企業(yè)收到30個客戶的配送訂單，配送中心及客戶相關(guān)信息如表3所示。假設(shè)任意兩個需求點都能以直線方式到達，兩點間距離dij=x1－x22+y1－y22。根據(jù)對物流公司實際運輸費用的調(diào)研，模型中的相關(guān)參數(shù)值如表4所示。

3.2 算例結(jié)果

程序使用Matlab R2016b編寫，并在Intel（R）Core（TM）i57200U CPU 2.50GHz的DELL筆記本電腦（4核，8GB內(nèi)存）上運行。種群大小為100，最大迭代次數(shù)為100，獨立運行50次。第1階段的Pareto最優(yōu)解集的空間分布如圖1所示。選取碳排放成本最低方案作為第2階段實時優(yōu)化的初始方案。

在t等于14時刻，配送中心已發(fā)出3輛車，其中車輛4和車輛5已返回配送中心3，車輛2位于客戶點10。此刻出現(xiàn)一些動態(tài)事件，如表5所示，其中，“*”表示與第1階段初始客戶信息無變化，“+”表示需求量增加，“-”表示需求量減少。此外，客戶28和31之間的交通發(fā)生了中斷，同時接收到8個新客戶訂單，其客戶信息如表6所示。t等于14時刻，已經(jīng)完成配送服務(wù)的客戶有5，7，9，8，11，12，16，24以及25。在第2階段，去掉已經(jīng)完成配送服務(wù)的客戶，未服務(wù)客戶和新增客戶一共29個，將14時刻車輛所在的客戶點設(shè)為虛擬配送中心。

根據(jù)第2階段模型，采用INSGA-II算法進行求解，最終Pareto最優(yōu)解集的空間分布如圖2所示。

3.3 對比分析

為了分析考慮碳排放對路徑優(yōu)化的影響，針對第1階段模型，將考慮總配送成本和客戶滿意度（不考慮碳排放）為決策目標(biāo)與考慮總配送成本、客戶滿意度和碳排放為決策目標(biāo)的較優(yōu)解進行對比。

根據(jù)表7，與不考慮碳排放方案相比可得：考慮碳排放方案的配送成本增加了19.00%，但是運輸距離減少了5.16%，使得車輛可按時抵達客戶點，客戶滿意度相對較高，故企業(yè)在成本可接受的前提下，采用考慮碳排放的配送方案可提高客戶滿意度；考慮碳排放的配送方案減少了車輛行駛距離，碳排放成本降低了13.03%，有助于企業(yè)積極響應(yīng)國家碳稅政策并向低碳化轉(zhuǎn)型升級，同時運輸距離越短，生鮮品在路途中產(chǎn)生的貨損就越小，客戶對產(chǎn)品的體驗感也越好，有利于提高產(chǎn)品銷量。

通過對比預(yù)優(yōu)化方案與實時優(yōu)化方案，由表8可知，與初始配送方案相比，實時優(yōu)化方案的配送成本下降了29.78%，碳排放成本下降了23.19%，客戶滿意度由69%提高至79%，增幅14.49%，這表明與冷鏈物流靜態(tài)車輛路徑相比，在動態(tài)車輛路徑問題中考慮碳排放既可以減少碳排放成本又可以降低配送成本，進一步說明本文所建模型是合理且有效的。

為了驗證多中心半開放式冷鏈配送的有效性，本文在預(yù)優(yōu)化階段采用單中心獨立配送模式與之對比。在相同的假設(shè)和系統(tǒng)優(yōu)化環(huán)境下，運用設(shè)計的NSGA-II算法進行多次求解，選擇較優(yōu)解進行比較。如表9所示，與單配送中心模式相比，多配送中心模式雖然多派出兩輛車輛，但配送成本降低了27.30%，碳排放成本降低了48.89%，客戶滿意度提高了13.11%。這表明多配送中心半開放式配送模式可顯著減少車輛行駛距離，降低配送成本與碳排放成本以及提高客戶滿意度，有助于企業(yè)長遠發(fā)展。

4 結(jié)語

本文在冷鏈配送車輛路徑問題中考慮了多配送中心、時間窗以及多種動態(tài)變化因素。構(gòu)建了考慮時間窗的動態(tài)多中心半開放式冷鏈物流車輛路徑優(yōu)化數(shù)學(xué)模型。為求解該問題模型，改進了傳統(tǒng)NSGA-II算法，并利用測試函數(shù)證實改進的NSGA-II算法具有更好的收斂性與多樣性。通過決策目標(biāo)、動靜態(tài)、配送中心數(shù)量等對比分析表明：與不考慮碳排放方案相比，采用考慮碳排放的配送方案可提高客戶滿意度、降低碳排放成本；與冷鏈物流靜態(tài)車輛路徑相比，在動態(tài)車輛路徑問題中考慮碳排放既可減少碳排放成本又可降低配送成本；與單配送中心模式相比，多配送中心模式可顯著減少車輛行駛距離，降低配送成本與碳排放成本以及提高客戶滿意度，從而助力冷鏈物流企業(yè)在碳稅政策下承擔(dān)節(jié)能減排這一重要的社會責(zé)任，對推動中國早日實現(xiàn)“雙碳”目標(biāo)具有重要的積極意義。

然而，本文所建模型雖然盡可能地貼近現(xiàn)實情況，但仍忽略了生鮮企業(yè)可能會根據(jù)產(chǎn)品種類、客戶需求量等派出不同類型的配送車輛，因此后續(xù)工作可考慮異型車輛，使研究的問題更符合實際。此外，改進NSGA-II算法雖然在實驗結(jié)果上要優(yōu)于其他算法，但忽略了算法運行速度，導(dǎo)致程序計算時間較長，在下一步研究中，可設(shè)計出更加高效的啟發(fā)式算法，提高其運行速度。

參考文獻：

［1］LENG L， ZHANG C， ZHAO Y， et al. Biobjective Low-carbon location-routing problem for cold chain logistics：formulation and heuristic approaches［DB/OL］.［20230128］.https：//doi.org/10.1016/j.jclepro.2020.122801.

［2］LIU G， HU J， YANG Y， et al. Vehicle routing problem in cold chain logistics： a joint distribution model with carbon trading mechanisms［DB/OL］.［20230128］. https：//doi.org/10.1016/j.resconrec.2020.104715.

［3］LIAN J. An optimization model of cross-docking scheduling of cold chain logistics based on fuzzy time window［J］. Journal of Intelligent and Fuzzy Systems， 2021， 41（1）：19011915.

［4］ 李倩，蔣麗，梁昌勇. 基于模糊時間窗的多目標(biāo)冷鏈配送優(yōu)化［J］. 計算機工程與應(yīng)用， 2021， 57（23）： 255262.

LI Qian， JIANG Li， LIANG Changyong. Multi-objective cold chain distribution optimization based on fuzzy t-ime window ［J］. Computer Engineering and Applicati-ons， 2021， 57（23）： 255262.

［5］任騰，羅天羽，李姝萱，等. 面向冷鏈物流配送路徑優(yōu)化的知識型蟻群算法［J］. 控制與決策， 2022， 37（3）： 545554.

REN Teng， LUO Tianyu， LI Shuxuan， et al. Knowledge based ant colony algorithm for distribution route optimization of cold chain logistics ［J］. Control and Decision， 2022， 37（3）： 545554.

［6］白秦洋，尹小慶，林云. 考慮路網(wǎng)中實時交通的冷鏈物流路徑優(yōu)化［J］. 工業(yè)工程與管理， 2021， 26（6）： 5665.

BAI Qinyang， YIN Xiaoqing， LIN Yun. Cold chain logistics routing optimization considering real-time traffic in road network ［J］. Industrial Engineering and Management， 2021， 26（6）： 5665.

［7］方文婷，艾時鐘，王晴，等. 基于混合蟻群算法的冷鏈物流配送路徑優(yōu)化研究［J］. 中國管理科學(xué)， 2019， 27（11）： 107115.

FANG Wenting， AI Shizhong， WANG Qing， et al. Research on distribution route optimization of cold chain logistics based on hybrid ant colony algorithm ［J］. Chinese Journal of Management Science， 2019， 27（11）： 107115.

［8］BRANDO J. A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem［J］. European Journal of Operational Research， 2020， 284（2）：559571.

［9］WANG Y， LI Q， GUAN X， et al. Two-echelon collaborative multi-depot multi-period vehicle routing problem［DB/OL］.［20230128］.https：//doi.org/10.1016/j.eswa.2020.114201.

［10］ FAN H， ZHANG Y， TIAN P， et al. Time-dependent multi-depot green vehicle routing problem with time windows considering temporal-spatial distance［DB/OL］.［20230128］.https：//doi.org/10.1016/j.cor.2021.105211.

［11］ 廖列法，張幸平. 考慮客戶滿意度的多配送站低碳物流路徑規(guī)劃［J］. 信息與控制， 2020， 49（4）： 420428.

LIAO Liefa， ZHANG Xingping. Low-carbon logistics route planning for multi-distribution stations considering customer satisfaction ［J］. Information and Control， 2020， 49（4）： 420428.

［12］ 范厚明，張軒，任曉雪，等. 多中心開放且需求可拆分的VRPSDP問題優(yōu)化［J］. 系統(tǒng)工程理論與實踐， 2021， 41（6）： 15211534.

FAN Houming， ZHANG Xuan， REN Xiaoxue， et al. Optimization of multi-center open VRPSDP problem with separable requirements ［J］. Systems Engineering Theory amp; Practice， 2021， 41（6）： 15211534.

［13］ 王萬良，陳浩立，李國慶，等. 基于深度強化學(xué)習(xí)的多配送中心車輛路徑規(guī)劃［J］. 控制與決策， 2022， 37（8）： 21012109.

WANG Wanliang， CHEN Haoli， LI Guoqing， et al. Vehicle routing planning in multi-distribution centers based on deep reinforcement learning ［J］. Control and Decision， 2022， 37（8）： 21012109.

［14］ 張穎鈺，吳立云.多中心半開放式送取需求可拆分的車輛路徑優(yōu)化［J］.計算機應(yīng)用研究，2022，39（8）：23162321.

ZHANG Yingyu， WU Liyun. Optimization of multi-center semi-open vehicle routing with split delivery demand ［J］. Application Research of Computers， 2012，39（8）：23162321.

［15］ XIAO Y， ZHAO Q， KAKU I， et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem［J］. Computers and Operations Research， 2012， 39（7）：14191431.

［16］ 張建勇，郭耀煌，李軍. 基于顧客滿意度的多目標(biāo)模糊車輛優(yōu)化調(diào)度問題研究［J］. 鐵道學(xué)報， 2003（2）： 1517.

ZHANG Jianyong， GUO Yaohuang， LI Jun.Research on multi-objective fuzzy vehicle optimization scheduling problem based on customer satisfaction ［J］. Journal of the China Railway Society， 2003（2）： 1517.

［17］ 潘立軍，符卓. 求解帶時間窗取送貨問題的遺傳算法［J］. 系統(tǒng)工程理論與實踐， 2012， 32（1）： 120126.

PAN Lijun， FU Zhuo. Genetic algorithm for pickup and delivery problem with time window［J］. Systems Engineering Theory amp; P-ractice， 2012， 32（1）： 120126.

（責(zé)任編輯 李 進）