Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles
Authors:
- 1 November 2020
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 54 (6) , 1571-1600
Abstract
We study the problem of computing constrained shortest paths for battery electric vehicles. Because 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 [ ]-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.Keywords
All Related Versions
This publication has 64 references indexed in Scilit:
- Multiobjective heuristic search in road mapsExpert Systems with Applications, 2012
- The Pollution-Routing ProblemTransportation Research Part B: Methodological, 2011
- Factors affecting electric vehicle energy consumptionInternational Journal of Sustainable Engineering, 2011
- A multicriteria Pareto-optimal path algorithmEuropean Journal of Operational Research, 1992
- On a multicriteria shortest path problemEuropean Journal of Operational Research, 1984
- A dual algorithm for the constrained shortest path problemNetworks, 1980
- Efficient Algorithms for Shortest Paths in Sparse NetworksJournal of the ACM, 1977
- A Note on Dijkstra's Shortest Path AlgorithmJournal of the ACM, 1973
- An efficient algorith for determining the convex hull of a finite planar setInformation Processing Letters, 1972
- A note on two problems in connexion with graphsNumerische Mathematik, 1959