{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T06:29:44Z","timestamp":1772778584283,"version":"3.50.1"},"reference-count":31,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"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>We consider the problem of computing a set of meaningful alternative origin-to-destination routes, in real-world road network instances whose arcs are accompanied by travel-time functions rather than fixed costs. In this time-dependent alternative route scenario, we present a novel query algorithm, called Time-Dependent Alternative Graph (TDAG), that exploits the outcome of a time-consuming preprocessing phase to create a manageable amount of travel-time metadata, in order to provide answers for arbitrary alternative-routes queries, in only a few milliseconds for continental-size instances. The resulting set of alternative routes is aggregated in the form of a time-dependent alternative graph, which is characterized by the minimum route overlap, small stretch factor, small size, and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. The preprocessed metadata prescribe the minimum travel-time informations between a small set of \u201clandmark\u201d nodes and all other nodes in the graph. The TDAG query algorithm carries out the work in two distinct phases: initially, a collection phase constructs candidate alternative routes; consequently, a pruning phase cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real-world, time-dependent road networks demonstrates that TDAG performed much better (by one or two orders of magnitude) than the existing baseline approaches.<\/jats:p>","DOI":"10.3390\/a14080220","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T11:53:23Z","timestamp":1626868403000},"page":"220","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Time-Dependent Alternative Route Planning: Theory and Practice"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8559-6418","authenticated-orcid":false,"given":"Spyros","family":"Kontogiannis","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, University of Ioannina, 45110 Ioannina, Greece"},{"name":"Computer Technology Institute & Press \u201cDiophantus\u201d, 26504 Patra, Greece"}]},{"given":"Andreas","family":"Paraskevopoulos","sequence":"additional","affiliation":[{"name":"Computer Technology Institute & Press \u201cDiophantus\u201d, 26504 Patra, Greece"},{"name":"Department of Computer Engineering & Informatics, University of Patras, 26504 Patras, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1425-5138","authenticated-orcid":false,"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"Computer Technology Institute & Press \u201cDiophantus\u201d, 26504 Patra, Greece"},{"name":"Department of Computer Engineering & Informatics, University of Patras, 26504 Patras, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kliemann, L., and Sanders, P. (2016). Route planning in transportation networks. Algorithm Engineering: Selected Results and Surveys, Springer.","DOI":"10.1007\/978-3-319-49487-6"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Delling, D., and Wagner, D. (2009). Pareto paths with SHARC. International Symposium on Experimental Algorithms, Springer.","DOI":"10.1007\/978-3-642-02011-7_13"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Kriegel, H.P., Renz, M., and Schubert, M. (2010, January 1\u20136). Route skyline queries: A multi-preference path planning approach. Proceedings of the 26th International Conference on Data Engineering (ICDE), Long Beach, CA, USA.","DOI":"10.1109\/ICDE.2010.5447845"},{"key":"ref_4","first-page":"652","article-title":"Finding the k shortest paths","volume":"28","author":"Eppstein","year":"1998","journal-title":"J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1002\/net.21552","article-title":"Finding k-shortest simple paths in directed graphs: A node classification algorithm","volume":"64","author":"Feng","year":"2014","journal-title":"Networks"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","article-title":"Finding the k shortest loopless paths in a network","volume":"17","author":"Yen","year":"1971","journal-title":"Manag. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bader, R., Dees, J., Geisberger, R., and Sanders, P. (2011). Alternative route graphs in road networks. International Conference on Theory and Practice of Algorithms in (Computer) Systems, Springer.","DOI":"10.1007\/978-3-642-19754-3_5"},{"key":"ref_8","unstructured":"Ittai, A., Delling, D., Goldberg, A.V., and Werneck, R.F. (2010). Alternative routes in road networks. International Symposium on Experimental Algorithms, Springer."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kobitzsch, M. (2013). An alternative approach to alternative routes: Hidar. European Symposium on Algorithms, Springer.","DOI":"10.1007\/978-3-642-40450-4_52"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Luxen, D., and Schieferdecker, D. (2012). Candidate sets for alternative routes in road networks. International Symposium on Experimental Algorithms, Springer.","DOI":"10.1007\/978-3-642-30850-5_23"},{"key":"ref_11","first-page":"108","article-title":"Improved Alternative Route Planning","volume":"Volume 33","author":"Paraskevopoulos","year":"2013","journal-title":"13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)"},{"key":"ref_12","unstructured":"(2020, September 01). eCOMPASS Project, 2011\u20132014. Available online: http:\/\/www.ecompass-project.eu."},{"key":"ref_13","unstructured":"(2020, September 01). Camvit: Choice Routing. Available online: http:\/\/www.camvit.com."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/TITS.2006.889437","article-title":"Reliable pretrip multipath planning and dynamic adaptation for a centralized road navigation system","volume":"8","author":"Chen","year":"2007","journal-title":"Trans. Intell. Transp. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1007\/s00453-015-0003-0","article-title":"Distance oracles for time-dependent networks","volume":"74","author":"Kontogiannis","year":"2016","journal-title":"Algorithmica"},{"key":"ref_16","unstructured":"Dean, B.C. (2021, July 20). Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms. Available online: https:\/\/people.cs.clemson.edu\/~bcdean\/tdsp.pdf."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/s00453-010-9461-6","article-title":"Shortest paths in time-dependent FIFO networks","volume":"62","author":"Dehne","year":"2012","journal-title":"Algorithmica"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1007\/s00453-012-9714-7","article-title":"On the complexity of time-dependent shortest paths","volume":"68","author":"Foschini","year":"2014","journal-title":"Algorithmica"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/79147.214078","article-title":"Shortest-path and minimum delay algorithms in networks with time-dependent edge-length","volume":"37","author":"Orda","year":"1990","journal-title":"J. ACM"},{"key":"ref_20","first-page":"1.1","article-title":"Minimum time-dependent travel times with contraction hierarchies","volume":"18","author":"Batz","year":"2013","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"ref_21","unstructured":"Kontogiannis, S., Papastavrou, G., Paraskevopoulos, A., Wagner, D., and Zaroliagis, C. (2017). Improved oracles for time-dependent road networks. arXiv."},{"key":"ref_22","first-page":"1","article-title":"Hierarchical time-dependent oracles","volume":"64","author":"Kontogiannis","year":"2016","journal-title":"Algorithms Comput. (ISAAC)"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.17.3.395","article-title":"An appraisal of some shortest-path algorithms","volume":"17","author":"Dreyfus","year":"1969","journal-title":"Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Hansen, P. (1980). Bicriterion path problems. Multiple Criteria Decision Making Theory and Application, Springer.","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","article-title":"On a multicriteria shortest path problem","volume":"16","year":"1984","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Barth, F., Funke, S., and Storandt, S. (2019). Alternative Multicriteria Routes. Algorithm Engineering & Experiments (ALENEX), SIAM.","DOI":"10.1137\/1.9781611975499.6"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1007\/s00778-020-00604-x","article-title":"Finding k-shortest paths with limited overlap","volume":"29","author":"Chondrogiannis","year":"2020","journal-title":"VLDB J."},{"key":"ref_28","unstructured":"Doran, J. (1967). An approach to automatic problem-solving. First International Machine Learning Workshop (Machine Intelligence 1), Oliver and Boy."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"Trans. Syst. Sci. Cybern."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Mali, G., Michail, P., Paraskevopoulos, A., and Zaroliagis, C. (2013). A new dynamic graph structure for large-scale transportation networks. International Conference on Algorithms and Complexity\u2014CIAC 2013, Springer.","DOI":"10.1007\/978-3-642-38233-8_26"},{"key":"ref_31","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. Algorithmics (JEA)"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/220\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:32:52Z","timestamp":1760164372000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":31,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["a14080220"],"URL":"https:\/\/doi.org\/10.3390\/a14080220","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]}}}