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

Heuristic Algorithm for Constrained Shortest Link-disjoint Paths

作　　者：高石云[1] 高国伟[2] 马峰[3] 

机构地区：[1]解放军理工大学通信工程学院研究生1队 [2]中国人民解放军93251部队 [3]解放军理工大学通信工程学院研究生3队

出　　处：《军事通信技术》2012年第1期57-62,共6页Journal of Military Communications Technology

摘　　要：文章研究约束最短链路不相交路径(CSDP(k))问题,该问题分为两类:CSDP(k)-和CSDP(k)-。首先引入问题的整数规划模型,通过拉格朗日乘子将复杂约束引入到目标函数中,接着给出了求解CSDP(k)-的一种快速启发式算法FHABIP,并给出了改进的搜索方案。算法实验结果表明该算法快速有效,能得到最优解或很好的近似最优解。The Constrained Shortest link-Disjoint Paths （CSDP （k）） phenomenon contains two classes ： CSDP （k）-I and CSDP （k）- Ⅱ. Firstly, an integer programming formulation of this phenomenon was introduced. Secondly, the complicated constraints were included in the objective function of the integer programming problem formulated by Lagrangian multipliers. Then a heuristic algorithm FHABIP aiming at solving the CSDP（k）I problem was proposed, and the improved searching schemes of the algorithm were presented as well. The computational experiments show that the proposed algorithm is fast and effective in terms of the ability to obtain the optimal solution or a good approximate solution.

关 键 词：服务质量路由 链路不相交路径 整数规划 全幺模矩阵 最优解 

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