Upgrading the Maximal Covering Location Problem

  1. Marta Baldomero-Naranjo 3
  2. Jörg Kalcsics 1
  3. Alfredo Marín 2
  4. Antonio M. Rodríguez-Chía 3
  1. 1 School of Mathematics, University of Edinburgh, Edinburgh, EH9 3FD, United Kingdom
  2. 2 Departamento de Estadística e Investigación Operativa, Universidad de Murcia, Facultad de Matemáticas, Murcia, 30100, Spain
  3. 3 Departamento de Estadística e Investigación Operativa, Universidad de Cádiz, Facultad de Ciencias, Puerto Real (Cádiz), 11510, Spain
Mostrar afiliaciones +
Actas:
EUROWorking Group on Locational Analysis Meeting EWGLA XXV

Editorial: VUBPRESS Brussels University Press

ISBN: 978 90 5718 493 2

Año de publicación: 2019

Tipo: Aportación congreso

GOOGLE SCHOLAR

Resumen

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.