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

  1. Marta Baldomero-Naranjo 1
  2. Jörg Kalcsics 2
  3. Antonio M. Rodríguez Chía 1
  1. 1 Departamento de Estadística e Investigación Operativa, Universidad de Cádiz, Spain.
  2. 2 School of Mathematics, University of Edinburgh, UK.
Actes:
THE XI INTERNATIONAL WORKSHOP ON LOCATIONAL ANALYSIS AND RELATED PROBLEMS

Editorial: Universidad Miguel Hernández

ISBN: 978-84-123480-6-4

Any de publicació: 2022

Pàgines: 19

Tipus: Aportació congrés

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.