郜振華，朱興偉

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

0 引言

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

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

1 問題描述

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

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

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

2.1 符號及變量描述

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

表1 符號及變量描述

2.2 模型構(gòu)建

2.2.1 成本目標(biāo)函數(shù)

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

(1)配送中心選址成本

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

Cj=c1+c2+c3+c4

(1)

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

(2)

(2)配送成本

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

(3)

(3)制冷成本

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

(4)

2.2.2 顧客滿意度

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

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

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

(5)

顧客送達(dá)滿意度為

(6)

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

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

(7)

2.2.3 碳排放

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

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

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

(8)

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

D**=?2dabQab

(9)

2.3 模型構(gòu)建

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

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

3 算法設(shè)計(jì)與測試

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

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

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

3.2 編碼

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

3.3 初始種群

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

3.4 模擬二進(jìn)制交叉算子

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

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

(21)

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

(22)

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

3.5 自適應(yīng)的交叉與變異

采用基于進(jìn)化階段的自適應(yīng)方法作為個體交叉率與變異率的調(diào)整方法[12]。自適應(yīng)交叉率與變異率的模型的兩個部分如下。

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

(23)

(24)

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

(25)

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

3.6 基于參考點(diǎn)的選擇機(jī)制

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

3.7 算法有效性檢測

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

3.7.1 多目標(biāo)算法評價指標(biāo)

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

(26)

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

3.7.2 算法測試

為了評估基于模型的多目標(biāo)I-NSGA-III算法的性能,本文選取4組測試函數(shù): DTLZ1、DTLZ2、DTLZ3、DTLZ4分別對NSGA-II算法、NSGA-III算法、I-NSGA-III算法進(jìn)行20次測試，表1為得到的評價指標(biāo)IGD的均值，不僅可以評價算法的收斂性還能體現(xiàn)算法的多樣性。設(shè)置種群為500，交叉概率為0.5，變異概率為0.05，分別測試M(目標(biāo)函數(shù)的數(shù)量) 為3的實(shí)驗(yàn)，這是因?yàn)楸疚闹心Ｐ偷哪繕?biāo)函數(shù)個數(shù)是3個。其結(jié)果如表2所示。

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

表2 IGD對比表

4 實(shí)例分析

4.1 已知條件

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

圖2 備選配送中心與客戶點(diǎn)的散點(diǎn)圖

表3 需求點(diǎn)的需求點(diǎn)和服務(wù)時間窗以及服務(wù)時間

表4 配送中心相關(guān)數(shù)據(jù)

4.2 運(yùn)算結(jié)果

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

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

表5 實(shí)例相關(guān)參數(shù)匯總

圖3 帕累托解集

圖4 路徑圖

5 結(jié)論

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