RT journal article
T1 Upgrading edges in the maximal covering location problem
A1 Baldomero Naranjo, Marta
A1 Kalcsics, Jörg
A1 Marín, Alfredo
A1 Rodríguez Chía, Antonio Manuel
A2 Estadística e Investigación Operativa
K1 Location
K1 Covering problems
K1 Networks
K1 Upgrading problems
K1 Integer programming
AB We study the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem aims at locating p facilities on the vertices (of the network) so as to maximise 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. This problem is NP-hard on general graphs. To solve it, we propose three different mixed-integer formulations and a preprocessing phase for fixing variables and removing some of the constraints. Moreover, we strengthen the proposed formulations including valid inequalities. Finally, we compare the three formulations and their corresponding improvements by testing their performance over different datasets. © 2022 The Author(s)
PB ELSEVIER
SN 0377-2217
YR 2022
FD 2022
LK http://hdl.handle.net/10498/26922
UL http://hdl.handle.net/10498/26922
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 11-nov-2026