AN ALGORITHM SEARCHES FOR TABOO FOR THE CAPABLE PROBLEM OF LOCATING FACILITIES WITH PARTIAL COVERAGE AND SINGLE SOURCE

This paper deals with the Capacitated Partial Set Covering Location Problem with Single Source. Given a network, a set of potential capacitated facilities, and a set of customers with their demands, this problem consists of determining which facilities should be installed to minimize the total cost of the installations and guarantee that minimum demand and capacity constraints are met. Furthermore, each customer cannot be covered by more than one facility. We present a mathematical programming formulation to represent it and a Tabu Search-based algorithm to deal with large-scale instances of the problem since it is NP-hard. The results of the experiments using benchmark instances from the literature show that the Tabu Search algorithm finds high-quality solutions in shorter computational times when compared to the CPLEX solver applied to the formulation.