# Test Center Location Problem: A Bi-Objective Model and Algorithms
## 1 Introduction  
The purposeful allocation of facilities, which includes the selection of examination centers, has undergone thorough scrutiny spanning various fields, including operations research, geography, and transportation planning. In particular, facility location (FL) problems within the context of healthcare systems have garnered significant attention due to their practical implications in enhancing healthcare delivery. These problems involve determining strategic locations for healthcare facilities such as hospitals, clinics, and medical centers to serve a given population while considering various factors, including geographical distribution of population, patient demand, resource constraints, and cost considerations. One of the recent challenges in this area was finding optimal locations for testing centers during the COVID-19 pandemic. As observed by many people worldwide in recent times, crowded conditions not only prolong waiting times in testing queues for individuals but also lead to increased chances of viral transmission. Hence, when increasing the number of test centers is not possible (e.g., due to resource constraints), the strategic organization and placement of these facilities assume paramount importance. This problem entails a delicate trade-off between two essential objectives. Firstly, it is imperative to minimize the traveling distance between individuals seeking testing and their nearest testing center, thereby reducing their associated travel time costs. On the other hand, in order to mitigate the risk of infection and ensure efficient service delivery, it is equally crucial to achieve an equitableworkload distribution across these centers. Striking this balance should significantly contribute to the effective management of these facilities, fostering a fair distribution of responsibilities among them. In light of two fundamental real-world considerations, namely, the tendency of individuals to select the closest available center and the constraints imposed by a limited number of such testing centers, the overarching objective became clear. The goal is to strategically deploy a limited (say \(k\) centers) set of test centers with the dual purpose of minimizing the distance between individuals and their closest test center, while concurrently minimizing the differences in workload among the test centers. In this paper, we consider clusters of individuals as weighted demand points, analogous to the population residing in an apartment complex, in conjunction with a predefined set of potential locations for establishing test centers. Consequently, the problem at hand entails the selection of \(k\) potential center locations, wherein two key objectives are pursued: (_i_) the attainment of maximum balance among the workloads of the centers, specifically minimizing the disparity between the highest and lowest workloads, and (_ii_) the minimization of the average traveling time for the demand points. We name this particular FL problem the _test center location problem_ and denote it by TCLP. It is pertinent to note that solving either of the objectives in the TCLP is an NP-hard problem. The first objective, often referred to as the 'k-balanced' objective, has been studied recently, while the second objective aligns with the well-established 'k-median' problem, which has received substantial research focus over time. In this study, we undertake a comprehensive approach to address this bi-objective optimization challenge. Initially, we formulate the problem as an integer linear program, providing a solid foundation for subsequent analysis. We then proceed to propose two distinct approaches for obtaining Pareto-optimal solutions. The first approach involves leveraging the \(\epsilon\)-constraint approach in conjunction with the commercial solver Gurobi. This approach demonstrates efficacy, particularly for smaller problem instances; however, it exhibits notable computational demands for larger-scale scenarios.