Abstract

The Traveling Salesman Problem (TSP) is a canonical NP-hard problem that continues to drive advances in combinatorial optimization, approximation theory, and neural combinatorial optimization. Despite extensive work across exact, heuristic, metaheuristic, and deep-learning paradigms, existing comparative studies often focus on only a subset of solver families, lack consistent evaluation pipelines, or omit explicit links between theoretical guarantees and empirical behavior. This makes it difficult for practitioners and researchers to understand which solver is appropriate for which application regime. This paper presents a unified, transparent, and reproducible comparative study spanning five major families of TSP methods: (i) exact branch-and-cut solvers (Concorde); (ii) approximation algorithms such as the Christofides–Serdyukov 3/2 bound and the Karlin–Klein–Oveis Gharan (3/2 − ε) improvement; (iii) polynomial-time approximation schemes (PTAS) for Euclidean TSP; (iv) heuristic and metaheuristic methods including 2- opt/3-opt, Lin–Kernighan, LKH, GA–EAX, and Ant Colony Optimization; and (v) learning-based models such as attentionbased solvers, POMO, NeuroLKH, and reinforcement learning– augmented LKH variants. Using synthetic Euclidean instances and representative TSPLIB datasets, we develop a reproducible evaluation pipeline supported by publicly shared artifacts (CSV logs, seed files, plots). Our results show that simple heuristics (Nearest Neighbor, Random Insertion) improved with 2-opt achieve 10–15% optimality gaps on small Euclidean instances, whereas LKH and GA–EAX provide near-optimal performance (< 0.02% gap) on TSPLIB. Learningbased solvers demonstrate competitive performance (1–3% gap) with sub-second inference after training. We further map solver properties to real-world domains such as logistics, robotics, VLSI routing, and genomics, offering domain-specific recommendations. Overall, this work provides a comprehensive, research-oriented, and educationally valuable comparison of TSP solvers, bridging classical optimization with modern learning-based approaches.

References

• E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Chichester, UK: Wiley, 1985.
• D. L. Applegate, R. E. Bixby, V. Chvátal, and W. J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
• N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Carnegie Mellon University, Tech. Rep. Report 388, 1976.
• S. Arora, “Polynomial-time approximation schemes for euclidean TSP and other geometric problems,” Journal of the ACM, vol. 45, no. 5, pp. 753–782, 1998.
• J. S. B. Mitchell, “Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems,” SIAM Journal on Computing, vol. 28, no. 4, pp. 1298–1309, 1999.
• S. Lin and B.W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21, no. 2, pp. 498–516, 1973.
• K. Helsgaun, “An effective implementation of the lin– kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126, no. 1, pp. 106–130, 2000.
• K. Helsgaun, “An extension of the lin–kernighan– helsgaun TSP solver for constrained TSP and VRP,” Roskilde University, Tech. Rep., 2017, available at: https://www.akira.ruc.dk/˜keld/research/LKH/LKH- 3_REPORT.pdf.
• I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” ICLR Workshop on Deep Reinforcement Learning, 2017, available at: https://arxiv.org/abs/1611.09940.
• W. Kool, H. van Hoof, and M. Welling, “Attention, learn to solve routing problems!” International Conference on Learning Representations (ICLR), 2019, available at: https://arxiv.org/abs/1803.08475.
• Y. Kwon, J. Park, and I. Y. Chun, “Pomo: Policy optimization with multiple optima for reinforcement learning,” Neural Information Processing Systems (NeurIPS), 2020, available at: https://arxiv.org/abs/2010.16011.
• L. Xin, W. Song, Z. Cao, and J. Zhang, “Neurolkh: Combining deep learning model with lin–kernighan–helsgaun heuristic for solving the traveling salesman problem,” Neural Information Processing Systems (NeurIPS), 2021, available at: https://arxiv.org/abs/2110.07983.
• G. Reinelt, “Tsplib – a traveling salesman problem library,” ORSA Journal on Computing, vol. 3, no. 4, pp. 376–384, 1991.
• Y. Nagata and S. Kobayashi, “A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem,” INFORMS Journal on Computing, vol. 25, no. 2, pp. 346–363, 2013.
• M. Dorigo and L. M. Gambardella, “Ant colonies for the traveling salesman problem,” BioSystems, vol. 43, no. 2, pp. 73– 81, 1997.
• A. R. Karlin, N. Klein, and S. O. Gharan, “A (slightly) improved approximation algorithm for the traveling salesman problem,” in Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC). ACM, 2021, pp. 32–45.
• A. R. Karlin, N. Klein, and S. Oveis Gharan, “A (slightly) improved deterministic approximation algorithm for metric TSP,” 2022.
• A. Seb˝o and J. Vygen, “Shorter tours by nicer ears: 7/5- approximation for graphic TSP,” Combinatorica, vol. 34, no. 5, pp. 597–629, 2014.
• O. Svensson, J. Tarnawski, and L. A. Végh, “A constant-factor approximation algorithm for the asymmetric traveling salesman problem,” Journal of the ACM, vol. 67, no. 6, pp. 1–53, 2020, sTOC 2018 version.
• J. Zheng et al., “Reinforced lin–kernighan–helsgaun algorithms for the TSP and variants (vsr-LKH-3),” arXiv preprint, 2022, arXiv:2207.03876.
• N. Sultana et al., “Learning to guide local search (L2GLS),” Computers & Operations Research (in press), 2024, doi:10.1016/j.cor.2024.106706.
• J. Sui et al., “Neuralgls: Learning to guide local search with graph neural networks,” Neural Computing and Applications (early access), 2024, doi:10.1007/s00521-023-09042-6.
• Google OR-Tools, “Traveling salesperson problem (TSP) tutorial,” Online documentation, 2024, https://developers.google.com/optimization/routing/tsp (accessed 2025-09-28).
• J. Beardwood, J. H. Halton, and J. M. Hammersley, “The shortest path through many points,” Proceedings of the Cambridge Philosophical Society, vol. 55, pp. 299–327, 1959.