The budget constrained r-interdiction median problem with capacity expansion |
| |
Authors: | Deniz Aksen Nuray Piyade Necati Aras |
| |
Institution: | 1. College of Administrative Sciences and Economics, Ko? University, Rumelifeneri Yolu, 34450, Sar?yer, Istanbul, Turkey 2. Department of Industrial Engineering, Bo?azi?i University, 34342, Bebek, Istanbul, Turkey
|
| |
Abstract: | In this article, we elaborate on a budget constrained extension of the r-interdiction median problem with fortification (RIMF). The objective in the RIMF is to find the optimal allocation of protection
resources to a given service system consisting of p facilities so that the disruptive effects of r possible attacks to the system are minimized. The defender of the system needs to fortify q facilities of the present system to offset the worst-case loss of r non-fortified facilities due to an interdiction in which the attacker’s objective is to cause the maximum possible disruption
in the service level of the system. The defender-attacker relationship fits a bilevel integer programming (BIP) formulation
where the defender and attacker take on the respective roles of the leader and the follower. We adopt this BIP formulation
and augment it with a budget constraint instead of a predetermined number of facilities to be fortified. In addition, we also
assume that each facility has a flexible service capacity, which can be expanded at a unit cost to accommodate the demand
of customers who were serviced by some other interdicted facility before the attack. First, we provide a discrete optimization
model for this new facility protection planning scenario with a novel set of closest assignment constraints. Then, to tackle
this BIP problem we use an implicit enumeration algorithm performed on a binary tree. For each node representing a different
fortification scheme, the attacker’s problem is solved to optimality using Cplex 11. We report computational results obtained
on a test bed of 96 randomly generated instances. The article concludes with suggestions for future research. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|