Heuristic search to the capacitated clustering problem

Given a weighted graph, the capacitated clustering problem (CCP) is to partition a set of nodes into a given number of distinct clusters (or groups) with restricted capacities, while maximizing the sum of edge weights corresponding to two nodes from the same cluster. CCP is an NP-hard problem with many relevant applications. This paper proposes two effective algorithms for CCP: a Tabu Search (denoted as FITS) that alternates between exploration in feasible and infeasible search space regions, and a Memetic Algorithm (MA) that combines FITS with a dedicated cluster-based crossover. Extensive computational results on five sets of 183 benchmark instances from the literature indicate that the proposed FITS competes favorably with the state-of-the-art algorithms. Additionally, an experimental comparison between FITS and MA under an extended time limit demonstrates that further improvements in terms of the solution quality can be achieved with MA in most cases. We also analyze several essential components of the proposed algorithms to understand their importance to the success of these approaches.