کوتاه ترین مسیرهای انرژی برای وسایل نقلیه الکتریکی و هیبریدی

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.