Empirical Evaluation of Two Routing Algorithms for Transportation Networks

Abstract

In the shortest path problem we have a weighted graph, a source vertex and a target vertex as an input. The task is to find a sequence of connected edges from the source to the target such that the sum of the edge weights in the path is minimized.

In this thesis we examine two algorithms for solving this problem: (1) contraction hierarchies, an algorithm proposed by Robert Geisberber in 2008 that takes advantage of the hierarchical structure of real world road networks and (2) hub labeling, an algorithm developed by Abraham et al. in 2010 that precomputes the distances between certain vertices to always find the shortest path in just two hops. We also implement these two algorithms and run them on the road network of Finland to compare their performance to each other and to that of Dijkstra's algorithm.

The results of our experiments show that both algorithms have significantly better query times than Dijkstra's algorithm decreasing the average times from 4.5 seconds to 44 milliseconds for contraction hierarchies and 0.4 ms for hub labeling in the road network of Finland with 440000 nodes. This increased performance comes at the cost of few minutes of preprocessing time and increased memory consumption, with hub labeling being requiring significantly more memory than the other algorithms. Unfortunately, our Python implementation falls behind the most efficient ones in running time and memory usage.