@InProceedings{CravoRibeLore:2006:GREfPr,
author = "Cravo, Gild{\'a}sio Lecchi and Ribeiro, Glaydston Mattos and
Lorena, Luiz Antonio Nogueira",
affiliation = "{Faculdade de Aracruz (UNIARACRUZ)} and {Instituto Nacional de
Pesquisas Espaciais (INPE)} and {Instituto Nacional de Pesquisas
Espaciais (INPE)}",
title = "Um GRASP Eficiente para o Problema da Rotula{\c{c}}{\~a}o
Cartogr{\'a}fica de Pontos",
booktitle = "Anais...",
year = "2006",
organization = "Simp{\'o}sio Brasileiro de Pesquisa Operacional, 38. (SBPO).",
keywords = "GRASP, rotula{\c{c}}{\~a}o cartogr{\'a}fica de pontos,
heur{\'{\i}}stica, otimiza{\c{c}}{\~a}o combinat{\'o}ria, map
labeling, heuristic, combinatorial optimization.",
abstract = "O Problema da Rotula{\c{c}}{\~a}o Cartogr{\'a}fica de Pontos
(PRCP) {\'e} uma importante etapa no processo de
gera{\c{c}}{\~a}o de mapas em sistema de informa{\c{c}}{\~o}es
geogr{\'a}ficas e consiste em posicionar os r{\'o}tulos dos
pontos em posi{\c{c}}{\~o}es que n{\~a}o ocasionam
sobreposi{\c{c}}{\~o}es. O PRCP {\'e} um problema da classe NP
dif{\'{\i}}cil e por isso, v{\'a}rias abordagens foram
propostas usando heur{\'{\i}}sticas/metaheur{\'{\i}}sticas
para resolv{\^e}-lo no sentido de se obter solu{\c{c}}{\~o}es
polinomiais e de boa qualidade. Seguindo essa id{\'e}ia, esse
trabalho prop{\~o}e um GRASP para o PRCP baseado em seu grafo de
conflitos. Os resultados encontrados para inst{\^a}ncias da
literatura mostram que essa metaheur{\'{\i}}stica {\'e} uma boa
estrat{\'e}gia, pois a mesma produziu solu{\c{c}}{\~o}es de
melhor qualidade que todos os resultados informados na literatura,
e em um tempo de computacional razo{\'a}vel. ABSTRACT: The
point-feature cartographic label placement problem (PFCLP) is an
important task in map generation process mainly in geographic
information systems. It consists in placing point labels in clear
and legible positions in a map or diagram. The PFCLP is a NP-Hard
problem consequently in the literature, there are several
approaches using heuristics/metaheuristics for producing good
solutions in reduced times. Following this idea, in this paper we
proposed a GRASP that uses the conflict graph produced by the
PFCLP. Considering instances proposed in the literature, our
results show that this metaheuristic is a good strategy. We had
better solution than all those reported in the literature in
reasonable computational times.",
conference-location = "Goi{\^a}nia, Brasil",
conference-year = "12-15 set.",
copyholder = "SID/SCD",
language = "pt",
organisation = "SOBRAPO",
targetfile = "Um GRASP eficiente.pdf",
urlaccessdate = "27 jun. 2024"
}