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.
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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).Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2017. Customizable route planning in road networks. Transportation Science 51(2): 566--591.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2015. Round-based public transit routing. Transportation Science 49(3): 591--604. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269--271. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Donald E. Knuth. 1998. The Art of Computer Programming, Sorting and Searching, volume 3. Addison-Wesley. Google ScholarDigital Library
- 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.Google Scholar
- 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).Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
Index Terms
- Connection Scan Algorithm
Recommendations
Railway crew scheduling with semi-flexible timetables
AbstractWe investigate the impact of coordinating the timetable and the crew schedule in an operational freight railway system. Usually, those problems are solved sequentially—resulting in suboptimal schedules for train drivers due to large idle times ...
Processing time-dependent shortest path queries without pre-computed speed information on road networks
Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations ...
Multi-agent Delay Simulation Model in Mass Rail Transit System
ICMTMA '09: Proceedings of the 2009 International Conference on Measuring Technology and Mechatronics Automation - Volume 03A primary delay is the deviation from a scheduled process time caused by disruption within the process. Delay is controlled by timetable and shows the characters of random occurrence. Rail transit system is a complex system which is dynamic, nonlinear, ...
Comments