# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 5 Computational Experiments
Again, the results show that using multiple threads significantly reduced the average elapsed time needed to solve the CLTPI instances. For the PSO, on average, using sixteen CPU cores was 7.96 times faster than using one CPU core. The best reduction in the running time was achieved, for instance, by \"coord100-5-1b.dat\", where the PSO was 10.66 times faster when using sixteen CPU cores instead of one CPU core. The maximum average running time using 16 CPU cores was 12.20, for instance, with \"coord200-10-2b.dat\". Therefore, it can be assumed that the computational effort used by the PSO was lower than the BRKGA. On the other hand, the PSO also showed good precision for all instances, with an average variance of 12.15. The quality of the solutions, considering the best solution found by the PSO, will be discussed later in this section. For the BRKGA and PSO, the speedup results are presented graphically in Figures 5 and 6. The BRKGA had a better speedup (8.10) than the PSO (7.96) when using 16 CPU cores. However, the PSO still had shorter solution times than the BRKGA. The reason was that  
\begin{table}
\begin{tabular}{l r r r r r r r} \hline
**Instances** & **Best** & **Mean** & **Worst** & **T1** & **T16** & \(S(\mathbf{16}  
iterations in the PSO were faster than in the BRKGA. The BRKGA took more time in each iteration due to the crossover operation. The efficiency of parallelization was around 50% for both algorithms. This efficiency was low due to the repeatability feature included in both algorithms. This means the algorithms had to return the same solution for a single given seed. To achieve the repeatability feature, the random numbers used in each iteration (in both algorithms) were generated using a single core, reducing the overall parallelization efficiency. The repeatability feature was lost if the generation of random numbers in each iteration was parallelized. Table 5 compares the results of the three proposed solution algorithms. Column **BKS** presents the best-known solution for each instance, while columns **Gap** present the percentage of variation concerning the best solution found by each algorithm with the LB found by the EM. Values in bold in these columns indicate that the corresponding algorithm found the best-known solution. Finally, **T16** shows the elapsed time when using 16 CPU cores with the EM, PSO, and BRKGA solution algorithms. Regarding the best-known solutions, the EM algorithm reached the best-known solutions for 29 of the 36 benchmark instances, while the PSO reached the best-known solution for 7 of the 36 benchmark instances. The BRKGA did not reach any best-known solution. The results show that the EM algorithm found the best solutions for all instances with up to 100 clients (see Figures 7 and 8), except for \"coord100-10-3b.dat,\" where the PSO obtained the best-known solution. The PSO obtained all the best-known solutions in the group of instances with  
Figure 5: Speedup for instances with at most 50 vertices. Figure 6: Speedup for instances with 100 vertices or more. 200 clients. The EM obtained poor results for instances with 200 clients with gaps between 30.10% and 120.35%, which were huge. The EM required much more computational effort than the BRKGA and PSO. Its average time was 5221.63 s, far greater than the 4.46 and 3.25 s used by the BRKA and PSO, respectively. The PSO obtained the lowest average gap with 1.50, the BRKGA's was 1.54, and the EM's was 9.96. The PSO and BRKGA found better solutions for large instances than the EM because the complexity of the PSO and BRKGA did not grow exponentially as it did for the EM.