多車型綠色車輛路徑問題優化模型

何東東，李引珍

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

0 引言

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

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

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

1 問題的描述

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

2 模型的建立

2.1 能源消耗和碳排放量計算

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

Fij≈Pt(Dij/vij)/q≈

(1)

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

Eij=ε×Fij

(2)

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

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

2.2 數學模型

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

(11)

ei≤ti≤li;?i∈V0

(12)

(13)

(14)

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

(15)

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

3 算法設計

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

3.1 初始解

根據客戶點時間窗的最遲開始服務時間li的大小，對客戶編號進行升序排序；如果最遲開始服務時間相同，則比較li-ei的大小，較小的排在前面，如得到客戶以1～9順序排列。對于車輛的分配，由于maxdi≤Qm，且研究表明：多用一輛車所帶來的固定費用總是超過其因總行駛距離縮短或速度優化等所帶來的節省，所以首先使用大容量的車進行裝載，當該車輛的聲譽裝載量無法滿足下一個客戶需求時，將此時的裝載容量∑di與次大型車的車容量Qm進行比較，如果∑di≤Qm，則換到次大型車，同時次大型車還可以繼續向下作類似比較；否則，采用原大容量車型；從而達到選取最適合車輛，使得裝載率最高，提高車輛使用率。當某種車型的車輛使用數超過車輛擁有數時，選取下一種車型，直到所選有客戶點被分配。根據上述方法，將客戶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 鄰域結構

解的質量和算法的搜索速度很大程度上依賴于鄰域結構的設計，本文根據編碼的特點設計了3種鄰域結構：

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

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

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

3.3 解的評價

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

(16)

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

3.4 禁忌表

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

4 數值實驗結果及分析

4.1 實驗設置

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

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

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

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

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

表5 不同車輛類型相關參數Tab.5 Relative parameters of different types of vehicles

4.2 模型的計算結果及分析

4.2.1 算法性能分析

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

圖1 不同算法收斂效果示意圖Fig.1 Schematic diagram of convergence effects for different algorithms表6 不同算法求解數值實驗統計結果Tab.6 Statistical results of different algorithms for solving numerical experiments

算法最優解平均解平均偏差/%最大偏差/%未得到最優解個數平均計算時間/s傳統禁忌搜索算法755.633784.8773.8719.99413.170改進的禁忌搜索算法755.633778.9323.0811.2728.122

4.2.2 結果分析

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

由表7可得：作為不同的運輸參與者可以選用不同的路徑方案。如：從政府節能減排的角度出發，則S2最小油耗和碳排放是政府的最佳選擇；對于承運人追求的就是總成本最小，則S4最小總費用是承運人的最佳選擇。如若涉及物流外包的情況，則對于物流提供方，S1最短走行距離或者S3 最短服務時間便是其最佳選擇，因為物流提供方希望租出去的車輛走行越短的距離并且用盡量短的時間完成運輸任務，這樣可以再為下一個有運輸需求的客戶服務，獲得更大的收益。

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

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

分析由表7各項指標得到的結果，得出以下結論：

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

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

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

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%，相差較大，所以用走行距離來衡量油耗和碳成本存在很大的偏差。本文引入噸公里數這個指標，得到S36與S15的噸公里數相比為2 419/1 564=1.55，則偏差率ξ=1.6-1.55|/1.6=3.1%，更加接近油耗和碳成本的比值，這時的偏差可認為是速度平方的差引起的。因此引入噸公里數這個指標更能反映油耗和碳成本。

3)優化運輸組織，提高車輛的利用率。

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

4)車型的影響。

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

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

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

5 結語

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

1)以模型的綜合成本最小為目標與傳統的以走行距離、旅行時間為目標得到的路徑安排有所不同，雖然以綜合成本最小為目標將導致走行距離增加或者旅行總時間增加，但是不會增加運輸企業的經濟負擔，即此時的總成本仍然是最小的。

2)目前我國的碳價較低，當前的碳交易機制不會顯著影響運輸企業的車輛路徑安排，因此政府需要適當調高碳價才能在運輸行業有效地實現節能減排；在將來，新能源車投入運輸市場將是新的趨勢。

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

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

5)運輸企業采用混合車型進行運輸比采用單一車型運輸更加節約成本。

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