SOLVING THE CAPACITATED CLUSTERING PROBLEM WITH GENETIC ALGORITHMS

ABSTRACT

The Capacitated Clustering Problem (CCP) partitions a group of n items (e.g., customer orders) into k clusters (e.g., vehicles) and restricts the capacity of each cluster. During the partitioning, points with the shortest assigning paths are grouped together, and the objective function attempts to minimize the total assigning cost. The CCP is NP-complete and exact optimization integer programming algorithms are ineffective for large cases. Therefore, this study applies genetic algorithms (GAs), the effective metaheuristic for combinatorial optimization problems, to solve the CCP. For the 0-1 nature of CCP, this problem is coded as binary strings for genetic operating. This binary coding facilitates the evolutionary search with the standard steps of a genetic algorithm, i.e., modifying the genetic operators is unnecessary and infeasible solutions do not exist except for violation of the capacity constraint. In addition, an adaptive penalty function is adopted to handle the constraint of capacity and, according to our results, can effectively solve constrained problems in GA by enhancing the convergence and solution quality. Moreover, a computational study is performed, in which the proposed GA method is evaluated by two sets of test problems and compared with other heuristics and the integer optimization method of the LINDO software as well. Analytic results demonstrate the effectiveness of the proposed GA method in solving the CCP.

Keywords:

• capacitated clustering problem
• genetic algorithms
• iterative heuristic algorithm
• binary coding
• adaptive penalty function