Portal de Administração de Conferências - CEFET-MG, 13ª SEMANA DE CIÊNCIA & TECNOLOGIA 2017 - CEFET-MG

Tamanho da fonte: 
Problema de máxima cobertura: aplicado nos assentamentos de ajuda humanitária
Marco Antonio Espírito Santo, Matheus Martins Aguiar, Rafael Antunes Batista, Mateus Rocha Gonçalves

Última alteração: 2017-08-29

Resumo


O Problema da Máxima Cobertura consiste em localizar em um grafo os nodos que selecionados cubram a maior área possível, podendo ser representada como a maior quantidade possível de vértices, através da definição de k subconjuntos, maximizando a união entre os mesmos, ou seja, maximizar a área máxima coberta. É considerado um problema NP-completo clássico da teoria da complexidade computacional e possui diversas aplicações em problemas reais, como a procura da melhor localização para infraestruturas ou qualquer tipo de problema que exija uma cobertura máxima de uma área/conjunto.O objetivo deste trabalho é apresentar um algoritmo heurístico baseado em Algoritmos Genéticos para a resolução deste problema. Espera-se, com isso, determinar de forma eficaz melhores locais possíveis para maximizar a cobertura sobre um conjunto de sub-conjuntos. Uma aplicação real e prática deste clássico problema da otimização, seu uso na localização de postos de ajuda humanitária em um assentamento de refugiados, foi modelado, abordando com maiores detalhes as escolhas tomadas e os pormenores do desenvolvimento. Os resultados obtidos são satisfatórios na solução do problema, tendo um grande potencial para problemas de larga escala. Nesse sentido, este trabalho contribui de forma confiável na bordagem própria de resolução do problema da Máxima Cobertura.

Palavras-chave


Máxima Cobertura. Problema de Localização da Máxima Cobertura. Otimização. Algoritmo Genético.