考慮多配送中心的多目標(biāo)動態(tài)車輛路徑優(yōu)化

江雨燕，尹 莉，王付宇

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

0 引言

Dantzing和Ramser在1959年提出車輛路徑問題[1](Vehicle Routing Problem，VRP)。在實際物流配送過程中可能出現(xiàn)原客戶點的需求增多、減少以及交通堵塞等情況，需要配送車輛根據(jù)這些動態(tài)變化調(diào)整配送路線，這種問題就叫做動態(tài)車輛路徑問題，與之對應(yīng)的靜態(tài)車輛路徑問題是指在配送過程中客戶所處位置、客戶的需求量等都是不會發(fā)生變化的。顯然，研究前者具有更深的實際意義。

動態(tài)車輛路徑優(yōu)化問題一直是眾多學(xué)者研究的熱點[2-4]。曹炳汝等[5]在車輛路徑優(yōu)化問題中，考慮需求變化及多種車型等因素，并建立兩階段車輛配送路徑規(guī)劃模型。李陽等[6]針對客戶點不斷更新的動態(tài)需求車輛路徑問題，提出基于延遲服務(wù)的周期性客戶點實時重置策略，建立周期性優(yōu)化模型。范雙南等[7]針對車輛配送過程中出現(xiàn)的配送路線不合理、客戶需求發(fā)生變化等問題,建立動態(tài)車輛路徑優(yōu)化模型。Hu C等[8]在硬時間窗車輛路徑問題中，考慮了動態(tài)變化的客戶需求和行駛時間，建立一個基于新的路徑相關(guān)不確定性集的魯棒優(yōu)化模型。然而，已有文獻(xiàn)在動態(tài)車輛路徑優(yōu)化問題的模型上很少有加入多配送中心這一因素。由于目前大中型城市的物流配送系統(tǒng)中普遍存在多個配送中心，因此在動態(tài)車輛路徑優(yōu)化問題中加入多個配送中心更具有研究意義。

快速非支配排序遺傳算法(NSGA-II)的應(yīng)用十分廣泛，但其具有種群多樣性不足、容易陷入局部最優(yōu)的缺點。針對其不足，許多學(xué)者提出一系列改進(jìn)措施[9-11]。李燕等[12]為了提高NSGA-II算法的收斂性和搜索范圍，提出一種改進(jìn)的NSGA-II算法。吳暖等[13]在NSGA-II算法中引入非劣解進(jìn)行局部搜索，提高了算法的搜索效率。

基于已有研究，本文以運輸成本最小化、碳排放成本最小化和客戶滿意度最大化為目標(biāo)，建立考慮多配送中心的多目標(biāo)動態(tài)車輛路徑優(yōu)化模型，并針對動態(tài)變化采用兩階段求解策略；為求解該模型，設(shè)計一種改進(jìn)的自適應(yīng)非支配排序遺傳算法，最后通過實驗對其進(jìn)行驗證與分析。

1 考慮多配送中心的多目標(biāo)動態(tài)車輛路徑優(yōu)化模型構(gòu)建

1.1問題描述

考慮多配送中心的多目標(biāo)動態(tài)車輛路徑優(yōu)化問題可以描述為：存在多個配送中心，每個配送中心都配有相應(yīng)的車輛，為了按時按量完成配送服務(wù)，在不超過配送車輛最大載貨量的條件下，以車輛運輸成本最小化、碳排放成本最小化以及客戶滿意度最大化為目標(biāo)，根據(jù)配送途中可能出現(xiàn)的信息變化動態(tài)調(diào)整配送路線。

問題假設(shè)：(1)只能用一輛任一配送中心的車輛為客戶完成配送；(2)已知配送中心坐標(biāo)和客戶需求點的坐標(biāo)、需求量和時間窗；(3)配送中心的車輛數(shù)量足夠多且車型統(tǒng)一；(4)車輛從配送中心駛出，配送完成后選擇返回到距離較近的配送中心；(5)車輛的行駛速度全程保持不變；(6)當(dāng)車載貨物配送完或即將配送完，無法為下一客戶配送貨物時，每個車輛都可以在途經(jīng)的多個配送中心進(jìn)行補充貨物，繼續(xù)為下一客戶完成配送。

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

1.2.1 第一階段初始配送模型

目標(biāo)函數(shù)除了運輸成本z1(固定成本和運輸距離產(chǎn)生的成本)最小以外，還有碳排放成本z2最小和客戶滿意度F最大。用Q表示車輛最大載貨量，用X表示車輛載貨量，用ρ*表示車輛滿載時單位距離燃料消耗量，用ρ0表示車輛空載時單位距離燃料消耗量，則

(1)

若車輛從客戶i運送xij單位的貨物到客戶j，則產(chǎn)生的碳排放成本為

e(xij)=c0e0ρ(xij)dij

(2)

其中：dij含義為客戶i到客戶j的距離；c0含義為單位碳排放費用；e0含義為二氧化碳排放系數(shù)；ρ(xij)含義為單位距離燃料消耗量。

式(4)表示客戶i的滿意度函數(shù)，F(xiàn)表示將所有客戶滿意度的平均值定義為平均客戶滿意度，如式(3)所示

(3)

其中

(4)

ei、li分別表示客戶i滿意的最早配送時間和最晚配送時間，e′i、l′i分別表示客戶i可以接受的最早配送時間和最晚配送時間(其中e′i≤ei≤li≤l′i) 。

符號說明：

(1)集合

M=[1,2,…,Kh]為配送車輛的集合，每個配送中心具備Kh(h=1,2,…H)輛配送車；N=[1,2,…,n]為需要服務(wù)的客戶數(shù)的集合，有n個客戶；H=[n+1,n+2,…,n+H]為配送中心數(shù)量的集合，有H個配送中心。

(2)參數(shù)

Qk為配送車輛的容量，k∈{1,2,…Kh}，h∈{n+1,n+2,…n+H}；dij為客戶i與客戶j之間的歐式距離，其中dij=dji，i,j∈(1,2,…n,n+1,n+2,…n+H)，dij=∞時，其含義為禁止從配送中心到配送中心或客戶i與客戶j之間的交通發(fā)生中斷；ck為第k輛車的單位運輸成本，比如燃料成本、司機雇傭工資等，k∈{1,2,…Kh}，h∈{n+1,n+2,…n+H}；Gk為第k輛車的固定成本，k∈{1,2,…Kh}，h∈{n+1,n+2,…n+H}；ti為客戶i得到服務(wù)的時間。

(3)變量

第一階段初始配送模型為

(5)

(6)

(7)

st.

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

約束式(8)表示配送車輛的承載能力；約束式(9)表示配送中心具有的車輛總數(shù)應(yīng)不小于該配送中心派出的車輛數(shù)；(10)和約束式(11)表示任一客戶只被一輛車訪問；約束式(12)表示從配送中心出發(fā)的車輛載貨量為車輛的容量，它是約束式(13)、約束式(14)及約束式(15)的前提條件；約束式(13)表示車輛的運輸量不低于任一客戶的需求量；約束式(14)表示車輛通過客戶點j后，其運輸量發(fā)生變化的關(guān)系式；約束式(15)表示車輛進(jìn)入配送中心補貨的條件，即現(xiàn)有運輸量無法滿足下一客戶的需求時。

1.2.2 第二階段實時優(yōu)化模型

在第一階段初始配送階段中，配送車輛為部分客戶完成了配送服務(wù)，且處于客戶點位置，因此，第二階段將無法進(jìn)行直接調(diào)度。在動態(tài)事件發(fā)生后，第二階段需要及時更新道路交通情況、客戶所在位置及需求量、配送時間窗、車輛狀態(tài)等信息。本文將車輛所在的客戶點設(shè)為虛擬配送中心，第一階段未完成配送的客戶與第二階段新增客戶的總數(shù)量記為S，若Rh表示第一階段派出的車輛數(shù)，Qhz(h=1,2,…H,z=1,2,…Rh)表示派出車輛的剩余載貨量，則用Rh表示虛擬配送中心數(shù)量，虛擬配送中心編號為S+H+1,S+H+2,…S+H+Rh，原配送中心編號為S+1,S+2,…S+H，新派車輛Th(k=Rh+1,Rh+2,…Rh+Th)輛。第二階段實時優(yōu)化模型為

(16)

(17)

(18)

st.

(19)

(20)

(21)

(22)

h∈{S+1,S+2,…,S+H+Rh}

k∈{1,2,…Rh,Rh+1,Rh+2,…Rh+Th}

(23)

(24)

h∈{S+1,S+2,…,S+H+Rh}

k∈{1,2,…Rh,Rh+1,Rh+2,…Rh+Th}

(25)

式(16)包括3部分：第一部分是第一階段派出的車輛對第一階段未完成配送的客戶和第二階段新增加的客戶消耗的運輸成本；第二部分是第二階段新派出車輛產(chǎn)生的運輸成本；第三部分是第二階段新派出車輛的固定成本。式(17)包括兩部分：第一部分是第一階段派出車輛對第一階段未完成配送的客戶和第二階段新增客戶產(chǎn)生的碳排放成本；第二部分是第二階段新派出車輛產(chǎn)生的碳排放成本；式(18)表示的是第一階段未完成配送的客戶和第二階段新客戶的平均客戶滿意度。約束式(19)表示配送車輛容量的限制；約束式(20)和(21)含義為每個客戶只有一輛車為其配送；約束式(22)表示從配送中心新派出車輛的運輸量為車輛的容量，它是約束式(23)、約束式(24)及約束式(25)的初始條件；約束式(23)表示配送任一客戶之前，車輛的運輸量不低于這個客戶的需求量；約束式(24)表示配送車輛經(jīng)過客戶點j后運輸量發(fā)生改變的關(guān)系式；約束式(25)表示車輛進(jìn)入配送中心補貨的條件，即下一客戶的需求大于車輛的載貨量。

2 改進(jìn)的自適應(yīng)非支配排序遺傳算法設(shè)計

2.1 問題的求解策略

對于前文建立的考慮多配送中心的多目標(biāo)動態(tài)車輛路徑優(yōu)化模型，采用兩階段求解策略對其求解，如圖1所示。

2.2 改進(jìn)的自適應(yīng)非支配排序遺傳算法

本文設(shè)計改進(jìn)的自適應(yīng)非支配排序遺傳算法(IANSGA-II)對模型求解。在初始配送階段，配送方案采用IANSGA-II算法求得；由于配送過程中可能出現(xiàn)原有客戶需求變化、新增客戶點以及交通中斷等情況，在一定程度上會影響初始方案，故采用動態(tài)添加和優(yōu)化策略，對所有已規(guī)劃子路徑中尚未服務(wù)的客戶和新增客戶進(jìn)行整合，重新進(jìn)行線路優(yōu)化。算法流程如圖 2 所示。

算法改進(jìn)方式：

(1)自適應(yīng)交叉和變異操作：交叉操作采用正態(tài)分布交叉算子( normal distribution crossover，NDX)[14]。變異操作是采用交換變異，即互換不同基因位上的數(shù)值，互換后產(chǎn)生新的個體。為了使算法搜索能力更強，設(shè)計一種自適應(yīng)的交叉概率和變異概率。如果種群個體的適應(yīng)度值相差較大，則增加交叉概率。如果種群個體的適應(yīng)度值都是良好的，則在成熟狀態(tài)下減少交叉和變異概率。交叉和變異概率的取值如公式(26)和(27)所示。

圖1 兩階段求解策略流程圖

(26)

(27)

(28)

(2)選擇算子 ：為了維持種群多樣性，選擇操作采用平均距離聚類的選擇算子[15]。設(shè)種群P的規(guī)模大小為n，小種群中個體數(shù)量記為ξ，第i個目標(biāo)函數(shù)的最大值和最小值分別記為fj,max和fj,min，則其第j個目標(biāo)函數(shù)的平均距離為

(29)

若個體j與i在同一個小種群內(nèi)，則個體j應(yīng)滿足

fi,min≤fj≤fi,max

(30)

fi,min=((f1+f1,avg),(f2+f2,avg),…,(fλ+fλ,avg))

(31)

fi,max=((f1+f1,avg),(f2+f2,avg),…,(fλ+fλ,avg))

(32)

fi,max和fi,min的含義分別為i小種群中全部個體目標(biāo)函數(shù)的最大值和最小值，λ為目標(biāo)函數(shù)的個數(shù)。

圖2 IANSGA-II算法流程圖

(3)動態(tài)添加和優(yōu)化策略：在動態(tài)添加策略中，按照近鄰優(yōu)先原則，將新客戶添加到距離新客戶最近的路線中。若新客戶的需求大于車輛容量，則將新客戶加入新的服務(wù)隊列中，并派出其他車輛來處理，最后形成一條額外的路線。對于加入新客戶的初始路線，需要對其進(jìn)行重新優(yōu)化。每條新路線包括兩條子路線，一條是己經(jīng)完成服務(wù)且不需要改變的路線，另外一條路徑則需要采用變鄰域搜索算法(VNS)進(jìn)行優(yōu)化。本文采用Lei H等[14]設(shè)計的3種鄰域結(jié)構(gòu)進(jìn)行局部搜索，分別是Inter Route Insertion Inter Route Swap和Inter Route 2-Opt。

3 實驗設(shè)計及分析

3.1 實驗設(shè)計

為了驗證模型及IANSGA-II算法的有效性，本文以某物流企業(yè)為例，該企業(yè)具有4個配送中心，每個配送中心各自擁有10輛同質(zhì)且載重量為5的配送車。在配送開始前，該企業(yè)接收到來自所在城市不同位置的30個客戶的配送訂單。4個配送中心以及30個客戶的信息如表1所示，其中配送中心的編號為1至4。根據(jù)對物流公司實際運輸費用的調(diào)研和文獻(xiàn)[7]，模型中的相關(guān)參數(shù)值如表2所示。

表1 初始客戶及配送中心信息

表2 模型相關(guān)參數(shù)信息

3.2 實驗求解與結(jié)果分析

程序使用Matlab R2016b編寫，并在Intel(R) Core(TM) i5-7200U CPU 2.50 GHz的DELL 筆記本電腦(4核，8 GB內(nèi)存) 上運行。本文用前文實驗算例進(jìn)行算法分析。在初始配送階段采用INSGA-II算法，種群大小為100，最大迭代次數(shù)為100，獨立運行50次，得到Pareto解集如圖3所示。分別選取3個目標(biāo)最優(yōu)時的初始配送路線，如表3所列。

在t等于10時刻，發(fā)生如下的動態(tài)事件：客戶需求點3和7分別增加需求0.4 t和0.2 t；客戶需

圖3 初始配送Pareto最優(yōu)解集

表3 初始配送路線

求點9和14分別減少需求0.2 t和0.3 t；客戶需求點8和17的滿意區(qū)間和可接受區(qū)間分別發(fā)生更改；客戶需求點28和31之間的道路交通發(fā)生中斷；同時有5個新客戶提出配送請求，其客戶信息如表4所示。實時優(yōu)化階段得到的Pareto解集如圖4所示，最優(yōu)路線如表5所示。

表4 客戶變化信息

圖4 實時優(yōu)化 Pareto最優(yōu)解集

表5 實時優(yōu)化路線

為了驗證本文提出的IANSGA-II算法的有效性，在初始配送階段將NSGA-II算法、IANSGA-II算法、MOPSO算法在不同迭代次數(shù)下的評價解集分布性的超體積指標(biāo)(HV，Hypervolume)[16]以及運行時間進(jìn)行比較。實驗中將3種算法在不同迭代次數(shù)下獨立運行50次，計算指標(biāo)的平均值，如表6和表7所示。

表6 超體積指標(biāo)HV對比

表7 算法運行時間對比(單位：s)

從表6可以看出， IANSGA-II的HV基本高于NSGA-II和MOPSO，表明IANSGA-II得到的Pareto解集可以較好地收斂到理想的Pareto前沿，并且具有更好的解集多樣性，說明本文引入的平均距離聚類的選擇算子能夠較好地保證種群的多樣性。此外，從表7可以看出，IANSGA-II在不同迭代次數(shù)下，運行時間均明顯比NSGA-II和MOPSO較短，也進(jìn)一步說明本文引入的自適應(yīng)交叉和變異概率可以較好地加快種群尋優(yōu)速度以及算法的全局搜索能力。

4 結(jié)語

本文針對動態(tài)車輛路徑優(yōu)化問題，結(jié)合多配送中心及多種動態(tài)因素，構(gòu)建了以運輸成本最小化、碳排放成本最小化以及客戶滿意度最大化為目標(biāo)的優(yōu)化模型，該模型更貼近物流配送活動的實際以及滿足生態(tài)文明建設(shè)和生態(tài)環(huán)境綜合治理的內(nèi)在需求；針對該模型，提出了兩階段求解策略，并提出了改進(jìn)的自適應(yīng)NSGA-II算法；通過實驗驗證，表明該算法能夠有效求解多配送中心動態(tài)車輛路徑優(yōu)化模型，并且算法性能更優(yōu)。

未來研究中將考慮不同車型、車輛行駛速度等因素的影響，使問題更貼近實際配送的場景，并改進(jìn)出更加有效的求解算法。