mlsanityData to 7 Oct 2026

Unsupervised Learning for Solving the Travelling Salesman Problem

arXiv 2303.10538 ↗First posted 19 Mar 2023cs.AI cs.LGcited by 57

Not on the map. Why?

Abstract (arXiv)

We propose UTSP, an unsupervised learning (UL) framework for solving the Travelling Salesman Problem (TSP). We train a Graph Neural Network (GNN) using a surrogate loss. The GNN outputs a heat map representing the probability for each edge to be part of the optimal path. We then apply local search to generate our final prediction based on the heat map. Our loss function consists of two parts: one pushes the model to find the shortest path and the other serves as a surrogate for the constraint that the route should form a Hamiltonian Cycle. Experimental results show that UTSP outperforms the existing data-driven TSP heuristics. Our approach is parameter efficient as well as data efficient: the model takes ~ 10% of the number of parameters and ~ 0.2% of training samples compared with reinforcement learning or supervised learning methods.

Key facts. Cited by 57 papers in the map (data through 7 Oct 2026). Builds on 15 of its 27 references that are in the map. First posted on arXiv 19 Mar 2023.

Builds on

15 of 27 references.

References · 15

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2018Attention, Learn to Solve Routing Problems!cited by 646
  4. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  5. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  6. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  7. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  8. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  9. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  10. 2020Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instancescited by 161
  11. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  12. 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 96
3 more
  1. 2022Can Hybrid Geometric Scattering Networks Help Solve the Maximum Clique Problem?cited by 25
  2. 2019On Learning Paradigms for the Travelling Salesman Problemcited by 24
  3. 2022Overcoming Oversmoothness in Graph Convolutional Networks via Hybrid Scattering Networkscited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 23; 2025: 18; 2026: 16.

57 papers.

Sort:

By area:

  1. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  2. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  3. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  4. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  5. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  6. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  7. 2024Diffusion Models as Constrained Samplers for Optimization with Unknown Constraintscited by 33
  8. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  9. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  10. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  11. 2025Neural Deconstruction Search for Vehicle Routing Problemscited by 15
  12. 2025Learning to Reduce Search Space for Generalizable Neural Routing Solvercited by 14
38 more
  1. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  2. 2024A GREAT Architecture for Edge-Based Graph Problems Like TSPcited by 7
  3. 2026RADAR: Learning to Route with Asymmetry-aware DistAnce Representationscited by 7
  4. 2024Less Is More -- On the Importance of Sparsification for Transformers and Graph Neural Networks for TSPcited by 6
  5. 2024Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and Morecited by 6
  6. 2025Learning for routing: A guided review of recent developments and future directionscited by 6
  7. 2024Moco: A Learnable Meta Optimizer for Combinatorial Optimizationcited by 5
  8. 2024SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groupscited by 5
  9. 2025EFormer: An Effective Edge-based Transformer for Vehicle Routing Problemscited by 5
  10. 2025Learning to Segment for Vehicle Routing Problemscited by 5
  11. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  12. 2025Towards graph neural networks for provably solving convex optimization problemscited by 4
  13. 2026Survey on Neural Routing Solverscited by 4
  14. 2024Beyond the Heatmap: A Rigorous Evaluation of Component Impact in MCTS-Based TSP Solverscited by 3
  15. 2024Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimizationcited by 2
  16. 2025LocalEscaper: A Weakly-supervised Framework with Regional Reconstruction for Scalable Neural TSP Solverscited by 2
  17. 2025Structure As Search: Unsupervised Permutation Learning for Combinatorial Optimizationcited by 2
  18. 2026Towards Efficient Constraint Handling in Neural Solvers for Routing Problemscited by 2
  19. 2024On Size and Hardness Generalization in Unsupervised Learning for the Travelling Salesman Problemcited by 1
  20. 2024IDEQ -- Improving Diffusion Models for the Traveling Salesman Problem (TSP) by Leveraging the Structure of the Solution Spacecited by 1
  21. 2025Unsupervised Ordering for Maximum Cliquecited by 1
  22. 2025Recurrent State Encoders for Efficient Neural Combinatorial Optimizationcited by 1
  23. 2026Graph Neural Networks are Heuristicscited by 1
  24. 2026CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimizationcited by 1
  25. 2026Efficient Decoder Scaling Strategy for Neural Routing Solverscited by 1
  26. 2026Leveraging Structural Constraints for Diffusion-based Neural TSP Solverscited by 1
  27. 2024Supplementary Materials to Graph Convolutional Branch and Boundcited by 0
  28. 2024Comment on paper: Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 0
  29. 2024Permutation Picture of Graph Combinatorial Optimization Problemscited by 0
  30. 2024ReMAP: Neural Reparameterization for Scalable MAP Inference in Arbitrary-Order Markov Random Fieldscited by 0
  31. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  32. 2025Unsupervised Learning for Quadratic Assignmentcited by 0
  33. 2025Graph Reduction with Unsupervised Learning in Column Generation: A Routing Applicationcited by 0
  34. 2025On Distributional Dependent Performance of Classical and Neural Routing Solverscited by 0
  35. 2025Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problemcited by 0
  36. 2025Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimizationcited by 0
  37. 2026HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problemscited by 0
  38. 2026Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?cited by 0

50 most cited of 57 All 57 (JSON)