Upgrading edges in the maximal covering location problem

Resumen

The upgrading version of the maximal covering location problem with edge length modifications on networks is studied. This problem aims at locating p facilities on the nodes so as to maximize coverage, considering that the length of the edges can be reduced at a cost, subject to a given budget. Hence, we have to decide on: the optimal location of p facilities and the optimal edge length reductions. As far as we know, it is the first time that this problem is discussed in the literature. We have proposed three different mixed-integer formulations to model the problem.Furthermore, we develop an effective preprocessing phase. Besides, we derive several sets of valid inequalities. The performance of the three formulations and the improvement provided by the preprocessing phase and the valid inequalities can be appreciated in the computational results.We believe that this work could be an encouraging starting point to address the upgrading version of other classical location problems.