A metaheuristic to solve the capacitated clustering problem

Abstract EN

One of the most important combinatorial optimisation problems (COPs) is the capacitated clustering problem (CCP).

this sort of problem involves dividing a set of nodes into a predefined number of clusters within specific limits (upper and lower); for each node in the cluster, a pair of nodes is defined that has a benefit value, and the total values of these benefits in the cluster must be maximised.

the CCP is of a non-deterministic polynomial-time hard (NP-hard) nature.

such problems cannot be practically solved by exact optimisation algorithms, so we must choose one of the metaheuristic algorithms to solve them.

the CCP has many applications in a variety of domains.

this paper aims to design a metaheuristic method that solves the CCP, with an artificial bee colony (ABC) as the metaheuristic algorithm.

the effectiveness of the proposed ABC based algorithm was confirmed through several computational experiments.

the results demonstrate that the proposed algorithm produced competitive outcomes compared to the state-of-the-art metaheuristics developed for the CCP.