Learning to Reduce Search Space for Generalizable Neural Routing Solver
This addresses scalability issues in neural routing solvers for applications like logistics, though it is incremental by building on existing NCO methods.
The paper tackles the challenge of generalizing neural combinatorial optimization to large-scale routing problems by proposing a learning-based method to reduce search space, achieving generalization to instances with up to 1 million nodes while maintaining solution quality.
Constructive neural combinatorial optimization (NCO) has attracted growing research attention due to its ability to solve complex routing problems without relying on handcrafted rules. However, existing NCO methods face significant challenges in generalizing to large-scale problems due to high computational complexity and inefficient capture of structural patterns. To address this issue, we propose a novel learning-based search space reduction method that adaptively selects a small set of promising candidate nodes at each step of the constructive NCO process. Unlike traditional methods that rely on fixed heuristics, our selection model dynamically prioritizes nodes based on learned patterns, significantly reducing the search space while maintaining solution quality. Experimental results demonstrate that our method, trained solely on 100-node instances from uniform distribution, generalizes remarkably well to large-scale Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) instances with up to 1 million nodes from the uniform distribution and over 80K nodes from other distributions.