mlsanityData to 7 Oct 2026

Attention, Learn to Solve Routing Problems!

arXiv 1803.08475 ↗First posted 22 Mar 2018stat.ML cs.LGcited by 646

Not on the map. Why?

Abstract (arXiv)

The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention layers with benefits over the Pointer Network and we show how to train this model using REINFORCE with a simple baseline based on a deterministic greedy rollout, which we find is more efficient than using a value function. We significantly improve over recent learned heuristics for the Travelling Salesman Problem (TSP), getting close to optimal results for problems up to 100 nodes. With the same hyperparameters, we learn strong heuristics for two variants of the Vehicle Routing Problem (VRP), the Orienteering Problem (OP) and (a stochastic variant of) the Prize Collecting TSP (PCTSP), outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms.

Key facts. Cited by 646 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Mar 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 90; 2022: 90; 2023: 87; 2024: 121; 2025: 127; 2026: 131.

646 papers.

Sort:

By area:

  1. 2023Large Language Models as Optimizerscited by 830
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 266
  4. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  5. 2022Diffusion models as plug-and-play priorscited by 230
  6. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  7. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  8. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  9. 2025Interactive Post-Training for Vision-Language-Action Modelscited by 129
  10. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  11. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  12. 2021Learning to Delegate for Large-scale Vehicle Routingcited by 108
38 more
  1. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  2. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  3. 2022The CLRS Algorithmic Reasoning Benchmarkcited by 103
  4. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  5. 2025Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Designcited by 100
  6. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  7. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  8. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  9. 2021Learning Collaborative Policies to Solve NP-hard Routing Problemscited by 86
  10. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  11. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  12. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  13. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  14. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  15. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  16. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  17. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  18. 2024HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMscited by 68
  19. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  20. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  21. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  22. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  23. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  24. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  25. 2021Ordering-Based Causal Discovery with Reinforcement Learningcited by 55
  26. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  27. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  28. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  29. 2023Jumanji: a Diverse Suite of Scalable Reinforcement Learning Environments in JAXcited by 52
  30. 2023Algorithm Evolution Using Large Language Modelcited by 52
  31. 2024Multi-objective Evolution of Heuristic Using Large Language Modelcited by 52
  32. 2022A Survey on Quantum Reinforcement Learningcited by 50
  33. 2021CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraintscited by 49
  34. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  35. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 49
  36. 2021Learning to Select Cuts for Efficient Mixed-Integer Programmingcited by 48
  37. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  38. 2025UAVs Meet LLMs: Overviews and Perspectives Toward Agentic Low-Altitude Mobilitycited by 48

50 most cited of 646 All 646 (JSON)