标题： 学习用于车辆路径问题的分割 显示英文标题

标题： Learning to Segment for Vehicle Routing Problems

摘要： 迭代搜索启发式方法被广泛认为是解决车辆路径问题（VRPs）的最先进技术。 在本工作中，我们识别并利用了一个关键观察：在这些求解器中，大部分解保持稳定，即在搜索迭代中未发生变化，导致冗余计算，尤其是在具有长子路径的大规模VRPs中。 为了解决这个问题，我们开创性地对首先分段然后聚合（FSTA）分解技术进行了正式研究，以加速迭代求解器。 具体而言，FSTA在搜索过程中保留稳定的解段，将每个段内的节点聚合为固定超节点，并仅关注不稳定的部分。 然而，一个关键挑战在于确定哪些段应由FSTA进行聚合。 为此，我们随后引入了学习分段（L2Seg），一种新颖的神经框架，用于智能区分FSTA分解中可能稳定和不稳定的部分。 我们提出了三种L2Seg变体：非自回归（全局全面但局部不加区分）、自回归（局部细化但全局不足）及其协同作用，并配有专门的训练和推理策略。 在CVRP和VRPTW上的实验结果表明，L2Seg可使最先进的迭代求解器加速达7倍。 此外，我们提供了深入分析，表明NAR和AR的协同作用通过结合它们的互补优势实现了最佳性能。 值得注意的是，L2Seg是一个灵活的框架，兼容传统、基于学习和混合求解器，同时支持一大类VRPs。 显示英文摘要

摘要： Iterative search heuristics are widely recognized as state-of-the-art for solving Vehicle Routing Problems (VRPs). In this work, we identify and exploit a critical observation: within these solvers, 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. Specifically, 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 by FSTA. To this end, we then 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, with bespoke training and inference strategies. Empirical results on CVRP and VRPTW suggest that L2Seg accelerates state-of-the-art iterative solvers by up to 7x. Additionally, we provide in-depth analysis showing NAR and AR synergy achieves best performance by combining their complementary strengths. Notably, L2Seg is a flexible framework that is compatible with traditional, learning-based, and hybrid solvers, while supporting a broad class of VRPs.