提出一种加速求解多仓库车辆路径问题的混合算法
A GPU-Accelerated Hybrid Method for a Class of Multi-Depot Vehicle Routing Problems
- 融合学习驱动的路径交换与多惩罚评估机制
- 在大规模实例上性能优于当前最优方法
- 适用于物流调度、智能配送等场景
多仓库车辆路径问题（MDVRPs）广泛存在于各类实际应用中，但因其内在复杂性，求解计算难度大。本文针对一类MDVRPs提出一种高效混合算法，结合学习驱动的多样性控制路径交换交叉算子与基于多惩罚评估函数的多仓库支持可行/不可行搜索框架，并引入两个专用的仓库相关局部搜索算子以增强多仓库环境下的搜索能力。为提升计算效率与可扩展性，开发了改进版本，采用基于张量的GPU加速与新型多步更新策略。在三类MDVRP基准实例上的大量实验表明，所提算法在大规模实例上表现优异，与当前最先进方法相比具有高度竞争力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。