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.1
URN: urn:nbn:de:0030-drops-131371
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13137/
Sauer, Jonas ;
Wagner, Dorothea ;
Zündorf, Tobias
An Efficient Solution for One-To-Many Multi-Modal Journey Planning
Abstract
We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. For large target sets, we achieve a speedup of up to 7 compared to a naive one-to-many extension of a state-of-the-art multi-modal approach.
BibTeX - Entry
@InProceedings{sauer_et_al:OASIcs:2020:13137,
author = {Jonas Sauer and Dorothea Wagner and Tobias Z{\"u}ndorf},
title = {{An Efficient Solution for One-To-Many Multi-Modal Journey Planning}},
booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
pages = {1:1--1:15},
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/13137},
URN = {urn:nbn:de:0030-drops-131371},
doi = {10.4230/OASIcs.ATMOS.2020.1},
annote = {Keywords: Algorithm Engineering, Route Planning, Public Transit, One-to-Many}
}
|
Keywords: |
|
Algorithm Engineering, Route Planning, Public Transit, One-to-Many |
|
Collection: |
|
20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
10.11.2020 |
|
Supplementary Material: |
|
Source code is available at https://github.com/kit-algo/ULTRA-PHAST. |
