Hybrid matheuristics for the multi-capacitated clustering problem

¹ Department of Applied Mathematics, University of São Paulo, São Paulo Brazil
² Department of Statistics and Applied Mathematics, Federal University of Ceará, Fortaleza, Brazil
³ Department of Industrial Engineering, Federal University of Ceará, Fortaleza, Brazil

^* Corresponding author: baprata@ufc.br

Received: 25 May 2021
Accepted: 23 March 2022

Abstract

The capacitated clustering problem is a well-known and largely studied combinatorial optimization problem with several industrial applications. Although a great attention has been paid to this problem in the literature, the deeming of the problem with clusters centers with multiple types and a unique capacity per type is quite limited. We introduce a novel variant of capacitated clustering problems named multi-capacitated clustering problem (MCCP), a NP-hard optimization problem in which there are clients with different types and units of services to offer that must be grouped into given centers that demand with limited capacity per type the services. It is taken into account the distance between each one of these clients and the potential clusters to which they can be allocated, aiming to minimize the sum of such distances. It is presented an integer programming model for this problem, which it is shown to have limited application solving large-sized instances. As solution procedures, we present the following algorithms. We propose a greedy heuristic to generate a tentative feasible solution within a negligible computational effort. We adapt a size-reduction (SR) matheuristic to solve the problem under study. Furthermore, we introduce an innovative matheuristic that hybridizes the constructive phase of the well-known GRASP metaheuristic with the SR algorithm. Also, we develop a variable fixing (VF) heuristic. Finally, we propose a hybrid matheuristic based on the SR and VF algorithms. Computational results over a set of 100 randomly generated test instances point out the quality of the solutions found by the proposed algorithms. Besides, the results are statistically tested, and thus, our proposals are recommended to solve the problem under study.