Banca de QUALIFICAÇÃO: MATEUS DA SILVA BATISTA

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
DISCENTE : MATEUS DA SILVA BATISTA
DATA : 23/06/2026
HORA: 10:00
LOCAL: Remoto
TÍTULO:

Problema Contínuo de Cobertura por Discos de Raio Fixo

PALAVRAS-CHAVES:

geometria computacional; otimização combinatória; cobertura por discos; programação linear inteira; meta-heurística; matheurística; CMSA; BRKGA

PÁGINAS: 100
RESUMO:

O Problema Contínuo de Cobertura por Discos de Raio Fixo (PCCD) consiste em determinar o menor conjunto de discos de raio fixo capaz de cobrir todos os pontos de uma instância no plano Euclidiano. Diferentemente de versões discretas do problema, os centros dos discos
podem ser posicionados em qualquer ponto de R², o que torna o espaço de soluções contínuo e amplia a dificuldade computacional do problema. Apesar de sua formulação simples, o PCCD é um problema NP-difícil, motivando o desenvolvimento de métodos capazes de produzir soluções de alta qualidade em tempo computacional viável.
Esta dissertação investiga abordagens exatas, heurísticas e matheurísticas para o PCCD. Inicialmente, é proposta uma matheurística baseada no método Construct, Merge, Solve & Adapt (CMSA), denominada CMSAPCCD, na qual discos candidatos são gerados por procedimentos construtivos e posteriormente combinados em subinstâncias resolvidas por Programação Linear Inteira. Além disso, é apresentado um algoritmo híbrido baseado em Biased Random-Key Genetic Algorithm(BRKGA), denominado HBRKGA, que combina uma representação por chaves aleatórias, um procedimento de decodificação, uma heurística de refinamento e um componente exato para intensificar a busca por soluções melhores. 

O trabalho também propõe métodos exatos para o problema, baseados na discretização do espaço contínuo de soluções e na redução do PCCD para o problema de cobertura de conjunto. A partir dessa redução, são desenvolvidos dois algoritmos exatos, denominados método exato fraco e método exato forte, que diferem quanto à forma de geração dos discos candidatos. Adicionalmente, é apresentado um gerador de instâncias artificiais com ótimo conhecido, o que permite avaliar de forma controlada a qualidade das soluções obtidas e a capacidade dos métodos exatos em comprovar otimalidade. 

Os resultados computacionais indicam que as abordagens propostas são competitivas em relação a métodos da literatura, especialmente quando combinam estratégias heurísticas com modelos de Programação Linear Inteira. Em particular, o HBRKGA apresentou bom desempenho na obtenção de soluções de alta qualidade, enquanto os métodos exatos foram capazes de comprovar a otimalidade em instâncias artificiais com ótimo conhecido. Dessa forma, esta dissertação contribui para o estudo computacional do PCCD por meio de novas formulações, algoritmos híbridos e instâncias de teste voltadas à avaliação experimental do problema.

MEMBROS DA BANCA:
Presidente - 1114959 - RIAN GABRIEL SANTOS PINHEIRO
Interno(a) - 1803490 - BRUNO COSTA E SILVA NOGUEIRA
Externo(a) à Instituição - ALFREDO LIMA MOURA SILVA - UFF