用神经网络智能识别路径稳定段，加速车辆路径求解
Learning to Segment for Vehicle Routing Problems
- 提出L2Seg框架，自动判断路径中可聚合的稳定段
- 在CVRP和VRPTW上使求解速度提升2至7倍
- 兼容传统与学习型求解器，适用于多种车辆路径问题
迭代启发式算法是车辆路径问题（VRPs）的主流方法。本文发现：求解过程中大量路径片段保持不变，导致重复计算，尤其在大规模问题含长子环时更显著。为此，我们首次系统研究了先分段后聚合（FSTA）技术以加速求解。FSTA保留稳定段，将段内节点合并为固定超节点，仅对不稳定的部分进行搜索。核心挑战在于如何识别应聚合的段。为此提出Learning-to-Segment（L2Seg）神经框架，智能区分潜在稳定与不稳定区域。设计三种变体：非自回归（全局全面但局部粗略）、自回归（局部精细但全局不足）及其协同策略。在CVRP和VRPTW数据集上的实验表明，L2Seg使先进求解器提速2至7倍。深入分析揭示协同策略性能最优。该方法兼容传统、学习型及混合求解器，支持多种VRP场景。
原文摘要 · Abstract (English)
Iterative heuristics are widely recognized as state-of-the-art for Vehicle Routing Problems (VRPs). In this work, we exploit a critical observation: a large portion of the solution remains stable, i.e., unchanged across search iterations, causing redundant computations, especially for large-scale VRPs with long subtours. To address this, we pioneer the formal study of the First-Segment-Then-Aggregate (FSTA) decomposition technique to accelerate iterative solvers. FSTA preserves stable solution segments during the search, aggregates nodes within each segment into fixed hypernodes, and focuses the search only on unstable portions. Yet, a key challenge lies in identifying which segments should be aggregated. To this end, we introduce Learning-to-Segment (L2Seg), a novel neural framework to intelligently differentiate potentially stable and unstable portions for FSTA decomposition. We present three L2Seg variants: non-autoregressive (globally comprehensive but locally indiscriminate), autoregressive (locally refined but globally deficient), and their synergy. Empirical results on CVRP and VRPTW show that L2Seg accelerates state-of-the-art solvers by 2x to 7x. We further provide in-depth analysis showing why synergy achieves the best performance. Notably, L2Seg is compatible with traditional, learning-based, and hybrid solvers, while supporting various VRPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。