{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:57:35Z","timestamp":1760245055556,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T00:00:00Z","timestamp":1574812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100009056","name":"Z\u00e1pado\u010desk\u00e1 Univerzita v Plzni","doi-asserted-by":"publisher","award":["SGS-2019-015"],"award-info":[{"award-number":["SGS-2019-015"]}],"id":[{"id":"10.13039\/100009056","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Education, Youth and Sports of the Czech Republic","award":["LO1506"],"award-info":[{"award-number":["LO1506"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>In this paper, the shortest paths search for all departure times (profile search) are discussed. This problem is called a time-dependent shortest path problem (TDSP) and is suitable for time-dependent travel-time analysis. Particularly, this paper deals with the    \u03b5   -approximation of profile search computation. The proposed algorithms are based on a label correcting modification of Dijkstra\u2019s algorithm (LCA). The main idea of the algorithm is to simplify the arrival function after every relaxation step so that the maximum relative error is maintained. When the maximum relative error is 0.001, the proposed solution saves more than 97% of breakpoints and 80% of time compared to the exact version of LCA. Furthermore, the runtime can be improved by other 15% to 40% using heuristic splitting of the original departure time interval to several subintervals. The algorithms we developed can be used as a precomputation step in other routing algorithms or for some travel time analysis.<\/jats:p>","DOI":"10.3390\/ijgi8120538","type":"journal-article","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T11:07:00Z","timestamp":1574852820000},"page":"538","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The \u03b5-Approximation of the Time-Dependent Shortest Path Problem Solution for All Departure Times"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2070-5871","authenticated-orcid":false,"given":"Franti\u0161ek","family":"Kolovsk\u00fd","sequence":"first","affiliation":[{"name":"Department of Geomatics, University of West Bohemia, Univerzitn\u00ed 2732\/8, 301 00 Plze\u0148, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1868-117X","authenticated-orcid":false,"given":"Jan","family":"Je\u017eek","sequence":"additional","affiliation":[{"name":"Department of Geomatics, University of West Bohemia, Univerzitn\u00ed 2732\/8, 301 00 Plze\u0148, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4556-2771","authenticated-orcid":false,"given":"Ivana","family":"Kolingerov\u00e1","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of West Bohemia, Univerzitn\u00ed 2732\/8, 301 00 Plze\u0148, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,27]]},"reference":[{"key":"ref_1","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_2","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 (JACM)"},{"key":"ref_3","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_4","doi-asserted-by":"crossref","unstructured":"Omran, M., and Sack, J.R. (2014, January 4\u20136). Improved approximation for time-dependent shortest paths. Proceedings of the International Computing and Combinatorics Conference, Atlanta, GA, USA.","DOI":"10.1007\/978-3-319-08783-2_39"},{"key":"ref_5","unstructured":"Geisberger, R., and Sanders, P. (2010). Engineering Time-Dependent Many-To-Many Shortest Paths Computation, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1.1","DOI":"10.1145\/2444016.2444020","article-title":"Minimum time-dependent travel times with contraction hierarchies","volume":"18","author":"Batz","year":"2013","journal-title":"J. Exp. Algorithmics"},{"key":"ref_7","unstructured":"Geisberger, R. (2010). Engineering Time-dependent One-To-All Computation. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Q. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kolovsk\u00fd, F., Je\u017eek, J., and Kolingerov\u00e1, I. (2019, January 3\u20135). The e-approximation of the Label Correcting Modification of the Dijkstra\u2019s Algorithm. Proceedings of the 5th International Conference on Geographical Information Systems Theory, Applications and Management\u2014Volume 1: GISTAM, Crete, Greece.","DOI":"10.5220\/0007658200260032"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Gilsinn, J.F., and Witzgall, C. (1973). A Performance Comparison of Labeling Algorithms for Calculating Shortest Path Trees, US National Bureau of Standards.","DOI":"10.6028\/NBS.TN.772"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/BF01585517","article-title":"Implementation and efficiency of Moore-algorithms for the shortest route problem","volume":"7","author":"Pape","year":"1974","journal-title":"Math. Program."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bardossy, M.G., and Shier, D.R. (2006). Label-correcting shortest path algorithms revisited. Perspectives in Operations Research, Springer.","DOI":"10.1007\/978-0-387-39934-8_10"},{"key":"ref_13","first-page":"159","article-title":"An optimal algorithm for approximating a piecewise linear function","volume":"9","author":"Imai","year":"1986","journal-title":"J. Inf. Process."},{"key":"ref_14","unstructured":"Strasser, B. (2017). Dynamic Time-Dependent Routing in Road Networks through Sampling, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"ref_15","unstructured":"Dean, B.C. (2004). Shortest Paths in FIFO Time-Dependent Networks: Theory and Algorithms, Massachusetts Institute of Technology. Rapport Technique."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Dehne, F., Omran, M.T., and Sack, J.R. (2009, January 3). Shortest paths in time-dependent FIFO networks using edge load forecasts. Proceedings of the Second International Workshop on Computational Transportation Science, Seattle, WA, USA.","DOI":"10.1145\/1645373.1645374"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/12\/538\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:38:06Z","timestamp":1760189886000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/12\/538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,27]]},"references-count":16,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["ijgi8120538"],"URL":"https:\/\/doi.org\/10.3390\/ijgi8120538","relation":{},"ISSN":["2220-9964"],"issn-type":[{"type":"electronic","value":"2220-9964"}],"subject":[],"published":{"date-parts":[[2019,11,27]]}}}