Heuristics Applied to Minimization of the Maximum-Diameter Clustering Problem

Authors

  • Gustavo Silva Semaan UFF
  • Augusto Cesar Fadel IBGE
  • José André de Moura Brito ENCE

Keywords:

heuristics, Clustering, Metaheuristic algoritms, integer programming

Abstract

This paper introduces two heuristic algorithms for the Maximum-Diameter Clustering Problem (MDCP), based on the Biased Random-Key Genetic Algorithm (BRKGA) and the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics. This problem consists of finding k clusters that minimize the largest within-cluster distance (diameter) among all clusters. The MDCP is classified as NP-hard and presents increased difficulty when attempting to determine the optimal solution for any instance. The results obtained in the experiments using 50 well-known instances indicate a good performance of proposed heuristics, that outperformed both three algorithms and an integer programming model from the literature.

Downloads

Published

2020-09-16
Bookmark and Share