The upgrading version of the Maximal Covering Location Problem: an algorithmic approach

Resumen

In this talk, we analyze the upgrading version of the maximal covering location problem with edge length modifications on networks (UpMCLP). The Up-MCLP aims at locating p facilities to maximize the coverage taking into account that the length of the edges can be reduced subject to a budget constraint. Therefore, we look for both solutions: the optimal location of p facilities and the optimal upgraded network. Note that for each edge, we are 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 each edge). Furthermore, a total budget for reductions is given. In [1] several Mixed-Integer Programming formulations were proposed to solve this problem on general networks, on which the problem is NP-hard. In this talk, we turn our attention to particular networks such as stars,paths, and trees and study the complexity of this problem. Moreover, we provide polynomial and pseudo-polynomial time algorithms to solve theproblem under different assumptions for the parameters.