In traditional route planning—such as finding the fastest path on a digital map—algorithms operate under a straightforward assumption: edge costs (like time or distance) are positive and strictly additive. Taking a detour always increases the total cost. Because of this monotonic behavior, standard algorithms like Dijkstra’s or A* can safely discard suboptimal sub-paths early in the search.
When routing electric vehicles (EVs), drones, or other range-limited autonomous systems, this fundamental assumption breaks down. The primary objective shifts from minimizing distance to managing a finite energy reserve: the vehicle's State of Charge (SoC). Managing the SoC introduces hard upper and lower boundaries, along with non-monotonic cost functions, transforming pathfinding into a highly complex optimization challenge.
The Mathematical Challenge of Energy Boundaries
The core difficulty of routing under energy constraints stems from two physical realities: energy depletion and energy recuperation. As Jochen Eisner, Stefan Funke, and Sabine Storandt demonstrate in Optimal Route Planning for Electric Vehicles in Large Networks, electric vehicles can regain energy when traveling downhill. This means that certain graph edges can have negative costs.
However, this energy gain is strictly bounded by the battery's maximum capacity ($C$). If a vehicle descends a long mountain pass with a fully charged battery, it cannot store the extra power; any additional energy is lost due to overcharging constraints. Conversely, the SoC can never drop below zero.
Battery Capacity (C) ------------------------ Overcharge Boundary (Energy Wasted)
/\
/ \ <-- Downhill Recuperation
/ \
Empty (0) ----------------/------\----------- Stranded Boundary (Infeasible Path)
These hard boundaries break Bellman’s principle of optimality. A sub-path that appears optimal because it minimizes distance might cause the vehicle to run out of power before reaching a charging station. Conversely, a sub-path that seems inefficient because it overcharges the battery might actually be part of the only feasible global route. As a result, standard shortest-path algorithms cannot be applied directly without tracking the exact SoC boundaries at every node.
Adapting Graph Search for Energy Feasibility
To solve this problem efficiently on a continental scale, algorithms must embed energy constraints directly into the network topology. Sabine Storandt and Stefan Funke formalize this in Cruising with a Battery-Powered Vehicle and Not Getting Stranded and Enabling E-Mobility: Facility Location for Battery Loading Stations by redefining graph reachability. Instead of tracking a single scalar cost, the search space must maintain a profile of valid intervals for the vehicle's SoC.
Eisner et al. achieved sub-second query times on massive networks by adapting Contraction Hierarchies—a preprocessing technique that creates "shortcuts" between distant nodes. By calculating the upper and lower SoC bounds for these shortcuts ahead of time, the system can bypass thousands of intermediate nodes during a live query while guaranteeing that the vehicle will neither overcharge nor run out of power.
When a journey exceeds a single battery charge, the algorithm must simultaneously determine the optimal route, which charging stations to visit, and exactly how much energy to replenish at each stop. In Heuristic Search for Path Finding With Refuelling, Anushtup Nandy et al. introduce "Refuel A" (RF-A). This approach uses specialized heuristic functions to aggressively prune search paths that are mathematically guaranteed to result in energy starvation or excessive charging delays, significantly accelerating the pathfinding process.
Scaling to Fleet Logistics
The complexity multiplies when moving from a single vehicle to an entire fleet. In the classic Vehicle Routing Problem (VRP), routes are constrained primarily by cargo capacity. In the Electric VRP (E-VRP), fleet managers must orchestrate spatial detours to a sparse network of charging infrastructure while meeting strict customer deadlines. U. Breunig et al. explore this in The electric two-echelon vehicle routing problem, illustrating how the scarcity and placement of charging stations dictate the operational efficiency of urban logistics.
The underlying mathematics of these constraints are inherently difficult. In A Complexity-theoretic Analysis of Green Pickup-and-Delivery Problems, Tan et al. prove that adding limited vehicle ranges and sparse refueling infrastructure makes even highly simplified routing tasks strongly NP-complete. However, single-author work by Xing Tan in Complexity Analysis of Green Pickup-and-Delivery Problems on Ring Structures identifies a theoretical silver lining: when routing tasks are confined to specific network topologies, such as a ring structure, the problem drops to weakly NP-complete, allowing for efficient pseudo-polynomial time solutions.
To tackle arbitrary network structures, modern frameworks deploy advanced metaheuristics and exact formulations:
- Exact Formulations: For autonomous fleets, Kaarthik Sundar develops mixed-integer linear programming (MILP) models in Analysis of Mixed-Integer Linear Programming Formulations for a Fuel-Constrained Multiple Vehicle Routing Problem to guarantee that vehicles complete complex multi-stop circuits without ever depleting their energy reserves.
- Constant-Time Station Insertion: Rui Xu et al. (Memetic Search for Green Vehicle Routing Problem with Private Capacitated Refueling Stations) and Zubin Zheng et al. (Hybrid Memetic Search for Electric Vehicle Routing With Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges) utilize memetic algorithms. These approaches use intelligent "tour-splitting" mechanisms to evaluate and insert optimal charging stops into a route in constant time, allowing the algorithm to scale to thousands of delivery locations.
Managing Spatiotemporal Dynamics
In real-world deployments, energy-constrained routing cannot occur in isolation. A charging station that appears optimal during initial planning might be congested by the time the vehicle arrives.
To prevent localized infrastructure bottlenecks, Saeed Nasehi et al. propose a proactive planning framework in Proactive Route Planning for Electric Vehicles. Instead of routing each vehicle selfishly to the nearest available plug, the system models the future arrival times of other EVs, balancing individual travel times with global station utilization to reduce system-wide delays.
Furthermore, fleet operators must navigate continuous uncertainties in both passenger demand and charging availability. Sihong He et al. address this in Data-Driven Distributionally Robust Electric Vehicle Balancing for Mobility-on-Demand Systems under Demand and Supply Uncertainties using distributionally robust optimization to minimize idle driving distance.
When fleets expand dynamically, Man Luo et al. demonstrate in Rebalancing Expanding EV Sharing Systems with Deep Reinforcement Learning that multi-agent reinforcement learning can successfully coordinate vehicle rebalancing. By prioritizing proximity to charging infrastructure and ensuring sufficient charging dwell time, these systems prevent vehicles from becoming stranded while maximizing fleet availability.
Key Foundational Work
Helicopter Routing for Maintaining Remote Sites in Alaska using a Genetic Algorithm (2005) — contributed 2 concept elements to this direction.
Optimal Route Planning for Electric Vehicles in Large Networks (2011) — contributed 1 concept elements to this direction.