A bilevel partial interdiction problem with capacitated facilities and demand outsourcing

Abstract

In this paper, partial facility interdiction decisions are integrated for the first time into a median type network interdiction problem with capacitated facilities and outsourcing option. The problem is modeled as a static Stackelberg game between an intelligent attacker and a defender. The attacker's (leader's) objective is to cause the maximum (worst-case) disruption in an existing service network subject to an interdiction budget. On the other hand, the defender (follower) is responsible for satisfying the demand of all customers while minimizing the total demand-weighted transportation and outsourcing cost in the wake of the worst-case attack. She should consider the capacity reduction at the interdicted facilities where the number of interdictions cannot be known a priori, but depends on the attacker's budget allocation. We propose two different methods to solve this bilevel programming problem. The first one is a progressive grid search which is not viable on large sized instances. The second one is a multi-start simplex search heuristic developed to overcome the exponential time complexity of the first method. We also use an exhaustive search method to solve all combinations of full interdiction to assess the advantage of partial interdiction for the attacker. The test results suggest that under the partial interdiction approach the attacker can achieve a better utilization of his limited resources.