Exploiting flat subspaces in local search for p-Center problem and two fault-tolerant variants

Seyed R. Mousavi

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
28 Downloads (Pure)

Abstract

In this paper, local search algorithms are proposed for the p-Center, α-Neighbour p-Center and p-Next Center facility location problems. The α-Neighbour p-Center and p-Next Center problems may be viewed as two fault-tolerant variants of the p-Center problem. The algorithm proposed for p-Center outperforms the most recent state-of-the-art metaheuristic for this problem using standard datasets. The proposed algorithm for p-Next Center also outperforms an existing, more complex, state-of-the-art metaheuristic for this problem. The algorithm proposed for α-Neighbour p-Center is the first metaheuristic for this problem, to the best of the author's knowledge. The proposed algorithms share a common design, which is the integration of the first-improvement local search with strategies to exploit flat subspaces in the search space. The overall success of this design paradigm motivates further investigation about its properties and applications to similar NP-hard optimisation problems.

Original languageEnglish
Article number106023
Number of pages22
JournalComputers and Operations Research
Volume149
Early online date17 Sept 2022
DOIs
Publication statusPublished - Jan 2023

Bibliographical note

Published by Elsevier Ltd. This is an open access article under the CC BY license (https://creativecommons.org/licenses/by/4.0/).

Keywords

  • Flat subspace
  • Heuristic function
  • Local search
  • Metaheuristic
  • Move operation
  • p-Center problem
  • Search space

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Exploiting flat subspaces in local search for p-Center problem and two fault-tolerant variants'. Together they form a unique fingerprint.

Cite this