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

• Grant number: 15/06876-0
• Support Opportunities: 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
• Host 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

Abstract

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.