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

doi:10.1007/s11704-024-40490-y

Front. Comput. Sci.

2025, Vol. 19

Issue (6) : 196322 https://doi.org/10.1007/s11704-024-40490-y

Artificial Intelligence

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

Jingyan SUI^1,², Shizhe DING^1,², Xulin HUANG^1,⁴, Yue YU^1,^2,⁵, Ruizhi LIU^1,², Boyang XIA^1,², Zhenxin DING^1,², Liming XU^1,², Haicang ZHANG^1,², Chungong YU^1,², Dongbo BU^1,^2,³(

)

¹. State Key Lab of Processor, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
². University of Chinese Academy of Sciences, Beijing 100190, China
³. Central China Institute of Artificial Intelligence, Zhengzhou 450046, China
⁴. Henan Institute of Advanced Technology, Zhengzhou University, Zhengzhou 450002, China
⁵. Hangzhou Institute for Advanced Study, UCAS, Hangzhou 310024, China

Download: PDF(16377 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

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.

Keywords traveling salesman problem algorithms design deep learning neural network

Corresponding Author(s): Dongbo BU

Just Accepted Date: 27 June 2024 Issue Date: 29 August 2024

Cite this article:

Jingyan SUI,Shizhe DING,Xulin HUANG, et al. A survey on deep learning-based algorithms for the traveling salesman problem[J]. Front. Comput. Sci., 2025, 19(6): 196322.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-024-40490-y
https://academic.hep.com.cn/fcs/EN/Y2025/V19/I6/196322

Fig.1 A TSP instance with 50 nodes (TSP

50

)

Fig.2 2-OPT and 3-OPT heuristics for TSP [41]

Fig.3 Classification of DL-based algorithms for TSP

Fig.4 Markov decision process associated with RL [24]

Fig.5 Attention mechanism [76]

Fig.6 Transformer [78]

Fig.7 Graph convolutional network [92]

Fig.8 Graph attention network [93]

Fig.9 Pointer network [46]

Fig.10 Attention+RL algorithm [48]

Fig.11 Encoder of AM algorithm [50]

Fig.12 Decoder of AM algorithm [50]

Fig.13 POMO framework [51]

Fig.14 LEHD model [55]

Fig.15 S2V-DQN framework [56]

Fig.16 GPN algorithm [57]

Fig.17 Learned 2-OPT algorithm by Wu et al. [62]

Fig.18 Learned 2-OPT algorithm by Costa et al. [63]

Fig.19 DACT algorithm [64]

Fig.20 Neural-3-OPT algorithm [41]

Fig.21 GCN+BS algorithm [65]

Fig.22 GAT+GLS algorithm [66]

Fig.23 NeuralGLS algorithm [67]

Fig.24 Att-GCRN+MCTS algorithm [68]

Fig.25 NeuroLKH algorithm [71]

Fig.26 AEL framework [73]

Fig.27 ReEvo framework [74]

Type	Size	Discription
Randomly generated	20/50/100/200	randomly generated with node coordinates in the unit square $[0, 1] 2$
TSPLIB	14 – 85900	from various sources and of various types in the real world

Tab.1 Datasets commonly used to evaluate algorithms performance for TSP

	Algorithm	Category	TSP20		TSP50		TSP100
	Algorithm	Category	Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s
Heuristic	Concorde [36]		0.000	0.010	0.000	0.051	0.000	0.224
	Nearest Neighbor [37]		17.448	0.000	23.230	0.001	25.104	0.006
	Farthest Insertion [37]		2.242	0.002	7.263	0.022	12.456	0.174
	Local Search [35]		1.824	0.007	3.358	0.086	4.169	0.574
	LKH-3 [45] (1 trail)		0.000	0.001	0.009	0.017	0.022	0.050
	LKH-3 [45] (10 trails)		0.000	0.001	0.004	0.021	0.011	0.065
	LKH-3 [45] (100 trails)		0.000	0.002	0.001	0.062	0.002	0.212
DL-based algorithm	Kool et al. [50]	C	0.068	0.026	0.494	0.065	2.359	0.167
	Costa et al. $∗$ [63]	I	0.001	0.464	0.134	0.637	0.758	0.931
	Joshi et al. [65]	D	0.035	0.974	0.227	2.261	1.516	4.327
	Hudson et al. [66]	D	0.000	10.008	0.002	10.048	0.454	10.175
	Xin et al. [71] (1 trail)	D	?	?	0.001	0.008	0.009	0.018
	Xin et al. [71] (10 trails)	D	?	?	0.000	0.010	0.003	0.027
	Xin et al. [71] (100 trails)	D	?	?	0.000	0.037	0.001	0.118
	Ye et al. [74]	L	0.000	0.007	0.000	0.089	0.004	0.393

Tab.2 Performance of five traditional algorithms and six classical DL-based algorithms in solving randomly generated TSPs. Gap denotes the optimality gap, measured in percent (%), and Time represents the computation time, measured in seconds (s). C, I, D, and L respectively denotes the four categories of algorithms: End-to-end construction algorithms, End-to-end improvement algorithms, Direct hybrid algorithms, and LLM-based hybrid algorithms

Fig.28 Comprehensive perspective of solution quality and computation time for various algorithms on TSP50

Fig.29 Comprehensive perspective of solution quality and computation time for various algorithms on TSP100

TSP	Kool et al. [50]		Costa et al. [63]		Joshi et al. [65]		Hudson et al. [66]		Xin et al. [71] $∗$		Ye et al. [74]
TSP	Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s
eil51	1.692	0.069	0.394	523.907	8.341	2.414	0.000	10.044	0.000	0.114	2.346	0.001
berlin52	17.953	0.073	1.743	531.19	41.694	2.377	0.000	10.053	0.000	0.070	3.862	0.001
st70	1.930	0.117	1.004	845.866	33.836	3.108	0.000	10.040	0.000	0.083	2.316	0.002
eil76	2.525	0.128	0.693	656.161	5.682	3.432	0.000	10.097	0.000	0.071	1.846	0.001
pr76	2.810	0.124	0.445	677.782	17.893	3.344	0.000	10.043	0.000	0.155	1.506	0.001
rat99	5.843	0.167	1.064	803.023	20.747	4.19	0.056	10.816	0.000	0.098	4.873	0.004
kroA100	6.674	0.161	2.918	749.98	0.774	4.357	0.042	10.885	0.000	0.117	2.534	0.003
kroB100	8.232	0.169	0.732	750.806	18.792	4.393	0.263	10.716	0.000	0.174	0.585	0.003
kroC100	6.127	0.175	0.946	758.839	1.111	4.409	0.000	10.776	0.000	0.103	5.573	0.003
kroD100	5.637	0.168	1.049	754.058	11.206	4.338	0.000	10.762	0.000	0.127	3.851	0.004
kroE100	3.939	0.163	1.163	710.341	23.053	4.439	0.983	10.818	0.000	0.133	4.352	0.005
rd100	3.366	0.169	0.371	763.456	0.057	4.445	0.077	10.793	0.000	0.092	2.950	0.005
eil101	2.526	0.173	1.390	771.908	0.426	4.542	0.519	10.792	0.000	0.097	1.302	0.003
lin105	16.414	0.190	1.935	783.738	85.133	4.601	0.161	10.190	0.000	0.098	0.734	0.004
pr107	8.004	0.183	28.617	784.38	47.583	4.592	1.033	10.286	0.000	2.051	0.617	0.003
pr124	4.350	0.226	0.629	821.876	24.467	5.407	1.367	10.218	0.000	0.561	1.890	0.004
bier127	9.253	0.231	4.953	854.601	36.361	5.517	2.878	10.092	0.027	0.194	1.299	0.004
ch130	3.228	0.242	1.178	887.715	11.329	5.501	1.498	10.044	0.000	0.310	5.985	0.004
pr136	4.961	0.285	0.856	901.362	36.47	5.812	1.893	11.850	0.000	0.932	6.789	0.006
pr144	11.274	0.288	1.218	805.555	49.799	6.187	1.519	12.197	0.000	0.823	1.281	0.005
ch150	4.475	0.318	1.325	994.263	28.499	6.529	0.930	10.425	0.000	0.406	2.110	0.006
kroA150	12.380	0.318	2.396	964.421	31.413	6.479	2.174	10.112	0.000	0.397	7.097	0.006
kroB150	8.431	0.313	2.777	981.929	55.122	6.443	2.142	10.281	0.000	0.313	3.720	0.016
pr152	10.478	0.306	5.793	857.961	54.053	6.605	5.473	10.896	0.000	2.613	1.892	0.006
u159	8.799	0.331	0.823	982.689	37.904	6.952	0.207	10.398	0.000	0.165	5.962	0.283
rat195	16.879	0.478	5.340	1259.682	42.35	8.684	2.843	11.714	0.000	1.006	1.089	0.015
d198	434.654	0.474	31.723	1128.726	51.979	8.492	7.814	10.912	0.360	1.201	2.039	0.010
kroA200	15.661	0.495	6.224	1206.469	40.861	8.77	2.481	10.754	0.000	0.321	0.861	0.014
kroB200	18.612	0.477	5.606	1196.682	46.528	9.062	1.881	10.355	0.000	0.243	5.511	0.016
Mean	22.659	0.242	3.976	852.047	29.775	5.359	1.318	10.599	0.013	0.451	2.992	0.015

Tab.3 Performance of six classical DL-based algorithms in solving real-world TSPs

Fig.30 Comprehensive perspective of solution quality and computation time for DL-based algorithms on real-world TSP instances from TSPLIB

Algorithm	Category	Model trained on TSP20
		TSP20		TSP50		TSP100		TSP200
		Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s
Kool et al. [50]	C	0.068	0.026	1.806	0.062	22.525	0.158	66.220	0.480
Costa et al. $∗$ [63]	I	0.001	0.464	2.482	0.802	23.181	1.071	94.452	1.879
Joshi et al. [65]	D	0.035	0.974	28.892	9.176	66.655	13.264	149.489	21.563
Hudson et al. [66]	D	0.000	10.008	0.093	10.029	2.112	10.010	6.365	10.852

Tab.4 Generalization performance of models trained on TSP20 dataset for four representative DL-based algorithms

Algorithm	Category	Model trained on TSP50
		TSP50		TSP100		TSP200
		Gap/%	Time/s	Gap/%	Time/s	Gap/%	Time/s
Kool et al. [50]	C	0.494	0.065	2.876	0.160	20.541	0.480
Costa et al. $∗$ [63]	I	0.134	0.637	1.404	1.074	7.824	1.801
Joshi et al. [65]	D	0.227	2.261	49.581	13.197	95.421	21.637
Hudson et al. [66]	D	0.002	10.048	1.028	10.091	5.765	10.632

Tab.5 Generalization performance of models trained on TSP50 dataset for four representative DL-based algorithms

Algorithm	Cateroty	Model trained on TSP100
		TSP100		TSP200
		Gap/%	Time/s	Gap/%	Time/s
Kool et al. [50]	C	2.359	0.167	6.785	0.479
Costa et al. $∗$ [63]	I	0.758	0.931	2.785	1.676
Joshi et al. [65]	D	1.516	4.327	49.477	21.592
Hudson et al. [66]	D	0.454	10.175	3.285	10.422

Tab.6 Generalization performance of models trained on TSP100 dataset for four representative DL-based algorithms

1	W J Cook . In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton: Princeton University Press, 2012
2	Maire B F J, La V M Mladenov . Comparison of neural networks for solving the travelling salesman problem. In: Proceedings of the 11th Symposium on Neural Network Applications in Electrical Engineering. 2012, 21–24
3	Y, LeCun Y, Bengio G Hinton . Deep learning. Nature, 2015, 521( 7553): 436–444
4	K, Wei T, Li F, Huang J, Chen Z He . Cancer classification with data augmentation based on generative adversarial networks. Frontiers of Computer Science, 2022, 16( 2): 162601
5	H, Shi J, Wang J, Cheng X, Qi H, Ji C J, Struchiner D A M, Villela E V, Karamov A S Turgiev . Big data technology in infectious diseases modeling, simulation, and prediction after the COVID-19 outbreak. Intelligent Medicine, 2023, 3( 2): 85–96
6	Y, Wu P, Zhang H, Shen H Zhai . Visualizing a neural network that develops quantum perturbation theory. Physical Review A, 2018, 98( 1): 010701(R)
7	P, Zhang H, Shen H Zhai . Machine learning topological invariants with neural networks. Physical Review Letters, 2018, 120( 6): 066401
8	N, Sun J, Yi P, Zhang H, Shen H Zhai . Deep learning topological invariants of band insulators. Physical Review B, 2018, 98( 8): 085402
9	J, Jumper R, Evans A, Pritzel T, Green M, Figurnov O, Ronneberger K, Tunyasuvunakool R, Bates A, Žídek A, Potapenko A, Bridgland C, Meyer S A A, Kohl A J, Ballard A, Cowie B, Romera-Paredes S, Nikolov R, Jain J, Adler T, Back S, Petersen D, Reiman E, Clancy M, Zielinski M, Steinegger M, Pacholska T, Berghammer S, Bodenstein D, Silver O, Vinyals A W, Senior K, Kavukcuoglu P, Kohli D Hassabis . Highly accurate protein structure prediction with AlphaFold. Nature, 2021, 596( 7873): 583–589
10	K, Tunyasuvunakool J, Adler Z, Wu T, Green M, Zielinski A, Žídek A, Bridgland A, Cowie C, Meyer A, Laydon S, Velankar G J, Kleywegt A, Bateman R, Evans A, Pritzel M, Figurnov O, Ronneberger R, Bates S A A, Kohl A, Potapenko A J, Ballard B, Romera-Paredes S, Nikolov R, Jain E, Clancy D, Reiman S, Petersen A W, Senior K, Kavukcuoglu E, Birney P, Kohli J, Jumper D Hassabis . Highly accurate protein structure prediction for the human proteome. Nature, 2021, 596( 7873): 590–596
11	M, Baek F, DiMaio I, Anishchenko J, Dauparas S, Ovchinnikov G R, Lee J, Wang Q, Cong L N, Kinch R D, Schaeffer C, Millán H, Park C, Adams C R, Glassman A, Degiovanni J H, Pereira A V, Rodrigues Dijk A A, Van A C, Ebrecht D J, Opperman T, Sagmeister C, Buhlheller T, Pavkov-Keller M K, Rathinaswamy U, Dalwadi C K, Yip J E, Burke K C, Garcia N V, Grishin P D, Adams R J, Read D Baker . Accurate prediction of protein structures and interactions using a three-track neural network. Science, 2021, 373( 6557): 871–876
12	F, Ju J, Zhu B, Shao L, Kong T Y, Liu W M, Zheng D Bu . CopulaNet: learning residue co-evolution directly from multiple sequence alignment for protein structure prediction. Nature Communications, 2021, 12( 1): 2535
13	A, Davies P, Veličković L, Buesing S, Blackwell D, Zheng N, Tomašev R, Tanburn P, Battaglia C, Blundell A, Juhász M, Lackenby G, Williamson D, Hassabis P Kohli . Advancing mathematics by guiding human intuition with AI. Nature, 2021, 600( 7887): 70–74
14	A, Fawzi M, Balog A, Huang T, Hubert B, Romera-Paredes M, Barekatain A, Novikov F J R, Ruiz J, Schrittwieser G, Swirszcz D, Silver D, Hassabis P Kohli . Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 2022, 610( 7930): 47–53
15	W, Tenachi R, Ibata F I Diakogiannis . Deep symbolic regression for physics guided by units constraints: toward the automated discovery of physical laws. The Astrophysical Journal, 2023, 959( 2): 99
16	B, Romera-Paredes M, Barekatain A, Novikov M, Balog M P, Kumar E, Dupont F J R, Ruiz J S, Ellenberg P, Wang O, Fawzi P, Kohli A Fawzi . Mathematical discoveries from program search with large language models. Nature, 2024, 625( 7995): 468–475
17	N, Wu J, Wang W X, Zhao Y Jin . Learning to effectively estimate the travel time for fastest route recommendation. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2019, 1923–1932
18	N, Wu X W, Zhao J, Wang D Pan . Learning effective road network representation with hierarchical graph neural networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020, 6–14
19	J, Ji J, Wang Z, Jiang J, Ma H Zhang . Interpretable spatiotemporal deep learning model for traffic flow prediction based on potential energy fields. In: Proceedings of IEEE International Conference on Data Mining. 2020, 1076–1081
20	J, Wang N, Wu W X Zhao . Personalized route recommendation with neural network enhanced search algorithm. IEEE Transactions on Knowledge and Data Engineering, 2022, 34( 12): 5910–5924
21	Z, Wang Z, Pan S, Chen S, Ji X, Yi J, Zhang J, Wang Z, Gong T, Li Y Zheng . Shortening passengers’ travel time: a dynamic metro train scheduling approach using deep reinforcement learning. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 5): 5282–5295
22	J, Wang J, Ji Z, Jiang L Sun . Traffic flow prediction based on spatiotemporal potential energy fields. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 9): 9073–9087
23	J, Ji J, Wang C, Huang J, Wu B, Xu Z, Wu J, Zhang Y Zheng . Spatio-temporal self-supervised learning for traffic flow prediction. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023, 4356–4364
24	Y, Bengio A, Lodi A Prouvost . Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 2021, 290( 2): 405–421
25	Mele U, Junior Gambardella L, Maria R Montemanni . Machine learning approaches for the traveling salesman problem: a survey. In: Proceedings of the 8th International Conference on Industrial Engineering and Applications (Europe). 2021, 182–186
26	Y, Shi Y Zhang . The neural network methods for solving traveling salesman problem. Procedia Computer Science, 2022, 199: 681–686
27	Y, Yang A Whinston . A survey on reinforcement learning for combinatorial optimization. In: Proceedings of IEEE World Conference on Applied Intelligence and Computing. 2023, 131–136
28	R, Matai S P, Singh M L Mittal . Traveling salesman problem: an overview of applications, formulations, and solution approaches. In: Davendra D, ed. Traveling Salesman Problem, Theory and Applications. Rijeka: InTech, 2010, 1
29	W L Eastman . Linear programming with pattern constraints. Harvard University, Dissertation, 1958
30	D L, Miller J F Pekny . Exact solution of large asymmetric traveling salesman problems. Science, 1991, 251( 4995): 754–761
31	M, Held R M Karp . A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 1962, 10( 1): 196–210
32	G Laporte . The traveling salesman problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 1992, 59( 2): 231–247
33	G, Dantzig R, Fulkerson S Johnson . Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 1954, 2( 4): 393–410
34	C E, Miller A W, Tucker R A Zemlin . Integer programming formulation of traveling salesman problems. Journal of the ACM, 1960, 7( 4): 326–329
35	G, Gutin A P Punnen . The Traveling Salesman Problem and Its Variations. New York: Springer, 2007
36	D, Applegate R, Bixby V, Chvatal W Cook . Concorde TSP solver. See Math. uwaterloo. ca/tsp/concorde website, 2006
37	D J, Rosenkrantz R E, Stearns II P M Lewis . An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 1977, 6( 3): 563–581
38	D S, Johnson L A McGeoch . The traveling salesman problem: a case study in local optimization. Local Search in Combinatorial Optimization, 1997, 1( 1): 215–310
39	C, Voudouris E Tsang . Guided local search and its application to the traveling salesman problem. European Journal of Operational Research, 1999, 113( 2): 469–499
40	C Nilsson . Heuristics for the traveling salesman problem. Linkoping University, 2003, 38( 0085-9): 26
41	J, Sui S, Ding R, Liu L, Xu D Bu . Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. In: Proceedings of the 13th Asian Conference on Machine Learning. 2021, 1301–1316
42	D S Johnson . Local optimization and the traveling salesman problem. In: Proceedings of the 17th International Colloquium on Automata, Languages, and Programming. 1990, 446–461
43	K Helsgaun . An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 2000, 126( 1): 106–130
44	K Helsgaun . General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 2009, 1( 2-3): 119–163
45	K Helsgaun . An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems: technical report. Roskilde: Roskilde University, 2017, 966–980
46	O, Vinyals M, Fortunato N Jaitly . Pointer networks. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. 2015, 2692–2700
47	I, Bello H, Pham Q V, Le M, Norouzi S Bengio . Neural combinatorial optimization with reinforcement learning. In: Proceedings of the 5th International Conference on Learning Representations. 2017
48	M, Nazari A, Oroojlooy M, Takáč L Snyder . Reinforcement learning for solving the vehicle routing problem. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, 9861–9871
49	M, Deudon P, Cournut A, Lacoste Y, Adulyasak L M Rousseau . Learning heuristics for the TSP by policy gradient. In: Proceedings of the 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 2018, 170–181
50	W, Kool Hoof H, Van M Welling . Attention, learn to solve routing problems!2018, arXiv preprint arXiv: 1803.08475
51	Y D, Kwon J, Choo B, Kim I, Yoon Y, Gwon S Min . POMO: policy optimization with multiple optima for reinforcement learning. In: Proceedings of the 34th Conference on Neural Information Processing Systems. 2020, 21188–21198
52	X, Bresson T Laurent . The transformer network for the traveling salesman problem. 2021, arXiv preprint arXiv: 2103.03012
53	X, Pan Y, Jin Y, Ding M, Feng L, Zhao L, Song J Bian . H-TSP: hierarchically solving the large-scale traveling salesman problem. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023, 9345–9353
54	A, Lischka J, Wu R, Basso M H, Chehreghani B Kulcsár . Less is more-on the importance of sparsification for transformers and graph neural networks for TSP. 2024, arXiv preprint arXiv: 2403.17159
55	F, Luo X, Lin F, Liu Q, Zhang Z Wang . Neural combinatorial optimization with heavy decoder: toward large scale generalization. In: Proceedings of the 37th Conference on Neural Information Processing Systems. 2024
56	H, Dai E B, Khalil Y, Zhang B, Dilkina L Song . Learning combinatorial optimization algorithms over graphs. In: Proceedings of the 31st Conference on Neural Information Processing Systems. 2017, 30
57	Q, Ma S, Ge D, He D, Thaker I Drori . Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. 2019, arXiv preprint arXiv: 1911.04936
58	I, Drori A, Kharkar W R, Sickinger B, Kates Q, Ma S, Ge E, Dolev B, Dietrich D P, Williamson M Udell . Learning to solve combinatorial optimization problems on real-world graphs in linear time. In: Proceedings of the 19th IEEE International Conference on Machine Learning and Applications. 2020, 19–24
59	W, Ouyang Y, Wang P, Weng S Han . Generalization in deep RL for TSP problems via equivariance and local search. 2021, arXiv preprint arXiv: 2110.03595
60	Z, Sun Y Yang . DIFUSCO: graph-based diffusion solvers for combinatorial optimization. In: Proceedings of the 37th International Conference on Neural Information Processing Systems. 2023, 164
61	H, Liu Y, Kuang J, Wang X, Li Y, Zhang F Wu . Promoting generalization for exact solvers via adversarial instance augmentation. 2023, arXiv preprint arXiv: 2310.14161
62	Y, Wu W, Song Z, Cao J, Zhang A Lim . Learning improvement heuristics for solving routing problems. 2019, arXiv preprint arXiv: 1912.05784
63	P R D O, Costa J, Rhuggenaath Y, Zhang A Akcay . Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In: Proceedings of the 12th Asian Conference on Machine Learning. 2020, 465–480
64	Y, Ma J, Li Z, Cao W, Song L, Zhang Z, Chen J Tang . Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In: Proceedings of the 34th Conference on Neural Information Processing Systems. 2021, 11096–11107
65	C K, Joshi T, Laurent X Bresson . An efficient graph convolutional network technique for the travelling salesman problem. 2019, arXiv preprint arXiv: 1906.01227
66	B, Hudson Q, Li M, Malencia A Prorok . Graph neural network guided local search for the traveling salesperson problem. 2021, arXiv preprint arXiv: 2110.05291
67	J, Sui S, Ding B, Xia R, Liu D Bu . NeuralGLS: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Computing and Applications, 2024, 36( 17): 9687–9706
68	Z H, Fu K B, Qiu H Zha . Generalize a small pre-trained model to arbitrarily large TSP instances. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 7474–7482
69	S, Sanyal K Roy . Neuro-Ising: accelerating large-scale traveling salesman problems via graph neural network guided localized Ising solvers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41( 12): 5408–5420
70	J, Zheng K, He J, Zhou Y, Jin C M Li . Combining reinforcement learning with Lin-Kernighan-Helsgaun algorithm for the traveling salesman problem. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 12445–12452
71	L, Xin W, Song Z, Cao J Zhang . NeuroLKH: combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem. In: Proceedings of the 35th International Conference on Neural Information Processing Systems. 2021, 572
72	J, Zheng K, He J, Zhou Y, Jin C M Li . Reinforced Lin–Kernighan–Helsgaun algorithms for the traveling salesman problems. Knowledge-Based Systems, 2023, 260: 110144
73	F, Liu X, Tong M, Yuan Q Zhang . Algorithm evolution using large language model. 2023, arXiv preprint arXiv: 2311.15249
74	H, Ye J, Wang Z, Cao F, Berto C, Hua H, Kim J, Park G Song . Large language models as hyper-heuristics for combinatorial optimization. 2024, arXiv preprint arXiv: 2402.01145
75	F, Liu X, Tong M, Yuan X, Lin F, Luo Z, Wang Z, Lu Q Zhang . Evolution of heuristics: towards efficient automatic algorithm design using large language mode. 2024, arXiv preprint arXiv: 2401.02051
76	D, Bahdanau K, Cho Y Bengio . Neural machine translation by jointly learning to align and translate. In: Proceedings of the 3rd International Conference on Learning Representations. 2015
77	R Sato . A survey on the expressive power of graph neural networks. 2020, arXiv preprint arXiv: 2003.04078
78	A, Vaswani N, Shazeer N, Parmar J, Uszkoreit L, Jones A N, Gomez Ł, Kaiser I Polosukhin . Attention is all you need. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 6000–6010
79	H, Naveed A U, Khan S, Qiu M, Saqib S, Anwar M, Usman N, Akhtar N, Barnes A Mian . A comprehensive overview of large language models. 2024, arXiv preprint arXiv: 2307.06435
80	D Hu . An introductory survey on attention mechanisms in NLP problems. In: Proceedings of Intelligent Systems Conference (IntelliSys) Volume 2. 2020, 432–448
81	M T, Luong H, Pham C D Manning . Effective approaches to attention-based neural machine translation. In: Proceedings of 2015 Conference on Empirical Methods in Natural Language Processing. 2015
82	A, Sperduti A Starita . Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 1997, 8( 3): 714–735
83	I I, Baskin V A, Palyulin N S Zefirov . A neural device for searching direct correlations between structures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, 1997, 37( 4): 715–721
84	M, Gori G, Monfardini F Scarselli . A new model for learning in graph domains. In: Proceedings of IEEE International Joint Conference on Neural Networks. 2005, 729–734
85	F, Scarselli M, Gori A C, Tsoi M, Hagenbuchner G Monfardini . The graph neural network model. IEEE Transactions on Neural Networks, 2009, 20( 1): 61–80
86	D, Duvenaud D, Maclaurin J, Aguilera-Iparraguirre R, Gómez-Bombarelli T, Hirzel A, Aspuru-Guzik R P Adams . Convolutional networks on graphs for learning molecular fingerprints. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. 2015
87	Y, Li D, Tarlow M, Brockschmidt R S Zemel . Gated graph sequence neural networks. In: Proceedings of the 4th International Conference on Learning Representations. 2016
88	H, Dai B, Dai L Song . Discriminative embeddings of latent variable models for structured data. In: Proceedings of the 33rd International Conference on Machine Learning. 2016, 2702–2711
89	J, Gilmer S S, Schoenholz P F, Riley O, Vinyals G E Dahl . Neural message passing for quantum chemistry. In: Proceedings of the 34th International Conference on Machine Learning. 2017, 1263–1272
90	W L, Hamilton R, Ying J Leskovec . Inductive representation learning on large graphs. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 1025–1035
91	T N, Kipf M Welling . Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations. 2017
92	X, Bresson T Laurent . Residual gated graph convnets. 2017, arXiv preprint arXiv: 1711.07553
93	P, Velickovic G, Cucurull A, Casanova A, Romero P, Liò Y Bengio . Graph attention networks. In: Proceedings of the 6th International Conference on Learning Representations. 2018
94	W X, Zhao K, Zhou J, Li T, Tang X, Wang Y, Hou Y, Min B, Zhang J, Zhang Z, Dong Y, Du C, Yang Y, Chen Z, Chen J, Jiang R, Ren Y, Li X, Tang Z, Liu P, Liu J Y, Nie J R Wen . A survey of large language models. 2023, arXiv preprint arXiv: 2303.18223
95	B, Min H, Ross E, Sulem A P B, Veyseh T H, Nguyen O, Sainz E, Agirre I, Heinz D Roth . Recent advances in natural language processing via large pre-trained language models: a survey. ACM Computing Surveys, 2024, 56( 2): 30
96	Tian H, Lu W, Li T O, Tang X, Cheung S C, Klein J, Bissyandé T F. Is ChatGPT the ultimate programming assistant-how far is it? 2023, arXiv preprint arXiv: 2304.11938
97	K M, Jablonka P, Schwaller A, Ortega-Guerrero B Smit . Is GPT-3 all you need for low-data discovery in chemistry? See Chemrxiv. org/engage/chemrxiv/article-details/63eb5a669da0bc6b33e97a35 website, 2023
98	P, Lee S, Bubeck J Petro . Benefits, limits, and risks of GPT-4 as an AI chatbot for medicine. New England Journal of Medicine, 2023, 388( 13): 1233–1239
99	H, Nori N, King S M, McKinney D, Carignan E Horvitz . Capabilities of GPT-4 on medical challenge problems. 2023, arXiv preprint arXiv: 2303.13375
100	K, Cheng Q, Guo Y, He Y, Lu S, Gu H Wu . Exploring the potential of GPT-4 in biomedical engineering: the dawn of a new era. Annals of Biomedical Engineering, 2023, 51( 8): 1645–1653
101	J, Blocklove S, Garg R, Karri H Pearce . Chip-chat: challenges and opportunities in conversational hardware design. In: Proceedings of the 5th ACM/IEEE Workshop on Machine Learning for CAD. 2023, 1–6
102	Z, He H, Wu X, Zhang X, Yao S, Zheng H, Zheng B Yu . ChatEDA: a large language model powered autonomous agent for EDA. 2023, arXiv preprint arXiv: 2308.10204
103	D, Shah M R, Equi B, Osiński F, Xia B, Ichter S Levine . Navigation with large language models: semantic guesswork as a heuristic for planning. In: Proceedings of the 7th Conference on Robot Learning. 2023
104	H, Xiao P Wang . LLM A: human in the loop large language models enabled A search for robotics. 2023, arXiv preprint arXiv: 2312.01797
105	C, Yang X, Wang Y, Lu H, Liu Q V, Le D, Zhou X Chen . Large language models as optimizers. In: Proceedings of ICLR 2024 Conference. 2024
106	X, Wu Y, Zhong J, Wu B, Jiang K C Tan . Large language model-enhanced algorithm selection: towards comprehensive algorithm representation. In: Proceedings of the 33rd International Joint Conference on Artificial Intelligence. 2024
107	F, Liu X, Lin Z, Wang S, Yao X, Tong M, Yuan Q Zhang . Large language model for multi-objective evolutionary optimization. 2024, arXiv preprint arXiv: 2310.12541
108	I, Sutskever O, Vinyals Q V Le . Sequence to sequence learning with neural networks. In: Proceedings of the 27th International Conference on Neural Information Processing Systems. 2014, 3104–3112
109	D E, Rumelhart G E, Hinton R J Williams . Learning representations by back-propagating errors. Nature, 1986, 323( 6088): 533–536
110	S, Hochreiter J Schmidhuber . Long short-term memory. Neural Computation, 1997, 9( 8): 1735–1780
111	V, Mnih A P, Badia M, Mirza A, Graves T, Harley T P, Lillicrap D, Silver K Kavukcuoglu . Asynchronous methods for deep reinforcement learning. In: Proceedings of the 33rd International Conference on Machine Learning. 2016, 1928–1937
112	N Christofides . Worst-case analysis of a new heuristic for the travelling salesman problem. Pittsburgh: Carnegie-Mellon University, 1976
113	Perron L, Furnon V. OR-Tools. See developers.google.com/optimization/ website. 2023
114	R J Williams . Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 1992, 8( 3-4): 229–256
115	D P, Kingma J Ba . Adam: a method for stochastic optimization. In: Proceedings of the 3rd International Conference on Learning Representations. 2015
116	R S, Sutton A G Barto . Reinforcement learning: an introduction. Robotica, 1999, 17( 2): 229–235
117	G Reinelt . TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 1991, 3( 4): 376–384
118	J, Ho A, Jain P Abbeel . Denoising diffusion probabilistic models. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. 2020, 574
119	E, Perez F, Strub Vries H, De V, Dumoulin A Courville . FiLM: visual reasoning with a general conditioning layer. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018
120	A Misevičius . Using iterated Tabu search for the traveling salesman problem. Information Technology and Control, 2004, 32( 3): 29–40
121	P A Vikhar . Evolutionary algorithms: a critical review and its future prospects. In: Proceedings of International Conference on Global Trends in Signal Processing, Information Computing and Communication. 2016, 261–265
122	F, Arnold K Sörensen . Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 2019, 105: 32–46

[1]

Download

[1]	Bingbing DONG, Chenyang BU, Yi ZHU, Shengwei JI, Xindong WU. Simplified multi-view graph neural network for multilingual knowledge graph completion[J]. Front. Comput. Sci., 2025, 19(7): 197324-.
[2]	Yanping ZHENG, Lu YI, Zhewei WEI. A survey of dynamic graph neural networks[J]. Front. Comput. Sci., 2025, 19(6): 196323-.
[3]	Yanlin LI, Wantong JIAO, Ruihan LIU, Xuejin DENG, Feng ZHU, Weiwei XUE. Expanding the sequence spaces of synthetic binding protein using deep learning-based framework ProteinMPNN[J]. Front. Comput. Sci., 2025, 19(5): 195903-.
[4]	Mengting NIU, Yaojia CHEN, Chunyu WANG, Quan ZOU, Lei XU. Computational approaches for circRNA-disease association prediction: a review[J]. Front. Comput. Sci., 2025, 19(4): 194904-.
[5]	Yao WU, Hong HUANG, Yu SONG, Hai JIN. Soft-GNN: towards robust graph neural networks via self-adaptive data utilization[J]. Front. Comput. Sci., 2025, 19(4): 194311-.
[6]	Tao HE, Ming LIU, Yixin CAO, Zekun WANG, Zihao ZHENG, Bing QIN. Exploring & exploiting high-order graph structure for sparse knowledge graph completion[J]. Front. Comput. Sci., 2025, 19(2): 192306-.
[7]	Jingyu LIU, Shi CHEN, Li SHEN. A comprehensive survey on graph neural network accelerators[J]. Front. Comput. Sci., 2025, 19(2): 192104-.
[8]	Xiaosong HAN, Mengchen CAO, Dong XU, Xiaoyue FENG, Yanchun LIANG, Xiaoduo LANG, Renchu GUAN. SEOE: an option graph based semantically embedding method for prenatal depression detection[J]. Front. Comput. Sci., 2024, 18(6): 186911-.
[9]	Liangxuan ZHU, Han LI, Xuelin ZHANG, Lingjuan WU, Hong CHEN. Neural partially linear additive model[J]. Front. Comput. Sci., 2024, 18(6): 186334-.
[10]	Lingling ZHAO, Shitao SONG, Pengyan WANG, Chunyu WANG, Junjie WANG, Maozu GUO. A MLP-Mixer and mixture of expert model for remaining useful life prediction of lithium-ion batteries[J]. Front. Comput. Sci., 2024, 18(5): 185329-.
[11]	Junfei TANG, Ran SONG, Yuxin HUANG, Shengxiang GAO, Zhengtao YU. Semantic-aware entity alignment for low resource language knowledge graph[J]. Front. Comput. Sci., 2024, 18(4): 184319-.
[12]	Enes DEDEOGLU, Himmet Toprak KESGIN, Mehmet Fatih AMASYALI. A robust optimization method for label noisy datasets based on adaptive threshold: Adaptive-k[J]. Front. Comput. Sci., 2024, 18(4): 184315-.
[13]	Hengyu LIU, Tiancheng ZHANG, Fan LI, Minghe YU, Ge YU. A probabilistic generative model for tracking multi-knowledge concept mastery probability[J]. Front. Comput. Sci., 2024, 18(3): 183602-.
[14]	Mingzhi YUAN, Kexue FU, Zhihao LI, Manning WANG. Decoupled deep hough voting for point cloud registration[J]. Front. Comput. Sci., 2024, 18(2): 182703-.
[15]	Mingzhen LI, Changxi LIU, Jianjin LIAO, Xuegui ZHENG, Hailong YANG, Rujun SUN, Jun XU, Lin GAN, Guangwen YANG, Zhongzhi LUAN, Depei QIAN. Towards optimized tensor code generation for deep learning on sunway many-core processor[J]. Front. Comput. Sci., 2024, 18(2): 182101-.

Viewed

Full text

Abstract

Cited

Shared

Discussed