License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.14
URN: urn:nbn:de:0030-drops-111352
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11135/
Go to the corresponding LIPIcs Volume Portal

Baum, Moritz ; Buchhold, Valentin ; Sauer, Jonas ; Wagner, Dorothea ; Zündorf, Tobias

UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution

pdf-format:
LIPIcs-ESA-2019-14.pdf (0.5 MB)

Abstract

We study a multi-modal route planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or taxis). The objective is to compute all journeys that are Pareto-optimal with respect to arrival time and the number of required transfers. While various existing algorithms can efficiently compute optimal journeys in either a pure public transit network or a pure transfer graph, combining the two increases running times significantly. As a result, even walking between stops is typically limited by a maximal duration or distance, or by requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called ULTRA (UnLimited TRAnsfers): Given a complete transfer graph (without any limitations, representing an arbitrary non-schedule-based mode of transportation), we compute a small number of transfer shortcuts that are provably sufficient for computing all Pareto-optimal journeys. We demonstrate the practicality of our approach by showing that these transfer shortcuts can be integrated into a variety of state-of-the-art public transit algorithms, establishing the ULTRA-Query algorithm family. Our extensive experimental evaluation shows that ULTRA is able to improve these algorithms from limited to unlimited transfers without sacrificing query speed, yielding the fastest known algorithms for multi-modal routing. This is true not just for walking, but also for other transfer modes such as cycling or driving.

BibTeX - Entry

@InProceedings{baum_et_al:LIPIcs:2019:11135,
  author =	{Moritz Baum and Valentin Buchhold and Jonas Sauer and Dorothea Wagner and Tobias Z{\"u}ndorf},
  title =	{{UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11135},
  URN =		{urn:nbn:de:0030-drops-111352},
  doi =		{10.4230/LIPIcs.ESA.2019.14},
  annote =	{Keywords: Algorithms, Optimization, Route Planning, Public Transportation}
}

Keywords: Algorithms, Optimization, Route Planning, Public Transportation
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019
Supplementary Material: Source code of ULTRA is available at https://github.com/kit-algo/ULTRA.

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