交通 | 车辆路径问题的簇分支法

1.引言

2.分支质量度量与簇分支动机——以CMT13算例为例

3.簇分支的簇划分方法

4.数值实验

4.1 XML 数据集实验（小规模多样化，100个客户）

4.2 X 数据集实验（大规模 CVRP，100-1000个客户）

4.3 Homberger & Gehring 数据集实验（VRPTW）

4.4 延长运行时间与攻克开放算例 (Long Runs)

5.结论

微信公众号后台回复

蓝色字

关注我们！

推文作者：周博龙，香港科技大学在读博士生，研究方向: 城市环境中无人机集成服务网络优化

编者按

本文介绍了一种用于求解车辆路径问题（VRP）精确算法的新颖分支策略——簇分支（Cluster Branching）。尽管分支操作对于基于分支定界（branch-and-bound）算法的效率至关重要，但现有的分支类型（如边分支、割集分支以及 Ryan-Foster 分支）均存在一定的局限性。本文提出的分支策略将多个边变量聚合成了与客户簇（clusters of customers）相对应的更高层次的决策结构。

通过对带容量限制的车辆路径问题（CVRP）和带时间窗的车辆路径问题（VRPTW）算例进行大量计算实验，本文证明了簇分支（CB）显著提升了当前最先进的分支切割定价算法（Branch-Cut-and-Price）的性能。簇分支策略通常能够提高分支质量并有效缩减搜索树的规模，从而使得更多算例得以成功求解。不仅如此，研究还表明，CB 在不同类型的算例上均展现出了鲁棒的性能，即使对于客户位置随机分布的算例也能取得良好的效果。

车辆路径问题（VRPs）是组合优化领域被研究得最广泛的问题之一。由于几乎所有 VRP 的变体都是 NP-hard 的，启发式算法在实际应用中占据主导地位。然而，近年来精确算法取得了长足进步，目前最先进的精确算法大多基于分支切割定价算法（branch-and-cut,BC）或 分支切割定价算法（Branch-Cut-and-Price, BCP）。即使是最复杂的 BCP，本质上仍是分支定界（B&B）算法。这些算法通过分支来探索解空间：它首先构建一个搜索树，然后使用界限来剪枝无法产生改进解的节点。

B&B 搜索树的规模在很大程度上取决于根节点间隙（root node gap）以及分支质量（Branching Quality）。现有的 VRP 分支策略主要包括：

现有策略大多没有在分支决策时明确考虑算例的空间拓扑结构。本文提出了一种新颖的簇分支（Cluster Branching, CB）策略，通过提取并利用客户间的空间结构特征，将处于顶层搜索树中的关键分支决策与短暂的分数解解耦，从而引导算法做出更具战略性、更稳定的分支决策。

为了科学评估不同分支策略的优劣，本文定义了两个核心指标：

经典数据集中的 CMT13 算例（带有距离约束的 CVRP）长期以来即使是最先进的 BCP 算法也难以在合理时间内求解。观察其最优解的拓扑结构可以发现，客户被分成了 6 个非常明显且相互远离的“簇（Clusters）”。

因此，传统的边分支（EB）对 CMT13 效果不佳。为此，作者提出了簇分支（CB）。定义簇的划分，其中为车场。CB不仅对整个簇相关的变量进行分支，还对聚合了两个两个簇之间所有变的变量进行分支。在CMT13的实验中，CB结合传统策略将原本24小时无法解决的问题在不到2.5小时内求解至最优。

CB 的一大特点是在优化算法启动前就进行静态簇划分。在CMT13算例中，作者采取了手动簇划分。本文还探索了多种自动簇划分算法：

为了验证簇分支（CB）策略在实际求解中的有效性，作者依托 BaPCod C++ 库，结合目前最先进的 BCP 底层实现（包含基于桶图的标签算法、路径枚举等），开展了大规模的数值实验。实验服务器配备了双路 18 核 Intel Xeon Gold 6240 处理器，并针对每个算例分配单线程运行。

算法的搜索策略采用了独特的双树结构（广度优先与深度优先结合）：主树采用广度优先搜索（BFS），优先探索下界（LB）最小的开放节点，从而在搜索树顶层积累大量节点；当开放节点达到一定数量时，将新节点推入辅树进行深度优先搜索（DFS）。这种机制有利于在搜索树顶层和不同部分测试和分析不同分支决策的质量。

XML 数据集包含了 10,000 个精心设计的 100 客户 CVRP 算例，涵盖了多种客户分布（随机、聚类、随机-聚类）、车场位置、需求分布以及路线长度特征。BCP 算法在根节点直接求解了其中 7,585 个相对简单的算例，因此后续分支策略的对比均在剩余的 2,415 个困难算例上进行，时间限制设定为 1 小时。

首先，作者对比了在传统边分支（EB）和割集分支（CSB）基础上加入不同簇划分算法（MST, K-means, DBSCAN等）的综合表现：

从 结果来看，无论使用哪种簇划分算法，CB 都能显著提升现有分支类型的性能。其中，表现最佳的是 CSB 结合参数 的最小生成树簇划分（CSB + MST1.5），它在所有测试配置中求解了最多的算例并获得了最高的分支得分。

为了进一步深入探究，作者选取了表现非常稳定的 MST1.0 作为基准聚类方法，并针对不同的算例特征进行了细化分析，同时使用 Wilcoxon 符号秩检验进行了统计学分析：

作者得出几个关键结论：

为什么随机分布也能起效？作者通过绘图指出，在 100 个点的空间内，即使是随机生成，也容易出现靠得比较近的“自然簇”。

为了测试算法在大规模实例上的泛化能力，作者使用了包含 100 至 1000 个客户的经典 X 数据集。经过筛选，实验在 70 个难以在根节点求解的算例上进行，时间限制延长至 24 小时，且主树限制为 100 个开放节点。

在更大规模的测试中，CB 再次证明了其价值，尤其是在聚类（Cl）和随机-聚集（RC）算例中，基于 MST 的 CB 为 EB 和 CSB 提供了全面的性能提升。

不过作者也指出：对于高达 1000 个客户的纯随机分布（Rd）的大规模算例，传统的 EB 表现有时会优于加入了 CB 的策略。原因在于，当随机点的数量呈数量级增加时，空间中几乎不再存在“自然簇”，这导致 CB 难以提取有效的几何特征。

针对带有时间窗约束的 VRPTW，作者在 Homberger 和 Gehring 的 200至1000客户基准测试集上进行了实验，筛选出 93 个困难算例，时间限制 24 小时。

结论与前文类似：加入 MST CB 能够显著提高 EB 和 CSB 的总体（Overall）性能得分。但作者在这里提出了一个前瞻性的讨论：目前测试的 CB 仅考虑了纯空间的几何距离聚类簇划分，而忽略了时间窗信息。 实际上，两个空间上很近的客户，如果时间窗完全错开，它们其实不应被归入同一个“簇”。如果未来的簇划分算法能将时间维度纳入考量，CB 在 VRPTW 上的表现有望得到进一步的飞跃。

最后，针对那些在 24 小时实验中 ETS%（期望探索树规模百分比）指标较高的“潜力算例”，作者在服务器多个核心上对开放节点生成的子树进行了长达数月的并行计算。详细的结果可以在原文Appendix B中找到。

本研究为车辆路径问题提出了一种基于问题空间拓扑结构的新型分支策略——簇分支（CB）。其核心思想是在优化启动前，根据空间位置将客户聚类，并将生成的簇相关的聚合边变量引入 B&B 算法中提供新的分支维度。

大量实验表明，CB 能够使搜索树顶层的关键分支决策不再局限于短视地修补当前分数解，而是从更高层的结构着眼。将 CB 与经典的边分支（EB）或割集分支（CSB）相结合，能够普遍且显著地提升算法性能。这种策略不仅在空间分布聚集的现实物流场景中极具价值，也为未来结合机器学习进行更智能的特征聚类，或向其他组合优化问题推广提供了广阔的想象空间。

参考文献：

Silva, J. M. P., Uchoa, E., & Subramanian, A. (2025). Cluster branching for vehicle routing problems. INFORMS Journal on Computing.

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

文章须知

作者：周博龙，香港科技大学在读博士生

责编：祝心怡

微信编辑：疑疑

文章由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知

关注我们

FOLLOW US