💻 computer science

A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem

本文介绍了 ILS+SP，这是一种将迭代局部搜索（Iterated Local Search）与集合划分（Set Partitioning）后优化相结合的混合元启发式算法，该算法通过在解决大规模基准实例时获得近优解，显著优于现有的最先进方法，从而解决了家庭容量车辆路径问题（Family Capacitated Vehicle Routing Problem）。

原作者： Bruno Oliveira, Diogo Lima, Marcos Roboredo

发布于 2026-07-02

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Bruno Oliveira, Diogo Lima, Marcos Roboredo

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

想象一下，你是某家快递公司的经理。你拥有一支由完全相同的卡车组成的车队，所有卡车都从一个中央仓库出发。你的任务是向各种客户交付包裹。

但这里有一个转折：你的客户不仅仅是个人，他们被组织成了家庭。例如，“史密斯一家”在不同的街道上有五处房屋，但你的合同只要求你配送其中两处房屋。 “加西亚一家”有三处房屋，但你只需要访问其中的一处。

这就是家庭容量限制车辆路径问题 (F-CVRP)。这是一个包含两个主要规则的大型谜题：

家庭规则： 你必须访问每个家庭要求的确切房屋数量，但你可以选择访问哪些具体的房屋。
卡车规则： 每辆卡车都有重量限制（容量）。你不能超载。

目标很简单：找到最便宜的方式来驾驶所有卡车，在满足这些规则的同时，既不耗尽汽油也不超时。

问题所在：它太难完美解决了

随着家庭和房屋数量的增加，可能存在的路径数量变得如此庞大，以至于即使是世界上最快的超级计算机也需要花费数年时间才能找到“完美”的答案。这就是为什么作者 Bruno、Diogo 和 Marcos 创建了一个“智能猜想者”（元启发式算法）来快速找到一个“非常出色”的答案。

他们将他们的解决方案称为 ILS+SP。让我们用烹饪类比来拆解它。

配方：ILS+SP

1. “迭代局部搜索” (ILS) —— 品尝味道的厨师

想象一位正在完善汤品配方的厨师。

开始： 厨师制作了一份基础汤品（初始解）。
味觉测试（局部搜索）： 厨师品尝并进行微调：“也许可以多加一点盐？”或者“把胡萝卜换成土豆？”他们不断进行这些微小的改变以改善风味。
“模拟退火”转折： 有时，某种改变会让汤的味道暂时变差。普通的厨师会立即拒绝它。但这位厨师使用了一条特殊的规则（模拟退火）：如果汤只是稍微变差了，他们可能会接受它。为什么要这样做？因为有时你必须让汤的味道暂时变得“不对劲”，才能发现之后全新的、惊人的风味。这有助于他们跳出那些由于陷入平庸配方而无法自拔的“糟糕区域”。
“摇晃”过程（扰动）： 如果厨师陷入了无法带来改进的小规模微调循环中，他们会做一些激进的操作：他们倒掉一半的汤，然后用一种全新的食材组合重新开始。这被称为“扰动”。这迫使搜索过程去寻找厨房里完全不同的新领域。

作者在厨师的工具箱里加入了一个特别的配料：MemberRelocate（成员重定位）。由于这是一个“家庭”问题，厨师不仅是在交换食材，他们还在交换“家庭成员”。如果他们正在访问史密斯家的 1 号房，他们可能会问：“等等，2 号房更近。让我们把 1 号房换成 2 号房，看看是否能节省时间。”

2. “集合划分” (SP) —— 大师级编辑

在厨师经过数小时的微调、摇晃和品尝后，他们拥有了一本厚厚的笔记本，记录了沿途尝试过的各种汤品变化（路径）。

集合划分这一步就像是一位大师级的编辑，他审视着那本完整的笔记。编辑并不负责烹饪，他只负责挑选和组合。他观察厨师在一天中制作出的所有优秀的“汤品块”，并问道：“如果我把上午 10 点的这条特定路径与下午 2 点的那条路径结合起来，我能否做出一顿完美的餐点？”

这最后一步确保了即使厨师在烹饪过程中错过了完美的组合，编辑也能通过数学方法，从全天的成果中组装出最好的部分。

结果：奏效了吗？

作者将他们的 “ILS+SP” 配方与世界上现有的最佳方法进行了对比测试。

测试： 他们使用了 144 个大型且困难的谜题（拥有超过 50 个客户），这些谜题此前已被其他研究人员尝试解决过。
得分： 他们的算法在每一个实例上都取得了领先或并列第一。
改进： 在这篇论文发表之前，最佳方法的平均误差约为 1.84%。作者的方法将这个差距缩小到了 0.01%。在物流领域，这就像是从“略微偏离目标”进化到了“几乎每次都能射中靶心”。
速度： 他们还测试了规模更大的谜题（高达 142 个客户）。他们的算法平均在约 37 秒内就能找到极佳的解决方案。

总结

本文提出了一种新的混合方法，用于解决一个复杂的配送路径问题，即在必须选择访问哪些家庭成员的情况下进行调度。通过将一个会进行智能且有时带有风险的小幅调整的“品尝厨师”，与一个能组装全天最佳部分的“大师级编辑”相结合，他们创造了一个比以往针对该特定问题发表的任何工具都更快、更准确的工具。

技术摘要：一种用于家庭容量车辆路径问题的混合元启发式算法

问题定义

本文研究的是家庭容量车辆路径问题（F-CVRP），它是家庭旅行商问题（FTSP）和经典容量车辆路径问题（CVRP）的一种推广。在 F-CVRP 中，一支由 $K$ 辆容量为 $Q$ 的同质车队组成，从单个仓库出发，为划分成不同“家庭”的客户提供服务。与每个客户都必须被访问的标准 CVRP 不同，F-CVP 要求访问每个家庭 $l$ 中的特定数量成员（ $v_l$ ），而该家庭的其他成员可以不被访问。其目标是在遵守车辆容量限制并满足每个家庭精确访问需求的同时，最小化总路径成本。

随着问题规模的扩大，精确解法在计算上变得难以承受。因此，本文的研究重点是开发一种快速、高质量的启发式算法，能够在紧凑的时间预算内交付解，既可作为独立的求解器，也可作为精确框架中原始界的提供者。

方法论：ILS+SP 混合元启发式算法

作者提出了 ILS+SP，这是一种结合了迭代局部搜索（ILS）框架与集合划分（SP）后优化阶段的混合元启发式算法。该算法运行如下：

1. 迭代局部搜索 (ILS) 核心

搜索由一个维护路径池（ $P$ ）并追踪已找到的最佳可行解（ $s^*$ ）的 ILS 框架驱动。

初始解： 通过最佳并行插入（BPI）启发式算法生成，通过迭代插入客户以最小化成本增量来构建 $K$ 条路径，同时确保满足家庭访问计数。
局部搜索 (RVND)： 局部搜索采用**随机变量领域下降（RVND）**策略。它探索一个包含九个领域的组合：
- 路径间（5个）： 交换(1,1)、交换(2,1)、交换(2,2)、移动(1,0)、移动(2,0)。
- 路径内（3个）： 交换（Exchange）、重插入（Reinsertion）、Or-opt2。
- 专用领域（1个）： 成员重定位（MemberRelocate），这是一个针对特定问题的算子，它移除一个已被访问的客户，并将同一家庭中未被访问的成员插入到所有路径中的最佳位置。
- 所有领域均保持家庭访问计数和活跃路径数量（ $K$ ）的结构约束。
接受准则： 与标准的局部搜索不同，该算法根据基于时间驱动的模拟退火（SA）冷却机制接受恶化移动。这使得搜索能够跳出局部最优。
扰动： 为了增加搜索的多样性，算法在重新进入局部搜索之前，会对当前解应用三种随机扰动之一（随机交换、随机移动或随机成员重定位）。
惩罚处理： 容量违规通过目标函数中的动态惩罚系数（ $\theta$ ）进行处理，该系数根据当前解的可行性进行调整，以引导搜索向可行区域靠拢。

2. 集合划分 (SP) 后优化

在耗尽时间预算后，算法执行最终的优化步骤。它在整个搜索过程中收集到的容量可行路径池（ $P$ ）之上，构建一个集合划分问题。

SP 模型选择一组路径，以最小化总成本，同时满足家庭访问要求并恰好使用 $K$ 条路径。
由于路径池 $P$ 包含了构成当前最佳解 $s^*$ 的路径，因此 SP 的最优解至少与 $s^*$ 一样好。

核心贡献

本文强调了四个主要贡献，这些贡献使本研究区别于现有的最先进技术（特别是 Bernardino 和 Paias 在 2024 年提出的 ILS）：

与集合划分的混合化： 引入了 SP 后优化阶段来重新优化路径池，这是一个在以往方法中缺失的数学启发式（matheuristic）组件。
增强型局部搜索： 实现了 MemberRelocate 领域，该领域能将未被访问的家庭成员最优地插入到所有路径中的最佳位置，而非仅仅是在原位进行交换。
随机化领域探索： 使用 RVND 来随机化领域探索的顺序，与先前文献中使用的固定顺序形成对比。
模拟退火接受机制： 采用了 SA 准则来接受较差的解，取代了以往方法中严格的仅限改进的接受机制，从而改善了强化搜索（intensification）与多样化搜索（diversification）之间的平衡。

计算结果

作者在两个基准测试集上评估了 ILS+SP：

标准基准（144 个实例）： 衍生自 Augerat 等人（1995）的集合，包含超过 50 个客户的实例。
- 性能： 该方法在每一个实例上都击败或并列第一，其对手是 Bernardino 和 Paias（2024）的最先进启发式算法。
- 差距缩减： 与最佳已知解（BKS）的平均差距从之前的 1.84% 降低到了 0.01%。
可扩展性基准（120 个实例）： 一个新的较大规模实例集（最多 142 个客户），衍生自 CVRP Set X (Uchoa 等人, 2017)。
- 性能： 该算法实现了 0.47% 的平均差距，平均运行时间为 37 秒，展示了对更大问题规模的可扩展性。

意义与主张

本文将 ILS+SP 定位为 F-CVRP 的一种鲁棒且可扩展的解决方案。作者声称，通过将具有特定问题领域和 SA 接受机制的复杂 ILS 框架与数学启发式后优化（SP）相结合，该方法显著优于现有的启发式算法。结果表明，该方法不仅能够匹配或改进既定基准的最优解，而且能有效地扩展到更大、更复杂的问题实例，使其成为独立应用及集成到精确求解框架中的有力工具。