COAgents：用于学习和导航路径规划问题搜索空间的多智能体框架

# COAgents: 多智能体框架用于学习和导航路径规划问题的搜索空间
来源：https://arxiv.org/html/2605.20618
11institutetext:华为技术加拿大公司，4321 Still Creek Dr, 本拿比, BC, 加拿大 V5C 6S722institutetext:华为技术有限公司，中国Mahdi MostajabdavehCheikh AhmedAbdullah Ali SivasXiaorui LiZirui ZhouMao Kun

###### 摘要

尽管车辆路径问题（VRP）对许多现实系统至关重要，但由于其组合复杂度，在大规模场景下仍然难以在计算上得到解决。传统启发式方法依赖手工制定的规则进行局部改进，并偶尔通过跳跃来逃离局部最优，但往往难以在不同实例间泛化。我们提出了COAgents，一个合作式多智能体框架，将搜索过程建模为一个图：节点代表解，边对应局部优化或用于多样化的大规模扰动（即跳跃）。部分搜索图（PSG）在搜索过程中动态构建，使COAgents能够训练一个节点选择智能体和一个移动选择智能体来引导强化搜索，并训练一个跳跃智能体来触发对新区域及时探索。与端到端学习方法不同，COAgents将独立于问题的搜索控制与紧凑的领域特定编码清晰分离，从而便于在不同任务间自适应。在CVRP和VRPTW基准测试上的大量实验表明，COAgents在CVRP上可与若干学习搜索基线方法竞争，在更具挑战性的VRPTW实例上，相较于最强的神经求解器（POMO），将最优已知解的差距缩小了14%（N=100时）和44%（N=50时），相较于ALNS则分别缩小了21%和40%，从而在学习方法中达到了新的最优水平。

代码可在 https://github.com/mahdims/COAgents 获取。

## 1 引言

组合优化问题是金融、电子商务、物流和制造等许多现实世界决策场景的核心[27 (https://arxiv.org/html/2605.20618#bib.bib59)]。尽管通用求解器取得了突破，但这些问题固有的离散性质意味着即使是当前最优的求解器，在实际规模的实例上也常常表现不足，尤其是在现实世界的大规模物流和路径规划应用中[26 (https://arxiv.org/html/2605.20618#bib.bib63)]。因此，我们迫切需要能够在有限计算时间内产生高质量解的快速、可靠的启发式方法。许多车辆路径问题（VRP）的变体为原型开发和测试此类运筹方法提供了一个坚实且多样化的试验场。

许多用于VRP的传统启发式方法基于迭代局部搜索：每一步，它们 (i) 选择当前解，(ii) 应用一个或多个邻域移动，以及 (iii) 通过启发式规则接受或拒绝得到的解。为避免陷入停滞，VRP求解器通过增加多样化操作、随机化构造或进行能“跳跃”到新区域的大规模扰动来增强此过程。局部搜索算法反复回答三个核心问题：1) 哪个解将成为下一个当前解？2) 接下来应该应用哪个算子？3) 何时以及如何重定向搜索以逃离局部最优？

尽管这些经典方法取得了广泛成功，但它们依赖于针对每个决策手工定制的、针对特定问题的规则，需要大量的领域知识和代价高昂的试错调参[15 (https://arxiv.org/html/2605.20618#bib.bib13)]。即使是问题表述或输入数据的微小变化，也可能使调整后的参数失效，需要专家介入和全面的重新工程。此外，静态规则集无法从过去的搜索经验中积累或适应，也无法在线调整以适应不断变化的实例分布。这种脆弱性和维护负担促使我们转向COAgents框架，在该框架中，学习型智能体取代固定启发式规则，提供自适应的、数据驱动的决策策略，只需最少的手工调整。

COAgents是一个通用的多智能体框架，利用搜索历史通过三个学习型智能体来编排局部改进启发式：节点选择智能体（NSA）、移动选择智能体（MSA）和跳跃智能体（JA）。它们在一个部分搜索图（PSG）上运行。PSG是整个搜索空间中已访问的子图，节点代表已探索的解，边代表移动或跳跃，从而编码了搜索历史。从初始解开始，NSA选择一个候选节点，MSA预测最有前景的改进启发式方法，驱动局部探索。当重复的失败尝试表明陷入停滞时，JA基于搜索历史从头生成一个新解，将搜索引导到之前未探索或不可达的区域。这种跳跃变换不是标准的算子，而是一种学习到的重启方式，用于逃离局部最优，并从一个新起点重新开始下坡搜索。控制权随后返回给NSA和MSA，以进行新一轮局部搜索。图1 (https://arxiv.org/html/2605.20618#S1.F1) 描绘了这一顶层循环：NSA、MSA、移动应用、PSG更新以及JA的条件调用。该循环一直执行，直到计算预算（例如，时间限制或已探索节点数）耗尽。

参考图注图 1：COAgents 定义了我们的三个智能体如何协作编排搜索。

##### 贡献

COAgents是第一个通过部分搜索图上的协作决策来建模和学习VRP组合搜索空间的多智能体框架。我们的主要贡献如下： (1) 新颖的学习型智能体。我们引入了两个新智能体——节点选择智能体（优先搜索有前景区域）和跳跃智能体（预测学习到的重启以逃离停滞），以及一个学习型移动选择智能体，共同取代手工制定的规则。 (2) 统一的、权重共享的架构。智能体共享一个共同的神经骨干网络，从而实现数据高效的训练、易于迁移到新问题变体，并减少专家调参。 (3) 部分搜索图表示。我们将PSG形式化为一种通用的、历史感知的状态编码，驱动智能体决策。 (4) 求解器与问题自适应框架。COAgents可包裹现有局部搜索例程和神经求解器，通过自适应决策策略增强它们，从而无缝适应不同的VRP问题变体。实验表明，COAgents在VRPTW上达到了学习方法中的新最优水平，相较于最强的神经基线方法，将最优已知解的差距缩小了多达44%。

## 2 相关工作

超启发式是自动化选择或生成启发式方法以解决组合问题的方法，最早于20世纪90年代提出[6 (https://arxiv.org/html/2605.20618#bib.bib10)]。由于能够减少开发开销以及机器学习方面的进展，对超启发式的兴趣与日俱增[7 (https://arxiv.org/html/2605.20618#bib.bib11)]。它们大致分为选择型和生成型两类[2 (https://arxiv.org/html/2605.20618#bib.bib12)]。选择型超启发式从一组低级启发式中选择应用于当前解，然后决定是否接受新解[31 (https://arxiv.org/html/2605.20618#bib.bib61)]。相反，生成型超启发式通过组合构建模块或在现有启发式中识别模式来创建新的启发式[37 (https://arxiv.org/html/2605.20618#bib.bib60)]。COAgents与这些方法不同，因为它是一个多智能体框架，不仅选择启发式方法，还做出关于解选择和多样化跳跃的决策。

学习搜索方法。[23 (https://arxiv.org/html/2605.20618#bib.bib14)]引入了用于VRP的学习搜索（L2S）框架，该框架通过强化学习（RL）控制器选择定制化算子，迭代改进初始解。[3 (https://arxiv.org/html/2605.20618#bib.bib15)]在此基础上提出了深度RL方法，迭代修改局部解组件直至收敛，成功解决了诸如容量约束车辆路径问题（CVRP）、调度和旅行商问题（TSP）等。最近，[21 (https://arxiv.org/html/2605.20618#bib.bib8)]将超启发式中的算子选择表述为多臂老虎机（MAB）问题，利用汤普森采样和EXP3自适应处理对抗性和非平稳设置。这些在线MAB算法在运行时动态调整参数，并在带时间窗的车辆路径问题（VRPTW）上进行了测试。COAgents与这些方法有根本不同，它超越了算子选择。它引入了一个多智能体框架，同时决定扩展哪个解、应用哪个算子以及何时何地进行多样化，并显式地将搜索空间建模为图以提供更丰富的上下文。

ALNS算子选择。最近的研究应用深度强化学习（DRL）来改进自适应大邻域搜索（ALNS）中的算子选择。[11 (https://arxiv.org/html/2605.20618#bib.bib55)]和[14 (https://arxiv.org/html/2605.20618#bib.bib17)]使用了多层感知机架构，仅依赖高层搜索特征（例如，迭代次数、温度和最优性差距），忽略了特定于解的细节。这种省略可能会限制算子选择的效果。为了解决这个问题，[13 (https://arxiv.org/html/2605.20618#bib.bib16)]使用图神经网络（GNN）嵌入当前解图，从大型池（28个破坏算子和7个修复算子）中指导算子选择，在五个路径规划问题上取得了持续改进。[30 (https://arxiv.org/html/2605.20618#bib.bib18)]在此基础上引入了DR-ALNS，这是一个联合学习算子选择并动态调整算法参数的DRL框架。在定向运动问题上的评估表明，DR-ALNS优于传统和贝叶斯调参的ALNS[22 (https://arxiv.org/html/2605.20618#bib.bib62)]。与这些方法不同，COAgents将整个搜索轨迹显式建模为PSG，从而为其解选择、算子选择和跳跃智能体提供更丰富的上下文。

## 3 问题陈述

我们将VRP变体的一种组合解空间定义为有向图 \(G^{CO}_P(\mathcal{S}, E)\)，其中每个节点 \(s \in \mathcal{S}\) 代表问题 \(P\) 的一个不同解，\(E\) 是问题 \(P\) 的邻域移动集合。如果存在一个移动将 \(s^i\) 转换为 \(s^j\)，则边 \(e_{ij} \in E\) 连接两个节点 \(s^i\) 和 \(s^j\)。对应于一条边的移动示例是旅行商（子）问题的 2-opt 启发式。

问题 \(P\) 的任何全局最优解 \(s^*\) 都是图 \(G^{CO}_P(\mathcal{S}, E)\) 中的一个节点。然而，不能保证任意解 \(s\) 能通过一序列移动转换为 \(s^*\)。等价地说，\(G^{CO}_P(\mathcal{S}, E)\) 可能是一个不连通的图。此外，对于每个局部最优解 \(s^*_i\)，存在一个诱导子图 \(G^{CO}_P(s^*_i; \mathcal{S}, E)\)，使得如果 \(s\) 是 \(G^{CO}_P(s^*_i; \mathcal{S}, E)\) 的一个节点，那么从 \(s\) 出发的移动序列很可能导向 \(s^*_i\)。我们将这些诱导子图称为吸引域。因此，图遍历是有偏的，即使存在通往全局最优的路径，邻域移动也可能导向局部最优。

在实际场景中，只有所有可能的移动的一个子集是可用的和/或廉价的。因此，我们引入搜索空间作为子图 \(G^{SS}_P(\mathcal{S}, E_{\mathcal{M}}) \subset G^{CO}_P(\mathcal{S}, E)\)，其中 \(\mathcal{M}\) 表示可用移动的集合，\(E_{\mathcal{M}}\) 是相应的边集合。从现在起，我们分别称这些空间为 \(G^{SS}\) 和 \(G^{CO}\)。请注意，\(G^{SS}\) 的边是 \(G^{CO}\) 边的子集，并且最优解 \(s^*\) 是 \(G^{SS}\) 中的一个节点。

现在，我们将寻找给定 VRP 问题 \(P\) 的最优解 \(s^* \in \mathcal{S}\) 的问题转化为：

- 找到一个边集合 \(E_J\)（不一定对应任何合法移动），使得 \(G^{SS}_P(\mathcal{M}; \mathcal{S}, E_{\mathcal{M}} \bigcup E_J)\) 是连通的，
- 并在图 \(G^{SS}_P(\mathcal{M}; \mathcal{S}, E_{\mathcal{M}} \bigcup E_J)\) 上找到初始解 \(s^{(0)} \in \mathcal{S}\) 与 \(s^* \in \mathcal{S}\) 之间的最短路径。

我们将集合 \(E_J\) 称为跳跃。注意跳跃不必改善目标值；因此，它们不受吸引域的影响。参见图̃3 (https://arxiv.org/html/2605.20618#S3.F3) 的说明。

由于空间和时间限制，无法显式表示 \(G^{SS}\)。相反，我们的目标是训练模型在推理过程中隐式构建搜索空间。我们通过构建一组部分搜索图并将其作为模型的额外输入来实现这一点。部分搜索图是整个搜索空间的一个已探索子空间。节点代表搜索过程中遇到的解。边代表移动或跳跃。因此，PSG捕获了搜索空间 \(G^{SS}\) 内的一条搜索轨迹，显示了已访问的空间部分及其连接方式。图̃3 (https://arxiv.org/html/2605.20618#S3.F3) 展示了 PSG 如何在迭代之间演变。

参考图注图 2：移动（黑色）和跳跃（橙色）在全局最优搜索中协同工作。
参考图注图 3：算法过程中 PSG 的演变。\(s\) 表示解，\(m\) 表示移动。

在本研究中，我们提出了一种方法，学习如何从先前经验中引导搜索空间的探索，以及如何在探索过程中生成跳跃。我们将使用 PSG 来识别解探索中的模式并指导进一步探索，通过专注于未探索或有前景的区域来提高搜索效率。我们将在方法部分讨论我们的方法。

## 4 求解方法：COAgents

COAgents 由三个智能体组成——NSA、MSA 和 JA，它们按图1 (https://arxiv.org/html/2605.20618#S1.F1) 所示进行交互。每个智能体都实现为基于图神经网络的策略，经过训练以最大化朝向最优解的长期进展。在本节中，我们将讨论这三个智能体的数据表示、模型架构和训练过程。

### 4.1 搜索历史数据表示

导航 VRPs 的非凸组合解空间是一项具有挑战性的任务。为了增强智能体对解空间的理解，整合关于问题、解和探索历史的信息至关重要。虽然问题和解编码天生是特定于问题的，但历史在组合优化问题的许多变体中表现出一致的结构。接下来，我们详细讨论与问题无关的探索历史表示。

##### 部分搜索图

所提出的框架建立在 PSG 数据结构之上，该结构表示搜索历史。如上所述，PSG 本质上是一个有向、不连通的图。PSG 中的每个节点对应组合优化问题的一个解 \(s_i\)，一个