# Test Center Location Problem: A Bi-Objective Model and Algorithms
## 4 Solution Approach for Test Center Location Problem
### A Local Search Approach for the TCLP
In this case, we employ a _crowding operator_ to select a diverse ensemble of non-dominated solutions. Various approaches exist for reaching diversity among the solutions [28; 29]. As an example, we first normalize the objective values and initiate by selecting two extreme solutions, those with the minimum \(F_{1}\) and minimum \(F_{2}\) values, incorporating them into \(Pop_{t+1}\). Following this, we proceed to determine the largest axis-aligned bounding box that encompasses each solution while ensuring that no other solution is contained within it. We select the \(N-2\) solutions that have the largest bounding boxes and incorporate them into \(Pop_{t+1}\). This approach can be easily implemented by sorting the solutions based on their objectives. Consequently, it requires a time complexity of \(O(Nk\log(kN))\). Therefore, TCLA initiates its process with an initial random population and then proceeds to generate a new population through the utilization of the Voronoi exchange operator. From these populations, it selects the non-dominated solutions to be carried forward into the subsequent generation. These steps are reiterated for a specified number of iterations to accomplish its optimization objective. The pseudocode for TCLA is presented in Algorithm 1. The time complexity of this algorithm for one iteration is \(O(Nkn\log k)\) for evaluating the solutions using their corresponding Voronoi diagram, plus \(O(Nk\log(Nk))\) if the crowding operator is needed. It is worth noting that, we utilize the Voronoi diagram for a dual purpose: to ascertain the neighbors of a given solution and to expediently calculate the objective values associated with a solution. The number of Voronoi neighbors pertaining to a solution may exhibit variability, ranging from 2 to \((k-1)\). Nevertheless, the average number of Voronoi neighbors is constant. Additionally, the overall number of neighbors remains linear (\(\leq\)3k). The assessment of a solution can be achieved through a brute-force algorithm in \(O(nk)\) time; however, by employing the Voronoi diagram and performing the nearest point query, this process can be improved to \(O(n\log k)\) time complexity [34]. TCLA, like all population-based heuristics, requires two predefined parameters: the size of the population (\(N\)) and the number of iterations. Remarkably, TCLA stands out by not requiring any additional parameters. In contrast, many heuristic algorithms necessitate a multitude of parameters, including crossover rate, mutation probability, and learning weights, among others [29]. We firmly believe that in FL problems, particularly in the case of large instances, the Voronoi diagram plays a crucial role in efficiently achieving a balance between exploration and exploitation concepts within the search space. The Voronoi partition of the space serves as a valuable tool for distributing the combinatorial complexity of the problem into localized complexities. ```
0: Sets \(P\) and \(Q\), distance function (or matrix \(d_{ij}\)) and the integer number \(k\)
0: Set of non-dominated solutions for the TCLP
1: Set the size of population to \(N\), and number of generations to \(T\)
2: Initialize population \(Pop_{0}\) with \(N\) random solutions like \(C=\{c_{1},c_{2},...,c_{k}\}\)
3: For any solutions \(C\in Pop_{0}\), compute Voronoi diagram of \(C\), denoted by \(VD(C)\), and then evaluate their objective values, \(F_{1}(C)\) and \(F_{2}(C)\)
4:for\(t=0\)to\(T-1\)do
5: For any solutions \(C\in Pop_{t}\), apply \(VD(C)\) and the Voronoi exchange operator and reproduce \(k\) neighbor solutions. Put the new generated \(Nk\) solutions in temp a population \(TPop\)
6: Remove the duplicated solutions in \(TPop\)
7: For any solution \(C^{\prime}\in TPop\), compute \(VD(C^{\prime})\), \(F_{1}(C^{\prime})\) and \(F_{2}(C^{\prime})\).