Title: Learning to Reduce Search Space for Generalizable Neural Routing Solver

Abstract: Constructive neural combinatorial optimization (NCO) presents a compelling approach to solving vehicle routing problems (VRPs) by directly training models to generate approximate optimal solutions, thus minimizing the need for manual algorithm design by experts. Despite this potential, extending these techniques to large-scale scenarios is hindered by significant computational demands. Although recent dynamic search space reduction (SSR) strategies enhance inference speed via geometric distance-based pruning, they frequently falter when confronted with complex instances featuring non-uniform distributions or when optimality depends heavily on non-spatial constraints.

To overcome these limitations, we introduce Learning to Reduce (L2R), the inaugural learning-based dynamic SSR framework. L2R leverages problem-specific features to identify and extract patterns, allowing it to adaptively prioritize nodes and prune the search space at every step. This mechanism facilitates the efficient and scalable construction of solutions. Comprehensive experiments demonstrate that the L2R framework exhibits robust generalization across various VRP variants, performing consistently well across different data distributions and problem scales.

To our knowledge, L2R represents the first neural solver capable of effectively handling VRP instances containing 10 million nodes without compromising solution quality. This achievement substantially advances the boundaries of NCO regarding both scalability and generalization. The source code for this work is accessible at https://github.com/CIAM-Group/L2R.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC