A Tabu Search algorithm for the single source capacitated partial set covering location problem

Abstract This work introduces the Single Source Capacitated Partial Set Covering Location Problem (SSCPSCLP). Given a set of potential capacitated facilities and a set of customers with their demands, this problem consists of determining the facilities to be opened and the customers to be served to minimize the total cost of opening facilities, ensuring that at least a minimum amount of the total demand is served, only covered customers can be served, the capacity of the facilities is not exceeded, and each customer can be served by at most one facility. This work introduces a mathematical model for the problem and, since it is NP-hard, develops an algorithm based on the Tabu Search (TS) metaheuristic to handle large-scale instances. The TS algorithm explores the problem’s solution space through two neighborhoods, one of which is incorporated into a local search procedure that is periodically applied. The initial solution is generated either by a constructive greedy heuristic or by solving the linear relaxation of the SSCPSCLP. Four TS variants were proposed, differing in the method for generating the initial solution and in the use of local search. The results of computational experiments on instances from the literature show that the TS algorithm finds high-quality solutions in a shorter runtime than a mathematical programming-based solver and that the version using initial solutions from the linear relaxation of the problem and local search performs best.