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

parts of the network.
We extended operation Cluster with local optimization steps. We have four options to control the
frequency of performing Moves and Swaps within the clustering: (i) no local optimization at all,
(ii) we apply Moves and Swaps only at the end of Cluster, (iii) we apply local optimization for
each value of K, and (iv) we apply local optimization after each allocation and relocation step.
5.1.2.2. ReclusterLevel. This operation iteratively performs operation Recluster in order to /nd
better connections and concentrator positions in an entire level of the hierarchy. We go through the
nodes of the given level (l) sequentially and choose these nodes as parameter r for Recluster. By
this, the concentrators in level l + 1 will be reorganized in the entire network. We can consider
operation ReclusterLevel as a horizontal optimization in the hierarchy.
We apply this operation in the improvement phase to recompute the concentrators at each level.
We start with the reconstruction of level 1, then we continue with levels 2; : : : ; L − 1, by iterating
vertically.
5.1.2.3. LocalOpt. This operation performs a neighborhood search by applying operations Moves
and Swaps. The nodes of a complete hierarchy level are chosen as the input node set for Moves and
Swaps. We can restrict operation LocalOpt to optimize the connections only between two adjacent
levels of the network, getting a level optimization. We can allow Moves and Swaps between two
nodes disregarding their level to achieve a thorough optimization. We have an option to restrict the
application of Moves and Swaps to particular aggregation trees separately.
Operation LocalOpt is used between the clustering steps of the improvement phase and it helps
to migrate nodes between clusters.
5.2. Algorithms for initial solution
We introduce three methods to construct initial solutions. First we present our algorithm called
Top-Down, which is built on operations Cluster and Tree. Then we give an initial solution, called
TreePlan, which adapts two existing approaches based on simulated annealing (TreePlan and
TreeMake algorithms, see [
18
,
19
]). Finally, a very fast initial solution, Random is given as ref-
erence. This algorithm may give an expensive solution because this is a randomized-greedy method
without any sophisticated optimization step. It was developed to analyze the performance of the
improvement phase.
5.2.1. Top-down
This top-down clustering algorithm /rst determines where and how many nodes should be in
level 1 in the network. It applies operation Cluster with special modular elements. Then it selects

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
71
some nodes to be at level 2, and so on, till it reaches the lowest level. The framework is the
following:
(1) Apply operation Cluster to divide the network into distinct aggregation tree areas. The medians
of the resulting clusters will be the root concentrator nodes of the evolving trees.
(2) Perform operation Cluster separately for each cluster formed in Step 1. This way, within each
tree, we get clusters and median nodes that will serve as second-level concentrators. We connect
the new medians to the corresponding parent median nodes (namely to the corresponding root
concentrators). Thus we have created the /rst two levels of the hierarchy.
(3) In the same way, compute concentrators in levels l = 3; : : : ; L − 1.
In operation Cluster, we compose the total cost of the network from two factors. The /rst factor is
the cost of the already planned parts. The second factor is the cost of the yet unknown remaining part,
which consists of the most recently determined clusters. In order to give a realistic approximation
of the second factor, we construct greedy trees from the nodes of these clusters by operation Tree
and temporarily extend the already planned parts with the new trees. The second factor will be the
cost of these temporary parts.
In operation Cluster, we apply the /rst type of allocation step and the relocation step presented
in operation Recluster. However, the optimization is done on a geometrical basis because the exact
aggregated tra3c values of the nodes are unknown at this point (these values are known only in the