646 - UMA APLICAÇÃO DA BUSCA TABU AO PROBLEMA DE ROTULAÇÃO CARTOGRÁFICA DE PONTOS

UMA APLICAÇÃO DA BUSCA TABU AO PROBLEMA DE ROTULAÇÃO CARTOGRÁFICA DE PONTOS

Missae Yamamoto
Gilberto Câmara
Luiz Antonio Nogueira Lorena

missae@dpi.inpe.br, gilberto@dpi.inpe.br e lorena@lac.inpe.br

Instituto Nacional de Pesquisas Espaciais (INPE)
Av. dos Astronautas, 1758
Jrd. Da Granja, São José dos Campos-SP Brasil
CEP 12227-010 tel. (012)345-6523 fax. (012)345-6468

RESUMO

A geração de configurações ótimas de rótulos em um mapa é um problema que surge com a produção cartográfica automatizada. O objetivo de uma boa rotulação é mostrar a posição geográfica das entidades com texto associado, de forma legível, e respeitando as convenções cartográficas, com qualidades estética e harmônica na apresentação dessas informações. Abordamos o problema de rotulação cartográfica sob o ponto de vista de otimização combinatória. Nesta perspectiva, a rotulação cartográfica pertence à classe de problemas de difícil solução, conduzindo-nos à necessidade de algoritmos de aproximação, uma vez que não existe nenhum algoritmo exato capaz de solucioná-lo em um intervalo de tempo aceitável. Nossa pesquisa consistiu na avaliação do algoritmo de otimização Busca Tabu aplicado à rotulação cartográfica. A Busca Tabu implementada no SCARTA, um software de produção cartográfico em desenvolvimento pela Divisão de Processamento de Imagens (DPI/INPE), mostrou-se um algoritmo eficiente, nos casos-teste real e aleatório. Quando comparado a técnicas alternativas como "Simulated Annealing", algoritmo genético com máscara, e outras descritas na literatura, a Busca Tabu apresentou o melhor desempenho em qualidade. Concluímos que a Busca Tabu é um método recomendável para solução de problema de rotulação cartográfica de pontos, devido a sua simplicidade, praticidade, eficiência e bom desempenho, conjugado à capacidade de gerar soluções de qualidade em tempo computacional aceitá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 quality 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 (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.

1. INTRODUÇÃO

Rotulação cartográfica refere-se ao processo de inserção de texto em documento cartográfico, aqui denominado "carta", num ambiente de sistemas de informação geográfica (SIG), que é composto por cinco subsistemas: interface; entrada de dados; visualização e plotagem; transformação, consulta e análise espacial; e gerência de dados espaciais (Figura 1). A rotulação cartográfica é tratada no subsistema de visualização e tem se mostrado um dos maiores desafios para a cartografia computadorizada, pois posicionar os textos requer que associação não ambígua entre o texto e a entidade correspondente seja alcançada, que não haja sobreposição entre os textos ou entre texto e entidades, que sejam respeitadas as convenções e preferências cartográficas, que o tempo de processamento seja irrisório e que um alto nível de harmonia e qualidade sejam alcançados.

Figura 1 - O pacote de software de um SIG
FONTE: Câmara (1995, p. 2-6).

Em cartografia são identificados três tipos de rotulação: rotulação de ponto (cidades, pico de montanhas, escolas, hospitais, ...), rotulação de linhas (rios, estradas, ...) e rotulação de área (oceanos, países, estados, ...). O presente artigo aborda apenas a rotulação cartográfica de pontos sob o ponto de vista de otimização combinatória e, como tal, posições candidatas, preferência cartográfica e função objetivo merecem a atenção. Entende-se por posições candidatas o conjunto de todas as possíveis posições que o rótulo de um determinado ponto pode ocupar. A Figura 2 mostra um conjunto de 4 posições candidatas para o rótulo de um ponto. Cada retângulo representa uma região em que o rótulo pode ser colocado e os números mostrados indicam a preferência cartográfica; quanto menor for o número, maior é a preferência.

A função objetivo é uma função a ser otimizada que tem por meta medir a qualidade da rotulação, diferenciando elementos bons dentre as posições candidatas existentes. Geralmente a qualidade da rotulação depende do número de rótulos em conflito e preferência cartográfica.

Se considerarmos 2 posições candidatas (L0 e L1) para cada ponto pi, onde i varia entre 1 e o número de pontos, veremos que o número de configurações possíveis aumenta exponencialmente de acordo com o número de pontos do leiaute (Figura 3). Como o conjunto de possíveis soluções é finito, teoricamente poderiamos selecionar a solução ótima por enumeração, mas quando o número de pontos é grande a proposta torna-se inviável, pois o problema introduz uma gama muito grande de possibilidades, configurando uma explosão combinatória de soluções possíveis, e uma consequente explosão no tempo necessário para encontrar a solução ótima e Marks e Shieber (1993) mostraram que o problema de rotulação de pontos é NP-difícil. Portanto, nos necessitamos de heurísticas e metaheurísticas que não buscam a solução exata, mas uma solução suficientemente boa em termos de custo.

Várias heurísticas e metaheurísticas tem sido usado ao longo dos anos para resolver o problema de rotulação de pontos tais como: busca exaustiva, algoritmo guloso, "discrete gradient descent", algoritmo de Hirsch, "simulated annealing" e outros que foram revistos por Christensen et al. (1995) e algoritmo genético com máscara descrito em Verner et al. (1997). Em Yamamoto (1998), as técnicas citadas foram revistas e foi proposto um novo algoritmo para a solução do problema. Neste artigo nos vamos apresentar o algoritmo busca tabu para resolver o problema de rotulação cartográfica de pontos. O restante do artigo está organizado da seguinte forma. A seção 2, apresenta o algoritmo de otimização busca tabu para solucionar o problema de rotulação de pontos. A seção 3, apresenta e discute os resultados obtidos da aplicação de busca tabu à rotulação de pontos, tanto em dados reais quanto em um conjunto padrão de dados sugerido na literatura. A comparação do algoritmo busca tabu com os demais algoritmos descritos na literatura é também apresentado nesta seção. As conclusões são apresentadas na seção 4.

2. BUSCA TABU PARA ROTULAÇÃO CARTOGRÁFICA DE PONTOS

A busca tabu ("Tabu Search") é um procedimento heurístico proposto por Fred Glover para resolver problemas de otimização combinatória. A idéia básica é evitar que a busca por soluções ótimas termine ao encontrar um mínimo local. (Glover. 1989a, 1989b, 1990; Laguna. 1994; Glover et al. 1995, 1997). Este tipo de algoritmo faz uma busca agressiva no espaço de soluções do problema de otimização com o intuito de obter sempre as melhores alternativas que não sejam considerados tabu. A heurística busca tabu algumas vezes aceita a solução considerado tabu, baseado no critério de aspiração que determina quando as restrições tabu podem ser ignorados. Descrição geral do algoritmo busca tabu para PFLP será descrito a seguir:

Pré-computar todas as possíveis sobreposições entre rótulos, registrando para cada rótulo potencial uma lista de rótulos em sobreposição.
Gerar uma configuração inicial, rotulando cada ponto com a posição candidata de melhor preferência cartográfica.
Repetir por um número de iterações ou até alcançar um estado de não sobreposição.

	Criar uma lista de soluções alternativas.
	Escolher o melhor candidato da lista, baseado na função objetivo, levando em consideração a lista tabu e o critério de aspiração.
	Realizar a mudança de configuração, designando a solução obtida como sendo a nova solução corrente. Cada mudança de configuração consiste em modificar a posição de um rótulo.
	Atualizar a lista tabu.

A implementação do algoritmo busca tabu deste artigo envolve 6 componentes: função objetivo, lista de candidato, mudança de configuração, memória de longo prazo, lista tabu e critério de aspiração que serão descritos a seguir.

2.1 FUNÇÃO OBJETIVO

A busca tabu aqui utilizada é totalmente determinística e seleciona agressivamente os melhores movimentos admissíveis, logo existe a necessidade de examinar e comparar as opções de movimento, o que acarreta um grande número de cálculos para o seu sucesso, principalmente quando o número de pontos a ser rotulado for grande. Assim sendo as melhores funções objetivo são aquelas em que o custo pode ser computado facilmente, tornando assim a busca eficiente, ao mesmo tempo que soluções de qualidade possam ser alcançadas beneficiando-se da melhor configuração de rótulos.

E a função objetivo de minimização adotada foi:

Figura 4 - calculo de conflitos

2.2 LISTA TABU

A lista tabu é um componente essencial do algoritmo, e armazena as ultimas localizações onde a posição do label tem sido mudado. Em Yamamoto (1998), nos usamos uma lista dinâmica , pois o problema de rotulação de pontos necessita de uma lista tabu grande no início para resolver os conflitos entre os rótulos de pontos distintos da carta, evitando assim que se concentre em resolver os conflitos só de uma determinada região da carta. Contudo, quando o número de conflitos diminui, existe a necessidade de uma lista tabu pequena, uma vez que a busca deve ser realizada em algumas regiões da carta, visando apenas um ajuste final

O tamanho da lista tabu adotado foi de 7 + INT(0.25 * num. de rótulos em conflito) pois assim com o decorrer das iterações o número de rótulos em conflito diminui e em consequência o tamanho da lista tabu. O coeficiente 0.25 assim como o recálculo do tamanho da lista tabu a cada 50 iterações foram estabelecidas depois de testes e experimentos que foram feitos em configurações com 100, 250, 500, 750 e 1000 pontos (detalhes em Yamamoto , 1998).

2.3 LISTA DE CANDIDATOS

Para o PFLP, cada solução consiste de um conjunto de pares (ponto, rótulo) e esta associado a um custo. Em geral (dependendo dos fatores a 1 e a 2) soluções de custo alto apresentam um grande número de sobreposições e o rótulos não se encontram nas melhores posições cartográficas. Com o intuito de otimizar agressivamente a função objetivo, a lista de candidatos é composto de soluções que apresentarão custo baixo na próxima configuração. Nas literaturas do algoritmo tabu, a lista de candidatos é também referenciado como vizinhança.

A cada 50 iterações, o tamanho da lista de candidatos foi recalculado usando a expressão: 1 + INT(0.05 * num. de rótulos em conflito). O fator 0.05 foi escolhido depois de testes feitos em 9 diferentes configurações de 1000 pontos. A média de rótulos sem conflito das 9 diferentes configurações para os fatores 0.03, 0.04, 0.05, 0.06 e 0.07 mostraram que o fator 0.05 obteve os melhores resultados (detalhes em Yamamoto, 1998).

2.4 MUDANÇA DE CONFIGURAÇÃO

A cada mudança de configuração, todas soluções da lista de candidatos são testados. O candidato que apresentar o maior decréscimo na função objetivo é escolhido. Soluções gerados por pontos que faz parte da lista tabu não são aceitos, e a próxima melhor alternativa é então selecionada. Algumas vezes o critério de aspiração descrito a seguir , é usado para ignorar a restrição tabu.

2.5 CRITÉRIO DE ASPIRAÇÃO

Em algumas situações, é necessário considerar alternativas que são parte da lista tabu. Em tais casos, o critério de aspiração é usado para ignorar a restrição tabu em dois casos:

Uma solução é selecionada se ela apresentar um custo menor do que a melhor solução até então encontrada.

Se todas as soluções candidatas foram gerados por pontos, que tiveram a posição de rótulo mudado e faz parte da lista tabu e o critério de aspiração acima não foi satisfeito, então o candidato com o menor status tabu é selecionado.

2.6 MEMÓRIA DE LONGO PRAZO

Com frequência, os custos de diferentes soluções são iguais, resultando na presença das mesmas alternativas na lista de candidatos. Portanto, tem se a necessidade de diversificar a busca. Nos usamos a estratégia de memória de longo prazo que conta o número de vezes que a posição do rótulo de um ponto tem sido mudado e após 50 iterações consecutivas divide-se o valor acumulado de cada ponto pelo valor máximo, obtendo então a frequência normalizada. Esta informação é usado para aplicar penalidades aos pontos que não causam melhora, fazendo com que perca a sua atratividade. O custo C(i) de cada ponto "i" foi então modificado para:

Onde a frequência normalizada (i) é um instrumento para diversificar a busca.

3. RESULTADOS

Com o objetivo de verificar o desempenho do algoritmo busca tabu com relação a dados reais, foram utilizados os dados disponíveis em Knuth (1993). Trata-se de um conjunto de 128 pontos referente às cidades de uma região dos Estados Unidos da América e seus respectivos nomes de comprimento variável, o que torna o teste bastante realístico. A área considerada em coordenadas geográficas foi: longitude (O 123 0 0 ~ O 73 0 0), latitude (N 25 0 0 ~ N 51 0 0) e projeção LAMBERT / HAYFORD.

Com os dados reais obtidos foram feitos testes com diferentes valores de a 1 (que manipula o nível de consideração a ser dada aos rótulos em conflito) e a 2 (que manipula o nível de consideração a ser dada a preferência cartográfica). Para os testes foram considerados:

tamanho da lista tabu = 7 + INT(0.25 * num. de rótulos em conflito),

tamanho da vizinhança = 1 + INT (0.05 * num. de rótulos em conflito),

Número de iterações para recálculo = 50,

altura do caracter que compõe o texto = 1.0 mm e

posições candidatas = 8.

Os resultados dos testes estão reportados na Tabela 3.1.

TABELA 3.1 – RESULTADOS DOS TESTES PARA DIFERENTES VALORES DE a 1 E a 2

leiaute	USA1	USA2	USA3	USA4
a 1	1	1	1	3
a 2	10	5	1	1
Número de iterações	324	140	28	28
Num. de rótulos em conflito	26	4	0	0

Verificou-se que quando o nível de consideração da preferência cartográfica é bastante grande em relação ao nível de consideração dada ao número de rótulos em conflito, o número de rótulos em conflito é grande, mas é possível verificar que os rótulos ocupam a melhor posição cartográfica, na medida do possível. Por outro lado, a medida que o nível de consideração da preferência cartográfica diminui e o nível de consideração do número de rótulos em conflito aumenta, o número de rótulos em conflito diminui, mas verifica-se que os rótulos ocupam qualquer uma das 8 posições candidatas. A Figura 5 apresenta um exemplo de leiaute e a Figura 6 apresenta uma ampliação da área de agrupamento do leiaute da Figura 5. Resultados dos testes para diferentes altura de caracter e diferentes escalas estão descritos em Yamamoto (1998).

Christensen et al. (1995) e Verner et al. (1997) compararam vários algoritmos usando um conjunto padrão de dados gerados randomicamente: região de tamanho 792 x 612 unidades, rótulo de tamanho fixo 30 x 7 unidades e folha de papel de tamanho 11 x 8.5 polegada.

Nos usamos o conjunto padrão de pontos e simulamos o mesmas condições descritas em Christensen et al. (1995) e Verner et al. (1997) para comparar o nosso algoritmo busca tabu com os outros algoritmos da literatura:

	Número de pontos: n = 100, 250, 500, 750, 1000
	Para cada n, nos geramos 25 configurações diferentes de distribuição aleatória de pontos através do uso de diferentes sementes.
	Para cada n calcularmos a média percentual do número de rótulos sem conflito das 25 configurações;
	Não foi determinada nenhuma penalidade para os rótulos que se situam além do limite da região, uma vez que Verner et al. (1997) também não considerou;
	Foram consideradas 4 posições candidatas.
	Não foi considerada a preferência cartográfica, uma vez que Verner et al. (1997) também não considerou;
	Não houve seleção de pontos ( não deleta ponto ou rótulo que estiver em conflito na configuração final).
	Os parâmetros utilizados pela busca tabu foram:

Tamanho da lista tabu: 7 + INT(0.25 * num. de rótulos em conflito)

	Tamanho da vizinhança: 1 + INT (0.05 * num. de rótulos em conflito)
	Número de iterações para recalculo: 50

A média obtida da aplicação do busca tabu às 25 configurações estão mostrados na (Tabela 3.2), onde as linhas se referem a:

	Iteração: número médio de iterações para alcançar o estado de não conflito entre os rótulos ou o estado de conflito mínimo, respeitando a iteração máxima dada que foi de 50 para 100 pontos, 100 para 250 pontos, 8000 para 500 pontos, 15000 para 750 pontos e 30000 para 1000 pontos.
	Rótulos em conflito: número médio de rótulos em estado de conflito
	Tempo: tempo médio de processamento do algoritmo busca tabu para alcançar o estado de não conflito ou conflito mínimo entre os rótulos. O tempo mostrado se refere apenas ao tempo de processamento do algoritmo busca tabu, ou seja o tempo usado para o pré-computação dos conflitos existentes entre os rótulos não foi contabilizado.
	Resultados(%): trata-se da média percentual do número de rótulos sem conflito das 25 configurações.

TABELA 3.2 – RESULTADOS OBTIDOS POR BUSCA TABU USANDO O CONJUNTO

PADRÃO DE DADOS

Num. de pontos	100 pontos	250 pontos	500 pontos	750 pontos	1000 pontos
Número de Iterações	7	45	450	6645	21410
Rótulos em conflito	0	0	4	24	100
Tempo (seg.)	0.01	0.15	3.95	102	732
Resultados (%)	100.00	100.00	99.26	96.76	90.00

Um leiaute com configuração de rótulos inicial e configuração de rótulos após aplicação da busca tabu para 1000 pontos são apresentados na Figura 7 e 8.

Com relação a todos os algoritmos de otimização citados na literatura, o algoritmo busca tabu mostrou resultados superiores como pode ser visto na (Tabela 3.3), onde as colunas se referem ao percentual médio de rótulos sem conflitos para 100, 250, 500, 750 e 1000 pontos, por diferentes algoritmos da literatura e as linhas mostram o percentual médio de rótulos sem conflito alcançados pelos algoritmos de otimização testados na literatura por Christensen et al. (1995) (busca exaustiva, algoritmo guloso, "gradient descent", "2-opt gradient descent’, "3-opt gradient descent", algoritmo de Hirsch, Zoraster e "simulated Annealing"), por Verner et al. (1997) (GA sem máscara e GA com máscara) e busca tabu.

TABELA 3.3 – RESULTADOS OBTIDOS POR VÁRIOS ALGORITMOS USANDO

O CONJUNTO PADRÃO DE DADOS

Algoritmo	100 pontos	250 pontos	500 pontos	750 pontos	1000 pontos
Busca tabu	100.00	100.00	99.26	96.76	90.00
GA com máscara	100.00	99.98	98.79	95.99	88.96
GA sem máscara	100.00	98.40	92.59	82.38	65.70
"Simulated annealing"	100.00	99.90	98.30	92.30	82.09
Zoraster	100.00	99.79	96.21	79.78	53.06
Hirsch	100.00	99.58	95.70	82.04	60.24
"3-Opt gradient descent"	100.00	99.76	97.34	89.44	77.83
"2-Opt gradient descent"	100.00	99.36	95.62	85.60	73.37
"Gradient descent"	98.64	95.47	86.46	72.40	58.29
Algoritmo guloso	95.12	88.82	75.15	58.57	43.41
Busca exaustiva	84.56	65.63	44.06	29.06	19.53

Adaptada de Verner et al. (1997, p. 273).

O tempo de processamento médio gasto por algoritmo genético com máscara para resolver o problema de rotulação de 100, 250, 500, 750 e 1000 pontos foi de 6, 49, 414, 1637 e 7256 segundos, usando uma estação SUN-SPARC 10. A busca tabu resolveu o problema em 0.01, 0.15, 3.95, 102 e 732 segundos usando uma estação SUN-SPARC 20. Entretanto o tempo de pré- computação gasto não foi incluído.

4. CONCLUSÕES

A rotulação de pontos é um problema de grande importância prática em geoprocessamento e cartografia automatizada.

O nosso trabalho propôs e avaliou o algoritmo de otimização busca tabu aplicado a um problema de rotulação de pontos, Os testes computacionais usando o conjunto padrão de pontos gerados aleatoriamente com as mesmas condições descritas por Christensen et al. (1995) e Verner et al. (1997) mostraram que busca tabu apresentou o melhor desempenho do que os outros métodos apresentados na literatura. Isso indica que a busca tabu é um método recomendado para resolver a rotulação cartográfica de pontos, por sua abilidade de gerar soluções de alta qualidade .

O outro objetivo foi a de avaliar o algoritmo busca tabu com relação a dados reais a fim de verificar o seu comportamento em relação a ocorrência natural de distribuição de pontos, uma vez que o agrupamento natural dos pontos e a relação entre a área do mapa considerado, o tipo de papel e a escala em uso dificulta bastante a qualidade da rotulação. Outros fatores que afetam a qualidade da rotulação são o comprimento variável do texto, a altura dos caracteres que compõe os textos dos dados reais e a preferência cartográfica. Foram feitos então testes para verificar a influência da preferência cartográfica manipulando o seu nível de consideração em relação ao nível de consideração dados aos rótulos em conflito. Os resultados mostraram que quanto maior o nível de consideração dado à preferência cartográfica, maior é a dificuldade do algoritmo em alcançar o estado de não conflito entre os rótulos, mas ao mesmo tempo, os rótulos em geral se encontram nas melhores posições, segundo o critério de preferência cartográfica adotada. Finalmente, é possível afirmar que o desempenho da busca tabu foi boa, mesmo quando aplicado a dados reais onde existe um agrupamento natural dos pontos com rótulos de comprimento variável.

O código foi implementado usando uma estação de trabalho Sun Sparc 20, sistema operacional UNIX versão solaris 2.5, compilador C++ versão 4.0.1, SIG SCARTA e SPRING versão 3.0 (Câmara, 1996)

Figura5 – USA3

Figura6 – "zoom" da área de agrupamento

Figura7 – Configuração inicial (703 conflitos)

Figura-8 Configuração final (77 conflitos)

REFERÊNCIAS BIBLIOGRÁFICAS

Câmara, G.; Souza R.C.M.; Freitas U.M.; Garrido J.C.P. Spring integrating remote sensing and gis with object-oriented data modelling. Computers and graphics, 15:395-403, 1996.

Câmara, G. Modelos, Linguagens e Arquiteturas para Bancos de Dados Geográficos. Tese (Doutorado em Computação Aplicada) – Instituto Nacional de Pesquisas Espaciais, São José dos Campos, 1995.

Chistensen, J.; Marks, J.; Shieber, S. An empirical study of algorithms for point-feature label placement. ACM Transactions on Graphics, v. 14, n. 3, p. 203-232, July, 1995.

Christensen, J.; Marks, J.; Shieber, S. Placing Text Labels on Maps and Diagrams. London, Academic Press, 1993. 10p.

Edmondson, S.; Christensen, J.; Marks, J.; Shieber, S. A general cartographic labeling algorithm. December, 1996. 19p.

Glover, F. Tabu search – part I. ORSA Journal on Computing, v. 1, n. 3, p. 190-206, Summer 1989a.

Glover, F. Tabu Search – part II. ORSA Journal on Computing, v. 2, n. 1, p.4-32, Winter 1989b.

Glover, F. Tabu Search – a tutorial. Interfaces, v. 20, n. 4, p. 74-94, July-Aug. 1990.

Glover, F.; Laguna, M. Tabu search. In: Colin, R. R. Modern heuristic techniques for combinatorial problems. New York, McGraw-Hill, 1995. p. 70-150.

Glover, F. Tabu search. Boston, Kluwer, 1997. 408p.

Hirsch, S. A. An algorithm for automatic name placement around point data. American Cartographer, v. 9, n. 1, p. 5-17, 1982.

Knuth, D. E. The stanford graphBase, a platform for combinatorial computing. New York, Addison-Wesley, 1993. 576p.

Laguna, M. A guide to implementing tabu search. Investigación Operativa, v. 4, p.5-25, 1994.

Marks J.; Shieber S. The computational complexity of cartographic label placement. Technical report, Center for Research in Computing Technology, Harvard University, 1993.

Verner, O. V.; Wainwright, R. L.; Schoenefeld, D. A. Placing text labels on maps and diagrams using genetic algorithms with masking. INFORMS Journal on Computing, v. 9, p. 266-275, 1997.

Yamamoto, M. Uma aplicação da busca tabu ao problema de rotulação cartográfica de pontos. São José dos Campos. 116p. Dissertação (Mestrado em Computação Aplicada) – Instituto Nacional de Pesquisas Espaciais, 1998.

Zoraster, S. Integer programming applied to the map label placement problem. Cartographica, v. 23, n. 3, p . 16-27, 1986.

Zoraster, S. The solution of large 0-1 integer programming problems encountered in automated cartography. Operations Research, v. 38, n. 5, p. 752-759, Sept.-Oct. 1990.