A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems. Issue 1 (12th August 2015)

• Record Type: Journal Article
• Authors: Gomes, Sóstenes Pereira; Lorena, Luiz Antonio Nogueira; Ribeiro, Glaydston Mattos
• Is Part Of: Geographical analysis. Volume 48:Issue 1(2016)
• Page Start: 43
• Page End: 58
• Publication Date: 2015-08-12
• Subjects: Geography -- Methodology -- Periodicals; Electronic journals; 910.00182
• DOI: 10.1111/gean.12082
• Languages: English
• ISSNs: 0016-7363

Abstract

Abstract : 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.