Journal
COMPUTERS & INDUSTRIAL ENGINEERING
Volume 58, Issue 4, Pages 774-784Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2010.02.011
Keywords
Set covering problem; Ant colony optimization; Local search; Metaheuristic
Funding
- National Natural Science Foundation of China [60875043, 60905044]
- Ministry of Education of China [20090201120042]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available