The route computation module is one of the most important functional blocks in a dynamic route guidance system. Although various algorithms exist for finding the shortest path, their performance tends to deteriorate as the network size increases. We present an efficient hierarchical routing algorithm that finds a near-optimal route and evaluate it on a large city road network. Solutions provided by the hierarchical routing algorithm are compared with the optimal solutions to analyze and quantify the loss of accuracy. We propose a novel yet simple heuristic to substantially improve the performance of the hierarchical routing algorithm with acceptable loss of accuracy. A network pruning technique has been incorporated into the algorithm to reduce the search space and the correctness of the results is evaluated. The improved hierarchical routing algorithm that incorporates the heuristic techniques has been found to be over 50 times faster than a typical shortest path algorithm.
Heuristic techniques for accelerating hierarchical routing on road networks
IEEE Transactions on Intelligent Transportation Systems ; 3 , 4 ; 301-309
01.12.2002
403231 byte
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks
British Library Online Contents | 2002
|Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks
Online Contents | 2002
|Efficient Routing on Large Road Networks Using Hierarchical Communities
Online Contents | 2011
|