Formulation and algorithms for the robust maximal covering location problem

Let N be the line-set and M be the column-set of a matrix {aij}, such that aij=1 if line i∈N is covered by column j∈M, or aij=0 otherwise. Besides, let bj≥0 be the benefit associated with a column j∈M. Given a constant T<|M|, the NP-Hard Maximal Covering Location Problem (MCLP) consists in finding a subset X⊆M with the maximum sum of benefits, such that |X|≤T and every line in N is covered by at least one column in X. In this study, we investigate the min-max regret Maximal Covering Location Problem, a robust counterpart of MCLP, where the benefit of each column is uncertain and modeled as an interval data. The objective is to find a robust solution that minimizes the maximal regret over all possible combinations of values for the columns benefit. This problem has applications in disaster relief. We propose a MILP formulation, an exact and 2-approximation algorithms, and test them using classical instances from the literature.