URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization

Multi-task neural routing solvers have emerged as a promising paradigm for their ability to solve multiple vehicle routing problems (VRPs) using a single model. However, existing neural solvers typically rely on predefined problem constraints or require per-problem fine-tuning, which substantially limits their zero-shot generalization ability to unseen VRP variants. To address this critical bottleneck, we propose URS, a unified neural routing solver that achieves zero-shot generalization across a wide range of unseen VRPs with a single model. We propose a unified data representation (UDR) that replaces problem enumeration with data unification, thereby broadening the problem coverage and reducing reliance on domain expertise. In addition, we introduce a mixed bias module (MBM) during encoding to improve node embeddings, which efficiently captures multiple priors inherent to various problems. On top of the UDR, we develop a problem-conditioned parameter generator to further improve zero-shot generalization. Extensive experiments show that URS consistently produces high-quality solutions for 110 VRP variants (including 99 unseen variants) while demonstrating impressive scalability to large-scale instances with up to 7000 nodes. To the best of our knowledge, URS is the first neural solver to handle over 100 VRP variants with a single model. Our code is available at https://github.com/CIAM-Group/URS.

Planning routes for delivery trucks, buses, or service vehicles is hard because each real-world setting has different rules, such as time windows, duration limits, and pickup and delivery requirements. Most neural routing solvers are built for only a few problem types, so they often need to be redesigned or retrained when the problem changes. We introduce URS, a unified neural routing solver that handles a wide range of routing tasks, including those it has never seen before. Instead of listing every possible problem type in advance, URS uses a shared way to describe problem instances, allowing the same model to understand different routing scenarios. It also adapts its decision-making to the specific rules of each case. In experiments, URS found high-quality routes across 110 routing problems, including 99 unseen during training, and handled large-scale cases with up to 7,000 locations.