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

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

2、ally only related to the travel distance，but in the actual situation，the fuel consumption caused by the loadis also an important factor leading to the increase of thetransportation cost of enterprises.Therefore，in the model ofsolving the vehicle routing problem，the objective functionconsiders the co

3、st changes caused by vehicle load and drivingdistance at the same time，which has more practical significance forenterprises to optimize the vehicle routing.This paper sorts out therelevant domestic and foreign research literature about the fuelconsumption caused by load and the influence of vehicle

4、drivingroute，summarizes the algorithms to solve such problems in recentyears，and finally puts forward the limitations of the problem andthe future research direction.【關键词】载重量;燃料消耗;货物权重;车辆路径优化【Keywords】load;fuel consumption;cargo weight;vehicle routingoptimization【中图分类号】F570.7【文献标志码】A【文章编号】1673-1069（

5、2020）03-0168-021 引言近年来，电子商务发展快速，根据中国电子商务研究中心的数据统计显示，截止到 2016 年我国在线电子商务网购规模己经超过 7 亿人次，使用人数的逐渐增多对末端物流配送效率和效益提出了更高的挑战。国家发改委发布的数据显示，2016 年度我国社会物流总费用为 11.1 万亿元，其中运输成本占据 6 万亿元，如何优化运输车辆的行驶路线对降低运输成本具有重要意义。同时有研究表明，在物流配送和运输环节所消耗的能源占到了整个物流环节 90%的能耗1，随着我国对能源消耗概念的提出，在考虑车辆行驶路线中考虑能耗问题更具有实际意义。车辆路径问题在 1959 年由 Dantzi

6、ng 和 Ramser2提出后，基于实际情况的考虑便衍生出带有不同约束条件的车辆路径模型，在众多的数学模型中都假设客户之间的运输费用与运输距离有关，目标函数旨在优化车辆的最小行驶距离。然而，从车辆本身消耗的燃料来看，车辆载重量的变化对于燃料的消耗存在差异，同样的运输距离在经典车辆路径问题中会产生同样的运输费用，但由于同样的距离运载量的不同，对燃料的消耗也会有明显的差异，运输成本不仅仅与运输距离有关更与运载量有关。2 带货物权重的车辆路径问题研究现状2.1 国外研究2007 年 Kara and Yetis 将车辆自身重量和车辆的载货量作为车辆行驶过程中能源消耗的一部分，提出了最小燃料消耗的车辆

7、路径问题（EMVRP），基于行驶距离和重量建立了如下的目标函数，其中 y 表示车辆在顾客之间的总重量：FMindy2008 年 Taveares、Zaigraiova 在废物收集和运输中同时考虑了行驶距离、路面坡度和车载量对燃料消耗的影响，结果表明在运输成本中考虑车载量会节约更多的燃料消耗，存在路线梯度因素时影响会更大。2012 年 xiao 和 zhao 等对行驶车辆的总重量引起燃料消耗的目标函数进行改进，得出如下的线性关系式，其中为车辆本身引起的燃料消耗：=+y=+ayi，j=1，r在提出车辆总重量对燃料消耗的影响之后，2012 年 Huang 等由于车辆载重量引起的燃料消耗与 CO2 气

8、体排放结合求解了同时取送货车辆路径问题的最小目标值，并建立了 CO2 气体排放与货物重量之间的关系：carbon emissions=（a10load+b）2015 年 Zachariadis 和 Tarantilis 为了区分与普通 VRP 的区别提出了车载量依赖型车辆路径问题并引入参数，其中=（Q/T），当值非常小时，车载量依赖型车辆路径问题近似于经典 VRP，运输成本决定于车辆自身重量和行驶距离，当值较大时，运输成本取决于车辆的载重和行驶距离，此时 VRP 问题便为车载量依赖型车辆路径问题。2.2 国内研究国内对于将载重量引入目标函数考虑对运输成本的影响起步较晚。2008 年唐加福等人对

9、散车运输进行了进一步的改进，考虑到车辆使用数量对于成本的影响，加上了车辆的租车费用提出了更为标准的目标函数：Min C=（adZ+bdu）+（dZ）2010 年唐加福等人将车辆的发车费用考虑在目标函数中，进一步得出如下的目标函：Min cos t=Dx（c+cy）+cx在已存在的文献中，考虑油耗影响的因素包括载重量、速度和路面坡度，Kuo假设在某一速度恒定下耗油量与载重量成正比，而从实际和文献中可以看出当考虑载重量和速度时，耗油量和载重量并不成正比，Franceschetti 在瞬时油耗的基础上推导出在两时间段下恒定速度下的油耗模型，但仅用 CPLEX 求解了较为小规模的问题。近几年，带货物权

10、重的问题被大家研究并结合在更多的实际问题中，如 2009 年朱才华等人将时间窗约束引入带货物权重的车辆路径中，并利用遗传算法进行求解。2010 年吴思、丁以中将货物权重和计重收费结合考虑，目标函数不仅包括固定费用还有由于运量引起的燃料消耗和路桥费用。2016 年张琳琳提出了带货物权重的软时间窗开放式车辆路径问题研究，并用遗传算法进行求解。3 算法3.1 精确算法2015 年 Zachariadis 和 Tarantilis 利用分支定价的方法求解了小规模的车载量依赖型车辆路径问题。2016 年 Ricardo Fukasawa 利用分支定价的方法求解了最小耗能的车辆路径问题，提出了两种新的混合

11、整数规划公式，基于循环消除的弧载重和附加约束的集划分公式，结果明显优于其他方法。3.2 启发式算法精确算法可以解决小规模的问题，但随着实际问题规模的增大，启发式算法相比于精确算法在求解难度和时间上更有优势。近几年，不断有研究者将启发式算法应用到求解带货物权重的车辆路径问题上。4 研究中存在的问题4.1 模型构建存在的局限性带货物权重的车辆路径问题的目标函数考虑运输成本的最小化，包括行驶距离、载重量等，虽然考虑因素符合实际需要但缺乏合理性，燃料的消耗不仅与车载量有关，还与车型、行驶速度、出发时间相关，目标函数的考虑无疑会导致燃料消耗的重复计算。对于行驶速度已有的文献都在考虑交通拥堵和不拥堵时间段

12、下对燃料消耗的影响，但在实际情况中，城市各个时间段的行驶速度都会有所不同。在现有的文献中很多都假设配送中心有相同车型的车辆，但在实际情况中，配送企业往往会有不同的车辆运输货物，并且这些车辆有不同的装载能力和运行速度。如何在充分考虑各因素的情况下建立正确的燃料消耗与载重函数对优化车辆出行具有更多实际意义。4.2 求解結果的实用性不强在研究过程中，学者们大多利用启发式算法对问题进行求解。虽然随着研究的深入，有学者对其算法进行改进，采用两阶段法、混合算法等，但问题本身存在的复杂性和局限性导致算法结果的收敛性和有效性不强，在一定程度上影响了运用到实际情况下的合理性和实用性。此外，由于影响燃料消耗的因素

13、众多，但目前很少有学者对不同的影响因素进行敏感度分析，进而对不同的因素包括车型、速度、出发时间和路面坡度对考虑载重量下的燃料消耗进行比较，从而更有效地贴合实际问题。5 结语在能源消耗的大背景下，在车辆路径问题中考虑能源消耗的最小化，一方面可以优化行车路线，降低企业的运输成本，一方面也符合国家对能源消耗的政策。因此，对于带货物权重一类问题的研究具有更多实际意义，但目前对于燃料消耗问题更多的关注于载重量的影响，但实际情况并非如此，燃料的消耗还与车型、速度等有关，未来的研究应从实际出发考虑。同时现有的研究大多只能用启发式算法进行大规模问题的求解，未来应该采用精确算法解决规模较大的问题。由于车辆路径问题具有多种不同的约束条件，可以将更多的约束条件考虑在带货物权重的车辆路径问题中，提出更多符合实际条件的问题模型，如多车型、多车程的带货物权重的车辆路径问题。【参考文献】【1】靳方平.基于低碳经济视角的车辆路径优化理论与方法研究D.长沙：中南大学，2013.【2】Dantzig G B，Ramser J H.The Truck DispatchingProblemJ.Management Science，1959，6（1）：80-91.