基于物流配送的车辆路径优化问题综述

王雪凤，陈 昊

基于物流配送的车辆路径优化问题综述

王雪凤，陈 昊

（辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001）

针对日常运营中与物流配送相关的车辆路径规划问题进行了汇总，从不同角度归纳了基于物流配送的车辆路径优化问题的研究分类，并归纳了几种常见的求解算法，旨在确定近几年VRP变体和应用算法的发展趋势，最后对未来物流配送中车辆路径问题的发展方向进行了讨论。

车辆路径优化；物流配送；算法

近年来，受各种因素推力作用，我国的物流行业得到了迅猛发展，物流作为“第三效益源”，显著影响着经济发展水平。随着更多企业加入到物流行业中，物流行业已经成为竞争最激烈的行业之一。物流配送是指根据客户需求，进行备货、装货、运输、送达的过程。配送调度和车辆路径规划对物流配送至关重要，在很大程度上决定了配送成本、客户满意度、配送时间等。由于货物的配送受到运输公司、客户和外部环境等多种因素的影响，物流配送与车辆路径优化问题(vehicle routing optimization in material distribution)已经成为众多学者研究的热门课题。如何实现科学物流配送是每个物流企业必须面临的一个非常复杂和关键的问题。物流配送过程中不仅仅要考虑车辆的路线规划，还要考虑车辆数量、车辆容量、配送时间和突发情况等，加之物流企业服务水平的提高和客户需求的随机性，使得现代物流配送在实际运营中难度更大。车辆路径优化是物流配送中的关键一环，直接影响到配送完成时间和配送成本。

车辆路径问题(vehicle routing optimization problem，VRP)最早是由Dantzig等[1]提出来的，是一组高级而复杂的路线问题，物流的合理化在很大程度上依赖于运输决策的合理化，通过运输路线的优化，可以提高物流配送车辆的效率，满足客户的服务需求。车辆路径优化问题被广泛应用于现实生活中。货物的配送受到多种因素的影响，这些因素被转化为问题的约束或变量，并最终导致VRP不同变体的产生。比如，带车辆容量限制的路径优化问题、动态车辆路径优化问题、绿色车辆路径优化问题等。学者们对该类问题的研究已经取得丰富的成果，理想又高效的物流配送与车辆运输调度计划是现今物流业急切需要的。

在复杂多变的现实环境下，对物流配送与车辆路径优化这一问题，如何综合多种目标，合理制定车辆调度计划，一直是国内外学者关注的焦点，因此本文主要总结现实情况下的VRP变体、问题的表述、目标函数以及对应求解算法。

1 物流供应与车辆路径优化问题的问题描述和研究分类

1.1 问题描述

物流供应与车辆路径优化问题旨在满足项目活动优先级和各种约束的情况下，合理安排不同装载容量的车辆，并根据实际路线情况选择适合的路线，以达到总成本最小、用时最短等目标。VRP问题可以描述如下。

(1)物流配送问题评价指标

最大效益、最小总成本、最高满意度、最低能源消耗等，VRP问题中配送总成本一般由车辆固定成本、等待成本、服务成本、惩罚成本、能源消耗费用等多种成本组成。

(2)物流配送路线优化数学模型

一个物流配送网络包含个客户站点，这些客户站点有不同的位置和货物需求；物流配送中心共有辆配送车，每辆车已知最大承载能力P(=1, 2, …,)，从配送中心出发并返回配送中心。

(3)约束条件

每辆车在执行物流配送任务时，且物流装载量不能大于车辆承载能力；车辆从配送中心出发，执行完任务必须回到配送中心，且每个客户只访问1次。

(4)VRP问题的决策变量

1.2 目标函数

VRP问题的目标函数一般情况下可以分为以下几类：总成本最小化(minimum total cost)、时间最短化(shortesttime)、客户满意度最高化(highest customer satisfaction)、碳排放量最少化(least carbon emissions)。

(1)总成本最小

(2)时间最短

(3)客户满意度最高

(4)碳排放量最少

(5)路程最短

总成本最小化的目标函数公式见式(1)，其中是车辆使用的固定费用，为车辆行驶单位时间内动态费用(如行驶过程中单位时间内的燃油费用和碳排放纳税额)。t表示车辆从节点行驶到节点的行驶时间，δ是提前到达目的地的等待时间，g是服务客户的时间。是项目中所有节点的集合，是客户集合。

客户满意度最高的目标函数公式见式(3)，在VRP问题中，客户期望物流能够及时配送且对配送的及时性有一定容忍度，一般而言，越接近客户的期望值，客户满意度就越高。F是关于客户满意度函数。

碳排放量的目标函数公式见式(4)，燃油消耗是衡量碳排放量的重要指标，通常用燃油消耗的函数进行碳排放量的计算。配送过程中使用车辆数量为，G表示车辆从节点到节点完成配送的碳排放量。

路程最短的目标函数公式见式(5)，其中d表示车辆从节点行驶到节点距离。配送总路程等于所有车辆所经过节点的累加和。

2 VRP变体分类

车辆路线问题(VRP)是当今物流业面临的关键性挑战之一，自提出以来产生了大量的变体，现实的路径问题中包含的约束和参数与不同的VRP变体有关，它们决定了路线、长度和持续时间。

2.1 考虑环境影响的研究

考虑环境影响的车辆路径问题是VRP重要的变体之一，被称之为GreenVRP(GVRP)。随着全球平均气温的上升和全球能源紧张局势，气候变化问题已成为全球关注的焦点。节能减排已成为国际社会的共同责任。碳排放是温室气体的主要来源，而交通运输是温室气体产生的主要途径之一，经济日益发展，交通运输与日增长，如何节能减排和提高资源效率是一项重要的科学研究课题。众多学者致力于减少碳排放的绿色车辆路径优化问题研究。

车辆中的碳排放取决于许多因素，如车辆负荷、重量、燃料的类型、燃料效率、行驶速度以及起点和目的地之间的距离等。距离并不是唯一的决定性因素，其他因素也有不同的涉及，传统测量燃油消耗的方法是行程长度的线性函数，但这不够精确。因此Liu等[2]提出了一种基于速度的碳排放量算法，发现以速度作为决策变量的路径优化策略比固定速度决策更有效地减少能源消耗和碳排放，且证明了在以最短路径为目标时，最短路径不一定能源消耗最小。邱金红等[3]研究了基于配送收益的多目标绿色车辆路径优化问题。Ganji等[4]针对具有多异质车辆进行配送的集成供应调度问题，综合考虑了车辆负载、速度和实际行驶距离3个因素对碳排放水平的影响，并采用3种多目标元启发式算法：多目标粒子群算法、NSGAII-非支配排序遗传算法和多目标蚁群算法求解。

2.2 考虑实时性和随机需求的研究

在现实的物流配送中，会面临很多诸如天气变化、事故等复杂的、不确定的情况，造成客户需求的变化。若大型车辆进行物流配送，客户减少需求量，会造成额外的车辆成本增加；若客户需求量突然增加，会造成部分客户的需求无法满足。订单和不可预见的事件可能会在执行过程中动态出现。

在运输因素不稳定的情况下，Dror等[5]首次提出允许分割交付的物流配送模型，以节省总距离和车辆费用。鲁玉等[6]研究了具有随机需求的铁路冷链物流运输问题，研究发现，客户需求量在一定的时期内服从正态分布，利用机会约束规划理论，将该问题转化为满足一定置信水平的约束条件的确定性问题。并设计了自适应遗传-模拟退火算法进行求解。陈治亚等[7]通过分析基于随机需求下的物流运输的可靠性，在车辆限载量满足一定的约束下，构造多目标车辆路径优化模型，改进蚁群算法并引入贪心策略进行求解。张得志等[8]提出了一种考虑随机需求和各线路均衡的订单拆分、车辆随机配对的服务策略，发现当客户需求大于车辆最大容量，那么订单将进行拆分，使用2个或2个以上的车辆进行物流运输。

考虑随机需求的车辆路径优化模型更具有现实意义，很大程度上提高了订单完成数量，节约配送成本。

2.3 考虑时间窗的研究

带有时间窗口的VRP(VRPTW)也是最常见的变体之一。在车辆运输的路径优化问题中，一般情况会加入时间窗限制，用来更好地定义客户满意度和计算运输过程中提前成本和延迟费用，其中每个客户确定了必须交付订单的时间窗，时间窗分为软时间窗、硬时间窗、模糊时间窗。软时间窗VRP要求车辆在时间窗内[ET, LT]到达，在[EET, ET]或[LT, LLT]到达会给予一定的惩罚；硬时间窗VRP要求必须在时间窗内到达，否则拒绝服务；模糊时间窗VRP是构造车辆到达时间的隶属模糊度函数，来定义客户满意度或惩罚费用。

吴倩云等[9]针对集成物流调度下的车辆路径优化问题，结合软时间窗和装载约束，建立了基于遗传算法的车辆路径优化模型；Pérez-Rodríguez等[10]研究了一种带有硬时间窗VRP问题，考虑服务每个客户的时间窗间隔、车辆数量和客户数量的关系，提出了一种分布估计算法来解决该问题；但经典的时间窗的概念并不能很好地表现出车辆未在合理时间内到达所造成的损失，也不能很好地模拟客户的偏好，因此户佐安等[11]对时间窗采用模糊化处理，用隶属度函数表示客户的偏好，在一定程度上提高了物流配送车辆路径问题的有效性和实用性。

2.4 考虑协同配送的研究

协同配送是包含多个配送中心的物流配送问题，旨在提高物流配送效率。Renaud等[12]描述一种新的启发式算法的多仓库车辆路线问题(MDVRP)在有多个配送中心的情况下，客户通常被分配到最近的仓库，该仓库包含每个客户订购的货物。MDVRP在许多情况下都会遇到，并且具有相当大的经济重要性，比如快递送餐、石油运输、包装食品等。Wang等[13]提出了一种基于多仓库的协同配送车辆路径优化问题(CMCVRP)，通过协作机制，使客户需求合理分配到相邻的仓库，以实现运营成本和分销成本最小化的目标，有效地提高车辆装载率，减少交叉运输现象，提高物流网络运营效率。

在运输公司中不太常见的2种VRP变体，分割交付VRP(SDVRP)和定期VRP(PVRP)。Dror等[14]研究VRP的松弛版本，在通常情况下，每个客户必须由1辆车访问1次的约束被放宽，并且客户需求的交付可以分给任意数量的车辆。在某些配送环境中，特殊放松可能是有利的，例如当平均客户需求略超过车辆容量时，增加车辆负荷系数和减少交付路线数量，会节约成本。而PVRP，最早是Coene等[15]提出来的，是针对一个时期的优化，与传统的VRP一样，给出了每个具有特定需求功能的客户位置，以及一组有能力的车辆。此外，路线的计划发生在天的时间内，客户以不同的频率访问。其目标是使规划范围内所有路线的成本总和最小化。Francis等[16]在PVPP问题中引入服务频率进行建模，在一段时间内为每辆车每天寻找一组行程，以减少总旅行成本减去服务效益的目标，同时满足操作限制(车辆容量和访问频率最小值)。

2.5 考虑车辆能力的研究

道路物流运输会用到不同类型和容量的车辆，任何情况下都不能违背车辆的运输能力限制。车辆的容量是车辆路径问题的一个关键因素，因为它是现实分布情况中研究最多的2个变体VRP：(1)同构VRP(CVRP)，所有车辆具有相同的容量；(2)异构VRP(HFVRP)，车辆具有不同的容量。

Ganji等[4]根据订单货物容量分配订单给不同的异构车辆，在一定程度上减少了燃料成本和碳排放量。陈希琼等[17]在研究带车辆容量限制的同构VRP问题时，用有向图表示网状物流运输路线，并设置最大车辆运输距离和每条边上流量不能超过最大车辆容量的约束条件，以达到成本和各车辆工作负荷之差最小的双目标模型。

殷亚等[18]在对同构VRP问题的研究中引入车辆路线限制和装载能力约束。无论车辆异构的还是同构的，考虑装载约束时，又有2个变体产生：二维(2D-VRP)装载约束和三维(3D-VRP)装载约束。

尚正阳等[19]在考虑车辆容量和装载约束的情况下，设计了最少剩余开放空间的货物装载方法，更大限度提高车辆利用率。王勇等[20]研究了三维装载约束的车辆路径优化问题，装车时对货物的行数、列数、层数进行规划，并结合车辆装载货物的数量、体积、重量，采用NSGA-Ⅱ算法生成配送路径和三维装载方案。

2.6 带有回程和同时拾取交付的研究

物流操作并不会在货物交付阶段结束，因为客户退货的现象在实践中是常见的。最早的取货和送货VRP的研究为带有回程的VRP(VRPB)，VRPB中车辆送货后取货，避免了回程的空车行驶，节省了运输成本。然而在传统的VRPB中，需服务完送货点后再服务取货点，这样势必造成车辆路径的迂回，对于既有送货需求又有取货需求的客户，产生了同时拾取和交付的VRP(VRPSPD)。这2种变体几乎都以最小化车辆数或总行驶距离为研究目标。

Montané等[21]首次提出VRPSPD问题，在VRPSPD的情况下，货物从中央仓库开始交付给客户，同时取货装载到车辆上，然后返回仓库。在每个阶段，都必须考虑交付和拾取负荷，因为不能超过车辆的总容量。另一方面，Goetschalckx等[22]研究的VRPB也涉及拾取和交付，并且所有拾取都是在每条路线交货后收集的。所以这2种变体被认为是同一变体，在文献的分类中被命名为VRPPD，因为它们都涉及到拾取和交付。

3 求解算法

车辆路径规划问题是经典的组合优化问题之一，属于NP-hard问题。在这个问题被提出的几十年历史中，算法研究逐渐繁荣起来，总体上可以分为精确算法、启发式算法和元启发式算法等。精确算法可以求得小规模物流配送路径优化问题的最优解，但对现代大型物流配送路径优化问题来说，计算复杂性大，求解效率低。启发式算法与精确方法相比，提高了求解效率，但很难得到物流配送路线的最优解决方案。元启发式算法具有搜索速度快，能够获得高质量解等优点，因此成为解决物流配送问题的主要方法。

不同的算法具有不同的优缺点，在车辆路径优化的研究中，学者不断改进或融合各算法的优势，提出具有更高效率或最优解的算法。Bhagade等[23]首次应用人工蜂群算法求解物流配送中的车辆路径优化问题。人工蜂群算法具有很高的灵活性，通过考虑很少的控制参数，可以有效地寻找最短路径。Zhao等[24]提出了一种基于成本、碳排放和客户满意度的多目标优化模型，并设计了一种具有多目标启发式函数的蚁群算法(ACOMO)来求解，ACOMO算法优于经典的蚁群算法。

Liu等[25]提出了一种基于对立学习的物流配送路径优化(OBLPSO)算法，建立物流配送路径优化数学模型，通过粒子间的协作和信息交换求解，引入基于对立的学习机制来提高粒子群优化能力和收敛速度，与其他物流配送路线优化算法相比，OBLPSO算法可以获得短时间、合理路线的物流配送解决方案。Ganji等[4]采用3种多目标元启发式算法：多目标粒子群算法(MOPSO)、非支配排序遗传算法(NSGA-Ⅱ)和多目标蚁群算法(MOACO)求解车辆路径优化问题，实验表明，NSGA-Ⅱ在求得最优解和处理时间上，优于其他2种算法。Xiong[26]针对物流配送路径优化问题，提出了一种新的混合更新信息素策略的蚁群算法(ICAO)，在以最短距离和最短时间为目标时，IACO算法明显优于经典ACO算法，有效缩短了配送任务时间和运输路径距离，最大限度地提高物流整体和配送的效率。Jabir等[27]提出了一种将蚁群优化算法与变量邻域搜索相结合的混合求解算法(ACO-VNS)，混合ACO-VNS启发式算法将提供一组通向Pareto最优解边界的非支配解。Liu等[2]提出了一种基于云模型的多目标混合量子免疫算法(CHQIA)。郭森等[28]提出了一种基于动态学习和突变因子的粒子群算法(DSPSO)，采用动态学习策略来自适应更新PSO认知成分和社会成分的权重，突变因子使PSO算法具有跳出局部收敛的能力。罗梓瑄等[29]设计带有精英策略的非支配排序遗传算法(NSGA-Ⅱ)对物流配送路径优化模型进行求解。François等[30]开发并测试了2种自适应大邻域搜索(ALNS)算法，该算法不考虑持续时间的约束。Nalepa等[31]针对带有时间窗车辆路径问题，提出了一种自适应模因算法，算法的参数，如选择方案、种群大小和生成的子解的数量，在搜索过程中被动态调整。主要优化目标及其算法如表1所示。

表1 主要优化目标及其求解算法

4 未来研究展望

物流配送与车辆路径优化问题随着时代发展不断发展，该问题已经产生了大量变体，并且由此而产生的解决方案已经应用于现实生活中，未来的研究方向主要包括以下方面。

(1)随着清洁能源的电动汽车的普及，带充电站的电动汽车物流配送可作为未来研究的新热点。

(2)在实际的物流配送车辆路径优化所构建的模型中，大部分研究忽略了天气、道路交通、客户需求不稳定等不确定性因素。不确定环境下的动态物流配送问题，将是未来的研究方向，也更加贴近生活需要。

(3)未来的信息价值将呈现出重要价值。如何对现在的信息进行整合，对未来的车辆调度或者路径规划进行合理的指导，获得一个最优方案将是物流配送中亟待解决的问题。

[1] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[2] Liu X H, Shan M Y, Zhang R L, et al. Green Vehicle Routing Optimization Based on Carbon Emission and Multi-objective Hybrid Quantum Immune Algorithm[J]. Mathematical Problems in Engineering, 2018, 2018(4): 1-9.

[3] 邱金红, 孙靖, 仲兆满. 基于配送收益均衡的多目标绿色车辆路径优化算法[J]. 控制与决策, 2021, 12(3): 1-7.

[4] Ganji M, Kazemipoor H, Molana S. A green multi-objective integrated scheduling of production and distribution with heterogeneous fleet vehicle routing and time windows[J]. Journal of Cleaner Production, 2020, 259: 120824.

[5] Dror M, Trudeau P. Savings by Split Delivery Routing[J]. Transportation Science, 1989, 23(2): 141-145.

[6] 鲁玉, 徐行方, 尹传忠, 等. 铁路冷链物流运输多目标机会约束规划[J]. 同济大学学报: 自然科学版, 2021, 49(10): 1407-1416.

[7] 陈治亚, 高辉, 徐光明, 等. 考虑随机需求和硬时间窗的多目标车辆路径优化方法[J]. 铁道科学与工程学报, 2021, 18(12): 3110-3120.

[8] 张得志, 何亦扬, 龚浩翔. 随机需求订单可拆分的多目标车辆路径问题[J]. 铁道科学与工程学报, 2018, 15(5): 1-10.

[9] 吴倩云, 谢乃明, 邵雨婷. 考虑时间窗和装载约束的装配线集成物流调度[J]. 计算机集成制造系统, 2020, 26(3): 806-814.

[10] Pérez-Rodríguez R, Hernández-Aguirre A. A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows[J]. Computers & Industrial Engineering, 2019, 130: 75-96.

[11] 户佐安, 贾叶子, 李博威, 等. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.

[12] Renaud J, Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle routing problem[J]. Computers & Operations Research, 1996, 23(3): 229-235.

[13] Wang Y, Ma X, Li Z, et al. Profit distribution in collaborative multiple centers vehicle routing problem[J]. Journal of Cleaner Production, 2017, 144: 203-219.

[14] Dror M, Trudeau P. Savings by split delivery routing[J]. Transportation Science, 1989, 23(2): 141-145.

[15] Coene S, Arnout A, Spieksma F C R. On a periodic vehicle routing problem[J]. Journal of the Operational Research Society, 2010, 61(12): 1719-1728.

[16] Francis P, Smilowitz K, Tzur M. The Period Vehicle Routing Problem with Service Choice[J]. Transportation Science, 2006, 40(4):439-454.

[17] 陈希琼, 胡大伟, 杨倩倩, 等. 多目标同时取送货车辆路径问题的改进蚁群算法[J]. 控制理论与应用, 2018, 35(9): 1347-1356.

[18] 殷亚, 张惠珍. 求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法[J]. 计算机应用研究, 2017, 34(12): 3632-3636.

[19] 尚正阳, 顾寄南, 潘家保. 考虑LIFO约束的2L-CVRP优化[J]. 计算机集成制造系统, 2021, 27(7): 2134-2143.

[20] 王勇, 左佳昕, 蒋琼, 等. 基于产品回收定价的逆向物流车辆路径优化问题[J].系统管理学报, 2022, 31(2): 199-216.

[21] Montané F A T, Galvao R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J]. Computers & Operations Research, 2006, 33(3): 595-619.

[22] Goetschalckx M, Jacobs-Blecha C. The vehicle routing problem with backhauls[J]. European Journal of Operational Research, 1989, 42(1): 39-51.

[23] Bhagade A S, Puranik P V. Artificial bee colony algorithm for vehicle routing optimization problem[J]. International Journal of Soft Computing and Engineering, 2012, 2(2): 329-333.

[24] Zhao B, Gui H, Li H, et al. Cold chain logistics path optimization via improved multi-objectiveant colony algorithm[J]. Ieee Access, 2020, 8(1): 142977-142995.

[25] Liu X J, Zhang B. Study on Optimization of Logistics Distribution Routes Based on Opposition- based Learning Particle Swarm Optimization Algorithm[J]. Logistics Technology, 2014, 7(1): 1318-1322.

[26] Xiong H. Research on cold chain logistics distribution route based on ant colony optimization algorithm[J]. Discrete Dynamics in Nature and Society, 2021, 2021(1): 134-139.

[27] Jabir E, Panicker V V, Sridharan R. Multi-objective Optimization Model for a Green Vehicle Routing Problem[J]. Procedia-Social and Behavioral Sciences, 2015, 189: 33-39.

[28] 郭森, 秦贵和, 张晋东, 等. 多目标车辆路径问题的粒子群优化算法研究[J]. 西安交通大学学报, 2016, 50(9): 97-104.

[29] 罗梓瑄, 杨杰庆, 刘学文. 基于NSGA-Ⅱ的考虑客户满意度的多目标车辆路径问题研究[J]. 重庆师范大学学报: 自然科学版, 2020, 37(6): 1-5.

[30] François V, Arda Y, Crama Y, et al. Large neighborhood search for multi-trip vehicle routing[J]. European Journal of Operational Research, 2016, 255(2): 422-441.

[31] Nalepa J, Blocho M. Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows[J]. Soft Computing, 2016, 20(6): 2309-2327.

Review of Vehicle Routing Optimization Based on Logistics Distribution

WANG Xue-feng, CHEN Hao

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

This paper summarizes the vehicle routing plan problems related to logistics distribution in daily operations, the research classifications of vehicle routing optimization problems based on logistics distribution from different perspectives, and several common algorithms to determine the development trend of VRP variants and application algorithms in recent years, and finally discusses the development direction of vehicle routing problems in logistics distribution in the future.

vehicle routing optimization; logistics distribution; algorithm

10.15916/j.issn1674-3261.2022.06.008

TP311

A

1674-3261(2022)06-0386-07

2022-04-12

王雪凤(1996-)，女，河南开封人，硕士生。

责任编辑：孙 林