基于模糊時間窗的多目標冷鏈配送優化

李 倩，蔣 麗，梁昌勇

合肥工業大學 管理學院，合肥 230009

受消費水平不斷提高和消費觀念逐漸轉變的影響，人們對生鮮冷鏈產品的需求量日益增大，質量要求也越來越高。生鮮冷鏈產品由于具有保存不易、易腐等特性，配送難度高于普通貨品。企業為保證生鮮冷鏈產品的新鮮度，配送時需進行嚴格的溫度控制，而冷藏車等溫度控制設備的使用會導致配送成本的提高。另外，若配送時路徑規劃不合理，配送時長就會增加，生鮮冷鏈產品的損耗就會隨之增大，車輛配送成本也會因此上升。在這種情況下，冷鏈配送更加難以滿足客戶的時間窗要求，極易引起客戶滿意度水平的降低，甚至導致客戶的流失。總的來說，這些因素都使冷鏈配送路徑的研究越來越重要。

冷鏈配送路徑優化是由車輛路徑問題演化而來。而車輛路徑問題自1959年首次提出就吸引許多學者的關注，經過許多年的研究，成果非常豐碩。其中，Huang等[1]研究了顧客自提和送貨上門相結合的策略下，包含多類型站點的電動物流車輛路徑問題。郭放等[2]考慮前置倉選址策略，研究面向城市的小件物流配送同時取送貨的車輛路徑問題。徐小峰等[3]構建考慮需求優先等級和配送成本的多油品多油庫車輛路徑規劃多目標優化模型，并采用MOPSO算法對模型求解。王新等[4]考慮了多個無人機站點和顧客的時間窗要求，研究車輛與無人機聯合配送路徑問題。

隨著研究的不斷深入以及實際配送的需要，國內外專家學者在傳統車輛路徑問題的基礎上加入時間窗、新鮮度、準時性等約束，將其擴展為冷鏈物流配送路徑優化問題，并分別從不同方面對此問題進行了研究。Xiao等[5]考慮異質車輛、時變交通、時間窗、碳排放、車輛容量及里程約束，構建了混合整數線性規劃模型來解決GVRSP問題。Hsiao等[6]提出基于自適應生物地理優化的算法來求解多溫共配的冷鏈物流配送模型。Belhaiza等[7]設計滿足納什均衡條件的混合變鄰域禁忌搜索算法，結合加拿大運輸公司的實例來驗證多目標模型的可行性。Li等[8]和Ding等[9]均構建了總成本最小的單目標路徑優化模型，分別通過改進粒子群算法和混合蟻群算法對模型進行求解。Zhang等[10]在冷鏈物流中加入碳排放成本，改進蟻群算法并有效降低碳排放量。王淑云等[11]針對冷鏈物流多溫共配問題，將多種算法結合并通過實例來驗證其有效性。馬向國等[12]考慮日溫度差，對冷鏈配送中的制冷成本進行修正，建立總成本最小的優化模型。鮑春玲等[13]考慮多配送中心情況下的冷鏈物流聯合配送問題，證明聯合配送在配送費用及碳排放成本方面均大大低于分區配送。方文婷等[14]將節能減排轉化為綠色成本與車輛路徑問題結合，并構造混合蟻群算法改進原算法收斂速度慢的缺陷。于江霞等[15]在VRP的基礎上加入客戶分類以提高配送準時性，加強客戶精細化管理。

綜上所述，目前關于冷鏈物流配送路徑的研究以成本為主，構建模型時局限于單一目標的優化。基于此，本文基于時間窗引入客戶滿意度函數，并考慮由固定成本、制冷成本、貨損成本、懲罰成本構成的總配送成本，構建客戶滿意度最高和總成本最小的多目標優化模型。針對模型的求解，利用Pareto最優處理多目標問題的優勢，設計了基于Pareto最優的NSGA-II多目標智能算法，再結合solomon數據集進行仿真模擬實驗。實驗表明，該算法在較短的運行時間里可獲得較優的運行結果，得出的配送方案也更加高效。

1 問題描述

考慮到冷鏈企業實際配送中的成本約束，本文僅設置單個配送中心，并對該情況下的冷鏈配送路徑問題進行研究。配送時車輛均從同一配送中心出發，對有需求的客戶點完成配送后返回起始配送中心。

冷鏈物流企業面臨的競爭不斷加劇，客戶已成為企業提高競爭力的重要資源。因此，本文在考慮總成本最小的基礎上，還設置了客戶滿意度最大為優化目標，解決在車輛最大載重量、客戶需求量、時間窗等限制之下，客戶滿意度最大和總成本最小的問題。假設如下：

（1）配送中心可滿足所有客戶點的冷鏈品配送需求，無缺貨情況；

（2）配送車輛生鮮品的裝載量不超過車輛的最大裝載量，且配送的為同一冷藏溫度的生鮮產品，配送車輛均為同種類型；

（3）已知客戶要求的時間窗、客戶點位置、冷鏈品需求量；

（4）每個客戶點僅由一輛車提供配送服務，且只能到達和出發一次，但每輛配送車可服務多個客戶點；

（5）若未按照約定的配送時間窗對客戶點進行配送，企業需支付罰金；

（6）配送車輛從配送中心出發，完成配送后返回起始配送中心。配送過程中，除為客戶點服務外不發生裝卸產品的情況；

（7）配送車輛的燃油為汽油。

2 模型構建

2.1 參數設置

0：配送中心；

N：配送中心服務的客戶點總數；

K：滿足配送中心配送需要的車輛數；

fk：使用配送車輛K的固定成本；

b3：單位制冷成本；

tsi：配送車輛服務客戶點i所需要的時間；

tik：配送車輛k到達客戶點i的時間；

t0k：配送車輛k從配送中心出發的時間；

Qim：配送車輛服務完客戶點i離開時，車上所剩生鮮品的重量。

qi：客戶點i對生鮮品的需求量；

Q：車輛最大載重量；

wi：配送車輛在客戶點i的等待時間。

2.2 變量分析

2.2.1 決策變量分析

決策變量xijk：

xijk=直接由客戶點i駛向客戶點j時，xijk=1，否則為0。

決策變量yik：

yik=點i由車輛k提供配送服務且滿足配送需求時，yik=1，否則為0。

2.2.2 引入客戶滿意度

假設客戶預約服務時間為[ei,li]，若在此時間窗內進行配送，則fi(ti)=1。但是在實際配送過程時，配送時間會受到配送安排及交通情況等多種因素的影響，這就造成實際配送會早于或晚于客戶預約服務的時間窗，從而導致客戶滿意度的降低。假設Ei、Li分別表示客戶能接受的最早和最晚服務時間。若在[Ei,ei]或[li,Li]時間范圍內進行配送，則客戶滿意度隨著與預約服務時間窗的時間差的增大而降低。若配送時間在[Ei,Li]范圍之外，fi(ti)=0。圖1為客戶滿意度隨時間窗變化情況。

圖1 時間滿意度函數Fig.1 Time satisfaction function

時間滿意度函數如式（1）所示：

其中，ti為客戶點i開始服務的時間，α、β為客戶對事件的敏感系數。

2.2.3 成本變量分析

（1）固定成本

固定成本一般由駕駛員工資、車輛折舊費、保養費等費用組成，僅與車輛的數量有關，如式（2）所示：

（2）制冷成本

本文中的制冷成本不僅包括車輛行駛過程中為維持車廂溫度而產生的成本，還包括裝卸貨物時開車門而產生的成本，如式（3）所示：

其中，Qk1=R S(1+β0)(θw-θn)；Qk2=f(0.54Vk+3.22)(θwθn)；Qk1表示配送車輛k運輸行駛的熱負荷；Tk為配送車輛k完成配送任務回到配送中心的時間；β0為車廂破損程度；R為傳熱率；S為車廂傳熱面積；θw為外界空氣溫度；θn為生鮮產品冷藏溫度；Vk為配送車輛k冷藏箱的體積；f為開門附加熱負荷系數。

（3）貨損成本

冷鏈品產生貨損的原因主要有兩個：第一個是由于配送過程中時間累積造成的；第二個是由于裝卸時周圍環境變化導致產品損失。本文結合冷鏈品新鮮度衰減函數構建貨損成本，新鮮度衰減函數如式（4）所示：

θ(t)表示生鮮品在t時刻的新鮮程度，θ0表示冷鏈產品從配送中心出發時的新鮮程度，?1表示運輸過程中的新鮮度衰減系數，?2表示裝卸過程中的新鮮度衰減系數。新鮮度衰減系數受溫度、含氧量等影響較大，裝卸過程中易產生較大波動，故?2>?1。貨損成本如式（5）所示：

其中，p表示所運輸的生鮮品的單位價值。

（4）懲罰成本

由2.2.2小節中可知，[ei,li]為客戶要求的接受服務的時間窗，[Ei,Li]為客戶能接受的最大容忍時間窗。懲罰成本如式（6）所示：

其中，δ1、δ2分別為配送車輛到達客戶點時間在[Ei,ei]、[li,Li]內的懲罰系數。

2.3 數學模型

通過以上分析，本文構建冷鏈物流車輛配送優化模型，以客戶滿意度最大，固定成本、制冷成本、貨損成本、懲罰成本總成本最小為目標函數。

在上述約束條件中，式（7）表示客戶滿意度最大；式（8）表示路徑優化總成本最小；式（9）確保不超過車輛最大載重量；式（10）保證每個客戶點只被訪問一次；式（11）保證車輛從配送中心出發且返回配送中心；式（12）確保配送所需的車輛不會超過配送中心車輛總數；式（13）和（14）確保每個客戶點只允許配送車輛出發到達一次；式（15）定義決策變量；式（16）確保無子回路；式（17）保證配送的連續性；式（18）定義等待時間；式（19）保證配送服務在最大時間窗內。

3 算法設計

本文解決的是客戶滿意度最大和配送總成本最小的多目標問題。通常多目標優化問題中不同目標相互制約，只有非劣解解集即帕累托解集。而NSGA-II算法是在2002年由Deb等[16]提出的基于Pareto最優解的多目標優化算法，在處理多目標優化問題上簡單有效并且具有明顯的優越性，通過引入精英策略、擁擠度和擁擠比較算子來更好地求解多目標優化模型。因此，本文選擇NSGA-II算法來對模型進行仿真求解。

3.1 算法原理步驟

NSGA-II算法主要是從快速非支配排序、擁擠度和擁擠比較算子、精英策略三個方面進行改進，更好地降低了計算的復雜度，加快算法的收斂速度。算法具體步驟如下所示：

步驟1通過編碼確定初始種群P(t)，t=1，種群規模為N；

步驟2對初始種群進行非支配排序、選擇、交叉、變異操作，產生子代種群Q(t)；

步驟3將子代種群Q(t)與初始種群P(t)合并組成種群R(t)，大小為2N，并對種群R(t)進行非支配排序、擁擠度計算、精英保留策略操作，得到種群P(t+1)；

步驟4終止判斷。若進化代數已達到最大，則算法停止并輸出Pareto解，否則返回到步驟2。

算法流程圖如圖2所示。

圖2 NSGA-II算法流程圖Fig.2 NSGA-II algorithm flow chart

3.2 編碼及算子設計

3.2.1整數編碼

配送路徑優化問題是配送車輛從配送中心出發，經過不同的客戶點得到的車輛行駛路線，即車輛配送路徑。本文根據研究問題的特點，采取整數編碼的形式。在配送網絡中，客戶點編碼為1、2、…、N，配送車輛編碼為N+1、N+2、…、N+K。每條染色體都由車輛編號和客戶需求點編號兩部分組成，由于有且僅有一個配送中心，所有配送車輛均從該配送中心出發，故不在染色體中設置配送中心位置。這種編碼方式表達較為簡潔、可擴充性強，能夠在一定程度上減少模型的復雜度，提升算法的計算效率。

3.2.2交叉算子

在交叉算子的選擇中，本文采用PMX，即部分匹配法來提高Pareto解集質量。從父代染色體中隨機選擇兩個個體，再選擇兩個個體中被選位置相同的幾個基因的起止位，將選中的基因提取出來并進行交換。然后進行沖突檢測，將交換后的兩組基因建立相應的映射關系，通過映射把交換后個體中重復的基因進行轉變，重復這個步驟直到個體中沒有沖突為止。最終所有沖突的基因都會經過映射，形成一對新的無沖突基因的子代。具體步驟如圖3所示。

3.2.3變異算子

變異操作采取與交叉操作相同的基因編碼方式，并通過變異概率來判斷是否需要進行變異。若需要變異則采用交換變異方式，設置產生兩個隨機數，從父代中選擇隨機數所對應的兩個基因位置，再將這兩個位置的基因進行互換，通過不斷的隨機變異，從而找到最短路徑。

圖3 PMX原理圖Fig.3 PMX schematic diagram

4 算例驗證

本文的算例驗證使用Solomon的標準數據集[17]作為實驗數據，在Solomon的標準數據集中，一共包含了6類：R1，R2，C1，C2，RC1，RC2。數據集中包含著每個客戶的坐標、需求量、時間窗的開始和結束時間以及客戶的服務時間。其中，R類（random）為隨機分布的客戶地理位置，C類（clustered）則為聚集分布的客戶地理位置，RC類為部分聚集部分隨機。數字1、2類則表示：1類問題中，調度范圍及車輛容量小，服務的客戶對象較少，時間窗較窄。2類問題中時間窗相對較寬，調度范圍較大，每條路線允許更多的客戶。

模型參數設置為車輛固定成本fk為500元，車輛行駛速度為60 km/h勻速行駛，車輛單位距離運費為40元/km，假設θw為夏季最高平均氣溫38℃，θn為0~2℃，配送車輛單位制冷成本b3為5.72元/L。產品在車輛運輸和裝卸階段的新鮮度衰減系數分別為0.03和0.06，配送車輛早于約定時間窗罰金為50元/h，晚于約定的時間窗罰金為100元/h。客戶接受的最大時間窗可以在約定的服務時間提前或延后5~15 min。

算法參數設置種群規模為N=100，交叉概率為Px=0.9，變異概率為Pm=0.2。本文選取R102、R104、R202、R204、C102、C104、C202、C204、RC102、RC104、RC202、RC204共12組數據來進行算例驗證，涵蓋數據集中所有種類，并將各組算例最優運行結果進行對比分析，結果如表1、表2所示。

表1 運行結果1Table 1 Computational results 1

表2 運行結果2Table 2 Computational results 2

數據最優運行結果如表1、表2所示。為使運行結果對比更加方便，在表1、2的基礎上繪制圖4~圖7。如圖所示可以更清晰地看到，迭代次數設置為300及以上時，最優運行結果明顯優于迭代次數為100。由此可知迭代次數對算法性能有一定的影響，根據運行結果建議R類數據迭代次數取值300，以節省運行時間。而C類、RC類數據迭代次數設置為500效果更好。

參考以往許多學者的研究，solonmon數據集中C類數據客戶配送路徑長度一般明顯低于另外兩類，但本文運行結果中并未有顯著差別，對比可知此算法在處理C類數據中相對無優勢。鑒于此，將不再在下文中對C類數據進行對比分析。

除表1、表2中的12組數據之外，本文另選取6組數據，并將其運行結果與文獻[18-19]對比分析。文獻[18]算法IAO表示伊藤-螞蟻優化算法。文獻[19]算法NSGAII表示帶精英策略的非支配排序遺傳算法。由表3可以看出，本文所設計的NSGA-II算法相對于文獻[18-19]中設計的算法更有優越性。其中，針對R101、R105、RC101、RC105分別節省54.2%、31.58%、50%、42.1%的車輛，并縮短9.7%、0.07%、16.13%、21.23%的路徑長度。由此得出，本文所設計的算法更適合解決時間窗較窄且客戶地理位置隨機或部分聚集部分隨機的配送問題。此外，本文利用部分R1、RC1類數據，設置不同種群規模并通過運行獲取最優運行結果，具體結果如表4所示。整體來看，不同種群規模的客戶滿意度均可達到或接近100%的水平，但是隨著種群規模的不斷增大，配送車輛數、總路徑長度、配送成本均不斷上升。考慮到實際配送中需面臨的各種問題，建議單個配送中心匹配20~40個客戶點，以更有效地控制配送成本，提高客戶配送滿意度。

5 結語

本文從滿意度和總成本兩方面考慮，建立相應的數學模型，對模糊時間窗下的冷鏈物流配送進行研究。通過NSGA-II算法對模型進行求解分析，并利用數據集對不同類型問題進行仿真實驗，驗證模型和算法的可行性和優越性。最終得出結論如下：

圖4 車輛數運行結果圖Fig.4 Number of vehicles running results chart

圖5 總路徑長度運行結果圖Fig.5 Total path length run result graph

圖6 滿意度運行結果圖Fig.6 Satisfaction running result chart

圖7 總成本運行結果圖Fig.7 Total cost running results chart

表3 本文最優結果與文獻最優結果對比Table 3 Comparison of optimal results of this paper and other literatures

表4 不同規模運行結果對比Table 4 Comparison of operation results of different scales

（1）在實際生活中，冷鏈產品配送既不是絕對的硬時間窗也不完全是軟時間窗，大部分更偏向處于軟硬時間窗之間的模糊時間窗。配送車輛一定范圍內早于或晚于約定時間窗會產生相應的成本，影響客戶對于配送的滿意程度，但大部分客戶并不會因此拒收而導致配送失敗。

（2）針對研究的問題進行模型構建時，很可能出現多目標優化的情況，此時解并不唯一，而是有多個非劣解。帕累托最優解可以以最小的損失來換取最優化的效益產出，更好地對多個目標之間進行平衡。

（3）相對于未考慮客戶滿意度的情況，本文在配送時所需的配送車輛更少，配送路徑總長度更短。在同樣的客戶點數量、客戶需求、車輛構造等條件下，考慮客戶滿意度時的總成本更低。除此之外，企業考慮客戶滿意度并采取策略提高客戶滿意度更能維持已有客戶的忠誠度，并且更有利于發掘潛在客戶，提高企業利潤。

本文的研究雖能為企業生鮮冷鏈配送提供理論參考，提醒企業在降低成本的同時也要注重顧客滿意度的提升。但本文所考慮的配送產品均為同一溫度要求，且并未考慮配送過程中交通等突發情況。在未來的研究中可結合現實中的具體問題解決時變路網、異構車輛下的生鮮冷鏈配送問題。