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

LaT: LLM-as-Trainer for Multi-Task Vehicle Routing Solvers
Jul 20, 2026Yang Wang, Ya-Hui Jia, Wei-Neng Chen +3Large Language Model-Guided Optimization Multi-Task Learning
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
Enhancing Cross-Problem Vehicle Routing via Federated Learning
Apr 12, 2026Xiangchi Meng, Jianan Zhou, Jie Gao +4Vehicle Routing Neural Combinatorial Optimization
Dalian University of Technology · Nanyang Technological University · Delft University of Technology +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

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

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

Yang Wang, Ya-Hui Jia, Wei-Neng Chen, Yi Mei+2

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

Open paper AskPDF arXiv

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.

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