|Table of Contents|

Comparative Study of Multi-constrained Optimal Path Algorithms


Research Field:
Publishing date:


Comparative Study of Multi-constrained Optimal Path Algorithms
MA Yue-yong1WANG Hai-mei2LIAO Jian-jun2
1. Modern Educational Technology Center; 2. School of Automation,NUST,Nanjing 210094,China
multi-constraint optimal path multi-arc weights network path algorithm heuristic search
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.


[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.


Last Update: 2012-10-25