research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleAnalysis and Experimental Evaluation of Time-Dependent Distance Oracles
Bibtex cite IDRACTI-RU1-2014-36
Booktitle Algorithm Engineering and Experiments
Year published 2014
Organization ALENEX 2015 (SIAM, 2015)
Note to appear
Urban road networks are represented as directed graphs, accompanied by a metric which assigns cost functions (rather than scalars) to the arcs, e.g. representing time-dependent arc-traversal-times. In this work, we present oracles for providing time-dependent min-cost route plans, and conduct their experimental evaluation on a real-world data set (city of Berlin). Our oracles are based on precomputing all landmark-to-vertex shortest travel-time functions, for properly selected landmark sets. The core of this preprocessing phase is based on a novel, quite efficient and simple oneto-all approximation method for creating approximations of shortest travel-time functions. We then propose three query algorithms, including a PTAS, to efficiently provide mincost route plan responses to arbitrary queries. Apart from the purely algorithmic challenges, we deal also with several implementation details concerning the digestion of raw traffic data, and we provide heuristic improvements of both the preprocessing phase and the query algorithms. We conduct an extensive, comparative experimental study with all query algorithms and six landmark sets. Our results are quite encouraging, achieving remarkable speedups (at least by two orders of magnitude) and quite small approximation guarantees, over the time-dependent variant of Dijkstra˘s algorithm.
Kontogiannis, Spyros
Michalopoulos, George
Papastavrou, Georgia
Paraskevopoulos, Andreas
Wagner, Dorothea
Zaroliagis, Christos
C69-ALENEX2015-TDDO.pdf (main file)
Publication ID1062