节点约束型链路分离算法

Node constrained link disjoint algorithm

针对节点约束型链路分离问题中的两条链路需经过各自必经点集的特点,提出一种以遗传算法和迪杰斯特拉算法为基础的节点约束型链路分离算法。通过改进的遗传算法得到较优的必经点序列,利用带有禁忌搜索的迪杰斯特拉最短距离算法求必经点对之间的无环最短路径,采用禁忌边的方式保证路径间重边最少。得到起点到终点之间的两条受必经点约束的路径,路径内无环路、路径间重边最少。大量模拟仿真实验结果表明了该算法的有效性和可行性。

According to the characteristics of two disjunct links being required to pass through their respective set of nodes for nodeconstrained link-disjoint problems,a node-constrained link disjoint algorithm based on genetic algorithm and Dijkstra algorithm was proposed.The optimal sequence of the necessary nodes with the method of an improved genetic algorithm was obtained.The Dijkstra algorithm with tabu search was used to find the loop-free shortest path between the pair of necessary nodes.The method of tabu edge was used to minimize the number of same edge between paths.Two loop-free paths were obtained which were constainted by necessary nodes from start node to end node.The number of the same edges between the pair of paths is minimized.It is verify that the alogrithm is effective and feasible by a large number of simulation experiments.