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

Journal of Advances in Computer Research

شناسنامه علمی شماره، دوره 4، شماره 1، فروردین 2013، صفحه 89-100   

نویسندگان

Narges Mahmoodi Darani^{* 1}؛ Vahid Ahmadi²؛ Zahra Saadati Eskandari³؛ Majid Yousefikhoshbakht⁴

¹Department of Mathematic, Malayer Branch, Islamic Azad University, Malayer, Iran

²Department of Mathematic, Ahvaz Branch, Islamic Azad University, Ahvaz, Iran

³Young Researchers & Elite Club, Fereydan Branch, Islamic Azad University, Fereydan, Iran

⁴Young Researchers & Elite Club, Hamedan Branch, Islamic Azad University, Hamedan, Iran

چکیده

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.

کلیدواژه‌ها

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