# Optimization of the Multi-Facility Location Problem Using Widely Available Office Software
## 2 Materials and Methods
### Metaheuristic Algorithm  
The metaheuristic algorithm used to complement the Excel Solver is based on the Simulated Annealing (SA) principle adapted for the MFLP problem. This choice was based on the previous experiences of the authors as this algorithm proved to be very successful in other position optimization problems (see [23] for more details). The principle is inspired by annealing in metallurgy, where this process is used to reduce the defects of material by way of heating and controlled cooling. Algorithm 1 presents this method in pseudocode. The inputs of the algorithm are as follows:  
* \(c\): number of centers to deploy. * \(b\): number of points. * \(B\): set of points. * The outputs are as follows:
* \(C_{best}\): best solution (i.e., locations of \(c\) centers) found during optimization. * \(D_{best}\): evaluation of the best solution found during optimization (objective function). Settings of the algorithm:
* \(T_{max}\): maximum temperature (the initial value used in the first generation). * \(T_{min}\): the threshold value of the temperature (used in the termination condition). * \(\gamma\): coefficient controlling the speed of temperature cooling. * \(n_{1 max}\): maximum number of transformations per iteration. * \(n_{2 max}\): maximum number of replacements per iteration. * Other symbols used:
* \(C\): current solution. * \(D\): value of the current solution. * \(C^{\prime}\): transformed solution. \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Value** \\ \hline Max time & Unlimited \\ Iterations & Unlimited \\ Constraint precisions & 0.000001 \\ Convergence & 0.0001 \\ Population size & 100 \\ Random seed & 0 \\ Mutation rate & 0.075 \\ Maximum time without improvement & 30 s \\ Max subproblems & Unlimited \\ Maximum feasible solutions & Unlimited \\ Integer optimality & 1\% \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Parameters used for optimization in the Excel Solver. * \(D^{\prime}\): value of the transformed solution. * \(p(C\to C^{\prime})\): probability that the transformed solution replaces the original. * \(n_{1}\): current number of transformations in an iteration. * \(n_{2}\): current number of replacements in an iteration. ```
1: Algorithm_MFLP_SA (\(c\),\(b\),\(B\),\(T_{max}\),\(T_{min}\),\(\gamma\),\(n_{1 max}\),\(n_{2 max}\))
2:\(C=C_{best}=\)Generate_Random_Solution()
3:\(D=D_{best}=f(C)\)
4:\(T=T_{max}\)
5:while\(T\geq T_{min}\)do// Iterations
6:\(n_{1}=n_{2}=1\)
7:while\(n_{1}\leq n_{1 max}\)and\(n_{2}\leq n_{2 max}\)do// Transformations
8:\(C^{\prime}=\)Transform_Solution (\(C\),\(T\),\(T_{max}\),\(T_{min}\))
9:\(D^{\prime}=f(C^{\prime})\)
10:\(p(C\to C^{\prime})=f(C,C^{\prime},T)\)
11:with probability\(p(C\to C^{\prime})\)do// Replacements
12:\(C=C^{\prime}\)
13:\(D=D^{\prime}\)
14:\(n_{2}=n_{2}+1\)
15:if D \(<D_{best}\)thendo
16:\(C_{best}=\) C
17:\(D_{best}=D\)
18:\(n_{1}=n_{1}+1\)
19:\(T=\gamma\)_T_
20:return\(C_{best}\),\(D_{best}\)
```  
**Algorithm 1** SA algorithm for the MFLP  
At the beginning (point 1), the initial deployment of centers is generated using the random number generator with uniform distribution. The value of every variable \(C_{i}\) is generated in range limited by the minimum and maximum value of all the points in the corresponding axes \(x\) or \(y\). In point 2, this solution is evaluated using the objective function in Formula (2). The algorithm works in iterations. During an iteration (points 4 to 18), the value of temperature \(T\) is constant. In each iteration, a number of transformations of the current solution \(C\) into solution \(C^{\prime}\) is performed (see point 7). This transformed solution replaces the original (points 10 to 13) with some probability given by the Metropolis criterion (4). A better solution is always replaced. However, the key is accepting even worse solutions, thus expanding the search space explored for the global optimum.