4 Search Results for "Schieferdecker, Dennis"

Document
DOI: 10.4230/OASIcs.ATMOS.2025.12
Separator-Based Alternative Paths in Customizable Contraction Hierarchies

Authors: Scott Bacherle, Thomas Bläsius, and Michael Zündorf

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We propose an algorithm for computing alternatives to the shortest path in a road network, based on the speed-up technique CCH (customizable contraction hierarchy). Computing alternative paths is a well-studied problem, motivated by the fact that route-planning applications benefit from presenting different high-quality options the user can choose from. Another crucial feature of modern routing applications is the inclusion of live traffic, which requires speed-up techniques that allow efficient metric updates. Besides CCH, the other speed-up technique supporting metric updates is CRP (customizable route planning). Of the two, CCH is the more modern solution with the advantages of providing faster queries and being substantially simpler to implement efficiently. However, so far, CCH has been lacking a way of computing alternative paths. While for CRP, the commonly used plateau method for computing alternatives can be applied, this is not so straightforward for CCH. With this paper, we make CCH a viable option for alternative paths, by proposing a new separator-based approach to computing alternative paths that works hand-in-hand with the CCH data structure. With our experiments, we demonstrate that CCH can indeed be used to compute alternative paths efficiently. With this, we provide an alternative to CRP that is simpler and has lower query times.
Cite as

Scott Bacherle, Thomas Bläsius, and Michael Zündorf. Separator-Based Alternative Paths in Customizable Contraction Hierarchies. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bacherle_et_al:OASIcs.ATMOS.2025.12,
  author =	{Bacherle, Scott and Bl\"{a}sius, Thomas and Z\"{u}ndorf, Michael},
  title =	{{Separator-Based Alternative Paths in Customizable Contraction Hierarchies}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{12:1--12:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.12},
  URN =		{urn:nbn:de:0030-drops-247685},
  doi =		{10.4230/OASIcs.ATMOS.2025.12},
  annote =	{Keywords: Alternative routes, realistic road networks, customizable contraction hierarchies, route planning, shortest paths}
}
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}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021
  • 1 2020
  • 1 2013

  • Refine by Author
  • 3 Schieferdecker, Dennis
  • 2 Delling, Daniel
  • 2 Wegner, Michael
  • 1 Bacherle, Scott
  • 1 Baum, Moritz
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 3 OASIcs

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Alternative routes
  • 1 Alternatives
  • 1 Electric Vehicles
  • 1 Graph repartitioning
  • 1 Parallelization
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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