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: | Ribeiro Celso C., Uchoa Eduardo, Werneck Renato F. |
Keywords: | Steiner problem |
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.