Solving the Capacitated Clustering Problem by a Combined Meta-Heuristic Algorithm

The capacitated clustering problem (CCP) is one of the most importantcombinational optimization problems that nowadays has many real applications inindustrial and service problems. In the CCP, a given n nodes with known demandsmust be partitioned into k distinct clusters in which each cluster is detailed by anode acting as a cluster center of this cluster. The objective is to minimize the sumof distances from all cluster centers to all other nodes in their cluster, such that thesum of the corresponding node weights does not exceed a fixed capacity and everynode is allocated to exactly one cluster. This paper presents a hybrid three-phasemeta-heuristic algorithm (HTMA) including sweep algorithm (SA), ant colonyoptimization (ACO) and two local searches for the CCP. At the first step, a feasiblesolution of CCP is produced by the SA, and at the second step, the ACO, insert andswap moves are used to improve solutions. Extensive computational tests onstandard instances from the literature confirm the effectiveness of the presentedapproach compared to other meta-heuristic algorithms.

Keywords:

Capacitated Clustering Problem , NP-hard Problems , Ant Colony Optimization , Sweep Algorithm , Local Search