Algoritmos para problemas de cobertura generalizados

Abstract

A presente tese refere-se ao estudo de técnicas de resolução para o problema de cobertura generalizado (PCG). Conhecida que é a complexidade computacional deste problema combinatório, começam por ser estudados métodos de tipo heurístico, envolvendo heurísticas greedy primais com pesquisa local e heurísticas duais. Na avaliação das heurísticas fazem-se análises da situação mais desfavorável e também análises estatísticas elementares dos resultados computacionais. Com vista ao melhoramento dos limites para o óptimo são exploradas três relaxações lagrangeanas para o problema em causa. Uma relaxa todas as restrições de cobertura e outras duas, a estrutural e a de decomposição sugeridas por casos particulares do PCG, exigem reformulações no problema para forçar o aparecimento de subestruturas de fluxo de custo mínimo. Escreve-se sobre a possibilidade de aplicação ao PCG de técnicas de corte, mais precisamente dos cortes condicionais e dos cortes-penalidades. É apresentado um algoritmo de pesquisa em árvore para o PCG que combina algumas técnicas estudadas com a programação linear. Nos testes computacionais para análise empírica dos procedimentos utilizaram-se quase exclusivamente instâncias relativas ao escalonamento dos condutores de transportes urbanos. No final, para além dos resultados obtidos com o mencionado conjunto de instâncias, é sintetizada a experiência efectuada num vasto conjunto de instâncias do problema de cobertura provenientes de aplicações reais e da literatura. Dá-se especial relevo aos casos de PCG relacionados com escalonamento de pessoal, contudo os mesmos métodos podem ser aplicados a qualquer tipo de problema de cobertura generalizado. Das conclusões deste trabalho, poder-se-á destacar a importância de que se revestiu o desenvolvimento da relaxação lagrangeana estrutural. Também os cortes-penalidades se mostraram de grande interesse.