Um GRASP para o problema da rotulação cartográfica de pontos: novas soluções

Gildásio Lecchi Cravo, Glaydston Mattos Ribeiro, Luiz Antonio Nogueira Lorena

Resumo


O Problema da Rotulação Cartográfica de Pontos (PRCP) é uma importante etapa no processo de geração de mapas em um sistema de informações geográficas e consiste em posicionar os rótulos dos pontos em posições que não ocasionam sobreposições. O PRCP é um problema da classe NP-difícil e por isso, várias abordagens foram propostas usando heurísticas/metaheurísticas para resolvê-lo no sentido de se obter soluções polinomiais e de boa qualidade. Seguindo essa idéia, esse trabalho propõe um GRASP para o PRCP baseado em seu grafo de conflitos. Os resultados encontrados para instâncias da literatura mostram que essa metaheurística é uma boa estratégia, pois a mesma produziu soluções de melhor qualidade que todos os resultados informados na literatura, em um tempo de computacional razoável.

Palavras-chave


Pesquisa Operacional

Texto completo:

PDF


DOI: https://doi.org/10.22456/1983-8026.1465