License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.11
URN: urn:nbn:de:0030-drops-78672
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7867/
Go to the corresponding LIPIcs Volume Portal

Baum, Moritz ; Dibbelt, Julian ; Wagner, Dorothea ; Zündorf, Tobias

Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

pdf-format:
LIPIcs-ESA-2017-11.pdf (0.5 MB)

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 where 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. In this work, we present a novel framework to compute optimal constrained shortest paths 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 performance of previous inexact methods. For even faster performance, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.

BibTeX - Entry

@InProceedings{baum_et_al:LIPIcs:2017:7867,
  author =	{Moritz Baum and Julian Dibbelt and Dorothea Wagner and Tobias Z{\"u}ndorf},
  title =	{{Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7867},
  URN =		{urn:nbn:de:0030-drops-78672},
  doi =		{10.4230/LIPIcs.ESA.2017.11},
  annote =	{Keywords: electric vehicles, constrained shortest paths, algorithm engineering}
}

Keywords: electric vehicles, constrained shortest paths, algorithm engineering
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI