# Globally Optimal Facility Locations for Continuous-Space Facility Location Problems
## 3 Location Estimation Based on the Manhattan Distance
### Identification of the Candidate Locations  
As presented in (33), the globally optimal single-facility location is an element from the set of mesh points. Then, we investigate the candidate locations for the multi-facility location problem. In the multi-facility location problem, each demand point is assigned to its closest facility. Suppose that we have obtained the optimal facility locations, then the set of demand points served by the same facility is considered as a group, which is independent of other groups. In this sense, the optimal facility location is still one ofthe mesh points within this group. After considering the optimal facility locations for all groups, these optimal facility locations are from the mesh points that are constructed based on the observation coordinates. Then, we have  
\[(\widetilde{u}_{l},\widetilde{v}_{l})\in\big{\{}\big{(}x_{i},y_{j}\big{)}:i,j=1, 2,\ldots,n\big{\}}\cup\bigg{\{}\bigg{(}\frac{x_{i}+x_{i+1}}{2},\frac{y_{j}+y_{j+ 1}}{2}\bigg{)}:i,j=1,2,\ldots,n-1\bigg{\}}\ l=1,\ 2,\ldots,m \tag{35}\]  
where \(m\) is the number of facilities, which is indexed by \(l\).  
As an illustration, we provide an example to show the candidate locations (i.e., mesh points) for the facilities. In the example, we consider three demand points (see Table 3). As shown in Figure 2, we construct the mesh points based on these three demand-point coordinates. Accordingly, 25 mesh points are represented by black hollow rhombuses that also contain three demand points. These 25 mesh points are considered as the candidate facility locations. It is easy to conclude that the number of candidate facilities E is related to the number of demand points \(n\), where the relationship between them is given by  
\[\text{E}=(n+n-1)^{2}=5^{2}=25 \tag{36}\]  
When the demand points have the same coordinate value on one axis, the number of candidate facilities E can be smaller. Suppose that there are \(p\) (\(p\leq 2n-1\)) different \(x\)-axis values and \(q\) (\(q\leq 2n-1\)) different \(y\)-axis values, the number of candidate facilities E can be smaller, which is given by  
\[\text{E}\ =pq\leq(2n-1)^{2} \tag{37}\]  
Based on the conclusion about the number of the candidate locations for the two-dimensional multi-facility location problem, it is easy to deduce the number of candidate locations for the three-dimensional multi-facility location problem, which is given by  
\[\text{E}\leq(2n-1)^{3} \tag{38}\]  
\begin{table}
\begin{tabular}{c c c c} \hline \hline \(i\) & \(x_{i}\) & \(y_{i}\) & \(\omega_{i}\) \\ \hline
1 & 1 & 1 & 0.3 \\
2 & 3 & 7 & 0.2 \\
3 & 7 & 5 & 0.5 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Data for the example with three demand points.  
Figure 2: Illustration of the candidate facility locations.  
If we consider the minimizer from \(x_{(k)}\) and \(x_{(k+1)}\) for the second case presented in (39), the number of mesh points can be reduced and the number of candidate facilities E for the two- and three-dimensional multi-facility location problems are given below  
\[\mathrm{E}\leq(n-1)^{2} \tag{39}\]  
\[\mathrm{E}\leq(n-1)^{3} \tag{40}\]  
Finally, we construct the candidate facility locations and transfer the continuous-space multi-facility location problem to the discrete-space multi-facility location problem. Next, our goal is to select the optimal locations from the mesh points, which is the global optimum solution to the problem.