带货物权重车辆路径问题的研究现状

苏永梅

【摘  要】在经典车辆路径问题中运输成本往往只与行驶距离有关，但在实际情况中由于载重量引起的燃料消耗也是导致企业运输成本增加的重要因素。所以在解决车辆路径问题模型中，目标函数同时考虑车辆载重量和行驶距离导致的成本变化对于企业优化车辆行驶线路具有更多实际意义。论文整理了有关载重量引起燃料消耗进而影响车辆行驶路线的相关国内外研究文献，并总结近几年解决此类问题的算法，最后提出问题存在的局限性和未来的研究方向。

【Abstract】In the classical vehicle routing problem， the transportation cost is usually only related to the travel distance， but in the actual situation， the fuel consumption caused by the load is also an important factor leading to the increase of the transportation cost of enterprises. Therefore， in the model of solving the vehicle routing problem， the objective function considers the cost changes caused by vehicle load and driving distance at the same time， which has more practical significance for enterprises to optimize the vehicle routing. This paper sorts out the relevant domestic and foreign research literature about the fuel consumption caused by load and the influence of vehicle driving route， summarizes the algorithms to solve such problems in recent years， and finally puts forward the limitations of the problem and the future research direction.

【關键词】载重量;燃料消耗;货物权重;车辆路径优化

【Keywords】load; fuel consumption; cargo weight; vehicle routing optimization

【中图分类号】F570.7                               【文献标志码】A                                   【文章编号】1673-1069（2020）03-0168-02

1 引言

近年来，电子商务发展快速，根据中国电子商务研究中心的数据统计显示，截止到2016年我国在线电子商务网购规模己经超过7亿人次，使用人数的逐渐增多对末端物流配送效率和效益提出了更高的挑战。国家发改委发布的数据显示，2016年度我国社会物流总费用为11.1万亿元，其中运输成本占据6万亿元，如何优化运输车辆的行驶路线对降低运输成本具有重要意义。同时有研究表明，在物流配送和运输环节所消耗的能源占到了整个物流环节90%的能耗[1]，随着我国对能源消耗概念的提出，在考虑车辆行驶路线中考虑能耗问题更具有实际意义。车辆路径问题在1959年由Dantzing和Ramser[2]提出后，基于实际情况的考虑便衍生出带有不同约束条件的车辆路径模型，在众多的数学模型中都假设客户之间的运输费用与运输距离有关，目标函数旨在优化车辆的最小行驶距离。然而，从车辆本身消耗的燃料来看，车辆载重量的变化对于燃料的消耗存在差异，同样的运输距离在经典车辆路径问题中会产生同样的运输费用，但由于同样的距离运载量的不同，对燃料的消耗也会有明显的差异，运输成本不仅仅与运输距离有关更与运载量有关。

2 带货物权重的车辆路径问题研究现状

2.1 国外研究

2007年Kara and Yetis将车辆自身重量和车辆的载货量作为车辆行驶过程中能源消耗的一部分，提出了最小燃料消耗的车辆路径问题（EMVRP），基于行驶距离和重量建立了如下的目标函数，其中y表示车辆在顾客之间的总重量：

F∶Mindy

2008年Taveares、Zaigraiova在废物收集和运输中同时考虑了行驶距离、路面坡度和车载量对燃料消耗的影响，结果表明在运输成本中考虑车载量会节约更多的燃料消耗，存在路线梯度因素时影响会更大。2012年xiao和zhao等对行驶车辆的总重量引起燃料消耗的目标函数进行改进，得出如下的线性关系式，其中ρ为车辆本身引起的燃料消耗：

ρ=ρ+y=ρ+ay        i，j=1，…，r

在提出车辆总重量对燃料消耗的影响之后，2012年Huang等由于车辆载重量引起的燃料消耗与CO2气体排放结合求解了同时取送货车辆路径问题的最小目标值，并建立了CO2气体排放与货物重量之间的关系：

carbon emissions=μ×（a×10×load+b）

2015年Zachariadis 和Tarantilis为了区分与普通VRP的区别提出了车载量依赖型车辆路径问题并引入参数λ，其中λ=（Q/T），当λ值非常小时，车载量依赖型车辆路径问题近似于经典VRP，运输成本决定于车辆自身重量和行驶距离，当λ值较大时，运输成本取决于车辆的载重和行驶距离，此时VRP问题便为车载量依赖型车辆路径问题。

2.2 国内研究

国内对于将载重量引入目标函数考虑对运输成本的影响起步较晚。2008年唐加福等人对散车运输进行了进一步的改进，考虑到车辆使用数量对于成本的影响，加上了车辆的租车费用提出了更为标准的目标函数：

Min C=（adZ+bdu）+（dZ）

2010年唐加福等人将车辆的发车费用考虑在目标函数中，进一步得出如下的目标函：

Min cos t=Dx（c+cy）+cx

在已存在的文献中，考虑油耗影响的因素包括载重量、速度和路面坡度，Kuo假设在某一速度恒定下耗油量与载重量成正比，而从实际和文献中可以看出当考虑载重量和速度时，耗油量和载重量并不成正比，Franceschetti在瞬时油耗的基础上推导出在两时间段下恒定速度下的油耗模型，但仅用CPLEX求解了较为小规模的问题。近几年，带货物权重的问题被大家研究并结合在更多的实际问题中，如2009年朱才华等人将时间窗约束引入带货物权重的车辆路径中，并利用遗传算法进行求解。2010年吴思、丁以中将货物权重和计重收费结合考虑，目标函数不仅包括固定费用还有由于运量引起的燃料消耗和路桥费用。2016年张琳琳提出了带货物权重的软时间窗开放式车辆路径问题研究，并用遗传算法进行求解。

3 算法

3.1 精确算法

2015年Zachariadis和Tarantilis利用分支定价的方法求解了小规模的车载量依赖型车辆路径问题。2016年Ricardo Fukasawa利用分支定价的方法求解了最小耗能的车辆路径问题，提出了两种新的混合整数规划公式，基于循环消除的弧载重和附加约束的集划分公式，结果明显优于其他方法。

3.2 启发式算法

精确算法可以解决小规模的问题，但随着实际问题规模的增大，启发式算法相比于精确算法在求解难度和时间上更有优势。近几年，不断有研究者将启发式算法应用到求解带货物权重的车辆路径问题上。

4 研究中存在的问题

4.1 模型构建存在的局限性

带货物权重的车辆路径问题的目标函数考虑运输成本的最小化，包括行驶距离、载重量等，虽然考虑因素符合实际需要但缺乏合理性，燃料的消耗不仅与车载量有关，还与车型、行驶速度、出发时间相关，目标函数的考虑无疑会导致燃料消耗的重复计算。对于行驶速度已有的文献都在考虑交通拥堵和不拥堵时间段下对燃料消耗的影响，但在实际情况中，城市各个时间段的行驶速度都会有所不同。在现有的文献中很多都假设配送中心有相同车型的车辆，但在实际情况中，配送企业往往会有不同的车辆运输货物，并且这些车辆有不同的装载能力和运行速度。如何在充分考虑各因素的情况下建立正确的燃料消耗与载重函数对优化车辆出行具有更多实际意义。

4.2 求解結果的实用性不强

在研究过程中，学者们大多利用启发式算法对问题进行求解。虽然随着研究的深入，有学者对其算法进行改进，采用两阶段法、混合算法等，但问题本身存在的复杂性和局限性导致算法结果的收敛性和有效性不强，在一定程度上影响了运用到实际情况下的合理性和实用性。此外，由于影响燃料消耗的因素众多，但目前很少有学者对不同的影响因素进行敏感度分析，进而对不同的因素包括车型、速度、出发时间和路面坡度对考虑载重量下的燃料消耗进行比较，从而更有效地贴合实际问题。

5 结语

在能源消耗的大背景下，在车辆路径问题中考虑能源消耗的最小化，一方面可以优化行车路线，降低企业的运输成本，一方面也符合国家对能源消耗的政策。因此，对于带货物权重一类问题的研究具有更多实际意义，但目前对于燃料消耗问题更多的关注于载重量的影响，但实际情况并非如此，燃料的消耗还与车型、速度等有关，未来的研究应从实际出发考虑。同时现有的研究大多只能用启发式算法进行大规模问题的求解，未来应该采用精确算法解决规模较大的问题。由于车辆路径问题具有多种不同的约束条件，可以将更多的约束条件考虑在带货物权重的车辆路径问题中，提出更多符合实际条件的问题模型，如多车型、多车程的带货物权重的车辆路径问题。

【参考文献】

【1】靳方平.基于低碳经济视角的车辆路径优化理论与方法研究[D].长沙：中南大学，2013.

【2】Dantzig G B， Ramser J H. The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.