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

Heuristic algorithm for multi-constrained shortest link-disjoint paths

作　　者：倪明放[1] 高石云[1] 马峰[1] 吴传信[1] 陈建文 

机构地区：[1]解放军理工大学通信工程学院,江苏南京210007 [2]总参信息化部,北京100840

出　　处：《解放军理工大学学报（自然科学版）》2013年第1期79-83,共5页Journal of PLA University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(70971136)

摘　　要：为求解多约束最短链路不相交路径(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.

关 键 词：QOS路由 链路不相交路径 整数规划 全幺模矩阵 多约束路由 最优解 

分 类 号：O221.4[理学—运筹学与控制论]