提出分阶段方法解决多图上的大规模路径规划问题。
Two-Stage Learned Decomposition for Scalable Routing on Multigraphs
- 将路径决策分为节点排序与边选择两阶段，提升可扩展性。
- 在六种车辆路径问题上表现优于或媲美当前最佳模型。
- 适合需要快速训练与推理的工业级路径优化场景。
现有神经网络方法大多局限于欧氏空间或简单图结构，难以处理多图上的车辆路径问题（VRPs），其中平行边代表不同权衡的出行选项（如距离与时间）。少数适配该场景的方法存在严重可扩展性瓶颈。本文提出节点-边策略分解（NEPF）框架，将路由策略拆分为节点排列与边选择两个阶段，并设计预编码边聚合机制、非自回归边阶段架构及层次化强化学习训练方式以支持分解。在六种典型VRP变体上的实验表明，该方法在解质量上达到或超越当前最优水平，同时训练与推理速度显著提升。
原文摘要 · Abstract (English)
Most neural methods for Vehicle Routing Problems (VRPs) are limited to Euclidean settings or simple graphs. In this work, we instead consider multigraphs, where parallel edges represent distinct travel options with varying trade-offs (e.g., distance vs time). Few methods are designed for such formulations and those that do exist face major scalability issues. We mitigate these scalability issues via a Node-Edge Policy Factorization (NEPF) approach, which splits the routing policy into a node permutation stage and an edge selection stage. To enable the decomposition, we introduce a pre-encoding edge aggregation scheme and a non-autoregressive architecture for the edge stage, as well as a hierarchical reinforcement learning method to train the stages jointly. Our experiments across six VRP variants demonstrate that NEPF matches or outperforms the state-of-the-art in terms of solution quality, while being significantly faster in training and inference.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。