{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T22:01:27Z","timestamp":1782770487090,"version":"3.54.5"},"reference-count":34,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T00:00:00Z","timestamp":1570924800000},"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>In this paper, a new model, known as the multimodal dynamic timetable model (DTM), is presented for computing optimal multimodal journeys in schedule-based public transport systems. The new model constitutes an extension of the dynamic timetable model (DTM), which was developed originally for a different setting (unimodal journey-planning). Multimodal DTM demonstrates a very fast query algorithm that meets the requirement for real-time response to best journey queries, and an ultra-fast update algorithm for updating the timetable information in case of delays of scheduled-based vehicles. An experimental study on real-world metropolitan networks demonstrates that the query and update algorithms of Multimodal DTM compare favorably with other state-of-the-art approaches when public transport, including unrestricted\u2014with respect to departing time\u2014traveling (e.g., walking and electric vehicles) is considered.<\/jats:p>","DOI":"10.3390\/a12100213","type":"journal-article","created":{"date-parts":[[2019,10,14]],"date-time":"2019-10-14T03:54:13Z","timestamp":1571025253000},"page":"213","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Multimodal Dynamic Journey-Planning"],"prefix":"10.3390","volume":"12","author":[{"given":"Kalliopi","family":"Giannakopoulou","sequence":"first","affiliation":[{"name":"Computer Technology Institute and Press \u201cDiophantus\u201d, 26504 Patras, Greece"},{"name":"Department of Computer Engineering &amp; Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Paraskevopoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering &amp; Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1425-5138","authenticated-orcid":false,"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"Computer Technology Institute and Press \u201cDiophantus\u201d, 26504 Patras, Greece"},{"name":"Department of Computer Engineering &amp; Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,13]]},"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":"Bast","year":"2016","journal-title":"Algorithm Engineering\u2014Selected Results and Surveys"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2","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. Algorithm."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"26","DOI":"10.3141\/2032-04","article-title":"Multiobjective optimum path algorithm for passenger pretrip planning in multimodal transportation networks","volume":"2032","author":"Aifadopoulou","year":"2007","journal-title":"J. Transp. Res. Board"},{"key":"ref_4","unstructured":"Antsfeld, L., and Walsh, T. (2012, January 22\u201326). Finding multi-criteria optimal paths in multi-modal public transportation networks using the transit algorithm. Proceedings of the 19th ITS World Congress, Wien, Austria."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/S0377-2217(97)00376-7","article-title":"A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks","volume":"111","author":"Modesti","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Dibbelt, J., Pajor, T., and Wagner, D. (2012, January 16). User-constrained multi-modal route planning. Proceedings of the Algorithm Engineering and Experiments (ALENEX 2012), Kyoto, Japan.","DOI":"10.1137\/1.9781611972924.12"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Delling, D., Dibbelt, J., Pajor, T., Wagner, D., and Werneck, R. (2013, January 5\u20137). Computing multimodal journeys in practice. Proceedings of the 12th International Symposium on Experimental Algorithms (SEA 2013), Rome, Italy.","DOI":"10.1007\/978-3-642-38527-8_24"},{"key":"ref_8","unstructured":"Dibbelt, J. (2016). Engineering Algorithms for Route Planning in Multimodal Transportation Networks. [Ph.D. Thesis, Karlsruhe Institute of Technology]."},{"key":"ref_9","unstructured":"Bast, H., Brodesser, M., and Storandt, S. (2013). Result diversity for multi-modal route planning. Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Dagstuhl Publishing."},{"key":"ref_10","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_11","doi-asserted-by":"crossref","unstructured":"Giannakopoulou, K., Paraskevopoulos, A., and Zaroliagis, C. (2018, January 25\u201328). Multimodal Dynamic Journey Planning. Proceedings of the 2018 IEEE Symposium on Computers and Communications (ISCC), Natal, Brazil.","DOI":"10.1109\/ISCC.2018.8538625"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10878-009-9247-4","article-title":"Recoverable robust timetabling for single delay: Complexity and polynomial algorithms for special cases","volume":"18","author":"Cicerone","year":"2009","journal-title":"J. Comb. Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1007\/978-3-642-05465-5_2","article-title":"Recoverable robustness in shunting and timetabling","volume":"Volume 5868","author":"Cicerone","year":"2009","journal-title":"Robust and Online Large-Scale Optimization"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/trsc.1090.0264","article-title":"Fast approaches to improve the robustness of a railway timetable","volume":"43","author":"Fischetti","year":"2009","journal-title":"Transp. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1016\/j.cor.2009.03.022","article-title":"Computing delay resistant railway timetables","volume":"37","author":"Liebchen","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1287\/trsc.1100.0318","article-title":"To wait or not to wait\u2014And who goes first? delay management with priority decisions","volume":"44","author":"Schachtebeck","year":"2010","journal-title":"Transp. Sci."},{"key":"ref_17","unstructured":"Goldberg, A., and Harrelson, C. (2005, January 23\u201325). Computing the shortest path: A search meets graph theory. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, BC, Canada."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/978-3-642-05465-5_7","article-title":"Engineering time-expanded graphs for faster timetable information","volume":"Volume 5868","author":"Delling","year":"2009","journal-title":"Robust and Online Large-Scale Optimization"},{"key":"ref_19","unstructured":"Wagner, D., and Z\u00fcndorf, T. (2017, January 7\u20138). Public Transit Routing with Unrestricted Walking. Proceedings of the Algorithmic Approaches for Transportation Modelling, Optimization, and Systems\u2014ATMOS 2017, Vienna, Austria."},{"key":"ref_20","unstructured":"(2017, February 25). Transport for London, Available online: https:\/\/tfl.gov.uk."},{"key":"ref_21","unstructured":"(2017, February 25). Transit Feeds. Available online: https:\/\/transitfeeds.com."},{"key":"ref_22","unstructured":"OpenStreetMap (2018, February 21). Data Extracts. Available online: http:\/\/download.geofabrik.de."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 18\u201321). R-trees: A dynamic index structure for spatial searching. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1984), Boston, MA, USA.","DOI":"10.1145\/602264.602266"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2625","DOI":"10.1109\/TPDS.2017.2671868","article-title":"Parallel Graph Partitioning for Complex Networks","volume":"28","author":"Meyerhenke","year":"2017","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_25","unstructured":"Mali, G., Michail, P., Paraskevopoulos, A., and Zaroliagis, C. (2013, January 22\u201324). A new dynamic graph structure for large-scale transportation networks. Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC2013), Barcelona, Spain."},{"key":"ref_26","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B., and Weihe, K. (1995). Network Flows: Theory, Algorithms and Applications, Prentice Hall."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/351827.384249","article-title":"Fast Priority Queues for Cached Memory","volume":"5","author":"Sanders","year":"2000","journal-title":"J. Exp. Algorithm."},{"key":"ref_28","unstructured":"(2018, May 25). Reference CPU Scores. Available online: https:\/\/i11www.iti.kit.edu\/~pajor\/survey."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Phan, D.M., and Viennot, L. (2019). Fast Public Transit Routing with Unrestricted Walking through Hub Labeling. arXiv.","DOI":"10.1007\/978-3-030-34029-2_16"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3274661","article-title":"Connection scan algorithm","volume":"23","author":"Dibbelt","year":"2018","journal-title":"Acm J. Exp. Algorithm."},{"key":"ref_31","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_32","unstructured":"(2019, July 12). Public Transport Multimodal Graph Data. Available online: https:\/\/files.inria.fr\/gang\/graphs\/public_transport\/."},{"key":"ref_33","unstructured":"(2019, July 12). HL-CSA-Raptor Source Code. Available online: https:\/\/github.com\/lviennot\/hl-csa-raptor."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Giannakopoulou, K., Nikoletseas, S., Paraskevopoulos, A., and Zaroliagis, C. (2017, January 3\u20136). Dynamic Timetable Information in Smart Cities. Proceedings of the 2017 IEEE Symposium on Computers and Communications (ISCC), Heraklion, Greece.","DOI":"10.1109\/ISCC.2017.8024502"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/213\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:25:55Z","timestamp":1760189155000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,13]]},"references-count":34,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100213"],"URL":"https:\/\/doi.org\/10.3390\/a12100213","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,13]]}}}