Patching the security breach: Locating and guarding the guards

Abstract

The guard placement problem, as the name implies, aims at placing a team of guards around a site. Main concerns are the dispersion of the guards and the mutual visibilities among them. After presenting the mathematical model and the computation of mutual visibility, we focus on a continuous solution approach based on local search. We then discuss a discrete approximation to the continuous problem, and propose a tree search solution approach. We next give an extension as a constrained problem, where each guard has to be seen by at least one other guard. Finally, we present a computational study for different instances to illustrate the proposed methods.