Heuristics Applied to Minimization of the Maximum-Diameter Clustering Problem

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.