💻 computer science

A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

本研究表明，一种结合了灵活容量约束的蚁群优化方法在实际的哥伦比亚入境物流网络中显著优于地理聚类基准模型，在实现车队规模、行驶距离和运营成本大幅降低的同时，最大化了车辆利用率。

原作者： Joseph Javier Sánchez Acuña

发布于 2026-06-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Joseph Javier Sánchez Acuña

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是哥伦比亚一家物流公司的经理。你在一个叫作布加达尔拉圭哈拉迪亚莱古查尔德拉（Guadalajara de Buga）的小镇有一个中央仓库，你需要从全国各地分散的 30 个不同地点收集包裹——从沿海港口到山城。你拥有一支由 10 辆完全相同的卡车组成的车队，每辆卡车的官方额定载重量为 150 件包裹。

然而，你的公司有一个聪明的规则：如果数学计算得非常完美，一辆卡车可以多装一点——最多增加 5%（约 157 件包裹）——而不会违反法律或损坏卡车。这就是你的“弹性容量”。

问题在于，你目前的路线规划系统（名为“Rout Now”）有点死板。它的工作方式就像老师根据学生在教室里坐得有多近来分组一样（使用直线地图）。一旦分组完成，它就会派出一辆卡车去取货。因为它根据“直线”而不是“实际道路”来分组，所以经常导致有些卡车半空，而有些则超载，迫使你即使明明只需要 8 辆车时也必须动用全部 10 辆车。

新的解决方案：“蚁群”方法

作者约瑟夫·哈维尔·桑切斯·阿库尼亚（Joseph Javier Sánchez Acuña）利用一种受蚂蚁寻找食物启发而产生的计算机程序，测试了一种更智能的新方法。这被称为蚁群优化算法（Ant Colony Optimisation, ACO）。

以下是论文如何使用简单的概念来解释这种差异的：

1. “直线”与“实际道路”

旧方法（Rout Now）： 想象一下，你试图通过在纸上画直线来规划公路旅行。你可能认为两个城镇在地图上很近。但实际上，要从一个地方到达另一个地方，你可能必须翻越一座大山或绕行很长的路。旧系统忽略了实际的道路，只是根据平面地图上的位置进行分组。
新方法（蚂蚁）： 新系统观察的是实际的道路网络（使用名为 OpenStreetMap 的数字地图）。它知道在地图上看似“最近”的城镇，在实际道路交通中可能是最难到达的。

2. “打包”类比

旧方法： 旧系统尝试通过先抓取最近的邻居来填满卡车。这就像试图通过把最近的东西扔进手提箱而不看手提箱形状来打包一样。你最后会留下缝隙和浪费的空间，因此即使第一个手提箱还有空间，你也需要打开第二个手提箱（第二辆卡车）。
新方法： 蚁群算法就像一位打包大师。它不仅仅是抓取最近的东西；它会观察整个手提箱。它会问：“如果我把这个重箱子放在这里，我还能把那个轻一点的箱子放进去吗？”它非常谨慎地使用“弹性容量”（额外的 5% 空间）。它逐站构建路线，并不断检查卡车是否快满了。如果一辆卡车快满了，但仍有足够的空间再多跑一站，蚂蚁就会接下这一站。如果不行，它就会关闭这辆卡车并开始新的一辆。

3. 结果：更高效的装载

作者使用真实数据，针对 10 个不同的繁忙日期，将这种新系统与旧系统进行了对比。以下是发生的情况，特别是在最繁忙的一天（场景 S-3）：

更少的卡车： 旧系统使用了全部 10 辆卡车。新的蚁群系统仅需 8 辆卡车。这意味着车队需求减少了 20%。
更少的行驶距离： 卡车的行驶距离减少了 20%（节省了约 2,232 公里）。
节省的资金： 因为行驶距离更短且使用的卡车更少，燃油成本下降了 16%。
更满的卡车： 旧系统留下的卡车运行效率约为 79%（有很多空余空间）。新系统将其填满至 99.5%，这意味着几乎利用了卡车的每一寸空间。

4. 为什么有效（“秘诀”）

论文认为，这种神奇之处不仅仅在于新系统在一般意义上更“聪明”。其魔力在于它被允许以一种协调的方式使用弹性容量（额外的 5% 空间）。

旧系统无法做到这一点，因为它在开始规划路线之前，就已经根据地理位置锁定了卡车的特定分组。这就像是在粉刷墙壁之后才试图重新布置房间里的家具；分组是固定的。然而，蚁群系统在构建路线的同时也在构建分组。它可以说：“这辆卡车满了，但如果我挤进这一个额外的站点并使用 5% 的额外空间，我可以省下一整辆卡车。”

核心结论

这项研究证明，对于一个拥有复杂道路（如哥伦比亚的山区）的物流公司来说，使用一种尊重实际道路距离并使用弹性装载规则的仿生计算机程序（蚁群优化算法），要比使用基于直线距离的分组旧方法要好得多。

作者得出结论，这不仅仅是运气好；该结果针对每个场景都进行了 20 次测试，并证明了其统计学上的显著性。新方法节省了资金、节省了燃料并减少了所需的卡车数量，而这一切都是通过更智能地打包“手提箱”（卡车）实现的。

技术摘要：一种针对带容量限制车辆路径问题的元启发式算法解决方案

1. 问题定义与背景
本研究针对一个源自哥伦比亚入境原材料收集业务的现实世界带容量限制车辆路径问题（CVRP）进行探讨。该物流网络由位于布加德拉古达亚莱（瓦列德尔考卡）的一个中央仓库组成，为分布在哥伦比亚不同地区（海岸、安第斯高地和工业区）的 30 个配送中心提供服务。该业务面临着波动的需求周期（每个周期 643 至 1,192 件包裹），并使用 10 辆同质化的 Foton FRR Cummins 卡车车队。

一个关键的运营约束是灵活容量政策：虽然名义车辆容量为 $Q = 150$ 件包裹，但公司政策允许受控的 5% 超载，从而确立了有效规划容量 $Q_{eff} = 157.5$ 件包裹。路径规划必须基于源自 OpenStreetMap（通过 OSMnx）的非欧几里得路网进行，其中拓扑复杂性（山地走廊、单行道）导致实际行驶成本与欧几里得距离之间存在显著的不对称性。

现有的规划系统“Rout Now”采用“先聚类，后路径”的架构：它利用 k-means（基于平面坐标）将节点划分为 10 个地理集群，然后使用模拟退火算法（SA）独立对每个集群进行排序。这种方法导致了车队利用率的异质性（35%–90%），并且即使在理论下界表明仅需 6–8 辆车的情况下，也会系统性地部署全部 10 辆车。

2. 研究方法
本研究提出并评估了一种**蚁群优化（ACO）**元启发式算法，旨在直接在活跃节点的完全图中运行，而不进行预先的地理划分。

数学建模： 该问题被建模为一个混合整数线性规划（MILP）问题，使用 Miller–Tucker–Zemlin (MTZ) 公式进行子回路消除。容量约束被明确放宽至 $Q_{eff} = 157.5$ ，以在优化逻辑中模拟超载政策。
ACO 架构：
- 构建阶段： 蚂蚁迭代地构建多车辆路径。其核心差异在于动态掩码机制：可行下一节点的集合 ( $F_k$ ) 会进行实时过滤，以确保累积载荷不超过 $Q_{eff}$ 。这使得算法能够“高效装载”节点，仅在避免开启新路径时才利用这 5% 的裕量。
- 转移概率： 选择节点的概率取决于信息素轨迹 ( $\tau$ ) 和启发式可见度 ( $\eta = 1/C_{ij}$ )。鉴于哥伦比亚道路成本的高变异性（相对于均值的标准差为 47%），启发式权重 ( $\beta = 2.0$ ) 被校准为高于信息素权重 ( $\alpha = 1.0$ )，以优先考虑即时成本效率。
- 更新机制： 应用标准的挥发和沉积规则，强化那些有助于低成本、高整合方案的弧段。
实验设计：
- 场景： 从真实公司数据中提取了十个不同的运营场景（S-1 至 S-10），代表了一个完整的月度规划周期。
- 重复实验： 每个场景使用不同的随机种子独立执行 20 次，以隔离随机方差。
- 基准对比： 使用相同的 OSMnx 距离矩阵将 ACO 结果与基准方案（k-means + SA）进行对比，以确保内部有效性。
- 统计验证： 对每个场景 20 次运行的平均总距离应用了非参数 Wilcoxon 符号秩检验，以测试统计显著性。

3. 关键结果
ACO 方法在所有十个场景中均表现出优于基准方案的系统性且具有统计学意义的改进：

车队缩减： 在最高需求场景（S-3；1,192 件包裹）下，ACO 将活跃车队从 10 辆车（基准）减少到 8 辆车，达到了理论下界 ( $\lceil 1192/157.5 \rceil = 8$ )。在所有场景中，活跃车队减少了约 20%。
距离与成本：
- 总距离： 平均减少了 20.05%（范围在 19.97% 至 20.25% 之间）。在 S-3 场景中，距离从 11,023 公里降至 8,790.5 公里。
- 燃油成本： 在关键场景中估计节省了 16.05%（每个周期约 941,340 COP）。
- 运营时间： 减少了 20.02%。
容量利用率： ACO 实现了近乎完美的整合，将平均容量利用率从基准的 ~79.47% 提升至 S-3 中的 99.50%。ACO 方案中的路径在名义容量的 96% 至 101% 之间运行，特定路径通过利用 5% 的超载裕量来防止需要第九辆车。
统计显著性： Wilcoxon 符号秩检验得出统计量 $W=0$ （所有差异均有利于 ACO）且 p 值 $< 0.01$ ，拒绝了中位数相等的原假设，证实了改进的稳健性。

4. 意义与贡献
本文声称了三个主要的科学贡献：

灵活约束的实证评估： 本研究记录了在构造性元启发式算法中显式建模灵活容量约束 ( $Q_{eff}$ ) 如何实现协调的载荷整合，而这种整合在预分区架构中是结构性不可能实现的。研究表明，5% 的容差不仅是一个安全缓冲，而且是管理动态化时实现车队缩减的战略杠杆。
现实拓扑结构的稳健性： 研究证明，在复杂的非欧几里得路网中，生物启发式元启发式算法（特别是 ACO）优于经典的“先聚类，后路径”启发式算法。研究强调，地理预分区（k-means）未能考虑到道路网络的不对称性，而 ACO 则是在真实的成本空间内运行。
因果机制识别： 本文将“动态掩码”不可行节点作为成功的因果机制。这使得算法能够执行“高效装载”需求，有机地利用超载裕量以最小化路径数量，而这种能力在基准方案的固定地理集群中是不存在的。

5. 局限性与未来工作
作者指出，由于本研究局限于特定的工业背景，未考虑时间窗（VRPTW）或驾驶员时长约束。提出的未来研究方向包括：

将模型扩展至 VRPTW 以纳入接收时间表。
通过随机 VRP (SVRP) 处理需求不确定性。
使用进化算法开发多目标公式（例如，最小化二氧化碳排放量）。
将 ACO 核心作为微服务集成到现有物流系统中，用于受控的 A/B 测试。