Learning to Route Electric Trucks Under Operational Uncertainty

以下是论文《学习在运营不确定性下调度电动卡车》的详细技术总结。

1. 问题定义：电动卡车车队路径规划问题 (eTFRP)

本文解决了电动卡车车队路径规划问题 (eTFRP)，这是针对重型电动卡车量身定制的经典车辆路径问题 (VRP) 的复杂扩展。与标准路径规划问题不同，eTFRP 涉及一个耦合的物流与能源管理挑战，其特征包括：

• 共享充电基础设施： 多辆卡车在容量有限的站点争夺有限的充电端口，导致内生的排队延误。
• 运营不确定性： 行驶时间、能耗和卸货时长是随机的（建模为截断高斯分布），受交通拥堵和天气影响。
• 现实的充电动态： 问题纳入了非线性的直流快充行为（恒流 - 恒压或 CCCV），即随着电池荷电状态 (SoC) 的增加，充电功率逐渐降低，而非假设线性充电。
• 车队级耦合： 决策是相互依赖的；一辆卡车的路线可行性取决于车队中其他卡车的行为（例如，如果某站点被其他车辆拥堵）。

目标是最小化整个车队完成所有配送的预期总时间，包括行驶、充电、等待和卸货时间，同时确保能源可行性（避免电池耗尽）。

2. 方法论

作者提出了一种使用强化学习 (RL) 的基于学习的框架来解决 eTFRP。其核心组件包括：

A. 问题建模

该问题被建模为一个事件驱动的半马尔可夫决策过程 (SMDP)。

• 状态空间： 仅在卡车进入“待执行动作”状态（例如，到达某个节点后）时做出决策。状态表示为包含三种节点类型的异构图：卡车、配送点和充电站。
• 动作空间： 动作空间是可变且依赖于状态的。它包括导航至配送点或充电器，或选择充电时长。为确保运营可行性，应用了基于规则的动作掩码，将策略限制为仅允许的动作（例如，如果电池能量不足，则禁止导航至目的地）。
• 奖励函数： 使用基于时间的奖励来最小化总运营时间，并对失败（电池耗尽）施加惩罚，对完成的配送给予奖励。

B. GraphPPO 架构

作者引入了 GraphPPO，这是一种基于图神经网络 (GNN) 的近端策略优化 (PPO) 算法。

• 状态编码器： 使用带有异构交互层的异构图编码器来处理系统状态图。这使得模型能够捕捉卡车、基础设施和配送之间的交互，同时保持对实体数量的不变性（可扩展性）。
• 动作编码器： 可行动作集也被编码为图。Actor 网络根据全局状态嵌入对这些动作节点进行评分，以产生可行动作上的概率分布。
• 训练： 模型使用带有广义优势估计 (GAE) 的 PPO 算法进行训练，通过优化截断的代理目标来确保策略更新的稳定性。

C. 仿真环境

开发了一个自定义的事件驱动仿真环境（基于 Gymnasium 构建），以支持训练和基准测试。它模拟了：

• 随机的行驶和能耗。
• 非线性的 CCCV 充电曲线。
• 充电站的先到先服务 (FCFS) 排队。
• 来自加利福尼亚州的真实道路网络数据。

3. 主要贡献

1. 现实的问题建模： 本文将 eTFRP 建模为事件驱动的 SMDP，明确模拟共享充电资源、随机行驶/能耗以及非线性充电行为，超越了以往文献中简化的抽象。
2. 基于可行性的图基强化学习： 引入了 GraphPPO，将 GNN 与显式的动作可行性掩码相结合。这确保了 RL 智能体学习到的策略在运营上是有效的（例如，遵守电池约束和站点容量），而无需依赖事后修复机制。
3. 全面的基准测试： 开发了一个统一的仿真环境，允许在一致的随机假设下，直接比较基于学习的方法、数学优化 (MILP) 和元启发式基线。
4. 可扩展性与泛化性： 该框架展示了从单车到大规模车队场景（多达 100 辆卡车）的可扩展性，并表现出强大的零样本泛化能力。

4. 实验结果

该研究在多种车队规模（1 到 100 辆卡车）下，将 GraphPPO 与数学优化 (Math. Opt.)、启发式算法、通用 PPO 以及 MaskPPO（带动作掩码但无图结构的 PPO) 进行了评估。

• 性能与车队规模的关系：

  • GraphPPO 在所有车队规模下始终实现了接近最优的性能（归一化奖励 0.987–1.005），并保持高成功率（例如，50 辆卡车时为 76.5%，而通用 PPO 为 0%）。
  • 通用 PPO 由于无法处理复杂的可行性约束，在较大规模设置中完全失败（成功率为 0%）。
  • MaskPPO 在小规模设置中表现良好，但随着车队规模增加显著退化（100 辆卡车时成功率降至 2%），突显了基于图的状态表示对于捕捉车队级拥堵的必要性。
  • 数学优化 提供了强有力的基线，但在大规模随机设置中，其可扩展性和计算时间面临挑战。

• 零样本泛化：

  • 一个仅在 100 辆卡车设置 (100T3S) 下训练的策略被应用于更小和更大的配置，而无需重新训练。
  • 该策略有效地进行了泛化，通常在大型拥堵场景中优于保守的数学优化基准（50–100 辆卡车的胜率 >70%）。

• 单车 eVRP：

  • 在单车设置 (1T20S) 中，GraphPPO 实现了接近最优的奖励（数学优化的 99.7%），同时大幅减少了计算时间（0.8 秒 vs. 数学优化的 233 秒）。

• 运营洞察：

  • GraphPPO 比启发式算法更有效地利用电池（更低的剩余 SoC），并且比 MaskPPO 更好地管理充电队列，从而降低了总等待时间。

5. 意义

本文在绿色物流和自主车队管理领域做出了重要贡献：

• 弥合差距： 它成功弥合了数学规划的理论最优性与基于学习的方法的可扩展性之间的差距。
• 处理不确定性： 它证明了 RL 可以有效管理复杂的耦合不确定性（交通、能源、排队），而这些不确定性使得传统启发式算法和静态优化在实时场景中失效。
• 实际部署： 所提出的框架为现实世界的电动货运运营提供了解决方案，能够即使在大型拥堵车队中也能在实时（亚秒级推理）内做出高质量、可行的路径规划决策。
• 未来影响： 这项工作为将电网约束、动态定价和预约系统集成到基于学习的物流中奠定了基础，推动了货运交通的脱碳进程。