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.
News published in Agência FAPESP Newsletter about the scholarship: