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.
An efficient heuristic algorithm for multi-constrained path problems
2002
5 Seiten, 9 Quellen
Aufsatz (Konferenz)
Englisch
Shortest path using detour heuristic algorithm
Tema Archiv | 1999
|A heuristic algorithm for traveling salesman problems
Elsevier | 1971
|Path-Constrained Traffic Assignment: Model and Algorithm
Online Contents | 2012
|Resource Constrained Shortest Path Problems in Path Planning for Fleet Management
British Library Online Contents | 2004
|