The maximal covering location problem with edge downgrades

Résumé

Introduction. This talk deals with an extension of the well-known Maximal Covering Location Problem(MCLP), see. It considers that an agent (attacker) can modify the length of someedges within a budget, increasing the distance from the clients to the facilities. Under thisassumption, the Downgrading Maximal Covering Location Problem emerges as a significantchallenge, involving the interests of both the facility location planner and potential attackers.Note that this implies that the distances in the network are modified during the optimizationproblem, thus, the distance between two nodes after the downgrades will have to be computedwithin the model.This study falls within the domain of downgrading (upgrading) network problems, in whichspecific elements initially treated as fixed inputs in the classical version are now transformedinto decision variables (e.g. the length of the edges). As far as we know, it is the first studyanalysing edge downgrades. The version of the problem where edge upgrades are consideredhas been discussed in 1,ContributionsThe problem entails the strategic location of facilities within the nodes of a network tomaximise coverage while anticipating and mitigating potential attacks aimed at reducing thiscoverage. Then, it comprises an interaction between two distinct actors, each with conflictingobjectives:• The location planner aims to maximise the covered demand while anticipating that anattacker will attempt to reduce coverage by increasing the length of the edges.• The attacker seeks to maximise the demand initially covered by the facilities but leftuncovered after the downgrade. To achieve this, they can increase the length of certainedges within a specified budget.We propose a mixed-integer linear bilevel formulation to model the problem. Moreover, we introduce a strategy to preprocess the data to reduce the number of variables and constraints of the formulation. Furthermore, a matheuristic algorithm to solve the problem is developed. For this algorithm, we present some variants (levels of intensity), which allow the user to decide the best trade-off between the computational time employed and the quality of the solution.Several computational experiments are carried out to illustrate the advantages of applying the introduced model rather than using the classical MCLP and to show the potential and limitations of the proposed matheuristic algorithm. The solutions provided by the matheuristic are compared with the ones obtained by the general bilevel solver developed in [4].