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

Peiheng Jian; Zhenwei Wang; Tiehua Zhang; Lei Zhang; Zhishu Shen; Ruibin Bai; Zhijun Ding

cs.LGOct 20, 2026

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

Authors: Peiheng Jian, Zhenwei Wang, Tiehua Zhang, Lei Zhang, Zhishu Shen, Ruibin Bai, Zhijun Ding

Organizations: 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 · School of Computer Science and Artificial Intelligence, Wuhan University of Technology, Wuhan, 430070, China

Abstract

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.

Figures & tables

Figure 1: Constructive decoding trajectories for three selected demand-reassigned variants at fixed customer coordinates. Visiting trajectories and route lengths vary across the examples.

Panel of Figure 2 — Figure 2: Visiting order and route membership are different structural objects. Reordering customers $a,b,c$ changes their adjacency relations while preserving their same-route labels.

Symbol	Meaning
$\mathcal{V}_{c},0$	Customer set and depot
$\mathcal{R}^{\star},y_{ij}$	Reference route solution and same-route label
$\mathcal{P}$	Supervised customer-pair set for training
$\mathbf{P}=[P_{ij}]$	Dense route-consistency prior matrix
$\mathbf{H},g_{\phi}$	Encoder representations and symmetric pair predictor
$\widetilde{\mathbf{A}}$	Row-normalized relation-graph adjacency with self-loops

Table 1: Main notation. The encoder parameters

\theta

and the reweighting balance

\beta

are distinct.

Panel of Figure 3 — Figure 3: TRCM architecture. (a) Augmented inputs and reference-route labels train a symmetric pair predictor with topology and class-frequency weighting. (b) Shared node representations support base decoding and instance-specific prior prediction. The prior $\mathbf{P}$ and current route $\mathcal{S}_{t}$ determine compatibility scores for logit fusion, followed by feasibility masking and action selection. A depot return resets the route context. Graphs and matrix shading are schematic.

Figure 4: Qualitative pair contexts for TE-based supervision. Green solid and orange dashed links indicate low- and high-TE examples, respectively. Gray lines show reference routes, blue points denote customers, and the red square is the depot.

Setting	Value
Autoregressive backbone	POMO
Training instances	1M
Test instances	10,000
Node embedding dimension	128
Pairwise predictor	Two-layer MLP, hidden dimension 256
Optimizer	Adam

Table 2: Experimental settings for route-consistency learning and inference.

		CVRP50			CVRP100
Type	Method	Obj	Gap (%)	Time	Obj	Gap (%)	Time
Classical	HGS	10.36	0.00	21h	15.51	0.00	32h
	LKH3	10.38	0.19	7h	15.65	0.90	13h
	OR-Tools	10.98	5.98	1016s	17.09	10.19	1054s
Neural	PtrNet	11.39	9.94	$<1$ s	17.23	11.09	$<1$ s
	AM	10.98	5.98	3s	16.80	8.32	8s

Table 3: Performance on synthetic CVRP benchmarks. Obj is average route length, Gap is the percentage gap to the comparison’s reference values, and Time is inference time (s: seconds, m: minutes, h: hours). POMO/TRCM rows form the controlled backbone pairs; other methods use their respective inference procedures.

Factor	Level	Instances	Difference (%)
Overall	All	10000	-0.24
Depot	Random	3402	-0.22
	Centered	3322	-0.33
	Cornered	3276	-0.18
Customers	Random	3360	-0.17
	Clustered	3322	-0.32

Table 4: XML100 factor-wise relative objective differences for TRCM

\times

8Aug against POMO

\times

8Aug. Negative values favor TRCM. Differences are displayed to two decimal places. Each factor family summarizes the same 10,000 instances.

Figure 5: Signed objective-fluctuation trends for 500 demand-reassigned variants of one fixed geometry. Curves show rolling means and horizontal reference lines show model-wise means.

Figure 6: Absolute objective-fluctuation distributions for the same variants. Diamond markers denote means and horizontal lines within boxes denote medians. TRCM has smaller mean fluctuations than the corresponding POMO settings.

Model	Acc.	F1	Prec.	Rec.	$\Delta$ F1
TRCM (full)	0.9336	0.8065	0.8002	0.8131	0.0000
w/o RA	0.9147	0.7841	0.6890	0.9096	-0.0224
w/o SD	0.9249	0.7825	0.7720	0.7933	-0.0240
w/o DA	0.9355	0.7886	0.8923	0.7065	-0.0179
w/o TE	0.9111	0.7560	0.7099	0.8085	-0.0505

Table 5: Ablation of prior-prediction training.

\Delta

F1 is the change from the full model.

Figure 7: CVRP100 objective sensitivity to fusion strength: (a) non-augmented TRCM; (b) eightfold-augmented TRCM. Both settings have their best displayed value at

\lambda=1

Figure 8: Prior-prediction F1 as a function of TE temperature and propagation depth. The best annotated setting is

\alpha=1

L=1

, with F1 0.8065.

Dataset	Setting	POMO	TRCM	Time ratio
CVRP50	Non-augmented	1s	3s	$3.00\times$
CVRP100	Non-augmented	8s	15s	$1.88\times$
CVRP50	Eightfold augmentation	26s	40s	$1.54\times$
CVRP100	Eightfold augmentation	5m	7m	$1.40\times$

Table 6: Inference times under matched decoding configurations. The time ratio is TRCM time divided by POMO time.

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

RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
Oct 10, 2026Vladimir Kirill Bickov, Neil Yorke-SmithNeural Combinatorial Optimization Vehicle Routing
Delft University of Technology, The Netherlands
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
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

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

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

Vladimir Kirill Bickov, Neil Yorke-Smith

Delft University of Technology, The Netherlands

Neural Combinatorial Optimization Vehicle Routing

Open paper AskPDF arXiv

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.

Abstract

Vehicle Routing

Explore similar work

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

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

Depot-Closed Multi-Component Construction for Neural Vehicle Routing