mlsanityData to 7 Oct 2026

Learning Improvement Heuristics for Solving Routing Problems

arXiv 1912.05784 ↗First posted 12 Dec 2019cs.AI cs.LGcited by 162

Not on the map. Why?

Abstract (arXiv)

Recent studies in using deep learning to solve routing problems focus on construction heuristics, the solutions of which are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by hand-crafted rules which may limit their performance. In this paper, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention based deep architecture as the policy network to guide the selection of next solution. We apply our method to two important routing problems, i.e. travelling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art deep learning based approaches. The learned policies are more effective than the traditional hand-crafted ones, and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions and even real-world dataset.

Key facts. Cited by 162 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 20; 2022: 19; 2023: 31; 2024: 34; 2025: 35; 2026: 23.

162 papers.

Sort:

By area:

  1. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  2. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  3. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  4. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  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 102
  7. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  8. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  9. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  10. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  11. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  12. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
38 more
  1. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  2. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  3. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  4. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  5. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  6. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  7. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  8. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  9. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  10. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  11. 2023Algorithm Evolution Using Large Language Modelcited by 52
  12. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  13. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  14. 2023Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNetscited by 40
  15. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  16. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  17. 2021Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learningcited by 35
  18. 2021Learning Large Neighborhood Search Policy for Integer Programmingcited by 35
  19. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  20. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  21. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  22. 2021Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problemcited by 31
  23. 2022Learning to Solve Routing Problems via Distributionally Robust Optimizationcited by 31
  24. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  25. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  26. 2023ASP: Learn a Universal Neural Solver!cited by 27
  27. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  28. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  29. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  30. 2024Trajectory Data Management and Mining: A Survey from Deep Learning to the LLM Eracited by 23
  31. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  32. 2021Analytics and Machine Learning in Vehicle Routing Researchcited by 22
  33. 2021An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problemcited by 22
  34. 2023Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimizationcited by 21
  35. 2022Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Schedulingcited by 20
  36. 2023Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speedcited by 19
  37. 2025HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challengescited by 19
  38. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18

50 most cited of 162 All 162 (JSON)