The CCP consists of grouping a set of N nodes in several K different disjoint clusters with limited capacities. A particular type of node, named centroid, is defined for each cluster. Nodes with short paths to centroid are grouped, provided that cluster capacity is not exceeded. The objective of the CCP is to minimize the sum of the path length from each node to the corresponding centroid of the assigned cluster. The CCP is an NP-complete combinatorial optimization problem. In this work, a new method for solving the CCP is presented. This method can solve large problems in an acceptable time and still obtain competitive solutions. The results and execution times applying the method in instances of common use were compared with those obtained in recent publications.

CCP, location problems, capacitated p-median problems, column generation

Received: September 2, 2022; Revised: October 21, 2022; Accepted: November 1, 2022; Published: November 18, 2022

How to cite this article: Laura Michele Báez Villegas, Jose Luis Martínez Flores, Diana Sanchez Partida and Enrique Gabriel Baquela, An algorithm based on Coulomb’s law to solve the CCP, Advances and Applications in Discrete Mathematics 35 (2022), 61-75.
http://dx.doi.org/10.17654/0974165822052

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] S. Scheuerer and R. Wendolsky, A scatter search heuristic for the capacitated clustering problem, European J. Oper. Res. 169 (2006), 533-547.
[2] Y. Koskosidis and W. Powell, Clustering algorithms for consolidation of customer orders into vehicle shipments, Transpn. Res.-B 26B (1992), 365-379.
[3] S. Ahmadi and I. Osman, Greedy random adaptive memory programming search for the capacitated clustering problem, European J. Oper. Res. 162 (2005), 30-44.
[4] L. A. N. Lorena and E. Senne, A column generation approach to capacitated p-median problems, Comput. Oper. Res. 31 (2004), 863-876.
[5] N. Christofides and I. H. Osman, Capacitated clustering problems by hybrid simulated annealing and tabu search, Intl. Trans. Opl. Res. 1 (1994), 317-336.
[6] M. Negreiros and A. Palhano, The capacitated centred clustering problem, Comput. Oper. Res. 33 (2006), 1639-1663.
[7] P. M. Franca, N. M. Sosa and V. Pureza, An adaptive, Tabu search algorithm for the capacitated clustering problem, Intl. Trans. Opl. Res. 6 (1999), 665-678.
[8] T. K. Ralphs, Parallel branch and cut for the capacitated vehicle routing problem, Parallel Computing 5 (2003), 607-629.
[9] N. M. Darani, P. Bassiri and M. Yousefikhoshbakt, An effective algorithm in order to solve the capacitated clustering problem, Journal of New Res. in Math. 1 (2016), 81-102.
[10] R. Baldacci, E. Hadjiconstantinou and A. Mingozzi, An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation, Oper. Res. 52 (2014), 723-738.
[11] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Publisher: Freeman, San Francisco, CA, 1979, pp. 77-106.
[12] Z. Yang, H. Chen and F. Chu, A Lagrangian relaxation approach for a large scale new variant of capacitated clustering problem, Comp and Ind. Eng. 61 (2011), 430-435.
[13] Z. Qing, U. Benlic, W. Qinghua and J. Kao-Hao, Heuristic search to the capacitated clustering problem, European J. Oper. Res. 273 (2019), 464-487.
[14] D. Rodney, A. Soper and C. Walshaw, Multilevel approaches applied to the capacitated clustering problem, Proceedings of School of Computing and Mathematical Sciences, University of Greenwich, London, England, 2008.
[15] M. Lewis, H. Wang and G. Kochenberg, Exact solutions to the capacitated clustering problem: a comparison of two models, Ann. Data Sci. 1 (2014), 15-23.
[16] T. L. Quy, A. Roy, G. Friege and E. Ntostsi, Fair capacitated clustering, Proceedings of 14th International Conference on Educational Data Mining, Paris, France, 2021.
[17] A. Chaves, F. De Asis Correa and L. Lorena, Clustering search heuristic for the capacitated p-median problem, Innovations in Hybrid Intelligent Systems, E. Corchado, J. M. Corchado and A. Abraham, eds., Advances in Soft Computing, Springer, Berlin, Heidelberg, Vol. 44, 2007, pp. 136-143.
[18] Y. Liu, P. Guo and Y. Zeng, HA-CCP: a hybrid algorithm for solving capacitated clustering problem, Comp. Intell. Neurosc. 2022 (2022), 1-24.
[19] S. Geetha, G. Poonthalir and P. T. Vanathi, Improved K-means algorithm for capacitated clustering problem, J. Comp. Sci. 8 (2009), 52-59.
[20] A. Gavara, D. Landa-Silva and V. Campos, Randomized heuristics for the capacitated clustering problem, Inform. Sci. 417 (2017), 154-168.
[21] G. Spavieri, G. T. Gillies and M. Rodriguez, Physical implications of Coulomb’s law, Metrologia 41 (2004), 159-170.
[22] J. Murray and P. Politzer, The electrostatic potential: an overview, WIREs Comp. Molec. Sci. 1 (2011), 153-163.
[23] F. Stefanello, O. C. B. de Araujo and F. M. Muller, Matheuristics for the capacitated p-median problem, Intl. Trans. Opl. Res. (2014), 1-19.
[24] G. Cornuejols, M. L. Fisher and G. L. Nemhauser, Location of bank accounts to optimize float: an analytic study of exact and approximation algorithms. Man. Sci. 23 (1977), 789-810.
[25] M. Fisher and R. Jaikumar, A generalized assignment heuristic for the vehicle routing problem, Networks 11(2) (1981), 109-124.
[26] J. M. Mulvey and M. P. Beck, Solving capacitated clustering problems, European J. Oper. Res. 18(3) (1984), 339-348.
[27] V. Maniezzo, A. Mingozzi and R. Baldacci, A binomic approach to the capacitated p-median problem, J. Heuristics 4(3) (1998), 263-280.
[28] R. Baldacci, E. Hadjiconstantimou, V. Maniezzo and A. Mingozzi, A new method for solving capacitated location problems based on a set partitioning approach, Comp. and Op. Res. 29(4) (2002), 365-386.
[29] J. A. Diaz and E. Fernandez, Hybrid scatter search and path relinking for the capacitated p-median problem, European J. Oper. Res. 169 (2006), 570-585.
[30] K. Fleszar and K. S. Hindi, An effective VNS for the capacitated p-median problem, European J. Oper. Res. 191 (2008), 612-622.