Hiper-heurísticas e métodos exatos aplicados ao problema do posicionamento de pontos de acesso em ambientes internos

Abstract

O crescente uso de dispositivos móveis e aplicações de alta demanda torna o planejamento eficiente de redes Wi-Fi em ambientes internos um desafio relevante. O Problema do Posicionamento de Pontos de Acesso (APPP) consiste em determinar a quantidade, localização e configuração de Access Points (APs), de modo a garantir cobertura e capacidade adequadas, minimizando custos. Trata-se de um problema de otimização NP-difícil, cuja complexidade limita a aplicação de métodos exatos em instâncias de grande porte. Este trabalho propõe e avalia duas abordagens complementares para o APPP: hiper-heurísticas e métodos de otimização exata. Na vertente heurística, foram desenvolvidas hiper-heurísticas online e offline, além da aplicação do algoritmo BRKGA, incorporando novas heurísticas de construção e busca local específicas para o problema. Os experimentos demonstraram que as hiper-heurísticas obtiveram valores de função objetivo menores ou iguais aos melhores resultados da literatura em instâncias de médio e grande porte, com diferenças estatisticamente significativas (p < 0,05) pelo teste de Wilcoxon. Na vertente exata, foram propostas duas formulações matemáticas baseadas em cobertura de pontos e cobertura de regiões, incorporando modelos de propagação e restrições realistas de capacidade e canais. Testes conduzidos em 148 instâncias reais indicaram que a formulação baseada em regiões apresenta melhor escalabilidade computacional, com menor incidência de timeout em instâncias maiores e reduções de até 97% no número de APs em relação à formulação baseada em pontos. Enquanto métodos exatos se mostraram viáveis para instâncias pequenas e médias, as abordagens heurísticas apresentaram melhor desempenho em cenários de maior porte. Os resultados evidenciam que a combinação de hiper-heurísticas e modelagens exatas constitui uma estratégia eficaz para o APPP, contribuindo com novas heurísticas, formulações matemáticas e análises comparativas fundamentadas estatisticamente.