{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:52:43Z","timestamp":1760241163610,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T00:00:00Z","timestamp":1576627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper studies the journey planning problem in the context of transit networks. Given the timetable of a schedule-based transportation system (consisting, e.g., of trains, buses, etc.), the problem seeks journeys optimizing some criteria. Specifically, it seeks to answer natural queries such as, for example, \u201cfind a journey starting from a source stop and arriving at a target stop as early as possible\u201d. The fastest approach for answering to these queries, yielding the smallest average query time even on very large networks, is the Public Transit Labeling framework, proposed for the first time in Delling et al., SEA 2015. This method combines three main ingredients: (i) a graph-based representation of the schedule of the transit network; (ii) a labeling of such graph encoding its transitive closure (computed via a time-consuming pre-processing); (iii) an efficient query algorithm exploiting both (i) and (ii) to answer quickly to queries of interest at runtime. Unfortunately, while transit networks\u2019 timetables are inherently dynamic (they are often subject to delays or disruptions), ptl is not natively designed to handle updates in the schedule\u2014even after a single change, precomputed data may become outdated and queries can return incorrect results. This is a major limitation, especially when dealing with massively sized inputs (e.g., metropolitan or continental sized networks), as recomputing the labeling from scratch, after each change, yields unsustainable time overheads that are not compatible with interactive applications. In this work, we introduce a new framework that extends ptl to function in delay-prone transit networks. In particular, we provide a new set of algorithms able to update both the graph and the precomputed labeling whenever a delay affects the network, without performing any recomputation from scratch. We demonstrate the effectiveness of our solution through an extensive experimental evaluation conducted on real-world networks. Our experiments show that: (i) the update time required by the new algorithms is, on average, orders of magnitude smaller than that required by the recomputation from scratch via ptl; (ii) the updated graph and labeling induce both query time performance and space overhead that are equivalent to those that are obtained by the recomputation from scratch via ptl. This suggests that our new solution is an effective approach to handling the journey planning problem in delay-prone transit networks.<\/jats:p>","DOI":"10.3390\/a13010002","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T09:50:33Z","timestamp":1576835433000},"page":"2","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Journey Planning Algorithms for Massive Delay-Prone Transit Networks"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7833-9520","authenticated-orcid":false,"given":"Mattia","family":"D\u2019Emidio","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Computer Science and Mathematics, University of L\u2019Aquila, Via Vetoio, 67100 L\u2019Aquila, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0934-2392","authenticated-orcid":false,"given":"Imran","family":"Khan","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute (GSSI), Viale Francesco Crispi, 67100 L\u2019Aquila, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2180-8813","authenticated-orcid":false,"given":"Daniele","family":"Frigioni","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Computer Science and Mathematics, University of L\u2019Aquila, Via Vetoio, 67100 L\u2019Aquila, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering\u2014Selected Results and Surveys"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.jda.2017.09.001","article-title":"Engineering graph-based models for dynamic timetable information systems","volume":"46\u201347","author":"Cionini","year":"2017","journal-title":"J. Discret. Algorithms"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1287\/trsc.2014.0579","article-title":"Customizable Route Planning in Road Networks","volume":"51","author":"Delling","year":"2017","journal-title":"Transp. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3274661","article-title":"Connection Scan Algorithm","volume":"23","author":"Dibbelt","year":"2018","journal-title":"J. Exp. Algorithmics"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1287\/trsc.2014.0534","article-title":"Round-Based Public Transit Routing","volume":"49","author":"Delling","year":"2015","journal-title":"Transp. Sci."},{"key":"ref_6","unstructured":"Wagner, D., and Z\u00fcndorf, T. (2017, January 7\u20138). Public transit routing with unrestricted walking. Proceedings of the 17thWorkshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), Vienna, Austria."},{"key":"ref_7","unstructured":"Delling, D., Dibbelt, J., Pajor, T., and Z\u00fcndorf, T. (2017, January 7\u20138). Faster transit routing by hyper partitioning. Proceedings of the 17thWorkshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), Vienna, Austria."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Delling, D., Dibbelt, J., and Pajor, T. (2019, January 7\u20138). Fast and Exact Public Transit Routing with Restricted Pareto Sets. Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, San Diego, CA, USA.","DOI":"10.1137\/1.9781611975499.5"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1227161.1227166","article-title":"Efficient models for timetable information in public transportation systems","volume":"12","author":"Pyrga","year":"2008","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_10","first-page":"46","article-title":"Engineering Graph-Based Models for Dynamic Timetable Information Systems","volume":"Volume 42","author":"Cionini","year":"2014","journal-title":"Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS14)"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"213","DOI":"10.3390\/a12100213","article-title":"Multimodal Dynamic Journey-Planning","volume":"12","author":"Giannakopoulou","year":"2019","journal-title":"Algorithms"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bansal, N., and Finocchi, I. (2015). Trip-Based Public Transit Routing. Algorithms\u2013ESA 2015, Springer.","DOI":"10.1007\/978-3-662-48350-3"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/978-3-319-20086-6_21","article-title":"Public Transit Labeling","volume":"Volume 9125","author":"Delling","year":"2015","journal-title":"International Symposium on Experimental Algorithms (SEA15)"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Wang, S., Lin, W., Yang, Y., Xiao, X., and Zhou, S. (June, January 31). Efficient Route Planning on Public Transportation Networks: A Labelling Approach. Proceedings of the 2015 ACM International Conference on Management of Data (SIGMOD15), ACM, Melbourne, Australia.","DOI":"10.1145\/2723372.2749456"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., and Yoshida, Y. (2014, January 7\u201311). Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. Proceedings of the 23rd International World Wide Web Conference (WWW14), ACM, Seoul, Korea.","DOI":"10.1145\/2566486.2568007"},{"key":"ref_16","unstructured":"Cicerone, S., D\u2019Emidio, M., and Frigioni, D. (2018, January 18\u201320). On Mining Distances in Large-Scale Dynamic Graphs. Proceedings of the 19th Italian Conference on Theoretical Computer Science (ICTCS18), Urbino, Italy."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1002\/net.21542","article-title":"Fully dynamic update of arc-flags","volume":"63","author":"Frigioni","year":"2014","journal-title":"Networks"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-3-642-30850-5_13","article-title":"Fully Dynamic Maintenance of Arc-flags in Road Networks","volume":"Volume 7276","author":"Frigioni","year":"2012","journal-title":"International Symposium on Experimental Algorithms"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/978-3-319-07959-2_24","article-title":"Experimental Evaluation of Dynamic Shortest Path Tree Algorithms on Homogeneous Batches","volume":"Volume 8504","author":"Frigioni","year":"2014","journal-title":"International Symposium on Experimental Algorithms"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-319-44543-4_9","article-title":"Distance Queries in Large-Scale Fully Dynamic Complex Networks","volume":"Volume 9843","author":"Frigioni","year":"2016","journal-title":"International Workshop on Combinatorial Algorithms"},{"key":"ref_21","first-page":"1","article-title":"Fully Dynamic 2-Hop Cover Labeling","volume":"24","author":"Frigioni","year":"2019","journal-title":"J. Exp. Algorithmics"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1007\/s11280-016-0421-1","article-title":"Efficient computation of distance labeling for decremental updates in large dynamic graphs","volume":"20","author":"Qin","year":"2017","journal-title":"World Wide Web"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"D\u2019Emidio, M., and Khan, I. (2019, January 1\u20134). Dynamic Public Transit Labeling. Proceedings of the International Conference on computational Science And Its Applications, Saint Petersburg, Russia.","DOI":"10.1007\/978-3-030-24289-3_9"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Lin, W., Wang, S., and Xiao, X. (2014, January 22\u201327). Reachability queries on large dynamic graphs: a total order approach. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD14), ACM, Snowbird, UT, USA.","DOI":"10.1145\/2588555.2612181"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1287\/opre.35.1.70","article-title":"Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems","volume":"35","author":"Warburton","year":"1987","journal-title":"Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1338","DOI":"10.1137\/S0097539702403098","article-title":"Reachability and Distance Queries via 2-Hop Labels","volume":"32","author":"Cohen","year":"2003","journal-title":"SIAM J. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., and Fu, A.W.C. (2013, January 22\u201327). TF-Label: A topological-folding labeling scheme for reachability querying in a large graph. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD13), New York, NY, USA.","DOI":"10.1145\/2463676.2465286"},{"key":"ref_28","unstructured":"Yano, Y., Akiba, T., Iwata, Y., and Yoshida, Y. (November, January 27). Fast and Scalable Reachability Queries on Graphs by Pruned Labeling with Landmarks and Paths. Proceedings of the 22nd ACM International Conference on Information & Knowledge Management (CIKM13), ACM, San Francisco, CA, USA."},{"key":"ref_29","unstructured":"Colella, F., D\u2019Emidio, M., and Proietti, G. (2017, January 26\u201328). Simple and Practically Efficient Fault-tolerant 2-hop Cover Labelings. Proceedings of the 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic, Naples, Italy."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1017\/nws.2016.20","article-title":"NetworKit: A tool suite for large-scale complex network analysis","volume":"4","author":"Staudt","year":"2016","journal-title":"Netw. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/2\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:43:34Z","timestamp":1760190214000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,18]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["a13010002"],"URL":"https:\/\/doi.org\/10.3390\/a13010002","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,12,18]]}}}