A fast and efficient ant colony optimization approach for the set covering problem

In this paper, we present an ant colony optimization (ACO) approach to solve the set covering problem. A constraint-oriented solution construction method is proposed. The main difference between it and the existing method is that, while adding a column to the current partial solution, it randomly selects an uncovered row and only considers the columns covering the row, but not all the unselected columns as candidate solution components. This decreases the number of candidate solution components and therefore accelerates the run speed of the algorithm. Moreover, a simple but effective local search procedure, which aims at eliminating redundant columns and replacing some columns with more effective ones, is developed to improve the quality of solutions constructed by ants while keeping their feasibility. The proposed algorithm has been tested on a number of benchmark instances. Computational results indicate that it is capable of producing high quality solutions and performs better than the existing ACO-based algorithms.