A GPU-Accelerated Hybrid Method for a Class of Multi-Depot Vehicle Routing Problems

Zhenyu Lei; Jin-Kao Hao

cs.ROFeb 24, 2026

A GPU-Accelerated Hybrid Method for a Class of Multi-Depot Vehicle Routing Problems

Authors: Zhenyu Lei, Jin-Kao Hao

Organizations: LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France

Abstract

Multi-depot vehicle routing problems (MDVRPs) are prevalent in a variety of practical applications. However, they are computationally challenging to solve due to their inherent complexity. This paper proposes an effective hybrid algorithm for a class of MDVRPs. The algorithm integrates a learning-driven, diversity-controlled route-exchange crossover and a multi-depot-supported feasible-and-infeasible search framework guided by a multi-penalty evaluation function. Two dedicated depot-related local search operators are incorporated to further strengthen the search capability in multi-depot settings. To improve computational efficiency and scalability, an enhanced version of the algorithm is developed that uses a tensor-based GPU acceleration combined with a novel multi-move update strategy. Extensive computational experiments on benchmark instances of three MDVRP variants show that the proposed algorithms are highly competitive with state-of-the-art methods, especially for large-scale instances.

Figures & tables

Panel of Figure 1 — Figure 1: Illustration of the two dedicated depot operators Depot-Insert and Depot-Replace , along with their concatenation operations. Yellow nodes represent the original depot nodes, while “H” and “T” denote the head and tail of the route, respectively. The blue “D” nodes represent the new depot being inserted or used for replacement.

Parameter	Description	Candidate values	Final value
$\mu$	population size	{10, 20, 30, 40, 50}	20
$\theta$	granularity threshold	{25, 50, 75, 100}	50
$\delta$	local search depth	{100, 200, 300, 400, 500}	500
$\kappa$	coefficient adjustment factor	(0, 1)	0.5
$\xi$	fitness function coefficient	(0, 1)	0.7

Table 1: Parameter tuning results.

Reference algorithm	Approach	Problems	Benchmarks
CGL [ 5 ]	Tabu Search	MDVRP	C97
PR [ 29 ]	Adaptive Large Neighborhood Search	MDVRP	C97
VCGLR [ 45 ]	Hybrid Genetic Search	MDVRP	C97
ELTG [ 10 ]	Hybrid Granular Tabu Search	MDVRP	C97
VCGP [ 46 ]	Hybrid Genetic Search	MDVRPTW	C01 , C01-R , V13
JB [ 2 ]	Iterated Local Search	MDOVRP	L14

Table 2: Reference algorithms for benchmark sets.

Problem	Benchmark	#Instances	Algorithm	${\bar{f}_{Best}}$	$\bar{t}$ (s)	$\gamma\cdot\bar{t}$ (s)	$\overline{\text{Gap}}$ (%)	#Wins	#Ties	#Losses	p -value
MDVRP	C97	33	BKS	2423.02	-	-	0.00	7	23	3	0.047
			CGL	2455.56	1112.27	-	1.16	25	8	0	1.23E-05
			PR	2428.30	236.61	63.88	0.21	15	18	0	9.82E-04
			VCGLR	2425.22	254.30	68.66	0.10	8	25	0	0.012
			ELTG	2430.12	138.82	43.03	0.29	11	19	3	3.51E-03
			SCA	2430.86	217.37	293.45	0.20	15	17	1	6.43E-04

Table 3: Summary of comparative results on benchmarks between the proposed algorithms and the reference algorithms.

Figure 2: Performance comparison of MDFIHA and its variants. The x-axis indicates instances, and the y-axis shows the relative gap to the baseline MDFIHA. Colored lines denote mean gaps with 0.95 confidence intervals.

Panel of Figure 3 — Figure 3: Evolution of population diversity across generations for MDFIHA and its variants MDFIHA-SREX and MDFIHA-RARI. The diversity is measured by the solution distances within population.

Figure 4: Performance comparison of MDFIHA and its variants. The x-axis indicates algorithm variants, and the y-axis shows the relative gap to the baseline MDFIHA.

Panel of Figure 5 — Figure 5: Illustration of depot-related operators. Red triangles denote depots, blue points represent customers. Blue edges indicate unchanged routes, yellow edges highlight modified routes.

Panel of Figure 6 — Figure 6: Performance comparison between MDFIHA-ETGA and MDFIHA-ETGA-S, with VCGP [ 46 ] serving as the baseline.

Panel of Figure 7 — Figure 7: ETGA speedup analysis on V13 instances. The x-axis indicates the instance sizes, y-axis represents the speedup ratio.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 11 — Figure A1 : Illustration of the diversity-controlled route-exchange crossover. “A” and “B” are depot nodes. Blue indicates the routes added or nodes retained, while yellow represents the routes or nodes that are removed.

Benchmark	Problem	Literature	#Instances	#Depots	#Customers
C97	MDVRP	[ 5 ]	33	$[2,9]$	$[48,360]$
C97-T	MDVRP	[ 5 ]	10	$[4,6]$	$[48,288]$
C01	MDVRPTW	[ 6 ]	20	$[4,6]$	$[48,288]$
C01-R	MDVRPTW	[ 6 ]	10	$[4,6]$	$[48,288]$
V13	MDVRPTW	[ 46 ]	28	$[4,12]$	$[360,960]$
L14	MDOVRP	[ 22 ]	24	$[4,6]$	$[48,288]$

Appendix

Table A1 : Benchmark sets.

Reference algorithm	Approach	Problems	Benchmarks
CGL [ 5 ]	Tabu Search	MDVRP	C97
PR [ 29 ]	Adaptive Large Neighborhood Search	MDVRP	C97
VCGLR [ 45 ]	Hybrid Genetic Search	MDVRP	C97
ELTG [ 10 ]	Hybrid Granular Tabu Search	MDVRP	C97
VCGP [ 46 ]	Hybrid Genetic Search	MDVRPTW	C01 , C01-R , V13
JB [ 2 ]	Iterated Local Search	MDOVRP	L14

Appendix

Table A2 : Reference algorithms for benchmark sets.

Reference algorithm	Approach	Processor	Base frequency	CPU mark	$\gamma$
CGL [ 5 ]	Tabu Search	Sun Sparcstation 10	-	-	-
PR [ 29 ]	Adaptive Large Neighborhood Search	Pentium 4	3.0 GHz	528	0.27
VCGLR [ 45 ]	Hybrid Genetic Search	Pentium 4	3.0 GHz	528	0.27
ELTG [ 10 ]	Hybrid Granular Tabu Search	Intel Core Duo	2.0 GHz	608	0.31
VCGP [ 46 ]	Hybrid Genetic Search	Intel Xeon	2.93 GHz	1404	0.72
JB [ 2 ]	Iterated Local Search	Intel Core i7-3820	3.60 GHz	1744	0.90

Appendix

Table A3 : Processor information and conversion ratio.

Instance	$N_{C}$	$N_{D}$	$N_{V}$	BKS	CGL			PR			VCGLR			ELTG			SCA			MDFIHA (Ours)
Instance	$N_{C}$	$N_{D}$	$N_{V}$	BKS	$f_{Best}$	$t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)
p01	50	4	4	576.87*	576.87	194.00	0.00	576.87	7.83	0.00	576.87	3.78	0.00	576.87	2.17	0.00	576.87	33.18	0.00	576.87	576.87	7.97	0.00
p02	50	4	2	473.53*	473.87	208.00	0.07	473.53	7.56	0.00	473.53	3.51	0.00	473.53	1.86	0.00	473.53	21.03	0.00	473.53	473.53	18.43	0.00
p03	75	5	3	641.19*	645.15	340.00	0.62	641.19	17.28	0.00	641.19	7.02	0.00	641.19	8.99	0.00	641.19	78.69	0.00	641.19	641.60	14.01	0.00
p04	100	2	8	1001.04*	1006.66	467.00	0.56	1001.04	23.76	0.00	1001.04	31.32	0.00	1001.04	27.90	0.00	1001.04	85.59	0.00	1001.04	1004.04	70.91	0.00
p05	100	2	5	750.03*	753.34	493.00	0.44	751.26	32.40	0.16	750.03	17.28	0.00	750.03	8.06	0.00	750.03	126.86	0.00	750.03	750.14	45.39	0.00

Appendix

Table A4 : Comparative results on the 33 C97 MDVRP benchmark instances between BKS, CGL, PR, VCGLR, ELTG, SCA and MDFIHA.

Instance	$N_{C}$	$N_{D}$	$N_{V}$	Optima	SCA			MDFIHA (Ours)
Instance	$N_{C}$	$N_{D}$	$N_{V}$	Optima	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)
pr01	48	4	1	861.32	861.32	19.58	0.00	861.32	861.32	4.12	0.00
pr02	96	4	2	1307.34	1307.34	140.68	0.00	1307.34	1308.00	28.52	0.00
pr03	144	4	3	1803.80	1803.80	107.60	0.00	1803.80	1804.13	95.96	0.00
pr04	192	4	4	2058.31	2060.93	609.62	0.13	2058.31	2066.65	235.54	0.00
pr05	240	4	5	2331.20	2346.05	1038.39	0.64	2331.20	2339.81	797.08	0.00

Appendix

Table A5 : Comparative results on the 10 C97-T MDVRP benchmark instances between Optima, SCA and MDFIHA.

Instance	$N_{C}$	$N_{D}$	$N_{V}$	BKS	VCGP			SCA			MDFIHA (Ours)
Instance	$N_{C}$	$N_{D}$	$N_{V}$	BKS	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)
pr01	48	4	2	1074.12	1074.12	13.39	0.00	1074.12	67.74	0.00	1074.12	1074.12	14.09	0.00
pr02	96	4	3	1762.21	1762.21	49.68	0.00	1762.21	337.46	0.00	1762.21	1762.29	91.89	0.00
pr03	144	4	4	2373.65	2373.65	75.60	0.00	2373.65	520.38	0.00	2373.65	2380.24	166.76	0.00
pr04	192	4	5	2814.34	2815.75	254.45	0.05	2814.34	3454.26	0.00	2814.34	2817.89	669.76	0.00
pr05	240	4	6	2964.65	2964.65	374.98	0.00	2965.18	915.85	0.02	2962.25	2967.52	1494.27	-0.08

Appendix

Table A6 : Comparative results on the 20 C01 MDVRPTW benchmark instances between BKS, VCGP, SCA and MDFIHA.

Instance	$N_{C}$	$N_{D}$	$N_{V}$	BKS	VCGP			MDFIHA (Ours)
Instance	$N_{C}$	$N_{D}$	$N_{V}$	BKS	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)
pr11	48	4	2	1005.73	1005.73	22.03	0.00	922.44	922.44	9.05	-8.28
pr12	96	4	3	1464.50	1464.50	72.58	0.00	1430.29	1430.29	55.31	-2.34
pr13	144	4	4	2001.81	2001.81	127.01	0.00	2001.81	2002.33	175.36	0.00
pr14	192	4	5	2195.33	2195.33	282.96	0.00	2191.06	2192.77	285.07	-0.19
pr15	240	4	6	2433.15	2433.15	542.59	0.00	2419.88	2425.73	900.55	-0.55

Appendix

Table A7 : Comparative results on the 10 C01-R MDVRPTW benchmark instances between BKS, VCGP and MDFIHA.

Instance	$N_{C}$	$N_{D}$	$N_{V}$	VCGP			MDFIHA (Ours)				MDFIHA-ETGA (Ours)
Instance	$N_{C}$	$N_{D}$	$N_{V}$	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)
pr11a	360	4	10	6720.71	6772.00	726.19	6685.36	6702.83	2868.55	-0.53	6683.00	6697.60	5167.52	-0.56
pr12a	480	4	13	8179.80	8259.57	1296.00	8208.50	8225.16	7099.69	0.35	8164.72	8191.44	6226.49	-0.18
pr13a	600	4	16	9667.20	9751.22	2369.52	9602.32	9662.21	7201.87	-0.67	9571.71	9616.67	7015.26	-0.99
pr14a	720	4	19	11124.01	11235.13	2836.08	11089.24	11117.63	7202.28	-0.31	11062.70	11110.91	6919.64	-0.55
pr15a	840	4	22	13013.97	13078.26	5721.41	13019.83	13080.84	7205.23	0.05	12895.63	12941.05	7201.95	-0.91

Appendix

Table A8 : Comparative results on the 28 V13 MDVRPTW benchmark instances between VCGP, MDFIHA and MDFIHA-ETGA.

Instance	$N_{C}$	$N_{D}$	BKS	JB			RM			SCA			MDFIHA (Ours)
Instance	$N_{C}$	$N_{D}$	BKS	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$\gamma\cdot t$	Gap (%)	$f_{Best}$	$f_{Avg}$	$\gamma\cdot t$	Gap (%)
p01	50	4	386.18*	386.18	6.84	0.00	386.18	0.92	0.00	386.18	22.01	0.00	386.18	386.91	3.83	0.00
p02	50	4	375.93*	376.44	7.83	0.14	375.93	0.20	0.00	375.93	29.15	0.00	375.93	375.93	2.60	0.00
p03	75	5	474.57*	475.79	14.58	0.26	474.57	1.39	0.00	474.57	53.74	0.00	474.57	474.57	13.65	0.00
p04	100	2	662.22	662.22	27.54	0.00	662.22	7272.00	0.00	662.22	21.26	0.00	662.22	662.22	19.46	0.00
p05	100	2	607.53*	609.04	19.98	0.25	607.53	73.68	0.00	607.53	41.67	0.00	607.53	608.39	21.90	0.00

Appendix

Table A9 : Comparative results on the 24 L14 MDOVRP benchmark instances between BKS, JB, RM, SCA and MDFIHA.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

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
PyVRP $^+$ : LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems
Apr 9, 2026Manuj Malik, Jianan Zhou, Shashank Reddy Chirra +1Automated Heuristic Design Large Language Model-Guided Optimization
Singapore Management University Singapore, Singapore · Nanyang Technological University Singapore, Singapore · University of Oxford Oxford, England
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

Apr 30, 2026J/K move · Enter open · S save

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

Arthur Corrêa, Paulo Nascimento, Samuel Moniz

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

Multi-Task Learning Vehicle Routing Neural Combinatorial Optimization

Open paper AskPDF arXiv

Solving practical multi-depot vehicle routing problems (MDVRP) is a challenging optimization task central to modern logistics, increasingly driven by e-commerce. To address the MDVRP's computational complexity, neural-based combinatorial optimization methods offer a promising scalable alternative to traditional approaches. However, neural-based methods typically rely on rigid architectures and input encodings tailored to specific problem formulations. In real-world settings, heterogeneous constraints create multiple MDVRP variants, limiting the applicability of such models. While multi-task learning (MTL) has begun to accelerate the development of unified neural-based solvers, prior works focus almost exclusively on single-depot VRPs, leaving the MDVRP unaddressed. To bridge this gap, we propose Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routing (FiLMMeD), a novel unified neural-based model for 24 different MDVRP variants. We introduce three main contributions: (1) to improve the model's generalization, we augment the standard Transformer encoder with Feature-wise Linear Modulation (FiLM), which dynamically conditions learned internal representations based on the active set of constraints; (2) we provide an initial demonstration of Preference Optimization in the MTL setting, establishing it as a superior alternative to Reinforcement Learning for future MTL works; (3) to mitigate the generalization gap caused by the introduction of multi-depot constraints, we introduce a targeted curriculum learning strategy that progressively exposes the model to increasingly more complex constraint interactions. Extensive experiments on 24 MDVRP variants (including 8 novel formulations) and 16 single-depot VRPs confirm the effectiveness of FiLMMeD, which consistently outperforms state-of-the-art baselines. Our code is available at: https://github.com/AJ-Correa/FiLMMeD/tree/main

Abstract

Vehicle Routing

Explore similar work

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

PyVRP+^++: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems

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

PyVRP $^+$ : LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems