Performance evaluation of contraction hierarchies in road networks

Performance evaluation of contraction hierarchies in road networks

Contraction hierarchy is the new idea of route planning technique. The theory is merely based on the concept of node contraction. At a time, one node is removed out of the graph and then the shortcuts are added to the corresponding remaining graph to reserve the shortest path distances. As the resul...

Full description

Saved in:
Bibliographic Details
Main Author: Hardy, Jefry.
Other Authors: School of Computer Engineering
Format: Final Year Project
Language:English
Published: 2011
Subjects:
DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
DRNTU::Engineering::Computer science and engineering::Computer applications::Physical sciences and engineering
Online Access:http://hdl.handle.net/10356/43865
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:Contraction hierarchy is the new idea of route planning technique. The theory is merely based on the concept of node contraction. At a time, one node is removed out of the graph and then the shortcuts are added to the corresponding remaining graph to reserve the shortest path distances. As the result, contraction hierarchy consists of the original graph plus the shortcuts. Having all the shortcuts added to the graph, a modified bidirectional Dijkstra algorithm is applied to acquire the shortest paths. This hierarchy has five times lower query time than the previous best hierarchical Dijkstra-based technique.

Similar Items