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.
|Number of pages
|International Transactions in Operational Research
|Early online date
|3 Jul 2023
|E-pub ahead of print - 3 Jul 2023
Bibliographical note© 2023 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
- facility location
- hybrid metaheuristic
- iterated greedy
- obnoxious p‐median problem
- p‐median problem