# 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  
One of the key factors in the success of heuristic and local search algorithms is the way that they generate a new solution using the obtained solutions in each iteration. The other factor is striking a balance between exploration and exploitation power. Considering these two factors, in this section, we propose a customized local search algorithm for the TCLP. We call this algorithm the _Test Center Location Algorithm_ and denote it by TCLA. This algorithm is a population-based heuristic algorithm that regenerates solutions by leveraging Voronoi neighbors. This regeneration method is called the _Voronoi exchange operator_ and ensures the gradual reproduction of new generations through an exchange operator, avoiding abrupt changes akin to the \"mutation\" process in genetic algorithms. Instead, it explores the search space in multiple directions facilitated by Voronoi analysis. In terms of exploitation, the population is updated using a \"non-domination\" comparison criterion. This entails retaining solutions that are non-dominated concerning the current population. In a bi-objective problem, a solution \(C\) is said to _dominate_ a solution \(C^{\prime}\) if it is better in at least one objective and not worse in the other objective. In cases where the number of such non-dominated solutions exceeds the population's capacity, a crowding operator such as a basic clustering technique is employed to select the most diverse non-dominated subset. The following sections will delve into the specifics of this process. In a preprocess, we first compute Voronoi neighbors of each potential facility center, set \(Q\). This can be performed in \(O(mlogm)\) time [34]. Likewise, the nearest center to a given demand point can be determined in \(O(\log m)time\). Let \(Vor(q)\) denote Voronoi neighbors of each center \(q\in Q\) in the Voronoi diagram. For a solution \(C=\{c_{1},c_{2},\ldots,c_{k}\}\subset Q\) for the TCLP, a random solution \(C^{\prime}\) can be generated by the following Voronoi exchange operator. We choose a center \(c\in C\) and replace it with a random center \(c^{\prime}\in Vor(c)\). This Voronoi exchange operator can be applied for all centers, generating \(k\) new random solutions. Since the evaluation process, which involves computing \(F_{1}(C)\) and \(F_{2}(C)\), is computationally expensive, we identify and remove repeated solutions before computing the objective values. Now, let's elucidate the functioning of the entire local search algorithm. We commence with the assumption of a population denoted as \(Pop_{t}\) (i.e., for \(t=0\) in the beginning), possessing a size of \(N\), and initialize it with random solutions like \(C=c_{1},c_{2},\ldots,c_{k}\). Subsequently, we conduct an evaluation of these solutions, calculating their respective objective values, \(F_{1}\) and \(F_{2}\). This evaluation process demands \(O(k\log k+n\log k)\) time for an individual solution \(C\) by leveraging the Voronoi diagram of \(C\) and identifying the closest center for each demand point. In the next step, we employ the previously described Voronoi exchange operator to generate \(k\) random solutions for every solution within the population, totaling \(kN\) solutions in entirety. Following the removal of duplicated solutions and the computation of objective values for these generated solutions, we execute a non-dominated sorting, which identifies all non-dominated solutions within \(O(kN\log(kN))\) time [35]. In the final phase, we select non-dominated solutions from the union of \(Pop_{t}\) and the newly generated solutions and construct \(Pop_{t+1}\) with \(N\) solutions. Two cases may happen, if the number of non-dominated solutions is less than \(N\), we fill \(Pop_{t+1}\) with the second level of non-dominated solutions. That is the non-dominated solutions after removing the first level. We repeat this process to fill \(Pop_{t+1}\) with \(N\) solutions. The second case happens if the number of non-dominated solutions exceeds \(N\).