RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Infocomp >

Please use this identifier to cite or link to this item: http://repositorio.ufla.br/jspui/handle/1/9965

Title: Improved k-means algorithm for capacitated clustering problem
???metadata.dc.creator???: Geetha, S.
Poonthalir, G.
Vanathi, P. T.
Keywords: Combinatorial optimization problem
Capacitated clustering problem
K-means algorithm
Problema de otimização combinatória
Problema de agrupamento capacitado
Algoritmo K-means
Publisher: Editora da UFLA
???metadata.dc.date???: 1-Dec-2009
Citation: GEETHA, S.; POONTHALIR, G.; VANATHI, P. T. Improved k-means algorithm for capacitated clustering problem. INFOCOMP: Journal of Computer Science, Lavras, v. 8, n. 4, p. 52-59, Dec. 2009.
Abstract: The Capacitated Clustering Problem (CCP) partitions a set of n items (eg. customer orders) into k disjoint clusters with known capacity. During clustering the items with shortest assigning paths from centroids are grouped together. The summation of grouped items should not exceed the capacity of cluster. All clusters have uniform capacity. The CCP is NP-Complete and Combinatorial optimization problem. Combinatorial optimization problem can be viewed as searching for the best item in a set of discrete items, which can be solved using search algorithm or meta heuristic. However, generic search algorithms have not guaranteed to find an optimal solution. Many heuristic algorithms are formulated to solve CCP. This work involves the usage of the best known clustering algorithm k-means with modification, that use priority as a measure which directs the search for better optimization. The iterative procedure along with priority is used for assigning the items to the clusters. This work is developed using MATLAB 7.0.1 and tested with more than 15 problem instances of capacitated vehicle routing problem (CVRP). The computational results are competitive when compared with the optimal solution provided for the problems.
Other Identifiers: http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/282
???metadata.dc.language???: eng
Appears in Collections:Infocomp

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

View Statistics


DSpace Software Copyright © 2002-2010  Duraspace - Feedback