A Tabu Search Algorithm for the Map Labeling Problem

In this paper we propose an algorithm based on the Tabu Search metaheuristic for the Map Labeling problem, i.e. the relevant problem in cartography of assigning labels to specific points of interests in a clear and readable way. It is a combinatorial problem known to be \(\mathcal{N}\mathcal{P}\) -complete and therefore it needs to be tackled by means of good and efficient heuristics. In our experiments, we used real maps of Italian cities, Rome and Venice in particular.