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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Heuristic techniques for accelerating hierarchical routing on road networks


    Contributors:


    Publication date :

    2002-12-01


    Size :

    403231 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks

    Jagadeesh, G. R. / Srikanthan, T. / Quek, K. H. | British Library Online Contents | 2002




    Accelerating Road Vehicle Automation

    Peters, Joseph I. | Springer Verlag | 2014