Modifications and additions to ant colony optimisation to solve the set partitioning problem

Marcus Randall*, Andrew Lewis

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

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

Original languageEnglish
Title of host publicationProceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010
Pages110-116
Number of pages7
DOIs
Publication statusPublished - 2010
Event6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 - Brisbane, QLD, Australia
Duration: 7 Dec 201010 Dec 2010

Conference

Conference6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010
CountryAustralia
CityBrisbane, QLD
Period7/12/1010/12/10

    Fingerprint

Cite this

Randall, M., & Lewis, A. (2010). Modifications and additions to ant colony optimisation to solve the set partitioning problem. In Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 (pp. 110-116). [5693150] https://doi.org/10.1109/eScienceW.2010.27