The optimal route between a given origin and destination needs to be computed in a fast and efficient manner in dynamic route guidance systems. Conventional routing algorithms have been found to be inadequate when applied directly to large road networks. Algorithms based on the concept of hierarchical abstraction make use of the knowledge about the road network to reduce search and provide near-optimal solutions. A generic procedure is presented for organising a given road network as a multiple-layer hierarchy. An efficient hierarchical routing algorithm is proposed, which breaks down the route search into a number of individual searches in small sub-networks. The algorithm incorporates a heuristic layer-switching technique to improve its performance without compromising the accuracy. The hierarchical routing algorithm was tested on the road network of Singapore and the solutions were found to be comparable to the optimal least-cost paths.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Route computation in large road networks: a hierarchical approach


    Beteiligte:
    Jagadeesh, G.R. (Autor:in) / Srikanthan, T. (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    2008-12-01


    Format / Umfang :

    9 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Hierarchical Path Computation Approach for Large Graphs

    Rajagopalan, R. | Online Contents | 2008


    Hierarchical path computation approach for large graphs

    Rajagopalan, R. / Mehrotra, K. / Mohan, C. et al. | IEEE | 2008




    Route factors in road networks

    Timbers, J.A. | Engineering Index Backfile | 1967