Y. Lee, H. Sherali, J. Han and S. Kim in 2000 ([8]), have studied the IDP problem with an additional constraint such that for each ring i, |Nodes(Ei)| ≤ R. The authors present a mixed-integer programming model for the problem, and develop a branch-and-cut algorithm. They also introduce a heuristic to generate an initial feasible solution, and another one to improve the initial solution. To initialize a ring, the heuristic first, adds the node u with the maximum graph degree, with respect to unassigned edges, and then adds to the partition the edge [u, v] such that the graph degree of v is maximum. It iteratively increases the partition by choosing a node such that the total traffic does not exceed the limit B. A set of 40 instances is generated to test these heuristics and the branch-and-cut.

## 2.3 Local Search For Srap And Idp

More recently, in [2], these two problems have been studied. The authors have developed different metaheuristic algorithms, all based on the Tabu Search. The metaheuristics are the *Basic Tabu Search*
(BTS), two versions of the *Path Relinking* (PR1, PR2), the *eXploring Tabu Search* (XTS), the *Scatter* Search (SS), and the *Diversification by Multiple Neighborhoods* (DMN). These local search algorithms are detailed further.

Previously, we saw that with local search it is necessary to define a neighborhood to choose the next solution. The authors of [2] use the same for all of their metaheuristics. It tries to assign an item x from a partition, P1, to another partition, P2. The authors also consider the neighborhood obtained by swapping two items, x and y, from two different partitions, P1 and P2. But instead of trying all the pairs of items, it will only try to swap the two items if the resulting solution of the assignment of x to the partition P2 is unfeasible.

In order to compute a starting solution for the IDP problem, the authors describe four different heuristics. The first heuristic introduced in [2] ordered the edges by decreasing weight, at each iteration it tries to assign the edge with the biggest weight which is not already assigned, to the ring with the smallest residual capacity regarding to capacity constraint. If no assignment is possible, the current edge is assigned to a new ring. The second one, sorts the edges by increasing weight, and tries to assign the current edge to the current ring if the capacity constraint is respected, otherwise the ring is no longer considered and a new ring is initialized with the current edge.

The two other methods described in [2] are based on the idea that to save ADMs a good solution should have very dense rings. They are both greedy and rely on a clique algorithm. In graph theory, a clique in an undirected graph G = (V,E) is a subset of the vertex set C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. Finding a clique is not that easy, a way to do it is to use an "Union-Find" strategie, *Find* two clique A and B such that each node in A is adjacent to each node in B then merge the two cliques (*Union*). The associated heuristic starts by considering each node to be a clique of size one, and to merge two cliques into a larger clique until there are no more possible merges.

In the third method, *Clique-BF*, it iteratively selects a clique of unassigned edges with the total traffic less or equal to B. Then assigns it to the ring that minimizes the residual capacity and, if possible, preserves the feasibility. If both of them are impossible it places it to a new ring. Algorithm 4 shows the pseudo code associated to this heuristic. The last algorithm, *Cycle-BF*, is like the previous method, but instead of looking for a clique at each iteration it try to find a cycle with as many cords as possible.

They also introduce four objective functions, one of which depends on the current and the next status of the search. Let z0 be the basic objective function counting the number of rings of a solution for SRAP,
and the total number of ADMs for IDP, and let BN be the highest load of a ring in the current solution.