An ant colony optimization heuristic for constrained task allocation problem

• Developed an ant colony optimization (ACO) algorithm for constrained task allocation problem (CTAP).
• Compared the ACO model results with problem specific lower bounds and iterated greed heuristic using real-world and simulated datasets.
• Showed that ACO algorithm performs very well.
• For known optimal solutions the ACO results have a relative gap of less than 0.5%.
• Mathematical programming procedures for computing lower bounds for CTAP are presented.

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.