Research On Heuristic Algorithms For The Degree Constrained Minimum Spanning Tree Problem

The degree constrained minimum spanning tree problem exists in many application scenarios in industry,such as circuit chip design,communication engineering,transportation engineering,pipeline engineering,drainage system and so on.In addition,the degree constrained minimum spanning tree problem is inextricably related to many important problems.For example,when the degree constraints of spanning trees become extremely relaxed,the problem becomes the minimum spanning tree problem in graph theory.However,when the degree constraints of each vertex in spanning trees are fixed to 2,the problem becomes the classical traveling salesman problem.In terms of computational complexity,the degree constrained minimum spanning tree problem has been proved to be NP-hard,so there is no precise algorithm with polynomial time complexity to solve it.This paper will focus on the efficient heuristic algorithm for solving the degree constrained minimum spanning tree problem.Aiming at the special problem structure of the degree constrained minimum spanning tree problem,a tabu search algorithm based on multi-objective is proposed to solve it.The main work and innovations of this paper include: Firstly,the hard constraints on degree are transformed into the primary objective of the objective function,and the original problem is transformed into the minimum spanning tree problem with the secondary objective function.Secondly,a neighborhood action based on edge exchange is designed to solve the problem.Neighborhood action improves the primary or secondary targets in the objective function as much as possible each time,and improves the search efficiency of the algorithm.Thirdly,tabu search strategy is proposed to search for the global optimal solution.When the strategy of lifting taboos is satisfied,the strategy of lifting taboos is adopted to accept the action of lifting taboos.Finally,the tabu search algorithm of the proposed two-level objective function is used to test 248 standard examples in the literature,which shows the effectiveness of the proposed algorithm and strategy.The research results show that for the degree constrained minimum spanning tree problem,the method of relaxing the original constraints to the objective function,the domain structure based on edge exchange and the taboo strategy can effectively solve the problem.At the same time,these strategies can also be used to solve other NP-hard problems.