Towards Omni-generalizable Neural Methods for Vehicle Routing Problems
Learning heuristics for vehicle routing problems (VRPs) has gained much attention due to the less reliance on hand-crafted rules. However, existing methods are typically trained and tested on the same task with a fixed size and distribution (of nodes), and hence suffer from limited generalization performance. This paper studies a challenging yet realistic setting, which considers generalization across both size and distribution in VRPs. We propose a generic meta-learning framework, which enables effective training of an initialized model with the capability of fast adaptation to new tasks during inference. We further develop a simple yet efficient approximation method to reduce the training overhead. Extensive experiments on both synthetic and benchmark instances of the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) demonstrate the effectiveness of our method. The code is available at: https://github.com/RoyalSkye/Omni-VRP.
Code (1)
Tasks
Combinatorial OptimizationMeta-LearningTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation
Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring th…
Knowledge DistillationLearning to Reduce Search Space for Generalizable Neural Routing Solver
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 …
Combinatorial OptimizationTraveling Salesman ProblemTowards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy
Machine learning has been adapted to help solve NP-hard combinatorial optimization problems. One prevalent way is learning to construct solutions by deep neural networks, which has been receiving more and more attention …
Combinatorial OptimizationGenetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems
When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. Examples are the multi-depot vehicle routing problem (MDVRP), w…
Graph Neural NetworkSpatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows
Several metaheuristics use decomposition and pruning strategies to solve large-scale instances of the vehicle routing problem (VRP). Those complexity reduction techniques often rely on simple, problem-specific rules. How…
Clustering