Applying ant colony optimization algorithm to solve the deterministic single objective assignment problem
Loading...
Date
2024-11-01
Authors
Pathirana, C. P. S.
Daundasekara, W. B.
Journal Title
Journal ISSN
Volume Title
Publisher
Postgraduate Institute of Science (PGIS), University of Peradeniya, Sri Lanka
Abstract
This study proposed a metaheuristic algorithm known as the Ant Colony Optimization Algorithm (ACOA) to solve the deterministic Assignment Problem (AP) with a single objective. The AP is a special type of linear programming problem where the objective is to minimize the cost or time of completing a number of jobs by a number of persons/machines. The ACOA was designed based on the foraging behaviour of ants seeking a path between their colony and source of food. The ACOA is a probabilistic technique for finding the optimal path of the AP. When searching for food, ants initially explore the area surrounding their nest in a random manner. While moving, ants leave a chemical known as pheromone on the ground along the trail. When choosing their way, they tend to choose the path marked by strong pheromone concentrations. Ants’ pheromone laying phenomenon and, hence, locating the closest food source is adopted in the selection of the shortest path in the ACOA. To illustrate the proposed method, an AP was formulated by randomly generating the Assignment Cost Matrix (ACM). For the first row of the ACM, the transition probabilities were determined applying the ACOA. Subsequently, the shortest path for the first row of the ACM is found by comparing the cumulative probability solution set and the generated random set. The optimal solution for the first row of the ACM was recorded, and afterwards, the row and the column of the ACM corresponding to the selected path were excluded. This process was repeated for the rest of the rows and the optimal solution respect to each row is recorded. The proposed iterative technique converges to the optimal solution of the AP. The optimal assignment found using this method was verified by applying the Hungarian Algorithm (HA). The results indicate that this method is effective in finding the optimal assignment and performs better in terms of computational time for large-scale APs compared to the HA. Future works will focus on applying APs with uncertain assignment costs.
Description
Keywords
Ant colony optimization algorithm , Assignment cost matrix , Assignment problem , Hungarian algorithm
Citation
Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P 58