馬秋卓，王 健，宋海清

?

市區(qū)小范圍多車輛低碳VRP：以珠海速遞公司區(qū)域收件網絡為例

馬秋卓1，王 健2，宋海清1

（1．中山大學嶺南學院，廣東廣州510275；2. 廣東省郵政速遞物流有限公司珠海市分公司，廣東珠海519000）

考慮行駛過程中車載量的變化及其對油耗與碳排放量的影響，基于真實的企業(yè)數據探討了市區(qū)小范圍配送網絡內的最優(yōu)VRP決策。以最優(yōu)化MIQP方法為主，輔以統(tǒng)計分析的手段，對比分析了最小碳排放量與最短距離目標下，有無汽車指派總數限制時的各類績效并提出了一些決策上的建議。數值例子表明，大容量汽車更適用于以最小行駛距離為目標的最優(yōu)化VRP問題。但是若要降低油耗成本，則應側重使用多個小容量、高油耗效率的汽車。在混有大小不同容量汽車的優(yōu)化策略當中，大車不僅對碳排放量的影響較大，對總行駛距離的影響也非常突出。具體的路徑優(yōu)化策略顯示，兩點的需求與其間距離的比值對最優(yōu)汽車行駛路徑的影響較大。與現有的企業(yè)策略相比，平均來講我們的低碳規(guī)劃方法無論在油耗量、運營成本、總行駛距離還是指派車數上均有明顯的優(yōu)勢。

低碳；多車輛VRP；郵政區(qū)域收件網絡

0 引言

我國物流市場近幾年的高速發(fā)展使得人們逐漸重視商用汽車碳排放量對環(huán)境的影響。因為汽車排放的計算基于行駛過程中的油耗量，所以對于一個配送網絡來說，能夠降低排放量也意味著能夠降低油耗量，同時節(jié)省運營成本。

實踐證明，汽車的起步與停車所產生的油耗量相對較大。特別是當載重量增加時，這兩個動作對油耗量的影響更加明顯。然而，同等距離下，持續(xù)高速行駛的汽車由于慣性，油耗量要遠小于頻繁起步停車或慢速行駛時的汽車。因此，在市區(qū)小范圍內的配送網絡之中，由于每段運輸路程距離較短，特別是在復雜路況下，汽車排放量，即油耗與載重量的關系十分明顯。

基于上述情況，本文以一個真實企業(yè)為例，基于最小化碳排放量的目標探討了市區(qū)小范圍物流配送網絡中不同車型的最優(yōu)路徑規(guī)劃策略。同時，考慮到服務速率，我們對比分析了以最短行駛總距離為目標時的總排放量及相應的配送策略。

文章第一部分先對低碳VRP的相關研究進行了綜述；第二部分對問題進行了描述并給出了相關的假設；接下來我們在第三部分針對所研究的問題構建了運籌優(yōu)化模型，并在第四部分引入珠海速遞公司的城市區(qū)域配送網絡為實例，輔以統(tǒng)計手段進行了案例分析，同時我們還在建模方向對未來的研究做出了一些展望；第五部分總結了全文。

1 文獻綜述

先前的研究之中，Gendreau等人（1999）利用禁忌算法求解了異質車輛VRP問題[1]，之后章琦等（2007）使用蟻群算法求解了一個多目標多車輛VRP問題。同這類文章相似，早期的研究大多沒有考慮環(huán)境績效、碳排放及油耗等問題[2]；Kuo與Wang（2010）討論了如何在路徑優(yōu)化中最小化油耗量[3]；文章考慮了行駛速度、距離以及載貨量對排放量的影響。但現實情況下，由于城區(qū)街道路況復雜，嚴格控制車速十分困難；Neil Urquhart等人考慮行駛距離與車輛數量對碳排放整體績效的影響，討論了如何在加入碳排放約束的情況下優(yōu)化距離與總車數[4]；Xiao Yiyong等（2011）考慮了汽車毛重對碳排放量的影響，利用模擬退火算法求解了帶車容約束的多車輛VRP問題[5]；Shimizu（2012）利用擴展的Waber模型求解了一個僅有收貨的多車輛VRP問題。作者考慮了成本與距離、載重量之間的關系[6]；上述研究中，Kuo與Wang、Neil Urquhart、Shimizu等人以及Waber均考慮的同質汽車，并沒有顧及不同車型對油耗及排放量的影響；Kwon等人（2013）考慮了車型的差別，并將碳交易總成本與排放量結合成一個目標，利用禁忌算法進行求解。結論顯示，可以在不損失很多成本的情況下降低較多的排放量[7]；Prins（2002）在考慮最優(yōu)汽車指派數量的同時考慮了最小行駛距離的目標。同樣地，作者采用禁忌算法求解了異質多車輛VRP問題[8]；Canhong Lin等人（2014）從綠色VRP、污染路徑規(guī)劃（PRP：Pollution VRP）及逆向物流三大類對綠色VRP（Green VRP）問題進行了全面的綜述[9]；Bektas與Laporte（2011）在經典的VRP模型上加入了對行駛速度、裝載量、距離及成本的考量，探討了速度、時間及總成本之間的關系。研究發(fā)現PRP問題比VRP更難求解，不過能在降低成本方面表現更好[10]；相比本文，上述研究并沒有細節(jié)地考慮汽車在不同節(jié)點間的行駛過程之中由于載重量的變化所帶來的排放量的變化。

2 問題與假設

本文考慮一個市區(qū)內的小范圍配送網絡（例如某城市區(qū)域速遞網絡等），一個配送中心，多個節(jié)點，多臺不同類型的汽車。為分析方便假定一輪配送之中汽車只收貨（對送貨情況的分析類似）。收貨的例子如郵政收件、逆向物流運輸等。

討論碳排放應先從油耗入手。因為是小范圍城市配送，故汽車行駛過程當中的油耗不僅與自身固有的基礎油耗效率（BFCR-Basic Fuel Consumption Rate）有關，還與載重量相關（即變動油耗，或邊際油耗VFCR Variable Fuel Consumption Rate）。因為不同的汽車自重與發(fā)動機功率各不相同，所以基礎油耗隨汽車的型號不同而不同；變動油耗效率指每增加一單位（如一公斤）貨物時的汽車行駛一公里所多出來的邊際油耗量。參考國際汽車論壇（http://www.automotiveforums.com）及Nam與Giannelli的技術報告[1]等相關資料發(fā)現，當汽車型號、行駛環(huán)境，即包括車速，路況等差別不大時VFCR相差很小，因此本文將其統(tǒng)一為一個常數。整個收貨過程可由圖1表示。考慮固定的碳排放因字EF（Emission Factor），可知某一車型每一段任務的總排放量可由下式表達：

圖中不同的貨車型號不同，運輸過程中的運載量也不同，在各段路程上所產生的碳排放量也不同。如車型1已經收貨完畢準備回配送中心，它的在途貨運量相對較高，如果油耗因子與其它車輛相差不是很大的話，它的即刻排放量也理應較高。

圖1 考慮收貨的多車輛VRP路線簡圖

基于上述問題背景，我們采用真實的公司數據探討了最低碳排放路徑規(guī)劃策略及相應的運營績效，并對比了最小行駛距離策略下的總排放量。另外。我們還分析了不同指派車輛總數、不同車輛類型時的不同規(guī)劃績效。

3 模型

3.1 參數與變量

本文所用到的變量與參數如下：

3.2 目標函數

最小化行駛距離的目標函數為：

(1) (2) (3) (4) (5) (6) (7)

其中，約束(1)、(2)表明除了配送中心，每個節(jié)點有且僅有一臺汽車到達或離開；(3)表明第個汽車并不一定要從配送中心出去，它可以在當期被閑置，本文不考慮閑置成本。相應的，結合約束(2)，約束(3)與(4)使得進出配送中心的汽車數量與車型一致；等式(5)為流平衡約束；(6)為限制子回路約束。

相應的，最小化排放成本的目標函數如下：

(1)(7)

4 案例分析

4.1 數據輸入

珠海速遞公司香洲區(qū)物流配送網絡如圖2所示。其中A點表示配送中心，B至K表示各個收集點。各點之間的距離矩陣如表1所示，計算時設為一較大的值M。常用汽車類型及各項參數如表2所示。其中，該區(qū)域網絡中配備廂式卡車3輛（編號0至2）、輕型卡車2輛（編號3至4）。5輛車在實際操作中全部投入運營并以最小行駛距離為優(yōu)化目標。我們先依據約束(3)與(4)的設定，靈活安排出車總數，然后再與指派總車數受到限制時的優(yōu)化結果進行對比。汽車油耗價格采用公司（至2014年2月）統(tǒng)一進購價7.96元每升。

計算上，我們采用商業(yè)優(yōu)化工具IBM CPLEX12.5求解。所用平臺為32位內存4GB個人計算機，編譯平臺與編程語言分別采用VS2008與C++。

圖2 珠海速遞公司香洲區(qū)網絡配送運營總圖

表1 珠海速遞公司香洲區(qū)物流配送網絡點對點距離圖

表2 珠海速遞公司香洲配送區(qū)常用汽車及技術參數

數據來源：Natural Resource Canada, Fuel Consumption Guide 2010, ecoENERGY.

表3 8日平均收件量

圖2 各節(jié)點8月份需求分布

取該網絡2013年8月各點數據，得均值如表3所示，各點需求分布如圖2所示。由于國有企業(yè)工作與節(jié)假日的周期性，需求數據亦呈現出明顯的周期性。8月底因為是我國的中秋節(jié)前后，所以出現需求暴增的現象，貨品中以月餅及節(jié)日禮品為主。期間，E點的貨物量超過了負責此區(qū)域網絡所有車型的額定載荷，需要拆分訂單或超載運輸。本文僅對第二種方式進行討論。

4.2 優(yōu)化仿真結果

即使每期的需求數據各不相同，但當網絡規(guī)模較小時，我們完全可以采用逐期優(yōu)化，逐期實施的策略。例如8月份我們基于最小排放目標需進行31次優(yōu)化，每次優(yōu)化過后實施實際的指派與調度。由于收件活動發(fā)生在各節(jié)點需求量已知之后，所以我們面對的是確定型最優(yōu)化問題。同樣的，對于最短距離目標，我們仍需進行逐期求解，因需求變動及汽車容量限制，每次的行駛路徑都可能不盡相同。

每期以最小排放量為目標時的排放量及距離如圖3所示；每期以最小距離為目標時的距離及排放如圖4所示。

結果表明，當我們以距離最小化為目標時，除了有超載現象發(fā)生，排放量均比以排放最小化為目標的每期排放量要高。對應的，當我們以排放最小化為目標時，總行駛距離總大于以距離最小為目標時的策略。但是，最小總行駛距離并不意味著最短收件時間。因為整個收件任務的完成時間應以車隊中最慢完成自身任務的汽車為準。例如8月25日，若以最小距離為目標，總路程雖然只有27.1，但全部由5號汽車完成，顯然時間上相對多車行駛時的時間要長。至此，決策者可以很快地從各個策略中權衡配送效率、排放以及成本等指標，選擇一類另企業(yè)各既得利益者都滿意的方法。

圖3 兩種優(yōu)化下的排放表現

圖4 兩種優(yōu)化方法下的距離表現

兩類目標下的出車數量及運營成本如圖5與圖6所示?？梢钥吹剑疃叹嚯x目標下的出車總數一般要小于最小排放時的出車總數。而且還發(fā)現，當出車總數不高時，成本不一定低。我們采用線性回歸對兩類方法下的出車數量與成本進行分析發(fā)現均有較高的顯著程度。

圖5 出車數量

圖6 運營成本

考慮到公司的實際運作情況，每期規(guī)定5輛車全部出勤，修改約束(3)和(4)得：

(3)’ (4)’

對比分析此類情況下兩類策略得結果圖7與圖8；與圖3與圖4對應的指標相比得圖9與圖10。

圖7 全勤汽車兩類方法下的排放量

圖8全勤汽車兩類方法下的距離

圖10 全勤或非全勤汽車數量下的最小距離

圖7表明5輛汽車全勤時，用最小距離為目標，排放量每一期都大于最小排放量為目標時的情況。但是，全勤汽車使得不同情況下的最小總行駛距離比較穩(wěn)定，除了超載的一期，其它時間均保持在53.2公里。圖9表明，除了出現超載的情況，汽車全勤時的排放量一般比非全勤時的最優(yōu)策略要高；距離方面全勤汽車的總行駛距離總要高于非全勤時的解。

表4顯示了沒有全勤限制時最小排放與最小距離兩種方法下大、小型汽車的使用頻率。結果表明，若只要求總距離較小，企業(yè)應更多地采用大容量貨車而非小型廂式貨。但凡事皆有利弊，小車的油耗量相對較低，多臺小汽車組合起來能達到節(jié)能減排的作用。然而因為最小排放下的使用總車次比較高，因而人力成本可能也更高。

表4 最小排放與最短距離目標下各車型使用情意

表5中分別報告了31期中全勤與非全勤時最小排放及最短距離時的4類路徑策略。其中，因為有多個最短路徑的出現，我們僅列出最低與最高排放量的策略。

表5 不同目標值下的路徑規(guī)劃策略

注：最后一行碳排放量比第三行大很多是因為全勤約束下各期距離一致，5773.96相當于全部數據點中最高的一個。

具體的路徑及車輛指派結果顯示，非全勤最小排放目標下小車為主要運營工具，最短距離目標下大車為主要運營工具。全勤最小排放目標下，小車被指派的次數多于大車，自然地，其行駛總路徑也較長；若在最小距離情況下選擇最小排放，小車使用量仍然高于大車；對應的，若以最小距離為目標，放松對排放的管制，大車使用量很有可能高于小車。另外，從所有路徑中可以看出J、K之間是一條必經之路，這不僅是由于兩地間的距離短，還因為兩地需求水平較高，汽車往來運輸具有較高的運載效率，即兩地需求與路程的比值較大。雖然I、J、K幾地需求也高，但因為A點至他們之間的距離太遠，運營時并不經濟。

4.3 對比實際策略

實踐之中，企業(yè)最關注的是行駛總路徑。為此，我們對比分析了我們所提模型與受全勤約束的最小距離模型下8月份的平均績效水平，其中包括排放量、運營行駛成本、行駛總距離以及所用汽車數量。結果如表6所示。不難發(fā)現，我們雖然以碳排放為目標，但由于放松了指派車數的限制，結果明顯好于企業(yè)的現行策略。

表6 與現行規(guī)劃方法的比較結果

4.4 統(tǒng)計分析

考慮到對最優(yōu)解的結構進行分析比較復雜性，我們利用統(tǒng)計分析探知31期優(yōu)化結果之中各車輛對總排放與總距離的影響。建立下述回歸方程：

表7 最低排放下各汽車對排放量的影響

表8 最小距離下各汽車對總行駛距離的影響

另外我們用Logistic回歸方法分析了最優(yōu)決策下各點需求變動對汽車使用決策的影響。統(tǒng)計上說，僅有B、G與I點對是否使用廂式卡車0有顯著的影響。結果如表9所示。其中當B點與G點的需求量與是否采用小型貨車有反向影響，而當I點需求上升時，對0號車的需求概率將上升。查看原始數據發(fā)現B與G的需求水平相對較高，而I需求量較少。

4.5 研究擴展

在后續(xù)研究中，若想從上述兩個目標中取得某種均衡，可以通過線性加權平均優(yōu)化方，將(P1)與(P2)結合成一個目標函數。目標函數如下：

表9 需求對車輛使用情況的Logit影響

(1)(7)

(1)(7)

規(guī)模較大的二次0-1規(guī)劃會對計算時間提出較大的挑戰(zhàn)，針對VRP的二次規(guī)劃算法可能成為未來的研究對象。

5 結論

基于小范圍市區(qū)配送網絡，我們在路徑優(yōu)化的過程中考慮了汽車裝載量對油耗與排放的影響，通過對真實的個案數據進行分析得知，排放與距離兩個目標是不可兼得的。我們得到的一些決策上的建議包括：在以最低排放為目標的情況下，若想最小距離處于一個穩(wěn)定水平，可以在保證總車容能覆蓋到所有需求的前提下固定一個汽車指派總數。但這樣的代價是將產生較高的排放值。因為若不能靈活調整車量數，當需求較小時，車輛利用率會較低，多出來的排放量較多地來自空載汽車自有重量所產生的油耗；若以最小距離為目標，全勤出車并非最好的選擇，因為較多的在勤車輛與較長的行駛總距離可能增加人力開銷或維護費用等其它成本；行車路線方面，兩點需求量及之間弧長的距離之比是個比較關鍵的影響因素，因為它直接決定著兩點之間的貨物裝卸與運輸效率。另外通過統(tǒng)計分析可以看出，大車對最優(yōu)策略下的排放量或距離均有較大的影響。此外，我們還針對多目標低碳VRP問題提出了一些可行的目標函數，對未來研究進行了最優(yōu)化方法上的展望。

[1] Edward K. Nam, Robert Giannelli. Fuel Consumption Modeling of Conventional and Advanced Technology Vehicles in the Physical Emission Rate Estimator (PERE) [R]. U.S. Environmental Protection Agency, 2005.

[2] 章琦，龐小紅, 吳智銘. 約束法蟻群算法在多目標V R P 中的研究. 計算機仿真，2007(3)：263-265.

[3] Michel Gendreau, Gilbert Laporte, Christophe Musaraganyi, Eric D. Taillard. A tabu search heuristic for the heterogeneous fleet vehicle routing problem [J]. Computers & Operations Research 1999(26): 1153-1173.

[4] Yiyo Kuo and Chi-Chang Wang. Optimizing the VRP by minimizing fuel consumption [J]. Management of Environmental Quality: An International Journal, 2011(22): 440-450.

[5] Neil Urquhart, Catherine Scot, Emma Hart. Incorporating emissions models within a multi-objective vehicle routing problem [C]. Proceeding of the fifteenth annual conference companion on Genetic and evolutionary computation conference companion: 2013: 193-194.

[6] Yiyong Xiao, QiuhongZhao, IkouKaku, YuchunXu. Development of a fuel consumption optimization model for the capacitated vehicle routing problem [J]. Computers & Operations Research 2012(39): 1419-1431.

[7] Yoshiaki Shimizu. Generalized Vehicle Routing Problem for Reverse Logistics Aiming at Low Carbon Transportation. Proceedings of the Asia Pacific Industrial Engineering & Management Systems Conference 2012 [C]. pp: 1416-1425.

[8] Yong-Ju Kwon a, Young-Jae Choi a, Dong-Ho Lee. Heterogeneous fixed fleet vehicle routing considering carbon emission [J]. Transportation Research Part D, 2013(23): 81-89.

[9] Christian Prins. Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case [J]. Journal of Mathematical Modelling and Algorithms, 2002(1): 135-150.

[10] Canhong Lin, K.L. Choy, G.T.S. Ho, S.H. Chung, H.Y. Lam. Survey of Green Vehicle Routing Problem: Past and future trends [J]. Expert Systems with Applications 2014(41):1118-1138.

[11] Tolga Bektas, Gilbert Laporte. The Pollution-Routing Problem [J]. Transportation Research Part B, 2011(45): 1232-1250.

Small-Scaled Low Carbon Multi-Vehicle Routing Problem in Urban Area: An ExampleFrom the Regional Picking-Up Network of Zhuhai Express Company

MA Qiu-zhuo1, WANG Jian2, SONG Hai-qing1

(1. Lingnan College, Sun Yat-sen University, Guangzhou 510275, China; 2. Post Express Logistics Ltd. of Guangdong Province, Zhuhai Branch, Zhuhai 519000,China)

The rapid growth of the logistics industry has increased people’s concerns about air quality and vehicle emission. Vehicle’s emission is directly calculated from fuel consumption. It is important to understand the optimized method of operational research for saving fuel cost and reducing carbon emission.

In a small-ranged urban distribution network, vehicle’s fuel consumption is also very sensitive to the loaded weights associating with travelling distance in addition to distance. Therefore, an appropriate vehicle routing strategy becomes critical when considering weights variation during the pick-up and delivery process. Besides, we are also interested in the question about environmental performance when we have concerns about other objectives such as travelling distance.

By focusing on the pick-up service, this research constructs a multiple heterogeneous vehicle routing model considering the accumulation of on-road goods weight and its influence on fuel consumption and emission. A real case from a regional postal network of Zhuhai express company is introduced in which we solve a MIP VRP with 10 branch points, and 1 distribution center with 5 on-duty vehicles of two types.

In the first part, we propose the problem while providing some assumptions. In addition, the calculation method of emission is explicitly described in which the way of recording basic and variable fuel consumption rates for each vehicle type is introduced.

In the second part, we describe the MIP model under the objective of emission minimization and distance minimization.

In the third part, a real case study is implemented on the data support from Zhuhai express company. A total of 11 points are contained in its pick-up postal network. One is distribution center and the others are all branch stations.

We use a numerical experiment to compare the performances of emission and distance with the objectives of minimizing emission and total travelling distance. In addition, we compare these items under the constraint of 5 or no more than 5 vehicles. The result under not-all-duty constraint shows the superiority in emission under the objective of emission minimization. The strategy with more vehicles of smaller capacity but higher fuel efficiency creates lower emission but higher distance. However, fewer vehicles do not mean less operational cost because large vehicle has large fuel consumption. All-duty’s emission is higher than not-all-duty strategy, but the distance of the latter is more stable than the former’s. The details of the routing strategies suggest the frequent usage of vehicles on the short arc with large demand from both nodes. Besides, our statistical test results show that the large vehicle has more significant impact on both emission and distance, and only a few points within the network affect vehicle assignment strategy.

In summary, a small-ranged VRP network is preferred to the strategy patterns of combining higher-fuel-efficiency but lower-capacity vehicles. This routing method is more flexible in loading efficiency and thus more economical in fuel consumption. Fewer vehicles with large capacity but low fuel efficiency are favorable in distance minimization, but have higher operational cost. Moreover, as we compare different performance indicators, including emission, operation cost on road, total travelling distance and assigned vehicle number, our approach is better than the real strategy.

low carbon; multi-vehicle VRP; postal regional picking-up network

中文編輯：杜 ??；英文編輯：Charlie C. Chen

F273

A

1004-6062(2016)04-0153-07

10.13587/j.cnki.jieem.2016.04.019

2013-12-19

2014-04-27

國家自然科學基金資助項目（71171205）；中央高?；究蒲袠I(yè)務費專項資金資助項目

馬秋卓（1984—），男，湖南長沙市人；中山大學嶺南學院博士研究生，研究方向：供應鏈管理、低碳交通運輸、多目標優(yōu)化。