Heurísticas para o problema de rotulação cartográfica de pontos e coloração de vértices com pesos

Esta dissertacao propoe uma heuristica Variable Neighbourhood Descent, que alterna entre vizinhancas que sao exploradas por um algoritmo de Backtracking, aplicada ao problema de rotulacao cartografica de pontos e ao problema de coloracao de vertices com pesos. O primeiro consiste em posicionar rotulos em regioes de um mapa cartografico, proporcionando uma boa visualizacao pela reducao das sobreposicoes de rotulos. O segundo consiste em atribuir cores aos vertices de um grafo tal que vertices adjacentes nao recebam a mesma cor. Cada vertice do grafo possui um peso e para cada cor e atribuido um peso que corresponde ao peso maximo dos vertices coloridos com essa cor. O objetivo do problema de coloracao de vertices com pesos e minimizar a soma dos pesos das cores utilizadas. Os experimentos computacionais mostraram que a heuristica proposta e rapida e eficiente, indicando que pode ser avaliada como tecnica para resolver problemas de otimizacao combinatoria.