Require: v**: the characteristic function;**
A: the set of n **agents;** maxIter**: maximum number of iterations;** neighOP**: neighbourhood operator;** maxElite**: max pool dimension;** riiSteps**: max non improving search steps for the RII procedure;** wp**: RII walk probability**
Ensure: solution Cb ∈ M(A)
1: **iter = 0** 2: P = ∅
3: while **iter** < maxiter do 4: C = GreedyRandomisedConstruction() **/* lines 4-13 of the Alg. 2 */** 5: C = RandomisedIterativeImprovement(C, wp, riiSteps, neighOP)
6: if iter ≥ 1 **then** 7: **for all** x ∈ P do 8: determine which (C or x**) is the initial and which is the target**
9: xp = PathRelinking(xs, xt)
10: **update the elite set with** xp 11: if v(xp) > v(Cb) **then**
12: Cb = xp 13: update the elite set P **with** C
14: **else**
15: insert C **into the elite set** P
16: **iter = iter + 1**
17: **return** Cb by local search and to all the solutions from the pool. Improving solutions along the tajectories are considered as candidates for insertion into the pool.

6.1. GRASP with path-relinking evaluation. **The first part of the evaluation**
of GRASP+PR **for CSG regarded its efficacy by varying the relinking strategy and** the size of the pool of elite solutions. In the first experiment we investigated the GRASP+PR **efficacy by varying the relinking strategy. Figure 5 plots the graphs**
corresponding to the RLDs for GRASP+PR adopting the SPLIT/MERGE neighbourhood operator and different relinking strategies. The setup of the **experiment is**
the same as that used in the previous GRASP **evaluations, reported in Section 5.2:** 100 problem instances for each distribution and 10 GRASP+PR **runs per instance;** the number of agents was set to 15, the walk probability of RII to 0.7, and the cutoff run-length to 107 **operations. For each instance the solution quality obtained**
with GRASP+PR **has been computed as the ratio between the optimal solution value** and the GRASP+PR **best solution value. As we can see from the graphs reported**
in Figure 5 the FORWARD/BACKWARD strategy is the most robust for **all the**
distributions, while the FORWARD strategy seems to be the less beneficial one. Table 2 reports a descriptive statistics for the search space nodes visited by GRASP+PR
with a FORWARD relinking strategy, where \#nodes **is the total number of visited** nodes; \#construction, \#local and relinking **are, respectively, the number of** nodes visited in the construction, local search and relinking phase; iter represents