Performance evaluation of contraction hierarchies in road networks

• المؤلف الرئيسي: Hardy, Jefry.
• مؤلفون آخرون: School of Computer Engineering
• التنسيق: Final Year Project
• اللغة: English
• منشور في: 2011
• الموضوعات: 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
• الوصول للمادة أونلاين: http://hdl.handle.net/10356/43865
• المؤسسة: Nanyang Technological University

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.