Energy-efficient shortest routes for electric and hybrid vehicles

- A constrained shortest path model for routing electric and hybrid vehicles is developed.
- Electrical energy can be regained by recuperation, by visiting charging stations, and by converting fuel.
- Energy-efficient paths may contain cycles and several examples are studied in detail.
- An approximation scheme for computing energy-efficient shortest routes is designed.
- The corresponding network flow problem is studied.

Electric and hybrid vehicles are a big step towards a greener mobility, but they also open up completely new questions regarding the shortest path problem and the planning of trips. Since recharging an electric car will take much longer than refilling conventional fossil fuels, we have to balance between speed and range and we have to choose stops for charging wisely. For hybrid vehicles, a symbiosis between navigation system and power train control to choose a path with optimal phases for depleting and recharging the battery may yield much more energy-efficient paths. In this paper, we develop an appropriate model for finding shortest routes for these kinds of vehicles, which is mainly a constrained shortest path problem with convertible resources and charging stations. We study properties of solutions by classifying several types of cycles that may occur in the optimal route. We state sufficient conditions to exclude some of these cycle classes and we derive appropriate approximation schemes with provable quality and strict feasibility. We also study the related network flow problem for operating fleets of electric vehicles, e.g., shared vehicles or buses in urban areas.