Heurísticas para o problema de k-cobertura de conjuntos

The set k-covering problem (SkCP) is a variant of the classical set covering problem (SCP), in which each object is required to be covered at least k times. Aplications of the SkCP can be modeled as set covering problems, however, they are treated as kcovering problems whenever reliability constraints are considered. In this thesis, we describe a new application to the SkCP in telecommunications. Besides, we propose three heuristics. Initially, we propose a GRASP with path-relinking. Following, we present a Lagrangean heuristic which uses a greedy construction procedure to build feasible primal solutions. Finally, we propose a hybrid Lagrangean heuristic, named LAGRASP, combining a greedy Lagrangean heuristic to a GRASP with path-relinking. Computational experiments are reported for 135 instances derived from the OR-Library instances for the SCP. Keywords: Set covering problems, metaheuristics, Lagrangean heuristics.Coordenação de Aperfeiçoamento de Pessoal de Nível SuperiorO problema de k-cobertura de conjuntos (PkCC) é uma variação do problema de cobertura de conjuntos (PCC) clássico, no qual cada objeto deve ser coberto por, pelo menos, k conjuntos. Aplicações para o PkCC podem ser modeladas originalmente como problemas de coberturas de conjuntos, entretanto, elas devem ser tratadas como problemas de k-cobertura sempre que restrições de confiabilidade forem consideradas. Nesta tese, descreve-se uma nova aplicação para o PkCC no âmbito das telecomunicações. Além disso, três heurísticas são propostas. Inicialmente, propõe-se um GRASP com reconexão por caminhos. Em seguida, apresenta-se uma heurística lagrangeana que utiliza um algoritmo construtivo guloso para gerar soluções primais viáveis. Por fim, propõe-se uma heurística lagrangeana híbrida, denominada LAGRASP, que combina uma heurística lagrangeana gulosa a um GRASP com reconexão por caminhos. Experimentos computacionais são apresentados para 135 instâncias-teste derivadas a partir de instâncias extraídas da OR-Library para o PCC