Premium
A hybrid data mining heuristic to solve the point‐feature cartographic label placement problem
Author(s) -
Guerine Marcos,
Rosseti Isabel,
Plastino Alexandre
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12666
Subject(s) - heuristics , heuristic , computer science , simulated annealing , cluster analysis , set (abstract data type) , feature (linguistics) , data mining , point (geometry) , hyper heuristic , metaheuristic , artificial intelligence , mathematical optimization , machine learning , mathematics , linguistics , philosophy , robot learning , geometry , mobile robot , robot , programming language , operating system
A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature.