Parallel Clustering Search Applied to Capacitated Centered Clustering Problem

摘要

The Clustering Search (CS) is a hybrid method that tries to combine metaheuristics and local search heuristics so that the search is intensified only in promising regions of the solution space. In this paper we propose a new parallel method based on the CS, using the Genetic Algorithm as a solutions generator, to solve the Capacitated Centered Clustering Problem (CCCP). The CCCP is to partition a set of n points into p disjoint groups with limited capacity. Each point is associated with a demand value and the objective is to minimize the sum of the Euclidean distances between the points and their respective geometric centers. The parallel CS consists in a master-slave system implemented following a message passing approach in order to parallelize the local search component, which is the most computationally demanding procedure. The computational results show that the parallel CS is an effective strategy in terms of computational time and efficiency.