Improved K-Means Algorithm for Capacitated Clustering Problem

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.