3 Search Results for "Geisberger, Robert"

Document
DOI: 10.4230/LIPIcs.SEA.2023.16
Arc-Flags Meet Trip-Based Public Transit Routing

Authors: Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over TB, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks.
Cite as

Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil. Arc-Flags Meet Trip-Based Public Transit Routing. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 16:1-16:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2023.16,
  author =	{Gro{\ss}mann, Ernestine and Sauer, Jonas and Schulz, Christian and Steil, Patrick},
  title =	{{Arc-Flags Meet Trip-Based Public Transit Routing}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.16},
  URN =		{urn:nbn:de:0030-drops-183664},
  doi =		{10.4230/LIPIcs.SEA.2023.16},
  annote =	{Keywords: Public transit routing, graph algorithms, algorithm engineering}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.74
Engineering Time-Dependent Many-to-Many Shortest Paths Computation

Authors: Robert Geisberger and Peter Sanders

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
Computing distance tables is important for many logistics problems like the vehicle routing problem (VRP). While shortest distances from all source nodes in S to all target nodes in T are time-independent, travel times are not. We present the first efficient algorithms to compute time-dependent travel time tables in large time-dependent road networks. Our algorithms are based on time-dependent contraction hierarchies (TCH), currently the fastest time-dependent speed-up technique. The computation of a table is inherently in Theta(|S|*|T|), and therefore inefficient for large tables. We provide one particular algorithm using only Theta(|S|+|T|) time and space, being able to answer queries two orders of magnitude faster than the basic TCH implementation. If small errors are acceptable, approximate versions of our algorithms are further orders of magnitude faster.
Cite as

Robert Geisberger and Peter Sanders. Engineering Time-Dependent Many-to-Many Shortest Paths Computation. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 74-87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{geisberger_et_al:OASIcs.ATMOS.2010.74,
  author =	{Geisberger, Robert and Sanders, Peter},
  title =	{{Engineering Time-Dependent Many-to-Many Shortest Paths Computation}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{74--87},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.74},
  URN =		{urn:nbn:de:0030-drops-27511},
  doi =		{10.4230/OASIcs.ATMOS.2010.74},
  annote =	{Keywords: time-dependent, travel time table, algorithm engineering, vrp}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.88
Fast Detour Computation for Ride Sharing

Authors: Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders, and Lars Volker

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
Ride sharing becomes more and more popular not least because internet services help matching offers and request. However, current systems use a rather simple-minded functionality allowing to search for the origin and destination city, sometimes enriched with radial search around the cities. We show that theses services can be substantially improved using innovative route planning algorithms. More concretely, we generalize previous static algorithms for many-to-many routing to a dynamic setting and develop an additional pruning strategy. With these measures it becomes possible to match each request to $n$ offers using $2n+1$ exact travel time computations in a large road network in a fraction of a microsecond per offer. For requests spread over Germany according to population density, we are able to reduce the number of failing entries substantially. We are able to find a reasonable match for more than 60% of the failing entries left by contemporary matching strategies. Additionally, we halve the average waste of resources in the matches found compared to radial search.
Cite as

Robert Geisberger, Dennis Luxen, Sabine Neubauer, Peter Sanders, and Lars Volker. Fast Detour Computation for Ride Sharing. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 88-99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{geisberger_et_al:OASIcs.ATMOS.2010.88,
  author =	{Geisberger, Robert and Luxen, Dennis and Neubauer, Sabine and Sanders, Peter and Volker, Lars},
  title =	{{Fast Detour Computation for Ride Sharing}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{88--99},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.88},
  URN =		{urn:nbn:de:0030-drops-27525},
  doi =		{10.4230/OASIcs.ATMOS.2010.88},
  annote =	{Keywords: ride sharing, algorithm engineering, carpool}
}
  • Refine by Author
  • 2 Geisberger, Robert
  • 2 Sanders, Peter
  • 1 Großmann, Ernestine
  • 1 Luxen, Dennis
  • 1 Neubauer, Sabine
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 3 algorithm engineering
  • 1 Public transit routing
  • 1 carpool
  • 1 graph algorithms
  • 1 ride sharing
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2010
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact