Consider a set L of potential locations for p facilitites and a set U of locations of given users. The p-median problem is to locate simultaneously the p facilities at locations of L in order to minimize the total transportation cost for satisfying the demand of the users, each supplied from its closest facility. This model is a basic one in location theory and can also be interpreted in terms of cluster analysis where locations of users are then replaced by points in a given space. We propose several new Variable Neighborhood Search heuristics for the p-median problem and compare them with Greedy plus Interchange, and two Tabu Search heuristics.
