On the complexity of the upgrading version of the Maximal Covering Location Problem

Resum

We study the upgrading version of the maximal covering location problem with edge length modifications on networks (Up-MCLP). The UpMCLP aims at locating p facilities to maximize the coverage taking into account that the length of the edges can be reduced subject to a budgetconstraint. Therefore, we look for both solutions: the optimal location of p facilities and the optimal upgraded network. Note that for each edge, weare given its current length, an upper bound on the maximal reduction of its length, and a cost per unit of reduction (which can be different for eachedge). Furthermore, a total budget for reductions is given. In this talk, we focus on the complexity of this problem. Since it is a particular case of the Maximal Covering Location Problem, the Up-MCLP is NP-hard on general graphs. We analyze different types of graphs (paths, trees, stars, etc.) and study the complexity of the single-facility and the multi-facility version of the problem under different assumptions on the model parameters. We prove that this problem can be solved in polynomial time and pseudo-polynomial time in some particular cases. We derive algorithms for solving them. Moreover, we show several particular cases in which the problem is NP-hard.