Login | Register

Comparative Study of Speed-Up Routing Algorithms in Road Networks


Comparative Study of Speed-Up Routing Algorithms in Road Networks

Zarei Chamgordani, Raheleh (2021) Comparative Study of Speed-Up Routing Algorithms in Road Networks. Masters thesis, Concordia University.

[thumbnail of ZareiChamgordani_MSc_S2021.pdf]
Text (application/pdf)
ZareiChamgordani_MSc_S2021.pdf - Accepted Version
Available under License Spectrum Terms of Access.


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.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Zarei Chamgordani, Raheleh
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:13 May 2021
Thesis Supervisor(s):Narayanan, Lata
ID Code:988411
Deposited By: Raheleh Zarei Chamgordani
Deposited On:29 Jun 2021 23:20
Last Modified:29 Jun 2021 23:20
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top