Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

DOI10.4230/LIPICS.ESA.2017.11zbMATH Open1442.90191arXiv2011.10400OpenAlexW2758398289MaRDI QIDQ5111696FDOQ5111696

Authors: Moritz Baum, Julian Dibbelt, Dorothea Wagner, Tobias Zündorf 

Publication date: 27 May 2020

Abstract: We study the problem of computing constrained shortest paths for battery electric vehicles. Since battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes on which the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting NP-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. We present a novel framework to compute optimal constrained shortest paths (without charging stops) for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching the performance of previous inexact methods. For even faster query times, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.

Full work available at URL: https://arxiv.org/abs/2011.10400

Recommendations

• scientific article; zbMATH DE number 7121919
• Multicriteria stochastic shortest path problem for electric vehicles
• The electric vehicle shortest-walk problem with battery exchanges
• Energy-optimal routes for battery electric vehicles
• An efficient algorithm for routing and recharging of electric vehicles
• Two engineering applications of a constrained shortest-path model
• A constraint programming approach to electric vehicle routing with time windows
• Shortest path stochastic control for hybrid electric vehicles

zbMATH Keywords

electric vehiclesconstrained shortest pathsalgorithm engineering

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Paths and cycles (05C38) Traffic problems in operations research (90B20)

Cites Work

• A note on two problems in connexion with graphs
• Time-dependent route planning
• On the complexity of time-dependent shortest paths
• Minimum time-dependent travel times with contraction hierarchies
• A multicriteria Pareto-optimal path algorithm
• Multiobjective \(\mathrm{A}^\ast\) search with consistent heuristics
• On a multicriteria shortest path problem
• User-constrained multimodal route planning
• Polynomial-time construction of contraction hierarchies for multi-criteria objectives
• Computing the shortest path: \(A^\ast\) search meets graph theory
• A dual algorithm for the constrained shortest path problem
• Energy-optimal routes for battery electric vehicles
• Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
• Route planning with flexible objective functions
• Comparison of electric vehicle's energy consumption factors for different road types
• Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind

Cited In (5)

• Energy-optimal routes for battery electric vehicles
• Modelling battery constraints in discrete event automated guided vehicle simulations
• Multicriteria stochastic shortest path problem for electric vehicles
• Consumption profiles in route planning for electric vehicles: theory and applications
• The electric vehicle shortest-walk problem with battery exchanges

This page was built for publication: Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111696)