Engineering Oracles for Time-Dependent Road Networks

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\%$ 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.

Comment: In ALENEX 2016

Original document

The different versions of the original document can be found in:

• http://arxiv.org/abs/1511.08303

• http://arxiv.org/pdf/1511.08303

• http://epubs.siam.org/doi/pdf/10.1137/1.9781611974317.1,

http://dx.doi.org/10.1137/1.9781611974317.1

• https://dblp.uni-trier.de/db/journals/corr/corr1511.html#KontogiannisMPP15,

https://epubs.siam.org/doi/pdf/10.1137/1.9781611974317.1,

https://epubs.siam.org/doi/10.1137/1.9781611974317.1,

https://academic.microsoft.com/#/detail/2963732503