This paper considers the problem of placing suicide bomber detectors. The model takes into account the probability that a given detector may fail to detect bombers. In brief, the model assumes a layout of squares, some of which are blocked and some of which correspond to entry points to the area being monitored. The detectors are assumed to be capable of detecting a bomber within a certain distance with a given probability. The model considers the paths that a suicide bomber might take from an entrance square to the target square in which detonation could take place. The goal is to place a fixed number of detectors in order to minimize the possible number of casualties. Some squares can be eliminated from consideration as detector locations because they are “dominated” by other squares, that is, other squares cover the same paths as the dominated square.

Several algorithms for placing the detectors are considered: a greedy algorithm in which successive squares are chosen to maximally reduce the expected casualties; a greedy randomized adaptive search procedure (GRASP); a hill climbing (HC) algorithm in which the initial placement of the detectors is successively improved; an evolutionary algorithm (EA); and a univariate marginal distribution algorithm (UMDA), which is a form of EA. The algorithms are first compared via a set of synthetic scenarios in which the area to be monitored is a square array of locations with random instances of blocked squares.

The HC algorithm consistently finds the best solution, beating all others. The HC and greedy algorithms are run on three “more realistic” examples: a large plaza, an old-town urban area with narrow streets, and a mixture of these two. Once again, the HC algorithm proves superior. While the theoretical underpinnings of the paper are not new, the application is worthwhile in view of the potential for reducing--or even eliminating--casualties.