mlsanityData to 7 Oct 2026

An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

arXiv 1906.01227 ↗First posted 4 Jun 2019cs.LG stat.MLcited by 265

Not on the map. Why?

Abstract (arXiv)

This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes. In particular, we reduce the average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to 1.39% for 100 nodes. Finally, despite improving upon other learning-based approaches for TSP, our approach falls short of standard Operations Research solvers.

Key facts. Cited by 265 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 35; 2022: 45; 2023: 39; 2024: 54; 2025: 48; 2026: 44.

265 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  3. 2022Diffusion models as plug-and-play priorscited by 230
  4. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  5. 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
  6. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  7. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  8. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  9. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  10. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
  11. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  12. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
38 more
  1. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  2. 2021Matrix Encoding Networks for Neural Combinatorial Optimizationcited by 89
  3. 2022Simulation-guided Beam Search for Neural Combinatorial Optimizationcited by 84
  4. 2023GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-timecited by 82
  5. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  6. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  7. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  8. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  9. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  10. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  11. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  12. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  13. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  14. 2021The Transformer Network for the Traveling Salesman Problemcited by 59
  15. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  16. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  17. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  18. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  19. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  20. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  21. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  22. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  23. 2021On Representation Knowledge Distillation for Graph Neural Networkscited by 38
  24. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  25. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  26. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  27. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  28. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  29. 2022Learning to Solve Routing Problems via Distributionally Robust Optimizationcited by 31
  30. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  31. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  32. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  33. 2024In-the-loop Hyper-Parameter Optimization for LLM-Based Automated Design of Heuristicscited by 28
  34. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
  35. 2023ASP: Learn a Universal Neural Solver!cited by 27
  36. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited by 26
  37. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25
  38. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24

50 most cited of 265 All 265 (JSON)