{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T10:42:00Z","timestamp":1774003320140,"version":"3.50.1"},"reference-count":26,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transportation Science"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>We present FLASH-TB, a journey-planning algorithm for public transit networks that combines trip-based public transit routing (TB) with the arc-flags speedup technique. The basic idea is simple: The network is partitioned into a configurable number of cells. For each cell and each possible transfer between two vehicles, the algorithm precomputes a flag that indicates whether the transfer is required to reach the cell. During a query, only flagged transfers are explored. Our algorithm improves on previous attempts to apply arc-flags to public transit networks, which saw limited success due to conflicting rules for pruning the search space. We show that these rules can be reconciled while still producing correct results. Because the number of cells is configurable, FLASH-TB offers a tradeoff between query time and memory consumption. It is significantly more space efficient than existing techniques with a comparable preprocessing time, which store generalized shortest-path trees: To match their query performance, it requires up to two orders of magnitude less memory. The fastest configuration of FLASH-TB achieves a speedup of more than two orders of magnitude over TB, offering submillisecond query times even on large countrywide networks.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the Deutsche Forschungsgemeinschaft [Grants SCHU 2567\/3-1 and WA 654\/23-2].<\/jats:p>\n                  <jats:p>Supplemental Material: The online appendix is available at https:\/\/doi.org\/10.1287\/trsc.2023.0481 .<\/jats:p>","DOI":"10.1287\/trsc.2023.0481","type":"journal-article","created":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T15:26:33Z","timestamp":1766071593000},"page":"242-263","source":"Crossref","is-referenced-by-count":0,"title":["FLASH-TB: Integrating Arc-Flags and Trip-Based Public Transit Routing"],"prefix":"10.1287","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9678-0253","authenticated-orcid":false,"given":"Ernestine","family":"Gro\u00dfmann","sequence":"first","affiliation":[{"name":"Heidelberg University, Institute of Computer Science, 69120 Heidelberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7196-7468","authenticated-orcid":false,"given":"Jonas","family":"Sauer","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Department of Computer Science, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-3506","authenticated-orcid":false,"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"Heidelberg University, Institute of Computer Science, 69120 Heidelberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3282-4533","authenticated-orcid":false,"given":"Patrick","family":"Steil","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Department of Computer Science, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7867-3200","authenticated-orcid":false,"given":"Sascha","family":"Witt","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Department of Computer Science, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03456-5_24"},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Bast H, Hertel M, Storandt S (2016) Scalable transfer patterns. Goodrich M, Mitzenmacher M, eds.\n                      Proc. 18th Workshop Algorithm Engrg. Experiments\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 15\u201329.","DOI":"10.1137\/1.9781611974317.2"},{"key":"B3","unstructured":"Bast H, Sternisko J, Storandt S (2013) Delay-robustness of transfer patterns in public transportation route planning. Frigioni D, Stiller S, eds.\n                      Proc. 13th Workshop Algorithmic Approaches Transportation Model. Optim. Systems\n                      , OpenAccess Series in Informatics, vol. 33 (Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 42\u201354."},{"key":"B4","doi-asserted-by":"crossref","unstructured":"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.\n                      Proc. 18th Annual Eur. Sympos. Algorithms\n                      , Lecture Notes in Computer Science, vol. 6346 (Springer, Berlin), 290\u2013301.","DOI":"10.1007\/978-3-642-15775-2_25"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"B6","first-page":"4:1","volume":"14","author":"Bauer R","year":"2010","journal-title":"J. Experiment. Algorithmics"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2022.0198"},{"key":"B8","unstructured":"Berger A, Delling D, Gebhardt A, M\u00fcller-Hannemann M (2009) Accelerating time-dependent multi-criteria timetable information is harder than expected. Clausen J, di Stefano G, eds.\n                      Proc. 9th Workshop Algorithmic Approaches Transportation Model. Optim. Systems\n                      , OpenAccess Series in Informatics, vol. 12 (Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 2:1\u20132:21."},{"key":"B9","doi-asserted-by":"crossref","unstructured":"Brodal GS, Jacob R (2004) Time-dependent networks as models to achieve fast exact time-table queries. Gerards B, ed.\n                      Proc. 3rd Workshop Algorithmic Approaches Transportation Model. Optim. Systems\n                      , vol. 92 (Elsevier, Amsterdam), 3\u201315.","DOI":"10.1016\/j.entcs.2003.12.019"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05465-5_7"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2014.0534"},{"key":"B13","doi-asserted-by":"crossref","unstructured":"Delling D, Dibbelt J, Pajor T, Werneck RF (2015) Public transit labeling. Bampis E, ed.\n                      Proc. 4th Internat. Sympos. Experimental Algorithms\n                      , Lecture Notes in Computer Science, vol. 9125 (Springer, Berlin), 273\u2013285.","DOI":"10.1007\/978-3-319-20086-6_21"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"B15","doi-asserted-by":"crossref","unstructured":"Disser Y, M\u00fcller-Hannemann M, Schnee M (2008) Multi-criteria shortest paths in time-dependent train networks. McGeoch CC, ed.\n                      Proc. 7th Internat. Workshop Experimental Efficient Algorithms\n                      , Lecture Notes in Computer Science, vol. 5038 (Springer, Berlin), 347\u2013361.","DOI":"10.1007\/978-3-540-68552-4_26"},{"key":"B16","unstructured":"Gro\u03b2mann E, Sauer J, Schulz C, Steil P (2023) Arc-flags meet trip-based public transit routing. Georgiadis L, ed.\n                      Proc. 21st Internat. Sympos. Experiment. Algorithms\n                      , Leibniz International Proceedings in Informatics, vol. 265 (Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 16:1\u201316:18."},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/074\/03"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/074\/02"},{"key":"B19","first-page":"2.8:1","volume":"11","author":"M\u00f6hring RH","year":"2006","journal-title":"J. Experiment. Algorithmics"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74247-0_13"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1227166"},{"key":"B22","doi-asserted-by":"crossref","unstructured":"Sanders P, Schulz C (2013) Think locally, act globally: Highly balanced graph partitioning. Bonifaci V, Demetrescu C, Marchetti-Spaccamela A, eds.\n                      Proc. 12th Internat. Sympos. Experiment. Algorithms\n                      , Lecture Notes in Computer Science, vol. 7933 (Springer, Berlin), 164\u2013175.","DOI":"10.1007\/978-3-642-38527-8_16"},{"key":"B23","unstructured":"Steil P (2023) Optimal FIFO grouping in public transit networks. Technical report, Karlsruhe Institute of Technology, Karlsruhe, Germany."},{"key":"B24","doi-asserted-by":"crossref","unstructured":"Witt S (2015) Trip-based public transit routing. Bansal N, Finocchi I, eds.\n                      Proc. 23rd Annual Eur. Sympos. Algorithms\n                      , Lecture Notes in Computer Science, vol. 9294 (Springer, Berlin), 1025\u20131036.","DOI":"10.1007\/978-3-662-48350-3_85"},{"key":"B25","unstructured":"Witt S (2016) Trip-based public transit routing using condensed search trees. Goerigk M, Werneck R, eds.\n                      Proc. 16th Workshop Algorithmic Approaches Transportation Modelling Optim. Systems\n                      , OpenAccess Series in Informatics, vol. 54 (Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 10:1\u201310:12."},{"key":"B26","unstructured":"Witt S (2021) Extending the time horizon: Efficient public transit routing on arbitrary-length timetables. Technical report, Karlsruhe Institute of Technology, Karlsruhe, Germany."}],"container-title":["Transportation Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/trsc.2023.0481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:20:55Z","timestamp":1773994855000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/trsc.2023.0481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/trsc.2023.0481"],"URL":"https:\/\/doi.org\/10.1287\/trsc.2023.0481","relation":{},"ISSN":["0041-1655","1526-5447"],"issn-type":[{"value":"0041-1655","type":"print"},{"value":"1526-5447","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}