The Traveling Salesman Problem (TSP), a quintessential challenge in computational theory, involves finding the shortest route that visits each city exactly once before returning to the starting point. Due to its NP-hard nature, solving TSP has long been a formidable task, yet it holds crucial implications across various fields including operations research and mathematical optimization. Applications range from package delivery routing to warehouse order picking, where efficient route planning is paramount.
Despite its complexity, researchers have consistently sought solutions to TSP, especially leveraging deep learning (DL). However, existing surveys have not comprehensively covered a wide range of algorithms, focusing primarily on theoretical analysis with insufficient experimental validation, and they have not included algorithms based on large language models (LLMs).
Addressing these gaps, a research team led by Dongbo Bu published their comprehensive survey on TSP algorithms on 15 June 2025, in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The research categorizes algorithms for TSP into four categories: DL-based end-to-end construction algorithms, DL-based end-to-end improvement algorithms, direct hybrid algorithms, and LLM-based hybrid algorithms. The research evaluates representative algorithms from each category through experimentation.
Key findings highlight the strengths and trade-offs among different algorithm types: DL-based end-to-end construction algorithms offer speed but compromise on solution quality, whereas DL-based end-to-end improvement algorithms yield higher-quality solutions at the expense of longer computation times. Direct hybrid algorithms emerge as promising solutions, showcasing high-quality results in minimal time, underscoring their potential for real-world applications. LLM-based hybrids introduce novel possibilities for automated algorithm generation and refinement. Hybrid algorithms exhibit superior performance, when considering both solution quality and computation time.
The findings from this study provide valuable insights into enhancing TSP solving algorithms, paving the way for future innovations in computational efficiency and solution quality across diverse practical scenarios.
DOI
10.1007/s11704-024-40490-y