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

Abstract

This paper proposes a heuristic Variable Neighbourhood Descent which alternates between neighborhoods that are exploited by a Backtracking algorithm, applied to the point feature label placement problem and weighted vertex coloring problem. The first consists in placing point labels on map entity providing a cleam view and reduce the overlap for obtain a quality labeling placement. The second consists in to assign a color to each vertex in such way that color on adjacent vertex are diferent. Each vertex has associated a weight and each color has assigned a weight that corresponds to the maximum weight of the vertices colored with this color. The objective of vertex coloring problem is to minimize the sum of the weight of the colors used. The computational experiments show that the proposed heuristic is fast and efficient indicating that can be evaluated as a technique to solve combinatorial optimization problems.