Downgrading edges in the maximal covering locationproblem

Abstract

In this presentation, we tackle the downgrading maximal covering location problem within a network. In this problem, two decisions are made: determining the facility locations and increasing edge lengths to reduce coverage. Two actors with conflicting objectives are involved: a) The location planner aims to maximize the covered demand whileanticipating that an attacker will attempt to reduce coverage by increasing the length of the edges. b) The attacker seeks to maximize the demand initially covered by the facilities but left uncovered after the downgrade. To achieve this, they can increase the length of certain edges within a specified budget. We introduce a bilevel mixed-integer program to formulate the problem, a preprocessing phase, and a matheuristic algorithm to address it. Additionally, computational results are presented to illustrate the potential and limitations of the proposed algorithm.