New Method to Solve the Capacitated Clustering Problem

Resumen

The CCP consists of grouping a set of N nodes in a number of K different disjoint clusters with restricted capacities. A special type of node, named centroid, is defined for each cluster. Nodes with short paths to centroid are grouped together, provided that cluster capacity is not exceeded. The objective of the CCP is to minimize the sum of the path lengths from each node to the corresponding centroid of the assigned cluster. The CCP is an NP-Hard combinatorial optimization problem. In this work a new method of solution is presented. Previously reported techniques are analyzed as well as their results and compared with the method developed for this work with the aim of clarify its advantages and limitations.