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
Zugehörigkeit anzeigen +
Konferenzberichte:
EUROWorking Group on Locational Analysis Meeting EWGLA XXV

Verlag: VUBPRESS Brussels University Press

ISBN: 978 90 5718 493 2

Datum der Publikation: 2019

Art: Konferenz-Beitrag

GOOGLE SCHOLAR

Zusammenfassung

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.