A Steiner point candidate-based heuristic framework for the Steiner tree problem in graphs. Issue 2 (June 2016)

• Record Type: Journal Article
• Authors: Zhang, Hao; Ye, Dong-Yi; Guo, Wen-Zhong
• Is Part Of: Journal of algorithms & computational technology. Volume 10:Issue 2(2016)
• Page Start: 99
• Page End: 114
• Publication Date: 2016-06
• Subjects: NP-hard -- Steiner tree problem in graphs -- Steiner points -- Voronoi diagram; Computer algorithms -- Periodicals; Numerical calculations -- Periodicals; Computer algorithms; Numerical calculations; Periodicals; 518.1
• DOI: 10.1177/1748301816640714
• Languages: English
• ISSNs: 1748-3018

Abstract

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: markingSPC I points, constructing the Steiner tree, eliminating the detour paths, andSPC II -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 candidatesSPC I . The solution qualities of the classic heuristics are effectively improved by lookingSPC I points as terminals. By constructing a Voronoi diagram, a series of methods are suggested to mark the second type of Steiner point candidatesSPC II . The feasible solution quality is efficiently improved by employing theSPC II 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.