A reverse elimination approach for the p-median problem

The p-median problem is the well-known combinatorial optimisation problem of locating a number of p facilities on a graph such that the sum of all distances from each vertex to its nearest facility is minimised. Applying heuristics to the p-median problem has a long history with a greedy algorithm and a greedy interchange procedure being the most frequently applied approaches. Here we apply the reverse elimination method, a tabu search procedure whose tabu list management relies on logical interdependencies between the solutions encountered throughout the search path. While the original version of the method tends to run into problem specific difficulties a simple diversification mechanism helps to find good solutions for a number of benchmark problems.