Distance oracles for time-dependent road networks (Master thesis)

Παπασταύρου, Γεωργία

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 timedependent arc-traversal-times. In this work, we present oracles for providing timedependent min-cost route plans, and conduct their experimental evaluation in two real-world data sets of large-scale, in particular the road network for the metropolitan area of Berlin, and the national road network of Germany. Our oracles provably achieve two unique features: (i) subquadratic preprocessing time and space; (ii) sublinear query time, in either the network size or the actual Dijkstra-Rank of the query at hand. The first step towards a landmark-based oracle is the selection of a subset of vertices in the graph as landmarks. Then, 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 one-to-all approximation method for creating approximations of shortest travel-time functions, called the Trapezoidal approximation method (TRAP). We then propose the FLAT oracle and three appropriate query algorithms, 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 exploit parallelism and lossless compression to severely reduce preprocessing space and time requirements. We conduct an extensive, comparative experimental study. 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. We also implement and experimentally evaluate a novel oracle (HORN), based on a landmark hierarchy. The implementation and experimental evaluation of HORN is based on a hierarchy of landmarks, from a few “global” landmarks possessing knowledge of the entire network towards (many more) “local” landmarks whose knowledge of the network is restricted to small neighborhoods around them. The advantage of HORN over FLAT is that it achieves query times sublinear, not just in the size of the network, but in the actual Dijkstra rank of the query at hand, be it long-range, mid-range, or short-range, while requiring asymptotically similar preprocessing space and time. We present a third landmark-based oracle (CFLAT) for providing route plans in time-dependent road networks, which preprocesses time-varying combinatorial structures (collections of time-stamped shortest-path trees). Its main novelty is exactly that it preprocesses only shortest-path trees, ignoring entirely the actual travel-time values, except for assessing the quality of the currently achieved approximation guarantee (a.k.a. stretch) ensured by the preprocessed information. We further exploit the repetitive appearance of only a few patterns in the preprocessed information, in order to avoid duplicate records of the same data. This leads to a significant space reduction, compared with our previous oracles. For this new kind of time-varying data structure, we also need a novel query algorithm (CFCA) that will exploit it. As shown by our experimental evaluation, CFLAT achieves a significant improvement in preprocessing time and space requirements, better approximation guarantees and also comparable (if not better) query-response times, in comparison to previous state-of-art landmark-based oracles for time-dependent shortest paths. It also achieves comparable query-time performance and approximation guarantees, on both instances, compared to state-of-art speedup heuristic techniques for time-dependent road networks. Finally, we implement and experimentally test a dynamic scheme to provide responsiveness to live-traffic reports of incidents with a small timelife (e.g., a temporary blockage of a road segment due to an accident). Our experiments also indicate that traffic information can be updated in seconds.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Subject classification: Graphic methods
Keywords: Αλγόριθμοι,Γραφήματα,Βέλτιστες διαδρομές,Algorithms,Graphs,Shortest paths
URI: http://olympias.lib.uoi.gr/jspui/handle/123456789/27892
Appears in Collections:Διατριβές Μεταπτυχιακής Έρευνας (Masters)

Files in This Item:
File Description SizeFormat 
Μ.Ε. ΠΑΠΑΣΤΑΥΡΟΥ ΓΕΩΡΓΙΑ 2017.pdf1.26 MBAdobe PDFView/Open

 Please use this identifier to cite or link to this item:
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.