Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration

• URL: http://arxiv.org/abs/2506.17357v1
• Date: Fri, 20 Jun 2025 07:40:47 GMT
• Title: Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration
• Authors: Zhenyu Lei, Jin-Kao Hao, Qinghua Wu,
• Abstract summary: 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.
• Score: 23.87172157992149
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Local search plays a central role in many effective heuristic algorithms for the vehicle routing problem (VRP) and its variants. However, neighborhood exploration is known to be computationally expensive and time consuming, especially for large instances or problems with complex constraints. In this study, we explore a promising direction to address this challenge by introducing an original tensor-based GPU acceleration method designed to speed up the commonly used local search operators in vehicle routing. By using an attribute-based representation, the method offers broad extensibility, making it applicable to different VRP variants. Its low-coupling architecture, with intensive computations completely offloaded to the GPU, ensures seamless integration in various local search-based algorithms and frameworks, leading to significant improvements in computational efficiency and potentially improved solution quality. Through comparative experiments on benchmark instances of three routing problems, we demonstrate the substantial computational advantages of the proposed approach over traditional CPU-based implementations. We also provide a detailed analysis of the strengths and limitations of the method, providing valuable insights into its performance characteristics and identifying potential bottlenecks in practical applications. These findings contribute to a better understanding and suggest directions for future improvements.

Related papers

• DELTAv2: Accelerating Dense 3D Tracking [79.63990337419514]
  We propose a novel algorithm for accelerating dense long-term 3D point tracking in videos.<n>We introduce a coarse-to-fine strategy that begins tracking with a small subset of points and progressively expands the set of tracked trajectories.<n>The newly added trajectories are using a learnable module, which is trained end-to-end alongside the tracking network.
  arXiv  Detail & Related papers  (2025-08-02T03:15:47Z)
• Learning to Search for Vehicle Routing with Multiple Time Windows [13.91760960564074]
  We propose a reinforcement learning-based adaptive variable neighborhood search (RL-AVNS)<n>Our method integrates a reinforcement learning framework to dynamically select neighborhood operators based on real-time solution states and learned experience.
  arXiv  Detail & Related papers  (2025-05-29T05:03:28Z)
• Learning with Local Search MCMC Layers [11.772298193297013]
  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)
• Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks [0.47248250311484113]
  We introduce a novel and efficient algorithm for solving the maximum weighted independent set (MWIS) problem.<n>Given the NP-hard nature of the MWIS problem, our proposed algorithm, DynLS, incorporates three key innovations to solve it effectively.<n>Our experimental results demonstrate DynLS's superior performance, consistently delivering high-quality solutions within 1000 seconds.
  arXiv  Detail & Related papers  (2025-05-07T10:35:53Z)
• Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics [3.5112462023222504]
  We present a ride-pool simulator that encompasses several key ride-pool assignment algorithms, along with associated components such as vehicle routing and rebalancing.<n>We also open-source a highly optimized and modular C++, designed to facilitate extension of new algorithms.<n>Experiments on a large-scale, real-world dataset from Manhattan, NYC reveal that while all selected algorithms perform comparably, the newly proposed Multi-Round Linear Assignment with Cyclic Exchange achieves a state-of-the-art service rate with significantly reduced computational time.
  arXiv  Detail & Related papers  (2025-04-14T19:01:47Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms.<n>For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  We introduce OptVQ, a novel vector quantization method that employs the Sinkhorn algorithm to optimize the optimal transport problem.<n>Our experiments on image reconstruction tasks demonstrate that OptVQ achieves 100% codebook utilization and surpasses current state-of-the-art VQNs in reconstruction quality.
  arXiv  Detail & Related papers  (2024-12-19T18:58:14Z)
• Enhancing Dropout-based Bayesian Neural Networks with Multi-Exit on FPGA [20.629635991749808]
  This paper proposes an algorithm and hardware co-design framework that can generate field-programmable gate array (FPGA)-based accelerators for efficient BayesNNs. At the algorithm level, we propose novel multi-exit dropout-based BayesNNs with reduced computational and memory overheads. At the hardware level, this paper introduces a transformation framework that can generate FPGA-based accelerators for the proposed efficient BayesNNs.
  arXiv  Detail & Related papers  (2024-06-20T17:08:42Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  We propose a decompose-route-improve (DRI) framework that groups customers using clustering. Its similarity metric incorporates customers' spatial, temporal, and demand data. We apply pruned local search (LS) between solved subproblems to improve the overall solution.
  arXiv  Detail & Related papers  (2024-01-20T06:06:01Z)
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
  We propose a Laplacian enhanced low-rank tensor (LETC) framework featuring both lowrankness and multi-temporal correlations for large-scale traffic speed kriging. We then design an efficient solution algorithm via several effective numeric techniques to scale up the proposed model to network-wide kriging.
  arXiv  Detail & Related papers  (2022-10-21T07:25:57Z)
• Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
  Vehicle Re-Identification is one of the key elements in city-scale vehicle analytics systems. Many state-of-the-art solutions for vehicle re-id mostly focus on improving the accuracy on existing re-id benchmarks and often ignore computational complexity. We propose a simple yet effective hybrid solution empowered by self-supervised training which only uses a single network during inference time.
  arXiv  Detail & Related papers  (2022-05-16T12:14:42Z)
• Reinforcement Learning for Datacenter Congestion Control [50.225885814524304]
  Successful congestion control algorithms can dramatically improve latency and overall network throughput. Until today, no such learning-based algorithms have shown practical potential in this domain. We devise an RL-based algorithm with the aim of generalizing to different configurations of real-world datacenter networks. We show that this scheme outperforms alternative popular RL approaches, and generalizes to scenarios that were not seen during training.
  arXiv  Detail & Related papers  (2021-02-18T13:49:28Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

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.