Modifications and Additions to Ant Colony Optimisation to Solve the Set Partitioning Problem

Abstract

Ant colony optimisation has traditionally been used to solve problems that have few/light constraints or no constraints at all. Algorithms to maintain and restore feasibility have been successfully applied to such problems. Set partitioning is a very constrained combinatorial optimisation problem, for which even feasible solutions are difficult to construct. In this paper a binary ant colony optimisation framework is applied to this problem. To increase its effectiveness, feasibility restoration, solution improvement algorithms and candidate set strategies are added. These algorithms can be applied to complete solution vectors and as such can be used by any solver. Moreover, the principles of the support algorithms may be applied to other constrained problems. The overall results indicate that the ant colony optimisation algorithm can efficiently solve small to medium sized problems. It is envisaged that in future research parallel computation could be used to simultaneously reduce solver time while increasing solution quality.