Maximal Covering Location Problem with Different Levels of interdiction

Abstract

In this paper we introduce an interdiction problem for a maximal covering location problem in which an interdictor can attack each facility in different levels. The system includes real and dummy facilities in candidate locations and also identifies fortified facilities in order to maximize the covering of demand points. Dummy facility is a facility that cannot service demand points, but the interdictor considers every facility as a real one. He has different levels of weapons to interdict facilities. Each weapon reduces a specific amount of the covering radius. The interdictor’s objective is to identify an interdiction scenario with his limited resources in order to minimize the covering of the demand points. A bi-level formulation is presented to model this two-player game problem. <br><br>To solve this problem we use a combination of exact linear programming optimization technique and comprehensive enumeration. To reduce the computing time a heuristic approach based on local search is proposed.