Seyed Mousavi, Soni Bhambar, Matthew England

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

  • Management of Technology and Innovation
  • Management Science and Operations Research
  • Strategy and Management
  • Computer Science Applications
  • Business and International Management

AbstractThe 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.

Need a simple solution for managing your BibTeX entries? Explore CiteDrive!

  • Web-based, modern reference management
  • Collaborate and share with fellow researchers
  • Integration with Overleaf
  • Comprehensive BibTeX/BibLaTeX support
  • Save articles and websites directly from your browser
  • Search for new articles from a database of tens of millions of references
Try out CiteDrive

More from our Archive