An ant colony optimization heuristic for constrained task allocation problem

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

I present an ant colony optimization (ACO) heuristic for solving the constraint task allocation problem (CTAP). Using real-world and simulated datasets, I compare the results of ACO with those of mixed integer programming (MIP) formulation, iterated greedy (IG) heuristic, and tighter of linear programming or Lagrangian relaxation based lower bounds. For datasets where optimal results could be obtained using the MIP formulation, the ACO results were either optimal or very tight with an average relative gap of less than 0.5% from the optimal value. When comparing the ACO results to the best lower bound, the ACO results had an average relative gap of approximately 3%. In all cases, the ACO algorithm found better results than the IG heuristic. The results from my experiments indicate that the proposed ACO heuristic is very promising for solving CTAPs.

Original languageEnglish (US)
Pages (from-to)37-47
Number of pages11
JournalJournal of Computational Science
Volume7
DOIs
StatePublished - Mar 1 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Modeling and Simulation

Fingerprint

Dive into the research topics of 'An ant colony optimization heuristic for constrained task allocation problem'. Together they form a unique fingerprint.

Cite this