Comparative Study of Speed-Up Routing Algorithms in Road Networks

We study the problem of finding the shortest distance and the shortest path from one node to another in graphs modeling large road networks. Classical algorithms like Dijkstra and Astar do not have good performance in such networks. In recent years, two new approaches called Contraction Hierarchy and Hub Labeling which use preprocessing to generate auxiliary data to improve the query time performance were proposed, and many variants have followed. These algorithms are very efficient on large networks when a large number of queries is expected. In the literature, these algorithms are called speed-up algorithms. More recently, dynamic routing algorithms have been proposed, such as Customizable Contraction Hierarchy and Dynamic Hierarchical Hub Labeling. These are designed to respond efficiently to edge weight changes resulting from changes in traffic. In this thesis, we present an experimental study of the performance of the above static and dynamic routing algorithms on two different road networks, in terms of travel time and query processing time. Our results show that Customizable Contraction Hierarchy is the best for shortest path query in both the static and dynamic settings, while Hub Labeling is the most efficient in answering shortest distance queries in the static setting. We also show that Dynamic Hub Labeling’s edge weight update operations are inefficient in practice