|Table of Contents|

Comparative Study of Multi-constrained Optimal Path Algorithms

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2011年06期
Page:
749-754
Research Field:
Publishing date:

Info

Title:
Comparative Study of Multi-constrained Optimal Path Algorithms
Author(s):
MA Yue-yong1WANG Hai-mei2LIAO Jian-jun2
1. Modern Educational Technology Center; 2. School of Automation,NUST,Nanjing 210094,China
Keywords:
multi-constraint optimal path multi-arc weights network path algorithm heuristic search
PACS:
TP393
DOI:
-
Abstract:
In view of the problems of optimal path search and its efficiency for multi-arc weights network, four algorithms of multi-constrained optimal path ( MCOP) are presented and comparatively studied. A D_MCOP algorithm for MCOP is proposed based on the classical Dijkstra’s algorithm; an exact A* _MCOP algorithm and an iterative deepening search algorithm—IDA* _MCOP algorithm are designed by introducing a heuristic idea; a multi-constrained fringe search algorithm—Fringe_MCOP algorithm is proposed to overcome the shortcoming of the IDA* _MCOP algorithm that restarts search from the start node in each iteration. Example research results show: the extended node numbers, edge-numbers and execution times of the heuristic search algorithms are less than those of the D_MCOP algorithm, and the Fringe_MCOP algorithm has the best performance in the heuristic search algorithms; the more approximate the given constraint conditions and the weight vectors of the optimal path are, the higher the execution efficiencies of the algorithms are. The trend is more obvious when the network is bigger; when the constraint condition is too strict to get the fulfilling path, the speeds of the A* _MCOP algorithm and Fringe_MCOP algorithm are faster than that of the IDA* _MCOP algorithm, and the D_MCOP algorithm is the slowest.

References:

[1] Li Yuxi,Harms J,Holte R. Fast exact multiconstraint shortest path algorithms[A]. 2007 IEEE International Conference on Communication[C]. Glasgow,Scodland, UK: IEEE, 2007: 123-130.
[2] Fujita N, Iwata A. Adaptive and efficient multiple path pre-computation for QoS routing protocols[A]. 2001 Global Telecommunications Conference[C]. San Antonio, TX,USA: IEEE, 2001: 2215-2219.
[3] Yuan Y,Wang Dingwei. Multi-objective path selection model and algorithm for emergency evacuation[A]. 2007 IEEE International Conference on Automation and Logistics[C]. Jinan,China: IEEE, 2007: 340-344.
[4] Ji Zhaowang,Chen A,Subprasom K. Finding multi-objective paths in stochastic networks: A simulation-based genetic algorithm approach[A]. 2004 Congress on Evolutionary Computation[C]. Portland,OR,USA: IEEE, 2004: 174-180.
[5] 戴树贵,孙强,潘荫荣. 带限制条件的多权最短路径 近似算法[J]. 计算机工程, 2003, 29( 7) : 88-91.
[6] 邹永贵,魏来. 带多约束条件的最优路径选择算法 研究[J]. 计算机应用, 2008, 28( 5) : 1101-1103.
[7] Gang Liu,Ramakri-shnan K C. A* prune: An algorithm for finding K shortest paths subject to multiple constraints [A]. 2001 IEEE Computer and Communications Societies [C]. Anchorage,AK,USA: IEEE, 2001: 743-749.
[8] Korkmaz T,Krunz M. Multi-constrained optimal path selection[A]. 2001 IEEE Computer and Communications Societies[C]. Anchorage,AK,USA: IEEE, 2001: 834-843.
[9] 胡永良. 启发式多约束路由算法研究[J]. 计算机工 程与应用, 2005, 41( 30) : 155-157.

Memo

Memo:
-
Last Update: 2012-10-25