mlsanityData to 13 Oct 2026

Deep Policy Dynamic Programming for Vehicle Routing Problems

arXiv 2102.11756 ↗First posted 23 Feb 2021cs.LG stat.MLcited by 94

Not on the map. Why?

Abstract (arXiv)

Routing problems are a class of combinatorial problems with many practical applications. Recently, end-to-end deep learning methods have been proposed to learn approximate solution heuristics for such problems. In contrast, classical dynamic programming (DP) algorithms guarantee optimal solutions, but scale badly with the problem size. We propose Deep Policy Dynamic Programming (DPDP), which aims to combine the strengths of learned neural heuristics with those of DP algorithms. DPDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP), the vehicle routing problem (VRP) and TSP with time windows (TSPTW) and show that the neural policy improves the performance of (restricted) DP algorithms, making them competitive to strong alternatives such as LKH, while also outperforming most other 'neural approaches' for solving TSPs, VRPs and TSPTWs with 100 nodes.

Key facts. Cited by 94 papers in the map (data through 13 Oct 2026). Builds on 31 of its 75 references that are in the map. First posted on arXiv 23 Feb 2021.

Builds on

31 of 75 references.

References · 31

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,223
  2. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,991
  3. 2015Pointer Networkscited by 884
  4. 2018Attention, Learn to Solve Routing Problems!cited by 648
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 603
  6. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 344
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  8. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 314
  9. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 266
  10. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  11. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 184
  12. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
19 more
  1. 2020Solving Mixed Integer Programs Using Neural Networkscited by 180
  2. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 163
  3. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  4. 2016Sequence-to-Sequence Learning as Beam-Search Optimizationcited by 127
  5. 2020Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhoodcited by 123
  6. 2019Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problemcited by 117
  7. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  8. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
  9. 2020Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networkingcited by 70
  10. 2020Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimizationcited by 63
  11. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  12. 2020A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problemscited by 30
  13. 2020Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attentioncited by 29
  14. 2017Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networkscited by 28
  15. 2019On Learning Paradigms for the Travelling Salesman Problemcited by 24
  16. 2020Learn to Design the Heuristics for Vehicle Routing Problemcited by 24
  17. 2021Analytics and Machine Learning in Vehicle Routing Researchcited by 22
  18. 2020Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problemscited by 17
  19. 2019Approximate Dynamic Programming with Neural Networks in Linear Discrete Action Spacescited by 2

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 11; 2022: 18; 2023: 15; 2024: 19; 2025: 21; 2026: 10.

94 papers.

Sort:

By area:

  1. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 264
  2. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 141
  3. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 128
  4. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  5. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  6. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  7. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  8. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  9. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  10. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  11. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  12. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
38 more
  1. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  2. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  3. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 62
  4. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 58
  5. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  6. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 55
  7. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  8. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  9. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 40
  10. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  11. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 33
  12. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  13. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  14. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  15. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  16. 2023ASP: Learn a Universal Neural Solver!cited by 27
  17. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24
  18. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  19. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  20. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  21. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18
  22. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 18
  23. 2021Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problemscited by 16
  24. 2022Learning to Solve Vehicle Routing Problems: A Surveycited by 16
  25. 2023Equity-Transformer: Solving NP-hard Min-Max Routing Problems as Sequential Generation with Equity Contextcited by 16
  26. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  27. 2021A Game-Theoretic Approach for Improving Generalization Ability of TSP Solverscited by 14
  28. 2021A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Dronecited by 14
  29. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  30. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10
  31. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  32. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 7
  33. 2022Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problemcited by 6
  34. 2022Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?cited by 6
  35. 2023Efficient Training of Multi-task Neural Solver for Combinatorial Optimizationcited by 6
  36. 2024Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSPcited by 6
  37. 2024Prompt Learning for Generalized Vehicle Routingcited by 6
  38. 2025Learning for routing: A guided review of recent developments and future directionscited by 6

50 most cited of 94 All 94 (JSON)