RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem

Vladimir Kirill Bickov; Neil Yorke-Smith

cs.LGOct 10, 2026

RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem

Authors: Vladimir Kirill Bickov, Neil Yorke-Smith

Organizations: Delft University of Technology, The Netherlands

Abstract

Latent recursion repeatedly processes internal representations through the same neural network. Recent work has shown this approach to be effective on structured reasoning tasks such as Sudoku and maze solving. However, whether latent recursion can support neural routing remains unclear. We introduce RELAGRAM (Recursive Latent Graph Model), a novel approach that brings latent recursion to graph combinatorial optimization. RELAGRAM encodes a capacitated vehicle routing problem (CVRP) instance as edge tokens; a compact transformer recurrently updates the latent representations of these tokens. An output head maps the answer state to an edge heatmap, from which an autoregressive decoder constructs a feasible solution. On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. Trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. Together, these results demonstrate that latent recursion is a promising approach to neural routing.

Figures & tables

Figure 1: Overview of RELAGRAM. A CVRP instance is encoded as edge-token input $x$ ; the answer state $y$ and workspace $z$ start from fixed vectors. The shared transformer first updates $z$ from $x+y+z$ (red), then updates $y$ from $y+z$ (blue). Both states $(y,z)$ are carried forward (magenta) in a recursive loop. A linear head maps $y_{t}$ to edge logits, which are decoded into a solution.

		RELAGRAM	RELAGRAM	DeepACO
	decoder	160k	40k	40k
CVRP-100	greedy	13.40	15.55	11.61
	aug8	9.77	11.30	9.16
	combined256	8.30	9.57	6.08
CVRP-500	greedy	22.55	24.78	19.88
	aug8	17.61	19.30	17.68

Table 1: Gap to the PyVRP reference (%; lower is better). For RELAGRAM, Combined256 uses symmetry, noise, and starts; DeepACO uses 16 ants for 16 iterations.

	recursion depth
	1	2	4	6	8	12	16	best observed	$p$ -value
CVRP-100	15.29	13.69	13.40	13.35	13.75	14.69	15.49	13.35 @ 6	0.822
CVRP-500	25.46	23.74	22.55	22.36	22.44	21.96	22.80	21.81 @ 11	0.015
CVRP-1000	33.21	31.58	29.91	28.80	28.75	28.68	29.12	28.45 @ 10	$<0.001$

Table 2: Greedy gap to PyVRP reference (%; lower is better) by depth. RELAGRAM trained at depth four, 160,000 optimizer updates.

p

: two-sided paired

t

-test against depth four (

\alpha=0.05

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

$\lambda_{\mathrm{SI}}$	0	0.3	0.5	0.75	1
Greedy	12.124	7.577	8.150	8.359	8.661
Aug8	7.237	4.351	4.282	4.761	4.968

Appendix

Table 3: CVRP-32 gap to the PyVRP reference (%; lower is better).

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

TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing
Oct 20, 2026Peiheng Jian, Zhenwei Wang, Tiehua Zhang +4Vehicle Routing Neural Combinatorial Optimization
School of Computer Science and Technology, Tongji University, Shanghai, 201804, China · School of Computer Science, University of Nottingham Ningbo China, Ningbo, 315100, China · Yixin Group Limited, Beijing, China +1
Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport
May 10, 2026Samuel J. K. Chin, Maximilian SchifferVehicle Routing Neural Combinatorial Optimization
MIT · TUM
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

Oct 20, 2026J/K move · Enter open · S save

TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing

Peiheng Jian, Zhenwei Wang, Tiehua Zhang, Lei Zhang+3

School of Computer Science and Technology, Tongji University, Shanghai, 201804, China · School of Computer Science, University of Nottingham Ningbo China, Ningbo, 315100, China · Yixin Group Limited, Beijing, China+1

Vehicle Routing Neural Combinatorial Optimization

Open paper AskPDF arXiv

Neural combinatorial optimization has enabled fast constructive solvers for the Capacitated Vehicle Routing Problem (CVRP), yet most autoregressive models still construct solutions through sequential node selection and represent route organization only implicitly. We investigate whether route-level customer co-assignment can be modeled explicitly and used to guide this node-level decision process. To this end, we propose TopologyAware RouteConsistency Modeling (TRCM), which reuses node representations from a standard autoregressive construction pipeline to predict pairwise same-route probabilities and injects them into customer selection as a route-consistency signal. Because sameroute supervision is both class-imbalanced and structurally uneven, TRCM combines structure-preserving augmentation with Topological Entropy (TE)- based reweighting to emphasize locally ambiguous customer pairs. Under matched decoding budgets, TRCM reduces the optimality gap from 3.67% to 3.28% on CVRP50 and from 2.11% to 1.99% on CVRP100; under 8-fold augmented inference, it reduces the CVRP100 gap from 1.61% to 1.49%. On XML100, TRCM*8Aug improves the average objective by 0.24%, with larger gains on several structurally informative factors. A controlled demand-reassignment test over 500 variants further shows more concentrated objective fluctuations. These results support explicit route-consistency modeling as an effective structural principle for autoregressive neural routing.

Abstract

Neural Combinatorial Optimization

Explore similar work

TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing

Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems