EUVIMEDEUVIMED entdecken
Crossref

ULTRA: Unlimited Transfers for Efficient Multimodal Journey Planning

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

Transportation Science · 2023-11 · 57 (6) · 1536-1559

DOI: 10.1287/trsc.2022.0198 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Transportation Science, 2023-11. Verfasst von Moritz Baum und 4 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 15 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study a multimodal journey planning scenario consisting of a public transit network and a transfer graph that represents a secondary transportation mode (e.g., walking, cycling, e-scooter). The objective is to compute Pareto-optimal journeys with respect to arrival time and the number of used public transit trips. Whereas 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. Existing approaches, therefore, typically only support limited walking between stops by either imposing a maximum transfer distance or requiring the transfer graph to be transitively closed. To overcome these shortcomings, we propose a novel preprocessing technique called unlimited transfers (ULTRA): given an unlimited transfer graph, which may represent any non–schedule based transportation mode, ULTRA computes a small number of transfer shortcuts that are provably sufficient for computing a Pareto set of optimal journeys. 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 improves these algorithms from limited to unlimited transfers without sacrificing query speed. This is true not just for walking, but also for faster transfer modes, such as bicycle or car. Compared with the state of the art for multimodal journey planning, the fastest ULTRA-based algorithm achieves a speedup of an order of magnitude. Funding: This work was supported by Deutsche Forschungsgemeinschaft [Grant WA 654/23-2]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0198 .

Zitieren

APA

Baum, M., Buchhold, V., Sauer, J., Wagner, D., & Zündorf, T. (2023). ULTRA: Unlimited Transfers for Efficient Multimodal Journey Planning. Transportation Science, 57(6), 1536-1559. https://doi.org/10.1287/trsc.2022.0198

Vancouver

Baum M, Buchhold V, Sauer J, Wagner D, Zündorf T. ULTRA: Unlimited Transfers for Efficient Multimodal Journey Planning. Transportation Science. 2023;57(6):1536-1559. doi:10.1287/trsc.2022.0198

BibTeX
@article{Baum2023,
  author = {Baum, Moritz and Buchhold, Valentin and Sauer, Jonas and Wagner, Dorothea and Zündorf, Tobias},
  title = {ULTRA: Unlimited Transfers for Efficient Multimodal Journey Planning},
  journal = {Transportation Science},
  year = {2023},
  volume = {57},
  number = {6},
  pages = {1536--1559},
  doi = {10.1287/trsc.2022.0198}
}
Kostenlos starten →