A modified bacterial foraging algorithm for three-index assignment problem

Abstract

The Three-Index Assignment Problem (3-AP) is well-known combinatorial optimization problem which has been shown to be NP-hard. Since it is very difficult to find the best result in polynomial time, many heuristic methods have been proposed to obtain near optimal solutions in reasonable time. In this paper, a modified Bacterial Foraging Optimization Algorithm (BFOA) is proposed to solve 3-AP. BFOA is inspired by the social foraging behaviour of Escherichia coli (Ecoli). Algorithm imitates the behaviour of the foraging bacteria Ecoli and aims to eliminate those bacteria that have weak foraging methods and maintaining those bacteria that have strong foraging methods. The Hungarian method (most known method for solving the classical linear two-dimensional assignment problem) is integrated to BFOA algorithm at repositioning phase to swim farther and faster to find the best solution. Proposed algorithm has been tested and benchmarked with other algorithms in literature and results show that the new algorithm outperforms other heuristics in literature in terms of solution quality.