A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems

This article concerns the point feature cartographic label placement (PFCLP) problem, which is a NP‐hard (Non‐deterministic Polynomial‐time hard) combinatorial problem. It is considered that when all points must be labeled and overlaps are inevitable, the map can be more readable if overlapping labels are placed in a dispersive way, that is, overlapping labels are distant from each other. This work presents a constructive genetic algorithm (CGA) for the discrete dispersion PFCLP that utilizes the notion of masking to preserve optimal subsequences in chromosomes. We also define the discrete dispersion PFCLP as a mixed integer linear programming model, considering the problem of the minimum number of labels in conflict as well. The computational results validate our CGA approach using instances up to 5,046 points.