Clustering Search aplicado ao problema de agrupamento centrado capacitado: uma abordagem paralela

• Processo: 15/06876-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de maio de 2015
• Vigência (Término): 31 de dezembro de 2015
• Área do conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Antônio Augusto Chaves
• Beneficiário: Davi Melo Morales
• Instituição Sede: 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, Brasil
• Vinculado ao auxílio: 12/17523-3 - Novos métodos híbridos para resolução de problemas de otimização combinatória, AP.JP
• Assunto(s): Programação paralela Meta-heurística Computação em cluster
• Palavra(s)-Chave do Pesquisador: heurísticas híbridas | problema de agrupamento | Programação paralela | Metaheurísticas

Resumo

Esse trabalho visa estudar uma forma de paralelizar o método híbrido Clustering Search (CS), que busca combinar de maneira eficiente meta-heurísticas e heurísticas de busca local. O CS é um método facilmente paralelizável, uma vez que seus componentes podem ser executados independentemente. Por meio da paralelização do CS será possível utilizar todo o potencial de várias máquinas, bem como o uso de todos os processadores disponíveis para a resolução de um problema. Com o objetivo de validar o CS Paralelizado proposto, será abordado o problema de agrupamento centrado capacitado (CCCP, do inglês Capacitated Centered Clustering Problem). Trata-se de um problema relevante, de difícil solução e que ocorre em diversas aplicações práticas em diferentes setores empresariais. O CCCP é um problema de particionamento de conjunto de n clientes, no qual cada cliente possui uma demanda, em p agrupamentos disjuntos, de maneira que a dissimilaridade total dentro de cada agrupamento seja minimizada e a restrição de capacidade de cada agrupamento seja respeitada. A dissimilaridade total de cada agrupamento é calculada como a soma das dissimilaridades existentes entre cada ponto de demanda e o centróide do agrupamento. Os centróides são calculados a partir da média das coordenadas dos pontos de demanda alocados no agrupamento. Neste projeto pretende-se desenvolver uma heurística híbrida paralela para o CCCP, combinando elementos de diversas técnicas, tais como: Algoritmo Genético, Simulated Annealing, Path Relinking e heurísticas de busca local.