RI UFLA (Universidade Federal de Lavras) >
Revistas UFLA >
Please use this identifier to cite or link to this item:
|Title: ||Improved k-means algorithm for capacitated clustering problem|
|???metadata.dc.creator???: ||Geetha, S.|
Vanathi, P. T.
|Keywords: ||Combinatorial optimization problem|
Capacitated clustering problem
Problema de otimização combinatória
Problema de agrupamento capacitado
|Publisher: ||Editora da UFLA|
|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 ﬁnd 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 modiﬁcation, 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|
|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.