A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

Celso Ribeiro (celsoinf.puc-rio.br)
Eduardo Uchoa (uchoainf.puc-rio.br)
Renato Werneck (rwerneckinf.puc-rio.br)

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 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 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.

Keywords: Steiner problem in graphs, metaheuristics, GRASP, perturbations, path-relinking

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Applications -- Science and Engineering (VLSI layout )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Revised version submitted for publication, May 2001, Department of Computer Science, Catholic University of Rio de Janeiro, Rua Marquês de São Vicente 225, Rio de Janeiro 22453-900, Brazil

Download: [Postscript][Compressed Postscript]

Entry Submitted: 05/03/2001
Entry Accepted: 05/03/2001
Entry Last Modified: 05/03/2001

Modify/Update this entry