SED2AM: Solving Multi-Trip Time-Dependent Vehicle Routing Problem using Deep Reinforcement Learning

📄 arXiv: 2503.04085v1 📥 PDF

作者: Arash Mozhdehi, Yunli Wang, Sun Sun, Xin Wang

分类: cs.AI, cs.LG

发布日期: 2025-03-06

备注: Accepted by ACM TKDD: https://dl.acm.org/doi/10.1145/3721983

DOI: 10.1145/3721983

💡 一句话要点

提出SED2AM，利用深度强化学习解决带最大工作时间约束的多车次时变车辆路径问题

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

关键词: 车辆路径问题 深度强化学习 时变性 多车次 城市物流 Transformer 注意力机制

📋 核心要点

  1. 现有的基于Transformer的深度强化学习方法在车辆路径问题变体中表现出色，但在城市物流关键的多车次时变车辆路径问题(MTTDVRP)上的应用仍待探索。
  2. SED2AM通过引入时间局部性归纳偏置的编码模块和车辆选择、行程构建双解码器，有效处理MTTDVRP中的时间依赖性和多车次约束。
  3. 实验结果表明，SED2AM在真实数据集上优于现有DRL和元启发式基线，并展现出良好的泛化能力，能够解决更大规模的问题。

📝 摘要（中文）

本文提出了一种基于深度强化学习(DRL)的方法，称为同步编码器和双解码器注意力模型(SED2AM)，专门用于解决带最大工作时间约束的多车次时变车辆路径问题(MTTDVRP)。该方法在策略网络的编码模块中引入了时间局部性归纳偏置，使其能够有效地考虑旅行距离或时间中的时间依赖性。SED2AM的解码模块包括一个车辆选择解码器，用于从车队中选择车辆，有效地将行程与车辆关联起来，实现多车次路径规划。此外，该解码模块还配备了一个行程构建解码器，用于为车辆构建行程。该策略模型配备了两类状态表示：车队状态和路径状态，为在最大工作时间约束下有效构建路线提供所需的信息。使用来自加拿大两个主要城市的真实数据集进行的实验结果表明，SED2AM不仅优于当前最先进的基于DRL和基于元启发式的基线方法，而且还证明了其解决更大规模问题的泛化能力。

🔬 方法详解

问题定义：论文旨在解决带最大工作时间约束的多车次时变车辆路径问题(MTTDVRP)。现有的车辆路径问题方法，特别是基于深度学习的方法，在处理时变性和多车次约束方面存在不足，难以有效优化城市物流场景下的车辆调度。

核心思路：论文的核心思路是利用深度强化学习框架，设计一个能够同时考虑时间依赖性和多车次约束的策略网络。通过引入时间局部性归纳偏置，使模型能够更好地学习时变信息。同时，采用双解码器结构，分别负责车辆选择和行程构建，从而实现多车次的路径规划。

技术框架：SED2AM的整体框架包括一个编码器和一个双解码器。编码器负责提取问题特征，特别是时间依赖性信息。双解码器分别负责车辆选择和行程构建。编码器采用Transformer结构，并引入时间局部性归纳偏置。车辆选择解码器从车队中选择车辆，行程构建解码器为选定的车辆构建行程。整个过程通过强化学习进行训练，目标是最小化总的运输成本。

关键创新：SED2AM的关键创新在于以下几点：1) 引入时间局部性归纳偏置，使模型能够更好地学习时变信息；2) 采用双解码器结构，分别负责车辆选择和行程构建，从而实现多车次的路径规划；3) 提出车队状态和路径状态两种状态表示，为有效构建满足最大工作时间约束的路线提供信息。与现有方法相比，SED2AM能够更有效地处理MTTDVRP中的时间依赖性和多车次约束。

关键设计：编码器采用Transformer结构，并引入时间局部性归纳偏置，具体实现方式未知。解码器采用注意力机制，用于选择车辆和构建行程。损失函数采用强化学习中的策略梯度方法，目标是最小化总的运输成本。具体参数设置未知。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，SED2AM在两个加拿大主要城市的真实数据集上，优于当前最先进的基于DRL和基于元启发式的基线方法。具体性能提升数据未知。此外，SED2AM还展现出良好的泛化能力，能够解决更大规模的问题，证明了其在实际应用中的潜力。

🎯 应用场景

该研究成果可应用于城市物流、快递配送、外卖配送等领域，能够优化车辆调度，降低运输成本，提高服务效率。通过考虑交通状况的时变性，可以更合理地规划路线，减少拥堵带来的延误。同时，多车次约束的引入，使得车辆能够执行多次运输任务，提高车辆利用率。该研究对于构建智能物流系统具有重要意义。

📄 摘要（原文）

Deep reinforcement learning (DRL)-based frameworks, featuring Transformer-style policy networks, have demonstrated their efficacy across various vehicle routing problem (VRP) variants. However, the application of these methods to the multi-trip time-dependent vehicle routing problem (MTTDVRP) with maximum working hours constraints -- a pivotal element of urban logistics -- remains largely unexplored. This paper introduces a DRL-based method called the Simultaneous Encoder and Dual Decoder Attention Model (SED2AM), tailored for the MTTDVRP with maximum working hours constraints. The proposed method introduces a temporal locality inductive bias to the encoding module of the policy networks, enabling it to effectively account for the time-dependency in travel distance or time. The decoding module of SED2AM includes a vehicle selection decoder that selects a vehicle from the fleet, effectively associating trips with vehicles for functional multi-trip routing. Additionally, this decoding module is equipped with a trip construction decoder leveraged for constructing trips for the vehicles. This policy model is equipped with two classes of state representations, fleet state and routing state, providing the information needed for effective route construction in the presence of maximum working hours constraints. Experimental results using real-world datasets from two major Canadian cities not only show that SED2AM outperforms the current state-of-the-art DRL-based and metaheuristic-based baselines but also demonstrate its generalizability to solve larger-scale problems.