非线性约束最短路问题的启发式算法

多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题。它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法。然而这些方法只能求解一些带有线性约束的RSP。对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性。本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP。主要思想是将非线性约束作为检验条件来使用。当每得到一个解时,检查解是否满足非线性约束。如满足,则得到最终解;否则在原问题中添加一个线性约束。该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解。仿真算例说明了算法的有效性。

Heuristic Algorithm for Shortest Path Problem with Nonlinear Constraints

Multiple constrained quality of service (QoS) routing optimization is one of important problems in current network research. A basic problem in QoS routing is the restricted shortest path problem (RSP), which is known to be non-polynomial (NP). Many heuristic algorithms with polynomial-time and pseudo polynomial-time complexity have been proposed to solve it. However these algorithms only deal with RSP with linear constraint and transform nonlinear constraint such as loss rate to linear constraint when confronting nonlinear constraint, which will increase the complexity of the problem. A new heuristic algorithm with pseudo polynomial-time complexity is proposed to solve RSP with nonlinear constraints (NRSP). The core of this algorithm is that the nonlinear constraints will not be transformed to linear constraints but as examining conditions. At each iteration step, RSP problem with linear constraint will be solved. If the solution does not satisfy nonlinear constraints, a new linear constraint is added to the original RSP problem. The aim of the new linear constraint is to eliminate the selected path, which ensures the algorithm succeeds to find a solution to NRSP once NRSP has a solution.