Produção Nacional
Um GRASP para o problema da rotulação cartográfica de pontos: novas soluções
2009; Volume: 10; Issue: 1 Linguagem: Português
10.22456/1983-8026.1465
ISSN1983-8026
AutoresGildásio Lecchi Cravo, Glaydston Mattos Ribeiro, Luiz Antônio Nogueira Lorena,
Tópico(s)Geographic Information Systems Studies
ResumoO 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.
Referência(s)