An iterated greedy algorithm with variable reconstruction size for the obnoxious p-median problem

The obnoxious p-median problem is a facility location problem where we maximise the sum of the distances between each client point and its nearest facility. Since it is nondeterministic polynomial-time (NP)-hard, most algorithms designed for the problem follow metaheuristic strategies to find high-quality solutions in affordable time but with no optimality guarantee. In this paper, a variant of the iterated greedy algorithm is developed for the problem. It adopts the idea of increasing the search radius used in variable neighbourhood search by increasing the number of reconstructed components at each iteration with no improved solution, where the amount of the increase is determined dynamically based on the quality of the current solution. We demonstrate that the new algorithm significantly outperforms the current state-of-the-art metaheuristic algorithms for this problem on standard datasets.