A graph clustering based decomposition approach for large scale p-median problems

The p-median problem (PMP) is the well known network optimization problem of discrete location theory. In many real applications PMPs is defined on very large scale networks, for which ad-hoc exact and/or heuristic methods have to be developed. To this aim, in this work we propose a heuristic decomposition approach which exploits the decomposition of the network into disconnected components obtained by a graph clustering algorithm. Then, in each component several PMPs are solved for suitable ranges of p by a Lagrangian dual and simulated annealing based algorithm. The solution of the whole initial problem is obtained combining all the PMPs solutions through a multi-choice knapsack model. The proposed approach is tested using several graph clustering algorithms and compared with the results of the state-of-the-art heuristic methods.