A survey on deep learning-based algorithms for the traveling salesman problem

doi:10.1007/s11704-024-40490-y

	A survey on deep learning-based algorithms for the traveling salesman problem
	Sui, Jingyan 1,2; Ding, Shizhe 1,2; Huang, Xulin 1,4; Yu, Yue 1,2,5; Liu, Ruizhi 1,2; Xia, Boyang 1,2; Ding, Zhenxin 1,2; Xu, Liming 1,2; Zhang, Haicang 1,2; Yu, Chungong 1,2; Bu, Dongbo 1,2,3
	2025-06-01
发表期刊	FRONTIERS OF COMPUTER SCIENCE
ISSN	2095-2228
卷号	19 期号:6 页码:30
摘要	This paper presents an overview of deep learning (DL)-based algorithms designed for solving the traveling salesman problem (TSP), categorizing them into four categories: end-to-end construction algorithms, end-to-end improvement algorithms, direct hybrid algorithms, and large language model (LLM)-based hybrid algorithms. We introduce the principles and methodologies of these algorithms, outlining their strengths and limitations through experimental comparisons. End-to-end construction algorithms employ neural networks to generate solutions from scratch, demonstrating rapid solving speed but often yielding subpar solutions. Conversely, end-to-end improvement algorithms iteratively refine initial solutions, achieving higher-quality outcomes but necessitating longer computation times. Direct hybrid algorithms directly integrate deep learning with heuristic algorithms, showcasing robust solving performance and generalization capability. LLM-based hybrid algorithms leverage LLMs to autonomously generate and refine heuristics, showing promising performance despite being in early developmental stages. In the future, further integration of deep learning techniques, particularly LLMs, with heuristic algorithms and advancements in interpretability and generalization will be pivotal trends in TSP algorithm design. These endeavors aim to tackle larger and more complex real-world instances while enhancing algorithm reliability and practicality. This paper offers insights into the evolving landscape of DL-based TSP solving algorithms and provides a perspective for future research directions.
关键词	traveling salesman problem algorithms design deep learning neural network
DOI	10.1007/s11704-024-40490-y
收录类别	SCI
语种	英语
资助项目	National Key R&D Program of China[2020YFA0907000] ; National Natural Science Foundation of China[32270657] ; National Natural Science Foundation of China[32271297] ; National Natural Science Foundation of China[82130055] ; National Natural Science Foundation of China[62072435] ; Youth Innovation Promotion Association, Chinese Academy of Sciences
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:001376567700003
出版者	HIGHER EDUCATION PRESS
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/41131
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Bu, Dongbo
作者单位	1.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processor, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100190, Peoples R China 3.Cent China Inst Artificial Intelligence, Zhengzhou 450046, Peoples R China 4.Zhengzhou Univ, Henan Inst Adv Technol, Zhengzhou 450002, Peoples R China 5.UCAS, Hangzhou Inst Adv Study, Hangzhou 310024, Peoples R China
推荐引用方式 GB/T 7714	Sui, Jingyan,Ding, Shizhe,Huang, Xulin,et al. A survey on deep learning-based algorithms for the traveling salesman problem[J]. FRONTIERS OF COMPUTER SCIENCE,2025,19(6):30.
APA	Sui, Jingyan.,Ding, Shizhe.,Huang, Xulin.,Yu, Yue.,Liu, Ruizhi.,...&Bu, Dongbo.(2025).A survey on deep learning-based algorithms for the traveling salesman problem.FRONTIERS OF COMPUTER SCIENCE,19(6),30.
MLA	Sui, Jingyan,et al."A survey on deep learning-based algorithms for the traveling salesman problem".FRONTIERS OF COMPUTER SCIENCE 19.6(2025):30.