Local search with perturbations for the prize‐collecting Steiner tree problem in graphs
S. A. Canuto, Maurício G. C. Resende, Celso Carneiro Ribeiro · Networks · 2001
Abstract Given an undirected graph with prizes associated with its nodes and weights associated with its edges, the prize‐collecting Steiner tree problem consists of finding a subtree of this graph which minimizes the sum of the weights of its edges plus the prizes of the nodes not spanned. In this paper, we describe a multistart local search algorithm for the prize‐collecting Steiner tree problem, based on the generation of initial solutions by a primal‐dual algorithm using perturbed node prizes. Path‐relinking is used to improve the solutions found by local search and variable neighborhood search is used as a post‐optimization procedure. Computational experiments involving different algorithm variants are reported. Our results show that the local search with perturbations approach found optimal solutions on nearly all of the instances tested. © 2001 John Wiley & Sons, Inc.