# Solution Algorithms for the Capacitated Location Tree Problem with Interconnections
## 5 Computational Experiments  
To test the performance of the proposed solution algorithms (EM, BRKGA, and PSO), 36 test instances from the literature were used. These test instances were proposed to the LRP and can be found at [[http://prodhonc.free.fr/Instances/instances_us.htm](http://prodhonc.free.fr/Instances/instances_us.htm)]([http://prodhonc.free.fr/Instances/instances_us.htm](http://prodhonc.free.fr/Instances/instances_us.htm)) (accessed on 16 January 2025). These instances were chosen because their characteristics are applicable to the CLTPI. The size of the test instance ranged from 20 to 200 clients, and there were 5 to 10 potential facilities. The names of the test instances reflected the number of clients (first number) and the number of potential facilities (second number). The EM was developed in C++ Ubuntu 13.3.0 using GUROBI 9.1.1 as the solver. The BRKGA and PSO algorithms were also developed in C++ Ubuntu 13.3.0. All the experiments were run on a PC with an AMD Ryzen 9 3950 processor at 3.5 GHz with 16 cores and 64 GB of RAM. Tables 2-4 show, respectively, the results of the exact algorithm (Formulation), BRKGA, and PSO using the benchmark test instances. The EM was run just once (the algorithm was deterministic), while the BRKGA and PSO were run five times for each test instance. For the EM, a maximum solution time of 72,000 s was defined. A comparison of the best solutions obtained by each solution algorithm and the average time required to find it is presented in Table 5.  
For the BRKGA, the following parameters were used:  
* \(L=50\), the number of populations used;
* \(pe=0.25\), the percentage of elite elements in each population;
* \(pm=0.10\), the percentage of mutants introduced in each population after crossover;
* \(Th=1.32\) the number of threads to be used (parallel computing);
* \(ItEx=40\), the number of iterations between exchanges of elite solutions among populations;
* \(ElitetoEx=1\), the number of elite solutions to exchange;
* \(\rho=0.65\), the probability that offspring inherits the vector component of its elite parent;
* \(ItStop=350\), the number of iterations without improvement in the BRKGA stopping criterion. For the PSO, the following initial parameters were used:  
* \(L=224\), the number of particles used;
* \(c_{1}=[2,1.496]\), the acceleration coefficient towards the global best solution _Gbest_;
* \(c_{2}=[2,1.496]\), the acceleration coefficient towards the particles' best solution _Pbest_;
* \(w=[0.7928,0.7578]\), the percentage of mutants introduced in each population after crossover;
* \(ItStop=350\), the number of iterations without improvement in the stopping criterion. Note that the parameters \(c1\), \(c2\), and \(w\) were modified every iteration when no new best solution was found. In Table 2, column **Instance** gives the name of the test instance, while columns **UB** and **LB** show, respectively, the upper and lower bounds obtained by the EM. Column **Gap** shows the percentage deviation between the UB and LB, and **T16** shows the elapsed time used by the EM. For Tables 3 and 4, column **Instance** gives the name of the test instance, while columns **Best**, **Mean**, and **Worst** show, respectively, the best, the mean, and the worst value found by the corresponding algorithm after five runs. Columns **T1** and **T16** show the average time using one and sixteen CPU cores during five runs with the algorithms. Column **S(16)** shows the speedup of the parallel program using 16 CPU cores. The speedup was computed using  
\[S(16)=\frac{\text{T1}}{\text{T16}}.\]Finally, column \(\sigma\) shows the objective function's standard deviation for each instance after five runs. The results in Table 2 show that the exact algorithm could find near-optimal solutions with gaps of less than 1% for instances with up to 100 clients except for the instance \"coord100-10-3.dat\". However, for instances with 200 clients, the results were poor, with gaps between 23.14% and 54.62%.