## 2 Background
### Facility Location Problem
#### 2.1.3 Clustering and k-means Procedure  
Clustering is the classification of similar objects, data, or individuals into different groups. Objects, data, or individuals in the same group have greater similarity and have the smallest similarity in different categories. This analysis is an unsupervised learning technique that offers different views on the inherent structure of a given dataset [43; 44; 45]. Additionally, according to [PERSON] et al. [46], clustering algorithms can be used as regionalization techniques. According to [PERSON] and [PERSON] [47], there are different methods of clustering, which can be categorized into the hierarchical approach or in the partition approach. In the hierarchical approach, a nested series of partitions is produced, and in the partition approach, only one partition is obtained. The advantage of the partitional methods is realized in applications with large datasets; that is, when the construction of a dendrogram is computationally prohibitive in the hierarchical approach. Additionally, unlike hierarchical methods, in which clusters are not revisited after being built, reallocation algorithms can gradually improve clusters' partitional methods. With proper data, this results in high-quality clusters. Regarding the partition approach, the squared error criterion is the most frequently used criterion, and the k-means is the simplest and most commonly used algorithm with this criterion. The k-means algorithm, first introduced by [PERSON] [48], starts with a random initial partition, and with each iteration, patterns are reassigned to the clusters based on the similarity between the pattern and the cluster centers. The interactions occur until a convergence criterion is met or the square error stops decreasing significantly after a few interactions. This reasoning There are many ways to implement the k-means algorithm [48; 49; 50; 51]. [PERSON] and [PERSON]'s [51] algorithm has the advantage of avoiding unnecessary computations in each iteration. According to [PERSON] and [PERSON] [52], the purpose of [PERSON] and [PERSON]'s [51] algorithm is to identify the partition of the data space so that the sum of squares of errors (SSE) is locally ideal within the cluster. The first step of the algorithm is to choose the initial k centroid. This can be achieved based on previous empirical knowledge, if available, using k random observations from the dataset with the k observations that are farthest apart from each other in the data space. The cases are then assigned to the nearest centroid, and the centroid is averaged over the assigned data points. The iterations proceed as follows:  
* If the centroid has been updated in the last step, for each data point included, the within-cluster sum of squares for each data point, if included in another cluster, is calculated. * If one of the cluster sum of squares is smaller than the current one, the case is assigned to this new cluster. As discussed at the end of the previous section and according to [PERSON] and [PERSON] [15], the pre-processing required to identify candidate locations is essential for the execution of an MCLP. Thus, the k-means procedure could support models focused on the FLP of n facilities since it can be synthesized in the location of the k centroid, thus defining the possible candidate locations to position the facilities [39; 41; 42; 53]. In addition, because k-means can be relatively scalable and efficient for large datasets, the method often ends up finding an optimal centroid, which minimizes the sum of distances between data points (facilities and demand points) [54]. It is through this formal k-means procedure that the importance of data clustering is widely recognized by several researchers. Thus, this procedure is understood as a model to better manage, browse, filter, and efficiently and intelligently summarize a large amount of data that can be used for decision making with greater safety [41; 55; 56; 57; 58; 59; 60; 61; 62; 63; 64; 65; 66; 67].