New ideas for applying ant colony optimization to the set covering problem |
| |
Authors: | Zhi-Gang Ren Zu-Ren Feng Liang-Jun Ke Zhao-Jun Zhang |
| |
Affiliation: | 1. Department of Industrial Engineering, Seoul National University, Seoul 08826, Republic of Korea;2. Department of Materials and Production, Aalborg University, Aalborg 9220, Denmark;3. Institute for Industrial Systems Innovation, Seoul National University, Seoul 08826, Republic of Korea |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|