@MastersThesis{Yamamoto:1998:ApBuTa,
author = "Yamamoto, Missae",
title = "Uma aplica{\c{c}}{\~a}o da Busca Tabu ao problema de
rotula{\c{c}}{\~a}o cartogr{\'a}fica de pontos",
school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
year = "1998",
address = "Sao Jose dos campos",
month = "1998-12-18",
keywords = "Busca Tabu, rotula{\c{c}}{\~a}o cartogr{\'a}fica, algoritmo de
otimiza{\c{c}}{\~a}o, produ{\c{c}}{\~a}o cartografica
automatizada, sistemas de informa{\c{c}}{\~a}o geogr{\'a}fica,
SGI, GIS, tabu search, label placement, heuristic.",
abstract = "A gera{\c{c}}{\~a}o de configura{\c{c}}{\~o}es {\'o}timas de
r{\'o}tulos em um mapa e um problema que surge com a
produ{\c{c}}{\~a}o cartogr{\'a}fica automatizada. O objetivo de
uma boa rotula{\c{c}}{\~a}o e mostrar a posi{\c{c}}{\~a}o
geogr{\'a}fica das entidades com texto associado, de forma
leg{\'{\i}}vel, e respeitando as conven{\c{c}}{\~o}es
cartogr{\'a}ficas, com qualidades est{\'e}tica e harm{\^o}nica
na apresenta{\c{c}}{\~a}o dessas informa{\c{c}}{\~o}es.
Abordamos o problema de rotula{\c{c}}{\~a}o cartogr{\'a}fica
sob o ponto de vista de otimiza{\c{c}}{\~a}o combinat{\'o}ria.
Nesta perspectiva, a rotula{\c{c}}{\~a}o cartogr{\'a}fica
pertence a classe de problemas de dif{\'{\i}}cil
solu{\c{c}}{\~a}o, conduzindo-nos a necessidade de algoritmos de
aproxima{\c{c}}{\~a}o, uma vez que n{\~a}o existe nenhum
algoritmo exato capaz de soluciona-lo em um intervalo de tempo
aceit{\'a}vel. Nossa pesquisa consistiu na avalia{\c{c}}{\~a}o
do algoritmo de otimiza{\c{c}}{\~a}o Busca Tabu aplicado a
rotula{\c{c}}{\~a}o cartogr{\'a}fica. A Busca Tabu implementada
no SCARTA, um software de produ{\c{c}}{\~a}o cartogr{\'a}fico
em desenvolvimento pela Divis{\~a}o de Processamento de Imagens
do Instituto Nacional de Pesquisas Espaciais, mostrou-se um
algoritmo eficiente, nos casos-teste real e aleat{\'o}rio, Quando
comparado a t{\'e}cnicas alternativas como {"}Simulated
Annealing{"}, algoritmo gen{\'e}tico com mascara, e outras
descritas na literatura, a Busca Tabu apresentou o melhor
desempenho em qualidade. Conclu{\'{\i}}mos que a Busca Tabu e um
m{\'e}todo recomend{\'a}vel para solu{\c{c}}{\~a}o de problema
de rotula{\c{c}}{\~a}o cartogr{\'a}fica de pontos, devido a sua
simplicidade, praticidade, efici{\^e}ncia e bom desempenho,
conjugado a capacidade de gerar solu{\c{c}}{\~o}es de qualidade
em tempo computacional aceit{\'a}vel. 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 qua
when presenting 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 of the
National Institute of Aerospace Researches, 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.",
committee = "Carvalho, Solon Ven{\^a}ncio de (presidente) and Lorena, Luiz
Antonio Nogueira (orientador) and C{\^a}mara Neto, Gilberto
(orientador) and Scrich, Cintia Rig{\~a}o and Carvalho, Paulo
Cezar Pinto",
copyholder = "SID/SCD",
englishtitle = "Tabu search application for point features cartographic label
placement problem",
label = "8583",
language = "pt",
pages = "132",
ibi = "6qtX3pFwXQZ3r59YCT/GUJkQ",
url = "http://urlib.net/ibi/6qtX3pFwXQZ3r59YCT/GUJkQ",
targetfile = "publicacao.pdf",
urlaccessdate = "27 jun. 2024"
}