"A GRASP with path-relinking heuristic for the prize-collecting generalized minimum spanning tree problem"
Ruslán Marzo and Celso Ribeiro
The prize-collecting generalized minimum spanning tree problem is a generalization of the NP-hard generalized minimum spanning tree optimization problem. We propose a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic for its approximate solution. The computational experiments showed that the heuristic developed in this work found very good optimal and suboptimal solutions for test problems with up to 439 vertices. Furthermore, we also showed that path-relinking and restart strategies consistently improved the more basic version of GRASP algorithm.