Advanced search
Start date

Clustering Search applied to the capacitated centered clustering problem: a parallel approach

Grant number: 15/06876-0
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): May 01, 2015
Effective date (End): December 31, 2015
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal Investigator:Antônio Augusto Chaves
Grantee:Davi Melo Morales
Home Institution: Instituto de Ciência e Tecnologia (ICT). Universidade Federal de São Paulo (UNIFESP). Campus São José dos Campos. São José dos Campos , SP, Brazil
Associated research grant:12/17523-3 - New hybrid methods to resolve combinatorial optimization problems, AP.JP


This project aims to study a way to parallelize the hybrid method Clustering Search (CS), which seeks to combine efficiently metaheuristics and local search heuristics. CS is an easily parallelizable method, since its components can be executed independently. Through parallelization of CS, we can use the full potential of multiple machines, as well as the use of all available processors to solve a problem. In order to validate the proposed CS, we will apply it to solve the capacitated centered clustering problem (CCCP). This is a relevant problem classified as NP-hard and that occurs in many practical applications in various business sectors . CCCP is a set partitioning problem of n clients, where each client has a demand, in p disjoint groups, so that the total dissimilarity within each group is minimized and the capacity restriction is respected in each group. The total dissimilarity of each group is computed as the sum of the dissimilarity existing between each point and the centroid of the group. The centroids are calculated from the average of the coordinates of the points allocated in the group. In this project we intend to develop a parallel hybrid heuristic for the CCCP, combining elements of various techniques, such as Genetic Algorithm, Simulated Annealing, Path Relinking and heuristic local search.