考慮碳排放的冷鏈多配送中心選址與路徑優(yōu)化

郜振華，朱興偉

(安徽工業(yè)大學管理科學與工程學院 安徽 馬鞍山 243032)

0 引言

生鮮產品本身的易腐性決定了冷鏈物流與其他物流不同，其時效性更為重要。顧客對產品本身新鮮程度的要求提高，對環(huán)保和碳排放問題的重視和關注，這些都給冷鏈物流帶來挑戰(zhàn)。因此，應合理有效規(guī)劃冷鏈配送中心選址與路徑。這與以往僅僅考慮路徑問題不同，可以從整體上優(yōu)化配送路徑，降低選址成本和配送成本，提高配送的準時率，還能縮短配送里程，減低制冷成本與排放量，與此同時給顧客帶來較高質量服務。

求解選址與路徑優(yōu)化問題有很多種算法，常用的有混合遺傳算法[1]、蟻群算法[2，3]、混合免疫算法[4]等。國內外學者對冷鏈生鮮配送中心選址與路徑問題進行不同研究，并且取得許多成果。Helena M[5]等人針對改善環(huán)境與經濟效益的條件下，提出LDVRP模型，并且考慮在配送過程中的制冷排放，建立車輛路徑模型；Okan Dukkanci[6]等人還提出了一種基于整數規(guī)劃的算法和迭代局部搜索算法，從成本、燃料消耗和排放等方面分析若干參數對選址和路由決策的影響；Zhitao Xu[7]等人研究時變車輛速度和軟時間窗的有能力的綠色車輛路徑問題，將GVRP發(fā)展為一個包含燃料消耗計算算法的多目標混合整數非線性規(guī)劃( MINLP )模型；張明亮等人[8]根據時間和產品的新鮮程度滿意度建立多車型VRP模型；段硯等[9]、王旭坪等[10]研究在考慮碳規(guī)則下的冷鏈車輛路徑優(yōu)化問題，來減少在運輸中的碳排放。

1 問題描述

本文研究的考慮碳排放冷鏈多配送中心選址及路徑優(yōu)化問題，具體為：某個生鮮電商的4個備選配送中心對N個客戶進行配送；配送中心和客戶點是已知的；客戶軟時間窗是已知的；冷藏車的相關數據是已知的。在符合文中給出的所有約束條件下，綜合考慮最低成本、最大顧客滿意度以及最低碳排放3個目標，對整體配送中心選址及路徑方案進行優(yōu)化求解。

為了科學研究的嚴謹性以及方便研究計算，本文對配送中心選址及配送車輛路徑有著以下一系列基本假設：(1)配送車輛從配送中心出發(fā)到客戶點，然后再回到配送中心形成一個閉環(huán)并且一條路線有一輛車配送。(2)一個客戶點有且只能被一個配送中心和一輛車服務，并且一次性配送完成，避免二次配送。(3)配送中心只能對6公里內的客戶點進行服務。(4)因為上班高峰期，凌晨5:30之后，時速從30 km/h降到20 km/h。(5)顧客不僅對車輛到達客戶點的時間有要求，并且對農產品的新鮮程度也有著較高的要求。(6)為客戶點服務的車輛有著統(tǒng)一容量、油耗、制冷成本，配送量不能超過車輛統(tǒng)一的容量。(7)每個客戶點的需求量、坐標、能夠接受的服務時間假設都是提前了解的，配送中心的固定成本和容量也是已知的。(8)車輛都是同時從配送中心出發(fā)的。

2 數學模型

2.1 符號及變量描述

文中涉及的符號及變量如表1所示。

表1 符號及變量描述

2.2 模型構建

2.2.1 成本目標函數

最低成本包括配送中心選址成本、配送成本、制冷成本3個部分組成。

(1)配送中心選址成本

配送中心選址是一個影響久遠的戰(zhàn)略決策，配送中心的選址直接影響到后來的車輛路徑的設計，所以選址的重要意義顯而易見。一個配送中心的成本通常包括租金c1、管理成本c2、制冷成本c3，改造成本c4，可以表示為

Cj=c1+c2+c3+c4

(1)

被選中的所有配送中心總選址成本

(2)

(2)配送成本

配送成本由于不同客戶點的軟時間窗不同，在配送車輛較少的前提下，選擇最優(yōu)的路徑對提高顧客滿意度、減低配送成本和碳排放都非常重要。配送成本包括制冷車輛的啟動費和運輸費，可以表示為

(3)

(3)制冷成本

本文將制冷成本與時間相聯系，將制冷成本分為兩個部分，一個部分為運輸時的制冷成本，另一個則是為客戶點卸貨時(服務時間)的成本?？梢员硎緸?/p>

(4)

2.2.2 顧客滿意度

本文對顧客滿意度研究從配送時間和產品的新鮮程度兩個方面進行研究，并且以賦權的形式將這兩種影響因素結合起來。

(1)送達時間的顧客滿意度

已知客戶最佳時間窗[Sta2Sta3]，如果配送車輛到達客戶點時間在[Sta2Sta3]，則顧客滿意度為100%；客戶可接受服務時間[Sta1Sta4],假若配送車輛到達客戶點的時間點在[Sta2Sta3]之外，在[Sta1Sta4]之內客戶滿意度隨著時間變化而變化；如果配送車輛到達客戶點的時間在[Sta1Sta4]之外，客戶滿意度則直接為零?？蛻魸M意度與配送車輛送達時間函數表達式

(5)

顧客送達滿意度為

(6)

(2)產品新鮮程度的顧客滿意度

產品的新鮮程度考慮到是因外部因素導致其新鮮程度的變化，因此，產品的新鮮度跟配送車輛到達客戶點的時間有關，其函數表達式為F(t)=e-σti。產品新鮮程度的顧客滿意度可以表示為

(7)

2.2.3 碳排放

碳排放量的消耗是燃油所直接造成的，車輛的這部分燃油消耗與客戶節(jié)點配送的車輛在運輸貨物所行駛路程中的排放量以及車輛上貨物制冷所消耗燃油的碳排放。

(1)車輛在運輸貨物所行使路程中的排放量

D*=?1×φ(Qab)×dab

(8)

(2)車輛在運輸貨物所行使路程中制冷的排放量

D**=?2dabQab

(9)

2.3 模型構建

綜上所述，考慮的碳排放的冷鏈多配送中心選址及路徑優(yōu)化三目標模型為

(10)

maxS=εs1+θs2

(11)

minF=D*+D**

(12)

約束條件除了公式(5)之外，還有

(13)

(14)

(15)

(16)

(17)

xabk∈(0,1),a≠ba,b=1,2,…,n+m,k=1,2,…,l

(18)

xj∈(0,1),j=1,2,…,n

(19)

yji∈(0,1),j=1,2,…,n,i=1,2,…,m

(20)

式(13)表示每個客戶點只能被一個配送中心服務，而且客戶點也只能被一輛車配送。式(14)表示每輛車最多服務一個配送中心。式(15)表示每輛配送車都從配送中心出發(fā)，完成配送任務后再返回配送中心。式(16)表示在選擇配送中心為客戶點進行配送的時候，只有那些被選擇的配送中心才能對客戶進行配送。式(17)由于配送車輛載量有限，所有每條線路上客戶點全部需求之和不能超過車輛的載量限制。式(18)、式(19)、式(20)為決策變量。

3 算法設計與測試

本文選用標準NSGA-III[11]作為基礎算法進行求解，設計了改進的NSGA-III算法，記做I-NSGA-III。在I-NSGA-III中，考慮到需求解模型的復雜性，采取實數編碼；同時使用基于進化階段的自適應方法作為個體交叉率與變異率的調整方法過程并且采用模擬二進制交叉，增加算法的空間搜索能力，為算法后續(xù)操作的多樣性奠定基礎。

3.1 I-NSGA-III的算法求解過程

采用I-NSGA-III的算法求解考慮碳排放的冷鏈多配送中心選擇及路徑優(yōu)化模型的流程如圖1所示。

3.2 編碼

標準NSGA-III算法所采用的編碼規(guī)則并不適用于本文提出的考慮碳排放的冷鏈多配送中心選址及路徑優(yōu)化模型求解，本章提出的INSGA-III算法采用實數編碼規(guī)則。首先，與其他常見的編碼方法相比，實數(浮點數)編碼方法能夠表示范圍較大的數，同時降低算法計算的復雜性，具有較高的精度和魯棒性，適用于處理復雜的多約束優(yōu)化問題。

3.3 初始種群

初始種群的優(yōu)劣會直接影響算法迭代的執(zhí)行效率，所以初始種群的生成方法和種群規(guī)模在一定程度上影響了帕累托解集的質量。而標準NSGA-II算法中的初始種群是隨機生成的，并沒有做太多的篩選限制。所以，本文在隨機生成初始種群的基礎上加入了篩選條件，通過對初始種群的配送中心的容量和輻射范圍的限制，在一開始就將不滿足條件的染色體直接淘汰，從而大大提高了初始種群的質量。

3.4 模擬二進制交叉算子

初始NSGA-III算法采用的單點交叉，本文I-NSGA-III進化產生新解過程是采用模擬二進制交叉，對于兩個父體x1與x2，按照式(21)生成兩個子個體x′1與x′2。

圖1 I-NSGA-III算法流程圖

(21)

其中，γ為隨機變量，其在解的每一維上都需要重新生成，即

(22)

其中，μ是均勻分布于區(qū)間(0,1)上的隨機數，η是交叉參數，其值為一常數。

3.5 自適應的交叉與變異

采用基于進化階段的自適應方法作為個體交叉率與變異率的調整方法[12]。自適應交叉率與變異率的模型的兩個部分如下。

(1)當非支配解個數小于10時，個體交叉概率與變異概率的模型為

(23)

(24)

(2)當非支配解的個數不小于10時，該情況下的個體交叉率模型不變，而變異率的模型為

(25)

當中PC、Pm分別是個體交叉率和變異率，N是迭代次數，L是個體編碼的長度。N1、N2、β都是調節(jié)參數。

3.6 基于參考點的選擇機制

標準的NSGA-III算法結構與標準NSGA-II算法相似，最大區(qū)別就是在與NSGA-III算法采用的是基于參考點對個體進行選擇，而標準NSGA-II采用的是擁擠距離對個體進行選擇，這使得NSGA-III在對3個及3個以上目標函數進行求解時不僅提高種群的多樣性還降低計算代價。

3.7 算法有效性檢測

為驗證所提模型及方法的可行性和有效性，本文設計了算法測試。實驗在MATLAB R2019a軟件上實現，系統(tǒng)為Windows10專業(yè)版，處理為Intel(R) Core(TM) i5-4210U CPU @ 1.70 GHz～2.40 GH，運行內存8 GB的筆記本電腦上進行測試。

3.7.1 多目標算法評價指標

IGD為二元評價指標[13],通過計算真實帕累托前沿中所有解與算法求解出非支配解的平均歐式距離，從而評估解集的收斂性與多樣性。IGD值越小，表示解集越逼近真實帕累托前沿且分布均勻，解集的收斂性與多樣性佳。計算公式為

(26)

其中d(x*,X)表示解x*ep*到X中的最小歐式距離，|P*|表示P*內解的個數。

3.7.2 算法測試

為了評估基于模型的多目標I-NSGA-III算法的性能,本文選取4組測試函數: DTLZ1、DTLZ2、DTLZ3、DTLZ4分別對NSGA-II算法、NSGA-III算法、I-NSGA-III算法進行20次測試，表1為得到的評價指標IGD的均值，不僅可以評價算法的收斂性還能體現算法的多樣性。設置種群為500，交叉概率為0.5，變異概率為0.05，分別測試M(目標函數的數量) 為3的實驗，這是因為本文中模型的目標函數個數是3個。其結果如表2所示。

從表2中可以看出，I-NSGA-III在測試函數DTLZ1-4上的IDG值比較小。因此，可以說明I-NSGA-III算法求解時的多樣性和收斂性更為優(yōu)秀，同時也說明I-NSGA-III在解決三目標問題的優(yōu)越性。

表2 IGD對比表

4 實例分析

4.1 已知條件

某企業(yè)欲在4個備選配送中心之中選擇選性開放N個，對22客戶點進行配送，備選配送中心與客戶點散點圖如圖2所示，客戶點的需求點，最佳時間，可接受時間，服務時間如表3所示，配送中心成本參數如表4所示，其他參數如表5所示。

圖2 備選配送中心與客戶點的散點圖

表3 需求點的需求點和服務時間窗以及服務時間

表4 配送中心相關數據

4.2 運算結果

文采用I-NSGA-III算法對考慮碳排放的冷鏈多配送中心選址與路徑模型進行求解，通過MATLAB R2019a軟件上得帕累托解集，如圖3所示。

如圖3帕累托解集所示，可以清楚看出配送中心開放策略有3種且方案解分布廣泛，說明了I-NSGA-III算法在求解時多樣性。目標函數D與目標函數S成反比，目標S與目標F成反比，正是因為目標函數中存在反比例關系，才能求出帕累托解，而不是出現最優(yōu)解。如果不對目標函數進行加權處理，就可以認為帕累托解集之內任意一個解都不比其他解差。因此，可以從圖3帕累托解集中任意選出一個解得到其方案是開放第1和第3備選冷鏈配送中心，其配送路線如圖4所示，成本為5570.97元，顧客滿意度為0.87，碳排放為49.67 kg。

表5 實例相關參數匯總

圖3 帕累托解集

圖4 路徑圖

5 結論

本文在考慮到碳排放基礎上，研究綜合客戶滿意度的冷鏈多配送中心選址與路徑優(yōu)化問題。綜合考慮成本、顧客滿意度、碳排放3個目標，構建本文問題模型，采用改進的I-NSGA-III算法求解，并且對I-NSGA-III與NSGA-II和NSGA-III進行測試函數測試對比，結果顯示I-NSGA-III求解時更具有多樣性和收斂性。最后從實例求解的結果可以得知，在現有情況下隨著開放第1和第3配送中心更能達到最高顧客滿意度和一個較低碳排放量。本文可以為生鮮電商提供一些方案，企業(yè)若適當提高成本，既可以降低碳排放，又可以獲得較高的顧客滿意度。