Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems

Zhenwei Wang; Tiehua Zhang; Ning Xue; Ender Ozcan; Ling Wang; Ruibin Bai

cs.LGMar 8, 2026

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems

Authors: Zhenwei Wang, Tiehua Zhang, Ning Xue, Ender Ozcan, Ling Wang, Ruibin Bai

Organizations: 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. · Department of Automation, Tsinghua University, Beijing 100084, China

Abstract

Over the past decade, neural network solvers powered by generative artificial intelligence have garnered significant attention in the domain of vehicle routing problems (VRPs), owing to their exceptional computational efficiency and superior reasoning capabilities. In particular, autoregressive solvers integrated with reinforcement learning have emerged as a prominent trend. However, much of the existing work emphasizes large-scale generalization of neural approaches while neglecting the limited robustness of attention-based methods across heterogeneous distributions of problem parameters. Their improvements over heuristic search remain largely restricted to hand-curated, fixed-distribution benchmarks. Furthermore, these architectures tend to degrade significantly when node representations are highly similar or when tasks involve long decision horizons. To address the aforementioned limitations, we propose a novel fusion neural network framework that employs a discrete noise graph diffusion model to learn the underlying constraints of vehicle routing problems and generate a constraint assignment matrix. This matrix is subsequently integrated adaptively into the feature representation learning and decision process of the autoregressive solver, serving as a graph structure mask that facilitates the formation of solutions characterized by both global vision and local feature integration. To the best of our knowledge, this work represents the first comprehensive experimental investigation of neural network model solvers across a 378-combinatorial space spanning four distinct dimensions within the CVRPlib public dataset. Extensive experimental evaluations demonstrate that our proposed fusion model effectively captures and leverages problem constraints, achieving state-of-the-art performance across multiple benchmark datasets.

Figures & tables

Fig. 1: Demonstrating the effects of data augmentation, the numerical value within the rectangle above each scatter point indicates the origin node index, while the value in parentheses represents the node demand. The black dashed lines in the first row of the four symmetric transformation subgraphs correspond to the symmetry axes.

Fig. 2: Constraint matrix mapping from augmented optimal solution instances

Fig. 3: Constraint-Matrix Generation and Forward Corruption/Reverse Denoising under a Discrete-Noise Diffusion

Fig. 4: Overall architecture. (a) Graph‑diffusion prior with two submodules: (1) data augmentation and (2) constraint‑matrix generation. (b) Mask‑guided encoder: a pretrained multi‑layer GAT extracts global representations, and a trainable masked GAT extracts local representations; their fusion yields node embeddings. (c) Dual‑pointer decoder: two attention pointers fuse global and local decisions, conditioned on the global graph embedding and the current system state.

Parameters	Values
Diffusion Training steps $T$	1000
Diffusion Inference steps $T^{\prime}$	50
Diffusion linear noise schedule $\beta_{1}$	$10^{-4}$
Diffusion linear noise schedule $\beta_{T}$	$0.02$
Diffusion batch size	32
Diffusion Training epoch	50

TABLE I: Experimental parameters

Model	CVRP20			CVRP50			CVRP100
Model	Objective	Gap(%)	Time	Objective	Gap(%)	Time	Objective	Gap(%)	Time
Gurobi [ Gurobi Optimization, LLC(2024) ]	6.10	0.00	13h	-	-	-	-	-	-
HGS [ Kwon et al.(2020)Kwon, Choo, Kim, Yoon, Gwon, and Min ]	6.11	0.16	8.2h	10.36	0.00	21h	15.51	0.00	32h
LKH3 [ Helsgaun(2017) ]	6.14	0.65	2h	10.38	0.19	7h	15.65	0.90	13h
OR Tools [ Google Optimization Tools(2024) ]	6.18	1.31	*1000s	10.98	5.98	*1016s	17.09	10.19	*1054s
PtrNet [2018]	6.59	8.03	$<$ 1s	11.39	9.94	$<$ 1s	17.23	11.09	$<$ 1s

TABLE II: Comparison with SOTA methods on randomly generated CVRP instances. “–” in the Gurobi row indicates no result within the time limit; Gurobi, HGS, and LKH3 results are reproduced from prior studies [ Kool, Van Hoof, and Welling(2019) , Kwon et al.(2020)Kwon, Choo, Kim, Yoon, Gwon, and Min , Lei et al.(2022)Lei, Guo, Wang, Wu, and Zhao ] . “*” in the Time column denotes the total runtime of a single-threaded, sequential OR-Tools run with a 1s per‑instance search limit over 1,000 test cases. Entries in bold and underlined show the best results across neural solvers

Data instance	Nodes number	Optimal Solution	Our Approach $\times 8$ Aug		E-GAT		POMO $\times 8$ Aug		LEHD
Data instance	Nodes number	Objective	Objective	Gap(%)	Objective	Gap(%)	Objective	Gap(%)	Objective	Gap(%)
A-n44-k6	43	937	972	3.74	979	4.49	997	6.40	1000	6.74
A-n45-k6	44	944	970	2.75	984	4.23	993	5.22	994	5.33
A-n63-k10	62	1314	1337	1.75	1519	15.60	1329	1.16	1463	11.32
A-n64-k9	63	1401	1493	6.57	1659	18.40	1430	2.10	1478	5.55
A-n69-k9	68	1159	1193	2.93	1264	9.05	1199	3.47	1264	9.04

TABLE III: Model performance on CVRPLIB across multiple problem scales. Boldface upon underlines denotes the best result among compared methods; “–” indicates omitted (not reported) entries. The Gap column quantifies the discrepancy from the optimal solution.

Dimension	Description	Number of Instance	POMO		Our Approach		POMO $\times 8$ Aug		Our Approach $\times$ 8 Aug
Dimension	Description	Number of Instance	Gap(%)	Gap Std	Gap(%)	Gap Std	Gap(%)	Gap Std	Gap(%)	Gap Std
Depot Distribution	random	3402	8.80	7.10	8.27	6.42	5.86	4.25	5.62	3.87
	centered	3322	10.60	9.67	9.95	8.13	6.59	4.62	6.27	4.08
	cornered	3276	8.11	6.60	7.97	6.37	5.50	4.17	5.40	4.05
Customer Distribution	random	3360	8.28	6.59	7.86	6.25	5.58	3.84	5.36	3.56
	clustered	3322	10.59	9.11	9.98	8.07	6.62	5.05	6.42	4.66

TABLE IV: Comparative analysis of out‑of‑distribution (OOD) generalization. Boldface upon underlines indicates that the current subcategory achieves a lower average gap or lower average standard deviation than the competing model without/with

8

times data augmentation. Inference uses a pretrained 100‑node model trained on synthetic data.

Fig. 5: Performance gaps over 10,000 XML100 instances. A 0.5% gap defines significance: red denotes our model outperforming LEHD, and blue denotes POMO outperforming ours.

Fig. 6: Evaluation metrics for diffusion models parameterized by Bernoulli and Gaussian noise. All metrics are computed from entrywise classification statistics of the constraint matrix.

Module	CVRP100		CVRPLib
Module	Objectives	Gap(%)	Average Gap(%)
Ours	15.70	0.00	5.10
Ours-FTGAT	15.68	-0.13	5.52
w/o Ours-ME	15.92	1.40	6.33
w/o Ours-LA	15.88	1.14	5.98

TABLE V: Experimental results for the ablation and Fine-Tuned models

Fig. 7: Training curves for the ablation study.

Fig. 8: Sensitivity analysis of inference steps in the diffusion model

Fig. 9: Training curves of the encoder GAT across depths: 1–4‑layer models did not meet the early‑stopping criterion within 100 epochs, whereas 5–6‑layer models triggered early stopping.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 133 papers

Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement
Aug 25, 2026Arthur Corrêa, Paulo Nascimento, Samuel MonizVehicle Routing Neural Combinatorial Optimization
University of Coimbra, CEMMPRE, ARISE Department of Mechanical Engineering, Coimbra 3030-788, Portugal
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
Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems
Mar 13, 2025Zhenwei Wang, Tiehua Zhang, Jing Liu +3Constrained RL Vehicle Routing
University of Nottingham Ningbo China, 199 East Taikang Road, Ningbo, 315100, Zhejiang, China · Tongji University, 1239,Siping Road, Shanghai, 200092, Shanghai, China · State Key Laboratory for Novel Software Technology, Nanjing University, 163,Xianlin Road, Nanjing, 210023, Jiangsu, China +1

Aug 25, 2026J/K move · Enter open · S save

Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

Arthur Corrêa, Paulo Nascimento, Samuel Moniz

University of Coimbra, CEMMPRE, ARISE Department of Mechanical Engineering, Coimbra 3030-788, Portugal

Vehicle Routing Neural Combinatorial Optimization Preference Optimization

Open paper AskPDF arXiv

Multi-task vehicle routing problem (VRP) solvers seek to handle multiple VRP variants within a single unified model, avoiding the need to train a separate model for every variant. In spite of recent progress, current approaches remain limited on two fronts. On the training side, reinforcement learning suffers from reward-scale disparities and shrinking advantage signals as policies improve, whereas preference optimization stagnates once sampled tours become near-identical and thus fundamentally limited by the quality of the policy's own generated solutions, leaving both paradigms with weak supervision as training progresses. On the architecture side, existing fully shared encoders entangle constraint-dependent representations across heterogeneous variants, which limits generalization. We address these gaps with two model-agnostic contributions. First, we propose Preference Optimization with Locally Augmented Refinement (POLAR), a novel training algorithm that applies a local search refinement pass to the best decoded tour before forming preference pairs, yielding much more informative pairwise margins. Second, a Progressive Layered Extraction (PLE) encoder routes each encoder layer through one shared expert and a set of task-specific experts via a gating mechanism, progressively separating common routing structure from constraint-specific encodings. Through extensive experiments on various VRP variants, we show that POLAR and PLE together elevate the current state-of-the-art among neural multi-task solvers. We reduce the average gap to reference solutions by 21.3% relative to the strongest published baseline on 16 in-distribution variants, and outperform prior neural methods on 27 out of 32 unseen variants. Ablation studies confirm the efficacy of each contribution, showing that both improve cross-problem generalization across multiple backbone model architectures.

Abstract

Vehicle Routing

Explore similar work

Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problems