Document Open Access Logo

Improved Oracles for Time-Dependent Road Networks

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

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2017.4.pdf
  • Filesize: 4.33 MB
  • 17 pages

Document Identifiers

Author Details

Spyros Kontogiannis
Georgia Papastavrou
Andreas Paraskevopoulos
Dorothea Wagner
Christos Zaroliagis

Cite As Get BibTex

Spyros Kontogiannis, Georgia Papastavrou, Andreas Paraskevopoulos, Dorothea Wagner, and Christos Zaroliagis. Improved Oracles for Time-Dependent Road Networks. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/OASIcs.ATMOS.2017.4

Abstract

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.

Subject Classification

Keywords
  • Time-dependent shortest paths
  • FIFO property
  • Distance oracles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality. Algorithms and Models for the Web-Graph (WAW), pages 124-137, 2007. Google Scholar
  2. G. V. Batz, R. Geisberger, P. Sanders, and C. Vetter. Minimum time-dependent travel times with contraction hierarchies. ACM Journal of Experimental Algorithmics, 18(1.4):1-43, 2013. Google Scholar
  3. M. Baum, J. Dibbelt, T. Pajor, and D. Wagner. Dynamic time-dependent route planning in road networks with user preferences. Experimental Algorithms (SEA), LNCS(9685):33-49, 2016. Google Scholar
  4. F. Dehne, M. T. Omran, and J. R. Sack. Shortest paths in time-dependent FIFO networks. Algorithmica, 62(1-2):416-435, 2012. Google Scholar
  5. D. Delling. Time-Dependent SHARC-Routing. Algorithmica, 60(1):60-94, 2011. Google Scholar
  6. D. Delling and G. Nannicini. Core routing on dynamic time-dependent road networks. INFORMS Journal on Computing, 24(2):187-201, 2012. Google Scholar
  7. D. Delling and D. Wagner. Landmark-based routing in dynamic graphs. Experimental Algorithms (WEA), LNCS(4525):52-65, 2007. Google Scholar
  8. D. Delling and D. Wagner. Time-dependent route planning. Robust and Online Large-Scale Optimization, LNCS(5868):207-230, 2009. Google Scholar
  9. U. Demiryurek, F. Banaei-Kashani, and C. Shahabi. A case for time-dependent shortest path computation in spatial networks. SIGSPATIAL Advances in Geographic Information Systems (GIS), pages 474-477, 2010. Google Scholar
  10. S. E. Dreyfus. An appraisal of some shortest-path algorithms. Operations Research, 17(3):395-412, 1969. Google Scholar
  11. L. Foschini, J. Hershberger, and S. Suri. On the complexity of time-dependent shortest paths. Algorithmica, 68(4):1075-1097, 2014. Google Scholar
  12. M. Hilger, E. Köhler, R. H. Möhring, and H. Schilling. Fast point-to-point shortest path computations with arc-flags. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, AMS 74:41-72, 2009. Google Scholar
  13. KaHIP - Karlsruhe High Quality Partitioning, May 2014. Google Scholar
  14. S. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Analysis and experimental evaluation of time-dependent distance oracles. Algorithm Engineering and Experiments (ALENEX), SIAM:147-158, 2015. Google Scholar
  15. S. Kontogiannis, G. Michalopoulos, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Engineering oracles for time-dependent road networks. Algorithm Engineering and Experiments (ALENEX), SIAM:1-14, 2016. Google Scholar
  16. S. Kontogiannis, G. Papastavrou, A. Paraskevopoulos, D. Wagner, and C. Zaroliagis. Improved oracles for time-dependent road networks. CoRR abs/1704.08445 (arxiv:1704.08445), 2017. Google Scholar
  17. S. Kontogiannis, D. Wagner, and C. Zaroliagis. Hierarchical oracles for time-dependent networks. Algorithms and Computation (ISAAC), LIPICS 64(47):1-13, 2016. Google Scholar
  18. S. Kontogiannis and C. Zaroliagis. Distance oracles for time-dependent networks. Algorithmica, 74(4):1404-1434, 2016. Google Scholar
  19. G. Mali, P. Michail, A. Paraskevopoulos, and C. Zaroliagis. A new dynamic graph structure for large-scale transportation networks. Algorithms and Complexity (CIAC), LNCS(7878):312-323, 2013. Google Scholar
  20. G. Nannicini, D. Delling, L. Liberti, and D. Schultes. Bidirectional A* search on time-dependent road networks. Networks, 59:240-251, 2012. Google Scholar
  21. M. Omran and J. R. Sack. Improved approximation for time-dependent shortest paths. Computing and Combinatorics (COCOON), LNCS(8591):453-464, 2014. Google Scholar
  22. A. Orda and R. Rom. Shortest-path and minimum delay algorithms in networks with time-dependent edge-length. Journal of the ACM, 37(3):607-625, 1990. URL: http://dx.doi.org/10.1145/79147.214078.
  23. B. Strasser. Intriguingly Simple and Efficient Time-Dependent Routing in Road Networks. CoRR abs/1606.06636 (arxiv:1606.06636v2). URL: https://arxiv.org/abs/1606.06636.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact