FLASH-TB: Integrating Arc-Flags and Trip-Based Public Transit Routing

References

• Bast H (2009) Car or public transport: Two worlds. Albers S, Alt H, Näher S, eds. Efficient Algorithms, Lecture Notes in Computer Science, vol. 5760 (Springer, Berlin), 355–367.Crossref, Google Scholar
• Bast H, Hertel M, Storandt S (2016) Scalable transfer patterns. Goodrich M, Mitzenmacher M, eds. Proc. 18th Workshop Algorithm Engrg. Experiments (Society for Industrial and Applied Mathematics, Philadelphia), 15–29.Google Scholar
• Bast H, Sternisko J, Storandt S (2013) Delay-robustness of transfer patterns in public transportation route planning. Frigioni D, Stiller S, eds. Proc. 13th Workshop Algorithmic Approaches Transportation Model. Optim. Systems, OpenAccess Series in Informatics, vol. 33 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 42–54.Google Scholar
• Bast H, Carlsson E, Eigenwillig A, Geisberger R, Harrelson C, Raychev V, Viger F (2010) Fast routing in very large public transportation networks using transfer patterns. de Berg M, Meyer U, eds. Proc. 18th Annual Eur. Sympos. Algorithms, Lecture Notes in Computer Science, vol. 6346 (Springer, Berlin), 290–301.Google Scholar
• Bast H, Delling D, Goldberg AV, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, et al. (2016) Route planning in transportation networks. Kliemann L, Sanders P, eds. Algorithm Engineering: Selected Results and Surveys, Lecture Notes in Computer Science, vol. 9220 (Springer, Berlin), 19–80.Crossref, Google Scholar
• Bauer R, Delling D (2010) SHARC: Fast and robust unidirectional routing. J. Experiment. Algorithmics 14:4:1–4:29.Google Scholar
• Baum M, Buchhold V, Sauer J, Wagner D, Zündorf T (2023) ULTRA: Unlimited transfers for efficient multimodal journey planning. Transportation Sci. 57(6):1536–1559.Link, Google Scholar
• Berger A, Delling D, Gebhardt A, Müller-Hannemann M (2009) Accelerating time-dependent multi-criteria timetable information is harder than expected. Clausen J, di Stefano G, eds. Proc. 9th Workshop Algorithmic Approaches Transportation Model. Optim. Systems, OpenAccess Series in Informatics, vol. 12 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 2:1–2:21.Google Scholar
• Brodal GS, Jacob R (2004) Time-dependent networks as models to achieve fast exact time-table queries. Gerards B, ed. Proc. 3rd Workshop Algorithmic Approaches Transportation Model. Optim. Systems, vol. 92 (Elsevier, Amsterdam), 3–15.Google Scholar
• Cohen E, Halperin E, Kaplan H, Zwick U (2003) Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5):1338–1355.Crossref, Google Scholar
• Delling D, Pajor T, Wagner D (2009) Engineering time-expanded graphs for faster timetable information. Ahuja RK, Möhring RH, Zaroliagis CD, eds. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems, Lecture Notes in Computer Science, vol. 5868 (Springer, Berlin), 182–206.Crossref, Google Scholar
• Delling D, Pajor T, Werneck RF (2015) Round-based public transit routing. Transportation Sci. 49(3):591–604.Link, Google Scholar
• Delling D, Dibbelt J, Pajor T, Werneck RF (2015) Public transit labeling. Bampis E, ed. Proc. 4th Internat. Sympos. Experimental Algorithms, Lecture Notes in Computer Science, vol. 9125 (Springer, Berlin), 273–285.Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerical Math. (Heidelberg) 1:269–271.Crossref, Google Scholar
• Disser Y, Müller-Hannemann M, Schnee M (2008) Multi-criteria shortest paths in time-dependent train networks. McGeoch CC, ed. Proc. 7th Internat. Workshop Experimental Efficient Algorithms, Lecture Notes in Computer Science, vol. 5038 (Springer, Berlin), 347–361.Google Scholar
• Groβmann E, Sauer J, Schulz C, Steil P (2023) Arc-flags meet trip-based public transit routing. Georgiadis L, ed. Proc. 21st Internat. Sympos. Experiment. Algorithms, Leibniz International Proceedings in Informatics, vol. 265 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 16:1–16:18.Google Scholar
• Hilger M, Köhler E, Möhring RH, Schilling H (2009) Fast point-to-point shortest path computations with arc-flags. Demetrescu C, Goldberg AV, Johnson DS, eds. Proc. Shortest Path Problem: 9th DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 74 (American Mathematical Society, Providence, RI), 41–72.Crossref, Google Scholar
• Lauther U (2009) An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags. Demetrescu C, Goldberg AV, Johnson DS, eds. Proc. Shortest Path Problem: 9th DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 74 (American Mathematical Society, Providence, RI), 19–40.Crossref, Google Scholar
• Möhring RH, Schilling H, Schütz B, Wagner D, Willhalm T (2006) Partitioning graphs to speed up Dijkstra’s algorithm. J. Experiment. Algorithmics 11:2.8:1–2.8:29.Google Scholar
• Müller-Hannemann M, Schnee M (2007) Finding all attractive train connections by multi-criteria Pareto search. Geraets F, Kroon L, Schöbel A, Wagner D, Zaroliagis CD, eds. Algorithmic Methods for Railway Optimization, Lecture Notes in Computer Science, vol. 4359 (Springer, Berlin), 246–263.Crossref, Google Scholar
• Pyrga E, Schulz F, Wagner D, Zaroliagis CD (2008) Efficient models for timetable information in public transportation systems. J. Experiment. Algorithmics 12:2.4:1–2.4:39.Crossref, Google Scholar
• Sanders P, Schulz C (2013) Think locally, act globally: Highly balanced graph partitioning. Bonifaci V, Demetrescu C, Marchetti-Spaccamela A, eds. Proc. 12th Internat. Sympos. Experiment. Algorithms, Lecture Notes in Computer Science, vol. 7933 (Springer, Berlin), 164–175.Google Scholar
• Steil P (2023) Optimal FIFO grouping in public transit networks. Technical report, Karlsruhe Institute of Technology, Karlsruhe, Germany.Google Scholar
• Witt S (2015) Trip-based public transit routing. Bansal N, Finocchi I, eds. Proc. 23rd Annual Eur. Sympos. Algorithms, Lecture Notes in Computer Science, vol. 9294 (Springer, Berlin), 1025–1036.Google Scholar
• Witt S (2016) Trip-based public transit routing using condensed search trees. Goerigk M, Werneck R, eds. Proc. 16th Workshop Algorithmic Approaches Transportation Modelling Optim. Systems, OpenAccess Series in Informatics, vol. 54 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 10:1–10:12.Google Scholar
• Witt S (2021) Extending the time horizon: Efficient public transit routing on arbitrary-length timetables. Technical report, Karlsruhe Institute of Technology, Karlsruhe, Germany.Google Scholar