Candidate: Raheleh Zarei Chamgordani
Thesis Title: Comparative Study of Speed-up Routing Algorithms in Road Networks
Date & Time: May 11 th , 2021 @ 2:00 pm
Dr. Denis Pankratov - Chair
Dr. Lata Narayanan - Supervisor
Dr. Denis Pankratov - Examiner
Dr. Jorda Opatrny - Examiner
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.