×

zbMATH — the first resource for mathematics

Heuristic search to the capacitated clustering problem. (English) Zbl 1403.90661
Summary: Given a weighted graph, the capacitated clustering problem (CCP) is to partition a set of nodes into a given number of distinct clusters (or groups) with restricted capacities, while maximizing the sum of edge weights corresponding to two nodes from the same cluster. CCP is an NP-hard problem with many relevant applications. This paper proposes two effective algorithms for CCP: a tabu search (denoted as FITS) that alternates between exploration in feasible and infeasible search space regions, and a memetic algorithm (MA) that combines FITS with a dedicated cluster-based crossover. Extensive computational results on five sets of 183 benchmark instances from the literature indicate that the proposed FITS competes favorably with the state-of-the-art algorithms. Additionally, an experimental comparison between FITS and MA under an extended time limit demonstrates that further improvements in terms of the solution quality can be achieved with MA in most cases. We also analyze several essential components of the proposed algorithms to understand their importance to the success of these approaches.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
PDF BibTeX XML Cite
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, Optimization Letters, 1, 4, 355-366, (2007) · Zbl 1220.90102
[2] Bard, J. F.; Jarrah, A. I., Large-scale constrained clustering for rationalizing pickup and delivery operations, Transportation Research Part B: Methodological, 43, 5, 542-561, (2009)
[3] Bartz-Beielstein, T.; Chiarandini, M.; Paquete, L.; Preuss, M., Experimental methods for the analysis of optimization algorithms, (2010), Springer
[4] Benlic, U.; Hao, J. K., A multilevel memetic approach for improving graph k-partitions, IEEE Transactions on Evolutionary Computation, 15, 5, 624-642, (2011)
[5] Benlic, U.; Hao, J. K., Hybrid Metaheuristics for the Graph Partitioning Problem, 157-185, (2013), Hybrid Metaheuristics
[6] Brimberg, J.; Mladenović, N.; Todosijević, R.; Uros̆ević, D., Solving the capacitated clustering problem with variable neighborhood search, Annals of Operations Research, 2, 1-33, (2017)
[7] Brimberg, J.; Mladenović, N.; Urošević, D., Solving the maximally diverse grouping problem by skewed general variable neighborhood search, Information Sciences, 295, 650-675, (2015)
[8] Chen, Y. N.; Hao, J. K.; Glover, F., A hybrid metaheuristic approach for the capacitated arc routing problem, European Journal of Operational Research, 253, 1, 25-39, (2016) · Zbl 1346.90087
[9] Deng, Y.; Bard, J. F., A reactive GRASP with path relinking for capacitated clustering, Journal of Heuristics, 17, 2, 119-152, (2011) · Zbl 1211.90301
[10] Duarte, A.; Martí, R., Tabu search and grasp for the maximum diversity problem, European Journal of Operational Research, 178, 1, 71-84, (2007) · Zbl 1109.90081
[11] Errico, F.; Desaulniers, G.; Gendreau, M.; Rei, W.; Rousseau, L. M., A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times, European Journal of Operational Research, 249, 1, 55-66, (2016) · Zbl 1347.90010
[12] Falkenauer, E., Genetic algorithms and grouping problems, (1998), Wiley New York · Zbl 0803.68037
[13] Fisher, M. L.; Jaikumar, R., A generalized assignment heuristic for vehicle routing, Networks, 11, 2, 109-124, (1981)
[14] Galinier, P.; Boujbel, Z.; Fernandes, M. C., An efficient memetic algorithm for the graph partitioning problem, Annals of Operations Research, 191, 1, 1-22, (2011) · Zbl 1233.90271
[15] Galinier, P.; Hao, J.k., Hybrid evolutionary algorithms for graph coloring, Journal of Combinatorial Optimization, 3, 4, 379-397, (1999) · Zbl 0958.90071
[16] Gallego, M.; Duarte, A., Tabu search with strategic oscillation for the maximally diverse grouping problem, Journal of the Operational Research Society, 64, 5, 724-734, (2013)
[17] Hao, J. K., Memetic algorithms in discrete optimization, (Neri, F.; Cotta, C.; Moscato, P., Handbook of memetic algorithms. studies in computational intelligence 379, chapter 6, (2012), Springer Berlin Heidelberg), 73-94
[18] Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacitated arc routing problem, Operations Research, 48, 1, 129-135, (2000) · Zbl 1106.90384
[19] Higgins, A. J., A dynamic tabu search for large-scale generalised assignment problems, Computers & Operations Research, 28, 10, 1039-1048, (2001) · Zbl 1017.90089
[20] Johnes, J., Operational research in education, European Journal of Operational Research, 243, 3, 683-696, (2015) · Zbl 1346.90845
[21] Koskosidis, Y. A.; Powell, W. B., Clustering algorithms for consolidation of customer orders into vehicle shipments, Transportation Research Part B Methodological, 26, 5, 365-379, (1992)
[22] Laguna, M.; Glover, F., Tabu search, (1997), Springer
[23] Lai, X.; Hao, J. K., Iterated maxima search for the maximally diverse grouping problem, European Journal of Operational Research, 254, 3, 780-800, (2016) · Zbl 1346.90786
[24] Lai, X.; Hao, J. K., Iterated variable neighborhood search for the capacitated clustering problem, Engineering Applications of Artificial Intelligence, 56, 102-120, (2016)
[25] Lapierre, S. D.; Ruiz, A.; Soriano, P., Balancing assembly lines with tabu search, European Journal of Operational Research, 168, 3, 826-837, (2006) · Zbl 1083.90017
[26] López-Ibánez, M.; Dubois-Lacoste, J.; Cáceres, L. P.; Birattari, M.; Stützle, T., The irace package: iterated racing for automatic algorithm configuration, Operations Research Perspectives, 3, 43-58, (2016)
[27] Lü, Z.; Glover, F.; Hao, J. K., A hybrid metaheuristic approach to solving the UBQP problem, European Journal of Operational Research, 207, 3, 1254-1262, (2010) · Zbl 1206.90113
[28] Martínez-Gavara, A.; Campos, V.; Gallego, M.; Laguna, M.; Martí, R., Tabu search and GRASP for the capacitated clustering problem, Computational Optimization and Applications, 62, 2, 589-607, (2015) · Zbl 1334.90190
[29] Martínez-Gavara, A.; Landa-Silva, D.; Campos, V.; Martí, R., Randomized heuristics for the capacitated clustering problem, Information Sciences, 417, (2017)
[30] Morán-Mirabal, L. F.; González-Velarde, J. L.; Resende, M. G.; Silva, R. M., Randomized heuristics for handover minimization in mobility networks, Journal of Heuristics, 19, 6, 845-880, (2013)
[31] Moscato, P.; Cotta, C., A gentle introduction to memetic algorithms, Handbook of metaheuristics, (2006), Springer US · Zbl 1107.90459
[32] Mulvey, J. M.; Beck, M. P., Solving capacitated clustering problems, European Journal of Operational Research, 18, 3, 339-348, (1984) · Zbl 0547.62039
[33] Palubeckis, G.; Ostreika, A.; Rubliauskas, D., Maximally diverse grouping: an iterated tabu search approach, Journal of the Operational Research Society, 66, 4, 579-592, (2015)
[34] Paraskevopoulos, D. C.; Laporte, G.; Repoussis, P. P.; Tarantilis, C. D., Resource constrained routing and scheduling: review and research prospects, European Journal of Operational Research, 263, 3, 737-754, (2017) · Zbl 1380.90058
[35] Rodriguez, F. J.; Lozano, M.; García-Martínez, C.; González-Barrera, J. D., An artificial bee colony algorithm for the maximally diverse grouping problem, Information Sciences, 230, 5, 183-196, (2013) · Zbl 1293.90085
[36] Weitz, R. R.; Lakshminarayanan, S., An empirical comparison of heuristic methods for creating maximally diverse groups, Journal of the Operational Research Society, 25, 6, 473-482, (1998) · Zbl 1131.90365
[37] Wu, Q.; Hao, J. K., A hybrid metaheuristic method for the maximum diversity problem, European Journal of Operational Research, 231, 2, 452-464, (2013) · Zbl 1317.90338
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.