Efficient Deployment of Mobile Detectors for Security Applications

We present a real-world problem that arises in security threat detection applications. The problem consists of deploying mobile detectors on moving units that follow predefined routes. Examples of such units are buses, coaches, and trolleys. Due to a limited budget not all available units can be equipped with a detector. The goal is to equip a subset of units such that the utility of the resulting coverage is maximized. Existing methods for detector deployment are designed to place detectors in fixed locations and are therefore not applicable to the problem considered here. We formulate the planning problem as a binary linear program and present a coverage heuristic for generating effective deployments in short CPU time. The heuristic has theoretical performance guarantees for important special cases of the problem. The effectiveness of the coverage heuristic is demonstrated in a computational analysis based on 28 instances that we derived from real-world data.