Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
From MaRDI portal
Publication:5111696
DOI10.4230/LIPICS.ESA.2017.11zbMATH Open1442.90191arXiv2011.10400OpenAlexW2758398289MaRDI QIDQ5111696FDOQ5111696
Moritz Baum, Dorothea Wagner, Julian Dibbelt, 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
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 A * 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 (3)
Recommendations
- Title not available (Why is that?) 👍 👎
- The electric vehicle shortest-walk problem with battery exchanges 👍 👎
- Two engineering applications of a constrained shortest-path model 👍 👎
- Energy-optimal routes for battery electric vehicles 👍 👎
- An efficient algorithm for routing and recharging of electric vehicles 👍 👎
- Multicriteria stochastic shortest path problem for electric vehicles 👍 👎
- A constraint programming approach to electric vehicle routing with time windows 👍 👎
- Shortest path stochastic control for hybrid electric vehicles 👍 👎
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)
