Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

📄 arXiv: 2608.14156v1 📥 PDF

作者: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

分类: cs.LG

发布日期: 2026-08-14

💡 一句话要点

提出深度强化学习解决带时间窗和容量约束的货物配送问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 深度强化学习 货物配送 时间窗约束 容量约束 路径优化 JAMPR模型 物流调度

📋 核心要点

  1. 核心问题：现有方法在处理中大型的货物配送问题时，无法满足实时优化和复杂约束的需求。
  2. 方法要点：本文提出了一种基于深度强化学习的解决方案，利用修改后的JAMPR模型来优化配送路线。
  3. 实验或效果：实验结果表明，该模型在小型和中型问题上能够快速提供最优解，并在大型问题上提供快速的次优解。

📝 摘要（中文）

构建车辆的最优路线以进行货物的提取和配送是应对全球城市人口增长的重要任务。尽管小规模问题可以通过多种经典方法解决，但在现实世界的约束下（如容量和时间窗约束），中大型问题的快速（或实时）路线优化仍然是一个极具挑战的任务。本文首次成功应用深度强化学习方法（修改后的JAMPR模型）解决带容量和时间窗约束的提取与配送问题（CPDPTW）。我们获得了一个稳健的模型，能够为小型和中型问题提供快速的最优解，并为规模较大的问题（>200）提供快速的次优解。

🔬 方法详解

问题定义：本文旨在解决带有时间窗和容量约束的货物提取与配送问题（CPDPTW）。现有方法在面对中大型问题时，往往无法实现实时优化，且难以处理复杂的约束条件。

核心思路：论文的核心思路是应用深度强化学习，通过修改JAMPR模型来有效地学习和优化配送路线。这种方法能够在动态环境中快速适应并找到最优解。

技术框架：整体架构包括数据预处理、模型训练和路径优化三个主要模块。首先，收集和处理配送数据；然后，利用深度强化学习算法训练模型；最后，应用训练好的模型进行实时路径优化。

关键创新：最重要的技术创新在于将深度强化学习应用于CPDPTW问题，显著提高了求解效率和解的质量。这与传统的启发式或精确算法相比，具有更强的适应性和灵活性。

关键设计：在模型设计中，设置了适当的奖励函数以引导学习过程，并采用了深度神经网络结构来处理复杂的输入特征。此外，针对不同规模的问题，调整了网络的层数和节点数，以优化性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，所提出的模型在小型和中型问题上能够快速提供最优解，且在规模超过200的情况下，仍能提供快速的次优解。与传统方法相比，模型在求解效率上有显著提升，展示了深度强化学习在复杂约束条件下的应用潜力。

🎯 应用场景

该研究具有广泛的应用潜力，尤其在物流、快递配送和城市交通管理等领域。通过优化配送路线，可以显著提高运输效率，降低运营成本，并改善客户体验。未来，该方法还可以扩展到其他类型的调度和优化问题中。

📄 摘要（原文）

The task of constructing vehicles optimal routes for pickup and delivery of goods is one of most promising tasks in the context of global urban population growth. Although this kind of problems with small size can be solved by various classical approaches, a fast (or realtime) route optimizer under the constraints of the real world (such as capacity and time windows constraints) for medium-large size problems still remains a highly challenging task. In this work we, for the first time, successfully applied a deep Reinforcing Learning approach (modified JAMPR model) to solve Pickup and Delivery problem with Capacity and Time Window constraints (CPDPTW). We obtained a robust model that gives a fast optimal solution for problems of small and medium size, and gives fast suboptimal solution for problems of larger (> 200) size.