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

Seyed Mousavi, Soni Bhambar, Matthew England

Research output: Contribution to journalArticlepeer-review

16 Downloads (Pure)


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.
Original languageEnglish
Pages (from-to)(In-Press)
Number of pages32
JournalInternational Transactions in Operational Research
Early online date3 Jul 2023
Publication statusE-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


Dive into the research topics of 'An iterated greedy algorithm with variable reconstruction size for the obnoxious p-median problem'. Together they form a unique fingerprint.

Cite this