Solving the traveling salesman problem with machine learning: a review of recent advances and challenges

摘要

The Traveling Salesman Problem (TSP) is a classic NP-hard problem that is central to various applications in logistics, robotics, and scheduling. This paper presents a comprehensive review of Machine Learning (ML) approaches for solving the TSP. Unlike traditional solvers, including exact and heuristic methods, ML models can generalize beyond training data, solving larger problems without the need for re-optimization, and enabling fast inference in milliseconds. These properties make ML-based TSP solvers particularly advantageous in real-time, dynamic, and resource-constrained environments. ML-based approaches are classified into traditional ML and deep learning (DL) approaches, including Pointer Network (Ptr-Net)-based, Graph Neural Network (GNN)-based, Transformer-based, hybrid DL-heuristic-based, and multi-model DL-based approaches. Our analysis highlights the growing dominance of GNNs and Transformers, attributed to their ability to capture complex inter-node relationships and manage the graph-based nature of TSP. Hybrid DL-heuristic approaches, which integrate DL with heuristics like Lin-Kernighan-Helsgaun (LKH), exhibit superior performance on large instances, combining learning flexibility with heuristic efficiency. A comparative summary and discussion highlight each approach’s strengths and limitations, identifying key challenges such as scalability, computational overhead, generalization and preserving quality at scale. Finally, the paper outlines promising future directions, emphasizing the need for scalable, generalizable, and resource-efficient solutions to address real-world TSP applications.