A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

Celso C. Ribeiro, Eduardo Uchoa, Renato F. Werneck

INFORMS Journal on Computing · 2002 · Volume 14 · Issue 3

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 anode-based neighborhood 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 apost-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.

Keywords

Combinatorial Optimization, Steiner Problem in Graphics, Metaheuristics, GRASP, Perturbations, Strategic Oscillation, Path Relinking

Enable JavaScript for citation tools and additional paper interactions.