A multi-objective, bilevel sensor relocation problem for border security

Consider a set of sensors having varying capabilities and respectively located to maximize an intruder’s minimal expected exposure to traverse a defended border region. Given two subsets of the sensors that have been respectively incapacitated or degraded, we formulate a multi-objective, bilevel optimization model to relocate surviving sensors to maximize an intruder’s minimal expected exposure to traverse a defended border region, minimize the maximum sensor relocation time, and minimize the total number of sensors requiring relocation. Our formulation also allows the defender to specify minimum preferential coverage requirements for high-value asset locations and emplaced sensors. Adopting the ε-constraint method for multi-objective optimization, we subsequently develop a single-level reformulation that enables the identification of non-inferior solutions on the Pareto frontier and, consequently, identifies trade-offs between the competing objectives. We demonstrate the aforementioned model and solution procedure for a scenario in which a defender is relocating surviving air defense assets to inhibit intrusion by a fixed-wing aircraft.