## 2 Methods  
### The Basic Algorithmic Approaches  
Based on the algorithm proposed by [PERSON] [75] for discrete p-median problems on a network, Alternate Location-Allocation (ALA) procedure [87; 88] also known as the standard k-means procedure [76] the most popular algorithm for the k-means and p-median problems. This simple algorithm can be considered as a special case of similar Expectation Maximization (EM) procedure [89; 90; 91; 92]. The ALA procedure sequentially improves an intermediate solution, enabling us to find a local minimum of the objective Function (1). In terms of continuous optimization, the ALA procedure is not a true local search algorithm since it searches for a new solution not necessarily in the \(\varepsilon\)-neighborhood of the existing solution. However, it usually outperforms simpler local optimization methods: gradient or coordinate descent, etc. In the case of a p-median problem, Algorithm 1 solves the Weber problem (i.e., center search problem or a 1-median problem) for each cluster. The iterative Weiszfeld procedure gives an approximate solution to the Weber problem with given accuracy \(\varepsilon_{1}\). At each subsequent iteration, the coordinates of the solution (center) \(X^{\prime}\) of a subset \(S^{\prime}=\{A^{\prime}{}_{1},\ldots,A^{\prime}{}_{N^{\prime}}\}\subset\{A_{ 1},\ldots,A_{N}\}\) of \(N^{\prime}\) demand points are calculated from the previous solution \(X\) as follows:  
\[X^{\prime}\leftarrow\sum_{i=1}^{N^{\prime}}\frac{A^{\prime}{}_{i}}{L(X,A^{ \prime}{}_{i})}/\sum_{i=1}^{N^{\prime}}\frac{1}{L(X,A^{\prime}{}_{i})} \tag{4}\]These calculations are repeated until \(L(X,X^{\prime})<\epsilon_{1}\). Usually, the Weiszfeld procedure converges quickly. For the majority of problems, no more than 50 iterations are required in order to reach the accuracy limits of the double data type except include the cases where the solution coincides with one of the demand points. Such situations are easily bypassed:  
\[X^{\prime}\leftarrow\frac{\sum_{i\in\{\overline{1,N^{\prime}}\},L(X,A^{\prime} _{i})<\epsilon_{2}}\left[\frac{A^{\prime}_{i}}{L(X,A^{\prime}_{i})}\right]}{ \sum_{i\in\{1,N^{\prime}\},L(X,A^{\prime}_{i})<\epsilon_{2}}\left[\frac{1}{L(X, A^{\prime}_{i})}\right]} \tag{5}\]  
Here, \(\epsilon_{2}<\epsilon_{1}\) is a minimum distance at which two points are considered different. Embedding the Weiszfeld iterative procedure in an iterative ALA algorithm, which, in turn, is embedded in more complex algorithms, makes such algorithmic constructions difficult to use effectively with large-scale problems. Steps 1 and 2 of the ALA algorithm are aimed at the reduction of the objective function. Knowing the coordinates of the centers \(X_{i}\), without changing their coordinates, Step 1 redistributes the demand points \(A_{i},\ldots,A_{N}\) among the centers (i.e., forms clusters of demand points around the centers) so that the sum of the distances from each of the demand points to the nearest center becomes minimal. Step 1 solves a simplest simple discrete optimization problem. Step 2 solves a series of continuous optimization problems (Weber problems) which minimize the total distance from the center \(X_{i}\) to the demand points \(A^{\prime}_{1},\ldots,A^{\prime}_{N^{\prime}}\) of its cluster. Each iteration of the Weiszfeld procedure (4) is also aimed at gradual improvement of the current solution \(X\). For a gradual improvement of solutions, the Weber problem does not have to be solved to a given accuracy \(\epsilon_{1}\) at each iteration of the ALA algorithm. Thus, Steps 2 and 3 can take the following form:  
Step 2: For each cluster \(C_{i}\), \(i=\overline{1,p}\), correct its center \(X_{i}\) with an iteration of Weiszfeld procedure:  
\[X_{i}\leftarrow\frac{\sum_{Y\in C_{i},L(X,Y)<\epsilon_{2}}\left[\frac{Y}{L(X_{ i},Y)}\right]}{\sum_{Y\in C_{i},L(X,Y)<\epsilon_{2}}\left[\frac{1}{L(X_{i},Y)}\right]} \tag{6}\]  
Step 3: Repeat from Step 1 if Steps 1 and 2 moved at least one of centers \(X_{i}\) by a distance exceeding \(\epsilon_{1}\).