Full metadata record
DC FieldValueLanguage
dc.contributor.authorKolovský, František
dc.contributor.authorJežek, Jan
dc.contributor.authorKolingerová, Ivana
dc.date.accessioned2020-09-07T10:00:13Z-
dc.date.available2020-09-07T10:00:13Z-
dc.date.issued2019
dc.identifier.citationKOLOVSKÝ, F., JEŽEK, J., KOLINGEROVÁ, I. The ε-Approximation of the Time-Dependent Shortest Path Problem Solution for All Departure Times. ISPRS International Journal of Geo-Information, 2019, roč. 8, č. 12. ISSN 2220-9964.en
dc.identifier.issn2220-9964
dc.identifier.uri2-s2.0-85076685202
dc.identifier.urihttp://hdl.handle.net/11025/39605
dc.format14 s.
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherMDPIen
dc.relation.ispartofseriesISPRS International Journal of Geo-Informationen
dc.rights© MDPIen
dc.titleThe ε-Approximation of the Time-Dependent Shortest Path Problem Solution for All Departure Timesen
dc.typečlánekcs
dc.typearticleen
dc.rights.accessopenAccessen
dc.type.versionpublishedVersionen
dc.description.abstract-translatedIn 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 ε -approximation of profile search computation. The proposed algorithms are based on a label correcting modification of Dijkstra’s 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.en
dc.subject.translatedtime-dependent shortest path problemen
dc.subject.translatedapproximationen
dc.subject.translatedtravel time functionen
dc.subject.translatedroad networken
dc.identifier.doi10.3390/ijgi8120538
dc.type.statusPeer-revieweden
dc.identifier.document-number518041800017
dc.identifier.obd43928032
dc.project.IDSGS-2019-015/Využití matematiky a informatiky v geomatice IVcs
Appears in Collections:Články / Articles (KIV)
Články / Articles (KGM)
OBD

Files in This Item:
File SizeFormat 
ijgi-08-00538-v2.pdf3,06 MBAdobe PDFView/Open


Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/39605

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

search
navigation
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD