多車型綠色車輛路徑問題優(yōu)化模型

何東東，李引珍

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，蘭州 730070)(*通信作者電子郵箱liyz01@mail.lzjtu.cn)

0 引言

能源與環(huán)境問題已成為全球的熱點(diǎn)議題。人類活動產(chǎn)生的二氧化碳(CO2)是溫室氣體的主要來源，也是氣候變化和極端天氣出現(xiàn)的主要源頭。國際能源署(International Energy Agency, IEA)稱，2017年全球能源相關(guān)二氧化碳排放量增長1.4%，達(dá)到325億噸的歷史最高點(diǎn)。這一增長率相當(dāng)于增加4.60億噸的二氧化碳排放量，等同于1.7億輛汽車的排放量。

另一方面，運(yùn)輸行業(yè)不僅是能源消耗較大的產(chǎn)業(yè)，而且是碳排放大戶，據(jù)世界資源學(xué)院的統(tǒng)計(jì)，交通運(yùn)輸行業(yè)的二氧化碳排量占全球總排量的20%。實(shí)施綠色運(yùn)輸已經(jīng)成為減少碳排放的必然趨勢。自文獻(xiàn)[1]建立了帶時間窗且以碳排放和距離為目標(biāo)的運(yùn)輸車輛綜合優(yōu)化模型，分析了不同交通條件下速度優(yōu)化對模型的影響之后，文獻(xiàn)[2]將碳排放和燃料消耗的最小化作為優(yōu)化目標(biāo)，建立EVRP(Emissions Vehicle Routing Problem)的模型和算法，對不同擁堵水平下EVRP的解進(jìn)行了比較和分析。文獻(xiàn)[3]同時考慮經(jīng)濟(jì)和環(huán)境因素，將二氧化碳排放量、燃料消耗、旅行時間等納入到車輛路徑規(guī)劃中，從而求得經(jīng)濟(jì)環(huán)保的車輛路徑，提出了污染路徑問題(Pollution Routing Problem, PRP)。文獻(xiàn)[4-6]對污染路徑問題(主要是以二氧化碳排放量和油耗量為目標(biāo))的模型和算法進(jìn)行了拓展和創(chuàng)新研究，并對綠色車輛路徑問題進(jìn)行了評述。文獻(xiàn)[7]擬合了一個關(guān)于燃料消耗率(Fuel Consumption Rate, FCR)和車輛總重量之間的線性表達(dá)式，并提出了考慮FCR的有限容量車輛路徑問題(FCR considered Capacitated Vehicle Routing Problem, FCVRP)模型，確定并討論了導(dǎo)致燃料消耗變化的因素。文獻(xiàn)[8]建立購買或銷售碳排放權(quán)的混合整數(shù)規(guī)劃多車型車輛路徑問題模型，采用禁忌算法獲得的解表明碳排放量可以顯著減少且不用犧牲碳交易所帶來的收益。文獻(xiàn)[9]將燃料成本、碳排放成本和車輛使用成本納入傳統(tǒng)VRP問題中建立最低碳排放模型，構(gòu)造RS-TS(Route Splitting Tabu Search)算法，通過數(shù)值實(shí)驗(yàn)揭示了距離、燃料消耗、行程時間和其他參數(shù)之間的關(guān)系。文獻(xiàn)[10]考慮駕駛員小時成本、燃料成本、客戶地理位置、車隊(duì)組成(單一車型與多車型)，以及取貨或者送貨等一系列子問題，利用LANTIME禁忌搜索算法對算例求解表明，以不同成本作為求解目標(biāo)得到不同的車輛路徑。近年來國內(nèi)對此類問題的研究也日益增多，文獻(xiàn)[11-20]構(gòu)建了不同目標(biāo)函數(shù)下的低碳、低油耗、低成本的車輛路徑問題模型，并設(shè)計(jì)了相應(yīng)的算法進(jìn)行求解，如禁忌搜索算法、遺傳算法、粒子群算法、極線掃描算法，也都取得了很多成果。從以上研究可以看出綠色車輛路徑問題成為現(xiàn)階段研究的熱點(diǎn)。

為降低物流配送過程中車輛產(chǎn)生的廢氣污染，本文提出了帶時間窗的多車型綠色車輛路徑問題(Green Multi-type Vehicles Routing Problem with Time Windows, G-MVRPTW)模型，且以能耗、碳排放和司機(jī)工資最小為目標(biāo)建立了相應(yīng)的模型,并設(shè)計(jì)了改進(jìn)的禁忌搜索算法求解該問題。通過數(shù)值實(shí)驗(yàn)驗(yàn)證了所提模型和算法的有效性和可行性，為低碳運(yùn)輸及管理提供決策支持和方法指導(dǎo)。

1 問題的描述

本文研究的G-MVRPTW可描述為：一個配送中心D具有M種類型的車輛，其相應(yīng)車型的載重量為Qm(m={1,2,…,M})，各種類型的車輛數(shù)有km輛。不同類型的車輛從配送中心出發(fā)對若干個客戶點(diǎn)進(jìn)行服務(wù)，設(shè)每個客戶點(diǎn)的需求量不超過車輛的載重，即：maxdi≤Qm，每條子路徑的客戶需求總量不超過車輛載重，車輛完成任務(wù)后返回配送中心。求解滿足客戶需求且以能耗、碳排放和司機(jī)工資為總成本最小的情況下，通過模型和算法來尋找環(huán)境友好型綠色路徑，以達(dá)到承運(yùn)人經(jīng)濟(jì)成本和政府環(huán)保要求之間的均衡。

2 模型的建立

2.1 能源消耗和碳排放量計(jì)算

計(jì)算車輛油耗量需要依據(jù)多種因素，本文參考文獻(xiàn)[21-24]不斷通過對比分析研究取得的綜合油耗率模型，并結(jié)合文獻(xiàn)[3]的研究：當(dāng)車輛速度v<40 km/h時，發(fā)動機(jī)系統(tǒng)決定了燃油消耗量；當(dāng)車輛速度v≥40 km/h時，車輛牽引功率Pt決定了燃油消耗量。因此本文假定車輛在距離為Dij的弧(i,j)上以運(yùn)行速度vij≥40 km/h為客戶進(jìn)行配送，則在弧(i,j)上燃料的消耗量Fij的近似計(jì)算式為：

Fij≈Pt(Dij/vij)/q≈

(1)

研究表明，車輛的碳排放量與油耗量成正比，則弧(i,j)上的CO2的排放量為：

Eij=ε×Fij

(2)

上述模型式(1)～(2)中使用的具體參數(shù)及取值如表1所示。

表1 模型式(1)、(2)參數(shù)Tab.1 Parameters of model formula (1) and (2)

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

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

?i,j∈V0,m∈M,C是一個很大的正整數(shù)

(11)

ei≤ti≤li;?i∈V0

(12)

(13)

(14)

?i,j∈V且i≠j,m∈M

(15)

模型說明：式(3)是只考慮總里程最小的傳統(tǒng)車輛路徑的目標(biāo)函數(shù)；式(4)是本文G-MVRPTW模型的目標(biāo)函數(shù)；約束條件式(5)～(6)表示每個客戶只被一輛車訪問一次；式(7)表示車輛從車場出發(fā)完成任務(wù)最后回到車場；式(8)為節(jié)點(diǎn)平衡方程；式(9)表示每個客戶的需求被滿足；式(10)為送貨時車輛載重約束；式(11)～(12)為時間窗約束；式(13)為消除子回路約束；式(14)～(15)分別是決策變量和非負(fù)約束。

3 算法設(shè)計(jì)

多車型綠色車輛路徑問題是VRP的子問題，而VRP為非確定性多項(xiàng)式(Non-deterministic Polynomial, NP)難問題。考慮到所求解問題的NP特性及其規(guī)模，精確算法(分枝定界法、割平面法等)無法避開指數(shù)爆炸問題，只能求解小規(guī)模VRP問題，難以求得最優(yōu)解[25]；而模擬退火、禁忌搜索、遺傳算法、蟻群算法和神經(jīng)網(wǎng)絡(luò)等通用啟發(fā)式算法已被用于求解VRP問題，也取得了很好的效果。文獻(xiàn)[26-27]較為全面的綜述和分析表明，禁忌搜索是求解VRP及其變型問題的有效算法，因此，本文設(shè)計(jì)了改進(jìn)的禁忌搜索算法求解G-MVRPTW模型。

3.1 初始解

根據(jù)客戶點(diǎn)時間窗的最遲開始服務(wù)時間li的大小，對客戶編號進(jìn)行升序排序；如果最遲開始服務(wù)時間相同，則比較li-ei的大小，較小的排在前面，如得到客戶以1～9順序排列。對于車輛的分配，由于maxdi≤Qm，且研究表明：多用一輛車所帶來的固定費(fèi)用總是超過其因總行駛距離縮短或速度優(yōu)化等所帶來的節(jié)省，所以首先使用大容量的車進(jìn)行裝載，當(dāng)該車輛的聲譽(yù)裝載量無法滿足下一個客戶需求時，將此時的裝載容量∑di與次大型車的車容量Qm進(jìn)行比較，如果∑di≤Qm，則換到次大型車，同時次大型車還可以繼續(xù)向下作類似比較；否則，采用原大容量車型；從而達(dá)到選取最適合車輛，使得裝載率最高，提高車輛使用率。當(dāng)某種車型的車輛使用數(shù)超過車輛擁有數(shù)時，選取下一種車型，直到所選有客戶點(diǎn)被分配。根據(jù)上述方法，將客戶1分配給第1輛車，可得第1輛車的配送路徑0-1-0，并判斷添加客戶2到第1輛車能否滿足約束條件，若滿足則配送路徑為0-1-2-0；否則將客戶2分配給第2輛車，得到第1、2輛車的配送路徑為0-1-0-2-0。依此類推，直到所有客戶均都被分配，從而得到一個初始可行解0-1-2-6-0-3-5-8-0-4-7-9-0。

3.2 鄰域結(jié)構(gòu)

解的質(zhì)量和算法的搜索速度很大程度上依賴于鄰域結(jié)構(gòu)的設(shè)計(jì)，本文根據(jù)編碼的特點(diǎn)設(shè)計(jì)了3種鄰域結(jié)構(gòu)：

1)插入算子Insertion。隨機(jī)從子路徑A選取一個點(diǎn)插入到子路徑B中，生成鄰域解，但是在插入到B時，必須使得子路徑的客戶號序列是遞增的，這樣可以保證訪問順序滿足最遲開始服務(wù)時間li的約束。如0-1-2-6-0-3-5-8-0-4-7-9-0第2條子路徑中的客戶5，插入子路徑1的可能位置為012560，而051260則不滿足最遲開始服務(wù)時間的約束。隨后評估所有的可能性后選擇向當(dāng)前迭代最優(yōu)的方向進(jìn)行移動。在下面算子中，同樣需要遵循子路徑內(nèi)客戶序號遞增規(guī)則。

2)交換算子Swap。隨機(jī)選取兩條路徑中的兩點(diǎn)進(jìn)行交換插入生成鄰域解。

3)混合算子Hybrid。在一次迭代中隨機(jī)選擇算子1)或者2)。

3.3 解的評價

本文算法利用帶有懲罰機(jī)制的解的評價將算法設(shè)計(jì)為可接受導(dǎo)致不可行解的變換，產(chǎn)生可行解和不可行解的混合，以便通過不可行解的過渡，對鄰域空間進(jìn)行充分搜索，找到更好的可行解，避免過早陷入局部最優(yōu)。因此，解的評價參考文獻(xiàn)[28-29]，改進(jìn)為：

(16)

其中：P1、P2只表示每個目標(biāo)的優(yōu)先級，即P1?P2，是定性的概念，不賦予任何具體數(shù)值；K是最少子路徑數(shù)(即最小車輛數(shù))；Z(r)、E(r)分別是子路徑r上的總費(fèi)用值和超出載重部分；p為每條不可行路徑的懲罰權(quán)重。若一個解是可行的，則E(r)=0。p∈[50，2 000]，開始時等于200，并通過一個自調(diào)整參數(shù)來加權(quán)，每隔10次迭代測試一次。若前面的10個解是可行的，則將其除以2；若所有的10個解都是不可行的，則將其乘以2。這種機(jī)制由文獻(xiàn)[30]提出，可以產(chǎn)生一種可行解和不可行解的混合，有利于減少早熟的可能性。

3.4 禁忌表

禁忌表主要由禁忌對象和禁忌長度組成。本文構(gòu)造了一個N×N的矩陣作為禁忌表，以記錄禁忌對象的禁忌情況。如果進(jìn)行了3.2節(jié)中1)～3)操作，則將被操作客戶點(diǎn)i和j的禁忌情況存入矩陣的元素(i,j)中，禁忌長度采用文獻(xiàn)[30]的隨機(jī)禁忌長度，取值為[lmin,lmax]的隨機(jī)整數(shù)。

4 數(shù)值實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)設(shè)置

本文算例的測試數(shù)據(jù)采用隨機(jī)生成，客戶需求量是區(qū)間[1，9]內(nèi)隨機(jī)產(chǎn)生的整數(shù)(噸)，客戶信息見表2，其中，設(shè)定客戶點(diǎn)0為配送中心。

表2 客戶信息表Tab.2 The information of customers

客戶之間的距離矩陣D是[2，26]的隨機(jī)整數(shù)(km)，見表3；每兩個客戶點(diǎn)之間的速度矩陣V為[12，23]的隨機(jī)整數(shù)(m/s)見表4；車輛類型及相關(guān)參數(shù)見表5。表3～4中，D和V都是對角矩陣。

表3 客戶間距離矩陣 kmTab.3 Distance matrix between customers km

表4 客戶間速度矩陣 m/sTab.4 Speed matrix between customers m/s

表5 不同車輛類型相關(guān)參數(shù)Tab.5 Relative parameters of different types of vehicles

4.2 模型的計(jì)算結(jié)果及分析

4.2.1 算法性能分析

針對改進(jìn)的禁忌搜索算法的性能，本文以模型的總成本最小為優(yōu)化目標(biāo)，通過Java編程，用本文改進(jìn)的禁忌搜索算法和傳統(tǒng)禁忌搜索算法進(jìn)行數(shù)值實(shí)驗(yàn)，分別運(yùn)行10次，實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果如表6所示。表6中，平均偏差=(平均解-最優(yōu)解)/最優(yōu)解，最大偏差=(最劣解-最優(yōu)解)/最優(yōu)解。分別記錄某一次傳統(tǒng)禁忌搜索算法和改進(jìn)的禁忌搜索算法求得最優(yōu)解時的解的變化如圖1所示。由表6和圖1可知，改進(jìn)的禁忌搜索算法能在很短的時間得到最優(yōu)解，并表現(xiàn)出明顯的優(yōu)勢，收斂性能也有所提升，驗(yàn)證了改進(jìn)算法的可行性和有效性。

圖1 不同算法收斂效果示意圖Fig.1 Schematic diagram of convergence effects for different algorithms表6 不同算法求解數(shù)值實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果Tab.6 Statistical results of different algorithms for solving numerical experiments

算法最優(yōu)解平均解平均偏差/%最大偏差/%未得到最優(yōu)解個數(shù)平均計(jì)算時間/s傳統(tǒng)禁忌搜索算法755.633784.8773.8719.99413.170改進(jìn)的禁忌搜索算法755.633778.9323.0811.2728.122

4.2.2 結(jié)果分析

采用禁忌搜索算法分別求解以最小走行距離、最小油耗和碳、最小司機(jī)工資(即為最短服務(wù)時間，由模型可以看出司機(jī)成本與旅行總時間有關(guān)，旅行總時間=司機(jī)工資/單位時間司機(jī)工資)、最小總成本為優(yōu)化目標(biāo)，得到的路徑安排如表7所示。

由表7可得：作為不同的運(yùn)輸參與者可以選用不同的路徑方案。如：從政府節(jié)能減排的角度出發(fā)，則S2最小油耗和碳排放是政府的最佳選擇；對于承運(yùn)人追求的就是總成本最小，則S4最小總費(fèi)用是承運(yùn)人的最佳選擇。如若涉及物流外包的情況，則對于物流提供方，S1最短走行距離或者S3 最短服務(wù)時間便是其最佳選擇，因?yàn)槲锪魈峁┓较Ｍ獬鋈サ能囕v走行越短的距離并且用盡量短的時間完成運(yùn)輸任務(wù)，這樣可以再為下一個有運(yùn)輸需求的客戶服務(wù)，獲得更大的收益。

表7 不同目標(biāo)最小化算得的車輛路徑方案明細(xì)Tab.7 Details of vehicle routing schemes with minimization of different targets

同時可以看出：司機(jī)成本占總成本約60%，因此本文在算法構(gòu)建時盡量減少車輛數(shù)的使用的做法是正確的，同時驗(yàn)證了多用一輛車所帶來的費(fèi)用總是超過其因總行駛距離縮短或者速度優(yōu)化等所帶來的節(jié)省。另一方面，油耗和碳的成本占總成本的40%左右，而二氧化碳成本占比非常不明顯，大約在3%(40%×0.5/(6.5+0.5)≈2.86%)，并且本文設(shè)定的二氧化碳排放成本是190 元/噸，大大高于目前50～60 元/噸的碳價；同時也說明了作為發(fā)展中國家，國家鼓勵產(chǎn)業(yè)發(fā)展，因此不能制定太高的碳價，因此碳價普遍偏低，目前的碳價不會顯著影響企業(yè)的物流運(yùn)輸安排，因此很少有運(yùn)輸企業(yè)在運(yùn)營過程中考慮環(huán)保因素。但是為了有效控制溫室氣體排放，推進(jìn)綠色低碳轉(zhuǎn)型發(fā)展，參與和引領(lǐng)全球氣候治理，政府可以適當(dāng)調(diào)高碳價，讓碳成本在總成本中占比提高，從而讓運(yùn)輸企業(yè)將碳排放成本考慮到總的運(yùn)輸成本中去，才能有效地讓運(yùn)輸行業(yè)減少二氧化碳的排放。從更長遠(yuǎn)的情況來看，政府將來一定會加大節(jié)能減排的管控，則對于運(yùn)輸行業(yè)來講，新能源車輛投入運(yùn)輸市場進(jìn)行配送將是新的趨勢。

分析由表7各項(xiàng)指標(biāo)得到的結(jié)果，得出以下結(jié)論：

1)路徑最短的不一定能耗越小。

考慮以走行距離為目標(biāo)的車輛路徑安排S1比以低碳為目標(biāo)S2的路徑總長減少了約14.9%，但是能耗和碳的成本卻增加了約13.3%，類似的可以對比S4。走行距離減少了但油耗和碳成本卻增加的原因在于油耗和碳成本不僅與走行距離有關(guān)，還與載重量、行駛速度有關(guān)。

2)噸公里數(shù)更能反映油耗和碳成本。

S1的第5條子路徑(簡稱S15，下同)和S36采用同型車，裝載率、平均速度大致相同(18.96 m/s、18.68 m/s)的情況下，S36的旅行距離是S15的88/42=2.1倍，但是二氧化碳和油耗的成本卻是92.626 9/58.345 3=1.6倍，則偏差率ξ=|1.6-2.1|/1.6=31.3%，相差較大，所以用走行距離來衡量油耗和碳成本存在很大的偏差。本文引入噸公里數(shù)這個指標(biāo)，得到S36與S15的噸公里數(shù)相比為2 419/1 564=1.55，則偏差率ξ=1.6-1.55|/1.6=3.1%，更加接近油耗和碳成本的比值，這時的偏差可認(rèn)為是速度平方的差引起的。因此引入噸公里數(shù)這個指標(biāo)更能反映油耗和碳成本。

3)優(yōu)化運(yùn)輸組織，提高車輛的利用率。

注意到S13、S32、S43的司機(jī)工資所占總成本的比例非常高，分別為88.99%、90.8%、91.59%，而油耗和二氧化碳則僅僅為10%左右，其主要原因是車輛的裝載率較低，且同時服務(wù)的客戶數(shù)比較少，則從承運(yùn)人節(jié)省運(yùn)輸成本及優(yōu)化運(yùn)輸組織出發(fā)，可以提前制定運(yùn)輸計(jì)劃，如三天為一個時段集中配送，盡量減少單車單客運(yùn)輸或單車少客運(yùn)輸，提高車輛的利用率；同時，對于不可避免的單客戶，如果載重量允許，則盡量選擇小型車輛配送，因?yàn)檎{(diào)整與車型相關(guān)的參數(shù)βm和自重wm可減少成本。

4)車型的影響。

為了說明單車型和多車型的區(qū)別，本文采用最小總成本為目標(biāo)得到3種單一車型的對比結(jié)果，如表8所示。

表8 不同單一車型的結(jié)果對比Tab.8 Result comparison of different single type of vehicles

由表8可知：采用單一車型B時，得到802.883 5元的最低總成本。若從油耗和碳角度考慮，A型車的噸公里數(shù)比B少21.1%，比C少55.2%，以及車型的影響，導(dǎo)致A型車油耗和碳成本較B、C兩類車分別低5.3%和48.4%，因此應(yīng)選用載重量較小的A型車進(jìn)行配送，但此時的車輛使用數(shù)最多，總成本比B高6.2%。若從最短走行距離和最短旅行總時間(旅行總時間=司機(jī)工資/單位時間司機(jī)工資)考慮，C型車的走行距離分別比A、B兩類車少26.0%和8.1%，C型車的旅行總時間分別比A、B兩類車少10.0%和0.08%，因此應(yīng)選擇載重量大的C型車進(jìn)行運(yùn)輸，但此時的油耗和碳成本較高，總成本也比B高19.5%。綜上對A型車和C型車的分析，則很容易理解采用B型車時得到總成本最低，因?yàn)锽型車屬于中型車，同時繼承了A和C的優(yōu)勢，因此總成本是單一車型中最低的。另一方面，對比表7可知,采用單一車型的總成本普遍比采用混合車型的高，因此可以得出：運(yùn)輸企業(yè)采用混合車型進(jìn)行運(yùn)輸比采用單一車型運(yùn)輸更加節(jié)約成本。

5 結(jié)語

本文以VRPTW為基本模型，引入了基于載重、速度、距離的碳排放計(jì)算方法，建立了G-MVRPTW模型，然后設(shè)計(jì)了改進(jìn)的禁忌搜索算法。數(shù)值實(shí)驗(yàn)驗(yàn)證了所提模型和算法對于帶時間窗的城市綠色多車型車輛路徑安排的可行性和有效性，可以得出如下結(jié)論：

1)以模型的綜合成本最小為目標(biāo)與傳統(tǒng)的以走行距離、旅行時間為目標(biāo)得到的路徑安排有所不同，雖然以綜合成本最小為目標(biāo)將導(dǎo)致走行距離增加或者旅行總時間增加，但是不會增加運(yùn)輸企業(yè)的經(jīng)濟(jì)負(fù)擔(dān)，即此時的總成本仍然是最小的。

2)目前我國的碳價較低，當(dāng)前的碳交易機(jī)制不會顯著影響運(yùn)輸企業(yè)的車輛路徑安排，因此政府需要適當(dāng)調(diào)高碳價才能在運(yùn)輸行業(yè)有效地實(shí)現(xiàn)節(jié)能減排；在將來，新能源車投入運(yùn)輸市場將是新的趨勢。

3)噸公里數(shù)更能反映油耗和碳排放成本。

4)優(yōu)化運(yùn)輸組織，提高車輛的利用率。盡量減少單車單客運(yùn)輸或單車少客運(yùn)輸，或者是選用輕型車進(jìn)行單客戶配送。

5)運(yùn)輸企業(yè)采用混合車型進(jìn)行運(yùn)輸比采用單一車型運(yùn)輸更加節(jié)約成本。

本文只研究了閉合式車輛路徑問題，雖然文中也提到物流外包，但并沒有研究開放式車輛路徑問題(OVRP)，由于OVRP的車輛不需要返回配送中心；同時對于取貨的OVRP，車輛也不需要統(tǒng)一從配送中心出發(fā)，則可以減少更多的油耗和碳成本，也將更加節(jié)約運(yùn)輸時間，所以研究開放式綠色車輛路徑問題將是下一步研究的內(nèi)容。