
| Dis.    | #nodes         | #construction    | #local            | #relink          | iter      |          |       |
|---------|----------------|------------------|-------------------|------------------|-----------|----------|-------|
| U       | 33109.5        | 6745.0 (20.4%)   | 25578.4 (77.2%)   | 786.0 (2.4%)     | 13.2      |          |       |
| US      | 3789510.5      | 363175.4 (9.6%)  | 3334008.3 (88.0%) | 92326.8 (2.4%)   | 893.3     |          |       |
| N       | 3061.9         | 605.2 (19.8%)    | 2456.7 (80.2%)    | 0 (0.0%)         | 1         |          |       |
| NS      | 2732970.0      | 350673.3 (12.8%) | 2268367.5 (83.0%) | 113929.2 (4.17%) | 853.0     |          |       |
| ND      | 1528595.9      | 301562.6 (19.7%) | 1105793.2 (72.3%) | 121240.1 (7.9%)  | 699.0     |          |       |
| Table   | 2. Descriptive | statistics       | for               | the              | search    | space    | nodes |
| visited | by             | GRASP+PR         | with              | FORWARD          | relinking | strategy | and   |

Dist. **Alg.** mean min max stddev vc q0.75/q0.25 #opt

UG **48909.2 1658 1127280 89177.1 1.82 6.64 1000**

G+PR **33109.5 1697 826931 55954.2 1.69 4.49 1000**

US G **4422351.4 5958 10138012 3719544.2 0.84 7.76 781**

G+PR **3789510.5 5579 10130711 3500039.9 0.92 7.45 848**

NG **3057.6 2280 6683 600.5 0.20 1.23 1000**

G+PR **3061.9 2123 6115 585.4 0.19 1.23 1000**

NS G **3923760.0 2681 10076751 3496925.3 0.89 7.22 845**

G+PR **2732969.9 13193 10014158 3048544.5 1.11 6.81 911**

ND G **2131138.6 1633 10004863 2903255.4 1.36 10.65 929**

G+PR **1528595.9 1144 10002688 2548228.5 1.67 12.00 949**

Table 3. **Descriptive statistics for the RLDs shown in Figure 7;**

vc = stddev/mean **denotes the variation coefficient, and** q0.75/q0.25 the quantile ratio, where qx denotes the x**-quantile.**

we fixed the FORWARD relinking strategy and let to range the maxElite **parameter** from the values belonging to the set {10, 50, 100, 250, 500}**. Figure 6 plots the** obtained RLDs showing that, for each distribution, the adoption of **a large** maxiter value let GRASP+PR **to quickly find the best solution.**
The third experiment compared the behaviour of GRASP **with respect to that**
of GRASP+PR **by considering solution qualities and the runtime performances. The** setting of the experiment is the same: 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, the cutoff run-length to 107 **operations, the relinking**
strategy was FORWARD, the neighbourhood operator was SPLIT/MERGE, and the pool size of the elite solutions to 10. Figure 7 plots the obtained RDLs and the Table 3 reports the corresponding descriptive statistics.

Finally, even if GRASP+PR **is not a complete algorithm returning the optimal**
solution, we compared it to the two best performing algorithm able to **return the** optimal solution. Given different numbers of agents, ranging from 10 to 18, we compared GRASP+PR to IDP and IP **reporting the time required to find the optimal** coalition structure. As reported in Figure 8, where the time in seconds is plotted in a log scale, GRASP+PR **outperforms both** IDP and IP **for non scaled distributions.** Its efficacy is comparable to that of IDP and IP on the scaled distributions.