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.
Keywords: Clustering, mixed-integer linear programming, combinatorial optimization, approximation methods and heuristics
@article{RO_2022__56_3_1167_0,
author = {de Ara\'ujo, Kennedy Anderson Gumar\~aes and Guedes, Jedson Bernadino and Prata, Bruno de Athayde},
title = {Hybrid matheuristics for the multi-capacitated clustering problem},
journal = {RAIRO. Operations Research},
pages = {1167--1185},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {3},
doi = {10.1051/ro/2022048},
mrnumber = {4422227},
zbl = {1489.90066},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022048/}
}
TY - JOUR AU - de Araújo, Kennedy Anderson Gumarães AU - Guedes, Jedson Bernadino AU - Prata, Bruno de Athayde TI - Hybrid matheuristics for the multi-capacitated clustering problem JO - RAIRO. Operations Research PY - 2022 SP - 1167 EP - 1185 VL - 56 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022048/ DO - 10.1051/ro/2022048 LA - en ID - RO_2022__56_3_1167_0 ER -
%0 Journal Article %A de Araújo, Kennedy Anderson Gumarães %A Guedes, Jedson Bernadino %A Prata, Bruno de Athayde %T Hybrid matheuristics for the multi-capacitated clustering problem %J RAIRO. Operations Research %D 2022 %P 1167-1185 %V 56 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022048/ %R 10.1051/ro/2022048 %G en %F RO_2022__56_3_1167_0
de Araújo, Kennedy Anderson Gumarães; Guedes, Jedson Bernadino; Prata, Bruno de Athayde. Hybrid matheuristics for the multi-capacitated clustering problem. RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1167-1185. doi: 10.1051/ro/2022048
[1] and , Greedy random adaptive memory programming search for the capacitated clustering problem. Eur. J. Oper. Res. 162 (2005) 30–44. | MR | Zbl | DOI
[2] , , and , Solving the capacitated clustering problem with variable neighborhood search. Ann. Oper. Res. 272 (2019) 289–321. | MR | Zbl | DOI
[3] , and , A hybrid heuristic for the overlapping cluster editing problem. Appl. Soft Comput. (2019) 105–482.
[4] and , Clustering search algorithm for the capacitated centered clustering problem. Comput. Oper. Res. 37 (2010) 552–558. Hybrid Metaheuristics. | MR | Zbl | DOI
[5] and , Hybrid evolutionary algorithm for the capacitated centered clustering problem. Exp. Syst. App. 38 (2011) 5013–5018. | DOI
[6] , and , Adaptive biased random-key genetic algorithm with local search for the capacitated centered clustering problem. Comput. Ind. Eng. 124 (2018) 331–346. | DOI
[7] and , Variable fixing heuristics for solving multiple depot vehicle scheduling problem with heterogeneous fleet and time windows. Optim. Lett. 15 (2021) 153–170. | MR | Zbl | DOI
[8] and , A reactive grasp with path relinking for capacitated clustering. J. Heuristics 17 (2011) 119–152. | Zbl | DOI
[9] and , Size-reduction heuristics for the unrelated parallel machines scheduling problem. Comput. Oper. Res. 38 (2011) 301–309. Project Management and Scheduling. | DOI
[10] and , Greedy randomized adaptive search procedures. J. Glob. Optim. 6 (1995) 109–133. | MR | Zbl | DOI
[11] , and , An adaptive tabu search algorithm for the capacitated clustering problem. Int. Trans. Oper. Res. 6 (1999) 665–678. | MR | DOI
[12] and , Computers and Intractability. Vol 174. Freeman, San Francisco (1979). | MR | Zbl
[13] , and , Improved #-means algorithm for capacitated clustering problem. INFOCOMP J. Comput. Sci. 8 (2009) 52–59.
[14] and , A matheuristic for large-scale capacitated clustering. Comput. Oper. Res. 132 (2021) 105304. | MR | DOI
[15] and , Iterated variable neighborhood search for the capacitated clustering problem. Eng. App. Artif. Intell. 56 (2016) 102–120. | DOI
[16] , and , Model-based capacitated clustering with posterior regularization. Eur. J. Oper. Res. 271 (2018) 594–605. | MR | Zbl | DOI
[17] , , and , Randomized heuristics for the capacitated clustering problem. Inf. Sci. 417 (2017) 154–168. | DOI
[18] , Design and Analysis of Experiments. John Wiley & Sons (2017). | MR | Zbl
[19] and , Solving capacitated clustering problems. Eur. J. Oper. Res. 18 (1984) 339–348. | Zbl | DOI
[20] and , The capacitated centred clustering problem. Comput. Oper. Res. 33 (2006) 1639–1663. | Zbl | DOI
[21] , , , and , Capacitated clustering problems applied to the layout of it-teams in software factories. Ann. Oper. Res. (2020) 1–29. | MR | Zbl
[22] and , Capacitated clustering problems by hybrid simulated annealing and tabu search. Int. Trans. Oper. Res. 1 (1994) 317–336. | Zbl | DOI
[23] , The multi capacitated clustering problem. Technical report, Federal University of Ceará, Brazil (2015).
[24] and , A scatter search heuristic for the capacitated clustering problem. Eur. J. Oper. Res. 169 (2006) 533–547. | MR | Zbl | DOI
[25] and , Solving the capacitated clustering problem with genetic algorithms. J. Chin. Inst. Ind. Eng. 18 (2001) 1–12.
[26] , and , Matheuristics for the capacitated -median problem. Int. Trans. Oper. Res. 22 (2015) 149–167. | MR | Zbl | DOI
[27] , and , A lagrangian relaxation approach for a large scale new variant of capacitated clustering problem. Comput. Ind. Eng. 61 (2011) 430–435. Combinatorial Optimizatiion in Industrial Engineering. | DOI
[28] , , and , Heuristic search to the capacitated clustering problem. Eur. J. Oper. Res. 273 (2019) 464–487. | MR | Zbl | DOI
Cité par Sources :
