# Optimization of the Multi-Facility Location Problem Using Widely Available Office Software
## 2 Materials and Methods
### Benchmark Instances  
To verify the applicability of the proposed solution, both from the accuracy and optimization time points of view, five benchmark instances differing in difficulty are proposed.  
The first four instances (labeled A, B, C, D) are designed in such a way that the optimal solution can be easily determined. The points in these instances are arranged in groups of five, four at the vertices of the square, the fifth at its center. For each group, a center exists. The optimal position of the center for such a group is identical with the position of the fifth point in the center of the square. Instances A and D are shown in Figure 1 for illustration of the principle; blue circles represent points; orange circles represent centers in their optimal position. The fifth blue point in the center is covered by an orange circle.  
The last instance (labeled E) is created based on a real-world problem using real geographic data. There are 27 points and 4 centers to deploy. The coordinates of points are recorded in Table 1 and their visualization is shown in Figure 2. In contrast to benchmark tasks, for which it is possible to manually calculate the optimal position of the centers thanks to artificially designed points, for this type of task the optimal solution cannot be calculated in advance.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(P_{x}\) & \(P_{y}\) & \(P_{x}\) & \(P_{y}\) & \(P_{x}\) & \(P_{y}\) \\ \hline
1,007,667 & 801,321 & 1,034,425 & 791,499 & 1,154,708 & 568,789 \\
1,119,519 & 735,319 & 1,121,206 & 545,377 & 1,071,254 & 676,371 \\
1,071,043 & 646,830 & 974,653 & 687,137 & 1,155,563 & 630,925 \\
1,151,798 & 714,704 & 1,087,661 & 497,018 & 1,128,561 & 792,632 \\
1,128,044 & 512,236 & 1,131,202 & 523,717 & 1,033,047 & 722,781 \\
1,123,192 & 537,368 & 1,134,304 & 557,970 & 1,160,625 & 598,196 \\
1,168,146 & 570,806 & 1,061,233 & 646,733 & 1,042,352 & 640,852 \\
1,071,757 & 778,926 & 1,106,717 & 834,552 & 1,036,069 & 616,768 \\
1,130,697 & 751,389 & 1,047,521 & 742,126 & 1,098,638 & 587,366 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Coordinates of points for instance E.  
Figure 1: Examples of benchmark instances: (a) instance A; (b) instance D.  
The basic parameters and the optimal solution (if available) of all the benchmark instances are shown in Table 2 and in Figure 3.  
For each benchmark task, 100 optimizations were performed both in the Excel-Solver software as well as using the metaheuristic algorithm (see Section 2.4) and thus, 100 different solutions are obtained.  
Each task was solved in 4 ways:  
* by Excel-Solver evolutionary method on PC1;
* by Excel-Solver evolutionary method on PC2;
* by metaheuristic algorithm on PC1;
* by metaheuristic algorithm on PC2.  
For each task, method and hardware configuration, the following parameters and outputs calculated from all individual solutions are recorded:  
* minimal solution;
* average solution;
* standard deviation;  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Benchmark Instance** & **Number of Points** & **Number of Centers** & **Optimal Solution** \\ \hline A & 25 & 5 & 28.284271 \\ B & 50 & 10 & 56.568542 \\ C & 75 & 15 & 84.852814 \\ D & 100 & 20 & 113.137085 \\ E & 27 & 4 & NA \\ \hline \hline \end{tabular}
\end{table}
Table 2: Benchmark instances.  
Figure 3: Graphical comparison of benchmark complexity.  
Figure 2: Visualization of benchmark instance E.  
difference between the optimal and the minimal solutions in percent;
* difference between the optimal and the average solutions in percent;
* histogram, classes are from 1 percent to 10 percent deviation;
* graph with coordinates for result for the minimal solution.