Solving the Capacitated Clustering Problem by aCombined Meta-Heuristic Algorithm

Subject Areas : B. Computer Systems Organization

Narges  Mahmoodi Darani ¹ (Department of Mathematic, Malayer Branch, Islamic Azad University, Malayer, Iran)
Vahid  Ahmadi ² (Department of Mathematic, Ahvaz Branch, Islamic Azad University, Ahvaz, Iran)
Zahra  Saadati Eskandari ³ (Young Researchers & Elite Club, Fereydan Branch, Islamic Azad University, Fereydan, Iran)
Majid  Yousefikhoshbakht ⁴ (Young Researchers & Elite Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran)

Received: 2013-08-28 Accepted : 2013-08-28 Published : 2013-01-01

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

Abstract :

The capacitated clustering problem (CCP) is one of the most important combinational optimization problems that nowadays has many real applications in industrial and service problems. In the CCP, a given n nodes with known demands must be partitioned into k distinct clusters in which each cluster is detailed by a node acting as a cluster center of this cluster. The objective is to minimize the sum of distances from all cluster centers to all other nodes in their cluster, such that the sum of the corresponding node weights does not exceed a fixed capacity and every node is allocated to exactly one cluster. This paper presents a hybrid three-phase meta-heuristic algorithm (HTMA) including sweep algorithm (SA), ant colony optimization (ACO) and two local searches for the CCP. At the first step, a feasible solution of CCP is produced by the SA, and at the second step, the ACO, insert and swap moves are used to improve solutions. Extensive computational tests on standard instances from the literature confirm the effectiveness of the presented approach compared to other meta-heuristic algorithms.