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.2020.3
URN: urn:nbn:de:0030-drops-131395
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13139/
Go to the corresponding OASIcs Volume Portal

Lehoux, Vassilissa ; Loiodice, Christelle

Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm

pdf-format:
OASIcs-ATMOS-2020-3.pdf (0.4 MB)

Abstract

We propose an additional preprocessing step for the Trip-Based Public Transit Routing algorithm, an exact state-of-the art algorithm for bi-criteria min cost path problems in public transit networks. This additional step reduces significantly the preprocessing time, while preserving the correctness and the computation times of the queries. We test our approach on three large scale networks and show that the improved preprocessing is compatible with frequent real-time updates, even on the larger data set. The experiments also indicate that it is possible, if preprocessing time is an issue, to use the proposed preprocessing step on its own to obtain already a significant reduction of the query times compared to the no pruning scenario.

BibTeX - Entry

@InProceedings{lehoux_et_al:OASIcs:2020:13139,
  author =	{Vassilissa Lehoux and Christelle Loiodice},
  title =	{{Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{3:1--3:12},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Dennis Huisman and Christos D. Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13139},
  URN =		{urn:nbn:de:0030-drops-131395},
  doi =		{10.4230/OASIcs.ATMOS.2020.3},
  annote =	{Keywords: Public transit, Route planning, Algorithms, Preprocessing}
}

Keywords: Public transit, Route planning, Algorithms, Preprocessing
Collection: 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Issue Date: 2020
Date of publication: 10.11.2020

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