Application of the probability changing method for optimal location problems on a network

In this paper, the authors consider the p-median optimal location problem on a graph (network) which is a popular model for both logistic problems (optimal transportation, telecommunication and other infrastructure elements placement) and problems of cluster analysis, pattern recognition and estimation theory. The aim of the p-median problem on a graph (network) is to find the given number p of vertices of a graph such that the total distance from each vertex to the nearest chosen vertex reaches its minimum. To solve this NP-hard (in general) problem approximately, the authors propose a heuristic algorithm based on ideas of the probability changing method which is a random search method with adaptation. The idea of the proposed algorithm is based on random choosing of vertices in accordance with the given probabilities of choosing each of them. The probabilities for every chosen vertex and its neighborhood alter depending on the value of the objective function (i.e. in accordance with the total distance from each of the vertices to the nearest chosen vertex). For the algorithm for the large-scale p-median problems, a problem of optimal use of computational capacity is important. The effectiveness of the proposed algorithm was proved experimentally on test datasets from the ORLIB (special dataset library for operations research). In addition, the authors illustrate the results for the proposed algorithm combined with a local search procedure for the considered problem. The experiments show that the results of such combination exceed the results of the multiple start of the local search procedure from randomly chosen vertices. In addition, the experiments demonstrate the ability of the proposed algorithm to reach an exact solution for small problems.