Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: O Problema de Alocação de Pontos de Controle

Data: 04/09/2025
Horário: 13h
Local: Sala de Seminário – Bloco 952

Resumo:

Introduzimos formalmente o Problema de Alocação de Pontos de Controle Multi-período com Conflitos (PAPCMC), que aloca unidades de controle indivisíveis e móveis em localizações discretas ao longo de um horizonte temporal finito, maximizando o peso total das alocações sob restrições de exclusividade, compatibilidade e deslocamento. Mostramos que PAPCMC pode ser reduzido a um Problema de Atribuição com Conflitos (Assignment Problem with Conflicts (APC)). Adicionalmente, provamos tratar-se de um um problema NP-difícil, mesmo com apenas dois períodos de tempo, a partir de uma redução do problema (3, B2)-SAT. Modelamos o problema por dois modelos de programação linear inteira alternativos: BLP1 , que traduz uma solução como um conjunto independente máximo, e BLP2, que representa o PAPCMC como um problema de fluxo de custo máximo com restrições de conflito. Mostramos que BLP2 possui relaxação linear pelo menos tão forte quanto a de BLP1 e que pode ser resolvido em tempo polinomial quando todas as equipes compartilham escalas idênticas. Além disso, sua estrutura em blocos permite resolver subproblemas por equipe, inspirando heurísticas eficientes. Projetamos três heurísticas principais — Heurística Gulosa – União de Caminhos (HGC), Heurística Gulosa – União de Emparelhamentos (HGE) e Heurística Lagrangiana (HL) — além de versões penalizadas de Greedy Randomized Adaptive Search Procedure (GRASP) e Ant Colony Optimization (ACO). Criamos um conjunto de 15198 instâncias realistas a partir de dados públicos da cidade de Nova Iorque. Nos testes com tempo limite de 2 minutos, HGC superou HGE em 96,3% das instâncias; HL atingiu ótimos em mais da metade das instâncias e reduziu o gap médio para 1%. A inclusão de Lower Cutoff dada pelas heurísticas se mostrou eficiente. O BLP2 obteve 94,1% de ótimos, cortou o tempo médio em 40% e o gap em 35% frente ao BLP1 . Mesmo com limite de 1h de execução em casos difíceis, BLP2 manteve superioridade. Concluímos que a incorporação dos limites inferiores das heurísticas reduz o tempo total de computação e aumenta o número de instâncias resolvidas otimamente: adote HGC quando o objetivo é encontrar ótimo e HL para melhores garantias de qualidade do limite inferior. Em virtude do desempenho global, BLP2 é a abordagem recomendada em cenários operacionais.

Banca examinadora: