General variable neighborhood search approach to group steiner tree problem

Abstract

In this paper, we consider the Group Steiner Tree (GST) problem that can be stated as follows: For a given non-negative edge weighted graph G= (V, E) , an integer k, and the corresponding family g1, … , gk containing non-empty subsets of V called groups, we need to find a minimum cost tree T= (VT, ET) where VT⊆ V and ET⊆ E that spans at least one vertex from each of the groups. Numerous applications of this NP-hard problem initiated researchers to study it from both theoretical and algorithmic aspects. One of the challenges is to provide a good heuristic solution within the reasonable amount of CPU time. We propose the application of metaheuristic framework based on Variable Neighborhood Search (VNS) and related approaches. One of our main objectives is to find a neighborhood structure that ensures efficient implementation. We develop Variable Neighborhood Descend (VND) algorithm that can be the main ingredient of several local search approaches. Experimental evaluation involves comparison of our heuristic to exact approach based on Integer Linear Programming solvers and other metaheuristic approaches, such as genetic algorithm. The obtained results show that the proposed method always outperforms genetic algorithm. Exact method is outperformed in the case of instances with large number of groups.