电动汽车充电的协同分配与路径规划：面向大规模 EV 充电调度的 TL-ALNS算法

如何协同固定桩、移动桩？

随着新能源汽车的普及，城市中固定充电站排队等候的现象日益普遍。同时，部分车主因紧急出行或身处偏远地区而错过最佳充电时机。固定桩无法移动，移动充电车又受限于电量与再补能位置，两者的结构性差异使充电供需矛盾不断放大。

当充电需求持续压缩时间窗、挤占补能资源时，关键不再是“有桩可用”，而是 如何在 同一套资源中实现固定桩与移动桩的最优协同 ？

论文摘要

本文关注电动汽车（EV）充电服务中 固定充电桩 （Fixed Chargers，FCs）和 移动充电车 （Mobile Chargers，MCs）的 协同调度问题 。在中国 EV 拥有量快速增长的背景下，传统的固定充电设施呈现 空间和时间分布不均 ，部分充电站排长队而另一些闲置的现象。MCs 作为一种可移动电源，可为车主提供预约上门服务并利用低谷时段完成自身充电，具有缓解充电桩拥堵和削峰填谷的潜力。然而，现有研究很少同时考虑 MC 的再充电需求及 FC 与 MC 的协调问题 。为此，作者提出了 “固定–移动协同充电问题”（EVRP‑FCMC） ，构建了一个 混合整数规划模型 ，在满足 EV 时间窗、FC 容量和 MC 电量等约束条件下同时决定 EV 请求分配、FC 充电计划和 MC 路由与再充电策略，并设计了适用于大规模实例的 双层自适应大邻域搜索算法（TL‑ALNS） ，最后用南京真实充电数据进行仿真验证，显示该方法能有效提升收益、减少 EV 行驶里程并降低固定充电桩的峰值负载。

一、研究背景与问题陈述

1.1 城市充电需求与固定桩瓶颈

• 电动汽车增长迅猛：截至 2023 年，中国 EV 保有量达到 1260 万辆，预计 2030 年可能增至 8300 万辆。
• 固定充电设施不足与极化：固定充电站受位置限制，导致部分站点排队，另一些闲置。
• 特定场景需求：EV 可能在行程中途电量耗尽或需要紧急上门充电。
• 移动充电车优势：MC 可在任意时间地点提供按需服务，可利用低电价时段给自己充电，缓解电网峰时压力。

1.2 研究难点与需求

• 协调决策复杂：需要同时决定 EV 请求由 FC 还是 MC 处理、MC 的服务顺序与再充电地点，以及 FC 的充电排程。
• 时间与能量双约束：EV 有明确的服务时间窗，MC 的电池容量有限且充电过程可能占用 FC 的容量。
• 现有研究缺口：多数工作要么假定 MC 电量充足或只能在车库充电，要么不考虑 FC 与 MC 的协同。

下图示意了协调充电系统的图模型，节点包括出发点 O、FCs、停车地点 P、EV 请求 RC 及 FC 再充电虚拟节点 U′，边表示 EV 充电、MC 服务、再充电、出发和返回等不同类型的移动。

二、模型与方法

2.1 协调充电问题的混合整数模型

作者将“固定–移动协同充电问题”抽象为带时间窗和电量约束的网络流问题，目标是最大化运营利润：

其中：

• 收益项  包括 EV 在 MC 服务点和 FC 充电的总收入：

其中  表示 EV 请求分配给停车点（由 MC 充电）的边集， 表示分配给 FC 的边集； 为请求  所需能量；、 为在 MC 或 FC 环境下的收费率； 为二元变量，表示请求  分配到位置 。

• 用电成本  ：根据时间分段电价 、FC 的充电速率  和充电时长  计算 MC 和 EV 在 FC 的用电费用：

其中  表示在时间段  是否给 EV 或 MC 提供充电服务， 表示移动充电车  是否在固定桩  发生再充电事件。

• 再充电成本  ：当 MC 完成任务后回到车库进行电量补充，其费用为：

其中  表示 MC 从某节点返回车库的边集， 为 MC 电池容量， 为到达节点  时剩余电量， 为在边  上耗电量。

• 派遣成本  ：MC 的调度移动成本由行驶里程和单位成本  决定：

其中  为 MC 在边  上行驶的二元决策变量。

模型包含以下主要约束：

• 服务唯一性：每个 EV 请求最多分配一次：。
• 距离与电量可行：约束 (7)–(8) 保证 EV 前往服务点的行驶距离不超过最大允许距离且电量充足。
• MC 流量平衡：约束 (9)–(11) 确保 MC 的路径连通，每个虚拟再充电节点仅被一个 MC 访问一次，并保证流入流出平衡。
• 时间窗约束：约束 (12)–(16) 保证 MC 到达时间在 EV 的时间窗内，充电时长与充电速率匹配，同时 MC 电量动态更新。
• FC 容量限制：约束 (20) 保证各时间段在 FC 充电的 MC 与 EV 数量不超过充电口数。

该模型通过线性化技巧将非线性项转化为线性表达，以便使用 MILP 求解器处理（论文中引入了辅助变量  和  进行线性化，此处略）。

2.2 双层自适应大邻域搜索（TL‑ALNS）

由于混合整数模型在规模稍大时求解困难，作者提出了双层自适应大邻域搜索算法。该算法借鉴 ALNS 的“破坏–修复”思想，外层负责 EV 请求的分配策略，内层负责 MC 的具体路线与再充电决策。其核心框架如图示：

算法流程：

1. 初始解构建：基于电价峰谷时段，优先将 EV 请求安排在低谷时段的 FC 充电，减少电费支出。

2. 外层分配搜索：采用四种操作随机选择并删除部分 EV 请求的当前分配，再重新插入以探寻新的分配结构：

• 峰谷搜索：倾向将 EV 从高峰时段移动到电价较低的时段；
• 路线优化：尝试让更多 EV 由 MC 服务，缓解 FC 压力；
• 负载均衡：在不同 FC 之间重新分配 EV 以减少排队；
• 随机探索：随机调整部分分配以增加解空间多样性。

3. 内层路径搜索：对当前分配，使用 ALNS 的破坏–修复操作优化 MC 路线：

• 破坏操作：随机移除部分 MC 服务顺序或再充电节点；
• 修复操作：根据最小增量成本将移除的任务插入不同位置，并考虑 MC 电量、时间窗和 FC 容量；

4. 自适应权重与模拟退火：根据各操作在当前迭代中的表现更新权重，采用模拟退火接受准则在一定概率下接受略差的解，以跳出局部最优。

5. 滚动时域：针对动态环境，算法定期（每隔 ）重新优化，固定已经开始或即将执行的服务，对新的请求和剩余任务进行更新调度。

三、实验设计与结果分析

3.1 数据与参数设置

实验数据来自南京某平台的 9483 条 EV 充电记录，规划周期为 4 小时，时间步长  分钟。主要参数包括：

• MC 电池容量：150 kWh；
• FC 充电口数：10；
• 收费标准：MC 服务费 1.2 元/kWh，FC 服务费 1.0 元/kWh；
• 电价曲线：前 2 小时 0.55 元/kWh，后 2 小时 0.35 元/kWh；
• 单位调度成本与再充电成本：
• 调度成本  ：45 元/次（固定费用）
• 再充电成本  ：0.45 元/kWh

实验随机生成不同规模的 EV 请求集，比较 TL‑ALNS、传统 ALNS 和商用优化求解器 Gurobi 的表现。

3.2 计算效率与盈利效果

• 求解效率：在小规模实例（EV 请求数 ≤10）下，TL‑ALNS 在数秒内即能找到最优解，与 Gurobi 相当。但随着请求量增加，Gurobi 求解时间急剧增加，而 TL‑ALNS 仍能在可接受时间内（几分钟）获得高质量解。
• 运营利润：TL‑ALNS 获得的总利润与最优解非常接近，且显著优于传统 ALNS，尤其当请求数超过 30 时，差距更加明显。
• 服务方式分配：当 FC 容量紧张或电价高峰时，算法倾向调度 MC 上门服务；电价低谷时则充分利用 FC。

下图展示了一个具有 6 个 EV 请求的示例解。其中 – 由 MC 依次在停车点  和  服务， 在 FC  充电，、 在 FC  充电。MC 在完成  后到  充电并返回车库。

实验分析表明，适当分配 MC 服务能显著减少 EV 行驶距离，平均减少近 15%，同时降低 FC 的负荷峰值；而将 MC 仅限于在车库充电则会增加再充电行驶里程和电费支出，利润下降约 7%。

3.3 动态滚动决策

为适应新请求的动态到达，作者在算法中加入滚动时域优化框架。每次决策节点会划分为已完成、预安排且尚未执行、以及待安排三类请求，并根据实际运行情况更新 MC 余电和 FC 剩余容量。下图为其时间轴示意，灰色区域表示固定的已安排任务，白色区域表示可重新优化的时间段。

四、挑战与应对策略

4.1 多源异构约束的建模

• 时间窗与电量耦合：EV 的可服务时间窗与 MC 的充电时间、行驶时间共同决定可行性；模型通过约束 (12)–(16) 明确表述这种耦合。
• FC 容量离散化：通过引入虚拟节点 ，将 FC 容量转化为多个可访问的复制节点，每个虚拟节点代表一次可使用的充电口，从而将容量约束转化为路径选择问题。
• 非线性项线性化：对涉及产品  的非线性项引入辅助变量，将其分解为线性不等式，保证模型可以用 MILP 求解器处理。

4.2 算法设计难点

• 解空间巨大：EV 请求数量大且分布随机，直接枚举分配组合不可行。外层使用多策略破坏–重建方式在全局范围调整分配，内层精细优化 MC 路线。
• 权重自适应：不同操作在不同场景下表现差异明显，通过动态调整权重使算法逐渐倾向效果更好的操作。
• 动态性处理：滚动时域机制需实时更新状态，控制求解时间的同时保证解质量，作者通过提前锁定近期开工任务减少未来可变范围。

五、结论与创新点

本文首次系统地整合固定充电站与移动充电车的调度问题，提出了面向 EV 充电需求分配、FC 排程与 MC 路由再充电决策的混合整数模型。通过设计双层自适应大邻域搜索算法以及滚动时域优化框架，论文在以下方面具有显著创新：

• 协同优化模式：将 FC 与 MC 协同纳入统一模型，既考虑 MC 再充电需求又兼顾 FC 容量和 EV 时间窗，弥补了以往研究只针对单一服务模式的不足。
• 动态再充电决策：MC 不再局限于在车库充电，可在空闲 FC 进行再充电，降低行驶里程和电费，提升整体利润。
• 两层自适应大邻域搜索：通过外层分配和内层路由的协同搜索以及自适应权重调整，实现了在大规模实例下的高效求解，远优于传统启发式和商用求解器。
• 滚动时域机制：结合动态调度框架，算法能够适应实时请求变化，具有较强的实际应用价值。

总体而言，论文为城市电动汽车灵活充电提供了有力的优化方法，既缓解了固定充电桩的拥堵，又利用移动充电车实现了空间和时间的灵活供给。未来研究可进一步考虑需求和电价的不确定性，引入机器学习预测模型提升调度决策的响应性和预见性。