Optimization with tabu search in spatial data clustering with multiple objectives

Abstract

Clustering spatial-geographic units, zones or areas is employed to solve problems related to territorial design. The clustering adapts to the definition of territorial design of a particular problem, which demands spatial data processing under clustering schemes with topological requirements in the zones. For small instances, when the geographical compactness is attended as an objective function, this problem is solved by exact methods in an aceptable response time. However, for bigger instances and due to the combinatory nature of this problem, the computational complexity increases and the employment of approximated methods becomes a necessity, in such a way that when the geographical compactness was the only cost function, a couple of approximated methods were implemented, giving satisfactory results. A particular case of this kind of problems that has our attention in recent years is the classification of AGEBS (basic geographical units by its initials in Spanish) through partitions. Some works were made related to the formation of compact groups of AGEBS, but additional restrictions weren’t often considered. A very interesting and demanded application problem is extending the  compact clustering to form groups under a homogeneity criterion to balance the number of objects in every group. This problem implies a multiobjective approach that has to tackle two objectives to attain a balance between the two. This work presents a mathematical model and the resulting implementation to achieve the equilibrium between compactness and homogeneity in the number of objects. The metaheursitic incorporated to this multiobjective clustering problem is tabu search.