文章基本信息

标题：Improved Oracles for Time-Dependent Road Networks
本地全文：下载
作者：Spyros Kontogiannis ; Georgia Papastavrou ; Andreas Paraskevopoulos 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2017
卷号：59
页码：1-17
DOI：10.4230/OASIcs.ATMOS.2017.4
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A novel landmark-based oracle (CFLAT) is presented, which provides earliest-arrival-time route plans in time-dependent road networks. To our knowledge, this is the first oracle that preprocesses combinatorial structures (collections of time-stamped min-travel-time-path trees) rather than travel-time functions. The preprocessed data structure is exploited by a new query algorithm (CFCA) which also computes (and pays for it) the actual connecting path that preserves the theoretical approximation guarantees. To make it practical and tackle the main burden of landmark-based oracles (the large preprocessing requirements), CFLAT is extensively engineered. A thorough experimental evaluation on two real-world benchmark instances shows that CFLAT achieves a significant improvement on preprocessing, approximation guarantees and query-times, in comparison to previous landmark-based oracles. It also achieves competitive query-time performance compared to state-of-art speedup heuristics for time-dependent road networks, whose query-times in most cases do not account for path construction.
关键词：Time-dependent shortest paths; FIFO property; Distance oracles