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

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorRibeiro, Celso da Cruz Carneiro-
Autor(es): dc.contributorCPF:34620081022-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3614186131432854-
Autor(es): dc.contributorArmentano, Vinicius Amaral-
Autor(es): dc.contributorCPF:77545192834-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4783064Y9-
Autor(es): dc.contributorLucena Filho, Abilio Pereira de-
Autor(es): dc.contributorCPF:75123400922-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0907883161698484-
Autor(es): dc.contributorMartins, Simone de Lima-
Autor(es): dc.contributorCPF:30120908222-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5202429302236084-
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorCPF:31609080822-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.creatorPessoa, Luciana de Souza-
Data de aceite: dc.date.accessioned2024-07-11T18:03:08Z-
Data de disponibilização: dc.date.available2024-07-11T18:03:08Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2010-03-30-
Data de envio: dc.date.issued2021-03-10-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/18756-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/762553-
Descrição: dc.descriptionThe 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.-
Descrição: dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior-
Descrição: dc.descriptionO 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectProblemas de cobertura de conjuntos-
Palavras-chave: dc.subjectMetaheurística-
Palavras-chave: dc.subjectHeurísticas lagrangeanas-
Palavras-chave: dc.subjectSet covering problems-
Palavras-chave: dc.subjectMetaheuristic-
Palavras-chave: dc.subjectLagrangean heuristics-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleHeurísticas para o problema de k-cobertura de conjuntos-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.