基于改進(jìn)NSGA-II的冷鏈物流多目標(biāo)車輛路徑優(yōu)化

楊 亮,向萬里,王 麗,王超然,朱 亮

(蘭州交通大學(xué) a.交通運(yùn)輸學(xué)院;b.蘭州交通大學(xué) 現(xiàn)代物流研究所，甘肅 蘭州 730070)

生鮮產(chǎn)品的質(zhì)量受物流配送時(shí)間影響較大，配送不及時(shí)則會(huì)導(dǎo)致物流企業(yè)虧損，以及顧客滿意度變化。如何科學(xué)有效的規(guī)劃冷鏈物流行駛路徑、減少成本、提高客戶滿意度，成為學(xué)者關(guān)注的重心[1]。Bortolini[2]提出以運(yùn)營成本、碳足跡和車輛服務(wù)時(shí)間為優(yōu)化目標(biāo)的生鮮食品配送優(yōu)化模型。李善俊[3]以配送成本最小和生鮮品新鮮度最大為優(yōu)化目標(biāo)進(jìn)行求解。

然而，傳統(tǒng)算法經(jīng)常陷入局部最優(yōu)、無法收斂的情況，本文構(gòu)建多目標(biāo)冷鏈物流優(yōu)化模型，設(shè)計(jì)I-NSGA-II算法求解物流配送問題，通過算例驗(yàn)證多目標(biāo)優(yōu)化模型的合理性。

1 問題描述

配送問題描述：1個(gè)配送中心和n個(gè)客戶點(diǎn)的冷鏈物流優(yōu)化，在配送過程中結(jié)合生鮮產(chǎn)品的特點(diǎn)，假設(shè)客戶點(diǎn)的需求、地理位置、配送時(shí)間窗已知，從物流企業(yè)角度出發(fā)考慮如何減少配送總成本、提高客戶滿意度。

2 冷鏈物流多目標(biāo)車輛路徑優(yōu)化模型

2.1 模型假設(shè)

為了更好地建立多目標(biāo)車輛路徑優(yōu)化模型，假設(shè)有如下條件：① 每輛車載重不能超過車輛最大載重；② 每輛車均需從配送中心出發(fā)，配送任務(wù)完成后必須返回配送中心；③ 每個(gè)客戶點(diǎn)只需要執(zhí)行一次配送任務(wù)；④ 配送時(shí)間滿足客戶點(diǎn)的要求，早到或晚到都會(huì)有懲罰；⑤ 不考慮道路擁堵狀況；⑥ 配送總成本包括車輛使用成本、運(yùn)輸成本、時(shí)間懲罰成本、制冷成本、碳排放費(fèi)用、生鮮貨損成本。

2.2 符號(hào)說明

優(yōu)化模型中常用的數(shù)符號(hào)及含義見表1。

表1 符號(hào)定義

2.3 配送成本

1)車輛使用成本。車輛的固定使用成本是一個(gè)常數(shù)，僅與配送所需的車輛數(shù)量有關(guān)。x0jk表示從配送中心到客戶j出發(fā)的車輛，車輛固定成本C1可通過式(1)計(jì)算，即

(1)

2)運(yùn)輸成本。運(yùn)輸成本是指車輛隨著行駛距離變化產(chǎn)生油耗而造成的成本，文中采用單位行駛距離成本與行駛距離的關(guān)系，計(jì)算冷藏車的運(yùn)輸成本C2，即

(2)

3)時(shí)間懲罰成本?？蛻魧?duì)生鮮產(chǎn)品的配送提出的要求比普通貨物配送更高，而軟時(shí)間窗對(duì)時(shí)間要求較為寬松，能極大地優(yōu)化資源配置，在軟時(shí)間窗約束下，如果配送車輛到達(dá)時(shí)間早于客戶i的左時(shí)間窗ETi，則會(huì)產(chǎn)生早到懲罰φ1；在規(guī)定的[ETi,LTi]到達(dá)則不會(huì)產(chǎn)生懲罰；遲于LTi則會(huì)產(chǎn)生晚到懲罰φ2。時(shí)間懲罰成本函數(shù)如圖1所示，其中ET'i表示車輛早到時(shí)間，LT'i表示車輛晚到時(shí)間。

圖1 時(shí)間懲罰成本函數(shù)

配送車輛的時(shí)間懲罰成本為C3，即

(3)

4)制冷成本。運(yùn)輸時(shí)制冷成本受車輛行駛時(shí)間影響，而卸貨時(shí)由于冷藏車門打開，外部空氣進(jìn)入車廂，造成車廂內(nèi)部溫度變化，為了保持車廂內(nèi)部恒定溫度，車輛制冷機(jī)功耗增加，成本也會(huì)隨之變化，所以模型將車輛的制冷成本分為2個(gè)過程產(chǎn)生的成本：運(yùn)輸過程中產(chǎn)生成本、卸貨產(chǎn)生成本。

運(yùn)輸制冷成本為T1，即

(4)

只考慮對(duì)顧客點(diǎn)服務(wù)時(shí)間的卸貨制冷成本T2，則

(5)

式中：t0i表示開始服務(wù)客戶i的時(shí)間；yjk表示客戶j由第k輛車服務(wù)。

總制冷成本為C4，即

C4=T1+T2.

(6)

5)碳排放費(fèi)用。碳排放費(fèi)用是指車輛在行駛過程中隨著距離和載重的變化而產(chǎn)生的CO2排放成本，采用碳排放費(fèi)用=碳稅*碳排放量[4]的計(jì)算方法，綜合考慮車輛載重、油耗計(jì)算產(chǎn)生的費(fèi)用C5，即

(7)

(8)

式中：FCij表示客戶i到j(luò)的碳排放量；ρ0表示載重為0時(shí)的油耗；ρ*表示滿載時(shí)的油耗；Qij表示從客戶i到客戶j的載重量；w表示碳稅。

6)生鮮貨損成本。在只考慮配送時(shí)間對(duì)貨損成本的前提下，本文采用文獻(xiàn)[5]中生鮮損耗系數(shù)的計(jì)算辦法，來描述冷鏈產(chǎn)品隨時(shí)間變化產(chǎn)生貨損成本變化，則整個(gè)配送環(huán)節(jié)中產(chǎn)生的生鮮損耗成本C6為

(9)

式中：T表示冷鏈貨物的保質(zhì)期；r∈(0,1)是時(shí)間敏感因子。

2.4 客戶滿意度

本文主要研究冷鏈物流配送中軟時(shí)間窗對(duì)客戶滿意度的影響，如果配送時(shí)間在客戶左時(shí)間窗之前到達(dá)，客戶滿意度為1；如果在客戶期待時(shí)間窗到達(dá)，客戶滿意度則會(huì)隨著到達(dá)時(shí)間呈線性遞減趨勢(shì)；若配送時(shí)間遲于顧客要求的右時(shí)間窗則客戶滿意度為0?？蛻魧?duì)配送時(shí)間的滿意度函數(shù)Ui為

(10)

2.5 模型建立

冷鏈物流的車輛路徑模型以最小成本Z1(車輛使用成本、運(yùn)輸費(fèi)用、時(shí)間懲罰成本、制冷成本、碳排放費(fèi)用、生鮮貨損成本)、最大客戶滿意度為目標(biāo)進(jìn)行求解。模型如下：

minΖ1=C1+C2+C3+C4+C5+C6，

(11)

(12)

(13)

(14)

xijk=0 ?i=j,?i,j∈N0,?k∈K，

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

式(13)表示容量約束，式(14)表示每輛車只能訪問客戶后必須離開，式(15)表示每個(gè)節(jié)點(diǎn)不能訪問自己，式(16)、式(17)、式(18)表示每個(gè)客戶只能有1輛車進(jìn)行服務(wù)且不能重復(fù)訪問客戶點(diǎn)，式(19)表示所有車輛必須從配送中心出發(fā)進(jìn)行配送，式(20)表示每輛車必須返回配送中心，式(21)、式(22)、式(23)均為決策變量。

3 I-NSGA-II算法設(shè)計(jì)

3.1 遺傳算法

3.1.1 編碼、解碼

染色體編碼采用自然數(shù)編碼的方式，將1，2，3…，n個(gè)客戶隨機(jī)排列，如5-4-6-2-1-3，表示6個(gè)客戶點(diǎn)的隨機(jī)分布。上述編碼方式必須對(duì)染色體進(jìn)行解碼操作，算法按照染色體編碼中基因的順序，在不違反車輛載重約束的條件下，將客戶的需求插入路徑，若超過車輛載重則將該客戶放入下一輛車的路徑，0代表配送中心。例如上述6個(gè)客戶的需求分別為：6、5、7、9、8、3 t，車輛最大載重為20 t。在使每一個(gè)車輛盡可能裝滿的前提下，解碼后的路徑為：第一輛車路徑：0—5—4—6—0；第二輛車路徑：0—2—1—3—0。

3.1.2 交叉

采用遺傳算法順序交叉的方法對(duì)染色體進(jìn)行操作，首先，隨機(jī)選取[a,b]長度的染色體片段，交換父代和母代[a,b]部分基因片段，從b點(diǎn)以后基因起刪除重復(fù)基因；最后，重組基因。例如：父代1：13|2486|75，父代2：86|4573|12，交叉3-6位置的點(diǎn)，得到父代1：4573|13248675，刪除重復(fù)基因得到交叉后的父代1：4573|1286；同理得父代2交叉后的結(jié)果為：2486|5731。

3.2 NSGA-II算法

NSGA-II算法運(yùn)行速度快、收斂性好，是解決多目標(biāo)優(yōu)化問題的算法之一[6]，算法步驟和遺傳算法均需執(zhí)行編碼、解碼、交叉等操作。與遺傳算法不同的是，NSGA-II需要通過快速非支配排序、擁擠度距離計(jì)算，選擇解空間更好的個(gè)體進(jìn)入下一代，保證種群的優(yōu)良性狀。算法中種群進(jìn)化的步驟如圖2所示。

圖2 NSGA-II種群進(jìn)化策略

3.2.1 快速非支配排序

作為NSGA-II算法的重要步驟，快速非支配排序根據(jù)個(gè)體解的水平對(duì)種群實(shí)現(xiàn)分層，指引算法搜索向最優(yōu)Pareto解集的方向進(jìn)行。定義2個(gè)變量：np表示支配個(gè)數(shù)，Sp表示被p支配個(gè)體集合。如圖3所示，對(duì)于求解多個(gè)目標(biāo)且求解均為最小值的問題，圖中每一個(gè)點(diǎn)都表示一個(gè)解。對(duì)于c點(diǎn)而言，a、b點(diǎn)f1，f2值均優(yōu)于c點(diǎn)值，因此c被a，b兩點(diǎn)支配，np=2，Sb={c}。遍歷解集中所有點(diǎn)，記錄np和Sp，將np=0的點(diǎn)記為第一非支配層F1，將其所有個(gè)體賦予非支配序值rank=1(rank是個(gè)體i的非支配排序值)，將F1中的個(gè)體從種群中除去；接著循環(huán)尋找下一支配層中np=0的點(diǎn)，直到種群中所有個(gè)體都分層為止，得到F1?F2?F3?…(?表示優(yōu)先)。

圖3 快速非支配排序算法

3.2.2 選擇

選擇的目的是保留優(yōu)良的個(gè)體進(jìn)入下一代，以防止解的收斂效果不佳。首先對(duì)父代Pt和新子代Qt組合而成的種群Rt進(jìn)行非支配排序，按非支配排序值從小到大排序，將整層個(gè)體放入Pt+1，如果某一層出現(xiàn)Pt+1超過種群最大數(shù)目N時(shí)，計(jì)算擁堵距離，按擁堵距離從大到小放入Pt+1，直到滿足種群數(shù)目N。

3.3 改進(jìn)的NSGA-II

NSGA-II算法在收斂速度過快的同時(shí)，會(huì)出現(xiàn)過早收斂、分布性不佳、局部最優(yōu)等問題；為保證種群多樣性，提高算法收斂性能，通過C-W算法構(gòu)建初始種群，利用M-變異算子、C-進(jìn)擁堵距離計(jì)算的方法來提高算法的性能。

3.3.1 初始解構(gòu)造

NSGA-II算法的解集對(duì)初始種群依賴性很大，改進(jìn)算法通過C-W節(jié)約算法來提升解的可依賴性，構(gòu)建得到NSGA-II-CW算法。C-W節(jié)約算法將n個(gè)客戶點(diǎn)與配送中心相連，形成k條路徑；通過節(jié)約值的大小順序?qū)⒖蛻鬷和客戶j合并，形成0—i—j—…—0的路徑。C-W節(jié)約算法的步驟如下：

首先，計(jì)算節(jié)約值的大小，算法中距離節(jié)約值可通過式(24)計(jì)算，即

s(i,j)=d0i+d0j-dij，

(24)

排序?qū)ふ易畲缶嚯x節(jié)約值對(duì)應(yīng)的客戶i和客戶j，判斷要合并的路徑是否滿足時(shí)間窗約束，滿足則合并至一條配送路徑。其次，判斷路徑合并后是否滿足車輛載重，若滿足則繼續(xù)判斷是否存在只有1個(gè)客戶點(diǎn)的路徑，更新最大距離節(jié)約值；否則重新選擇客戶。當(dāng)1條路徑有2個(gè)或3個(gè)以上客戶時(shí)，計(jì)算不同位置點(diǎn)的節(jié)約值，在節(jié)約值最大的位置插入新客戶，例如：0—3—4—5—0有4個(gè)位置可以插入，分別計(jì)算0—i—3—4—5—0、0—3—i—4—5—0，0—3—4—i—5—0，0—3—4—5—i—0，選取節(jié)約值大的位置插入，最后，判斷是否滿足時(shí)間窗，直到滿足車輛載重量為止。

3.3.2 改進(jìn)變異算子

變異算子將父代的1個(gè)或多個(gè)基因點(diǎn)進(jìn)行交換，如：父代為：123456，對(duì)第二個(gè)位置進(jìn)行變化得：153426。

通過改進(jìn)變異算子，構(gòu)建M-變異算子，結(jié)合C-W算法得到NSGA-II-CW-M算法。M-變異算子可以避免種群出現(xiàn)過早收斂的情況，保證性狀更好的個(gè)體進(jìn)入種群，增加種群的多樣性，在算法中局部搜索更好的解集。變異過程為：隨機(jī)選擇父代個(gè)體進(jìn)行循環(huán)變異操作，對(duì)產(chǎn)生的新個(gè)體進(jìn)行解碼操作，根據(jù)支配關(guān)系判斷變異后的子代是否可放入種群。若產(chǎn)生的新個(gè)體與父代個(gè)體形成支配關(guān)系時(shí)，變異個(gè)體替換被選擇的父代個(gè)體；無任何支配關(guān)系時(shí)，則將新個(gè)體與種群中的其他個(gè)體比較。與種群中其他個(gè)體比較有無支配關(guān)系時(shí)，若形成支配關(guān)系，則直接放棄，繼續(xù)變異操作；若新個(gè)體不支配種群中的個(gè)體，則將產(chǎn)生的變異個(gè)體放入子代，結(jié)束變異。流程如圖4所示。

圖4 改進(jìn)變異算子流程

3.3.3 改進(jìn)擁堵距離計(jì)算

擁堵距離計(jì)算可以使非支配排序邊緣上的個(gè)體在下一代個(gè)體中更具有選擇優(yōu)勢(shì)，擁堵距離是指計(jì)算同一支配層中，個(gè)體i相鄰的個(gè)體i+1和i-1之間的距離。已有的計(jì)算距離方式存在將選擇后的個(gè)體放入下一代解集時(shí)，易出現(xiàn)分布性不佳、局部最優(yōu)的問題，針對(duì)該問題對(duì)擁堵距離計(jì)算進(jìn)行改進(jìn)，得到C-擁堵距離計(jì)算。改進(jìn)前擁堵距離計(jì)算步驟：

Step1:初始化擁堵距離，令d=0；

Step2:對(duì)同一層級(jí)的個(gè)體按目標(biāo)函數(shù)m排序；

Step3:令最大、最小個(gè)體的擁堵距離為d1=dend=inf；

Step4:求解其他個(gè)體的擁堵距離，即

(25)

Step5：對(duì)不同的個(gè)體重復(fù)Step2～Step4的操作，得到個(gè)體i的擁堵距離。

為了體現(xiàn)種群中個(gè)體分布的合理性，加強(qiáng)算法的收斂性，引入C-擁堵距離計(jì)算方式，定義如下:

(26)

其中，

(27)

N=

(28)

式中：M表示目標(biāo)函數(shù)向著最優(yōu)的方向前進(jìn)；N表示讓個(gè)體分布更加合理。M值越大個(gè)體的目標(biāo)函數(shù)越優(yōu)，收斂得越快；N值越大個(gè)體分布性更合理。綜合這2個(gè)參數(shù)后，整合進(jìn)C-擁擠距離計(jì)算方法中，得到I-NSGA-II算法。算法流程如圖5所示。

4 算例分析

為驗(yàn)證改進(jìn)算法的有效性，選取VRPTW數(shù)據(jù)集中C101中50個(gè)客戶點(diǎn)，算例數(shù)據(jù)見表2。設(shè)計(jì)合理的物流配送路徑，滿足所有客戶的貨物需求，以及配送成本最小和客戶滿意度的目標(biāo)。算法中種群數(shù)200，迭代次數(shù)500次，交叉概率0.9，變異概率0.3。根據(jù)市場(chǎng)調(diào)研得出以下參數(shù)：貨物價(jià)格p2=250元/kg，時(shí)間敏感因子r=0.8，保質(zhì)期T=30 000，運(yùn)輸制冷成本s3=0.2，卸貨制冷成本s4=1，車輛最大載重200 kg，車輛的固定成本s1=730元/輛，油耗價(jià)格s2=2元/km，早到等待懲罰φ1=0.1元/min，晚到懲罰φ2=10元/min，車輛載重量為0時(shí)油耗ρ0=0.2 L/km，滿載油耗為ρ*=1 L/km，碳稅ω=2.61，p1=2。

表2 客戶點(diǎn)坐標(biāo)、需求、時(shí)間窗

改進(jìn)算法通過C-W節(jié)約算法構(gòu)建的初始解為7輛冷藏車的配送路徑，初始解的配送成本為70 372.36，客戶滿意度為35.78。解碼得到的配送路徑如圖6所示。

圖6 C-W節(jié)約算法構(gòu)造初始解

通過計(jì)算得到NSGA-II、NSGA-II-CW、NSGA-II-CW-M、I-NSGA-II算法最優(yōu)解集分布圖。NSGA-II-CW算法改進(jìn)后的Pareto前沿分布較NSGA-II算法更好，算法有效搜索初始解構(gòu)造的解空間；而未改進(jìn)的NSGA-II算法表現(xiàn)較差，解集較為集中，易陷入局部最優(yōu)解中。NSGA-II-CW與NSGA-II-CW-M比較，淘汰部分相似個(gè)體，為物流企業(yè)提供多種選擇方案，保證了在配送成本最小的同時(shí)，顧客滿意度最大。I-NSGA-II算法較NSGA-II算法性能提升明顯，克服傳統(tǒng)算法陷入局部最優(yōu)解的問題。

在多目標(biāo)函數(shù)條件下，Pareto解集中的任何一個(gè)解都是最優(yōu)解，如圖7所示。改進(jìn)的算法得到的最優(yōu)解集，客戶滿意度最大為45.57，最小為36.16；成本最大值為23 750，成本最小值為22 033.58。當(dāng)客戶滿意度最大時(shí)使用7輛車對(duì)客戶進(jìn)行服務(wù)，最小時(shí)需要5輛車進(jìn)行服務(wù)。

圖7 改進(jìn)前后Pareto前沿解分布對(duì)比

通過上述實(shí)驗(yàn)結(jié)果對(duì)比，通過對(duì)擁堵距離、變異算子的改進(jìn)，得到的Pareto前沿解收斂性較好，解的多樣性得到了保證，避免了傳統(tǒng)算法中的早熟現(xiàn)象，證明了改進(jìn)算法的有效性。

本文同時(shí)對(duì)多個(gè)算例進(jìn)行了分析，分別選取C102、R01數(shù)據(jù)集中50個(gè)客戶點(diǎn)，得到改進(jìn)前后的算法前沿面如圖8所示。NSGA-II算法解集分布較差，改進(jìn)后的NSGA-II算法Pareto前沿解收斂、分布結(jié)果更好，進(jìn)一步證明了算法的有效性。

(a)R101實(shí)驗(yàn)

5 結(jié)語

本文以配送成本最小、顧客滿意度最大為目標(biāo)對(duì)冷鏈物流配送路徑優(yōu)化進(jìn)行了研究，提出了該問題的多目標(biāo)模型。模型在考慮碳排放的同時(shí)，考慮冷鏈物流運(yùn)輸過程中生鮮產(chǎn)品的損耗，通過I-NSGA-II算法對(duì)模型求解。改進(jìn)的算法構(gòu)造良好的初始解，確保解空間可以更加趨于最優(yōu)解集，避免出現(xiàn)局部收斂、早熟等問題。通過改進(jìn)變異算子、擁堵距離計(jì)算，調(diào)整種群搜索方向，保持了種群的多樣性。最后通過實(shí)驗(yàn)證明了本文所提算法的有效性，顯著提升了收斂效率，對(duì)傳統(tǒng)算法存在的問題也得到了一定的改進(jìn)。