The Weighted Safe Set Problem aims to determine in an
undirected graph a subset of vertices such that the weights of the con-
nected components they induce exceed the weights of the adjacent com-
ponents induced by the complementary subset. This paper tackles the
problem with Greedy Randomized Adaptive Search Procedures based on
two different randomisation schemes. Both approaches are tested on new
benchmark instances up to 300 vertices, and compared with the only
existing heuristic approach (that is a randomised destructive heuristic)
on the original benchmark. The results suggest that the use of a restricted
candidate list outperforms all the other approaches.