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

• URL: http://arxiv.org/abs/2605.05208v1
• Date: Tue, 24 Feb 2026 14:15:28 GMT
• Title: A GPU-Accelerated Hybrid Method for a Class of Multi-Depot Vehicle Routing Problems
• Abstract summary: Multi-depot vehicle routing problems (MDVRPs) are prevalent in a variety of practical applications.<n>This paper proposes an effective hybrid algorithm for a class of MDVRPs.
• Score: 11.270060015068529
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency [0.0]
  We address a dynamic, online variant combining elements of the Vehicle Problem (VRP) and the Orienteering Problem (OP)<n>We propose and evaluate a reward-density for dynamic multi-vehicle assignment, referred to as the Efficiency Routing.<n>Across all tested configurations, the Efficiency matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time.
  arXiv  Detail & Related papers  (2026-07-07T09:37:46Z)
• Multi-Agent DRL for V2X Resource Allocation: Disentangling Challenges and Benchmarking Solutions [51.22818149833102]
  Multi-agent reinforcement learning (MARL) has emerged as a promising approach for radio resource allocation in vehicle-to-everything (C-V2X) networks.<n>However, the multifaceted challenges inherent to MARL are often intertwined, making it difficult to understand their individual impact on performance in vehicular environments.<n>We bridge this gap by formulating C-V2X RRA as a sequence of multi-agent interference games with progressively increasing complexity.
  arXiv  Detail & Related papers  (2026-02-18T14:46:56Z)
• Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration [23.87172157992149]
  We introduce an original tensor-based GPU acceleration method to speed up the commonly used local search operators in vehicle routing.<n>Its low-coupling architecture, with intensive computations completely offloaded to the GPU, ensures seamless integration in various local search-based algorithms and frameworks.
  arXiv  Detail & Related papers  (2025-06-20T07:40:47Z)
• Learning with Local Search MCMC Layers [12.613397606663801]
  We introduce a theoretically-principled approach for learning with inexact solvers.<n>We transform problem-specific neighborhood systems used in local searchs into proposal distributions.<n>We demonstrate our approach on a large-scale dynamic vehicle routing problem with time windows.
  arXiv  Detail & Related papers  (2025-05-20T11:47:42Z)
• TuneNSearch: a hybrid transfer learning and local search approach for solving vehicle routing problems [44.035549471545586]
  TuneNSearch is a hybrid transfer learning and local search approach for addressing diverse variants of the vehicle routing problem (VRP)<n>Our method uses reinforcement learning to generate high-quality solutions, which are refined by an efficient local search procedure.
  arXiv  Detail & Related papers  (2025-03-16T21:34:11Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems.<n>We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [51.89707241449435]
  In this paper, we address the challenge of integrating multi-head self-attention into high-resolution representation CNNs efficiently.<n>We develop a multi-target multi-branch supernet method, which fully utilizes the advantages of high-resolution features.<n>We present a series of models via the Hybrid Convolutional-Transformer Architecture Search (HyCTAS) method that searches for the best hybrid combination of light-weight convolution layers and memory-efficient self-attention layers.
  arXiv  Detail & Related papers  (2024-03-15T15:47:54Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB)<n>We introduce an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor.<n>We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
  Vision Transformers (ViTs) have achieved impressive performance over various computer vision tasks. We propose Single-Path Vision Transformer pruning (SPViT) to efficiently and automatically compress the pre-trained ViTs. Our SPViT can trim 52.0% FLOPs for DeiT-B and get an impressive 0.6% top-1 accuracy gain simultaneously.
  arXiv  Detail & Related papers  (2021-11-23T11:35:54Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  Vehicle routing problem (VRP) is a typical discrete optimization problem. Many studies consider learning-based optimization algorithms to solve VRP. This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.
  arXiv  Detail & Related papers  (2021-07-15T02:13:03Z)
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach [9.717648122961483]
  Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics systems. Traditional methods incur the dilemma between computational efficiency and solution quality. We propose a novel reinforcement learning algorithm called the Multi-Agent Attention Model that can solve routing problem instantly benefit from lengthy offline training.
  arXiv  Detail & Related papers  (2020-02-13T14:26:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.