A bilevel exposure-oriented sensor location problem for border security

We propose a bilevel math programming model for locating a heterogeneous set of sensors to maximize the minimum exposure of an intruder's penetration path through a defended region. Our formulation also allows a defender to specify minimum probabilities of coverage for a subset of the located sensors (e.g., the most valuable sensors) and for high-value asset locations in the defended region. We reformulate the bilevel program to a single-level optimization problem for which instances can be readily solved using a commercial solver. Given the locations of a defender's sensors, we additionally formulate three alternative path identification models corresponding to conceptually-motivated intrusion-path metrics. We examine a test instance for the air defense of a border region against intrusion by an enemy aircraft; upon identifying the optimal, respective defender asset location and intruder routing solutions, we examine the intruder-optimal solutions corresponding to each of three alternative metric-specific paths, illustrating the relative impact of an intruder choosing an inappropriate metric. Sensitivity analyses are conducted to examine the effect of several model parameters on solution quality and required computational effort.