Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Jieyi Bi; Zhiguang Cao; Jianan Zhou; Wen Song; Yaoxin Wu; Jie Zhang; Yining Ma; Cathy Wu

cs.AIFeb 17, 2026

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Authors: Jieyi Bi, Zhiguang Cao, Jianan Zhou, Wen Song, Yaoxin Wu, Jie Zhang, Yining Ma, Cathy Wu

Organizations: Nanyang Technological University · MIT · Singapore Management University · Shandong University ·

Abstract

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.

Figures & tables

Methods	VRP applicability		Research focus		Feasibility	Feasibility Awareness			Feasibility
Methods	Simple	Complex	Optimality	Feasibility	Masking	Penalty	Features	Shared Rep.	Refinement
Most existing neural solvers	$\checkmark$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$	$\times$	$\times$
(e.g. POMO, UDC, LCP, RL4CO, NCS)	$\checkmark$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$	$\times$	$\times$
NeuOpt-GIRE ( Ma et al., 2023 )	$\checkmark$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$
Tang et al. (2022)	$\times$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\times$	$\times$	$\times$
MUSLA ( Chen et al., 2024 )	$\times$	$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$	$\times$	$\checkmark$	$\times$	$\times$

Table 1: Comparison between CaR and other existing neural solvers. CaR is the first to cover both simple and complex VRPs by combining flexible ‡ masking, shared-representation to implicitly enhance feasibility awareness, and explicit feasibility refinement.

Figure 1: Overall framework of CaR, where the construction module provides diverse and high-quality solutions for the refinement module to generate better solutions.

Figure 2: Overview of the unified network architecture in CaR. Blue dashed arrows indicate information flow specific to refinement, while purple dashed arrows indicate flow exclusive to construction.

Method		#Params	Paradigm §	n=50				n=100
Method		#Params	Paradigm §	Obj. $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$	Time	Obj. $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$	Time
TSPTW	LKH-3 (max trials $=$ 100)	/	I	25.590	0.004%	11.88%	7m	46.625	0.103%	31.05%	27m
	LKH-3 (max trials $=$ 10000)	/	I	25.611	$\diamond$	0.12%	7h	46.858	$\diamond$	0.13%	1.4d
	OR-Tools †	/	I	25.763	-0.001%	65.72%	2.4h	46.424	0.026%	97.45%	12m
	Greedy-L	/	C	/	/	100.00%	21.8s	/	/	100.00%	1m
	Greedy-C	/	C	26.394	1.534%	72.55%	4.5s	51.945	9.651%	99.85%	11.4s

Table 2: Results on complex VRPs: best are bolded ; best within 1 min are shaded to show solver efficiency.

Panel of Figure 3 — Figure 3: Performance over time on TSPTW-100 (left) and CVRPBLTW-100 (right). For CVRPBLTW, POMO+EAS+SGBS and CaR always achieve $0\%$ infeasibility due to feasibility guarantee by masking. Dots with black circles represent results reported in Table 2 .

Figure 4: CVRPLIB results.

Table 7

Problem	$\mathcal{L}_{\text{DIV}}$	Gap $\downarrow$	Infsb% $\downarrow$
CVRP	$\times$	0.325%	0.00%
CVRP	$\checkmark$	0.259%	0.00%
TSPTW	$\times$	0.421%	0.58%
TSPTW	$\checkmark$	0.014%	0.01%

Table 5: Effects of

\mathcal{L}_{\text{DIV}}

Table 9

Method	Train Scale	Test Scale	Gap $\downarrow$	Infsb% $\downarrow$	Time
POMO*+EAS+SGBS ( Choo et al., 2022 )	100	200	4.51%	0.00%	2.1m
NeuOpt* ( Ma et al., 2023 )	100	200	6.37%	75.78%	17m
CaR (R&R, $T_{\text{R}}=$ 20)	100	200	2.09%	0.00%	10s

Table 8: Generalization results on CVRPBLTW-200. The runtime for OR-Tools is 1.8h.

Method	Train	Test	Gap $\downarrow$	Infsb% $\downarrow$	Time
PIP (sample 5)	tight	tight	0.26%	4.62%	2.3m
PIP (sample 5)	loose	tight	0.03%	31.37%	2.3m
CaR-PIP ( $T_{\text{R}}=$ 20)	loose	tight	0.02%	3.52%	2.3m

Table 9: Generalization results on TSPTW-100 Hard with different time windows tightness.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Illustration of actions and operations in

k

-opt ( top ) and remove-and-reinsertion ( bottom ).

Type	Paradigm	Neural baselines
Single-task	Construction	AM ( Kool et al., 2018 ) , POMO ( Kwon et al., 2020 ) , BQ-NCO ( Drakulic et al., 2023 ) , LEHD ( Luo et al., 2023 ) ,
Single-task	Construction	UDC ( Zheng et al., 2024 ) , InViT ( Fang et al., 2024 ) , PolyNet ( Hottung et al., 2025 )
Single-task	Construction + Post-search	SGBS ( Choo et al., 2022 ) (on top of POMO+EAS ( Hottung et al., 2022 ) ),
Single-task	Construction + Post-search	RRC ( Luo et al., 2023 ) (on top of LEHD and UDC)
Multi-task	Construction	POMO-MTL ( Liu et al., 2024 ) , MVMoE ( Zhou et al., 2024 ) , ReLD-MoEL ( Huang et al., 2025 )
Single-task	Improvement	NeuOpt-GIRE ( Ma et al., 2023 )

Appendix

Table 10: Neural baselines for CVRP result comparison.

w. multi-start	w. mask	Obj. $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$
$\times$	$\times$	10.550	2.093%	0.00%
$\times$	✓	10.520	1.793%	0.00%
✓	$\times$	10.431	0.921%	0.00%
✓	✓	10.424	0.857%	0.00%

Appendix

Table 11: Effects of the multi-starting and feasibility masking during construction on

Method	Module	n=50			n=100
Method	Module	Obj. $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$
	Construction (w/o mask)	14.798	2.116%	3.50%	24.404	-2.050%	2.80%
CaR	Refinement ( $k$ -opt)	14.759	1.682%	2.50%	24.360	-2.285%	2.60%
	Re-construction (w. mask)	14.844	2.114%	0.00%	24.585	-1.724%	0.00%
	Construction (w/o mask)	14.843	2.235%	2.60%	24.460	-1.715%	3.10%
CaR	Refinement (R&R)	14.567	0.221%	1.10%	24.215	-2.886%	1.90%

Appendix

Table 12: CaR module impact on CVRPBLTW feasibility and quality ( Bold : reported in Table 2 ).

Method	#Params	Paradigm §	n = 50			n = 100
Method	#Params	Paradigm §	Obj. $\downarrow$	Gap $\downarrow$	Time	Obj. $\downarrow$	Gap $\downarrow$	Time
HGS	/	I	10.334	$\diamond$	4.6m	15.504	$\diamond$	9.1m
LKH-3	/	I	10.346	0.115%	9.9m	15.590	0.556%	18.0m
OR-Tools (short)	/	I	10.540	1.962%	10.4m	16.381	5.652%	20.8m
OR-Tools (long)	/	I	10.418	0.788%	1.7h	15.935	2.751%	3.5h
AM	0.68M	L2C-S	10.590	2.478%	17s	16.139	4.098%	1.1m

Appendix

Table 13: Results on CVRP: best are bolded; best within 1 min / 2min (

n=50/100

) shaded.

Instance	Opt	POMO (greedy)		BQ-NCO (greedy)		LEHD (greedy)		INViT (greedy)		UDC (RRC=2)		MVMoE (greedy)		CaR (greedy, $T_{\text{R}}=$ 20)
Instance	Opt	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap
X-n101-k25	27591	30138	9.23%	33617	21.84%	31445	13.97%	28311	2.61%	33466	21.29%	29361	6.42%	28518	3.36%
X-n106-k14	26362	39322	49.16%	28221	7.05%	27351	3.75%	27614	4.75%	28681	8.80%	27278	3.47%	27703	5.09%
X-n110-k13	14971	15223	1.68%	15718	4.99%	15252	1.88%	15729	5.06%	16665	11.32%	15089	0.79%	15232	1.74%
X-n115-k10	12747	16113	26.41%	15266	19.76%	13950	9.44%	13744	7.82%	16056	25.96%	13847	8.63%	13097	2.75%
X-n120-k6	13332	14085	5.65%	15524	16.44%	13851	3.89%	14363	7.73%	16618	24.65%	14089	5.68%	13483	1.13%

Appendix

Table 14: Results on CVRPLIB instances. Best results are bolded.

	HD $\uparrow$	PJD $\uparrow$	KTD $\uparrow$
PIP’s constructed solutions	$0.666\pm 0.837$	$0.013\pm 0.017$	$0.713\pm 0.938$
CaR’s constructed solutions	0.770 $\pm$ 0.893	0.015 $\pm$ 0.018	0.821 $\pm$ 0.997
CaR’s diversity improvement over PIP	+15.6%	+15.6%	+15.1%

Appendix

Table 15: Diversity comparison between PIP and CaR constructed solutions.

Method	TSPTW-50 Medium		TSPTW-50 Hard		TSPTW-100 Medium
Method	Infsb% $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$	Gap $\downarrow$
Construction-only	3.77%	5.230%	37.27%	1.635%	0.12%	10.931%
w/o Shared Rep.	0.01%	2.047%	0.68%	0.199%	0.00%	7.589%
w. Shared Rep.	0.00%	2.173%	0.01%	0.014%	0.00%	5.815%

Appendix

Table 16: Effects of unified encoder on TSPTW.

Backbones	Shared Rep.	$\mathcal{L}_{\text{SL}}$	Gap $\downarrow$	Infsb% $\downarrow$
POMO* (Construction-only)	–	–	1.959%	38.22%
CaR-POMO*	$\times$	$\checkmark$	0.136%	0.29%
CaR-POMO*	$\checkmark$	$\times$	0.199%	0.68%
CaR-POMO* (Ours)	$\checkmark$	$\checkmark$	0.014%	0.01%
PIP (Construction-only)	–	–	0.177%	2.67%
CaR-PIP	$\times$	$\times$	0.156%	1.85%

Appendix

Table 18: Comparison of different backbones with shared encoder and supervised loss.

Method	$T_{\text{train}}$	$T_{\text{test}}$	Gap	Infsb%
	5 (same as CaR)	20	/	100%
	10	20	/	100%
NeuOpt*	20	20	/	100%
	100	20	/	100%
	200 (original NeuOpt)	20	/	100%
	5 (same as CaR)	100	/	100%

Appendix

Table 19: Performance of NeuOpt* with different short-horizon settings during training.

Panel of Figure 10 — Figure 10: CaR’s refinement on one TSPTW instance. Green dots and red crosses denote the feasible and infeasible solutions, respectively. Green dashed lines mark the best-so-far feasible objective; the red line indicates the best objective with data augmentation. CaR’s refinement process is shown over time, with $t=$ 0 representing the initially constructed solution.

Panel of Figure 11 — Figure 11: Refinement efficiency of CaR ( top ) and NeuOpt ( bottom ) on typical TSPTW-50 instances.

Figure 12: Effects of

p

Hyperparameters	Gap $\downarrow$	Infsb% $\downarrow$
$\alpha_{1}=0$	0.421%	0.58%
$\alpha_{1}=0.01$ (Ours)	0.014%	0.01%
$\alpha_{1}=0.1$	1.483%	32.68%
$\alpha_{2}=0$	0.136%	0.29%
$\alpha_{2}=1$ (Ours)	0.014%	0.01%
$\alpha_{2}=2$	1.63%	32.12%

Appendix

Table 20: Hyperparameter sensitivity.

Figure 13: Boxplot of diverse methods on TSPTW-50.

Problem	Method	n=50		n=100
Problem	Method	Gap $\downarrow$	Infsb% $\downarrow$	Gap $\downarrow$	Infsb% $\downarrow$
TSPTW	CaR-POMO ( $T_{\text{R}}=$ 20)	0.016% $\pm$ 0.000%	0.01% $\pm$ 0.00%	0.401% $\pm$ 0.002%	2.33% $\pm$ 0.02%
TSPTW	CaR-PIP ( $T_{\text{R}}=$ 20)	0.005% $\pm$ 0.000%	0.00% $\pm$ 0.01%	0.158% $\pm$ 0.001%	0.64% $\pm$ 0.06%
CVRPBLTW	CaR ( $k$ -opt) ( $T_{\text{R}}=$ 20)	2.166% $\pm$ 0.025%	0.00% $\pm$ 0.00%	-1.697% $\pm$ 0.006%	0.00% $\pm$ 0.00%
CVRPBLTW	CaR (R&R) ( $T_{\text{R}}=$ 20)	0.454% $\pm$ 0.012%	0.00% $\pm$ 0.00%	-2.473% $\pm$ 0.015%	0.00% $\pm$ 0.00%

Appendix

Table 21: Standard deviation of the results in Table 2 under five different random seeds.

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 135 papers

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
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
Depot-Closed Multi-Component Construction for Neural Vehicle Routing
Sep 28, 2026Shinichiro Hamada, Hisashi KashimaVehicle Routing Neural Combinatorial Optimization
Core Technology, R&D Division Panasonic Connect Co., Ltd. · Graduate School of Informatics Kyoto University

May 11, 2026J/K move · Enter open · S save

Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver

Canhong Yu, Changliang Zhou, Rongsheng Chen, Zhenkun Wang+1

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

Neural Network Optimization Combinatorial Optimization Vehicle Routing Neural Combinatorial Optimization

Open paper AskPDF arXiv

Heavy-Encoder-Light-Decoder (HELD) neural routing solvers have emerged as a promising paradigm due to their broad applicability across multiple vehicle routing problems (VRPs). However, they typically struggle with VRP variants with complex constraints. To address this limitation, this paper systematically revisits existing neural solvers from the perspective of the generation mechanism for state embeddings (i.e., query vector prior to compatibility calculation) during decoding. We identify that current mechanisms restrict the observation space during attention computation, introducing a key bottleneck to achieving high-quality solutions. Through detailed empirical analysis, we demonstrate the necessity of preserving a global observation space. To overcome the constraint-agnostic drawback inherent to global observation spaces, we propose a simple yet powerful Constraint-Aware Residual Modulation (CARM) module. By adaptively modulating the context embedding with constraint-relevant variables, CARM effectively enhances constraint awareness, enabling the neural solver to fully leverage the global observation space and generate an efficient state embedding. Extensive experimental results across two single-task and five multi-task neural routing solvers confirm that the CARM module consistently boosts baseline performance. Notably, solvers equipped with our CARM achieve substantial improvements in scaling to large-scale instances and in generalizing to unseen VRP variants. These findings provide valuable insights for the architectural design of neural routing solvers.

Abstract

Neural Combinatorial Optimization

Explore similar work

Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems

Depot-Closed Multi-Component Construction for Neural Vehicle Routing