Enhancing Cross-Problem Vehicle Routing via Federated Learning

Xiangchi Meng; Jianan Zhou; Jie Gao; Yifan Lu; Yaoxin Wu; Gonglin Yuan; Yaqing Hou

cs.AIApr 12, 2026

Enhancing Cross-Problem Vehicle Routing via Federated Learning

Authors: Xiangchi Meng, Jianan Zhou, Jie Gao, Yifan Lu, Yaoxin Wu, Gonglin Yuan, Yaqing Hou

Organizations: Dalian University of Technology · Nanyang Technological University · Delft University of Technology · Eindhoven University of Technology

Abstract

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.

Figures & tables

Figure 1: Performance comparison of CPL. Neural solvers (with identical neural architectures) trained on CVRP and 6 VRPs are fine-tuned on VRPLTW, OVRPLTW, OVRPBTW, VRPBLTW, OVRPBLTW, respectively. These VRP variants are described in Section 3.1 .

Figure 2: Generalization performance decay when a pre-trained unified model is fine-tuned by CPL on OVRPB.

Figure 3: Our “Multi-problem Pre-train, then Single-problem Fine-tune” framework with Federated Learning (MPSF-FL) for VRPs, taking MVMoE as a model example. The

G

and

\{E_{1},E_{2},E_{3},E_{4}\}

in the figure represent the gating network and expert network in the mixture-of-expert moudle of MVMoE, which handles different problem features.

Method		$n=50$				$n=100$				Method		$n=50$				$n=100$
Method		Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Method		Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap
OVRPB	OR-Tools	5.764	0.332%	10.155	1.020%	8.522	1.852%	16.931	2.279%	OVRPL	OR-Tools	6.522	0.480%	10.071	1.003%	9.966	1.783%	16.770	2.286%
	OR-Tools (x10)	5.745		10.036		8.365		16.542			OR-Tools (x10)	6.490		9.953		9.790		16.383
	MVMoE-pretrain	6.092	5.999%	10.640	5.788%	8.959	7.088%	17.465	5.706%		MVMoE-pretrain	6.650	2.454%	10.578	6.181 %	10.097	3.148%	17.338	6.143%
	MVMoE-CPL	5.998	4.358%	10.656	5.833%	8.788	5.048%	17.541	6.008%		MVMoE-CPL	6.633	2.192%	10.578	6.116%	10.061	2.780%	17.372	6.236%
	MVMoE-MTF	6.011	4.588%	-	-	8.802	5.211%	-	-		MVMoE-MTF	6.640	2.295%	-	-	10.069	2.854%	-	-

Table 1: Client-side performance comparison for MVMoE on 1K test instances. The best performance is highlighted in bold, and the second-best is underlined.

Method		$n=50$				$n=100$				Method		$n=50$				$n=100$
Method		Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Method		Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap
OVRPB	HGS-PyVRP	6.898		12.297		10.335		19.457		OVRPL	HGS-PyVRP	6.507		12.341		9.724		19.525
	OR-Tools	6.928	0.412%	12.322	0.418%	10.577	2.315%	19.742	2.001%		OR-Tools	6.552	0.668%	12.364	0.389%	10.001	2.791%	19.806	1.948%
	CaDA-pretrained	7.660	10.953%	12.921	5.885%	11.237	8.659%	20.793	6.886%		CaDA-pretrained	7.497	15.054%	12.940	5.429%	10.365	6.621%	20.890	7.113%
	CaDA-CPL	7.049	2.152%	12.871	5.206%	10.750	3.988%	20.912	6.943%		CaDA-CPL	6.662	2.353%	12.949	5.452%	10.095	3.776%	20.886	6.834%
	CaDA-FL	7.053	2.213%	12.532	1.950%	10.767	4.148%	20.041	3.148%		CaDA-FL	6.656	2.255%	12.576	1.938%	10.109	3.923%	20.126	3.271%

Table 2: Client-side adaptation performance comparison for Cada on 1K test instances. The best performance is highlighted in bold, and the second-best is underlined.

Method		$n=50$				$n=100$				Method		$n=50$				$n=100$
Method		Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Method		Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap	Trained Obj.	Trained Gap	Unseen Obj.	Unseen Gap
OVRPB	MVMoE-CPL	6.018	4.719%	10.751	6.670%	8.783	4.986%	17.533	5.969%	OVRPL	MVMoE-CPL	6.647	2.408%	10.674	6.983%	10.065	2.820%	17.373	6.251%
	MVMoE-FL	6.011	4.596%	10.623	5.527%	8.804	5.243%	17.467	5.547%		MVMoE-FL	6.636	2.237%	10.564	5.908%	10.071	2.881%	17.340	5.919%
	CaDA-CPL	7.052	2.205%	12.869	5.204%	10.764	4.119%	20.823	6.613%		CaDA-CPL	6.660	2.318%	12.938	5.373%	10.100	3.829%	20.885	6.882%
	CaDA-FL	7.053	2.213%	12.528	1.931%	10.772	4.198%	20.058	3.246%		CaDA-FL	6.665	2.397%	12.574	1.945%	10.111	3.942%	20.136	3.323%
VRPBL	MVMoE-CPL	8.178	1.865%	10.569	7.937%	11.947	1.362%	17.182	6.685%	VRPBTW	MVMoE-CPL	15.935	8.049%	9.674	7.481%	27.015	6.219%	15.583	7.081%

Table 3: Client-side performance comparison in data-scarce scenario.

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
FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing
Apr 30, 2026Arthur Corrêa, Paulo Nascimento, Samuel MonizMulti-Task Learning Vehicle Routing
University of Coimbra, CEMMPRE, ARISE, Department of Mechanical Engineering, Coimbra, 3030-788, Portugal
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

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

FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing

Constraints Matrix Diffusion based Generative Neural Solver for Vehicle Routing Problems