Tabu Search Heuristic for Point-Feature Cartographic Label Placement

摘要

The generation of better label placement configurations in maps is a problem that comes up in automated cartographic production. The objective of a good label placement is to display the geographic position of the features with their corresponding label in a clear and harmonious fashion, following accepted cartographic conventions. In this work, we have approached this problem from a combinatorial optimization point of view, and our research consisted of the evaluation of the tabu search (TS) heuristic applied to cartographic label placement. When compared, in real and random test cases, with techniques such as simulated annealing and genetic algorithm (GA), TS has proven to be an efficient choice, with the best performance in quality. We concluded that TS is a recommended method to solve cartographic label placement problem of point features, due to its simplicity, practicality, efficiency and good performance along with its ability to generate quality solutions in acceptable computational time.