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

∞
otherwise
∞
otherwise
from the RBSs and they are given extended functionality. However, the optimal number of RNCs
and HUBs are not given. The tra3c can have a complex daily pro/le, but for the sake of simplicity,
we model the input tra3c in each RBS by a constant T
i
∈ R (∀i ∈ N). To summarize, the input
and the constraints are as follows:
• Nodes: RBSs with their geographical location (X
i
; Y
i
); ∀i ∈ N;
• Tra3c: T
i
∈ R; ∀i ∈ N;
• The maximum number of levels is L = 5;
• The maximum indegrees for the concentrator nodes at each level:
D
1
= 200 for the RNCs, and D
i
= 50, i = 2; : : : ; L − 1 for the HUBs.
Next we describe the applied cost functions. The cost model is arti/cial, but it models the typical
characteristics and complexity of the real situation. We have three ‘base cost’ parameters, for link,
RBS/HUB and RNC costs. The base cost multiplied with a tra3c-dependent factor gives the actual
cost of the particular equipment or link. The base costs are:
• BC
Li
= 1, BC
RNC
= 1000 and BC
RBS=HUB
= 5.
The equipment cost C
Eq
(i; l
i
; t
i
) depends on i; l
i
; t
i
; we di?erentiate two types of equipment costs:
one for RNCs and another for HUBs and ordinary RBSs. The /rst is the C
RNC
(i; t
i
), which depends
on the number of signal processors needed (P
i
) to control the attached RBSs and manage the tra3c.
The number of needed signal processors is approximated by a linear function of the number of RBSs
(n
i
) in the tree rooted at RNC i and the total aggregated tra3c t
i
: P
i
= L(n
i
; t
i
). In our model, we
involve /ve di?erent types of RNC equipment with varying number of signal processors. The RNC
cost depends upon the needed number of signal processors. The second type of equipment cost is
the C
RBS=HUB
(i; t
i
), standing for single RBSs and HUBs, which cost depends on the (aggregated)
tra3c passing through the node. In our model we have /ve RBS/HUB equipment types. Table
1
shows both equipment costs.
To sum up the equipment costs we get the following:
C
Eq
(i; l
i
; t
i
) =

C
RNC
(i; t
i
)
if l
i
= 1;
C
RBS=HUB
(i; t
i
) if l
i
¿ 1:
(11)
Finally, the link cost C
Li
(i; j; t
i
) depends on the length of the link and on the tra3c that it carries.
The length d of a link is the physical distance between the two endpoints i; j of the link, and we

---

66
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
Table 2
Link costs
C
Li
(i; j; t
i
):
6 d
ij
BC
Li
if 34 ¡ t
i
6 36
1 d
ij
BC
Li
if t
i
6 2
7 d
ij
BC
Li
if 36 ¡ t
i
6 42
2 d
ij
BC
Li
if 2 ¡ t
i
6 8
8 d
ij
BC
Li
if 42 ¡ t
i
6 44
3 d
ij
BC
Li
if 8 ¡ t
i
6 10
9 d
ij
BC
Li
if 44 ¡ t
i
6 50
4 d
ij
BC
Li
if 10 ¡ t
i
6 16
10 d
ij
BC
Li
if 50 ¡ t
i
6 155
5 d
ij
BC
Li
if 16 ¡ t
i
6 34
∞
otherwise
use 10 di?erent link types depending on the bandwidth of the link (see Table
2
):
d
ij
=

(X
i
− X
j
)
2
+ (Y
i
− Y
j
)
2
:
(12)
It is straightforward to take existing equipment into consideration in the equipment cost function,
i.e., for certain nodes the cost of equipment in that node can be forced to be less expensive, if there
is some previously deployed equipment, for instance, nodes from a GSM network, etc. Similarly,
one can take existing links into account to get a less expensive network con/guration. There can be
di?erent types of links available (microwave, optical, etc.) depending on the strategic decisions of
the network operator. These can also be taken into account in the chosen link cost function. Other
kind of exceptions such as a river between nodes i and j prohibiting the installation of a given
type of link can also be embedded in the cost function. There can be previously ?xed or forbidden
equipment and/or links in the network to be planned. Fixed equipment means that a node should
be placed in a given level (e.g. /xed at level 1 ⇒ there must be an RNC in that node). Forbidden
equipment means the opposite. A /xed link means that we must take this link into consideration
when we calculate the cost of a new link. A forbidden link means that the cost of a link between the
given nodes is ∞. It is very important to model the real-world network planning situations by the
use of existing, /xed or forbidden equipment/links and further exceptions. The proposed algorithms
can handle and support all the above special features of the model.
5. Algorithm
We use a two-phase heuristic planning algorithm. In the /rst phase, we construct an initial
network-solution and in the second phase, we improve it. Our initial solution ful/ls every con-
straint and limitation, therefore it can be used as it is. It is enough to give us an overall information
about how many nodes should be in certain hierarchy levels and let the improvement phase /nd
better interconnections between the nodes. We present three algorithms for constructing an initial
solution including a new algorithm called Top-Down. Once we have the initial solution, we continue
with the powerful and much more time-consuming improvement phase, see algorithm Full-Iterate.
Our approach /nds low cost connections and suitable hierarchy level for each node. We iterate the
improvement steps until no further improvements are found.
To describe our algorithm, we de/ne basic operations (or operators). The initial solution is built
with these basic operations, which also constitute the basis of compound operations. The compound
operations are used in the improvement phase. The complexity of the compound operations is adjusted
adaptively, where the adjustment is based on the actual performance of the algorithm. Such a way,

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
67
a) Set the complexity of
the compound opera-
tions to the minimum.
b) Set level 
l = 1.
a) If the improvement
rate is too low then
advance complexity.
b) Set level 
l = 1.
a) Recompute the number and the position of
concentrator nodes in level 
l.
b) Optimize connections between level l and l + 1.
c) 
l := l + 1
If the solution is improved or
the complexity can be advanced.
l < L
Improve connections between any two of the nodes.
End
Start
Set level 
l = 1.
a) Choose concentrators to be in level l
and consider them as connected.
b) Allocate the unconnected nodes to
these concentrators.
c) 
l := l + 1
l < L
yes
no
yes
no