Edge-DIRECT: A Deep Reinforcement Learning-based Method for Solving Heterogeneous Electric Vehicle Routing Problem with Time Window Constraints

📄 arXiv: 2407.01615v1 📥 PDF

作者: Arash Mozhdehi, Mahdi Mohammadizadeh, Xin Wang

分类: cs.LG, cs.AI

发布日期: 2024-06-28

💡 一句话要点

提出Edge-DIRECT，基于深度强化学习解决带时间窗约束的异构电动汽车路径优化问题

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

关键词: 车辆路径问题 电动汽车 时间窗约束 深度强化学习 图神经网络

📋 核心要点

  1. 现有车辆路径优化方法难以有效处理异构电动汽车的能量消耗差异和客户时间窗约束。
  2. Edge-DIRECT通过引入图表示增强节点连接，并利用双重注意力机制有效处理电动汽车异构性。
  3. 实验表明，Edge-DIRECT在求解质量和执行时间上优于现有DRL方法和启发式算法。

📝 摘要（中文）

为了响应发达国家的碳中和政策，电动汽车路径优化对于物流公司来说变得越来越重要。随着对客户期望的日益关注以及向更以客户为导向的商业模式的转变，整合交付时间窗已成为物流运营的关键。本文研究了带时间窗约束的异构电动汽车路径问题（HEVRPTW）。为了解决这种车辆路径问题（VRP）的变体，我们提出了一种基于深度强化学习（DRL）的方法，名为Edge-enhanced Dual attentIon encoderR and feature-EnhanCed dual aTtention decoder (Edge-DIRECT)。Edge-DIRECT的特点是增加了一个图表示，其节点连通性基于客户时间窗的重叠。Edge-DIRECT的自注意力编码机制通过利用位置之间的能量消耗和旅行时间得到增强。为了有效地考虑电动汽车车队的异构性，引入了双重注意力解码器。基于两个真实世界数据集的实验结果表明，Edge-DIRECT在解决方案质量和执行时间方面优于最先进的基于DRL的方法和一种成熟的启发式方法。此外，与另一种领先的启发式方法相比，它表现出具有竞争力的性能。

🔬 方法详解

问题定义：论文旨在解决带时间窗约束的异构电动汽车路径问题（HEVRPTW）。现有方法在处理电动汽车异构性（不同型号的电动汽车具有不同的能耗和行驶特性）以及客户时间窗约束方面存在不足，难以在实际应用中获得高效的路径规划方案。

核心思路：论文的核心思路是利用深度强化学习（DRL）框架，结合图神经网络和注意力机制，学习一个能够有效处理HEVRPTW问题的策略。通过引入额外的图表示来增强节点连接信息，并利用双重注意力机制来处理电动汽车的异构性，从而提高路径规划的效率和质量。

技术框架：Edge-DIRECT的整体框架包括一个Edge-enhanced Dual Attention Encoder和一个Feature-Enhanced Dual Attention Decoder。Encoder负责将HEVRPTW问题编码成一个图表示，其中节点表示客户位置，边表示位置之间的连接关系。Decoder则基于编码后的图表示，逐步生成车辆的行驶路径。该框架利用强化学习算法进行训练，目标是最大化奖励函数，奖励函数与路径长度、车辆能耗和时间窗约束相关。

关键创新：Edge-DIRECT的关键创新在于以下几点：1) 引入了一个额外的图表示，其节点连通性基于客户时间窗的重叠，从而更好地捕捉了时间窗约束的影响。2) 利用能量消耗和旅行时间信息增强了自注意力编码机制，从而更准确地建模了电动汽车的行驶特性。3) 引入了双重注意力解码器，从而能够有效地处理电动汽车车队的异构性。与现有方法相比，Edge-DIRECT能够更有效地处理HEVRPTW问题，并获得更好的路径规划方案。

关键设计：Edge-DIRECT的关键设计包括：1) 图表示的构建方式，节点之间的连接强度与时间窗的重叠程度相关。2) 自注意力编码器的设计，利用能量消耗和旅行时间信息增强注意力权重。3) 双重注意力解码器的设计，分别关注车辆类型和客户需求。4) 奖励函数的设计，综合考虑了路径长度、车辆能耗和时间窗约束。这些设计共同保证了Edge-DIRECT能够有效地解决HEVRPTW问题。

🖼️ 关键图片

fig_0

📊 实验亮点

在两个真实世界数据集上的实验结果表明，Edge-DIRECT在解决方案质量和执行时间方面优于最先进的基于DRL的方法和一种成熟的启发式方法。与另一种领先的启发式方法相比，Edge-DIRECT也表现出具有竞争力的性能。具体提升幅度未知，但整体性能优于对比方法。

🎯 应用场景

Edge-DIRECT可应用于城市物流配送、电商物流、冷链物流等领域，为物流企业提供高效、节能的电动汽车路径规划方案。通过优化车辆行驶路线，降低运营成本，减少碳排放，提升客户满意度，助力物流行业实现可持续发展。

📄 摘要（原文）

In response to carbon-neutral policies in developed countries, electric vehicles route optimization has gained importance for logistics companies. With the increasing focus on customer expectations and the shift towards more customer-oriented business models, the integration of delivery time-windows has become essential in logistics operations. Recognizing the critical nature of these developments, this article studies the heterogeneous electric vehicle routing problem with time-window constraints (HEVRPTW). To solve this variant of vehicle routing problem (VRP), we propose a DRL-based approach, named Edge-enhanced Dual attentIon encoderR and feature-EnhanCed dual aTtention decoder (Edge-DIRECT). Edge-DIRECT features an extra graph representation, the node connectivity of which is based on the overlap of customer time-windows. Edge-DIRECT's self-attention encoding mechanism is enhanced by exploiting the energy consumption and travel time between the locations. To effectively account for the heterogeneity of the EVs' fleet, a dual attention decoder has been introduced. Experimental results based on two real-world datasets reveal that Edge-DIRECT outperforms a state-of-the-art DRL-based method and a well-established heuristic approach in solution quality and execution time. Furthermore, it exhibits competitive performance when compared to another leading heuristic method.