A bilevel P-median Problem for location and protection planning of critical facilities

Abstract

In this thesis, we focus on the problem of location and protection planning of critical facilities. This problem involves a Stackelberg game between a system planner (defender) and a potential attacker. The system planner aims to both find the locations of p critical service facilities and determine the ones among them that should be protected. Following this twofold action, the attacker decides which facilities to interdict having the location and protection information of the opened facilities. This problem involves strategic decisions which can be taken either sequentially or simultaneously. In this study, we consider both of these cases. In the first case, the system planner first decides on the locations and then determines the protection plan of these facilities. In the second case however, the system planner gives concurrent decisions about location and protection of the facilities. Both cases are of a bilevel nature. Therefore, we formulate this problem as a bilevel mixed-integer programming problem. We propose two solution methods. The first one is a two-phase tabu search heuristic for the case which involves concurrent decision process and a sequential solution method for the second case where the system planner prefers to give sequential decisions. Both of the methods include a binary search tree embedded into it. The efficiency of the proposed algorithms is tested on an extensive amount of randomly generated test instances each with two budget levels, namely low and high. We also consider another case where the system planner does not have any financial resources to protect the facilities from an attack. This line of vision helps system planner to determine the critical facilities from the attacker’s perspective. The results show that the protection budget plays a significant role in maintaining the service accessibility after a possible attack.