A Steiner point candidate-based heuristic framework for the Steiner tree problem in graphs

摘要

The underlying models of many practical problems in various engineering fields are equivalent to the Steiner tree problem in graphs, which is a typical NP-hard combinatorial optimization problem. Thus, developing a fast and effective heuristic for the Steiner tree problem in graphs is of universal significance. By analyzing the advantages and disadvantages of the fast classic heuristics, we find that the shortest paths and Steiner points play important roles in solving the Steiner tree problem in graphs. Based on the analyses, we propose a Steiner point candidate-based heuristic algorithm framework (SPCF) for solving the Steiner tree problem in graphs. SPCF consists of four stages: marking SPC_Ⅰ points, constructing the Steiner tree, eliminating the detour paths, and SPC_Ⅱ-based refining stage. For each procedure of SPCF, we present several alternative strategies to make the trade-off between the effectiveness and efficiency of the algorithm. By finding the shortest path clusters between vertex sets, several methods are proposed to mark the first type of Steiner point candidates SPC_Ⅰ. The solution qualities of the classic heuristics are effectively improved by looking SPC_Ⅰ points as terminals. By constructing a Voronoi diagram, a series of methods are suggested to mark the second type of Steiner point candidates SPC_Ⅱ. The feasible solution quality is efficiently improved by employing the SPC_Ⅱ points as the insertable key-vertices in key-vertex insertion local search method. Numerical experiments show that the proposed strategies are all effective for improving the solution quality. Compared with other effective algorithms, the proposed algorithms can achieve better solution quality and speed performance.