The r-interdiction median problem with probabilistic protection and its solution algorithm

This paper discusses the critical infrastructure protection problem in supply systems regarding potential intentional attacks. Considering that the protection of a facility cannot be always successful, we present the r-interdiction median problem with probabilistic protection. Defensive resources are allocated according to the degree of importance of service facilities. Computational experiments demonstrate the benefits brought by centralizing resources to a few critical sites, as well as the importance of introducing probabilistic factors. Furthermore, we discuss the problem in a scenario of multiple interdictors. It is found that the worst-case interdictions made by multiple interdictors may cause much more serious system impairment than a single interdictor. Such losses can sometimes be effectively alleviated by adjustment of fortification plans. To solve the problem, we propose an iterated greedy search method which produces good approximations to optimal fortification strategies rather fast, even for instances of considerable size.