A Simple and Fast Algorithm for Restricted Shortest Path Problem
The restricted shortest path problem (RSP) is considered as one of the key components of the Quality of Service (QoS) routing. It is well-known that this problem is NP-hard. A simple and fast algorithm for solving RSP is presented in this paper. The idea is to include complicating constraints in the objective function with the penalty term, optimizes the resulting Lagrangian relaxation problem. A simple technique of updating multiplies based on penalty method is also applied in the iterative process. The motivation behind the algorithm is that relaxation problem can be solved rapidly and updating of Lagrangian multipliers are calculated easily in the iterative process. The numerical results show that the algorithm presented in this paper is simple and fast.
Restricted shortest path QoS routing Lagrangian relaxation Penalty function
Mingfang Ni Xinrong Wu Zhanke Yu Bin Gao
Institute of Communications Engineering PLA University of Science and Technology Nanjing, China, 210 Institute of Communications Engineering PLA University of Science and Technology Nanjing, China, 210
国际会议
昆明、丽江
英文
99-102
2011-04-15（万方平台首次上网日期，不代表论文的发表时间）