Lagrangean relaxation bounds for point-feature cartographic label placement problem
AUTOR(ES)
Ribeiro, Glaydston Mattos, Lorena, Luiz Antonio Nogueira
FONTE
Pesquisa Operacional
DATA DE PUBLICAÇÃO
2006-12
RESUMO
O Problema Rotulação Cartográfica de Pontos (PRCP) tem como objetivo dar maior legibilidade a um mapa, colocando os rótulos dos pontos em posições legíveis. Existem abordagens distintas para o PRCP direcionadas a obter o máximo número de pontos rotulados que podem ser colocados sem sobreposição ou ainda obter o máximo número de pontos rotulados sem sobreposição considerando que todos os pontos devem ser rotulados. Esse artigo aborda o problema de uma outra forma, minimizando o número de sobreposições existentes em uma rotulação de todos os pontos. Um grafo de conflitos é definido inicialmente e uma formulação matemática de programação linear inteira binária é apresentada. Instâncias de grande porte propostas na literatura não puderam ser resolvidas por um software comercial de otimização, com isso, uma heurística é examinada considerando uma relaxação Lagrangeana feita após um particionamento inicial do grafo de conflitos em clusters. Essa decomposição permitiu obter bons limitantes inferiores e superiores para o PRCP.
ASSUNTO(S)
rotulação de pontos relaxação lagrangeana modelagem
Documentos Relacionados
- Novos algoritmos para rotulação cartográfica de pontos
- Novos algoritmos para rotulação cartográfica de pontos
- Bounds for the subsistence of a problem of heat conduction
- Relaxação lagrangeana com divisão em clusters aplicada ao problema da diversidade máxima
- Relaxação lagrangeana com divisão em clusters aplicada ao problema da diversidade máxima