多约束最短链路不相交路径的启发式算法

Heuristic algorithm for multi-constrained shortest link-disjoint paths

为求解多约束最短链路不相交路径(MCSDP(k))问题,提出了一种启发式的整数规划方法:FHABIP,并给出了算法搜索方案。根据问题的整数线性约束集合具有的结构特点,利用拉格朗日乘子把整数线性约束集合中的复杂约束引入到目标函数中,导出具有约束系数矩阵是全幺模矩阵特点的整数线性规划问题,从而使这类问题能用单纯形法容易求解。MCSDP(k)在求解线性规划问题的迭代过程中很容易地被求出。算法实验结果表明该算法快速有效。

To solve the multi-constrained shortest link-disjoint paths （MCSDP（k）） problem, a heuristic in- teger program algorithm was proposed and the searching scheme was given. Based on a nice feature of the integer linear constrains set, the complicated constrains were penaltied in the objective function by La- grangian multipliers, then an integer linear program problem of which the constrains coefficients matrix is totally unimodular was reformulated. This integer linear problem can be solved efficiently by using sim- plex algorithm and the MCSDP（k） can be found in the iterative process of solving the linear programming problems. Experiments demonstrate that the algorithm proposed is fast and effective.