@InProceedings{YamamotoCamaLore:1999:ApBuTA,
author = "Yamamoto, Missae and Camara Neto, Gilberto and Lorena, Luiz
Antonio Nogueira",
title = "Uma aplica{\c{c}}{\~a}o da busca TABU ao problema de
rotula{\c{c}}{\~a}o cartogr{\'a}fica de pontos",
year = "1999",
organization = "Congresso e Feira para Usu{\'a}rios de Geoprocessamento da
Am{\'e}rica Latina, 5. (GISBRASIL'99).",
keywords = "GEOPROCESSAMENTO, algoritmo de otimiza{\c{c}}{\~a}o,
rotula{\c{c}}{\~a}o cartogr{\'a}fica, busca tabu,
rotula{\c{c}}{\~a}o de pontos, cartas, produ{\c{c}}{\~a}o
cartogr{\'a}fica automatizada.",
abstract = "A geracao de configuracoes otimas de rotulos em um mapa e um
problema que surge com a producao cartografica autorriatizada. 0
objetivo de uma boa rotulacao e mostrar a posicao geografica das
entidades co texto associado, de forma legivel, e respeitando as
convencoes cartograficas, com qualidades estetica e harmonica na
apresentacao dessas informacoes. Abordamos o problema de rotulacao
cartografica sob o ponto de vista de otimizacao combinatoria.
Nesta perspectiva, a rotulacao cartografica pertence a classe de
problemas de dificil solucao, conduzindo-nos a necessidade de
algoritmos de aproximacao, uma vez que nao existe nenhum algoritmo
exato capaz de soluciona-lo em um intervalo de tempo aceitavel.
Nossa pesquisa consistiu na avaliacao do algoritmo de otimizacao
Busca Tabu aplicado a rotulacao cartografica. A Busca Tab
implementada no SCARTA, um software de producao cartografico em
desenvolvimento pela Divis{\~a}o de Processamento de Imagens
(DPI/INPE), mostrou-se um algoritmo eficiente, nos casos-teste
real e aleatorio. Quando comparado a tecnicas alternativas como
{"}Simulated Annealing{"}, algoritmo genetico com mascara, e
outras descritas na literatura, a Busca Tabu apresentou o melhor
desempenho em qualidade. Concluimos que a Busca Tabu e um metodo
recomendavel para solucao de problema de rotulacao cartografica de
pontos, devido a sua simplicidade, praticidade, eficiencia e bom
desempenho, conjugado a capacidade de gerar solucoes de qualidade
em tempo computacional aceitavel. ABSTRACT: The generation of
better label placement configurations in maps is a problem that
comes up in automated cartographic production. The objective of a
good label placement is to show the geographic position of the
features with their corresponding texts clearly, respecting the
cartographic conventions, with an esthetic and a harmonious
quality when present , ing the information. We approached the
label placement problem from a combinatorial optimization point of
view. In this perspective, the cartographic label placement
belongs to a problem area of difficult solution, leading us to the
need of approximation algorithms as there is no exact algorithm
that is able to solve this problem within an acceptable amount of
time. Our research consisted in the evaluation of the tabu search
optimization algorithm applied to cartographic label placement.
The tabu search implemented in SCARTA, a cartographic production
software, in development by the Image Processing Division
(DPI/INPE), proved to be an efficient algorithm, in real and
random test cases. When compared with alternative techniques such
as {"}simulated annealing{"}, genetic algorithm with mask and
others described in literature, the tabu search had the best
performance in quality. We concluded that tabu search is a
recommended method to solve cartographic label placement problem
of point features, due to its simplicity, practicality, efficiency
and good performance along with its ability to generate quality
solutions in acceptable computational time.",
conference-location = "Salvador",
conference-year = "1999",
copyholder = "SID/SCD",
label = "8661",
language = "pt",
targetfile = "1998_yamamoto.pdf",
urlaccessdate = "27 jun. 2024"
}