The best initializing method assigned all the items, nodes for SRAP or edges for IDP, to the same partition. This solution is certainly unfeasible as all the traffic is on only one ring. This biases the search towards solutions with a minimum value for the cost and a very bad value for the capacity constraints' violations. Astonishingly this is the one that gave us the best results on large instances.

We had good confidence in another one which first computes the lower bound klb (described in section 2) and randomly assigns all the items to exactly klb partitions. The idea was to let the Local Search reduce the number of violations. This starting solution was good on small instances and not so good on large ones. It was the same with a random solution, which corresponds, for these problems, to a solution where all the items are randomly assigned to a partition.

## 3.2 Neighborhoods

In a generic partitioning problem there are usually two basic neighborhoods. From a given solution, we can move an object from a subset to another subset or swap two objects assigned to two different subsets.

For SRAP a neighboring solution is produced by moving a node from a ring to another (including a new one) or by swapping two nodes assigned to two different rings. The same kind of neighborhood can be used for IDP: moving an edge from a ring to another or swapping two edges.

In some cases it is more efficient to restrain the neighborhood to the feasible space. We have tested different variants of the basic neighborhood applying this idea, by choosing the worst partition (wrt. the capacity constraint) and even by assigning it to the partition with the lowest load. Anyway it appears to be less efficient than the basic one. As will be seen later it seems that on these problems it is necessary to keep the search as broad as possible.

## 3.3 Objective Function

We have compared the four objective functions described in [2] (see Section 2) to a new one we have defined: z5.

$$z_{5}=z_{0}+\sum_{p\,\in\,p a r t i o n s}v i o l a t i o n s(p)$$

where partitions are all the rings (in the case of the SRAP problem the *federal ring* is also included),

$\mathit{violations}(p)=\left\{\begin{array}{ll}\mathit{capacity}(p)-B&\text{if the load of$p$exceed$B$}\\ 0&\text{otherwise.}\end{array}\right.$
This objective function minimizes the basic function z0 and penalizes the unfeasible solutions, but contrarily to the previous objectives, this penalty is based on all the constraints. We consider that every constraint is violated by a certain amount (its current load minus B). By summing all the violations of the current solution, we obtain the total violation for all the constraints, and we can precisely say how far we are from a feasible one. If the current solution is feasible, ∑
p ∈ partitions violations(p) = 0.

This objective has also the nice property that it is merely local, depending only on the current solution and not on the other moves. Notice that a feasible solution with 4 rings will be preferred to an unfeasible solution with 3 rings, as z0 is much smaller than the load of a ring.