### State-of-the-Art  
[PERSON] proposed an iterative procedure for solving the Weber problem (1-median problem), one of the simplest location problems, based on the iterative weighted least squares method [7]. This algorithm determines a set of weights that are inversely proportional to the distances from the current estimate to the sample points, and creates a new estimate that is the weighted average of the sample according to those weights. The [PERSON] procedure is very slow if the solution coincides with one of the demand points. Many researchers have developed modifications of the Weiszfeld algorithm [6; 15; 16; 17; 18; 19; 20] to avoid this disadvantage. The Weiszfeld algorithm can be embedded into more complex algorithms such as the Alternate Location-Allocation (ALA) procedure also called Lloyd's algorithm. This algorithm alternates the allocation step which divides the demand points into p groups in accordance with the number of the closest center and the location step which recalculates the center of each group (i.e., solves the Weber problem for each of groups). The idea of the ALA algorithm is applicable for both network and continuous p-median problems. Reviews of various solution techniques for p-median problems can be found in [11; 21; 22]. [PERSON] considered the problem of finding the median of a graph (the Weber problem on a network) [12] and generalized this problem to finding the p-medians [23]. The authors of [24; 25; 26] proposed a branch-and-bounds algorithm solving the network p-median problem, and in [27; 28] the authors considered algorithms based on graph theory for rather small problems. Lagrangian relaxations enables us to obtain an approximate solution to medium-sized problems [29; 30]. Many heuristic approaches have been developed for large-scale problems. The simplest approaches consist in local search, in which a set of network nodes adjacent to the nodes of the current intermediate solution is considered as a search neighborhood [31; 32]. [PERSON] et al. [33; 34; 35; 36] presented local search approaches for solving continuous p-median location problems including the Variable Neighborhood Search (VNS). [PERSON] et al. [37] introduce the use of a Hybrid VNS/TABU Algorithm to determine the correct location of p centers. In addition, [PERSON] et al. [34] proposed heuristic procedures including the genetic algorithm (GA), for rather small datasets. Modern literature on location methods offers many heuristic approaches [21; 38] to setting the initial centers of the ALA procedure, which are mainly various evolutionary and random search methods. A standard local search algorithm starts with some initial solution S and goes to a neighboring solution if this solution turns out to be superior. Moreover, finding the set of neighbor solutions \(n(S)\) is the key issue. Elements of this set are formed by applying a certain procedure to a solution \(S\). At each local search step, the neighborhood function \(n(S)\) specifies the set of possible search directions [39; 40] and determines the efficiency of the algorithm [41]. Local search methods have been developed in metaheuristics. [PERSON] and [PERSON] [41; 42; 43; 44] proposed a search algorithm with alternating neighborhoods (Variable Neighborhood Search, VNS). In works of [PERSON], [PERSON], and [PERSON] [41; 42; 45; 46; 47; 48], the authors provide an overview of local search methods based on the idea of alternating neighborhoods, including methods of combining these methods with other metaheuristics which reduce the dependence of the result on the choice of the neighborhood. Flexibility and high efficiency explain the VNS competitiveness in solving NP-hard problems, in particular, for solving automatic grouping and location problems [49; 50], multiple Weber problem [51], p-median problem [50; 51], and many others. For example, VNS algorithms [52; 35] or agglomerative algorithms [53; 54] demonstrate good results for the p-median problem.