Ant colony optimization algorithm to solve deterministic multi-objective assignment problem

Abstract

This study proposes a metaheuristic algorithm known as the Ant Colony Optimization Algorithm (ACOA) to solve the deterministic Multi-Objective Assignment Problem (MOAP). MOAP consists of several objectives to be optimized simultaneously. ACOA is one of the most prominent biologically inspired algorithms to solve optimization problems. Multi-Objective Ant Colony Optimization Algorithm (MOACOA), which is based on the ACOA, is a probabilistic approach for finding the optimal path of the MOAP. The proposed algorithm is parameterized by the number of ant colonies and the number of pheromone trails. In this study, MOACOA is applied to solve a MOAP, where the assignment costs are randomly generated following the Uniform distribution. Initially, for the first row of each of the Assignment Cost Matrix (ACM) corresponding to the objective function, the transition probabilities with equal weights are determined by applying the MOACOA. Then, under the pheromone update rule, the optimal assignment for the first row of each ACM is determined by comparing the cumulative probability solution set and the generated random set. The optimal solution for the first row of each of the ACMs is recorded, and afterward, the row and the column of each of the ACMs corresponding to the selected path are excluded. This process is repeated for the rest of the rows of each of the ACMs and the optimal solution with respect to each row is recorded. This process terminates when the proposed iterative technique converges to the optimal solution of the MOAP. The proposed algorithm is coded in Python programming language and the efficiency of the algorithm is compared with an existing method known as Technique for an Order of Preference by Similarity to Ideal Solution (TOPSIS). The proposed MOACOA is proven to be capable of solving large-scale MOAP in less computational time compared to the TOPSIS method.