The capacitated centred clustering problem

The capacitated centred clustering problem (CCCP) consists of defining a set of clusters with limited capacity and maximum proper similarity per cluster. Each cluster is composed of individuals from whom we can compute a centre value and hence, determine a similarity measure. The clusters must cover the demands of their individuals. This problem can be applied to the design of garbage collection zones, defining salesmen areas, etc. In this work, we present two variations (p-CCCP and Generic CCCP) of this problem and their mathematical programming formulations. We first focus our attention on the Generic CCCP, and then we create a new procedure for p-CCCP. These problems being NP-HARD, we propose a two-phase polynomial heuristic algorithm. The first phase is a constructive phase for which we will propose two variants: the first technique uses known cluster procedures oriented by a log-polynomial geometric tree search, the other one uses unconstrained to constrained clustering. The second phase is a refinement of the variable neighbourhood search (VNS). We also show the results we have obtained for tests from the CCP literature, the design of garbage collection zones, and salesmen areas distribution using the approach implemented for the SISROT® system.