mlsanityData to 14 Oct 2026

Learning to Delegate for Large-scale Vehicle Routing

arXiv 2107.04139 ↗First posted 8 Jul 2021cs.LG cs.AIcited by 109

Not on the map. Why?

Abstract (arXiv)

Vehicle routing problems (VRPs) form a class of combinatorial problems with wide practical applications. While previous heuristic or learning-based works achieve decent solutions on small problem instances of up to 100 cities, their performance deteriorates in large problems. This article presents a novel learning-augmented local search framework to solve large-scale VRP. The method iteratively improves the solution by identifying appropriate subproblems and textitdelegating their improvement to a black box subsolver. At each step, we leverage spatial locality to consider only a linear number of subproblems, rather than exponential. We frame subproblem selection as regression and train a Transformer on a generated training set of problem instances. Our method accelerates state-of-the-art VRP solvers by 10x to 100x while achieving competitive solution qualities for VRPs with sizes ranging from 500 to 3000. Learned subproblem selection offers a 1.5x to 2x speedup over heuristic or random selection. Our results generalize to a variety of VRP distributions, variants, and solvers.

Key facts. Cited by 109 papers in the map (data through 14 Oct 2026). Builds on 11 of its 68 references that are in the map. First posted on arXiv 8 Jul 2021.

Builds on

11 of 68 references.

References · 11

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2015Pointer Networkscited by 895
  4. 2018Attention, Learn to Solve Routing Problems!cited by 656
  5. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  8. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  9. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 125
  10. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  11. 2020Learning What to Defer for Maximum Independent Setscited by 54

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 12; 2023: 21; 2024: 21; 2025: 29; 2026: 25.

109 papers.

Sort:

By area:

  1. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  2. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 85
  3. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  4. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 82
  5. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  6. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  7. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  8. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 70
  9. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 69
  10. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  11. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 55
  12. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 45
38 more
  1. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 42
  2. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  3. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 37
  4. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  5. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  6. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  7. 2025Large Language Models as End-to-end Combinatorial Optimization Solverscited by 28
  8. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24
  9. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  10. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  11. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  12. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  13. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 20
  14. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  15. 2023Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Contextcited by 16
  16. 2024Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problemscited by 15
  17. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  18. 2023Learning to Configure Separators in Branch-and-Cutcited by 14
  19. 2025Learning to Reduce Search Space for Generalizable Neural Routing Solvercited by 14
  20. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  21. 2025Learning to Insert for Constructive Neural Vehicle Routing Solvercited by 10
  22. 2024Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solvercited by 9
  23. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  24. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  25. 2024GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costscited by 8
  26. 2025Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degreescited by 8
  27. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 7
  28. 2024PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimizationcited by 7
  29. 2025Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Schedulingcited by 7
  30. 2025Learning for routing: A guided review of recent developments and future directionscited by 7
  31. 2025VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problemscited by 7
  32. 2025Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDPcited by 7
  33. 2022Prediction-aware and Reinforcement Learning based Altruistic Cooperative Drivingcited by 6
  34. 2023Efficient Training of Multi-task Neural Solver for Combinatorial Optimizationcited by 6
  35. 2023Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problemscited by 6
  36. 2024Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSPcited by 6
  37. 2025Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computationcited by 6
  38. 2023Routing Arena: A Benchmark Suite for Neural Routing Solverscited by 5

50 most cited of 109 All 109 (JSON)