💻 computer science

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

COAgents 引入了一种协作多智能体框架，将车辆路径问题搜索空间建模为动态构建的图，从而将问题无关的搜索控制与领域特定编码分离开来，通过在 VRPTW 基准测试中显著缩小与已知最优解的差距，在基于学习的方法中实现了最先进的性能。

原作者： Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

发布于 2026-05-21

📖 1 分钟阅读☕ 轻松阅读

原作者： Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

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

想象你是一名物流经理，正试图找出让一车队送货卡车访问 100 个不同房屋的最有效方式。这是一个经典的“车辆路径问题”。但难点在于：可能的路线数量如此庞大，以至于即使最快的超级计算机也无法穷尽所有检查。这就像试图在一个巨大且雾气弥漫的迷宫中找到唯一最佳路径，而你走的每一步都可能通向死胡同。

几十年来，人类通过编写严格的规则手册来解决这个问题：“如果你看到左边有房屋，就向右转。”但这些规则手册非常脆弱。如果城市布局发生轻微变化，规则就会失效，专家不得不花费数周时间重新编写它们。

现在，华为研究人员创造了一个新系统——COAgents。它不再依赖僵化的规则手册，而是使用由三名"AI 侦探”组成的团队，共同探索迷宫、从错误中学习，并找到比以往更好的路径。

以下是其工作原理，采用简单的类比说明：

1. 迷宫的地图：“部分搜索图”

想象 AI 不仅仅查看当前路线，而是在绘制它曾经尝试过的每一条路径的地图。

节点（那些点）： 地图上的每个点代表 AI 测试过的一个具体配送路线。
边（那些线）： 连接点的线条显示 AI 如何从一个路线过渡到下一个（例如：“我们交换了路线上的两个房屋”）。
“部分”的含义： AI 无法绘制整个无限迷宫，因此它只保留迄今为止访问过的有趣部分的“部分”地图。这张地图是团队的共享记忆。

2. 三个 AI 智能体

魔法之所以发生，是因为三个不同的 AI 智能体查看这张地图并做出不同的决策，就像一支拥有特定角色的运动队：

侦察兵（节点选择智能体）：
- 角色： “我们接下来应该查看哪条路线？”
- 类比： 想象你在一座拥有数千本书的图书馆里。侦察兵不会随机挑选一本书。它会查看你的“阅读历史”（即地图），然后说：“嘿，那边那条路线看起来很有希望；它接近一个优质解。让我们专注于那条路线。”这防止团队在死胡同上浪费时间。
机械师（移动选择智能体）：
- 角色： “我们如何改进这条特定路线？”
- 类比： 一旦侦察兵选定一条路线，机械师便介入。它拥有一个包含各种技巧的工具箱（例如交换两个停靠点或重新排序一条街道）。它查看当前路线并说：“如果我们交换这两个房屋，卡车将节省 5 分钟。让我们这样做吧！”它是擅长进行微小局部改进的专家。
探索者（跳跃智能体）：
- 角色： “我们陷入困境了！让我们尝试一些全新的东西。”
- 类比： 有时，侦察兵和机械师会陷入循环，做出微小的改进却无实际帮助。他们被困在一个“局部低谷”中。探索者则是那个会说“忘掉这条路径吧。让我们跳到地图上一个完全不同的区域”的智能体。它基于从过去学到的知识，从头生成一条全新路线，帮助团队摆脱陷阱，找到更好的低谷。

3. 它们如何协同工作

整个过程是一个连续循环：

侦察兵从历史地图中选择一条路线。
机械师尝试微调它以使其更好。
如果他们不断微调却未能取得显著改善，探索者就会介入，创建一条新路线，并将其添加到地图中。
团队重复此过程，直到时间耗尽。

为何这意义重大

该论文声称，这种基于团队的方法是一个游戏规则改变者，尤其对于像VRPTW（车辆路径问题带时间窗，即卡车有严格的时间窗口，例如“必须在下午 2:00 至 2:30 之间到达”）这样的难题而言。

超越最佳表现： 在这些高难度测试中，COAgents 以显著优势击败了此前最佳的 AI 求解器。例如，在 100 个停靠点的情况下，与之前最强的 AI 相比，它将与完美解的差距缩小了14%；与另一种顶级方法相比，差距缩小了44%。
学习而非规则： 与依赖人工编写规则的旧方法不同，COAgents 学会如何搜索。它不需要人类告诉它如何解决特定问题；它通过观察自身历史来找出最佳策略。
适应性： 由于“大脑”（智能体）与“游戏规则”（具体城市布局）是分离的，你可以轻松更换游戏规则（例如，从送货卡车改为无人机配送），而无需重建整个 AI。

权衡取舍

该论文诚实地指出了其中一个缺点：速度。
由于 COAgents 不断绘制其地图、检查历史并运行三个不同的智能体，其运行时间比某些更简单、更快的方法要长，后者只需构建一次路线即停止。然而，作者认为，对于最困难的问题，当找到最佳解决方案比速度更重要时，这额外的时间是值得的。

总之： COAgents 就像一个聪明、协作的探险家团队，他们详细记录自己的旅程。他们不再盲目猜测或遵循静态规则手册，而是利用共享历史来知道何时深入挖掘、何时调整路径、何时向新领域迈出巨大飞跃，最终找到比以往任何人都更好的解决方案。

技术摘要：COAgents——用于路由问题的多智能体框架

问题陈述

车辆路径问题（VRPs），包括带容量限制的车辆路径问题（CVRP）和带时间窗的车辆路径问题（VRPTW），是物流和制造业的核心，但由于其组合复杂性，在大规模场景下仍属于计算上不可行的问题。传统的启发式方法依赖于手工设计的规则进行局部改进和多样化（跳跃）以逃离局部最优解。然而，这些静态规则集往往缺乏对不同实例的泛化能力，需要大量的领域专业知识进行调整，且无法适应不断演变的问题分布。虽然“学习搜索”（L2S）方法已经出现，但许多方法仅关注算子选择或当前状态决策，未能有效建模搜索历史或更广泛的搜索空间结构。

方法论：COAgents 框架

作者提出了COAgents，这是一个将 VRP 搜索过程建模为图遍历的协作多智能体框架。其核心创新是部分搜索图（PSG），这是一个动态构建的子图，其中节点代表已探索的解，边代表局部移动或大幅扰动（跳跃）。

1. 部分搜索图（PSG）

PSG 充当一种具有历史感知能力的状态编码。它是一个有向、不连通的图，其中：

节点： 代表搜索过程中遇到的各个解。
边：代表邻域移动（局部细化）或跳跃（大幅扰动）。
结构： 该图分解为连通分量（样本），每个分量探索一个局部最优解的邻域。这种结构使系统能够追踪搜索轨迹并识别探索模式。

2. 多智能体架构

COAgents 采用三个在 PSG 上运行的学习智能体，它们共享一个由门控图卷积网络（GGCN）和 Transformer 组成的通用神经骨干：

节点选择智能体（NSA）： 从 PSG 中选择一个候选解（节点）作为下一步局部搜索的当前最优解。它根据历史数据优先考虑搜索空间中具有潜力的区域。
移动选择智能体（MSA）： 预测对选定解应用的最有希望的邻域算子（移动），以推动局部强化。
跳跃智能体（JA）： 当搜索停滞（表现为重复尝试失败）时触发，该智能体基于搜索历史从头生成一个全新的解。与标准算子不同，跳跃智能体执行一种学习到的重启操作，以逃离局部最优解并将搜索引导至未探索的区域。

3. 模型架构与训练

编码： 解被编码为节点特征（ $u_i$ ），捕捉全局属性（目标值、可行性）和内部结构矩阵（ $V_i$ ）。位置嵌入通过 PSG 结构的随机游走编码器和解拓扑的特定问题编码器导出。
核心模块： 网络使用交错的 GGCN 层来捕捉 PSG 内的局部结构模式，并使用 Transformer 层来建模所有节点之间的长程依赖关系。特定问题的端到端（E2E）模块细化组合问题的内部结构。
训练：
- NSA 和 MSA： 联合训练为二分类任务，分别识别最接近最优解的解和最佳下一步移动，最小化联合二元交叉熵。
- 跳跃智能体： 单独训练以预测代表新解的随机邻接矩阵。它针对一组近优参考解进行训练，以减少标签歧义。
推理： 框架执行一个循环，其中 NSA 选择节点，MSA 选择移动，并更新 PSG。如果发生停滞，则调用 JA。此过程持续进行，直到达到计算预算（时间或节点限制）。

主要贡献

新颖的学习智能体： 引入了节点选择智能体和跳跃智能体，以及移动选择智能体。这些智能体共同取代了手工规则，实现了用于解选择、算子应用和多样化的自适应、数据驱动决策策略。
统一且权重共享的架构： 所有智能体共享通用的神经骨干，促进了数据高效的训练、对新问题变体的可迁移性，并减少了对专家调整的需求。
部分搜索图表示： 将 PSG 形式化为一种通用的、具有历史感知能力的状态编码，用于驱动智能体决策，使该方法区别于仅依赖当前状态的方法。
求解器与问题自适应框架： COAgents 封装了现有的局部搜索例程和神经求解器，通过自适应策略增强它们，使其能够无缝适应不同的 VRP 变体。

实验结果

该框架在 CVRP 和 VRPTW 基准上进行了评估，使用了 10,000 个训练实例和标准测试集（例如 1,000 个 VRPTW 实例）。

VRPTW 性能： COAgents 在基于学习的方法中树立了新的最先进水平。
- 相对于最强的神经求解器（POMO），它将最优性差距降低了 14%（在 N=100 时）和 44%（在 N=50 时）。
- 相对于自适应大邻域搜索（ALNS），它将差距降低了 21%（N=100）和 40%（N=50）。
- 在 VRPTW 测试集上，它优于所有神经基线、OR-Tools 和 ALNS。
CVRP 性能： COAgents 保持了与最先进“学习搜索”基线的竞争力，证明了即使使用紧凑的特定问题编码模块也是有效的。
消融研究： 移除跳跃智能体几乎使最优性差距翻倍（从 3.7% 增加到 7.8%），突显了其在逃离局部最优解中的关键作用。节点和移动选择智能体也对性能做出了显著贡献。
与 ALNS 的比较： 即使 ALNS 被允许访问更大规模的手工算子池（包括 27 个额外的破坏 - 修复对），COAgents 仍 consistently 优于它，验证了学习策略优于静态启发式方法。

意义与主张

本文声称，COAgents 代表了从静态手工启发式方法向从搜索历史中学习的自适应多智能体系统的重大转变。通过将搜索空间显式建模为图并利用部分搜索图，该框架使智能体能够做出关于强化和多样化的明智决策，这是传统方法无法实现的。

作者将 COAgents 定位为经典启发式方法和现有“学习构建/搜索”方法的有力替代方案，特别是对于像 VRPTW 这样泛化能力和适应性至关重要的复杂问题。虽然承认当前的 Python 实现比基于 C/C++ 的启发式方法（如 LKH3 和 HGS）更慢，且由于二次注意力成本，扩展到非常大的实例仍然是一个挑战，但该框架证明了学习到的、具有历史感知能力的搜索控制可以显著缩小路由问题中与已知最优解的差距。