容量约束的车辆路径问题研究现状综述*

靳康飞，闫 军，梁云涛

（兰州交通大学 机电技术研究所，甘肃 兰州 730070）

0 引言

如何有效地分配物流资源、降低运输的成本，车辆路径问题（Vehicle Routing Problems，VRP）是近年来交通运输和物流研究领域的热门问题。VRP问题被提出后，影响VRP问题的因素被重点研究，如车辆容量的变化，与时间有关的限制，是否取送货的限制。容量约束的车辆路径问题（Capacitated Vehicle Routing Problems，CVRP）是车辆路径问题的拓展问题，最初由Dantzig和Ramser提出［1］，根据他们的定义，在一个中心仓库中具有相同容量或不同容量的车队，为一组需求量不同、位置信息不同的客户完成配送任务。在配送的过程中，从总的旅行时间、物流成本和配送时间等几个方面确定最优的路线。CVRP自从被提出后，国内外学者做了大量的研究。

CVRP问题在实际生活和理论研究中具有广泛的应用。比如在实际的物流配送中，牛奶的收集与配送，煤炭物流中生产资料的运输问题，垃圾的回收与处理，运输车辆能耗的绿色车辆路径问题，饮料行业的配送问题，抗震救灾中的物资配送等现实情况的应用。CVRP问题是VRP问题的基本类型，因为它是VRP问题最基本的衍生问题，也很容易与VRP的其他衍生问题相结合，因此VRP也是学者研究最多的问题。在新能源车辆能源补充站数量有限的情况，由于新能源车辆的行驶距离有限，研究考虑新能源车辆运载能力绿色车辆路径问题［2］。文章主要对物流运输领域的CVRP发表的文献进行简要的总结和分析，CVRP的基本类型和衍生类型的研究进展进行分类综述，并分析了CVRP未来的研究发展趋势。

1 CVRP问题研究现状

1.1 CVRP问题文献研究现状

文章从Web of science和ScienceDirect以“Capaci⁃tated Vehicle Routing Problems”检索了公开发表的文献，对检索的文献进行人工删选，剔除了不相关的文献（会议摘要，评论和已撤销的出版物），并做了客观的分析。研究CVRP问题的文献最早发表在1997年，随后众多学者的研究逐渐增多。从1997～2021年发表的有关研究CVRP问题的文献数量，如图1所示。从2012年开始，CVRP问题研究逐渐增多，2015年文献数量增长较快，而最近5年来发表的文献数量较多。可见，CVRP问题已经逐渐成为近年来研究的热点。

图1 1997～2021年CVRP领域发表文献数量

统计发表在SCI上发表的CVRP的文献。由表1可知，根据JCR分区，发表在Q1/Q2的文章居多（发表论文数量超过3篇的期刊）。图2表示的是发表CVRP期刊所属的国家情况：英国占比最多（32%），荷兰（29%）和美国（17%）次之。

表1 发表CVRP论文的主要期刊

图2 各国研究CVRP情况

通过分析现有发表的CVRP论文，其中发表在《Eu⁃ropean Journal Of Operational Research》中的一篇文献，被引了133次，发表CVRP问题最多的期刊是《Com⁃puters&Operations Research》。表1统计了1997～2021年发表CVRP论文的主要期刊（发表论文数量超过3篇的期刊）。图3表示了发表CVRP论文的数量和影响因子（图中期刊名称为简称）。

图3 发表CVRP论文期刊的数量和影响因子

1.2 CVRP研究进展

1.2.1 CVRP研究内涵

CVRP是指在物流的配送网络中，有一个分拨中心，多个需求量不同的客户和多台配送车辆，在不超过车辆容量的前提下，合理的规划车辆的配送路径，使得总的配送费用最低的目标。CVRP是VRP的最基本类型。此问题中，客户的信息是确定的，（如客户的需求量，车辆的数量，客户的位置等），客户的服务类型单纯为取送货物，配送中心车辆的类型相同且车辆的约束也相同，客户的需求量不大于车辆的容量，每个客户的需求量不能被分割（即每个客户仅由一辆车服务），配送车辆都是从分拨中心出发，完成配送任务后返回分拨中心，使问题的目标最小化。

CVRP可描述为假设某配送区域内有n个客户，分拨中心有m辆车，配送车辆从分拨中心出发，完成配送任务后返回分拨中心。CVRP问题做出以下假设：（1）配送中心或分拨中心和客户的位置点已知，且客户的需求量已知，车辆行驶的起点和终点都为配送中心；（2）每一条子路径必须至少有一个客户，每一条配送线路的子路径客户的总需求量不超过车辆的最大容量约束，配送中心可同时派出多辆车服务；（3）每辆车的单位时间的花费成本都相同，每辆车的载重量，性能都已知；（4）每个客户都有确定的需求，确保每个客户都被服务。

1.2.2 CVRP相关算法研究现状

CVRP属于NP-hard问题。CVRP问题是在VRP的基础上增加了车辆容量的约束条件，则在求解过程中必须同时考虑客户的需求量、货品的分配、车辆的数量和路径规划；CVRP的解是一组车辆路径规划的集合。CVRP求解时路径问题和排序子问题是车辆调度需要解决的两个子问题。路径子问题是指每一个客户必须有可供选择的车辆，即必须保证每个客户被服务。排序的子问题所有的客户被服务后，对所有的客户的服务顺序利用算法规划合适的路线。所以通常求解CVRP问题时一般有两种方法：一是分别考虑路径子问题和排序子问题；二是同时考虑两个子问题一起求解。

求解CVRP的算法一般可分为：精确算法、启发式算法和元启发式算法。精确算法指求出最优解的算法，在面对小规模的NP-hard问题时，求解效果优于启发式算法。精确算法可分为：动态规划算法、列生成法、切面法、分支定界算法和整数线性规划算法。Hokama提出一种分切割算法求解二维装载约束的CVRP问题［3］。在求解大规模CVRP问题时，精确算法容易陷入局部最优，从而影响其求解效果；而启发式算法和元启发式算法求解大规模的CVRP问题表现出很好的性能。启发式算法有：节约法、C-W节约算法、两阶段算法。元启发式算法又称智能优化算法：模拟退火算法、禁忌搜索算法、遗传算法、蜂群算法、粒子群算法、变领域搜索算法。近年来，为提高算法的求解性能，多种改进的优化算法和混合的优化算法被越来越多的学者提出。尚正阳利用回火操作，解决了全局搜索与局部搜索不平衡的问题；通过随机邻域变换策略，提高多约束条件下的新解生成质量，提出回火操作的改进模拟退火算法［4］。黄戈文［5］用自适应的遗传灰狼优化算法，蒋海青［6］在遗传算法的基础上应用化学优化算法，李阳［7］用混合变邻域生物共栖搜索算法求解CVRP问题。

2 CVRP衍生类型研究现状

在CVRP基础上，增加不同约束的可拓展为不同的子问题，主要有4个方面，包括：增加装载限制约束时，CVRP可拓 展 为2L-CVRP（Vehicle Routing Problems with Two-Dimensional Loading Constrain）和3L-CVRP（Vehicle Routing Problems with Three-Dimensional Load⁃ing Constrains）；增加时间窗的约束时，CVRP可以拓展为带时间窗的容量约束的车辆路径问题（Capacitated Vehicle Routing Problem with Time Window，CVRPTW）。当客户的需求量信息变化时，CVRP可拓展为客户点需求量信息具有随机分布特点的随机需求车辆路径问题（Vehicle Routing Problem With Stochastic Demand，VRPSD）；随着客户规模的不断增加，国内外的学者也开始研究大规模的CVRP问题。

2.1 装载限制的CVRP

具有二维装载约束的容量限制的车辆路径问题（2L-CVRP）是CVRP的拓展问题，2L-CVRP的目标是通过路径调度优化和装载优化两方面的问题，使配送车辆的总路径最小。在2L-CVRP问题中，货车的车厢被抽象为一个长为L、宽为W的二维长矩形，则S=L*W为货物的总装载面积，而所有的货物被抽象为矩形的底面。而根据货物装载的情况，2L-CVRP可分为有序无方向、有序有方向、无序无方向、无序有方向［8］。装载与路径的联合优化的求解，事实上并不是两个优化问题的简单叠加或集成，这两个问题是相互结合并且是错综复杂的。2005年，Iori［9］首先提出了2L-CVRP模型，并求解了规模为35个客户，90多个实例。2008年，Gendreau［10］提出了可以解决大规模2L-CVRP的禁忌搜索算法。随后，越来越多的优化算法被应用到了求解2L-CVRP。2017年，对考虑二维装箱约束的多车场时间窗车辆路径问题（Two-Dimensional Loading Capaci⁃tated Vehicle Routing Problems with Multi-depots and Time window，2L-CVRP-MDTW），颜瑞［11］提出了由量子粒子群算法和引导式局部搜索算法组成的混合算法进行求解。2021年，针对LIFO约束下的2L-CVRP问题，尚正阳［12］提出了ISA-LOS算法（Improved Simulated An⁃nealing，ISA，Least Open Space，LOS）。

三维装载约束的容量限制的车辆路径问题（Vehi⁃cle Routing Problems with Three-Dimensional Loading Constrains，3L-CVRP），是三维装箱配载和路径调度的组合优化问题。装载货物时，必须考虑货物的特性（易碎、不可挤压），能否进行配载，还需考虑货品的体积和重量不能超过车厢的可承受范围。车辆行驶路径是否可行依赖于货物能否全部装车，反过来货品的装载次序同样会影响配送路径的方案，因此两者是相互紧密联系的，必须综合考虑。Koch将车厢分区，从而解决同时取送货的3L-CVRP［13］。2015年，颜瑞针对3L-CVRP问题，提出模糊遗传算法和引导式局部算法相结合的GLSFGA算法［14］。2016年，颜瑞在3L-CVRP的基础上，考虑多配送中心，利用GLSFGA求解考虑三维装箱约束多配送中心车辆路径问题（Three-Dimensional Load⁃ing Multi-Depots Capacitated Constrains Vehicle Routing Problem）［15］。国内外的学者还考虑了分仓运输、生鲜农产品、货物的多层车厢配送、货物不能混装的3L-CVRP问题。

2.2 带时间窗的CVRP

带时间窗的容量约束车辆路径问题（CVRPTW），指每一个客户都有一个服务的时间窗口，这个时间窗口是指服务客户所用的时间，车辆的配送任务必须在这个时间窗口开始和结束的时间内为客户服务。González［16］提出了一种特殊的车辆路径问题，即累积容量约束问题带时间窗约束的车辆路径问题（the Cumu⁃lative Capacitated Vehicle Routing Problem with Timewindow Constraints，Cum CVRPTW）。问题描述为：有一组地理位置分散的客户，客户的要求是在一个固定的时间窗内完成配送任务，目标的成本计算为所有客户的到达时间之和；并用大领域搜索算法和遗传算法相结合的算法求解此问题。同时具有三维装载约束和时间窗约束的车辆路径问题（Capacitated Vehicle Routing Problem With Three-Dimensional Loading Constraints with Time Windows，3L-CVRPTW），Pace［17］用局部搜索算法和模拟退火算法相结合的算法，王超［18］用多阶段算法与两层算法相结合的算法分别求解了此问题。

2.3 随机需求的CVRP

在实际的快递物流过程中，零售商（快递和物流行业的客户）的货物数量事先不知道，快递和物流行业就得将客户需求的随机信息考虑进来，从而可以降低物流的成本。客户点需求量随机分布，且假设在规划每个客户的概率发布已知的车辆路径问题，称为随机需求的车辆路径问题（Capacitated Vehicle Routing Problem With Stochastic Demand，CVRPSD）。Christian［19］用分支定价算法求解随机需求的车辆路径问题。Wang［20］研究随机需求的两级有容量约束的车辆路径问题，首先用随机规划描述了此问题，并基于遗传算法求解2ECVRPSD问题。李阳［21］通过构建CVRPSD的随机机会约束的模型，设计两阶段的混合变领域搜索算法，减少对人工和车辆的占用。

2.4 大规模的CVRP

容量约束车辆路径问题（CVRP）由于其在各种现实场景中的应用，近年来得到了广泛的研究。通常对CVRP的研究是对标准算例库，其规模主要是从几十到几百个客户点，而随着科技的发展，CVRP中的客户通常会上升到一定的规模，因此LSCVRP研究就很有必要。然而，对于大多数现有算法来说，解决大规模CVRP仍然是一个非常具有挑战性的问题，即拥有数百或数千个客户的CVRP。在解决中小规模的CVRP问题（一般指服务的客户不到500人）时，启发式算法和数学规划算法有很高的效率；然而，这两种方法在处理LSCVRP时的可拓展性较差。上述2类算法在解决中小规模的CVRP问题（通常需要服务的客户不到500人）时都表现出了很高的效率。然而，它们中的大多数对大规模CVRP（LSCVRP）的可扩展性较差，尤其是对于拥有1000多个客户的客户。Teymourian［22］通过利用智能水滴和布谷鸟搜索方法在探索解决方案空间方面的优点，提出2种混合启发式算法，该算法在解决50～483个客户的CVRP问题有很高的效率。Mester［23］将进化策略和引导式局部搜索结合到一个迭代的两阶段过程中，对50～1200个客户的CVRP，实验结果表明该算法有较好的可拓展性。Xiao［24］提出可变领域的模拟搜索算法，并在1200个CVRP客户的基础上验证此算法的优越性。Armas［25］讨论时间容量限制的弧路径问题（Capacitated Vehicle Arc Routing Problem，CARP），并介绍了一种启发式和亚启发式算法解决此问题。

3 结语与展望

CVRP问题的研究对物流配送车辆的路径的优化有重要的生活应用和理论研究价值。通过对配送车辆的容量约束，优化装货方案和确定最优的路径方案可以降低车辆配送中的行驶成本，从而降低整体的物流成本。文章对CVRP研究进展做了简要的归纳和总结，包括CVRP的基本类型和衍生问题。基于CVRP研究现状综述，得出CVRP未来的研究方向和趋势，希望可以为交通运输、物流配送领域的学者提供一些见解和启示。

为减少对环境的影响和新能源车辆的使用，绿色车辆路径问题逐渐成为未来研究的热点。考虑实时的交通信息，比如道路状况和停车位的可用性，配送车辆可以被规划到不太拥挤的路线，可以减少配送的服务时间；通过规划使车辆以最佳的速度行驶，就可以使配送过程更加环保，从而减少污染。将日常交通拥堵的真实模式参考进来，如规划的范围、仓库的位置、车队规模和组合、出发的时间、客户的需求以及时间窗口的设置，这有助于更好地了解城市物流系统的运行，从而更好地处理能源消耗的变化。

设计和开发新的解决方案，比如优化模拟技术、智能优化的算法、机器学习。目前好多算法在解决特定的车辆路径优化问题表现出良好的性能，如何设计通用的算法来求解CVRP问题。精确算法只能求解小规模CVRP和启发式算法容易陷入局部最优，而机器学习具有求解高效、稳定的特点，已有学者将机器学习（无监督学习、强化学习）的方式应用到车辆路径优化问题。未来的研究中可以加大对机器学习的探索，从而使得求解CVRP更加稳定和高效。

多行程优化的车辆路径问题引起了学者的关注。配送车辆在完成配送任务时只能从配送中心出发一次，而多行程优化问题配送车辆可以返回配送中心补货后继续执行配送任务。关于时间窗的模糊需求的多行程优化问题，同时考虑车队规模和组合的复杂性、不同车型多车厢的限制，是CVRP问题未来面临的新挑战。