市区小范围多车辆低碳VRP：以珠海速递公司区域收件网络为例

马秋卓，王 健，宋海清



市区小范围多车辆低碳VRP：以珠海速递公司区域收件网络为例

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

（1．中山大学岭南学院，广东广州510275；2. 广东省邮政速递物流有限公司珠海市分公司，广东珠海519000）

考虑行驶过程中车载量的变化及其对油耗与碳排放量的影响，基于真实的企业数据探讨了市区小范围配送网络内的最优VRP决策。以最优化MIQP方法为主，辅以统计分析的手段，对比分析了最小碳排放量与最短距离目标下，有无汽车指派总数限制时的各类绩效并提出了一些决策上的建议。数值例子表明，大容量汽车更适用于以最小行驶距离为目标的最优化VRP问题。但是若要降低油耗成本，则应侧重使用多个小容量、高油耗效率的汽车。在混有大小不同容量汽车的优化策略当中，大车不仅对碳排放量的影响较大，对总行驶距离的影响也非常突出。具体的路径优化策略显示，两点的需求与其间距离的比值对最优汽车行驶路径的影响较大。与现有的企业策略相比，平均来讲我们的低碳规划方法无论在油耗量、运营成本、总行驶距离还是指派车数上均有明显的优势。

低碳；多车辆VRP；邮政区域收件网络

0 引言

我国物流市场近几年的高速发展使得人们逐渐重视商用汽车碳排放量对环境的影响。因为汽车排放的计算基于行驶过程中的油耗量，所以对于一个配送网络来说，能够降低排放量也意味着能够降低油耗量，同时节省运营成本。

实践证明，汽车的起步与停车所产生的油耗量相对较大。特别是当载重量增加时，这两个动作对油耗量的影响更加明显。然而，同等距离下，持续高速行驶的汽车由于惯性，油耗量要远小于频繁起步停车或慢速行驶时的汽车。因此，在市区小范围内的配送网络之中，由于每段运输路程距离较短，特别是在复杂路况下，汽车排放量，即油耗与载重量的关系十分明显。

基于上述情况，本文以一个真实企业为例，基于最小化碳排放量的目标探讨了市区小范围物流配送网络中不同车型的最优路径规划策略。同时，考虑到服务速率，我们对比分析了以最短行驶总距离为目标时的总排放量及相应的配送策略。

文章第一部分先对低碳VRP的相关研究进行了综述；第二部分对问题进行了描述并给出了相关的假设；接下来我们在第三部分针对所研究的问题构建了运筹优化模型，并在第四部分引入珠海速递公司的城市区域配送网络为实例，辅以统计手段进行了案例分析，同时我们还在建模方向对未来的研究做出了一些展望；第五部分总结了全文。

1 文献综述

先前的研究之中，Gendreau等人（1999）利用禁忌算法求解了异质车辆VRP问题[1]，之后章琦等（2007）使用蚁群算法求解了一个多目标多车辆VRP问题。同这类文章相似，早期的研究大多没有考虑环境绩效、碳排放及油耗等问题[2]；Kuo与Wang（2010）讨论了如何在路径优化中最小化油耗量[3]；文章考虑了行驶速度、距离以及载货量对排放量的影响。但现实情况下，由于城区街道路况复杂，严格控制车速十分困难；Neil Urquhart等人考虑行驶距离与车辆数量对碳排放整体绩效的影响，讨论了如何在加入碳排放约束的情况下优化距离与总车数[4]；Xiao Yiyong等（2011）考虑了汽车毛重对碳排放量的影响，利用模拟退火算法求解了带车容约束的多车辆VRP问题[5]；Shimizu（2012）利用扩展的Waber模型求解了一个仅有收货的多车辆VRP问题。作者考虑了成本与距离、载重量之间的关系[6]；上述研究中，Kuo与Wang、Neil Urquhart、Shimizu等人以及Waber均考虑的同质汽车，并没有顾及不同车型对油耗及排放量的影响；Kwon等人（2013）考虑了车型的差别，并将碳交易总成本与排放量结合成一个目标，利用禁忌算法进行求解。结论显示，可以在不损失很多成本的情况下降低较多的排放量[7]；Prins（2002）在考虑最优汽车指派数量的同时考虑了最小行驶距离的目标。同样地，作者采用禁忌算法求解了异质多车辆VRP问题[8]；Canhong Lin等人（2014）从绿色VRP、污染路径规划（PRP：Pollution VRP）及逆向物流三大类对绿色VRP（Green VRP）问题进行了全面的综述[9]；Bektas与Laporte（2011）在经典的VRP模型上加入了对行驶速度、装载量、距离及成本的考量，探讨了速度、时间及总成本之间的关系。研究发现PRP问题比VRP更难求解，不过能在降低成本方面表现更好[10]；相比本文，上述研究并没有细节地考虑汽车在不同节点间的行驶过程之中由于载重量的变化所带来的排放量的变化。

2 问题与假设

本文考虑一个市区内的小范围配送网络（例如某城市区域速递网络等），一个配送中心，多个节点，多台不同类型的汽车。为分析方便假定一轮配送之中汽车只收货（对送货情况的分析类似）。收货的例子如邮政收件、逆向物流运输等。

讨论碳排放应先从油耗入手。因为是小范围城市配送，故汽车行驶过程当中的油耗不仅与自身固有的基础油耗效率（BFCR-Basic Fuel Consumption Rate）有关，还与载重量相关（即变动油耗，或边际油耗VFCR Variable Fuel Consumption Rate）。因为不同的汽车自重与发动机功率各不相同，所以基础油耗随汽车的型号不同而不同；变动油耗效率指每增加一单位（如一公斤）货物时的汽车行驶一公里所多出来的边际油耗量。参考国际汽车论坛（http://www.automotiveforums.com）及Nam与Giannelli的技术报告[1]等相关资料发现，当汽车型号、行驶环境，即包括车速，路况等差别不大时VFCR相差很小，因此本文将其统一为一个常数。整个收货过程可由图1表示。考虑固定的碳排放因字EF（Emission Factor），可知某一车型每一段任务的总排放量可由下式表达：

图中不同的货车型号不同，运输过程中的运载量也不同，在各段路程上所产生的碳排放量也不同。如车型1已经收货完毕准备回配送中心，它的在途货运量相对较高，如果油耗因子与其它车辆相差不是很大的话，它的即刻排放量也理应较高。

图1 考虑收货的多车辆VRP路线简图

基于上述问题背景，我们采用真实的公司数据探讨了最低碳排放路径规划策略及相应的运营绩效，并对比了最小行驶距离策略下的总排放量。另外。我们还分析了不同指派车辆总数、不同车辆类型时的不同规划绩效。

3 模型

3.1 参数与变量

本文所用到的变量与参数如下：

3.2 目标函数

最小化行驶距离的目标函数为：

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

其中，约束(1)、(2)表明除了配送中心，每个节点有且仅有一台汽车到达或离开；(3)表明第个汽车并不一定要从配送中心出去，它可以在当期被闲置，本文不考虑闲置成本。相应的，结合约束(2)，约束(3)与(4)使得进出配送中心的汽车数量与车型一致；等式(5)为流平衡约束；(6)为限制子回路约束。

相应的，最小化排放成本的目标函数如下：

(1)(7)

4 案例分析

4.1 数据输入

珠海速递公司香洲区物流配送网络如图2所示。其中A点表示配送中心，B至K表示各个收集点。各点之间的距离矩阵如表1所示，计算时设为一较大的值M。常用汽车类型及各项参数如表2所示。其中，该区域网络中配备厢式卡车3辆（编号0至2）、轻型卡车2辆（编号3至4）。5辆车在实际操作中全部投入运营并以最小行驶距离为优化目标。我们先依据约束(3)与(4)的设定，灵活安排出车总数，然后再与指派总车数受到限制时的优化结果进行对比。汽车油耗价格采用公司（至2014年2月）统一进购价7.96元每升。

计算上，我们采用商业优化工具IBM CPLEX12.5求解。所用平台为32位内存4GB个人计算机，编译平台与编程语言分别采用VS2008与C++。

图2 珠海速递公司香洲区网络配送运营总图

表1 珠海速递公司香洲区物流配送网络点对点距离图

表2 珠海速递公司香洲配送区常用汽车及技术参数

数据来源：Natural Resource Canada, Fuel Consumption Guide 2010, ecoENERGY.

表3 8日平均收件量

图2 各节点8月份需求分布

取该网络2013年8月各点数据，得均值如表3所示，各点需求分布如图2所示。由于国有企业工作与节假日的周期性，需求数据亦呈现出明显的周期性。8月底因为是我国的中秋节前后，所以出现需求暴增的现象，货品中以月饼及节日礼品为主。期间，E点的货物量超过了负责此区域网络所有车型的额定载荷，需要拆分订单或超载运输。本文仅对第二种方式进行讨论。

4.2 优化仿真结果

即使每期的需求数据各不相同，但当网络规模较小时，我们完全可以采用逐期优化，逐期实施的策略。例如8月份我们基于最小排放目标需进行31次优化，每次优化过后实施实际的指派与调度。由于收件活动发生在各节点需求量已知之后，所以我们面对的是确定型最优化问题。同样的，对于最短距离目标，我们仍需进行逐期求解，因需求变动及汽车容量限制，每次的行驶路径都可能不尽相同。

每期以最小排放量为目标时的排放量及距离如图3所示；每期以最小距离为目标时的距离及排放如图4所示。

结果表明，当我们以距离最小化为目标时，除了有超载现象发生，排放量均比以排放最小化为目标的每期排放量要高。对应的，当我们以排放最小化为目标时，总行驶距离总大于以距离最小为目标时的策略。但是，最小总行驶距离并不意味着最短收件时间。因为整个收件任务的完成时间应以车队中最慢完成自身任务的汽车为准。例如8月25日，若以最小距离为目标，总路程虽然只有27.1，但全部由5号汽车完成，显然时间上相对多车行驶时的时间要长。至此，决策者可以很快地从各个策略中权衡配送效率、排放以及成本等指标，选择一类另企业各既得利益者都满意的方法。

图3 两种优化下的排放表现

图4 两种优化方法下的距离表现

两类目标下的出车数量及运营成本如图5与图6所示。可以看到，最短距离目标下的出车总数一般要小于最小排放时的出车总数。而且还发现，当出车总数不高时，成本不一定低。我们采用线性回归对两类方法下的出车数量与成本进行分析发现均有较高的显著程度。

图5 出车数量

图6 运营成本

考虑到公司的实际运作情况，每期规定5辆车全部出勤，修改约束(3)和(4)得：

(3)’ (4)’

对比分析此类情况下两类策略得结果图7与图8；与图3与图4对应的指标相比得图9与图10。

图7 全勤汽车两类方法下的排放量

图8全勤汽车两类方法下的距离

图10 全勤或非全勤汽车数量下的最小距离

图7表明5辆汽车全勤时，用最小距离为目标，排放量每一期都大于最小排放量为目标时的情况。但是，全勤汽车使得不同情况下的最小总行驶距离比较稳定，除了超载的一期，其它时间均保持在53.2公里。图9表明，除了出现超载的情况，汽车全勤时的排放量一般比非全勤时的最优策略要高；距离方面全勤汽车的总行驶距离总要高于非全勤时的解。

表4显示了没有全勤限制时最小排放与最小距离两种方法下大、小型汽车的使用频率。结果表明，若只要求总距离较小，企业应更多地采用大容量货车而非小型厢式货。但凡事皆有利弊，小车的油耗量相对较低，多台小汽车组合起来能达到节能减排的作用。然而因为最小排放下的使用总车次比较高，因而人力成本可能也更高。

表4 最小排放与最短距离目标下各车型使用情意

表5中分别报告了31期中全勤与非全勤时最小排放及最短距离时的4类路径策略。其中，因为有多个最短路径的出现，我们仅列出最低与最高排放量的策略。

表5 不同目标值下的路径规划策略

注：最后一行碳排放量比第三行大很多是因为全勤约束下各期距离一致，5773.96相当于全部数据点中最高的一个。

具体的路径及车辆指派结果显示，非全勤最小排放目标下小车为主要运营工具，最短距离目标下大车为主要运营工具。全勤最小排放目标下，小车被指派的次数多于大车，自然地，其行驶总路径也较长；若在最小距离情况下选择最小排放，小车使用量仍然高于大车；对应的，若以最小距离为目标，放松对排放的管制，大车使用量很有可能高于小车。另外，从所有路径中可以看出J、K之间是一条必经之路，这不仅是由于两地间的距离短，还因为两地需求水平较高，汽车往来运输具有较高的运载效率，即两地需求与路程的比值较大。虽然I、J、K几地需求也高，但因为A点至他们之间的距离太远，运营时并不经济。

4.3 对比实际策略

实践之中，企业最关注的是行驶总路径。为此，我们对比分析了我们所提模型与受全勤约束的最小距离模型下8月份的平均绩效水平，其中包括排放量、运营行驶成本、行驶总距离以及所用汽车数量。结果如表6所示。不难发现，我们虽然以碳排放为目标，但由于放松了指派车数的限制，结果明显好于企业的现行策略。

表6 与现行规划方法的比较结果

4.4 统计分析

考虑到对最优解的结构进行分析比较复杂性，我们利用统计分析探知31期优化结果之中各车辆对总排放与总距离的影响。建立下述回归方程：

表7 最低排放下各汽车对排放量的影响

表8 最小距离下各汽车对总行驶距离的影响

另外我们用Logistic回归方法分析了最优决策下各点需求变动对汽车使用决策的影响。统计上说，仅有B、G与I点对是否使用厢式卡车0有显著的影响。结果如表9所示。其中当B点与G点的需求量与是否采用小型货车有反向影响，而当I点需求上升时，对0号车的需求概率将上升。查看原始数据发现B与G的需求水平相对较高，而I需求量较少。

4.5 研究扩展

在后续研究中，若想从上述两个目标中取得某种均衡，可以通过线性加权平均优化方，将(P1)与(P2)结合成一个目标函数。目标函数如下：

表9 需求对车辆使用情况的Logit影响

(1)(7)

(1)(7)

规模较大的二次0-1规划会对计算时间提出较大的挑战，针对VRP的二次规划算法可能成为未来的研究对象。

5 结论

基于小范围市区配送网络，我们在路径优化的过程中考虑了汽车装载量对油耗与排放的影响，通过对真实的个案数据进行分析得知，排放与距离两个目标是不可兼得的。我们得到的一些决策上的建议包括：在以最低排放为目标的情况下，若想最小距离处于一个稳定水平，可以在保证总车容能覆盖到所有需求的前提下固定一个汽车指派总数。但这样的代价是将产生较高的排放值。因为若不能灵活调整车量数，当需求较小时，车辆利用率会较低，多出来的排放量较多地来自空载汽车自有重量所产生的油耗；若以最小距离为目标，全勤出车并非最好的选择，因为较多的在勤车辆与较长的行驶总距离可能增加人力开销或维护费用等其它成本；行车路线方面，两点需求量及之间弧长的距离之比是个比较关键的影响因素，因为它直接决定着两点之间的货物装卸与运输效率。另外通过统计分析可以看出，大车对最优策略下的排放量或距离均有较大的影响。此外，我们还针对多目标低碳VRP问题提出了一些可行的目标函数，对未来研究进行了最优化方法上的展望。

[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）；中央高校基本科研业务费专项资金资助项目

马秋卓（1984—），男，湖南长沙市人；中山大学岭南学院博士研究生，研究方向：供应链管理、低碳交通运输、多目标优化。