An iterated-tabu-search heuristic for a variant of the partial set covering problem

摘要

In this paper, we propose a heuristic algorithm to solve a new variant of the partial set covering problem. In this variant, each element e_i has a gain g_i (i.e., a positive profit), each set s_j has a cost c_j (i.e., a negative profit), and each set s_j is part of a unique group Gk that has a fixed cost f_k (i.e., a negative profit). The objective is to maximize profit and it is not necessary to cover all of the elements. We present an industrial application of the model and propose a hybrid heuristic algorithm to solve it; the proposed algorithm is an iterated-local-search algorithm that uses two levels of perturbations and a tabu-search heuristic. Whereas the first level of perturbation diversifies the search around the current local optimum, the second level of perturbation performs long jumps in the search space to help escape from local optima with large basins of attraction. The proposed algorithm is evaluated on thirty real-world problems and compared to a memetic algorithm. Computational results show that most of the solutions found by ITS are either optimal or very close to optimality.