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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/43865 |
| _version_ | 1826112010795876352 |
|---|---|
| author | Hardy, Jefry. |
| author2 | School of Computer Engineering |
| author_facet | School of Computer Engineering Hardy, Jefry. |
| author_sort | Hardy, Jefry. |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T02:59:55Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/43865 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:59:55Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | ntu-10356/438652023-03-03T20:44:00Z Performance evaluation of contraction hierarchies in road networks Hardy, Jefry. School of Computer Engineering Xiao Xiaokui 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 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. Bachelor of Engineering (Computer Science) 2011-05-04T08:26:14Z 2011-05-04T08:26:14Z 2011 2011 Final Year Project (FYP) http://hdl.handle.net/10356/43865 en Nanyang Technological University 57 p application/pdf |
| spellingShingle | 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 Hardy, Jefry. Performance evaluation of contraction hierarchies in road networks |
| title | Performance evaluation of contraction hierarchies in road networks |
| title_full | Performance evaluation of contraction hierarchies in road networks |
| title_fullStr | Performance evaluation of contraction hierarchies in road networks |
| title_full_unstemmed | Performance evaluation of contraction hierarchies in road networks |
| title_short | Performance evaluation of contraction hierarchies in road networks |
| title_sort | performance evaluation of contraction hierarchies in road networks |
| topic | 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 |
| url | http://hdl.handle.net/10356/43865 |
| work_keys_str_mv | AT hardyjefry performanceevaluationofcontractionhierarchiesinroadnetworks |