An effective binary artificial bee colony algorithm for maximum set k-covering problem

摘要

Given a row set M and a column set C, where each column in C covers several rows of M, the maximum set k-covering problem (MKCP) is to select k columns from C, such hat the number of rows covered by the selected columns is maximized. It can be formulated as linear integer programming, and has several real world applications. Several heuristic approaches have been previously presented for solving the MKCP. However, the obtained solution quality is not stable, and the solution time increases very quickly as the size of the instance increases. This work proposes a hybrid binary artificial bee colony algorithm (HBABC) to solve the MKCP. First, based on the characteristic of MKCP, HBABC redesigns a food source updating method. The new updating method uses the previously found solutions to guide the search. Second, to improve the exploitation ability of the HBABC, a tabu based simulated annealing (TBSA) is proposed. Moveover, we employ a bucket sorting technique to speed up the TBSA. Finally, the computational results on 75 benchmark instances demonstrate that the HBABC competes favorably with other algorithms. Specifically, our algorithm improves the best known solutions on about 20 percent of the tested instances. In addition, the HBABC performs better than two binary artificial bee colony algorithms on the tested instances. (c) 2020 Elsevier Ltd. All rights reserved.