A matheuristic for leader-follower games involving facility location-protection-interdiction decisions

Abstract

The topic of this chapter is the application of a matheuristic to the leaderfollower type of games-also called static Stackelberg games-that occur in the context of discrete location theory. The players of the game are a system planner (the leader) and an attacker (the follower). The decisions of the former are related to locating/relocating facilities as well as protecting some of those to provide service. The attacker, on the other hand, is interested in destroying (interdicting) facilities to cause the maximal possible disruption in service provision or accessibility. The motivation in the presented models is to identify the facilities that are most likely to be targeted by the attacker, and to devise a protection plan to minimize the resulting disruption on coverage as well as median type supply/demand or service networks. Stackelberg games can be formulated as a bilevel programming problem where the upper and the lower level problems with conflicting objectives belong to the leader and the follower, respectively. In this chapter, we first discuss the state of the art of the existing literature on both facility and network interdiction problems. Secondly, we present two fixed-charge facility location-protection-interdiction models applicable to coverage and median-type service network design problems. Out of these two, we focus on the latter model which also involves initial capacity planning and post-attack capacity expansion decisions on behalf of the leader. For this bilevel model, we develop a matheuristic which searches the solution space of the upper level problem according to tabu search principles, and resorts to a CPLEXbased exact solution technique to tackle the lower level problem. In addition, we also demonstrate the computational efficiency of using a hash function, which helps to uniquely identify and record all the solutions visited, thereby avoids cycling altogether throughout the tabu search iterations