Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
From MaRDI portal
Publication:5111696
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.
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
Cites work
- A dual algorithm for the constrained shortest path problem
- A multicriteria Pareto-optimal path algorithm
- A note on two problems in connexion with graphs
- Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
- Comparison of electric vehicle's energy consumption factors for different road types
- Computing the shortest path: \(A^\ast\) search meets graph theory
- Energy-optimal routes for battery electric vehicles
- Minimum time-dependent travel times with contraction hierarchies
- Multiobjective \(\mathrm{A}^\ast\) search with consistent heuristics
- On a multicriteria shortest path problem
- On the complexity of time-dependent shortest paths
- Polynomial-time construction of contraction hierarchies for multi-criteria objectives
- Route planning with flexible objective functions
- Solving time dependent shortest path problems on airway networks using super-optimal wind
- Time-dependent route planning
- User-constrained multimodal route planning
Cited in
(6)- Energy-optimal routes for battery electric vehicles
- Robustness generalizations of the shortest feasible path problem for electric vehicles
- Multicriteria stochastic shortest path problem for electric vehicles
- Modelling battery constraints in discrete event automated guided vehicle simulations
- 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)
