Solving the Steiner Tree Problem in graphs with Variable Neighborhood Descent
This work addresses the Steiner Tree Problem, which has applications in areas like integrated circuit design and networking, but it appears incremental as it builds on existing methods with new heuristics.
The authors tackled the Steiner Tree Problem in graphs by proposing an algorithm that combines a reducer and a solver using Variable Neighborhood Descent, along with new constructive heuristics and a vertex score system, and reported encouraging results on benchmark tests.
The Steiner Tree Problem (STP) in graphs is an important problem with various applications in many areas such as design of integrated circuits, evolution theory, networking, etc. In this paper, we propose an algorithm to solve the STP. The algorithm includes a reducer and a solver using Variable Neighborhood Descent (VND), interacting with each other during the search. New constructive heuristics and a vertex score system for intensification purpose are proposed. The algorithm is tested on a set of benchmarks which shows encouraging results.