A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
- 1 August 2002
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 14 (3), 228-246
- https://doi.org/10.1287/ijoc.14.3.228.116
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
This publication has 21 references indexed in Scilit:
- Local search with perturbations for the prize-collecting Steiner tree problem in graphsNetworks, 2001
- The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphsNetworks, 1999
- A tabu search heuristic for the Steiner Tree ProblemNetworks, 1999
- Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive MemoryINFORMS Journal on Computing, 1999
- Efficient path and vertex exchange in steiner tree algorithmsNetworks, 1997
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- The noising method: a new method for combinatorial optimizationOperations Research Letters, 1993
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- Reduction tests for the steiner problem in grapshNetworks, 1989
- A note on two problems in connexion with graphsNumerische Mathematik, 1959