用于多重图可扩展路由的两阶段学习分解

arXiv cs.LG 论文
vehicle-routing-problems multigraphs reinforcement-learning scalability neural-combinatorial-optimization graph-neural-networks

摘要

本文提出了节点-边策略分解（NEPF）方法，以解决多重图上车辆路径问题（VRP）的可扩展性难题。该方法结合了预编码边聚合与分层强化学习，在加快训练和推理速度的同时，实现了最先进的求解质量。

arXiv:2605.05389v1 公告类型：新文章 摘要：大多数用于车辆路径问题（VRP）的神经网络方法仅限于欧几里得环境或简单图。在本文中，我们转而考虑多重图，其中平行边代表具有不同权衡（例如距离与时间）的不同出行选项。针对此类公式设计的方法寥寥无几，且现有方法面临严重的可扩展性问题。我们通过节点-边策略分解（NEPF）方法缓解了这些可扩展性问题，该方法将路由策略分为节点排列阶段和边选择阶段。为了实现这种分解，我们引入了预编码边聚合方案和非自回归的边阶段架构，以及分层强化学习方法以联合训练这两个阶段。我们在六种VRP变体上的实验表明，NEPF在求解质量方面与当前最先进的方法持平或优于它们，同时在训练和推理速度上显著提升。
查看原文
查看缓存全文

缓存时间: 2026/05/08 07:14 

# 面向多图可扩展路由的两阶段学习分解
来源：https://arxiv.org/abs/2605.05389
查看 PDF (https://arxiv.org/pdf/2605.05389)

> 摘要：大多数针对车辆路径问题（VRP）的神经方法仅限于欧几里得设置或简单图。在本研究中，我们转而考虑多图，其中平行边代表具有不同权衡（例如，距离与时间）的不同旅行选择。为此类公式设计的现有方法寥寥无几，且存在的方法面临严重的可扩展性问题。我们通过节点-边策略分解（NEPF）方法缓解了这些可扩展性问题，该方法将路由策略分解为节点排列阶段和边选择阶段。为了实现这种分解，我们引入了预编码边聚合方案以及用于边阶段的非自回归架构，并采用分层强化学习方法联合训练这两个阶段。我们在六种 VRP 变体上的实验表明，NEPF 在解决方案质量上达到或优于最先进的方法，同时在训练和推理速度上显著更快。

## 提交历史

来自：Filip Rydin [查看邮件 (https://arxiv.org/show-email/4d4fdb48/2605.05389)] **\[v1\]** 2026 年 5 月 6 日，星期三 19:23:09 UTC (68 KB)

相似文章

表征优先于路由：克服多时间尺度PPO中的代理劫持

Hugging Face Daily Papers

本文指出了代理劫持和时间不确定性是多时间尺度强化学习中的失败模式，并提出了一种目标解耦架构，该架构从Actor中移除路由，利用Critic进行辅助表征学习。该方法消除了LunarLander-v2基准上的策略崩溃，并稳定地超越了'环境已解决'阈值，而无需超参数劫持。

GraphPO：面向推理模型的基于图策略优化

arXiv cs.CL

GraphPO 是一种新颖的基于图的强化学习框架，它将轨迹表示为一个有向无环图，合并语义等价的推理路径，以减少冗余探索并改进大型推理模型的信用分配。

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

arXiv cs.AI

COAgents是一个合作式多智能体框架，用于解决车辆路径问题，它将搜索过程建模为图，使用专门智能体进行节点选择、移动选择和跳跃以逃离局部最优。在CVRP和VRPTW基准测试上取得了最先进的结果，相比先前的基于学习的方法，将最佳已知解差距最多缩小了44%。