Algorithms for optimizing the placement of stationary monitors

Andrew Romich, Guanghui Lan, J. Cole Smith

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

This article examines the problem of placing stationary monitors in a continuous space, with the goal of minimizing an adversarys maximum probability of traversing an origin-destination route without being detected. The problem arises, for instance, in defending against the transport of illicit material through some area of interest. In particular, we consider the deployment of monitors whose probability of detecting an intruder is a function of the distance between the monitor and the intruder. Under the assumption that the detection probabilities are mutually independent, a two-stage mixed-integer nonlinear programming formulation is constructed for the problem. An algorithm is provided that optimally locates monitors in a continuous space. Then, this problem is examined for the case where the monitor locations are restricted to two different discretized subsets of continuous space. The analysis provides optimization algorithms for each case and derives bounds on the worst-case optimality gap between the restrictions and the initial (continuous-space) problem. Empirically, it is shown that discretized solutions can be obtained whose worst-case and actual optimality gaps are well within practical limits.

Original languageEnglish (US)
Pages (from-to)556-576
Number of pages21
JournalIIE Transactions (Institute of Industrial Engineers)
Volume47
Issue number6
DOIs
StatePublished - Jun 3 2015
Externally publishedYes

Keywords

  • Network optimization
  • Nonlinear programming
  • Shortest-path network interdiction

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Algorithms for optimizing the placement of stationary monitors'. Together they form a unique fingerprint.

  • Cite this