A parallel grasp for the Steiner tree problem in graphs using a hybrid local search strategy

In this paper, we present a parallel greedy randomized adaptive search proc edure (GRASP) for the Steiner problem in graphs. GRASP is a two-phase metah euristic. In the first phase, solutions are constructed using a greedy rand omized procedure. Local search is applied in the second phase, leading to a local minimum with respect to a specified neighborhood. In the Steiner pro blem in graphs, feasible solutions can be characterized by their non-termin al nodes (Steiner nodes) or by their key-paths. According to this character ization, two GRASP procedures are described using different local search st rategies. Both use an identical construction procedure. The first uses a no de-based neighborhood for local search, while the second uses a path-based neighborhood. Computational results comparing the two procedures show that while the node-based variant produces better quality solutions, the path-ba sed variant is about twice as fast. A hybrid GRASP procedure combining the two neighborhood search strategies is then proposed. Computational experime nts with a parallel implementation of the hybrid procedure are reported, sh owing that the algorithm found optimal solutions for 45 out of 60 benchmark instances and was never off by more than 48 of the optimal solution value. The average speedup results observed for the test problems show that incre asing the number of processors reduces elapsed times with increasing speedu ps. Moreover, the main contribution of the parallel algorithm concerns the fact that larger speedups of the same order of the number of processors are obtained exactly for the most difficult problems.