Dispersão discreta e decomposição lagrangeana desbalanceada para o problema de rotulação cartográfica de pontos - Sóstenes Pereira Gomes (2015)
Este trabalho aborda o Problema de Rotulação Cartográfica de Pontos (PRCP), que é um problema de otimização combinatória, demonstrado na literatura ser NP-difícil. Considera-se que quando todos os pontos devem ser rotulados e sobreposições de rótulos são inevitáveis, o mapa pode ser mais legível se os rótulos em conflito são posicionados de maneira dispersiva, isto é, se os rótulos são posicionados o mais distante possível. Neste contexto, é apresentada uma nova abordagem para o problema, denominada Dispersão Discreta, já utilizada em Problemas de Localização de Facilidades em diversos trabalhos da literatura. Com esta nova abordagem, o PRCP foi formulado como um Problema de programação inteira mista, de maneira a considerar as distâncias entre posições candidatas. Um algoritmo genético construtivo também foi desenvolvido, para obter resultados em instâncias mais complexas. Por fim, é proposta uma Decomposição Lagrangeana desbalanceada, que permitiu obter a solução ótima de diversas instâncias do PRCP, além de provar a otimalidade dos resultados já existentes de outras instâncias.