mlsanityData to 7 Oct 2026

Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances

arXiv 2012.10658 ↗First posted 19 Dec 2020cs.LGcited by 161

Not on the map. Why?

Abstract (arXiv)

For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.

Key facts. Cited by 161 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 19; 2023: 24; 2024: 36; 2025: 39; 2026: 25.

161 papers.

Sort:

By area:

  1. 2024Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Modelcited by 258
  2. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
  3. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  4. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  5. 2022Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimizationcited by 118
  6. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  7. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 102
  8. 2021Efficient Active Search for Combinatorial Optimization Problemscited by 99
  9. 2021Deep Policy Dynamic Programming for Vehicle Routing Problemscited by 94
  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. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  3. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 77
  4. 2021Graph Neural Network Guided Local Search for the Traveling Salesperson Problemcited by 70
  5. 2023RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmarkcited by 70
  6. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  7. 2023Towards Omni-generalizable Neural Methods for Vehicle Routing Problemscited by 68
  8. 2022Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillationcited by 61
  9. 2023Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policycited by 61
  10. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  11. 2023Unsupervised Learning for Solving the Travelling Salesman Problemcited by 57
  12. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  13. 2024RouteFinder: Towards Foundation Models for Vehicle Routing Problemscited by 54
  14. 2024Ant Colony Sampling with GFlowNets for Combinatorial Optimizationcited by 53
  15. 2023Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problemcited by 49
  16. 2024Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalizationcited by 49
  17. 2022A Survey for Solving Mixed Integer Programming via Machine Learningcited by 44
  18. 2023H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problemcited by 43
  19. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  20. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  21. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 39
  22. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  23. 2025Rethinking Light Decoder-based Solvers for Vehicle Routing Problemscited by 36
  24. 2024PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimizationcited by 35
  25. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvementcited by 32
  26. 2025EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Designcited by 32
  27. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  28. 2022Efficient Neural Neighborhood Search for Pickup and Delivery Problemscited by 29
  29. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  30. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  31. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
  32. 2023ASP: Learn a Universal Neural Solver!cited by 27
  33. 2021A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphscited by 26
  34. 2022On the Generalization of Neural Combinatorial Optimization Heuristicscited by 24
  35. 2024Cross-Problem Learning for Solving Vehicle Routing Problemscited by 24
  36. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  37. 2023Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimizationcited by 23
  38. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23

50 most cited of 161 All 161 (JSON)