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.2017.8
URN: urn:nbn:de:0030-drops-78962
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7896/
Go to the corresponding OASIcs Volume Portal

Delling, Daniel ; Dibbelt, Julian ; Pajor, Thomas ; Zündorf, Tobias

Faster Transit Routing by Hyper Partitioning

pdf-format:
OASIcs-ATMOS-2017-8.pdf (2 MB)

Abstract

We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and target cells. This results in a practical approach, suitable for networks that are too large to be efficiently handled by the basic RAPTOR algorithm.

BibTeX - Entry

@InProceedings{delling_et_al:OASIcs:2017:7896,
  author =	{Daniel Delling and Julian Dibbelt and Thomas Pajor and Tobias Z{\"u}ndorf},
  title =	{{Faster Transit Routing by Hyper Partitioning}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{8:1--8:14},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{Gianlorenzo D'Angelo and Twan Dollevoet},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7896},
  URN =		{urn:nbn:de:0030-drops-78962},
  doi =		{10.4230/OASIcs.ATMOS.2017.8},
  annote =	{Keywords: Routing, speed-up techniques, public transport, partitioning}
}

Keywords: Routing, speed-up techniques, public transport, partitioning
Collection: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Issue Date: 2017
Date of publication: 04.09.2017

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