Learning Centre

Empirical Evaluation of Two Routing Algorithms for Transportation Networks

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Kaski, Petteri
dc.contributor.author Suvivuo, Lari
dc.date.accessioned 2018-12-14T16:06:40Z
dc.date.available 2018-12-14T16:06:40Z
dc.date.issued 2018-12-10
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/35502
dc.description.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. en
dc.format.extent 51
dc.language.iso en en
dc.title Empirical Evaluation of Two Routing Algorithms for Transportation Networks en
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword shortest path algorithm en
dc.subject.keyword contraction hierarchies en
dc.subject.keyword hub labeling en
dc.subject.keyword Dijkstra's algorithm en
dc.identifier.urn URN:NBN:fi:aalto-201812146518
dc.programme.major Computer Science fi
dc.programme.mcode SCI3042 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Kaski, Petteri
dc.programme Master’s Programme in Computer, Communication and Information Sciences fi
local.aalto.electroniconly yes
local.aalto.openaccess no


Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

Statistics