An Effective Algorithm in order to solve the Capacitated Clustering Problem

Subject Areas : Statistics

N. Mahmoodi Darani ¹ , P. Bassiri ² , M. Yousefikhoshbakht ³

1 - Bouali University, hamedan, Iran
2 - The authors would like to acknowledge the Young Researchers And Elite club, Robatkarim Branch, Islamic Azad University, Robatkarim, Iran for the financial support of this work.
3 - The authors would like to acknowledge the Young Researchers And Elite club, Robatkarim Branch, Islamic Azad University, Robatkarim, Iran for the financial support of this work. Corresponding author

Received: 2015-10-11 Accepted : 2016-12-11 Published : 2016-02-01

Keywords: مساله کلاستربندی ظرفیت دار, مسائل &amp, ndash, NP سخت, روش رقابت استعماری, روش جایجایی, روش درج,

Abstract :

The capacitated clustering problem (CCP) is a data mining technique utilized to categorize a number of objects with known demands into k distinct clusters such that the capacity of each cluster is not violated, every object is allocated to exactly one cluster and sum of distances from all cluster centers to all other nodes is minimized. The CCP is an NP-hard combinatorial optimization problem. Therefore, practical large-scale instances of this problem cannot be solved by exact solution methodologies within acceptable computational time. Our interest was therefore focused on meta-heuristic solution approaches. For this reason, a modified imperialist competitive algorithm (MICA) is proposed for the CCP In this paper. The proposed MICA iterates steps between three basic phases, i.e., the random assignment phase to form clusters, the seed relocation phase to find a better median, and the local improvement phase to make a revision of the solution. The proposed algorithm is tested on several standard instances available from the literature. The computational results confirm the effectiveness of the presented algorithm and show that the proposed algorithm is competitive with other meta-heuristic algorithms for solving the CCP.

References:

[1] Baldacci, R., Hadjiconstantinou, E. and Mingozzi, A. “An exact algorithm for the capacitated vehicle routing problem based on a two commodity network flow formulation,” Operations Research, 2004.

[2] Ralphs, T.K., “Parallel branch and cut for capacitated vehicle routing,” Parallel Computing, 2003.

[3] Negreiros, M. and Palhano, A. “The capacitated centered clustering problem,” Computers and Operations Research, 2006.

[4] Fisher, M. L. and Jaikumar, R. “A generalized assignment heuristic for vehicle routing,” Networks, 11, 109-124, 1981.

[5] Chaves, A. A., de Assis Correa, F. and Lorena, L.A.N. “Clustering search heuristic for the capacitated p-median problem,” Advances in Software Computing Series, 2007.

[6] Mehrotra, A. and Trick, M. A. “Cliques and clustering: A combinatorial approach,” Operations Research Letters, 1998.

[7] Baldacci, R., Hadjiconstantinou, E., Maniezzo, V. and Mingozzi A., “A new method for solving capacitated location problems based on a set partitioning approach,” Computers & Operations Research, 2002.