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

• Ano de defesa: 2010
• Autor(a) principal: Pessoa, Luciana de Souza
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Problemas de cobertura de conjuntos; Metaheurística; Heurísticas lagrangeanas; Set covering problems; Metaheuristic; Lagrangean heuristics; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/18756

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.