New ideas for applying ant colony optimization to the set covering problem
The set covering problem (SCP) is a well known NP-hard problem with many practical applications. In this research, a new approach based on ant colony optimization (ACO) is proposed to solve the SCP. The main differences between it and the existing ACO-based approaches lie in three aspects. First, it adopts a novel method, called single-row-oriented method, to construct solutions. When choosing a new column, it first randomly selects an uncovered row and only considers the columns covering this row, rather than all the unselected columns as candidate solution components. Second, a kind of dynamic heuristic information is used in this approach. It takes into account Lagrangian dual information associated with currently uncovered rows. Finally, a simple local search procedure is developed to improve solutions constructed by ants while keeping their feasibility. The proposed algorithm has been tested on a number of benchmark instances. Computational results show that it is able to produce competitive solutions in comparison with other metaheuristics. (C) 2010 Elsevier Ltd. All rights reserved.
ant colony optimization set covering problem local search metaheuristic