DROPS

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}
}

Search Results

Documents authored by Kobitzsch, Moritz

Evolution and Evaluation of the Penalty Method for Alternative Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message