Multi-constrained path problem (MCPP) alms to find a path in a network that satisfies multiple additive path constraints, it has many applications such as route guidance in intelligent transportation systems and quality of service (QoS) routing in integrated networks for voice, data, and multimedia communications. It is well known that MCPP is NP-complete and heuristic or approximate algorithms are required to solve it suboptimally. A heuristic, limited path Dijkstra's algorithm (LPDKS), is presented by extension of the conventional Dijkstra's algorithm by maintaining a limited number of nondominated paths, say X non-dominated paths, for each node. Three key design problems are investigated for this new algorithm, i.e., how to maintain X non-dominated paths for each node when there are more paths available, how to decide which path to extend first, and how to determine X. We propose path deletion heuristics and path order heuristic to deal with the first two problems, and provide a heuristic value of X that can have very high probability to find a feasible path when one exists. The complexity analysis and extensive experiments are given to show the performance of the proposed algorithm.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An efficient heuristic algorithm for multi-constrained path problems


    Beteiligte:
    Xiao, Wendong (Autor:in) / Luo Yang (Autor:in) / Soong, Boon-Hee (Autor:in) / Xu, Aigong (Autor:in) / Choi Look Law (Autor:in) / Ling, Keck-Voon (Autor:in)


    Erscheinungsdatum :

    2002


    Format / Umfang :

    5 Seiten, 9 Quellen




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Print


    Sprache :

    Englisch




    Shortest path using detour heuristic algorithm

    Wu, Shu-Hui / Wang, Shu-Jen / Tai, Chien-Ting et al. | Tema Archiv | 1999



    A heuristic algorithm for traveling salesman problems

    Ashour, Said / Vega, J.F. / Parker, R.G. | Elsevier | 1971



    Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

    Avella, P. / Boccia, M. / Sforza, A. | British Library Online Contents | 2004