Search Results

Documents authored by Schieferdecker, Dennis

Document
DOI: 10.4230/OASIcs.ATMOS.2021.11
Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles

Authors: Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times. The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances.
Cite as

Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling. Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rajan_et_al:OASIcs.ATMOS.2021.11,
  author =	{Rajan, Payas and Baum, Moritz and Wegner, Michael and Z\"{u}ndorf, Tobias and West, Christian J. and Schieferdecker, Dennis and Delling, Daniel},
  title =	{{Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{11:1--11:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.11},
  URN =		{urn:nbn:de:0030-drops-148807},
  doi =		{10.4230/OASIcs.ATMOS.2021.11},
  annote =	{Keywords: Electric Vehicles, Route Planning}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.26
Fast and Stable Repartitioning of Road Networks

Authors: Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, and Michael Wegner

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
We study the problem of graph partitioning for evolving road networks. While the road network of the world is mostly stable, small updates happen on a relatively frequent basis, as can been observed with the OpenStreetMap project (http://www.openstreetmap.org). For various reasons, professional applications demand the graph partition to stay roughly the same over time, and that changes are limited to areas where graph updates occur. In this work, we define the problem, present algorithms to satisfy the stability needs, and evaluate our techniques on continental-sized road networks. Besides the stability gains, we show that, when the changes are low and local, running our novel techniques is an order of magnitude faster than running graph partitioning from scratch.
Cite as

Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, and Michael Wegner. Fast and Stable Repartitioning of Road Networks. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchhold_et_al:LIPIcs.SEA.2020.26,
  author =	{Buchhold, Valentin and Delling, Daniel and Schieferdecker, Dennis and Wegner, Michael},
  title =	{{Fast and Stable Repartitioning of Road Networks}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.26},
  URN =		{urn:nbn:de:0030-drops-121000},
  doi =		{10.4230/LIPIcs.SEA.2020.26},
  annote =	{Keywords: Graph repartitioning, stable partitions, road networks, algorithm engineering}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.94
Evolution and Evaluation of the Penalty Method for Alternative Graphs

Authors: Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
Computing meaningful alternative routes in a road network is a complex problem -- already giving a clear definition of a best alternative seems to be impossible. Still, multiple methods describe how to compute reasonable alternative routes, each according to their own quality criteria. Among these methods, the penalty method has received much less attention than the via-node or plateaux based approaches. A mayor cause for the lack of interest might be the unavailability of an efficient implementation. In this paper, we take a closer look at the penalty method and extend upon its ideas. We provide the first viable implementation --suitable for interactive use-- using dynamic runtime adjustments to perform up to multiple orders of magnitude faster queries than previous implementations. Using our new implementation, we thoroughly evaluate the penalty method for its flaws and benefits.
Cite as

Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker. Evolution and Evaluation of the Penalty Method for Alternative Graphs. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 94-107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{kobitzsch_et_al:OASIcs.ATMOS.2013.94,
  author =	{Kobitzsch, Moritz and Radermacher, Marcel and Schieferdecker, Dennis},
  title =	{{Evolution and Evaluation of the Penalty Method for Alternative Graphs}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{94--107},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.94},
  URN =		{urn:nbn:de:0030-drops-42474},
  doi =		{10.4230/OASIcs.ATMOS.2013.94},
  annote =	{Keywords: Alternatives, Routing, Shortest Paths, Penalties, Parallelization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact