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

• (Case1) 1 6 l ¡ L: C = {i ∈ P
i
; l
i
= l + 1}. P = {i ∈ P
i
; l
i
= l}.
• (Case2) l = L, that is, we choose the leaf nodes.
Let C = {i ∈ P
j
: l
i
= L ∨
v
∈P
i
x
vi
= 0}. Let P = P
i
.
• (Case3) l = L + 1: All node pairs. Let C = P = P
i
.
• (Case4) l = L + 2: This case is the same as Case3, but here we skip the checking of the
geometrical position of the selected node pairs in the Moves and Swaps procedures (cf. Steps
3 of them).
(4) (Local Optimization) Perform Moves(C; P) and then Swaps(C).
A.9. Procedure Top-Down-IniSol(N)
(1) (Initialize) Let l = 1 denote the actual level of the network to be constructed. Let G denote the
set of clusters to be processed and initially let G = {N}. Let H denote a set of clusters and
initially let H = ∅.
(2) (Loop) In order to assign nodes to level l, ∀G
i
∈ G do:
(a) (Calculate K
min
) Calculate K
min
depending on the number of nodes in G
i
, number of ?xed
nodes at level l in G
i
, and the degree and level constraints.
(b) (Clustering) Perform Cluster(G
i
; K
min
; l). Put the resulting clusters to H. If l ¿ 1, connect
all new medians M
j
(found by Cluster in G
i
) to the median of cluster G
i
that was found
at the previous level.
(3) (Next Level) Let G = H and let H = ∅. Let l = l + 1. If l 6 L, then go to Step 2, otherwise
Stop.
Top-Down-IniSol applies the following sub-procedures in Step 3 of Cluster:
(a) (Allocation) As the exact costs of allocations are not known, the allocation decision is done on
the shortest distance basis: ∀i ∈ P /nd the median M
j
(j = 1; : : : ; K) that is the closest to node
i, i.e., d
iM
j
is minimal (see Eq. (
12
)). Put i to G
j
, where G
j
is the jth cluster.
(b) (Relocation) Again, as the exact costs of the clusters are not known, the cluster center relocation
is done on a geometrical basis. ∀j =1; : : : ; K /nd a new median M
j
in cluster G
j
: calculate Geo
j
denoting the geometrical center of G
j
, by averaging the (X; Y ) coordinates of the nodes in G
j
.
Then /nd i ∈ G
j
that is the closest to Geo
j
, and let new median M
j
= i.
(c) (Cost-calculation) ∀j set M
j
to be in level l and perform Tree(G
j
; M
j
; l). If l ¿ 1, then tem-
porarily connect all M
j
to the corresponding median in level l − 1. Finally calculate the cost of
the resulted network con/guration according to Eq. (
1
) (see Problem de/nition).
A.10. Procedure Random-IniSol (N)
(1) (Initialize) Select a random node i ∈ N for being at level 1, let the set of connected nodes
C = {i}, and let the set of unconnected nodes U = N \ C. Let the multiset of punished nodes
C
P
be empty.
(2) (Loop) Select a random j ∈ U. Let the number of trials q = 0.

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
85
Table 5
Full-iteration-improvement
Advance loop
1
2
3
4
5
6
7
8
9
10
m
alloc
1
1
1
1
2
2
2
2
2
2
m
locopt
0
1
2
3
1
2
3
3
3
3
ByRoots
1
1
1
1
1
1
1
1
0
0
(3) (Parent Search) While q does not exceed 2 · |C| repeat the following: Select a random parent
k ∈ C and let q = q + 1. Try to connect node j to k. If the resulting cost is valid and the
connection does not violate any constraint, then perform the connection, take out node k from
C if it reached its degree constraint, and go to Step 5. Otherwise, if connecting j to k is not
valid, punish node k: put k to C
P
. If the total number of punishments for node k exceeds a
(small) limit, take out k from C.
(4) (New Root) If no k satisfying the above conditions was found, let node j be at level 1. (If j
is forbidden at level 1, choose another random j ∈ U, which is allowed to be at level 1.)
(5) (End) Take out j from U. Put j to C if it is not at the lowest allowed level. If U is not empty,
then go to Step 2.
A.11. Procedure Full-Iteration-Improvement (N, UseClu, UseLoc)
(1) (Initialize) Let C
act
, C
best
denote the actual cost, the best cost found, respectively, and let both
be initially equal to the cost of the network planned by the initial solution. Let A = 1 assign a
column of Table
5
.
(2) (Advance Loop) Set the parameters of ReclusterLevel and LocalOpt according to the column
A of Table
5
. In the row of parameter ByRoots, 1 denotes TRUE and 0 denotes FALSE.
(3) (Level Loop) Sequentially for each level l = 1; : : : ; L do:
(a) (ReclusterLevel) If UseClu ∧ l ¡ L, then perform ReclusterLevel(l − 1; m
alloc
; m
locopt
).
(b) (LocalOpt) If UseLoc ∧ A ¿ 7, then perform LocalOpt(l; ByRoots).
(4) (Extra LocalOpt1) Calculate C
act
. If C
act
¿ C
best
(1 − I) ∧ UseLoc, perform LocalOpt(L +
1; ByRoots) and calculate C
act
. I ∈ (0; 1)1 is a minimal improvement threshold parameter.
(5) (Check Cost) If C
act
¡ C
best
(1 − I), let C
best
= C
act
and go to Step 3.
(6) (Extra LocalOpt2) If A ¿ 9 ∧ UseLoc, perform LocalOpt(L + 2; FALSE). Recalculate C
act
.
(7) (Termination) If A 6 9, let A = A + 1. If C
act
¡ C
best
∨ A 6 9, let C
best
= C
act
and go to
Step 2. Otherwise stop, return the actual solution.
The parameters are changing according to the scheme presented in Table
5
.
References
[1] Daskin MS. Network and discrete location. New York: Wiley; 1995.
[2] Drezner Z, editor. Facility location. A survey of applications and methods. New York: Springer; 1995.

---

86
I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
[3] Gupta R. Problems in Communication Network Design and Location Planning; New Solution Procedures. PhD thesis,
The Ohio State University, 1996.
[4] Lo CC, Kershenbaum A. A two-phase algorithm and performance bounds for the star-star concentrator location
problem. IEEE Transactions on Communications 1989;37(11):1151–63.
[5] Narasimhan S, Pirkul H. Hierarchical concentrator location problem. Computer Communications 1992;15(3):185–91.
[6] Pirkul H, Gupta R. Topological design of centralized computer networks. International Transactions in Operational
Research 1997;4(1):75–83.
[7] Schneider GM, Zastrow MN. An algorithm for the design of multilevel concentrator networks. Computer Networks
1982;6(1):1–11.
[8] Soltys JR, Fischer MJ, Roth BD. Optimizing access to service based networks. Telecommunication Systems,
Modeling, Analysis, Design and Management 1998;10(3–4):269–90.
[9] Klincewicz JG. Hub location in backbone/tributary network design: a review. Location Science 1998;6:307–35.
[10] Minoux M. Network synthesis and optimum network design problems: models, solution methods and applications.
Network 1989;19:313–60.
[11] Brittain D. Optimisation of the Telecommunications Access Network. PhD thesis, University of Bristol, 1999.
[12] Anandalingam G, Friesz TL, editors. Hierarchical optimisation. Annals of Operations Research 1992;34:1–11.
[13] Eitan Y, Narula SC, Tien JM. A generalized approach to modeling the hierarchical location-allocation problem. IEEE
Transactions of Systems, Man, and Cybernetics 1991;21:39–46.
[14] Mateus GR, Cruz FRB, Luna HPL. An algorithm for hierarchical network design. Location Science, 1994;2:149–64.
[15] Mirchandani PB. Generalized hierarchical facility location. Transportation Science 1987;21:123–25.
[16] Serra de la Figuera D, ReVelle CS. The pq-median problem: location and districting of hierarchical facilities.
Location Science 1993;1:299–312, 1994;2:63–82.
[17] Weaver JR, Church RL. The nested hierarchical median facility location model. INFOR 1991;29:100–15.
[18] Harmatos J, JUuttner A, Szentesi (A. Cost-based UMTS transport network topology optimisation. Proceedings of the
International Conference on Computer Communications’99, 1999, Tokyo.
[19] Harmatos J, Szentesi (A, G(odor I. Planning of Tree-Topology UMTS Terrestrial Access Networks, PIMRC 2000,
London, September 2000.
[20] Kallenberg P. Optimization of the /xed part of GSM networks using simulated annealing. Proceedings of the
Networks’98, 1998, Sorrento, Italy.
[21] Kim MJ, Kim SB, Ryu KH. The capacitated hierarchical p-median problem for facility locations of PCS networks.
Proceedings of the Fourth International Conference on Telecommunications Systems, 1996, Nashville, TN.
[22] Aarts EHL, van Laarhoven PJM. Simulated annealing: theory and applications. Dordrecht: Kluwer Academic
Publishers; 1987.
[23] Balakrishnan A, Altinkemer K. Using a hop-constrained model to generate alternative communication network
designs. INFORMS Journal of Comput. 1992;4:192–205.
[24] Gavish B. Topological design of telecommunication networks—local access design methods. Annals of Operations
Research 1991;33:17–71.
[25] Gavish B. Topological design of telecommunication networks—the overall design problem. European Journal of
Operations Research 1992;58:149–72.
[26] The UMTS-Forum.
http://www.umts-forum.org
.
[27] Laiho L, Wacker A, Novosad T. Radio network planning and optimisation for UMTS. New York: Wiley; 2002.
[28] Jain A, Dubes R. Algorithms for clustering data. Englewoods Cli?s, NJ: Prentice-Hall; 1988.

---