Engineering oracles for time-dependent road networks

DOI10.1137/1.9781611974317.1MaRDI QIDQ5232540zbMATH OpenOpenAlexFDO

Authors George Michalopoulos, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, Spyros Kontogiannis, Christos Zaroliagis

Publication date 12 September 2019

Published in 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08303

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Traffic problems in operations research (90B20)

Abstract: We implement and experimentally evaluate landmark-based oracles for min-cost paths in large-scale time-dependent road networks. We exploit parallelism and lossless compression, combined with a novel travel-time approximation technique, to severely reduce preprocessing space and time. We significantly improve the FLAT oracle, improving the previous query time by $30\mathrm{\%}$ and doubling the Dijkstra-rank speedup. We also implement and experimentally evaluate a novel oracle (HORN), based on a landmark hierarchy, achieving even better performance wrt to FLAT.

Recommendations

• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Hierarchical time-dependent oracles
• Minimum time-dependent travel times with contraction hierarchies

Cited in

(4)

• An axiomatic approach to time-dependent shortest path oracles
• Hierarchical time-dependent oracles
• Space-efficient, fast and exact routing in time-dependent road networks
• Improved oracles for time-dependent road networks

This page was built for publication: Engineering oracles for time-dependent road networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232540)