Document Open Access Logo

REX: A Realistic Time-Dependent Model for Multimodal Public Transport

Authors Spyros Kontogiannis , Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos , Christos Zaroliagis

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2022.12.pdf
  • Filesize: 0.88 MB
  • 16 pages

Document Identifiers

Author Details

Spyros Kontogiannis
  • Computer Science & Engineering Department, University of Ioannina, Greece
  • Computer Technology Institute & Press "Diophantus", Rion, Greece
Paraskevi-Maria-Malevi Machaira
  • Department of Computer Engineering & Informatics, University of Patras, Greece
  • Computer Technology Institute & Press "Diophantus", Rion, Greece
Andreas Paraskevopoulos
  • Department of Computer Engineering & Informatics, University of Patras, Greece
  • Computer Technology Institute & Press "Diophantus", Rion, Greece
Christos Zaroliagis
  • Department of Computer Engineering & Informatics, University of Patras, Greece
  • Computer Technology Institute & Press "Diophantus", Rion, Greece

Funding

This work was supported by the Operational Program Competitiveness, Entrepreneurship and Innovation (co-financed by EU and GR national funds), under project i-Deliver (T2EDK-03472).

Cite AsGet BibTex

Spyros Kontogiannis, Paraskevi-Maria-Malevi Machaira, Andreas Paraskevopoulos, and Christos Zaroliagis. REX: A Realistic Time-Dependent Model for Multimodal Public Transport. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/OASIcs.ATMOS.2022.12

Abstract

We present the non-FIFO time-dependent graph model with REalistic vehicle eXchange times (REX) for schedule-based multimodal public transport, along with a novel query algorithm called TRIP-based LAbel-correction propagation (TRIPLA) algorithm that efficiently solves the realistic earliest-arrival routing problem. The REX model possesses all strong features of previous time-dependent graph models without suffering from their deficiencies. It handles non-negligible exchanges from one vehicle to another, as well as supports non-FIFO instances which are typical in public transport, without compromising space efficiency. We conduct a thorough experimental evaluation with real-world data which demonstrates that TRIPLA significantly outperforms all state-of-the-art query algorithms for multimodal earliest-arrival routing in schedule-based public transport.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Mathematics of computing → Graph algorithms
  • Applied computing → Transportation
Keywords
  • multimodal journey planning
  • REX model
  • TRIPLA query algorithm
  • schedule-based timetables

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Unlimited transfers for multi-modal route planning: An efficient solution. In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.14.
  2. Gerth Stølting Brodal and Riko Jacob. Time-dependent networks as models to achieve fast exact time-table queries. Electronic Notes in Theoretical Computer Science, 92:3-15, 2004. URL: https://doi.org/10.1016/j.entcs.2003.12.019.
  3. Daniel Delling, Andrew V Goldberg, Andreas Nowatzyk, and Renato F Werneck. Phast: Hardware-accelerated shortest path trees. In IEEE International Parallel & Distributed Processing Symposium (IPDPS), pages 921-931. IEEE, 2011. URL: https://doi.org/10.1109/IPDPS.2011.89.
  4. Daniel Delling, Thomas Pajor, and Renato F Werneck. Round-based public transit routing. Transportation Science, 49(3):591-604, 2015. URL: https://doi.org/10.1287/trsc.2014.0534.
  5. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Connection scan algorithm. Journal of Experimental Algorithmics (JEA), 23:1-56, 2018. URL: https://doi.org/10.1145/3274661.
  6. Edsger W Dijkstra et al. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  7. Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Multimodal dynamic journey-planning. Algorithms, 12(10):213, 2019. URL: https://doi.org/10.3390/a12100213.
  8. Andrew V Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In SODA, volume 5, pages 156-165, 2005. URL: https://doi.org/10.1145/1070432.1070455.
  9. Georgia Mali, Panagiotis Michail, Andreas Paraskevopoulos, and Christos Zaroliagis. A new dynamic graph structure for large-scale transportation networks. In 8th International Conference on Algorithms and Complexity, volume 7878, pages 312-323. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38233-8_26.
  10. Matthias Müller-Hannemann and Karsten Weihe. Pareto shortest paths is often feasible in practice. In International Workshop on Algorithm Engineering, volume 2141, pages 185-197. Springer, 2001. URL: https://doi.org/10.1007/3-540-44688-5_15.
  11. Karl Nachtigall. Time depending shortest-path problems with applications to railway networks. European Journal of Operational Research, 83(1):154-166, 1995. URL: https://doi.org/10.1016/0377-2217(94)E0349-G.
  12. OpenStreetMap datasets. URL: https://download.geofabrik.de/europe.html.
  13. Ariel Orda and Raphael Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM (JACM), 37(3):607-625, 1990. URL: https://doi.org/10.1145/79147.214078.
  14. Ariel Orda and Raphael Rom. Minimum weight paths in time-dependent networks. Networks, 21(3):295-319, 1991. URL: https://doi.org/10.1002/net.3230210304.
  15. Stefano Pallottino and Maria Grazia Scutellà. Dual algorithms for the shortest path tree problem. Networks: An International Journal, 29(2):125-133, 1997. URL: https://doi.org/10.1002/(SICI)1097-0037(199703)29:2<125::AID-NET7>3.0.CO;2-L.
  16. Public transport datasets. URL: https://transitfeeds.com.
  17. Public transport london dataset - benchmark. URL: https://files.inria.fr/gang/graphs/public_transport.
  18. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Efficient models for timetable information in public transportation systems. Journal of Experimental Algorithmics, 12:2.4.1-2.4.39, 2007. URL: https://doi.org/10.1145/1227161.1227166.
  19. Peter Sanders. Fast priority queues for cached memory. In Workshop on Algorithm Engineering and Experimentation, pages 316-321. Springer, 1999. URL: https://doi.org/10.1145/351827.384249.
  20. Peter Sanders, Dominik Schultes, and Christian Vetter. Mobile route planning. In European Symposium on Algorithms (ESA), pages 732-743. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-87744-8_61.
  21. Frank Schulz, Dorothea Wagner, and Karsten Weihe. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport. In International Workshop on Algorithm Engineering, pages 110-123. Springer, 1999. URL: https://doi.org/10.1007/3-540-48318-7_11.
  22. Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Using multi-level graphs for timetable information in railway systems. In Workshop on Algorithm Engineering and Experimentation, pages 43-59. Springer, 2002. URL: https://doi.org/10.1007/3-540-45643-0_4.
  23. Sascha Witt. Trip-based public transit routing. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 1025-1036. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_85.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact