Survey on Neural Routing Solvers

Yunpeng Ba; Xi Lin; Changliang Zhou; Ruihao Zheng; Zhenkun Wang; Xinyan Liang; Zhichao Lu; Jianyong Sun

math.OCFeb 25, 2026

Survey on Neural Routing Solvers

Authors: Yunpeng Ba, Xi Lin, Changliang Zhou, Ruihao Zheng, Zhenkun Wang, Xinyan Liang, Zhichao Lu, Jianyong Sun,

Organizations: Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China. · the School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China. · the Institute of Big Data Science and Industry, Shanxi University, Taiyuan, China. · the Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China.

Abstract

Neural routing solvers (NRSs) that leverage deep learning to tackle vehicle routing problems have demonstrated notable potential for practical applications. By learning implicit heuristic rules from data, NRSs replace the handcrafted counterparts in classic heuristic frameworks, thereby reducing reliance on costly manual design and trial-and-error adjustments. This survey makes two main contributions: (1) The heuristic nature of NRSs is highlighted, and existing NRSs are reviewed from the perspective of heuristics. A hierarchical taxonomy based on heuristic principles is further introduced. (2) A generalization-focused evaluation pipeline is proposed to address limitations of the conventional pipeline. Comparative benchmarking of representative NRSs across both pipelines uncovers a series of previously unreported gaps in current research.

Figures & tables

Exisiting Surveys	Unified Perspective †	Algorithm-Level Perspective ‡	Description
Learning Perspective	✓	$\times$	•Model Structures : GNN, Transformer, etc. [ 13 , 14 , 15 , 16 , 17 , 18 ] ; • Learning Paradigms : SL, RL, etc. [ 14 , 19 , 20 , 21 , 22 , 23 ] ; • Generation Paradigms : AR, NAR, etc. [ 15 , 22 ] ; • Reliance on Learned Modules : E2E, Hybrid, etc. [ 19 , 24 , 21 , 16 , 25 , 18 ] .
Hybrid Perspective (Heuristic + Others)	$\times$	✓	•Residual Categories : Grouping NRSs with failed-to-identify heuristic categories as “Predict” [ 26 ] / “Hybrid” [ 27 , 28 ] / “Non-DRL” [ 29 ] / “Decomposition” [ 30 ] ; • Self-Contradiction : Treating iterative GNN-based NRSs as construction-based [ 31 , 32 , 33 ] ; • Scope Limitations : Only concerning RL -based [ 34 , 35 , 36 , 37 ] or Transformer -based [ 38 ] NRSs.
Heuristic Perspective (Ours)	✓	✓	•Hierarchical Taxonomy : Detailing how solutions are constructed / improved; • Progression Identification : Tracing NRSs from traditional heuristics; • Category-Specific and Category-agnostic Insights : Transferring from heuristics to NRSs.

TABLE I: Comparisons of Existing Surveys for NRSs

Fig. 1: Hierarchical structure of the heuristic taxonomy. There are two main heuristic categories: the non-iterative construction-based methods and the iterative improvement-based methods. Construction-based methods can be further divided into single-stage and two-stage methods, based on whether the original graph is decomposed. Improvement-based methods can be further split into single-solution-based and population-based methods, depending on the number of solutions maintained during the improvement process.

Fig. 2: Hierarchical structure of the proposed NRS taxonomy. Each subcategory is presented with the proportion of existing studies. The statistics are obtained from Google Scholar between January 1, 2015, and November 17, 2025. The paper list is further filtered by content relevance and supplemented with relevant experience and subsequent publications. Finally, there are 439 papers, including 344 methods across categories, as well as other related studies such as surveys and benchmarks. Note that an NRS may be counted in multiple subcategories due to its use of multiple inference strategies.

Panel of Figure 4 — Fig. 3: Illustration of subcategories of single-stage methods. (a) For appending methods, the selected nodes are linked to the end of partial solutions one at a time. (b) For insertion methods, the positions are not limited.

Tertiary	Generation	Solvable	Backbone	Learning	Method	Year	Remarks
Category	Paradigm	VRPs	Backbone	Paradigm	Method	Year	Remarks
Appending	AR	TSP	LSTM	SL	Ptr-Net [ 49 ]	2015	The first NRS.
		TSP	LSTM	RL	PN-RL [ 54 ]	2017	The first RL-based NRS.
		TSP, CVRP,	Transformer	RL	AM [ 39 ]	2019	The first NRS with the Transformer
		OP, SDVRP,					encoder-decoder model.
		(S)PCTSP			MDAM [ 60 ]	2021	A multi-decoder framework with re-embedding.

TABLE II: Representative Construction-based Single-stage NRSs

Role of the	Generation	Solvable	Backbone	Learning	Method	Year	Remarks
First Stage	Paradigm	VRPs	Backbone	Paradigm	Method	Year	Remarks
Scale Reduction	AR	TSP	CNN,	RL	H-TSP [ 82 ]	2023	A two-stage NRS capable for TSP instances with
			Transformer				10K nodes.
Scale Reduction;	AR	CVRP	Transformer	RL	TAM-AM [ 83 ]	2023	A two-stage NRS capable for VRP instances with
Constraint Handling							over 5K nodes.

TABLE III: Representative Construction-based Two-stage NRSs

Panel of Figure 7 — Fig. 4: Illustration of subcategories of single-solution-based methods. (a) For small neighborhood methods, an example with the 2-opt operator is presented. At each iteration, two edges are replaced. (b) For large neighborhood methods, the classic destroy-and-repair process is illustrated. At each iteration, some nodes are picked out and then reinserted one by one in a prescribed order (indicated by the numbered labels).

Quaternary	Generation	Solvable	Backbone	Learning	Method	Year	Remarks
Category	Paradigm	VRPs	Backbone	Paradigm	Method	Year	Remarks
Immediate	AR	CVRP	LSTM	RL	NeuRewriter [ 92 ]	2019	Improvement with separate policies to select node-pairs.
		TSP, CVRP	Transformer	RL	LIH [ 47 ]	2021	Improvement with a single policy to select node-pairs.
		TSP, CVRP	Transformer	RL	DACT [ 93 ]	2021	Improvement with cyclic positional encoding.
		TSP	GCN, FiLM,	RL	Neural-3-OPT [ 94 ]	2021	Improvement with the 3-opt operator.
			LSTM

TABLE IV: Representative Improvement-based Single-solution-based Small Neighborhood NRSs

Quaternary	Generation	Solvable	Backbone	Learning	Method	Year	Remarks
Category	Paradigm	VRPs	Backbone	Paradigm	Method	Year	Remarks
	AR	CVRP,	Transformer	RL	NLNS [ 104 ]	2020	LNS with two handcrafted destroy and
Unrestricted		SDVRP					one learned repair criteria.
Direct LNS		CVRP(TW)	GAT, GRU	RL	EGATE [ 105 ]	2020	LNS with a learned criteria for both destroy and repair.
		CVRP	Transformer	RL	L2I [ 106 ]	2020	ILS with both small and large neighborhood search.
		TSP, CVRP	Transformer	SL	L2C-Insert ‡ [ 79 ]	2025	LNS with a handcrafted destroy and a learned repair criteria.

TABLE V: Representative Improvement-based Single-solution-based Large Neighborhood NRSs

Search	Generation	Solvable	Backbone	Learning	Method	Year	Remarks
Space	Paradigm	VRPs	Backbone	Paradigm	Method	Year	Remarks
Continuous	NAR	TSP, CVRP	GRU	SL	CVAE-Opt [ 128 ]	2021	Latent space search with DE.
Continuous	NAR	TSP, CVRP	Transformer	RL	COMPASS [ 129 ]	2023	Latent space search with CMA-ES.
Discrete	NAR	(PC)TSP, (S)OP,	GNN	RL	DeepACO [ 130 ]	2023	Learning heuristic measures in ACO with RL.
Discrete	NAR	CVRP(TW)	GNN	GFlowNet	GFACS [ 131 ]	2025	Learning heuristic measures in ACO with GFlowNet.

TABLE VI: Representative Improvement-based Population-based NRSs

Category				Method
Primary	Secondary	Tertiary	Quaternary
Construction	Single-stage	Appending	/	BQ [ 51 ]
				LEHD † [ 50 ]
				SIL † [ 65 ]
				ICAM [ 53 ]
				ELG [ 66 ]

TABLE VII: Selected NRSs for Comparative Evaluation

Method	TSP 100		TSP 1K		TSP 10K
Method	Gap	Time	Gap	Time	Gap	Time
LKH-3	0.000%	10.97m	0.000%	5.69m	0.000%	49.34m
Nearest Neighbor	24.722%	6.72s	25.022%	0.97s	23.864%	2.29s
Random Insertion	9.672%	2.04s	13.096%	0.46s	13.966%	4.64s
↑ BQ greedy	0.348%	1.13m	2.294%	1.19m	/	/
↑ LEHD ∗ greedy	0.576%	26.84s	3.116%	1.64m	/	/

TABLE VIII: Experimental Results of Conventional Evaluation Pipeline

Method

(0,1K)

[1K, 10K)

[10K, 100K]

Total

Gap

Time

Solved

Gap

Time

Solved

Gap

Time

Solved

Gap

Solved

TSP

Nearest Neighbor

25.29%

0.01s

69/69

26.66%

0.29s

109/109

25.01%

22.60s

50/50

25.88%

228/228

Random Insertion

10.60%

0.00s

69/69

15.32%

0.05s

109/109

16.37%

8.93s

50/50

14.12%

228/228

LKH-3 ↓ t=n/3, runs=1

0.00%

7.88s

69/69

0.01%

631.34s

109/109

0.08%

14600.50s

50/50

0.03%

228/228

LKH-3 ↓ t=n/3, runs=1

0.00%

9.25s

69/69

0.01%

600.36s

109/109

0.05%

10800.24s

50/50

0.02%

228/228

5.00%

2.51s

68/69

19.03%

22.74s

92/109

52.00%

187.81s

4/50

14.02%

164/228

TABLE IX: Experimental Results of the Proposed Evaluation Pipeline

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Link	License
LKH-3 [ 136 ]	http://webhotel4.ruc.dk/~keld/research/LKH-3/	Available for academic research use
HGS [ 137 ]	https://github.com/vidalt/HGS-CVRP	MIT License
AILS-II [ 138 ]	https://github.com/INFORMSJoC/2023.0106	MIT License
BQ [ 51 ]	https://github.com/naver/bq-nco	CC BY-NC-SA 4.0 license
LEHD [ 50 ]	https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/LEHD	MIT License
SIL [ 65 ]	https://github.com/CIAM-Group/SIL	MIT License

Appendix

TABLE X: Sources of the Adopted Methods

Benchmark	Instance	BKS
TSPLIB	http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/	http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html
National	https://www.math.uwaterloo.ca/tsp/world/countries.html	https://www.math.uwaterloo.ca/tsp/world/summary.html
VLSI	https://www.math.uwaterloo.ca/tsp/vlsi/index.html	https://www.math.uwaterloo.ca/tsp/vlsi/summary.html
8th DIMACS	http://dimacs.rutgers.edu/archive/Challenges/TSP/download.html	http://webhotel4.ruc.dk/~keld/research/LKH/DIMACS_results.html
Implementation Challenge		http://dimacs.rutgers.edu/archive/Challenges/TSP/opts.html
CVRPLIB	https://galgos.inf.puc-rio.br/cvrplib/index.php/en/instances	Provided in the corresponding .vrp files of the instances.

Appendix

TABLE XI: Sources of the Adopted Benchmarks

Method	(0,1K)			[1K, 10K)			[10K, 100K]			Total
Method	Gap	Time	Solved	Gap	Time	Solved	Gap	Time	Solved	Gap	Solved
Nearest Neighbor	25.29%	0.01s	69/69	26.66%	0.29s	109/109	25.01%	22.60s	50/50	25.88%	228/228
Random Insertion	10.60%	0.00s	69/69	15.32%	0.05s	109/109	16.37%	8.93s	50/50	14.12%	228/228
LKH-3 ↓ t=n/3, runs=1	0.00%	7.88s	69/69	0.01%	631.34s	109/109	0.08%	14600.50s	50/50	0.03%	228/228
LKH-3 ↓ t=n/3, runs=1	0.00%	9.25s	69/69	0.01%	600.36s	109/109	0.05%	10800.24s	50/50	0.02%	228/228
BQ	5.00%	2.51s	68/69	19.03%	22.74s	92/109	52.00%	187.81s	4/50	14.02%	164/228

Appendix

TABLE XII: Detailed Experimental Results of the Proposed Evaluation Pipeline for TSP

Method	(0,1K)			[1K, 10K)			[10K, 100K]			Total
Method	Gap	Time	Solved	Gap	Time	Solved	Gap	Time	Solved	Gap	Solved
Nearest Neighbor	21.17%	0.03s	99/99	15.18%	1.08s	5/5	11.80%	14.63s	6/6	20.39%	110/110
Random Insertion	75.00%	0.00s	36/99	/	/	0/5	/	/	0/6	75.00%	36/110
HGS t=n/3	0.29%	111.24s	99/99	3.59%	1428.41s	5/5	7.86%	6926.41s	6/6	0.85%	110/110
AILS-II t=n/3	0.57%	133.95s	99/99	1.58%	1388.42s	5/5	1.58%	5646.48s	6/6	0.68%	110/110
BQ	8.87%	3.63s	99/99	20.28%	39.97s	5/5	41.52%	202.69s	5/6	10.89%	109/110

Appendix

TABLE XIII: Detailed Experimental Results of the Proposed Evaluation Pipeline for CVRP

Neural Combinatorial Optimization

Neural combinatorial optimization uses neural networks to find high-quality solutions to discrete problems such as routing, scheduling, and graph partitioning.

See all 137 papers

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems
Feb 17, 2026Jieyi Bi, Zhiguang Cao, Jianan Zhou +5Neural Combinatorial Optimization Constrained Optimization
Nanyang Technological University · MIT · Singapore Management University +2
Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems
Mar 8, 2026Zhenwei Wang, Tiehua Zhang, Ning Xue +3Vehicle Routing Neural Combinatorial Optimization
School of Computer Science, University of Nottingham Ningbo China, Ningbo, 315100, China · School of Computer Science and Technology, Tongji University, Shanghai, 200092, China · Computational Optimisation and Learning Lab, School of Computer Science, University of Nottingham, NG8 1BB Nottingham, U.K. +1
Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver
May 11, 2026Canhong Yu, Changliang Zhou, Rongsheng Chen +2Neural Network Optimization Combinatorial Optimization
College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, China · School of Automation and Intelligent Manufacturing, Southern University of Science and Technology, Shenzhen, China · Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and Technology, Southern University of Science and Technology, Shenzhen, China +1

Feb 17, 2026J/K move · Enter open · S save

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Jieyi Bi, Zhiguang Cao, Jianan Zhou, Wen Song+4

Nanyang Technological University · MIT · Singapore Management University+2

Neural Combinatorial Optimization Constrained Optimization Vehicle Routing

Open paper AskPDF arXiv

Neural solvers have achieved impressive progress in addressing simple routing problems, particularly excelling in computational efficiency. However, their advantages under complex constraints remain nascent, for which current constraint-handling schemes via feasibility masking or implicit feasibility awareness can be inefficient or inapplicable for hard constraints. In this paper, we present Construct-and-Refine (CaR), the first general and efficient constraint-handling framework for neural routing solvers based on explicit learning-based feasibility refinement. Unlike prior construction-search hybrids that target reducing optimality gaps through heavy improvements yet still struggle with hard constraints, CaR achieves efficient constraint handling by designing a joint training framework that guides the construction module to generate diverse and high-quality solutions well-suited for a lightweight improvement process, e.g., 10 steps versus 5k steps in prior work. Moreover, CaR presents the first use of construction-improvement-shared representation, enabling potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. We evaluate CaR on typical hard routing constraints to showcase its broader applicability. Results demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-art solvers.

Abstract

Neural Combinatorial Optimization

Explore similar work

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems

Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver