跳转至

A Fast Heuristic Search Approach for Energy-Optimal Profile Routing for Electric Vehicles

会议: AAAI 2026
arXiv: 2512.01331
代码: 论文称代码已公开（脚注3），arXiv页面未附链接
领域: 自动驾驶/路径规划
关键词: 电动车路径规划, 能耗最优搜索, A*搜索, 能量profile, 多目标搜索

一句话总结

提出基于多目标A搜索的label-setting方法（Pr-A），在初始电量未知时高效求解电动车能耗最优路径（profile搜索），通过profile支配关系剪枝避免传统方法中复杂的profile合并操作，在大规模路网上性能接近已知初始电量的标准A*搜索。

背景与动机

电动车（EV）路径规划中，能量既可被消耗（正代价）也可通过再生制动回收（负代价），使得边权可为负。当初始电量已知时，问题可通过Dijkstra/A的变体高效求解（结合Johnson重加权消除负权边）。但许多实际场景中初始电量（SoC）是未知的：例如多段行程规划中每段起始SoC取决于上一段终态、或双向搜索中目的地SoC无法预先确定。此时需要对所有可能的初始SoC值都计算最优路径——这就是能量profile搜索*问题。

现有的profile搜索方法（Baum等, Schönfelder等）基于label-correcting策略，通过merge操作合并同一状态的多个能量profile。但merge操作复杂度高：虽然单条路径profile最多只有两个breakpoint，但merge后的profile可能有O(|S|)个breakpoint，且需要在整个SoC范围上扫描计算下包络线，实现困难、开销大，制约了实用性。

核心问题

如何在不进行复杂profile合并的前提下，高效完成EV的能耗最优profile搜索？即：对所有可能的初始电量值，如何以接近标准A*的效率找到对应的最优路径？

方法详解

整体框架

将能量profile搜索重新建模为多目标最短路径问题：除了最小化能量代价g外，还将最小所需能量ℰ_min和最大能量代价ḡ作为额外目标。在此框架下，采用label-setting（而非label-correcting）策略，按f值非递减顺序展开节点，利用profile支配关系剪枝，避免显式的profile合并。

算法（称为Pr-A*）维护一个优先队列Open和每个状态u的非支配节点集X(u)。搜索从start开始，每次提取f值最小的节点展开其后继，生成新节点时更新能量profile的三个断点值（g, ḡ, ℰ_min），并进行可行性与支配性检查。到达goal的节点作为候选解更新上界f̄。当Open为空或所有节点f值超过f̄时终止，返回X(goal)作为最优profile的超集。

关键设计

  1. 能量Profile表示: 每条路径的能量profile用两个breakpoint紧凑表示——(ℰ_min, g)和(ℰ_max, ḡ)。其中ℰ_min是遍历路径所需的最小初始能量，g是最低能量代价，ḡ是满电出发时的最大代价（因无法存储多余回收能量）。两breakpoint之间斜率为1，之前为常数g，整个profile呈分段线性。这避免了merge后breakpoint爆炸的问题。

  2. Profile支配剪枝: 核心创新。节点y被节点x支配的条件为：ℰ_min(x) ≤ ℰ_min(y)，g(x) ≤ g(y)，ḡ(x) ≤ ḡ(y)。由于A*按f值非递减展开，g(x) ≤ g(y)由展开顺序保证，只需额外检查ℰ_min和ḡ两个维度。被支配节点可安全剪枝不影响最优性。这种pair-wise支配比构建全局下包络线松弛，但实验表明足够有效。还有延迟/惰性检查策略：展开时仅与同状态最新已展开节点快速比较，提取时才做完整支配检查。

  3. 可行性剪枝与上界: 三个剪枝条件：(i) ℰ_min(y) > ℰ_max（路径不可遍历），(ii) ḡ(y) > ℰ_max（满电也无法走完），(iii) ḡ(y) + h(s(y)) > ℰ_max（最大后缀代价加剩余估计超限）。当找到第一个goal节点时，利用其ℰ_min和ḡ设置全局上界f̄ = max{ℰ_min, ḡ}，后续f值超过f̄的节点全部剪枝。

  4. 四种变体: (i) Pr-Afw——前向搜索（主算法），(ii) Pr-Abw——反向搜索（从goal到start），profile链接公式略有不同，(iii) Pr-BA——交错式双向搜索，前后向节点在同一状态会合构成完整路径，(iv) Pr-BApar——并行版双向搜索，前后向分别在独立CPU线程运行。

  5. 一致性启发函数: 基于物理能量模型设计了两类启发函数。一类基于势能差（高程差异）加距离估计，另一类基于纵向动力学模型的简化。两者均被证明满足一致性和可容纳性，即使在存在电池容量约束的负权图上也保持f值单调性，无需Johnson重加权。

损失函数 / 训练策略

不适用——本文是搜索算法论文，无训练过程。核心是理论证明的最优性保证（Theorem 1：Pr-A*返回包含所有最优profile的超集）。

实验关键数据

实验使用10张DIMACS大规模路网（最大Central USA含1400万节点、3400万条边），每张200个随机查询，共2000次查询。模拟Nissan Leaf，85kWh电池。

能量范围(kWh) 指标(平均ms) Dijkstra A*(已知SoC) Pr-A*fw Pr-A*bw 提升(Pr-A*fw vs Dijkstra)
0-20 平均运行时间 27.6 15.6 20.6 19.6 1.51×
20-40 平均运行时间 79.5 44.0 55.3 53.1 1.63×
40-60 平均运行时间 160.7 79.8 101.4 101.8 1.77×
60-85 平均运行时间 242.9 121.7 151.2 152.8 1.69×
  • Pr-Afw相比已知SoC的A仅慢约30%以内，但解决的是更一般化的profile问题
  • 双向变体Pr-BA*反而更慢（甚至慢于Dijkstra），因路径匹配开销过大
  • Pr-Afw展开节点数与标准A几乎相同（多<10%），表明剪枝非常有效

消融实验要点

  • 前向 vs 反向：前向变体更稳定，反向变体方差大（节点展开数波动超100%）
  • 单向 vs 双向：双向搜索在此问题上不优于单向（节点展开多约50%，匹配开销大）
  • 并行 vs 串行双向：并行版（Pr-BA*par）比串行双向快约35%，但仍慢于单向
  • 与Schönfelder等(2014)比较：现有profile A比标准A慢一个数量级，本文方法仅慢30%
  • 与Baum等(2020)间接比较：其profile Dijkstra比标准Dijkstra慢50%，本文profile A*比Dijkstra快70%，估计快2倍以上
  • 绝大多数查询仅返回1条最优路径，最多4条

亮点

  1. 极简优雅：将profile搜索重构为多目标搜索+支配剪枝，完全避免了label-correcting方法中复杂的profile merge操作，算法仅比标准A*多了几行代码
  2. 理论完备：提供了完整的正确性证明（支配关系安全性、收敛性、最优性超集保证），f值单调性在负权图上成立
  3. 实用性强：在1400万节点的真实路网上，profile搜索延迟仅百毫秒级，性能接近已知SoC的A*——意味着可以"免费"获得对所有SoC的规划结果
  4. 可扩展性好：代码以C++实现，使用标准数据结构（二叉堆），易于集成到现有EV路径规划系统中

局限性 / 可改进方向

  1. 双向搜索不理想：双向变体因路径匹配开销反而更慢，需要更高效的双向profile搜索策略
  2. 未结合预处理加速：文中未使用Contraction Hierarchies等预处理技术，在超大规模网络上仍有加速空间
  3. 能量模型较简化：仅考虑坡度和质量驱动的能耗，未建模交通状况、温度对电池、空调能耗等动态因素
  4. profile超集非紧致：算法返回的是最优profile的超集而非精确下包络线，需后处理提取。虽然实验显示超集通常很小（≤4），但理论上可能更大
  5. 单一车型：仅模拟Nissan Leaf，未验证在其他车型/电池容量下的泛化性

与相关工作的对比

  • Artmeier等(2010)/Sachenbacher等(2011): 解决已知SoC的能耗最优问题。本文在此基础上扩展到未知SoC，且保持相近效率
  • Baum等(2013, 2019): label-correcting + Dijkstra + CH预处理。本文无需预处理即获得更好性能，且实现更简单
  • Schönfelder等(2014): 最接近的基线，其profile A比标准A慢10倍。本文仅慢30%，改进巨大
  • 多目标搜索(LTMOA, BOA): 本文借鉴了多目标A*中的支配剪枝和惰性检查策略，创新地应用于能量profile搜索

启发与关联

  • 思路可迁移：将"参数化最优搜索"转化为"多目标搜索+支配剪枝"的范式很通用，可能适用于其他参数不确定的路径规划问题（如不确定的载重、不确定的速度profile等）
  • 与充电站规划结合：profile搜索天然适合多段行程+充电站选择的联合优化，因为每段起始SoC正是从profile中获得
  • 实时性：百毫秒级延迟意味着可用于在线导航，特别是当SoC传感器不精确时，profile搜索比点查询更鲁棒

评分

  • 新颖性: ⭐⭐⭐⭐ 将label-correcting问题转化为label-setting+多目标搜索，思路简洁有效，但核心技术（支配剪枝、启发函数）均有先驱工作
  • 实验充分度: ⭐⭐⭐⭐ 10张大规模真实路网、2000次查询、4种变体对比，统计详尽；但缺少与Baum等的直接比较和不同车型/电池的实验
  • 写作质量: ⭐⭐⭐⭐⭐ 问题定义清晰，理论证明完整，附录提供了反向/双向伪代码和profile链接示例，可复现性强
  • 价值: ⭐⭐⭐⭐ 对EV路径规划领域有实际价值，算法简洁高效，但研究方向相对窄众（EV profile搜索社区较小）