用张量加速车辆路径规划的局部搜索,大幅提升计算效率。
Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration
- 基于属性的张量表示,将局部搜索运算全迁至GPU并行处理。
- 在三个路由问题基准上,速度比传统CPU实现快数倍。
- 适用于多种车辆路径变体,适合需要快速求解的工业场景。
局部搜索在众多高效的车辆路径问题(VRP)及其变体启发式算法中起核心作用。然而,邻域探索通常计算成本高且耗时,尤其对大规模实例或含复杂约束的问题更为明显。本文提出一种新颖的张量基GPU加速方法,用于加速车辆路径中常用的局部搜索算子。通过属性化表示,该方法具有广泛可扩展性,适用于不同VRP变体。其低耦合架构将密集计算完全卸载至GPU,可无缝集成到各类基于局部搜索的算法与框架中,显著提升计算效率,可能改善解的质量。在三个路由问题的基准实例上进行对比实验,结果表明该方法相比传统CPU实现具有显著计算优势。我们还对方法的优势与局限进行了详细分析,揭示其性能特征并识别实际应用中的潜在瓶颈。这些发现有助于深入理解该方法,并为未来改进提供方向。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。