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

Arthur Corrêa; Paulo Nascimento; Samuel Moniz

cs.LGAug 25, 2026

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

Authors: Arthur Corrêa, Paulo Nascimento, Samuel Moniz

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

Abstract

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.

Figures & tables

Figure 1: Encoder architecture overview. Left: $L$ PLE layers with one shared expert $E_{\mathrm{shared}}^{(l)}$ and $\kappa$ task-specific experts per layer, coupled by gated residual connections, before fusion into final node embeddings $H^{(L)}$ . Right: micro-architecture of one expert block.

Method		$n=50$			$n=100$			Method		$n=50$			$n=100$
Method		Obj.	Gap	Time	Obj.	Gap	Time	Method		Obj.	Gap	Time	Obj.	Gap	Time
CVRP	PyVRP	10.372		10.4m	15.628		20.8m	VRPTW	PyVRP	16.031		10.4m	25.423		20.8m
	OR-Tools	10.572	1.907%	10.4m	16.280	4.178%	20.8m		OR-Tools	16.089	0.347%	10.4m	25.814	1.506%	20.8m
	MTPOMO	10.520	1.423%	2s	15.941	2.030%	8s		MTPOMO	16.419	2.423%	2s	26.433	3.962%	9s
	MVMoE	10.499	1.229%	3s	15.888	1.693%	11s		MVMoE	16.400	2.298%	3s	26.390	3.789%	11s
	RouteFinder	10.502	1.257%	2s	15.860	1.524%	8s		RouteFinder	16.341	1.933%	2s	26.228	3.154%	8s

Table 1: Performance on 1K test instances of 16 seen in-distribution VRPs. Gray cells indicate the best objective and gap among all neural MTL models.

Figure 2: Ablation study on the 16 standard VRP variants. Left: training paradigms (RL, PO, POLAR). Right: encoder settings (Shared, Deep-24, PLE). Rows: (a) MTPOMO, (b) MVMoE, (c) RouteFinder, (d) our backbone. Panel subtitles report the mean gap (%) over all variants.

$\alpha$	PO	POLAR
0.01	1.513	1.449
0.03	1.502	1.433
0.05	1.441	1.359
0.07	1.507	1.378
0.09	1.688	1.531

Table 2: Sensitivity of mean performance gap (%) to preference temperature

\alpha

. Best per column in gray.

$k$	Mean gap (%)	Avg. epoch time
1	1.359	6m 44s
2	1.367	7m 04s
3	1.395	7m 19s
4	1.417	7m 36s
5	1.461	7m 50s

Table 3: Effect of refining the top-

k

decoded tours in POLAR. Best per column in gray.

$\kappa$	Mean gap (%)	Epoch w/o LS	Epoch w/ LS
1	1.286	3m 29s	6m 41s
2	1.221	3m 36s	6m 50s
3	1.192	3m 43s	7m 01s
4	1.176	3m 51s	7m 11s

Table 4: Sensitivity of mean gap (%) and epoch time to the number of PLE task experts

\kappa

. Best gap in gray.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Metric	PO	POLAR
Mean preferred-pair gap $\Delta$	0.519	0.562
Cost near-tie fraction @ $\varepsilon{=}0.1\%$	2.36%	2.13%
Cost near-tie fraction @ $\varepsilon{=}0.5\%$	11.28%	10.29%
Cost near-tie fraction @ $\varepsilon{=}1\%$	21.66%	19.91%
Cost near-tie fraction @ $\varepsilon{=}5\%$	74.79%	71.83%
Mean policy gap $\Delta_{\theta}$	0.295	0.366

Appendix

Table 5: Preference-margin statistics during training for PO and POLAR. Gray cells mark the more informative regime (higher

\Delta

\Delta_{\theta}

and lower near-tie fraction).

Layer	Task 1	Task 2	Task 3	Shared
1	57.5%	19.0%	12.9%	10.7%
2	15.6%	39.6%	28.3%	16.5%
3	18.1%	11.3%	41.7%	28.9%
4	13.6%	36.7%	30.2%	19.5%
5	24.8%	28.2%	22.1%	24.8%
6	26.0%	34.1%	39.9%	0.02%

Appendix

Table 6: Relative contribution of each PLE expert to the embedding update.

Method	$n$	Parameters	Avg. epoch time	Total time	Peak GPU memory
POLAR+PLE	50	6.98M	4m 18s	21h 30m	15.66 GB
POLAR	50	1.84M	4m 16s	21h 20m	15.03 GB
PLE	50	6.98M	3m 37s	18h 05m	13.73 GB
Shared	50	1.84M	3m 36s	18h 00m	12.52 GB
POLAR+PLE	100	6.98M	14m 49s	74h 04m	27.00 GB
POLAR	100	1.84M	13m 42s	68h 30m	23.55 GB

Appendix

Table 7: Training cost on one NVIDIA L40S GPU. Average epoch time and total time follow the 300-epoch training schedule. Memory is the peak allocated GPU memory during training.

Set-X		MTPOMO		MVMoE		RouteFinder		CaDA		FiLMMeD(CaDA)		MoSES(CaDA)		Ours
Instance	Opt.	Cost	Gap	Cost	Gap	Cost	Gap	Cost	Gap	Cost	Gap	Cost	Gap	Cost	Gap
X-n101-k25	27591	29470	6.810%	29076	5.382%	29048	5.281%	28944	4.904%	29095	5.451%	29110	5.505%	28810	4.418%
X-n106-k14	26362	28029	6.323%	27443	4.101%	27159	3.023%	27042	2.579%	26826	1.760%	27051	2.614%	26801	1.665%
X-n110-k13	14971	15100	0.862%	15327	2.378%	15314	2.291%	15229	1.723%	15203	1.549%	15332	2.411%	15163	1.282%
X-n115-k10	12747	13433	5.382%	13475	5.711%	13338	4.636%	13060	2.455%	13244	3.899%	13085	2.652%	13071	2.542%
X-n120-k6	13332	14051	5.393%	13782	3.375%	13765	3.248%	13678	2.595%	13552	1.650%	13619	2.153%	13563	1.733%

Appendix

Table 8: Results on CVRPLib instances from the Set-X ( Uchoa et al., 2017 ) . Gray-shaded cells indicate the best objective and gap among all neural models.

	PyVRP		OR-Tools		MTPOMO		MVMoE		RouteFinder		CaDA		FiLMMeD(CaDA)		MoSES(CaDA)		Ours
Variant	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap	Obj.	Gap
VRPMB	13.54		14.93	10.27%	15.04	11.32%	14.99	10.94%	14.88	10.13%	14.83	9.73%	14.65	8.37%	14.93	10.50%	14.63	8.23%
OVRPMB	9.01		10.59	17.54%	10.87	20.65%	10.85	20.42%	10.72	19.02%	10.58	17.38%	10.51	16.71%	10.73	19.09%	10.41	15.53%
VRPMBL	13.78		15.42	11.90%	15.41	11.97%	15.33	11.37%	15.18	10.32%	15.05	9.27%	14.97	8.71%	15.23	10.65%	14.94	8.43%
VRPMBTW	25.51		29.97	17.48%	28.31	11.06%	28.32	11.10%	28.29	10.87%	28.40	11.42%	28.28	10.92%	28.40	11.40%	28.22	10.70%
OVRPMBL	9.01		10.59	17.54%	10.85	20.43%	10.82	20.14%	10.72	19.01%	10.58	17.41%	10.51	16.72%	10.72	18.96%	10.41	15.54%

Appendix

Table 9: Zero-shot generalization performance on 32 unseen VRP variants. Gray-shaded cells indicate the best objective and gap among all neural models.

Figure 3: t-SNE of final encoder embeddings on the 16 training variants ( $n{=}50$ ). Columns compare MTPOMO, MVMoE, RouteFinder, and our model. The top row shows shared-encoder baselines; the bottom row shows the same backbones with PLE. Points are colored by variant.

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

Jul 20, 2026

LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers

Multi-task neural solvers aim to handle multiple Vehicle Routing Problem (VRP) variants within a unified model, avoiding separate training for each constraint combination. However, VRP variants differ in optimization difficulty, while existing methods lack stage-wise feedback on their training status, making the model biased to some specific variants. Although meta-learning can support adaptive training, it typically requires bi-level optimization and additional gradient updates, increasing computational cost. To address this limitation, we propose LLM-as-Trainer (LaT), a plug-and-play training paradigm that uses a pretrained large language model as an external trainer. LaT periodically analyzes cross-task validation metrics to generate a stage-wise guidance vector. This vector is combined with the current task's constraint vector and injected into each encoder layer, providing the neural solver with additional training information during subsequent policy optimization. Experiments on 16 VRP variants show that LaT improves the solution quality of several state-of-the-art multi-task neural solvers on both trained and unseen variants, supporting the effectiveness and generality of the proposed training paradigm.

Yang Wang, Ya-Hui Jia, Wei-Neng Chen +3

School of Future Technology, South China University of Technology, China · School of Computer Science and Engineering, South China University of Technology, China · School of Engineering and Computer Science, Victoria University of Wellington, New Zealand +2

Large Language Model-Guided Optimization Multi-Task Learning Vehicle Routing Neural Combinatorial Optimization

Ask PDF

Apr 12, 2026

Enhancing Cross-Problem Vehicle Routing via Federated Learning

Vehicle routing problems (VRPs) constitute a core optimization challenge in modern logistics and supply chain management. The recent neural combinatorial optimization (NCO) has demonstrated superior efficiency over some traditional algorithms. While serving as a primary NCO approach for solving general VRPs, current cross-problem learning paradigms are still subject to performance degradation and generalizability decay, when transferring from simple VRP variants to those involving different and complex constraints. To strengthen the paradigms, this paper offers an innovative "Multi-problem Pre-train, then Single-problem Fine-tune" framework with Federated Learning (MPSF-FL). This framework exploits the common knowledge of a federated global model to foster efficient cross-problem knowledge sharing and transfer among local models for single-problem fine-tuning. In this way, local models effectively retain common VRP knowledge from up-to-date global model, while being efficiently adapted to downstream VRPs with heterogeneous complex constraints. Experimental results demonstrate that our framework not only enhances the performance in diverse VRPs, but also improves the generalizability in unseen problems.

Xiangchi Meng, Jianan Zhou, Jie Gao +4

Dalian University of Technology · Nanyang Technological University · Delft University of Technology +1

Vehicle Routing Neural Combinatorial Optimization Transfer Learning Federated Fine-Tuning Federated Learning

Ask PDF

Mar 8, 2026

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems

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.

Zhenwei Wang, Tiehua Zhang, Ning Xue +3

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

Vehicle Routing Neural Combinatorial Optimization

Ask PDF

Abstract

Vehicle Routing

Explore similar work

LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers

Enhancing Cross-Problem Vehicle Routing via Federated Learning

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems