AI Research Portal

This paper addresses the energy-optimal shortest path problem for electric vehicles (EVs) in large-scale road networks, particularly when the initial energy level is unknown, a task known as energy-optimal profile search. The core idea is a novel label-setting approach based on multi-objective A* search, which employs a profile dominance rule to efficiently prune unpromising paths and avoid complex profile merging procedures. The method is evaluated on real-world road networks with realistic energy consumption data, demonstrating performance comparable to energy-optimal A* with a known initial energy level, while offering a simpler and more practical solution than existing profile search methods.

The paper identifies several bottlenecks in energy-optimal pathfinding for Electric Vehicles (EVs):

Negative Edge Costs: Energy recuperation (e.g., via regenerative braking) introduces negative energy costs on road segments, making traditional shortest path algorithms (like Dijkstra's) inefficient or inapplicable without modifications.

A novel yet simple label-setting approach for energy-optimal profile search for EVs.
The method adopts a multi-objective search strategy to propagate profiles in a best-first manner.
Incorporation of efficient pruning mechanisms to discard unpromising profiles and avoid expensive profile merging.
Experimental results on realistic instances demonstrating a fast and practical framework for addressing energy-optimal profile queries in large road networks.
Achieves performance comparable to energy-optimal A* with a known initial energy level.

The proposed method is an A*-based approach for energy-optimal profile search, framed as a multi-objective shortest path problem. It leverages a novel profile dominance rule and efficient pruning to streamline the search process.

Energy Profile Representation: An energy profile for a path is represented by two breakpoints: (Emin(x), g(x)) and (Emax, ĝ(x)).

Emin(x) denotes the minimum initial energy required to traverse the path.
g(x) represents the minimum energy cost (when all or part of recuperated energy cannot be stored due to Emax).
ĝ(x) represents the maximum energy cost (when Einit increases).
The profile consists of two segments: (i) Einit < Emin, where the path is not traversable (infinite cost); (ii) Einit ≥ Emin, where the path is traversable with a minimum energy cost of g(x), increasing linearly up to ĝ(x) as Einit increases.

Dominance Pruning Rule: A node y is said to be dominated by node x if Emin(x) ≤ Emin(y), g(x) ≤ g(y), and ĝ(x) ≤ ĝ(y). This means node y's energy profile lies entirely above or equal to node x's across all relevant initial energy levels, and thus y does not offer a lower energy cost at any point in the (0, Emax] range. Dominated nodes are pruned to avoid unnecessary expansions.

*Search Flow (Algorithm 2: Energy Profile (Forward) A Search)**:

Initialization: An Open priority queue is initialized, and a list X(u) is set up for each state u ∈ S to store all non-dominated nodes expanded with u. An initial node x for the start state is created with g(x) = 0, ĝ(x) = 0, Emin(x) = 0, and f(x) = h(start), then added to Open.
Main Loop: While Open is not empty, extract node x with the smallest f-value.
Dominance Check: Before adding x to X(s(x)), it is checked against existing nodes y in X(s(x)). If x is dominated by any y (i.e., Emin(y) < Emin(x) and g(y) ≤ g(x)), x is discarded.
Goal Check: If s(x) is the goal state, the search upper bound f is updated with min(f, max(Emin(x), ĝ(x))).
Expansion: For each successor v of s(x):
- A new node y is created.
- Cost Update:
  - g(y) = max(g(x) + coste, -Emax)
  - f(y) = g(y) + h(v)
  - Emin(y) = max(Emin(x), g(y))
  - ĝ(y) = max(0, g(x) + coste)
- Feasibility Checks: Node y is considered infeasible and discarded if Emin(y) > Emax or ĝ(y) > Emax, or if ĝ(y) + h(v) > Emax.
- Lazy Dominance Check: A quick check is performed against the last node z in X(v) (if any). If z dominates y (Emin(z) < Emin(y) and ĝ(z) ≤ ĝ(y)), y is discarded.
- If feasible and not dominated, y is added to Open.
Termination: The algorithm terminates when Open is empty or the extracted node's f-value exceeds the current upper bound f. It returns X(goal), a superset of nodes representing optimal profiles.

Architecture: The search uses a priority queue (Open) to store unexplored nodes and a list X(u) for each state u to store non-dominated nodes.
Key Equations:
- Total cost estimate: f(x) = g(x) + h(s(x))
- Cumulative energy consumed (minimum): g(y) = max(g(x) + coste, -Emax)
- Minimum initial energy required: Emin(y) = max(Emin(x), g(y))
- Maximum energy cost: ĝ(y) = max(0, g(x) + coste)
Loss/Objective: The primary objective is to determine an optimum path π* with the least amount of energy consumed (g(x)), while ensuring the energy level remains within (0, Emax]. When Einit is unknown, the objective is to compute all minimum-energy paths as a function of Einit.
Optimization: The A* search is guided by f-values. Consistent and admissible heuristic function h: S → R is used. The dominance pruning rule and lazy dominance checks during expansion are key optimization mechanisms.
Data Handling: Road networks are represented as directed graphs G = (S, E). Edge costs are real-valued energy costs, which can be negative due to recuperation. Energy consumption is computed using a model accounting for road gradient, vehicle mass, and speed profiles.
Implementation Details:
- Implemented in C++.
- Compiled using GCC 11.04 compiler with optimization level -O3.
- Experiments conducted on a machine with an Intel Xeon Platinum 8488C processor @3.2GHz and 16GB of RAM.
- Each instance was run three times, and the median runtime is reported.
- Four variants were implemented: Pr-Afw (forward), Pr-Abw (backward), Pr-BA* (bidirectional), and Pr-BA*par (parallel bidirectional).

Datasets: 10 large maps from the 9th DIMACS Implementation Challenge, including "Central USA" with over 14 million states and 34 million edges. Maps were enriched with elevation data from the Shuttle Radar Topography Mission.
Metrics: Runtime (ms) (Min., Avg., Max.), Speedup (η) relative to Dijkstra, and Average number of node expansions (#Exp ×103).
Baselines:
- Dijkstra (standard energy-optimal with known initial SoC).
- A* (standard energy-optimal with known initial SoC).
- Existing label-correcting profile search methods (Schönfelder et al. 2014, Baum et al. 2020) (compared indirectly).
Numeric Results:
- Runtime Comparison (Avg. ms):
  - 0-20 kWh Range: Dijkstra: 27.6, A*: 15.6, Pr-Afw: 20.6, Pr-Abw: 19.6, Pr-BA*: 43.8, Pr-BA*par: 30.9.
  - 20-40 kWh Range: Dijkstra: 79.5, A*: 44.0, Pr-Afw: 55.3, Pr-Abw: 53.1, Pr-BA*: 110.9, Pr-BA*par: 75.7.
  - 40-60 kWh Range: Dijkstra: 160.7, A*: 79.8, Pr-Afw: 101.4, Pr-Abw: 101.8, Pr-BA*: 202.6, Pr-BA*par: 139.1.
  - 60-85 kWh Range: Dijkstra: 242.9, A*: 121.7, Pr-Afw: 151.2, Pr-Abw: 152.8, Pr-BA*: 298.7, Pr-BA*par: 191.9.
- Speedup (η) relative to Dijkstra: Energy-optimal A* consistently performs approximately twice as fast as Dijkstra. Pr-Afw and Pr-Abw are at most 30% slower than A* with known Einit. Pr-Afw and Pr-Abw are up to 70% faster than Dijkstra.
- Node Expansions (#Exp ×103): Pr-Afw expands nearly the same number of nodes as energy-optimal A. Bidirectional approaches expand approximately 50% more nodes on average. Pr-Afw incurs less than 10% extra expansions across most instances. Pr-BA consistently exhibits higher expansion overhead, often approaching or exceeding 100% additional node expansions.
- Comparison to Existing Solutions: The proposed approach is less than 30% slower on average than conventional energy-optimal A*. It is at least twice as fast as the profile search method of Baum et al. (2020) and approximately an order of magnitude faster than Schönfelder, Leucker, and Walther (2014)'s profile A* search.
Runtime/Training Cost: 200 random queries per map were generated, totaling 2000 energy-optimal pathfinding queries. The reported runtime includes search time and initialization time of data structures and priority queue.

Bidirectional Search Performance: The bidirectional variants (Pr-BA* and Pr-BApar) perform worse than the unidirectional profile search variants (Pr-Afw and Pr-Abw), and Pr-BA is even slower than Dijkstra. This is attributed to the significant computational overhead from continuously joining forward and backward frontiers and evaluating for optimality and potential upper-bound updates within fully overlapping search spaces.
Profile Merging: The relaxed pruning rule, while achieving comparable performance to conventional A* search, is less rigorous than explicitly maintaining the true lower envelope of profiles (via profile merging), which is done in label-correcting approaches.

Method evidence: "In this paper, we propose a simple yet effective label-setting approach based on multi-objective A* search, which employs a novel profile dominance rule to avoid generating and handling complex profiles." (section: Abstract)
Result evidence: "Experimental results demonstrate that our energy profile A* search achieves performance comparable to energy-optimal A* with a known initial energy level." (section: Abstract)
Limitation evidence: "Surprisingly, both bidirectional variants perform worse than the unidirectional profile search. In particular, Pr-BA* is even slower than Dijkstra. A key reason for this is the bidirectional path matching within the fully overlapping search spaces, where the forward and backward frontiers are continuously joined and later evaluated for optimality and potential upper-bound updates, introducing significant computational overhead." (section: Experimental Analysis)

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

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures