Date of this Version


Document Type

Conference Paper

Publication Details

Published Version.

Randall, M. & Lewis, A. (2010). Modifications and additions to ant colony optimisation to solve the set partitioning problem. Paper presented at the e-Science 2010: Sixth IEEE international conference on e-Science, Brisbane, Australia.

Access the conference website.

2010 HERDC submission. FoR Code: 080600

© Copyright IEEE, 2010. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.




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 simultaneouly reduce solver time while increasing solution quality.



This document has been peer reviewed.