A Novel Approximate Solution Method for Euclidean Steiner Tree Problem Based on Genetic Algorithm

A novel approximate solution method for the Euclidean Steiner tree problem is proposed and its performance is demonstrated through experiments using 195 benchmark problem instances from the OR-Library. Given a finite number of terminal points, the proposed method first generates non-terminal points around each terminal point and at the same location as the Steiner point for each triangle obtained by the Delaunay triangulation for all terminal points. It next runs a genetic algorithm to select a subset of the generated non-terminal points, aiming to minimize the total edge length of a minimum spanning tree for all the terminal points and the selected non-terminal points. It then optimizes the locations of the non-terminal points in the tree using Weiszfeld’s method, while preserving the topology. It finally refines the tree by adding new non-terminal points, adding and removing edges, and optimizing the locations of all non-terminal points. The experimental results show that, among 150 benchmark problem instances with known optimal solutions, the proposed method successfully constructs a Euclidean Steiner tree for 61 instances. For the remaining 89 instances, it produces an approximate solution whose total edge lengths is less than 100.7% of the optimal. The experimental results also show that the proposed method obtains approximate solutions efficiently: within 1.5 seconds for instances with up to 100 terminal points and within 61 seconds for instances with up to 1,000 terminal points.