License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2016.10
URN: urn:nbn:de:0030-drops-65341
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6534/
Go to the corresponding OASIcs Volume Portal

Witt, Sascha

Trip-Based Public Transit Routing Using Condensed Search Trees

pdf-format:
OASIcs-ATMOS-2016-10.pdf (0.4 MB)

Abstract

We study the problem of planning Pareto-optimal journeys in public transit networks.
Most existing algorithms and speed-up techniques work by computing subjourneys to intermediary stops until the destination is reached.
In contrast, the trip-based model focuses on trips and transfers between them, constructing journeys as a sequence of trips.
In this paper, we develop a speed-up technique for this model inspired by principles behind existing state-of-the-art speed-up techniques, Transfer Patterns and Hub Labelling.
The resulting algorithm allows us to compute Pareto-optimal (with respect to arrival time and number of transfers) 24-hour profiles on very large real-world networks in less than half a millisecond.
Compared to the current state of the art for bicriteria queries on public transit networks, this is up to two orders of magnitude faster, while increasing preprocessing overhead by at most one order of magnitude.

BibTeX - Entry

@InProceedings{witt:OASIcs:2016:6534,
  author =	{Sascha Witt},
  title =	{{Trip-Based Public Transit Routing Using Condensed Search Trees}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{10:1--10:12},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Marc Goerigk and Renato Werneck},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6534},
  URN =		{urn:nbn:de:0030-drops-65341},
  doi =		{10.4230/OASIcs.ATMOS.2016.10},
  annote =	{Keywords: Public Transit, Routing, Public Transport, Route Planning}
}

Keywords: Public Transit, Routing, Public Transport, Route Planning
Collection: 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)
Issue Date: 2016
Date of publication: 24.08.2016

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