A hybrid GRASP with perturbations for the Steiner problem in graphs

A hybrid GRASP with perturbations for the Steiner problem in graphs

0.00 Avg rating0 Votes
Article ID: iaor20032951
Country: United States
Volume: 14
Issue: 3
Start Page Number: 228
End Page Number: 246
Publication Date: Jul 2002
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: Steiner problem
Abstract:

We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP + PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in a strategic oscillation approach. The improvement phase circularly explores two different local search strategies. The first uses a node-based neigborhood for local search, while the second uses a key-path-based neighborhood. An adaptive path-relinking technique is applied to a set of elite solutions as a post-optimization strategy. Computational results on a broad set of benchmark problems illustrate the effectiveness and the robustness of our heuristic, which is very competitive when compared to other approximate algorithms.

Reviews

Required fields are marked *. Your email address will not be published.