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

√
P
i
=6:5
if P
i
6 1000
C
RBS=HUB
(i; t
i
):
BC
RBS=HUB
√
t
i
=2
if t
i
6 120
∞ otherwise
C
Li
(i; j; t
i
):
BC
Li
d
ij
√
t
i
if t
i
6 155
6.4. Robustness
The above tests showed that the proposed algorithm can successfully solve the presented network
planning problem for the given costs and constraints. We note that the structure of the optimal
network topology greatly depends on the ratio of the link and equipment costs. In order to examine
the robustness of the algorithm, namely how it works in di?erent environments, we tested the
algorithm for instances belonging to other problem classes. First we de/ned a special continuous
cost-function approximating the original one (see Section
4
). Next we examined the e?ect of changing
the number of levels in the trees and the maximal indegree of the nodes in each level. Finally we
considered the case when there was no distinguished root node in the equipment cost function. Four
sample networks are shown in Fig.
8
representing the solutions for the four di?erent cases. These
networks have the same input node set, only the connections between the nodes di?er from each
other, so one can easily recognize and compare the di?erences between them.
6.4.1. Continuous cost
The /rst special case is not to use discrete prede/ned equipment and links, but to apply continuous
equipment and link cost functions that approximate the cost values of the original discrete case as
shown in Table
4
.
We observed that the cost of the solutions found using continuous costs is always lower than in
the original case. This meets our expectations as the type of a RBS/HUB, RNC, link cannot be a
restrictive factor in this case. The shape of the trees converge to a minimal spanning tree, because it

---

78
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
(a)
(b)
(c)
(d)
Fig. 8. (a) Network solution with 400 nodes, original costs. (b) Continuous cost function. (c) Continuous cost function,
altered degree and level constraints. (d) No special root node costs.
has the lowest cost that could be found. Fig.
8
(b) shows an instance for this case with 400 nodes.
The quality of the di?erent approaches for this problem class is practically equivalent to the results
shown in Table
3
.
6.4.2. Modi?ed constraints
It is an interesting question how the algorithms react upon the modi/cation of the two main
constraints. Increasing the maximum number of levels in the tree and decreasing the maximum
indegree of the nodes bring a signi/cant change in the problem to be solved. Let L = 10 and
D
i
= 2; 2 6 i 6 L. In order to observe the impact of these constraints on the resulted network topol-
ogy we kept the above continuous cost functions. The Top-Down algorithm with Full-Iteration and
Alt-Iteration improvement methods gave the best results. However, TreePlan+Full-Iteration got

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
79
very close to them, but its running time was about four times larger than that of the Top-Down
method. The Random+Full-Iteration method yielded a similar network solution, but it was one
order of magnitude slower than the best ones. In this case the tree depth is larger (see
Fig.
8
(c)).
6.4.3. Equivalent nodes
Finally we assume that there is no distinguished root node. However, the equipment cost depen-
dence from the occupied level is kept. Now the cost of the nodes depends on their aggregated tra3c
and the occupied tree level. We simply divided the original RBS/HUB cost by the actual level of
the node and considered all nodes as an RBS/HUB. Now there is no di?erent cost for the roots
(RNCs). We decreased the maximum indegree of nodes in level 1 according to the other levels,
i.e., D
1
= 50. We expected that there would be much more /rst level nodes in the network resulting
many smaller trees. The tests met the expectations (see Fig.
8
(d)). In those areas where the density
of the nodes is higher, larger trees evolved, while in sparse areas very small trees have been created.
In the previous and this special case, applying the improvement algorithms is even more important,
since without these methods the initial solutions, especially TreePlan and Random, are much less
e?ective.
7. Conclusions and further work
This paper focused on cost-optimal hierarchical access network planning. This complex combina-
torial optimization problem is de/ned in a generalized way. It involves arbitrary link cost structures,
not only distance-based, but capacity-dependent cost components, as well. Moreover, equipment lim-
itations are taken into account and the costs of equipment can also have an arbitrary structure. The
problem has great signi/cance in the mobile telecommunications industry.
Due to the complexity of the problem and the size of practical instances, we propose a heuris-
tic algorithm. The idea is to combine clustering and local optimization operators and to apply the
combined operators iteratively within the levels of the hierarchy. For the individual operations, the
degree of complexity is adaptively adjusted runtime in order to provide a solution that is the best
one possible within the given time-frame. The method is con/gured for a trade-o? between so-
lution quality and running time; it can be used either to quickly obtain a low-quality solution (a
quick estimate for strategic decisions) or to /nd a near-optimal solution during a relatively longer
time.
Our empirical analysis showed that the proposed algorithm is robust and it meets all special
requirements of the problem statement. The method proved to be e3cient for practical network
planning purposes. The method can be used for extension planning of existing networks; any of the
links and nodes can be /xed by the user at the beginning. The method is independent from the cost
structure, therefore di?erent planning conditions and strategies can be supported.
We plan to use the approach for practical network planning support, especially for the challenging
area of GSM to 3G/UMTS transition. Our further research direction is to complete the presented
approach with core network planning algorithms to provide an overall solution for the planning
task.

---

80
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
Acknowledgements
The authors wish to thank J(anos Harmatos, L(aszl(o H(evizi, Alp(ar JUuttner, Zolt(an Kir(aly, Gyula
Sallai, (Aron Szentesi and the two anonymous referees for their valuable comments.
Appendix A. Procedure pseudocodes
A.1. Procedure Cluster (P; K
min
; l)
(1) (Initialize) Let C
best
=∞, denoting the cost of the overall best con/guration found. Let K =K
min
,
where K
min
is the minimal number of clusters to be formed from the set of input nodes P.
(2) (K-Loop) Initialize K median nodes M
j
from set P on level l randomly, and let each cluster
G
j
contain the selected median M
j
only, j = 1; : : : ; K. Let C
K
= ∞, denoting the best cost found
if using K medians.
(3) (Inner-Loop) Iterate the following steps while C
K
improves:
(a) Allocation: ∀i ∈ P, connect i to a chosen median M
j
, put i to G
j
, where M
j
is the median
of cluster G
j
, j = 1; : : : ; K.
(b) Relocation: ∀j = 1; : : : ; K, recompute the median M
j
in cluster G
j
.
(c) Cost-calculation: Compute the cost C
act
of the actual con/guration. If C
act
¡ C
K
, then let
C
K
= C
act
and save this con/guration as the best one found with K medians.
(4) (Update) If C
K
¡ C
best
, then C
best
= C
K
and store the found best con/guration with K medians
as the overall best con/guration.
(5) (Check) If C
best
has not improved during the last K
la
number of steps (K
la
is a look-ahead
parameter, set to a small value), then go to Step 6. Otherwise, let K = K + 1. If K 6 |P| − F,
then go to Step 2. (F denotes the number of nodes that are forbidden on level l.)
(6) (End) Return the overall best con/guration found.
A.2. Procedure Tree (P; root; l)
(1) (Initialize) Into set C we collect those already connected nodes of P, to which we can connect
other nodes of P without violating the topological constraints and without getting a network
with in/nite cost (due to equipment or link type violation). Initially let C = {root}. Let U be
the set of unconnected nodes of P, and initially let U = P \ {root}. Let C
P
denote the multiset
containing punished parents, let it be initially empty.
(2) (Loop) Select a set of candidate nodes S from U randomly, where |S| = min(|U|; q
samp
).
Parameter q
samp
denotes the /xed (small) sample size.
(3) (Find Best Parents) For all i ∈ S, /nd its possible best parent j ∈ C. That is, for all i ∈ S
select a parent j from C and denote it by p
i
for which the connection cost of i→p
i
is the
minimal possible. The connection has to ful/l the topological constraints (level, degree) and the
/xed/forbidden node limitations. Let the best connection cost found for node i ∈ S be denoted
by c
i
. If the actual cost of a connection between i ∈ S and j ∈ C during the search for the best
connection cost appears to be ∞ (forbidden because of constraints or costs), then put connected
node j ∈ C to C
P
.

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
81
(4) (Select Best) Find k ∈ S for which its best connection cost c
k
is minimal. If c
k
= ∞, then go
to Step 8.
(5) (Connect) Connect node k to its best parent p
k
. Remove k from U. If k is not placed at the
last tree level (L), then put k to C.
(6) (Punish Parents) If a node j ∈ C
P
has been punished m
p
times, then let C = C \ {j}. Parameter
m
p
speci/es the maximum number of greedy punishments and it is set to a rather small value.
(7) (Terminate) If U and C are both not empty, then go to Step 2. Otherwise, if U is empty, then
go to Step 9.
(8) (Failure) Return with notifying that the greedy tree construction has failed due to constraint or
cost violation.
(9) (Success) Return the con/guration that has been created.
A.3. Procedure Moves (C; P)
(1) (Initialize) The ordered set C holds the candidate nodes, and P holds the possible new parent
nodes. Initialize variables L
C
and L
P
to the /rst element of C and P, respectively. These working
variables mark the candidate and the parent nodes participating in the last successful move.
(2) (Loop) Let i be the /rst element of C and let j be the /rst element of P.
(3) (Check & Move) Check the possible move of node i to new parent j:
(a) Check the geometrical position of i and j. If i and j are relatively far (see Section
5.4
), go
to Step 4.
(b) Check constraints. If move i → j is not possible (e.g. i = j, or the degree/level constraints
would be violated, etc.), go to Step 4.
(c) Check the bene/t of the movement. Calculate the cost-di?erence between the old and the new
con/guration after the move. If it would not be a successful move (i.e., the cost increases),
go to Step 4.
(d) Accept move. Store the new con/guration. Let L
C
= i and L
P
= j.
(4) (Next Parent) If j is not the last element of P, advance j to the next element of P and go to
Step 6. Otherwise let j be the /rst element of P.
(5) (Next Candidate) If i is not the last element of C, then advance i to the next element of C.
Otherwise let i be the /rst element of C.
(6) (Terminate) If i=L
C
and j=L
P
, then stop and return the /nal con/guration. Otherwise continue
with Step 3.
A.4. Procedure Moves, cost-diBerence calculation in Step 3c
(1) (Initialize) Let k denote the original parent of i, where i is the examined node and j is the
possible new parent. Let B
old
denote the set of nodes above node i. Let B
new
contain node j
and the set of nodes above j. Let B
under
contain node i and the set of nodes in the tree-segment
under i. ‘Above’ and ‘under’ here means that there exists a path from the node upwards or
downwards in its tree to the particular node, respectively.
(2) (Original Cost) Calculate the cost of the links and equipment in B
old
and B
new
including the
cost of the outgoing link from i. Let the sum of them be denoted by C
orig
. If l
j
= l
k
, then add
the cost of elements in B
under
to C
orig
. (Refer to this case as Level-Change.)

---

82
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
(3) (New connection) Delete the connection from i to k and add a new connection from i to j.
Recalculate the amount of tra3c in B
old
(decrement) and in B
new
(increment). If Level-Change,
modify the levels of the nodes in B
under
according to the level-di?erence between the “parents”.
(4) (New Cost) Calculate the new cost C
new
according to Step 2.
(5) (Check & Accept) If C
orig
¿ C
new
, accept the new con/guration and Stop.
(6) (Failure) Restore the original connection between i and k. Restore the tra3c values. If Level-
Change, restore the original levels in B
under
.
A.5. Procedure Swaps (C)
(1) (Initialize) Let L
1
and L
2
be the /rst and second element of C, respectively. These working
variables mark the candidate node pair participating in the last successful swap.
(2) (Loop) Let i be the /rst and j be the second element of C.
(3) (Check & Swap) Check the possible swapping of node i and j:
(a) Check the geometrical position of i and j. If i and j are relatively far (see Section
5.4
), go
to Step 4.
(b) Check constraints. If swap i ↔ j is not possible (e.g. i = j, or the degree/level constraints
would be violated, etc.), go to Step 4.
(c) Check the bene/t of the swap operation. Calculate the cost-di?erence between the old and
the new con/guration after the swap. If it would not be a successful swap (i.e., the cost
increases), go to Step 4.
(d) Accept swap. Store the new con/guration. Let L
1
= i, L
2
= j.
(4) (Next-j) If j is not the last element of C, then advance j to the next element of C and go to
Step 6. Otherwise let j be the /rst element of C.
(5) (Next-i) If i is not the last element of C, then advance i to the next element of C. Otherwise
let i be the /rst element of C.
(6) (Terminate) If i =L
1
and j =L
2
, then stop and return the /nal con/guration. Otherwise continue
with Step 3.
A.6. Procedure Recluster(r; m
alloc
, m
locopt
)
(1) (Select Nodes) Build up node set P to be clustered according to r: