Learning to Reduce Search Space for Generalizable Neural Routing Solver
By: Changliang Zhou , Xi Lin , Zhenkun Wang and more
Potential Business Impact:
Finds best routes for millions of stops.
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.
Similar Papers
Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning
Machine Learning (CS)
Makes delivery routes work for huge cities.
Neural Combinatorial Optimization for Real-World Routing
Machine Learning (CS)
Finds best delivery routes using real-world data.
On Distributional Dependent Performance of Classical and Neural Routing Solvers
Machine Learning (CS)
Helps computers solve tricky puzzles faster.