电动车辆路径规划问题：考虑行驶时间和能耗不确定性的鲁棒研究

原文链接见文末

背景与研究问题

随着绿色物流的发展和新能源政策的推动，电动汽车（EV）在城市配送中的应用越来越广。然而，与传统燃油车相比，EV有诸多不确定性：行驶时间受天气、交通状况等外部因素影响，能耗也因路况、载重、气温等波动而变化。这些不确定性会导致提前或延迟到达客户、增加运营成本以及电量不足等风险。

以往文献多关注确定性参数或只考虑单一不确定性。本研究提出**“电动汽车路径规划问题—行驶时间和能耗双重不确定性”（EVRP‑TTECU）**，要求在满足软时间窗、部分充电策略和车辆数约束的前提下，制定对风险有抵抗力的路径和充电计划，使保守估计的总成本最小。

模型与技术核心

两阶段自适应鲁棒优化模型

作者使用两阶段自适应鲁棒优化建模。在第一阶段，确定车辆的行驶路径及各客户的装载决策；第二阶段在给定路径的情况下，根据真实出现的行驶时间和能耗情况，调整充电量和服务开始时间。为描述不确定性，作者设定了基于路径长度的“预算不确定集合”其中和分别是行驶时间和能耗的不确定度，约束了最坏情况下有多少条弧会出现最大偏差。模型目标函数包含固定车辆成本、行驶成本、能耗成本和客户不满意惩罚。

作者推导出一系列定理，说明当同时考虑行驶时间和能耗不确定性时，最优代价高于只考虑单一不确定性的TTU（Travel‑Time Uncertainty）和ECU（Energy‑Consumption Uncertainty）问题。为说明差异，论文给出了两个简单示例。在示例1（图1）中，车辆经过两位客户和一个充电站，在TTU或ECU情况下有可行的自适应决策，而在TTECU情况下由于充电量同时要满足最坏的能耗和不违反下一个客户的时间窗，反而无可行解。示例2（图2）则说明即便有可行解，考虑双重不确定性的成本高于单重不确定性。

图示示例

  • 图1 – 示例1的路径及不同模型下的决策。粗略表示不同弧的不确定区间和各模型下充电量、能耗和到达时间的决策。
  • 图2 – 示例2在给定成本参数下的不同模型决策与成本对比，显示TTECU的保守成本更高。

路径依赖辅助变量与递归约束

直接列举不确定集合的所有极点非常庞大，为验证路径的鲁棒可行性，作者提出了路径依赖的辅助变量和约束。通过引入辅助变量  和  分别表示在给定累计不确定度下的最晚到达时间和最小电量，建立递推方程来计算各节点的最坏情况，到达充电站时再计算所需充电量。这种方法不需要枚举所有极点，只需针对每条弧的最大偏差递归求解，从而显著减小约束数量。论文还通过引入向量操作和定理4提出了选择最大偏差弧的规则，用以计算部分路径的最大能耗或行驶时间。

双层搜索算法（BLSA）

由于模型为双层结构，直接求解困难。作者设计了一套双层搜索算法（Bi‑Level Search Algorithm, BLSA）：

  • 上层：集合式启发式（Set‑based Heuristic）利用改进的自适应大邻域搜索（ALNS）和局部搜索生成多个可行子路径，使用集合分割来重组子路径，逐步改进全局路径。为避免每次都验证整条路径的鲁棒性，作者开发了基于子路径的鲁棒可行性检查方法，仅检查发生变化的子路径。

  • 下层：双向标记算法（Bidirectional Labeling）当上层得到一条候选路径后，下层求解子问题以获得该路径在所有不确定情况下的最坏成本。鉴于极点数量庞大，标记算法从路径的起点和终点分别向内传播，动态剔除劣势标记，只保留可能产生最大成本的极少数场景。标记在中途节点合并后，再对每个保留场景求解简化的线性规划以决定服务开始时间并计算成本。图3展示了双向标记算法的传播和合并示例：

实验与分析

基准数据与参数设置

作者对Schneider等（2014）提供的EVRP基准进行了调整，设置了固定车辆费用、行驶费用、能耗费用和早/晚服务惩罚，将车辆电池容量设为77.75 kWh，装载容量200 kg。算法参数如ALNS迭代次数、局部搜索次数等在文中给出。

与CPLEX和其他启发式比较

在含不确定性的情况下，小型实例（客户数<20）的实验结果表明，BLSA在耗时远小于CPLEX的同时，能找到与CPLEX相同或更好的鲁棒解；对中大规模实例，BLSA的成本普遍低于移除‑插入遗传算法（RI‑GA）、变邻域搜索（VNS）和双层蚁群（BACO）等方法。例如，对实例RC202‑30，BLSA耗时183.29秒得到的鲁棒成本为1779.76元，而BACO耗时205.52秒成本为1874.68元，成本差距达5.3%。

代价与风险的权衡分析

作者定义“鲁棒性价格”PR = (R* – C*)/C*，表示鲁棒解相对确定解的成本增幅。在不同的不确定度组合(θt, θe)下，PR会随两者增大而上升。图4展示了四个示例实例在不同θt、θe组合下的PR热力图；随着实例规模增大，PR上升更明显，表明大规模问题在高不确定度下需要付出更高代价才能提升鲁棒性。

为了简化决策，作者提出总不确定度θsum = θt + θe，并计算不同θsum下PR的平均值prθsum。结果（图5）显示小规模实例即使θsum达到1.6（80%的路径可能处于最坏情况），PR也低于10%，而大规模实例当θsum超过0.6时PR迅速上升。因此建议：客户数小于20时可采用较大的θt和θe以提高安全性；客户数≥20时θsum宜小于0.6以避免过高成本。

案例研究：长沙超市配送

论文还以长沙市26家门店及6个充电站为例，利用百度地图估算路网距离、行驶时间和能耗。设定配送时间为8:00‑21:00，求解确定性与鲁棒模型的最优路径，结果如图6所示。鲁棒方案（b、d）较确定性方案（a、c）路径长度更长，但能更好抵御不确定性，保证时间窗与电量安全。

随后通过随机采样模拟行驶时间和能耗的不同波动程度Δ，比较不同不确定度预算下的鲁棒性。图7表明：随着Δ增大，可行比例整体下降，而较大的θt和θe显著提高路径在不同场景下保持可行的概率；相比之下，确定性模型（θt=θe=0）在Δ=0.2时可行率已降至60%，显示出极高的脆弱性。

表7中列出了不同θt、θe组合下的期望成本和PR，进一步说明增加不确定预算会提高鲁棒性，但PR在某些区域增长急剧，应谨慎设定。

结论与启示

  • 双重不确定性建模：论文同时考虑行驶时间和能耗的波动，并将不确定预算与经过弧数挂钩，使模型更加贴近实际配送场景。
  • 两阶段鲁棒框架+双层算法：通过自适应鲁棒优化和双向标记算法，实现对复杂鲁棒路径问题的高效求解，兼顾解决精度和计算效率。
  • 路径依赖辅助变量与子路径验证：采用递归公式和子路径级可行性检查，减少了约束规模，提高了解决效率。
  • 鲁棒性价格与决策建议：研究结果表明，增大不确定预算能提升路径的风险抵抗力，但代价随问题规模快速上升；决策者需根据订单规模选择合适的θt和θe，以在成本和风险之间取得平衡。
  • 实际可行性：长沙配送案例验证了模型与算法的实用性，体现出鲁棒方案在实际路况下的安全优势。作者还指出可进一步考虑非线性充电特性或电池损耗成本等问题。

本文为电动汽车配送路径规划研究提供了同时考虑行驶时间和能耗不确定性的全新框架，为绿色物流和新能源车辆的运营决策提供了理论支撑和算法工具。


原文链接：https://doi.org/10.1016/j.tre.2025.104211