arxiv: 2605.05208 · v1 · submitted 2026-02-24 · 💻 cs.RO · cs.DC· math.OC

Recognition: no theorem link

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

Zhenyu Lei , Jin-Kao Hao

Authors on Pith no claims yet

Pith reviewed 2026-05-15 19:49 UTC · model grok-4.3

classification 💻 cs.RO cs.DCmath.OC

keywords multi-depot vehicle routinghybrid algorithmGPU accelerationlocal searchcrossover operatorfeasible-infeasible searchrouting optimizationtensor computation

0 comments

The pith

A hybrid algorithm pairing learning-driven crossover with GPU tensor acceleration solves large multi-depot vehicle routing problems competitively with leading methods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a hybrid method for multi-depot vehicle routing problems that merges a learning-driven route-exchange crossover, kept diverse through control mechanisms, with a feasible-and-infeasible search framework that uses a multi-penalty function to guide moves. Two depot-specific local search operators are added to handle the multi-depot structure directly. An enhanced version accelerates the search via tensor-based GPU computation and a multi-move update strategy. Experiments on benchmark sets for three MDVRP variants show the approach matches or exceeds state-of-the-art solvers, with the largest gains appearing on big instances.

Core claim

The central claim is that integrating a learning-driven, diversity-controlled route-exchange crossover with a multi-depot-supported feasible-and-infeasible search framework, plus dedicated depot local searches, produces a competitive solver; the GPU tensor acceleration and multi-move strategy then scale this solver effectively to large instances where prior methods slow down.

What carries the argument

The tensor-based GPU acceleration with multi-move update strategy inside the multi-penalty feasible-and-infeasible search framework.

If this is right

The method scales to larger depot and customer counts while remaining competitive in solution quality.
The same framework applies across three standard MDVRP variants without major redesign.
GPU acceleration reduces runtime enough to support repeated runs or real-time re-optimization.
Depot-specific local searches improve feasibility handling in multi-depot settings compared with single-depot operators.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same hybrid structure could be tested on other multi-location routing variants such as periodic or stochastic MDVRPs.
Logistics planners might adopt the GPU version for daily large-scale fleet scheduling where exact solvers remain too slow.
The multi-move GPU strategy may transfer to other population-based combinatorial optimizers that rely on local search.

Load-bearing premise

That success on the chosen benchmark instances will continue on new or larger instances drawn from the same problem family.

What would settle it

A single large MDVRP instance on which the GPU hybrid returns solutions that are both worse in cost and slower than the current best published competitor.

Figures

Figures reproduced from arXiv: 2605.05208 by Jin-Kao Hao, Zhenyu Lei.

**Figure 2.** Figure 2: Performance comparison of MDFIHA and its variants. The x-axis indicates [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗

**Figure 3.** Figure 3: Evolution of population diversity across generations for MDFIHA and its [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗

**Figure 4.** Figure 4: Performance comparison of MDFIHA and its variants. The x-axis indicates [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗

**Figure 5.** Figure 5: Illustration of depot-related operators. Red triangles denote depots, blue [PITH_FULL_IMAGE:figures/full_fig_p026_5.png] view at source ↗

**Figure 6.** Figure 6: Performance comparison between MDFIHA-ETGA and MDFIHA-ETGA-S, [PITH_FULL_IMAGE:figures/full_fig_p027_6.png] view at source ↗

**Figure 7.** Figure 7: ETGA speedup analysis on V13 instances. The x-axis indicates the instance sizes, y-axis represents the speedup ratio. (XS), and 2-opt* (TOS)) depending on whether they act on one or two routes. It can be observed that inter-operators (XR, XS, TOS) achieve substantial speedups because the ETGA framework efficiently parallelizes their computationally intensive evaluations on the GPU. In contrast, intra-rout… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper builds a hybrid metaheuristic for multi-depot VRPs that adds learning-driven crossover and tensor GPU acceleration, then shows competitive results on standard large-scale benchmarks.

read the letter

The paper's main point is a hybrid solver for multi-depot vehicle routing that folds a learning-driven diversity-controlled route-exchange crossover into a multi-penalty feasible-infeasible framework, adds two depot-specific local search operators, and accelerates the whole thing with a tensor-based GPU multi-move update. On the benchmarks it reports results that stay competitive with published methods and pull ahead on the larger instances. The construction itself is straightforward to follow once the pieces are laid out. The authors supply pseudocode for the crossover, the penalty scheme, the operators, and the GPU update loop, which makes the integration concrete rather than hand-wavy. The GPU version is presented as a direct extension that preserves the same search logic while cutting wall-clock time, and the experiments cover three MDVRP variants with tabulated gaps against prior solvers. That combination of elements is not copied from any single earlier paper cited in the abstract, so the specific recipe counts as new work. The soft spots sit in the experimental side. The competitiveness claim rests on the chosen benchmark sets, and while the stress-test note indicates the full tables and baselines are there, the abstract itself gives no error bars, run counts, or significance tests, so a referee would still want those details confirmed. Generalization beyond the standard instances is left as an open question, which is normal for this style of paper but limits how far the results can be pushed. The work is aimed at researchers who build or tune metaheuristics for routing problems and who care about scaling them with hardware acceleration. Someone already working on VRP solvers or GPU implementations would find the operator choices and the tensor update strategy worth examining. It is not a foundational theoretical advance, but the implementation is careful enough and the results are sharp enough on the stated benchmarks that it deserves a serious referee rather than a desk rejection.

Referee Report

1 major / 1 minor

Summary. The paper proposes a hybrid metaheuristic for a class of multi-depot vehicle routing problems (MDVRPs). It integrates a learning-driven, diversity-controlled route-exchange crossover operator, a multi-depot-supported feasible-and-infeasible search framework driven by a multi-penalty evaluation function, and two dedicated depot-related local search operators. An enhanced GPU-accelerated variant is developed using tensor-based representations and a novel multi-move update strategy. Extensive experiments on standard benchmark instances for three MDVRP variants are reported to show that both the CPU and GPU versions are highly competitive with state-of-the-art methods, with particular strength on large-scale instances.

Significance. If the performance claims are statistically substantiated, the work would be a useful contribution to the vehicle-routing literature by demonstrating a practical hybrid framework that combines learning-based crossover with penalty-guided search and GPU tensor acceleration. The explicit algorithmic descriptions, pseudocode, and tabulated comparisons against published baselines provide a reproducible starting point for further research on scalable MDVRP solvers, which remain relevant for large-scale logistics applications.

major comments (1)

[§4] §4 (Computational Experiments) and Tables 1–3: the reported average gaps to best-known solutions are presented without standard deviations across runs, the number of independent runs per instance, or any statistical significance tests against the baselines. Without these, it is impossible to determine whether the claimed competitiveness (especially the advantage on large instances) is robust or could be explained by run-to-run variance.

minor comments (1)

[§3.4] The description of the tensor layout and multi-move update kernel in §3.4 would benefit from a small diagram or explicit indexing equations to clarify how depot-specific moves are batched without race conditions.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive feedback and positive overall assessment. The single major comment concerns the statistical robustness of the experimental results in §4 and Tables 1–3. We address it directly below.

read point-by-point responses

Referee: [§4] §4 (Computational Experiments) and Tables 1–3: the reported average gaps to best-known solutions are presented without standard deviations across runs, the number of independent runs per instance, or any statistical significance tests against the baselines. Without these, it is impossible to determine whether the claimed competitiveness (especially the advantage on large instances) is robust or could be explained by run-to-run variance.

Authors: We agree that the current presentation lacks the requested statistical details. Each instance was solved in 10 independent runs; the reported averages are means over these runs, but standard deviations and run counts were omitted for brevity. In the revision we will (i) add a new column to Tables 1–3 showing mean gap ± one standard deviation, (ii) state explicitly that 10 runs were performed per instance, and (iii) append a supplementary table of Wilcoxon signed-rank test p-values comparing our method against the strongest published baseline for each instance group. These additions will confirm that the observed advantages on large instances are statistically significant and not attributable to run-to-run variance. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a concrete hybrid metaheuristic for MDVRP variants, specifying a learning-driven crossover, multi-penalty feasible/infeasible framework, depot-specific operators, and tensor-based GPU multi-move updates, all described via pseudocode and implementation details. Performance is measured by direct execution on external benchmark instance sets drawn from the literature, with tabulated gaps reported against independently published SOTA baselines. No equation, parameter fit, or central claim reduces by construction to a quantity defined inside the paper; the benchmarks and comparison values are independent of the authors' fitted choices. The derivation chain is therefore self-contained algorithmic construction plus external empirical testing.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the approach rests on standard metaheuristic assumptions about search operators and benchmark validity.

pith-pipeline@v0.9.0 · 5449 in / 1113 out tokens · 21051 ms · 2026-05-15T19:49:43.886644+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

[1]

F. A. Tillman, The multiple terminal delivery problem with probabilistic demands, Transportation Science 3 (3) (1969) 192–204

work page 1969
[2]

G. B. Dantzig, J. H. Ramser, The truck dispatching problem, Management Science 6 (1) (1959) 80–91

work page 1959
[3]

Clarke, J

G. Clarke, J. W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research 12 (4) (1964) 568–581

work page 1964
[4]

J. K. Lenstra, A. Rinnooy Kan, Complexity of scheduling under precedence constraints, Operations Research 26 (1) (1978) 22–35

work page 1978
[5]

Lei, J.-K

Z. Lei, J.-K. Hao, Q. Wu, Speeding up local optimization in vehicle routing with tensor-based gpu acceleration (2026). arXiv:2506.17357. URLhttps://arxiv.org/abs/2506.17357v2

work page arXiv 2026
[6]

J. R. Montoya-Torres, J. L. Franco, S. N. Isaza, H. F. Jim´ enez, N. Herazo- Padilla, A literature review on the vehicle routing problem with multiple depots, Computers & Industrial Engineering 79 (2015) 115–129

work page 2015
[7]

Sharma, S

R. Sharma, S. Saini, Heuristics and meta-heuristics based multiple depot vehicle routing problem: A review, in: 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC), IEEE, 2020, pp. 683–689

work page 2020
[8]

Laporte, Optimal solutions to capacitated multidepot vehicle routing problems, Congressus Nemerantium 4 (1984) 283–292

G. Laporte, Optimal solutions to capacitated multidepot vehicle routing problems, Congressus Nemerantium 4 (1984) 283–292. 29

work page 1984
[9]

Laporte, Y

G. Laporte, Y. Nobert, S. Taillefer, Solving a family of multi-depot vehicle routing and location-routing problems, Transportation Science 22 (3) (1988) 161–172

work page 1988
[10]

Baldacci, A

R. Baldacci, A. Mingozzi, A unified exact method for solving different classes of vehicle routing problems, Mathematical Programming 120 (2009) 347–380

work page 2009
[11]

Contardo, R

C. Contardo, R. Martinelli, A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints, Discrete Optimization 12 (2014) 129–146

work page 2014
[12]

Giosa, I

I. Giosa, I. Tansini, I. Viera, New assignment algorithms for the multi-depot vehicle routing problem, Journal of the Operational Research Society 53 (9) (2002) 977–984

work page 2002
[13]

Tansini, O

L. Tansini, O. Viera, New measures of proximity for the assignment algorithms in the mdvrptw, Journal of the Operational Research Society 57 (3) (2006) 241–249

work page 2006
[14]

Torres-P´ erez, A

I. Torres-P´ erez, A. Rosete, G. Sosa-G´ omez, O. Rojas, New heuristics for assigning in the multi-depot vehicle routing problem, IFAC-PapersOnLine 55 (10) (2022) 2228–2233

work page 2022
[15]

A. Lim, F. Wang, Multi-depot vehicle routing problem: A one-stage approach, IEEE Transactions on Automation Science and Engineering 2 (4) (2005) 397– 402

work page 2005
[16]

Renaud, G

J. Renaud, G. Laporte, F. F. Boctor, A tabu search heuristic for the multi-depot vehicle routing problem, Computers & Operations Research 23 (3) (1996) 229– 235

work page 1996
[17]

Renaud, F

J. Renaud, F. F. Boctor, G. Laporte, An improved petal heuristic for the vehicle routeing problem, Journal of the Operational Research Society 47 (2) (1996) 329–336

work page 1996
[18]

Cordeau, M

J.-F. Cordeau, M. Gendreau, G. Laporte, A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks: An International Journal 30 (2) (1997) 105–119

work page 1997
[19]

Cordeau, G

J.-F. Cordeau, G. Laporte, A. Mercier, A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society 52 (8) (2001) 928–936

work page 2001
[20]

Cordeau, G

J.-F. Cordeau, G. Laporte, A. Mercier, Improved tabu search algorithm for the handling of route duration constraints in vehicle routing problems with time windows, Journal of the Operational Research Society 55 (5) (2004) 542–546

work page 2004
[21]

Cordeau, M

J.-F. Cordeau, M. Maischberger, A parallel iterated tabu search heuristic for vehicle routing problems, Computers & Operations Research 39 (9) (2012) 2033–2050

work page 2012
[22]

Polacek, R

M. Polacek, R. F. Hartl, K. Doerner, M. Reimann, A variable neighborhood search for the multi depot vehicle routing problem with time windows, Journal of Heuristics 10 (2004) 613–627. 30

work page 2004
[23]

Polacek, S

M. Polacek, S. Benkner, K. F. Doerner, R. F. Hartl, A cooperative and adaptive variable neighborhood search for the multi depot vehicle routing problem with time windows, Business Research 1 (2008) 207–218

work page 2008
[24]

M. E. H. Sadati, B. C ¸ atay, D. Aksen, An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems, Computers & Operations Research 133 (2021) 105269

work page 2021
[25]

Pisinger, S

D. Pisinger, S. Ropke, A general heuristic for vehicle routing problems, Computers & Operations Research 34 (8) (2007) 2403–2435

work page 2007
[26]

Vidal, T

T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, W. Rei, A hybrid genetic algorithm for multidepot and periodic vehicle routing problems, Operations Research 60 (3) (2012) 611–624

work page 2012
[27]

Vidal, T

T. Vidal, T. G. Crainic, M. Gendreau, C. Prins, A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research 40 (1) (2013) 475–489

work page 2013
[28]

Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (12) (2004) 1985–2002

C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (12) (2004) 1985–2002

work page 2004
[29]

J. W. Escobar, R. Linfati, P. Toth, M. G. Baldoquin, A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem, Journal of Heuristics 20 (2014) 483–509

work page 2014
[30]

W. Tu, Z. Fang, Q. Li, S.-L. Shaw, B. Chen, A bi-level voronoi diagram- based metaheuristic for a large-scale multi-depot vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review 61 (2014) 84–97

work page 2014
[31]

Moscato, C

P. Moscato, C. Cotta, A modern introduction to memetic algorithms, Handbook of Metaheuristics (2010) 141–183

work page 2010
[32]

Glover, J.-K

F. Glover, J.-K. Hao, The case for strategic oscillation, Annals of Operations Research 183(1) (2011) 163–173

work page 2011
[33]

S. Liu, K. Tang, X. Yao, Memetic search for vehicle routing with simultaneous pickup-delivery and time windows, Swarm and Evolutionary Computation 66 (2021) 100927

work page 2021
[34]

Qiao, J.-C

W.-B. Qiao, J.-C. Cr´ eput, Massive 2-opt and 3-opt moves with high performance gpu local search to large-scale traveling salesman problem, in: International Conference on Learning and Intelligent Optimization, Springer, 2018, pp. 82– 97

work page 2018
[35]

Qiao, J.-C

W.-B. Qiao, J.-C. Cr´ eput, Multiple k- opt evaluation multiple k- opt moves with gpu high performance local search to large-scale traveling salesman problems, Annals of Mathematics and Artificial Intelligence 88 (4) (2020) 347–365

work page 2020
[36]

J. A. Robinson, S. V. Vrbsky, X. Hong, B. P. Eddy, Analysis of a high- performance tsp solver on the gpu, Journal of Experimental Algorithmics (JEA) 23 (2018) 1–22. 31

work page 2018
[37]

Y. Nagata, Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem, Proceedings of the 7th Internatinal Conferencenon Genetic Algorithms (1997) 450–457

work page 1997
[38]

He, J.-K

P. He, J.-K. Hao, General edge assembly crossover-driven memetic search for split delivery vehicle routing, Transportation Science 57 (2) (2023) 482–511

work page 2023
[39]

He, J.-K

P. He, J.-K. Hao, Memetic search for the minmax multiple traveling salesman problem with single and multiple depots, European Journal of Operational Research 307 (3) (2023) 1055–1070

work page 2023
[40]

Lei, J.-K

Z. Lei, J.-K. Hao, A memetic algorithm for vehicle routing with simultaneous pickup and delivery and time windows, IEEE Transactions on Evolutionary Computation 29 (5) (2025) 1924 –1936

work page 2025
[41]

R. Liu, Z. Jiang, N. Geng, A hybrid genetic algorithm for the multi-depot open vehicle routing problem, OR Spectrum 36 (2014) 401–421

work page 2014
[42]

L´ opez-Ib´ a˜ nez, J

M. L´ opez-Ib´ a˜ nez, J. Dubois-Lacoste, L. P. C´ aceres, M. Birattari, T. St¨ utzle, The irace package: Iterated racing for automatic algorithm configuration, Operations Research Perspectives 3 (2016) 43–58

work page 2016
[43]

Brand˜ ao, A memory-based iterated local search algorithm for the multi- depot open vehicle routing problem, European Journal of Operational Research 284 (2) (2020) 559–571

J. Brand˜ ao, A memory-based iterated local search algorithm for the multi- depot open vehicle routing problem, European Journal of Operational Research 284 (2) (2020) 559–571

work page 2020
[44]

Lalla-Ruiz, M

E. Lalla-Ruiz, M. Mes, Mathematical formulations and improvements for the multi-depot open vehicle routing problem, Optimization Letters 15 (1) (2021) 271–286

work page 2021
[45]

Sadykov, E

R. Sadykov, E. Uchoa, A. Pessoa, A bucket graph–based labeling algorithm with application to vehicle routing, Transportation Science 55 (1) (2021) 4–28

work page 2021
[46]

A” and “B

Y. Nagata, S. Kobayashi, A memetic algorithm for the pickup and delivery problem with time windows using selective route exchange crossover, in: International Conference on Parallel Problem Solving from Nature, Springer, 2010, pp. 536–545. 32 Supplementary materials The supplementary materials include a detailed definition of the multi-penalty evaluation ...

work page arXiv 2010