Shortest-path algorithms on road networks and real-world applications Full text

Alexandros Efentakis
PhD Thesis, School of Electrical and Computer Engineering, National Technical University of Athens, Greece
2014
PhD Thesis
Abstract.

During the last two decades, shortest-path algorithms in the context of road networks and mapping applications have been a very active area of research that has produced significant results used by thousands of users worldwide. Unfortunately, despite the plethora of efficient methods and algorithms, there has not been an one-size-fits-all solution that may universally handle all the different query variations and use-cases. To this end, this thesis focuses on advancing several aspects of the current state-of-the-art in this suggested area, by improving previous works regarding point-to-point queries and proposing novel algorithms addressing multiple shortest-path query variations, especially in the context of dynamic road-networks with frequent traffic updates. Those query variations include: (i) The single-source shortest-path problem (finding the shortest-path distances between a source vertex and all other graph vertices) (ii) The one-to-many variant (calculating distances between a source vertex and a set of target vertices). (iii) Range queries (find all vertices reachable from source vertex within a given timespan) and finally (iv) k-NN queries (finding the k-nearest objects to a given query location). For all those different query definitions on road networks, the methods and algorithms proposed in this dissertation provide excellent performance and very short preprocessing times, suitable for all types of practical use-cases and applications.

The second main focus of this dissertation is to bridge the gap between the different solutions and types of shortest-path queries on road networks and propose a unified framework of algorithms and data structures that may efficiently handle all the different variations of shortest-path problems, while requiring very short preprocessing times of a few seconds, so that it may also be used in the case of dynamic road networks with frequent traffic updates. Such a solution will be extremely useful to many practical problems and may be used in several real-world applications. Consequently, within this work we have also developed a real-time service that demonstrates the practical applications of our novel results by utilizing traffic-data originating from vehicle fleets. Moreover, the results of our efforts have been significantly extended to multiple domains, from geomarketing applications and map-updates to crowdsourcing sentiments of users in relation to space.