Document Open Access Logo

Engineering Graph-Based Models for Dynamic Timetable Information Systems

Authors Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, Christos Zaroliagis

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2014.46.pdf
  • Filesize: 1.1 MB
  • 16 pages

Document Identifiers

Author Details

Alessio Cionini
Gianlorenzo D'Angelo
Mattia D'Emidio
Daniele Frigioni
Kalliopi Giannakopoulou
Andreas Paraskevopoulos
Christos Zaroliagis

Cite As Get BibTex

Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Engineering Graph-Based Models for Dynamic Timetable Information Systems. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 46-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/OASIcs.ATMOS.2014.46

Abstract

Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to be used in combination with speed-up techniques developed for road networks.

In this paper, we focus on the dynamic behavior of graph-based models considering the case where transportation systems are subject to delays with respect to the given timetable. We make three contributions: (i) we give a simplified and optimized update routine for the well-known time-expanded model along with an engineered query algorithm; (ii) we propose a new graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of the proposed models and algorithms by an experimental study, which shows that both models require negligible update time and a query time which is comparable to that required by some array-based models.

Subject Classification

Keywords
  • Timetabling
  • dynamic updates
  • queries
  • shortest paths

Metrics

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

References

  1. Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. Fast routing in very large public transportation networks using transfer patterns. In 18th Annual European Symposium on Algorithms (ESA 2010), volume 6346 of LNCS, pages 290-301. Springer, 2010. Google Scholar
  2. Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Mueller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato Werneck. Route planning in transportation networks. Technical Report MSR-TR-2014-4, Microsoft Research, 2014. Google Scholar
  3. Hannah Bast, Jonas Sternisko, and Sabine Storandt. Delay-Robustness of Transfer Patterns in Public Transportation Route Planning. In 13th Work. on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), pages 42-54. Schloss Dagstuhl, 2013. Google Scholar
  4. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. ACM J. Exp. Alg., 15:Article 2.3, 2010. Google Scholar
  5. Reinhard Bauer, Daniel Delling, and Dorothea Wagner. Experimental study of speed up techniques for timetable information systems. Networks, 57(1):38-52, 2011. Google Scholar
  6. F. Bruera, S. Cicerone, G. D'Angelo, G. Di Stefano, and D. Frigioni. Dynamic multi-level overlay graphs for shortest paths. Math. Comp. Sc., 1(4):709-736, 2008. Google Scholar
  7. Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra. Recoverable robust timetabling for single delay: Complexity and polynomial algorithms for special cases. Journal of Combinatorial Optimization, 18(3):229-257, 2009. Google Scholar
  8. Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, Alfredo Navarra, Michael Schachtebeck, and Anita Schöbel. Recoverable robustness in shunting and timetabling. In Robust and Online Large-Scale Opt., volume 5868 of LNCS, pages 28-60. Springer, 2009. Google Scholar
  9. Gianlorenzo D'Angelo, Mattia D'Emidio, and Daniele Frigioni. Fully dynamic update of arc-flags. Networks, 63(3):243-259, 2014. Google Scholar
  10. D. Delling and D. Wagner. Landmark-based routing in dynamic graphs. In 6th Work. on Experimental Algorithms, LNCS, pages 52-65. Springer, 2007. Google Scholar
  11. Daniel Delling, Kalliopi Giannakopoulou, Dorothea Wagner, and Christos Zaroliagis. Timetable Information Updating in Case of Delays: Modeling Issues. Technical Report ARRIVAL-TR-0133, ARRIVAL Project, 2008. Google Scholar
  12. Daniel Delling, Thomas Pajor, and Dorothea Wagner. Engineering time-expanded graphs for faster timetable information. In Robust and Online Large-Scale Optimization, volume 5868 of LNCS, pages 182-206. Springer, 2009. Google Scholar
  13. Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing, pages 130-140. SIAM, 2012. Google Scholar
  14. Daniel Delling and Renato F. Werneck. Faster customization of road networks. In 12th Symp. Exp. Alg. (SEA), volume 7933 of LNCS, pages 30-42. Springer, 2013. Google Scholar
  15. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. Intriguingly simple and fast transit routing. In 12th Symp. Exp. Alg. (SEA), volume 7933 of LNCS, pages 43-54. Springer, 2013. Google Scholar
  16. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. In 13th Int. Symp. on Exp. Alg. (SEA), volume 8504 of LNCS, pages 271-282. Springer, 2014. Google Scholar
  17. Alexandros Efentakis and Dieter Pfoser. Optimizing landmark-based routing and preprocessing. In 6th ACM SIGSPATIAL Int. Work. on Computational Transp. Science. ACM, 2013. Google Scholar
  18. Donatella Firmani, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. Is Timetabling Routing Always Reliable for Public Transport? In 13th Work. on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), pages 15-26. Schloss Dagstuhl, 2013. Google Scholar
  19. Matteo Fischetti, Domenico Salvagnin, and Arrigo Zanette. Fast approaches to improve the robustness of a railway timetable. Transportation Science, 43(3):321-335, 2009. Google Scholar
  20. A. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In ACM-SIAM Symposium on Discrete Algorithms (SODA05), pages 156-165. SIAM, 2005. Google Scholar
  21. HaCon - Ingenieurgesellschaft mbH. http://www.hacon.de, 2008.
  22. U. Lauther. An extremely fast, exact algorithm for finding shortest paths. Static Networks with Geographical Background, 22:219-230, 2004. Google Scholar
  23. Christian Liebchen, Michael Schachtebeck, Anita Schöbel, Sebastian Stiller, and André Prigge. Computing delay resistant railway timetables. Computers & OR, 37(5):857-868, 2010. Google Scholar
  24. Georgia Mali, Panagiotis Michail, Andreas Paraskevopoulos, and Christos Zaroliagis. A new dynamic graph structure for large-scale transportation networks. In 8th Int. Conf. on Algorithms and Complexity (CIAC), volume 7878 of LNCS, pages 312-323. Springer, 2013. Google Scholar
  25. Matthias Müller-Hannemann and Mathias Schnee. Efficient timetable information in the presence of delays. In Robust and Online Large-Scale Optimization, volume 5868 of LNCS, pages 249-272. Springer Berlin Heidelberg, 2009. Google Scholar
  26. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. Efficient models for timetable information in public transportation systems. ACM J Exp Alg, 12(2.4):1-39, 2008. Google Scholar
  27. Michael Schachtebeck and Anita Schöbel. To wait or not to wait - and who goes first? delay management with priority decisions. Transportation Sc., 44(3):307-321, 2010. Google Scholar
  28. D. Schultes and P. Sanders. Dynamic highway-node routing. In 6th Workshop on Experimental Algorithms (WEA), LNCS, pages 66-79. Springer, 2007. Google Scholar
  29. Dorothea Wagner, Thomas Willhalm, and Christos D. Zaroliagis. Geometric containers for efficient shortest-path computation. ACM J. Exp. Alg., 10(1.3):1-30, 2005. Google Scholar
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 About DROPS Imprint Privacy Contact