A bilevel partial interdiction problem with capacitated facilities and demand outsourcing

Abstract

The bilevel partial interdiction problem with capacitated facilities and demand outsourcing involves a static Stackelberg game between a system planner and a potential attacker. The system planner (defender) is responsible for satisfying the overall demand of customers in an existing service network and aims at minimizing the total demand-weighted transportation cost while serving customers from the capacitated facilities. Simultaneously, he should consider the possible capacity reduction of some facilities in the wake of a destructive attack while the attacker's objective is to cause maximum disruption in the service level. The number of facilities to be attacked cannot be known a priori but heavily depends upon the attacker's interdiction budget. Regarding the partial interdiction concept, this defender-attacker relationship is formulated as a bilevel programming model. The attacker takes on the leader role, and forces the system planner, who acts as the follower, to meet customer demands with a higher outsourcing cost. Two di erent methods are proposed in this study. The rst method is a progressive grid search which is impracticable on large-sized problems. The second method is a multi-start revised simplex search heuristic which is based on the Nelder-Mead simplex search method and is developed to overcome the exponential time complexity of the rst method. We also develop an exhaustive search to solve all combinations of the full interdiction of the facilities to assess the bene t of partial interdiction from the perspective of the attacker. Our test results indicate that it would be more bene cial to disrupt facility capacities partially rather than totally from the perspective of the attacker.