×

Clustering search algorithm for the capacitated centered clustering problem. (English) Zbl 1173.90413

Summary: The capacitated centered clustering problem (CCCP) consists in partitioning a set of \(n\) points into \(p\) disjoint clusters with a known capacity. Each cluster is specified by a centroid. The objective is to minimize the total dissimilarity within each cluster, such that a given capacity limit of the cluster is not exceeded. This paper presents a solution procedure for the CCCP, using the hybrid metaheuristic clustering search (CS), whose main idea is to identify promising areas of the search space by generating solutions through a metaheuristic and clustering them into groups that are then further explored with local search heuristics. Computational results in test problems of the literature show that the CS found a significant number of new best-known solutions in reasonable computational times.

MSC:

90B40 Search theory
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Christofides, N.; Beasley, J. E., A tree search algorithm for the \(p\)-median problem, European Journal of Operational Research, 10, 196-204 (1981) · Zbl 0481.90020
[2] Osman, I. H.; Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search, International Transactions in Operational Research, 1, 3, 317-336 (1994) · Zbl 0857.90107
[3] Negreiros, M. J.N.; Palhano, A. W.C., The capacitated centred clustering problem, Computers and Operations Research, 33, 6, 1639-1663 (2006) · Zbl 1087.90088
[4] Oliveira ACM, Lorena LAN. Detecting promising areas by evolutionary clustering search. Advances in artificial intelligence. In: Springer lecture notes in artificial intelligence series, 2004. p. 385-94.; Oliveira ACM, Lorena LAN. Detecting promising areas by evolutionary clustering search. Advances in artificial intelligence. In: Springer lecture notes in artificial intelligence series, 2004. p. 385-94.
[5] Oliveira ACM, Lorena LAN. Hybrid evolutionary algorithms and clustering search. In: Grosan C, Abraham A, Ishibuchi H, editors. Hybrid evolutionary systems—studies in computational intelligence. Springer SCI series, 2007. p. 81-102.; Oliveira ACM, Lorena LAN. Hybrid evolutionary algorithms and clustering search. In: Grosan C, Abraham A, Ishibuchi H, editors. Hybrid evolutionary systems—studies in computational intelligence. Springer SCI series, 2007. p. 81-102.
[6] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[7] Forgy, E. W., Cluster analysis of multivariate data: efficiency versus interpretability of classifications, Biometrics, 21, 3, 768 (1965)
[8] Lorena, L. A.N.; Senne, E. L.F., Local search heuristics for capacitated \(p\)-median problems, Networks and Spatial Economics, 3, 4, 407-419 (2003)
[9] Lorena, L. A.N.; Senne, E. L.F., A column generation approach to capacitated \(p\)-median problems, Computers and Operational Research, 31, 863-876 (1994) · Zbl 1048.90132
[10] Diaz, J. A.; Fernandez, E., Hybrid scatter search and path relinking for the capacitated \(p\)-median problem, European Journal of Operational Research, 169, 570-585 (2006) · Zbl 1079.90076
[11] Scheuerer, S.; Wendolsky, R., A scatter search heuristic for the capacitated clustering problem, European Journal of Operational Research, 169, 533-547 (2006) · Zbl 1079.90180
[12] Fleszar K, Hindi DS. An effective VNS for the capacitated \(p\); Fleszar K, Hindi DS. An effective VNS for the capacitated \(p\) · Zbl 1160.90496
[13] Chaves, A. A.; Correa, F. A.; Lorena, L. A.N., Clustering search heuristic for the capacitated \(p\)-median problem, Springer Advances in Software Computing Series, 44, 136-143 (2007)
[14] Wesolowsky, G., The Weber problem: history and perspectives, Location Science, 1, 5-23 (1993) · Zbl 0923.90110
[15] Brimberg, J.; Hansen, P.; Mladenovic, N.; Salhi, S., A survey of solution methods for the continuous location-allocation problem, International Journal of Operations Research, 5, 1, 1-12 (2008) · Zbl 1153.90487
[16] Aras, N.; Orbay, M.; Altinel, I. K., Efficient heuristics for the rectilinear distance capacitated multi-facilityWeber problem, Journal of the Operational Research Society, 59, 64-79 (2008) · Zbl 1167.90557
[17] Chaves, A. A.; Lorena, L. A.N., Hybrid algorithms with detection of promising areas for the prize collecting traveling salesman problem, International Conference on Hybrid Intelligent Systems, IEEE Computer Society, 49-54 (2005)
[18] Glover, F., Tabu search and adaptive memory programming: advances, applications and challenges, Interfaces in Computer Science and Operations Research, 1-75 (1996) · Zbl 0882.90111
[19] Ribeiro G, Nagano MS, Lorena LAN. Hybrid evolutionary algorithm for flowtime minimisation in no-wait flowshop scheduling. Berlin Heidelberg: Springer; 2007. p. 1099-109.; Ribeiro G, Nagano MS, Lorena LAN. Hybrid evolutionary algorithm for flowtime minimisation in no-wait flowshop scheduling. Berlin Heidelberg: Springer; 2007. p. 1099-109.
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.