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

√
0.02
0.01
√
√
0.23
√
0.04
Top-Down+Loc-Iteration
0.61
12.75
5.89
7.72
6.63
10.37
13.41
8.2
Top-Down+Clu-Iteration
0.78
1.38
1.58
1.86
2.35
2.32
3.15
1.92
Top-Down+Alt-Iteration
0.13
0.09
√
0.01
0.18
√
0.25
0.09
TreePlan+Full-Iteration
0.34
√
0.55
0.47
1.06
0.45
0.6
0.5
Random+Full-Iteration
0.61
0.6
1.27
1.06
1.23
1.12
0.64
0.93
Top-Down
3.98
17.51
12.69
15.92
15.91
18.81
23.77
15.51
TreePlan
4.14
8.51
10.37
17.93
20.56
18.16
20.33
14.29
Random
54.49
73.39
135.66
168.38
187.72
218.87
247.7
155.09
7.72 in column ‘n = 500’ means that the Top-Down+Loc-Iteration algorithm provided a solution,
which is 7.72% worse on average than the best one that is obtained by the Top-Down+Full-Iteration
algorithm (
√
). The last column of the table includes the averages of the rows. The Top-Down initial
solution with the Full-Iteration or Alt-Iteration improvement method provided the best solutions, but
their di?erence is not signi/cant. The results of TreePlan+Full-Iteration and Random+Full-Iteration
methods are a little bit worse. The Top-Down+Clu-Iteration and Top-Down+Loc-Iteration methods
are relatively farther from the best result found, roughly 2% and 8%, respectively. We conclude
that the best methods combine clustering and local optimization (Full-Iteration or Alt-Iteration
variants), and the ones that use the Top-Down initial solution provide slightly better results. Adding
the observation that these latter variants are also quicker, they seem to be a good choice. The results
of the initial solution methods alone are modestly farther from the best result found, by roughly
15–20%, except for the extremely far Random initial solution, which is much worse.
An illustrative investigation was performed with solving 50 random instances for n = 500, and
tracking the improvement of the average solution quality over time (see Fig.
7
). The /gure is divided
into two parts along the time-axis. The /rst part shows the beginning 100 s, while the second part
shows how the algorithms converge to their /nal solutions. In this latter part the cost-axis is focused
to the range where the curves converge. Beyond 100 s running time, Top-Down initial solution with
Full-Iteration and Alt-Iteration improvement methods give the best solutions. In the beginning,
Top-Down+Clu-Iteration without Loc-Iteration is the best, but after approx. 100 s we have to use
it together with Loc-Iteration to be able to improve the solution. It makes almost no di?erence to
choose Full-Iteration or Alt-Iteration to combine the clustering and local improvement methods.
Algorithms using only Clu-Iteration or Loc-Iteration stop their operation quickly, and /nally they
lag behind the complex improvement methods. Random+Full-Iteration and TreePlan+Full-Iteration
give slightly worse results than Top-Down+Full-Iteration, moreover, their results are always above
the best ones.
To summarize, we suggest to use Clu-Iteration improvement after our Top-Down initial solution
to solve hierarchical access network planning problems if the running time is critical. Depending
on the available time and the size of the instance, Clu-Iteration can be applied in itself or the
Full-Iteration or Alt-Iteration improvement can be used to /nd even better solutions.

---

I. G-odor, G. Magyar / Computers & Operations Research 32 (2005) 59–86
77
0
25
50
75
100
time [sec]
23000
25000
27000
29000
cost
Top-Down + Full-Iteration
Top-Down + Loc-Iteration
Top-Down + Clu-Iteration
Top-Down + Alt-Iteration
TreePlan + Full-Iteration
Random + Full-Iteration
100
200
300
400
500
600
time [sec]
23000
24000
25000
cost
Top-Down + Full-Iteration
Top-Down + Loc-Iteration
Top-Down + Clu-Iteration
Top-Down + Alt-Iteration
TreePlan + Full-Iteration
Random + Full-Iteration
Fig. 7. Algorithm comparison (500 node instances).
Table 4
Equipment and link costs
C
RNC
(i; t
i
):
BC
RNC