Heurísticas para o problema de rotulação cartográfica de pontos e coloração de vértices com pesos
AUTOR(ES)
Celso de Oliveira
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
16/03/2012
RESUMO
Esta dissertação propõe uma heurística Variable Neighbourhood Descent, que alterna entre vizinhanças que são exploradas por um algoritmo de Backtracking, aplicada ao problema de rotulação cartográfica de pontos e ao problema de coloração de vértices com pesos. O primeiro consiste em posicionar rótulos em regiões de um mapa cartográfico, proporcionando uma boa visualização pela redução das sobreposições de rótulos. O segundo consiste em atribuir cores aos vértices de um grafo tal que vértices adjacentes não recebam a mesma cor. Cada vértice do grafo possui um peso e para cada cor é atribuído um peso que corresponde ao peso máximo dos vértices coloridos com essa cor. O objetivo do problema de coloração de vértices com pesos é minimizar a soma dos pesos das cores utilizadas. Os experimentos computacionais mostraram que a heurística proposta é rápida e eficiente, indicando que pode ser avaliada como técnica para resolver problemas de otimização combinatória.
ASSUNTO(S)
ACESSO AO ARTIGO
http://hdl.handle.net/1843/ESBF-8SVMRYDocumentos Relacionados
- Novos algoritmos para rotulação cartográfica de pontos
- Novos algoritmos para rotulação cartográfica de pontos
- Heurísticas para o Problema de Dimensionamento de Lotes com Máquinas Paralelas Flexíveis
- Heuristicas para o problema de estoque e roteamento de veiculos
- Heurísticas e algoritmo exato para o problema de roteamento de veículos com coleta e entrega simultâneas
