Table 1: Number of evaluations for each investigated instance

| Instance n × m   | No of evaluations   |
|------------------|---------------------|
| 20 × 5 (#1)      | 1,000,000           |
| 20 × 5 (#2)      | 1,000,000           |
| 20 × 10 (#1)     | 1,000,000           |
| 20 × 10 (#2)     | 1,000,000           |
| 20 × 20          | 1,000,000           |
| 50 × 5           | 5,000,000           |
| 50 × 10          | 5,000,000           |
| 50 × 20          | 5,000,000           |
| 100 × 10         | 10,000,000          |
| 100 × 20         | 10,000,000          |

Algorithm 2 Multi-objective multi-operator search algorithm 1: Generate initial solution x, set P
approx = {x}
2: **repeat**
3: Randomly select some x ∈ P
approx | neighborhoods not investigated yet 4: Randomly select some neighborhood Ni from N1**, . . . ,** Nk 5: Generate Ni(x)
6: Update P
approx with Ni(x)
7: if x ∈ P
approx **then**
8: Set neighborhoods of x as 'investigated' 9: **end if**
10: **until** 6∃x ∈ P
approx | neighborhoods not investigated yet

## 4.2. Results

The average values obtained by the investigated metaheuristics are given in Table 2. It can be seen, that PILS
leads for all investigated problem instances to better results for both the D1 and the D2 metric. This general result is consistent independent from the actual problem instance. For a single instance, the 20×5 (\#1), PILS
was able to identify all optimal solutions in all test runs, leading to average values of D1 = D2 = 0.**0000**.

Apparently, this instance is comparably easy to solve.

| Table 2: Average results of D1 and D2 D1 D2   |        |        |        |        |
|-----------------------------------------------|--------|--------|--------|--------|
| Instance n × m                                | PILS   | MOS    | PILS   | MOS    |
| 20 × 5 (#1)                                   | 0.0000 | 0.0323 | 0.0000 | 0.1258 |
| 20 × 5 (#2)                                   | 0.1106 | 0.1372 | 0.3667 | 0.4249 |
| 20 × 10 (#1)                                  | 0.0016 | 0.0199 | 0.0146 | 0.0598 |
| 20 × 10 (#2)                                  | 0.0011 | 0.0254 | 0.0145 | 0.1078 |
| 20 × 20                                       | 0.0088 | 0.0286 | 0.0400 | 0.1215 |
| 50 × 5                                        | 0.0069 | 0.0622 | 0.0204 | 0.1119 |
| 50 × 10                                       | 0.0227 | 0.3171 | 0.0897 | 0.4658 |
| 50 × 20                                       | 0.0191 | 0.3966 | 0.0616 | 0.5609 |
| 100 × 10                                      | 0.0698 | 0.3190 | 0.1546 | 0.4183 |
| 100 × 20                                      | 0.0013 | 0.2349 | 0.0255 | 0.3814 |

A deeper analysis has been performed to monitor the resolution behavior of the local search algorithms and to get a better understanding of how the algorithm converges towards the Pareto front. Figure 2 plots with × the results obtained by random sampling 50,000 alternatives for the problem instance 100 × 10, and