Connection Scan Algorithm

Abstract

We introduce the Connection Scan Algorithm (CSA) to efficiently answer queries to timetable information systems. The input consists, in the simplest setting, of a source position and a desired target position. The output consists of a sequence of vehicles such as trains or buses that a traveler should take to get from the source to the target. We study several problem variations such as the earliest arrival and profile problems. We present algorithm variants that only optimize the arrival time or additionally optimize the number of transfers in the Pareto sense. An advantage of CSA is that it can easily adjust to changes in the timetable, allowing the easy incorporation of known vehicle delays. We additionally introduce the Minimum Expected Arrival Time (MEAT) problem to handle possible, uncertain, future vehicle delays. We present a solution to the MEAT problem that is based on CSA. Finally, we extend CSA using the multilevel overlay paradigm to answer complex queries on nationwide integrated timetables with trains and buses.

References

1. Hannah Bast, Erik Carlsson, Arno Eigenwillig, Robert Geisberger, Chris Harrelson, Veselin Raychev, and Fabien Viger. 2010. Fast routing in very large public transportation networks using transfer patterns. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA’10), Volume 6346 of Lecture Notes in Computer Science. Springer, 290--301.
2. Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller--Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2016. Route planning in transportation networks. In Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science. Springer, 19--80.
3. Hannah Bast, Matthias Hertel, and Sabine Storandt. 2016. Scalable transfer patterns. In Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX’16). SIAM, 15--29.
4. Hannah Bast, Jonas Sternisko, and Sabine Storandt. 2013. Delay-robustness of transfer patterns in public transportation route planning. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs). 42--54.
5. Hannah Bast and Sabine Storandt. 2014. Flow-based guidebook routing. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14). SIAM, 155--165.
6. Hannah Bast and Sabine Storandt. 2014. Frequency-based search for public transit. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press, 13--22.
7. Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller--Hannemann. 2009. Accelerating time-dependent multi-criteria timetable information is harder than expected. In Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’09), OpenAccess Series in Informatics (OASIcs).
8. Annabell Berger, Andreas Gebhardt, Matthias Müller--Hannemann, and Martin Ostrowski. 2011. Stochastic delay prediction in large train networks. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’11), volume 20 of OpenAccess Series in Informatics (OASIcs). 100--111.
9. Annabell Berger, Martin Grimmer, and Matthias Müller--Hannemann. 2010. Fully dynamic speed-up techniques for multi-criteria shortest path searches in time-dependent networks. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA’10), volume 6049 of Lecture Notes in Computer Science. Springer, 35--46.
10. Annabell Berger and Matthias Müller--Hannemann. 2009. Subpath-optimality of multi-criteria shortest paths in time- and event-dependent networks. Technical report, University Halle-Wittenberg, Institute of Computer Science.
11. Kateřina Böhmová, Matúš Mihalák, Tobias Pröger, Rastislav Šrámek, and Peter Widmayer. 2013. Robust routing in urban public transportation: How to find reliable journeys based on past observations. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs). 27--41.
12. Alessio Cionini, Gianlorenzo D’Angelo, Mattia D’Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. 2014. Engineering graph-based models for dynamic timetable information systems. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’14), volume 42 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 46--61.
13. Daniel Delling, Julian Dibbelt, Thomas Pajor, and Renato F. Werneck. 2015. Public transit labeling. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA’15), Lecture Notes in Computer Science. Springer, 273--285.
14. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2017. Customizable route planning in road networks. Transportation Science 51(2): 566--591.
15. Daniel Delling, Bastian Katz, and Thomas Pajor. 2012. Parallel computation of best connections in public transportation networks. ACM Journal of Experimental Algorithmics 17(4): 4.1--4.26.
16. Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2012. Round-based public transit routing. In Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12). SIAM, 130--140.
17. Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2015. Round-based public transit routing. Transportation Science 49(3): 591--604.
18. Julian Dibbelt, Thomas Pajor, Ben Strasser, and Dorothea Wagner. 2013. Intriguingly simple and fast transit routing. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13), volume 7933 of Lecture Notes in Computer Science. Springer, 43--54.
19. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. 2014. Delay-robust journeys in timetable networks with minimum expected arrival time. In Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’14), volume 42 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1--14.
20. Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269--271.
21. Yann Disser, Matthias Müller--Hannemann, and Mathias Schnee. 2008. Multi-criteria shortest paths in time-dependent train networks. In Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08), volume 5038 of Lecture Notes in Computer Science. Springer, 347--361.
22. John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull. 2003. Graphviz and dynagraph - static and dynamic graph drawing tools. In Graph Drawing Software. Springer, 127--148.
23. Donatella Firmani, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni. 2013. Is timetabling routing always reliable for public transport? In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs). 15--26.
24. Robert Geisberger. 2010. Contraction of timetable networks with realistic transfers. In Proceedings of the 9th International Symposium on Experimental Algorithms (SEA’10), volume 6049 of Lecture Notes in Computer Science. Springer, 71--82.
25. Marc Goerigk, Sascha Heße, Matthias Müller--Hannemann, and Marie Schmidt. 2013. Recoverable robust timetable information. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’13), OpenAccess Series in Informatics (OASIcs). 1--14.
26. Marc Goerigk, Martin Knoth, Matthias Müller--Hannemann, Marie Schmidt, and Anita Schöbel. 2011. The price of robustness in timetable information. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’11), volume 20 of OpenAccess Series in Informatics (OASIcs). 76--87.
27. Martin Holzer, Frank Schulz, and Dorothea Wagner. 2008. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics 13(2.5):1--26.
28. Donald E. Knuth. 1998. The Art of Computer Programming, Sorting and Searching, volume 3. Addison-Wesley.
29. Ulrich Lauther. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität - von der Forschung zur praktischen Anwendung, volume 22. IfGI prints, 219--230.
30. Matthias Müller--Hannemann and Mathias Schnee. 2006. Paying less for train connections with MOTIS. In Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS’05), OpenAccess Series in Informatics (OASIcs).
31. Matthias Müller--Hannemann and Mathias Schnee. 2009. Efficient timetable information in the presence of delays. In Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science. Springer, 249--272.
32. Matthias Müller--Hannemann, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. 2007. Timetable information: Models and algorithms. In Algorithmic Methods for Railway Optimization, volume 4359 of Lecture Notes in Computer Science. Springer, 67--90.
33. Matthias Müller--Hannemann and Karsten Weihe. 2001. Pareto shortest paths is often feasible in practice. In Proceedings of the 5th International Workshop on Algorithm Engineering (WAE’01), volume 2141 of Lecture Notes in Computer Science. Springer, 185--197.
34. Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. 2008. Efficient models for timetable information in public transportation systems. ACM Journal of Experimental Algorithmics 12(2.4): 1--39.
35. Frank Schulz, Dorothea Wagner, and Karsten Weihe. 1999. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport. In Proceedings of the 3rd International Workshop on Algorithm Engineering (WAE’99), volume 1668 of Lecture Notes in Computer Science. Springer, 110--123.
36. Frank Schulz, Dorothea Wagner, and Christos Zaroliagis. 2002. Using multi-level graphs for timetable information in railway systems. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX’02), volume 2409 of Lecture Notes in Computer Science. Springer, 43--59.
37. Ben Strasser and Dorothea Wagner. 2014. Connection scan accelerated. In Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14). SIAM, 125--137.
38. Dorothea Wagner and Tobias Zündorf. 2017. Public transit routing with unrestricted walking. In Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’17), volume 59 of OpenAccess Series in Informatics (OASIcs). 7:1--7:14.
39. Sibo Wang, Wenqing Lin, Yi Yang, Xiaokui Xiao, and Shuigeng Zhou. 2015. Efficient route planning on public transportation networks: A labelling approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD’15). ACM Press, 967--982.
40. Sascha Witt. 2015. Trip-based public transit routing. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA’15), Lecture Notes in Computer Science, pages 1025--1036. Springer.
41. Sascha Witt. 2016. Trip-based public transit routing using condensed search trees. In Proceedings of the 16th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’16), volume 54 of OpenAccess Series in Informatics (OASIcs). 10:1--10:12.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Design and analysis of algorithms