Neighborhood decomposition-driven variable neighborhood search for capacitated clustering

The capacitated clustering problem (CCP) is a general model relevant for a variety of important applications in areas such as parallel computing and very large scale integration design. However, the problem is known to be NP-hard, and thus computationally challenging. In this work, we present an original and highly effective variable neighborhood search algorithm for the problem, which is characterized by its neighborhood decomposition technique and a probability-based diversification strategy. The proposed algorithm is assessed via extensive experiments on 110 benchmark instances commonly used in the literature. Computational results show that the algorithm significantly outperforms the existing state-of-the-art algorithms in the literature. This work advances the state-of-the-art of solving the capacitated clustering problem and can be useful for the related practical applications. The key feature of the algorithm, i.e., combining the neighborhood decomposition-driven local search with the perturbation, is of general interest and can help to design effective heuristic algorithms for other important clustering problems.

Automated summary

The capacitated clustering problem is a general model relevant for a variety of important applications. This work presents an original and highly effective algorithm for solving this problem, which significantly outperforms existing state-of-the-art algorithms in the literature. The key feature of the algorithm, combining neighborhood decomposition-driven local search with perturbation, can be useful for designing effective heuristic algorithms for other important clustering problems.