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

We address the problem of energy-optimal pathfinding for electric vehicles (EVs) in large-scale road networks, where energy may be recuperated along paths, introducing negative costs. While traditional routing algorithms assume a known initial energy level, many real-world scenarios require computing optimal paths for all possible initial energy levels, a task known as energy profile search. Existing solutions often rely on complex and computationally demanding profile merging procedures. In this paper, we propose a novel A-based energy profile search algorithm that avoids explicit profile merging by applying relaxed dominance rules within a multi-objective search framework. We present four variants of our method and evaluate them on road networks enriched with realistic energy consumption data. Experimental results show that our energy profile A search performs comparably to conventional energy-optimal A*, which guarantees polynomial-time complexity, while additionally supporting profile queries through a simpler yet efficient solution for large-scale EV routing.