A parallel mayfly algorithm for the α-neighbor p-center problem

Cura T.

Applied Soft Computing, vol.144, 2023 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 144
  • Publication Date: 2023
  • Doi Number: 10.1016/j.asoc.2023.110527
  • Journal Name: Applied Soft Computing
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC
  • Keywords: Local search, Mayfly algorithm, Metaheuristics, p-center problem, Search-in-grid strategy
  • Istanbul University Affiliated: Yes


This study presents a competitive algorithm in which the mayfly optimization algorithm (MA) is combined with a local search procedure to provide high-quality solutions to the α-neighbor p-center problem (α – pCP). The aim of this problem is to locate p facilities on a plane such that the maximum distance between each demand point and its αth closest facility is minimized. Although α – pCP is a discrete optimization problem, it is addressed in this study from the perspective of a continuous optimization problem. The major reason for this choice is that the MA is a very suitable technique for finding the optimum point on a plane. However, it is very difficult to successfully apply this technique to a discrete optimization problem. Hence, additional efforts are made to reduce the computational burden that arises from approaching this from the perspective of a continuous problem. Thus, an effective solution method based on the MA for finding the optimum point on a plane is presented for the discrete α – pCP. The proposed MA method is compared to the best alternatives found in the literature, which are an extremely efficient exact procedure for the continuous variant of the problem, and a GRASP algorithm that includes a tabu search with strategic oscillation (SO) post-processing. A comparative analysis shows that the performance of the proposed algorithm is similar to that of these state-of-the-art methods. A more extensive comparison shows that the two best performing algorithms, the MA and the SO, complement each other. In addition, the proposed method performs very well for cases where the number of facilities are low. If we consider only the cases where p ≤ 50, we see that the MA performs best 5 times, 14 times and 14 times for α= 1, 2, 3, respectively, and loses twice, three times, and three times.