{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:55Z","timestamp":1760243275682,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Research Foundation - Flanders","doi-asserted-by":"publisher","award":["FWO-S007318N","HBC.2017.0970"],"award-info":[{"award-number":["FWO-S007318N","HBC.2017.0970"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012331","name":"Flanders Innovation and Entrepreneurship","doi-asserted-by":"publisher","award":["FWO-S007318N","HBC.2017.0970"],"award-info":[{"award-number":["FWO-S007318N","HBC.2017.0970"]}],"id":[{"id":"10.13039\/100012331","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A direct way of reducing the number of cars on the road is to dissuade individuals from exclusively using their car and instead integrate public transport into their daily routine. Planning multi-modal journeys is a complex task for which individuals often rely on decision support tools. However, offering individuals different journey options represents a significant algorithmic challenge. The failure to provide users with a set of journey options that differ considerably from one another in terms of the modes of transport employed is currently preventing the widespread uptake of multi-modal journey planning among the general public. In this paper, we introduce a dynamic programming algorithm that remedies this situation by modeling different transport networks as a graph that is then pruned by various graph-reduction pre-processing techniques. This approach enables us to offer a diverse set of efficient multi-modal solutions to users almost instantaneously. A computational study on three datasets corresponding to various real-world mobility networks with up to 30,000 vertices and 596,000 arcs demonstrates the effectiveness of the proposed algorithm.<\/jats:p>","DOI":"10.3390\/a15110416","type":"journal-article","created":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T11:31:51Z","timestamp":1667907111000},"page":"416","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Algorithm for Generating a Diverse Set of Multi-Modal Journeys"],"prefix":"10.3390","volume":"15","author":[{"given":"Federico","family":"Mosquera","sequence":"first","affiliation":[{"name":"Department of Computer Science, KU Leuven, 9000 Gent, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3955-7725","authenticated-orcid":false,"given":"Pieter","family":"Smet","sequence":"additional","affiliation":[{"name":"Department of Computer Science, KU Leuven, 9000 Gent, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0275-5568","authenticated-orcid":false,"given":"Greet","family":"Vanden Berghe","sequence":"additional","affiliation":[{"name":"Department of Computer Science, KU Leuven, 9000 Gent, Belgium"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TITS.2006.890077","article-title":"Assisting multimodal travelers: Design and prototypical implementation of a personal travel companion","volume":"8","author":"Rehrl","year":"2007","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1126\/science.1137521","article-title":"Fast routing in road networks with transit nodes","volume":"316","author":"Bast","year":"2007","journal-title":"Science"},{"key":"ref_3","unstructured":"Geisberger, R., Sanders, P., Schultes, D., and Delling, D. (June, January 30). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Proceedings of the International Workshop on Experimental and Efficient Algorithms, Provincetown, MA, USA."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Giannakopoulou, K., Paraskevopoulos, A., and Zaroliagis, C. (2019). Multimodal dynamic journey-planning. Algorithms, 12.","DOI":"10.3390\/a12100213"},{"key":"ref_5","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":"2007","journal-title":"J. Exp. Algorithmics"},{"key":"ref_6","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_7","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 JEA"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Witt, S. (2015). Trip-based public transit routing. Algorithms-ESA 2015, Springer.","DOI":"10.1007\/978-3-662-48350-3_85"},{"key":"ref_9","first-page":"14:1","article-title":"UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution","volume":"Volume 144","author":"Bender","year":"2019","journal-title":"Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1287\/trsc.2021.1104","article-title":"Muse: Multimodal separators for efficient route planning in transportation networks","volume":"56","author":"Falek","year":"2022","journal-title":"Transp. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Potthoff, M., and Sauer, J. (2022, January 9\u201310). Fast Multimodal Journey Planning for Three Criteria. Proceedings of the 2022 Symposium on Algorithm Engineering and Experiments (ALENEX), Alexandria, VA, USA.","DOI":"10.1137\/1.9781611977042.12"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Delling, D., Pajor, T., and Wagner, D. (2009, January 7\u20139). Accelerating multi-modal route planning by access-nodes. Proceedings of the 17th Annual European Symposium, Copenhagen, Denmark.","DOI":"10.1007\/978-3-642-04128-0_53"},{"key":"ref_13","unstructured":"Bast, H., Brodesser, M., and Storandt, S. (2013, January 5). Result diversity for multi-modal route planning. Proceedings of the ATMOS-13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Sophia Antipolis, France."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kontogiannis, S., Paraskevopoulos, A., and Zaroliagis, C. (2021). Time-Dependent Alternative Route Planning: Theory and Practice. Algorithms, 14.","DOI":"10.3390\/a14080220"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1109\/TKDE.2017.2773492","article-title":"Finding top-k shortest paths with diversity","volume":"30","author":"Liu","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/2444016.2444019","article-title":"Alternative routes in road networks","volume":"18","author":"Abraham","year":"2013","journal-title":"J. Exp. Algorithmics"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Bader, R., Dees, J., Geisberger, R., and Sanders, P. (2011, January 18\u201320). Alternative route graphs in road networks. Proceedings of the International Conference on Theory and Practice of Algorithms in (Computer) Systems, Rome, Italy.","DOI":"10.1007\/978-3-642-19754-3_5"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Delling, D., and Wagner, D. (2009, January 4\u20136). Pareto paths with SHARC. Proceedings of the International Symposium on Experimental Algorithms, Dortmund, Germany.","DOI":"10.1007\/978-3-642-02011-7_13"},{"key":"ref_19","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_20","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0377-2217(02)00147-9","article-title":"Vehicle dispatching with time-dependent travel times","volume":"144","author":"Ichoua","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bast, H., Delling, D., Goldberg, A., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., and Werneck, R.F. (2015). Route Planning in Transportation Networks. Algorithm Engineering, Springer.","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"M\u00fcller-Hannemann, M., Schulz, F., Wagner, D., and Zaroliagis, C. (2007). Timetable Information: Models and Algorithms. Algorithmic Methods for Railway Optimization, Springer.","DOI":"10.1007\/978-3-540-74247-0_3"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.eswa.2016.12.009","article-title":"An advanced GA\u2013VNS combination for multicriteria route planning in public transit networks","volume":"72","author":"Dib","year":"2017","journal-title":"Expert Syst. Appl."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1064546.1103378","article-title":"Geometric containers for efficient shortest-path computation","volume":"10","author":"Wagner","year":"2005","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_25","unstructured":"(2019, June 01). Open Mobility Data. Public Transit Data. Available online: https:\/\/transitfeeds.com."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1109\/TITS.2016.2577047","article-title":"Practical Multicriteria Urban Bicycle Routing","volume":"18","author":"Song","year":"2017","journal-title":"IEEE Trans. Intell. Transp. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/11\/416\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:12:02Z","timestamp":1760145122000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/11\/416"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":26,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2022,11]]}},"alternative-id":["a15110416"],"URL":"https:\/\/doi.org\/10.3390\/a15110416","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,11,7]]}}}