mlsanityData to 14 Oct 2026

Graph Neural Network Guided Local Search for the Traveling Salesperson Problem

arXiv 2110.05291 ↗First posted 11 Oct 2021cs.LG stat.MLcited by 70

Not on the map. Why?

Abstract (arXiv)

Solutions to the Traveling Salesperson Problem (TSP) have practical applications to processes in transportation, logistics, and automation, yet must be computed with minimal delay to satisfy the real-time nature of the underlying tasks. However, solving large TSP instances quickly without sacrificing solution quality remains challenging for current approximate algorithms. To close this gap, we present a hybrid data-driven approach for solving the TSP based on Graph Neural Networks (GNNs) and Guided Local Search (GLS). Our model predicts the regret of including each edge of the problem graph in the solution; GLS uses these predictions in conjunction with the original problem graph to find solutions. Our experiments demonstrate that this approach converges to optimal solutions at a faster rate than three recent learning based approaches for the TSP. Notably, we reduce the mean optimality gap on the 100-node problem set from 1.534% to 0.705%, a 2x improvement. When generalizing from 20-node instances to the 100-node problem set, we reduce the optimality gap from 18.845% to 2.622%, a 7x improvement.

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

Builds on

21 of 47 references.

References · 21

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  4. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  5. 2017Graph Attention Networkscited by 8,923
  6. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  7. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  8. 2015Pointer Networkscited by 895
  9. 2018Attention, Learn to Solve Routing Problems!cited by 656
  10. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  11. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  12. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
9 more
  1. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  2. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 269
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  4. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 164
  5. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 162
  6. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  7. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  8. 2021Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problemscited by 16
  9. 2021Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problemcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 10; 2023: 14; 2024: 13; 2025: 20; 2026: 12.

70 papers.

Sort:

By area:

  1. 2024ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolutioncited by 276
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  3. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 142
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  5. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 119
  6. 2025Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Designcited by 109
  7. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  8. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  9. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 71
  10. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 69
  11. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  12. 2023Algorithm Evolution Using Large Language Modelcited by 53
38 more
  1. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 45
  2. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  3. 2024In-the-loop Hyper-Parameter Optimization for LLM-Based Automated Design of Heuristicscited by 28
  4. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  5. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  6. 2024Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challengescited by 21
  7. 2023Unsupervised Learning for Combinatorial Optimization Needs Meta-Learningcited by 20
  8. 2025Pareto Set Learning for Multi-Objective Reinforcement Learningcited by 20
  9. 2023Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speedcited by 19
  10. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18
  11. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  12. 2022Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problemscited by 12
  13. 2025Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learningcited by 12
  14. 2022DeepSAT: An EDA-Driven Learning Framework for SATcited by 11
  15. 2024DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problemscited by 11
  16. 2025Adversarial Generative Flow Network for Solving Vehicle Routing Problemscited by 10
  17. 2025Generalizable Heuristic Generation Through LLMs with Meta-Optimizationcited by 9
  18. 2024Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimizationcited by 8
  19. 2024GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costscited by 8
  20. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 8
  21. 2025Learning for routing: A guided review of recent developments and future directionscited by 7
  22. 2022Neural Combinatorial Optimization: a New Player in the Fieldcited by 6
  23. 2024Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSPcited by 6
  24. 2023Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problemscited by 5
  25. 2024Leader Reward for POMO-Based Neural Combinatorial Optimizationcited by 5
  26. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 5
  27. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problemscited by 5
  28. 2022The Neural-Prediction based Acceleration Algorithm of Column Generation for Graph-Based Set Covering Problemscited by 4
  29. 2026Survey on Neural Routing Solverscited by 4
  30. 2022End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Locationcited by 3
  31. 2023Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networkscited by 3
  32. 2024Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solverscited by 3
  33. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 3
  34. 2025TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problemscited by 2
  35. 2025Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphscited by 2
  36. 2025Learning for Dynamic Combinatorial Optimization without Training Datacited by 1
  37. 2025Unsupervised Learning for the Elementary Shortest Path Problemcited by 1
  38. 2025ViTSP: A Vision Language Models Guided Framework for Solving Large-Scale Traveling Salesman Problemscited by 1

50 most cited of 70 All 70 (JSON)