一种高效的动态感知型深度强化学习方法，用于解决具有服务时间窗口和分时电价约束的电动汽车路径规划问题

《Applied Energy》：Efficient dynamic-aware deep reinforcement learning for solving capacitated electric vehicle routing problems with service time windows and time-of-use electricity prices

　　关庆树|曹晖|庄金妮|欧贝|陈柏东
中国西安交通大学电气工程学院，西安710049

摘要
在现代交通与可持续能源体系中，电动汽车路线规划问题日益受到重视，这得益于电动汽车在减少碳排放及降低化石燃料使用方面的潜力。尽管在电动汽车路线优化方面已取得显著进展，但如何同时考虑成本敏感型路线选择、服务时间限制、车辆容量约束、分时电价以及真实的电动汽车能耗情况，这一问题仍缺乏充分研究。为应对这些挑战，本研究探讨了一种以经济性为导向、包含服务时间限制与分时电价的带容量约束电动汽车路线规划问题（CEVRP-TWEP），其目标是通过综合考虑运输成本与充电成本来最小化总运营成本。研究还构建了更为精确的能耗模型，以更真实地反映车辆行驶特性、负载相关的驾驶行为以及实际工况下的充电过程。该问题被建模为马尔可夫决策过程，进而提出了一种基于编码器-精炼器-解码器架构的高效动态感知深度强化学习框架——EDA-DRL。其中，编码器采用图引导的稀疏注意力机制，以更高的计算效率获取具有表达力的节点表示；精炼器则将静态节点属性与动态车辆状态相结合，从而在每一步决策中更新上下文表示，实现时间依赖型系统条件的精准建模；解码器则通过兼容性层进行节点选择，为路线规划生成高质量决策。在合成数据集与真实世界数据集上的大量实验表明，EDA-DRL的性能始终优于多种启发式算法及基于学习的基准方法，与竞争性的基于DRL的Heter-AM模型相比，总运营成本可降低多达6.33%。此外，EDA-DRL在不同规模及空间分布的问题上均展现出较强的泛化能力，证明了其在智能能源与交通系统中用于实际电动汽车路线规划的实用性与扩展性。

引言
生态系统日益恶化以及化石资源日益枯竭，使得交通电气化成为实现低碳出行的关键途径[1][2]。电动汽车为传统化石燃料驱动的出行方式提供了可持续的替代方案，有助于减少碳排放、提升能源效率，并推动可再生能源在交通系统中的应用[3][4]。然而，要实现这些优势，不仅需要电池及驱动系统技术的进步[5]，还需要开发高效的路线规划与充电策略，以同时优化运营成本、可靠性与效率[6]。这一问题被正式定义为电动汽车路线规划问题（EVRP）[7]，即电动汽车从起点出发，为地理位置分散且需求各异的客户提供服务，可在可用充电站进行充电，最终完成任务后返回起点。其目标是在满足各种运营及系统约束的前提下，最小化总行驶距离。因此，高效解决这一问题对于将电动汽车从低排放车辆转变为可持续、注重能源效率的物流系统中的高效资产至关重要[8][9]。

不同的充电时间以及有限的电池容量加剧了续航焦虑，给高效的电动汽车路线规划带来了巨大挑战[10][11]。这些因素使得寻找成本效益高的路线规划策略愈发困难，尤其是在大规模或动态变化的环境中[12]。传统的EVRP求解方法主要分为两类：精确优化方法，如分支定界法[13]，虽然能够得到最优解，但其计算成本会随着问题规模的增大而迅速上升，因此不适用于大规模问题；而启发式方法，如模拟退火法[14]、蚁群优化法[15]以及大邻域搜索法[16]，则通过设计特定的搜索策略来高效探索解空间，往往能在合理时间内得到高质量解。不过，这类启发式方法的优化过程需要大量试错迭代，且最终性能在很大程度上取决于领域专家的经验。更根本的是，无论是精确优化方法还是启发式方法，都是孤立地处理单个路线规划问题，未能利用大规模数据集中的共性结构模式[17]。这一局限性限制了它们利用数据驱动的洞察力来提升可扩展性与泛化能力，而这在现实世界的电动汽车路线规划应用中越来越重要[18]。

随着深度学习[19]与GPU加速计算[20]的快速发展，人们越来越倾向于将深度强化学习应用于组合优化问题[21][22]。在这种框架下，电动汽车路线规划可被视为一个序贯控制问题，被建模为马尔可夫决策过程（MDP），其中智能体通过与不断变化的系统状态交互逐步构建路线。借助Transformer等强大的神经网络架构[23]，DRL模型能够有效捕捉大规模问题中的复杂结构模式，同时利用并行计算实现高效训练[24]。值得注意的是，这些方法已能获得接近最优的解，且相比传统启发式方法，对手工设计的规则依赖程度更低[25]。更广泛地说，DRL提供了一种数据驱动的框架，用于学习自适应的路线规划策略，为将智能优化技术融入现实世界的交通与能源系统开辟了新路径，在日益自动化且注重可持续性的基础设施中，电动汽车可作为响应迅速的智能体发挥作用。

尽管现有的基于DRL的EVRP解决方法在实证表现上十分出色，但仍存在若干重要局限。一些基于优化的研究已经超越了单纯的最小化行驶距离的目标，开始考虑运营成本与随时间变化的电价，但这些进展尚未完全体现在基于学习的电动汽车路线规划模型中。许多基于DRL的方法仍然依赖于以距离或简化后的能耗为导向的目标函数，很少能在统一的策略学习框架中将分时充电成本、服务时间限制、车辆容量约束以及真实的道路行驶能耗等因素结合起来。实际上，电动汽车在行驶过程中的能耗不仅受路线长度的影响，还与车辆动力学特性、滚动阻力、空气阻力、道路坡度以及充电效率密切相关。而这些物理因素往往被简化或忽略，可能导致学习到的路线规划与充电策略在真实物流环境中的准确性下降。从方法论角度来看，现有的编码器-解码器框架虽然能够以构建式的方式生成路线解决方案，但由于节点与环境表示在整个过程中保持不变，因此难以捕捉动态的车辆状态及不断变化的系统条件。此外，在编码阶段，典型的基于学习的方法会利用大规模的Transformer网络来计算图中所有节点之间的全量 pairwise注意力，虽然这种方法在问题规模适中时效果良好，但对于大规模场景而言却会带来较高的计算开销。这些挑战凸显出需要更先进的框架，这类框架应具备真实的物理建模能力、支持动态状态表示，并能在处理大规模电动汽车调度问题时实现更高的计算效率。

为克服现有电动汽车路线规划方法的局限性，本研究聚焦于一种更为真实且更具挑战性的问题变体，即包含服务时间限制与分时电价的带容量约束电动汽车路线规划问题（CEVRP-TWEP）。在此模型中，电动汽车需为地理位置分散、需求各异且具有不同服务时间要求的客户提供服务，可在分时电价下的充电站进行充电，同时还需遵循由实际能耗与充电要求所决定的续航限制。其目标是通过综合考虑运输成本与充电成本，来最小化总运营成本。为便于有效的策略学习，CEVRP-TWEP被建模为一种定制化的马尔可夫决策过程，同时开发了名为EDA-DRL的高效动态感知深度强化学习框架，以实现其在不同问题规模与空间分布下的通用性。此外，研究还引入了改进的能耗模型，通过纳入行驶阻力、道路坡度、车辆动力学特性以及充电效率等因素，更准确地描述电动汽车的能耗情况，而这些因素对路线规划与充电决策至关重要。

基于这一模型框架，本研究设计了编码器-精炼器-解码器（ERD）框架，用于在动态且具有约束条件的路线规划环境中进行序贯决策。编码器通过图引导的稀疏注意力机制，将原始问题特征转换为具有表达力的节点嵌入，使得每个节点仅关注稀疏图中的结构相关邻居，从而在提升计算效率与可扩展性的同时，捕捉到局部与全局的结构依赖关系。在路线规划过程中，为反映系统状态的动态变化，精炼器会在每一步决策中通过融合静态节点属性与动态车辆信息（包括位置、剩余载重、经过时间以及电池电量）来更新上下文表示。在解码阶段，环境标记既反映了图的结构，也体现了电动汽车当前的运行状态，通过基于兼容性的注意力机制指导节点选择。整个框架则采用基于策略梯度的DRL方法进行优化，同时借助基准网络来降低梯度方差，提高收敛稳定性。

EDA-DRL的路线规划性能在具有不同问题规模、空间分布及运营复杂度的合成数据集与真实世界数据集上进行了评估。实验结果表明，EDA-DRL的运营成本始终低于各类代表性的启发式算法及基于DRL的基准方法。在包含200个客户与40个充电站的大规模场景中，该方法可使每辆车的每日运营成本降低多达31.50美元，且相对优势可提升至6.33%。此外，EDA-DRL在更复杂的场景中也表现出较强的泛化能力，包括传统的EVRP基准测试案例以及真实的JD物流数据集。这些结果表明，所提出的框架能够有效捕捉复杂的运营动态，非常适合用于大规模、注重成本控制的电动汽车路线规划应用。

主要贡献如下：
•研究了另一种更具现实意义且更为复杂的电动汽车路线规划问题变体，即包含服务时间限制与分时电价的EVRP-TWEP问题。为体现其序贯性与随机性特征，该问题被建模为马尔可夫决策过程，为基于强化学习的优化提供了理论基础。
•开发了一种基于新型编码器-精炼器-解码器架构的高效动态感知DRL框架，用于解决复杂路线规划动态建模中的可扩展性问题。在编码器中，采用了稀疏图引导的注意力机制，既能够学习有用的节点表示，又保持了较高的计算效率。
•引入了精炼模块，通过将静态节点属性与动态车辆状态相结合，实现上下文表示的动态更新，从而使模型能够准确描述路线规划过程中出现的状态转换与结构变化。
•在具有不同规模与空间特征的合成数据集及真实世界数据集上进行了大量实验，结果表明EDA-DRL在电动汽车路线规划与充电决策方面取得了显著改进，有效降低了总运营成本。

章节节选
EVRP的传统解决方法
EVRP已成为运筹学与智能物流领域的核心研究主题，这反映了在实现碳减排目标与保障能源系统可持续发展的同时，协调货物运输需求的迫切需求[26][27]。现有的解决方法大致可分为精确优化方法与启发式方法两类，二者分别基于不同的建模假设与计算权衡。精确优化方法，如列生成法[28]与分支定界法[13]，通常将EVRP问题进行形式化建模……

问题建模
在本节中，我们首先在有向图上对CEVRP-TWEP问题进行建模，明确界定路线结构及相关运营约束。随后，我们构建了一个基于物理原理的能耗与充电成本模型，该模型能够反映车辆动力学特性、阻力作用、道路状况、充电行为以及分时电价等因素。最后，我们给出了该问题的数学表述，其目标是最小化电动汽车的总运营成本。

方法论
在本节中，我们介绍了用于处理CEVRP-TWEP中所存在的实际复杂问题的EDA-DRL方法。首先，我们将路线规划过程建模为马尔可夫决策过程，以此体现问题的结构特征。接着，我们详细描述了创新的编码器-精炼器-解码器架构，重点介绍了其网络设计及功能组件。最后，我们阐述了用于模型优化的训练策略。

实验
在本节中，我们介绍了CEVRP-TWEP问题数据生成过程、实验方案以及评估指标。我们在具有不同规模与空间结构的合成数据集及真实世界数据集上，将该框架与多种启发式算法及基于学习的基准方法进行了系统比较。为进一步评估模型的鲁棒性，我们还考察了所学策略在训练数据之外的泛化能力，即在更大规模问题及不同条件下的性能表现。

结论
本研究针对一种更为真实且具有挑战性的电动汽车路线规划问题变体——即CEVRP-TWEP进行了研究，该问题将服务时间限制与分时电价共同纳入总运营成本优化之中。为解决这一问题，我们将路线规划过程建模为马尔可夫决策过程，并开发了一种高效的动态感知深度强化学习框架。所提出的编码器-精炼器-解码器架构能够整合图结构特征……

CRediT作者贡献说明
关庆树：撰写——初稿、软件实现、方法论设计、概念构思。
曹晖：撰写——审稿与编辑、监督工作、资源协调、项目管理、方法论设计。
庄金妮：验证工作、软件实现、问题研究、形式化分析。
欧贝：软件实现、方法论设计、数据整理。陈巴东：写作——审稿与编辑、项目监督、项目管理。利益冲突声明作者声明不存在任何可能影响本文所述工作的已知财务利益或个人关系。致谢本研究部分得到了中国国家自然科学基金重点项目的支持，项目编号为62436005；中国国家自然科学基金联合基金的资助，项目编号为U25A20540；中国国家自然科学基金专项基金的支持，项目编号为32541016；以及中国国家自然科学基金的资助，项目编号为62306232。