Authors: Matijević, Luka 
Jelić, Slobodan
Davidović, Tatjana 
Affiliations: Computer Science 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: General variable neighborhood search approach to group steiner tree problem
Journal: Optimization Letters
Issue Date: 7-Jul-2022
Rank: M22
ISSN: 1862-4472
DOI: 10.1007/s11590-022-01904-7
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.
Keywords: Heuristic methods | Local search | Optimization on graphs | Stochastic search | Suboptimal solutions
Publisher: Springer Link

Show full item record

Page view(s)

23
checked on Sep 15, 2022

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.