Um método baseado em estratégia evolutiva e Variable Neighborhood Descent para o problema quadrático de alocação.

Abstract

O Problema Quadrático de Alocação (PQA) é bastante conhecido na área de otimização combinatória e possui ampla aplicação na indústria. O PQA faz parte da classe de problemas definidos na computação como NP-difícil, ou seja, para certas instâncias não é possível encontrar uma solução ótima em tempo computacional viável devido ao grande número de soluções a serem avaliadas. Assim, o uso de heurísticas torna-se fundamental, uma vez que essas indicam uma maneira de reduzir o número de avaliações necessárias para problemas com uma grande quantidade de soluções candidatas. O objetivo deste trabalho é o desenvolvimento de uma meta-heurística aplicável ao PQA por meio da Computação Evolucionária. Para isso, faz-se necessário o estudo do Problema Quadrático de Alocação, das estruturas de vizinhança, e algoritmos utilizados na resolução do problema. Este trabalho apresenta uma meta-heurística híbrida combinando Estratégias Evolutivas com a VND. Os resultados obtidos sugerem que não há diferença significativa entre as soluções do método proposto e da literatura, indicando que a meta-heurística proposta pode ser uma boa alternativa na busca pela melhor solução. Quando se compara a média das soluções obtidas, a literatura tende a apresentar um melhor resultado. Entretanto, a comparação dos valores médios do ES-VND com a literatura pode ser injusta, pois somente os melhores resultados estão disponíveis na literatura para comparação.