×

Tabu search and GRASP for the capacitated clustering problem. (English) Zbl 1334.90190

Summary: The capacitated clustering problem (CCP) consists of forming a specified number of clusters or groups from a set of elements in such a way that the sum of the weights of the elements in each cluster is within some capacity limits, and the sum of the benefits between the pairs of elements in the same cluster is maximized. This problem – which has been recently tackled with a GRASP/VNS approach – arises in the context of facility planners at mail processing and distribution. We propose a tabu search and several GRASP variants to find high quality solutions to this NP-hard problem. These variants are based on several neighborhoods, including a new one, in which we implement a one-for-two swapping strategy. We also hybridize both methodologies to achieve improved outcomes. The maximally diverse grouping problem (MDGP) is a special case of the CCP in which all the elements have a weight of 1 U. This problem has been recently studied in the academic context when forming student groups, and we adapt the best method reported in the literature, a tabu search with strategic oscillation (\(\mathrm{TS}_{\mathrm{SO}}\)), to the CCP. On the other hand, the handover minimization in mobility networks is a problem equivalent to the CCP in which we minimize the sum of the benefits (costs) of the edges between different clusters. GRASP with Path Relinking has been recently applied to it. Our empirical study with 133 instances shows the superiority of the new GRASP with tabu search for the CCP with respect to these three previous approaches: the GRASP/VNS, the adapted \(\mathrm{TS}_{\mathrm{SO}}\), and the GRASP with Path Relinking.

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C09 Boolean programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: TTT plots: a perl program to create time-to-target plots. Optim. Lett. 1(4), 355-366 (2007) · Zbl 1220.90102 · doi:10.1007/s11590-006-0031-4
[2] Deng, Y., Bard, J.F.: A reactive GRASP with path relinking for the capacitated clustering. J. Heuristics 17, 119-152 (2011) · Zbl 1211.90301 · doi:10.1007/s10732-010-9129-z
[3] Duarte, A., Sánchez-Oro, J., Resende, M., Glover, F., Martí, R.: Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization. Inform. Sci. 296, 46-60 (2015) · doi:10.1016/j.ins.2014.10.010
[4] Fan, Z.P., Chen, Y., Ma, J., Zeng, S.: A hybrid genetic algorithmic approach to the maximally diverse grouping problem. J. Oper. Res. Soc. 62, 92-99 (2011) · doi:10.1057/jors.2009.168
[5] Feo, T., Goldschmidt, O., Khellaf, M.: One-half approximation algorithms for the k-partition problem. Oper. Res. 40, S170-S173 (1992) · Zbl 0745.90072 · doi:10.1287/opre.40.1.S170
[6] Ferreira, C.E., Martin, A., de Souza, C.C., Weismantel, R., Wolsey, L.A.: The node capacitated graph partitioning problem: a computational study. Math. Program. 81, 229-256 (1998) · Zbl 0919.90139
[7] Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP, Part I: Algorithms. Int. Trans. Operat. Res. 16, 1-24 (2009) · Zbl 1153.90553 · doi:10.1111/j.1475-3995.2009.00663.x
[8] Gallego, M., Duarte, A., Laguna, M., Martí, R.: Hybrid heuristics for the maximum diversity problem. Comput. Optim. Appl. 44(3), 411 (2009) · Zbl 1181.90196 · doi:10.1007/s10589-007-9161-6
[9] Gallego, M., Laguna, M., Martí, R., Duarte, A.: Tabu search with strategic oscillation for the maximally diverse grouping problem. J. Oper. Res. Soc. 64, 724-734 (2013) · doi:10.1057/jors.2012.66
[10] Glover, F., Laguna, M.: Tabu Search. Kluwer, Boston (1997) · Zbl 0930.90083 · doi:10.1007/978-1-4615-6089-0
[11] O’Brien, F.A., Mingers, J.: The Equitable Partitioning Problem: A Heuristic Algorithm Applied to the Allocation of University Student Accommodation. Research Paper No. 187. Warwick Business School, Coventry (1995) · Zbl 0919.90139
[12] Martí, R., Sandoya, F.: The equitable dispersion problem. Comput. Operat. Res. 40, 3091-3099 (2013) · Zbl 1348.90475 · doi:10.1016/j.cor.2012.04.005
[13] Morán-Mirabal, L.F., González-Velarde, J.L., Resende, M.G.C., Silva, R.M.A.: Randomized heuristics for handover minimization in mobility networks. J. Heuristics 19, 845-880 (2013) · doi:10.1007/s10732-013-9223-0
[14] Ribeiro, C.C., Uchoa, E., Werneck, R.F.: A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J. Comput. 14, 228-246 (2002) · Zbl 1238.90117 · doi:10.1287/ijoc.14.3.228.116
[15] Weitz, R.R., Jelassi, M.T.: Assigning students to groups: a multi-criteria decision support system approach. Decis. Sci. 23(3), 746-757 (1992) · doi:10.1111/j.1540-5915.1992.tb00415.x
[16] Weitz, R.R., Lakshminarayanan, S.: An empirical comparison of heuristic methods for creating maximally diverse groups. J. Oper. Res. Soc. 49(6), 635-646 (1998) · Zbl 1131.90365 · doi:10.1057/palgrave.jors.2600510
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.