would return to the previous solution. On the other hand however, the perturbation should not entirely destroy the characteristics of the alternative. Doing that would result in a random restart of the search without keeping promising attributes of solutions.

![0_image_0.png](0_image_0.png)

Figure 1: Illustration of the Pareto Iterated Local Search metaheuristic. The archive of the currently best solutions is updated during the search. Here, G(x4) dominates G(x2) which is going to be deleted from P
approx.

The PILS metaheuristic may be formalized as given in Algorithm 1. The intensification of the algorithm, illustrated in the steps (1) and (3) of Figure 1 is within the lines 6 to 21, the description of the diversification, given in step (2) of Figure 1 is within the lines 22 to 26.

Algorithm 1 Pareto Iterated Local Search 1: Initialize control parameters: Define the neighborhoods N1**, . . . ,** Nk 2: Set i = 1 3: Generate initial solution x 4: Set P
approx = {x}
5: **repeat** 6: **repeat**
7: Compute Ni(x)
8: Evaluate Ni(x)
9: Update P
approx with Ni(x)
10: if ∃x
′ ∈ Ni(x) | x
′  x **then**
11: Set x = x
′

12: Set i = 1 13: Rearrange the neighborhoods N1**, . . . ,** Nk in some random order 14: **else**
15: Set i = i + 1 16: **end if**
17: **until** x locally optimal with respect to N1**, . . . ,** Nk, therefore **i > k**
18: Set neighborhoods of x as 'investigated' 19: Set i = 1 20: if ∃x
′ ∈ P
approx | neighborhoods not investigated yet **then**
21: Set x = x
′

22: **else**
23: Select x
′ ∈ P
approx 24: Compute x
′′ = N**perturb**(x
′
)
25: Set x = x
′′

26: **end if** 27: **until** termination criterion is met