Doi: 10. 1016/S0305-0548(03)00202-8

r
 level 
j
level 
j+1
 level 
j-1
Fig. 4. Algorithm illustration: before (left) and after (right) Recluster.
we create trees from these star-like clusters to evaluate the actual solution. Operation Tree is also
used in the TreePlan algorithm for creating trees under the already planned parts.
5.1.1.3. Moves. This operation performs local optimization on a candidate solution in order to
improve it. Operation Moves detaches a node from its original parent node and connects it to a
new parent node. The move is accepted if it yields a lower solution cost. Two subsets of N are
the input for this operation. The /rst set C includes the candidate nodes that can be moved, while
the second one P contains the parent nodes to be examined as target nodes for a move. We try all
candidate–parent pairs for possible moves while they improve the current solution. This operation is
used by compound operations Recluster and LocalOpt.
5.1.1.4. Swaps. This operation also performs local optimization on a given solution. Here the
elementary step interchanges (swaps) the parent nodes of two given candidate nodes. We accept a
swap only if it results lower cost. The input of Swaps is a subset C ⊆ N containing the candidate
nodes that are allowed to be swapped. We try all possible pairs of candidate nodes for swapping
while they improve the current solution. This operation is used by compound operations Recluster
and LocalOpt.
5.1.2. Compound operations
5.1.2.1. Recluster. This operation recalculates the number and positions of the concentrators in
a selected part of the network and integrates operation Cluster with local optimization operations
Moves and Swaps. It has three input parameters: a node r, which de/nes the subsection of the
solution to be reorganized, the type of allocation step within Cluster and the frequency of local
optimization steps. Operation Recluster works as follows (see Fig.
4
):
(1) Consider the child nodes of r in level j and their children in level j + 1.
(2) Select new nodes to be concentrators in level j from the considered nodes and connect them
to r.
(3) Connect the remaining nodes to the new concentrators.

---

70
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
We have two options for allocation step within Cluster. In the /rst case, we pick a random
node and connect it to the median that provides the least cost; then repeat this until all nodes have
been allocated to a median. In the second case, we choose the least-cost connection between a node
and a median from all possible node-median pairs. Then we repeat this until all nodes have been
allocated. At the relocation step, we try out all nodes in each cluster as a candidate for new median
and the one providing the least cost will be chosen as the new median in each cluster, separately.
The cost-calculation step is based on the real network costs and it is performed only in the a?ected