Solution strategy based on Gaussian mixture models and dispersion reduction for the capacitated centered clustering problem

Abstract

The Capacitated Centered Clustering Problem (CCCP)-a multi-facility location model-is very important within the logistics and supply chain management fields due to its impact on industrial transportation and distribution. However, solving the CCCP is a challenging task due to its computational complexity. In this work, a strategy based on Gaussian mixture models (GMMs) and dispersion reduction is presented to obtain the most likely locations of facilities for sets of client points considering their distribution patterns. Experiments performed on large CCCP instances, and considering updated best-known solutions, led to estimate the performance of the GMMs approach, termed as Dispersion Reduction GMMs, with a mean error gap smaller than 2.6%. This result is more competitive when compared to Variable Neighborhood Search, Simulated Annealing, Genetic Algorithm and CKMeans and faster to achieve when compared to the best-known solutions obtained by Tabu-Search and Clustering Search.

Keywords: Capacitated centered clustering problem; Dispersion reduction; Expectation-maximization; Gaussian mixture models.