TY - JOUR
T1 - A heuristic algorithm for minimax sensor location in the plane
AU - Cavalier, Tom M.
AU - Conner, Whitney A.
AU - del Castillo, Enrique
AU - Brown, Stuart I.
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. 0400140. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
PY - 2007/11/16
Y1 - 2007/11/16
N2 - This paper addresses the problem of locating a finite number of sensors to detect an event in a given planar region. The objective is to minimize the maximum probability of non-detection where the underlying region consists of a convex polygon. The sensor location problem has a multitude of applications, including the location of aircraft detection sensors, the placement of sentries along a border to detect enemy penetration, the detection of nuclear tests, and the detection of natural and hazardous man-made events. The problem is a difficult nonlinear nonconvex programming problem even in the case of two sensors. A fast heuristic based on Voronoi polygons is developed in this paper. The algorithm can quickly generate high-quality solutions. Computational experience is provided.
AB - This paper addresses the problem of locating a finite number of sensors to detect an event in a given planar region. The objective is to minimize the maximum probability of non-detection where the underlying region consists of a convex polygon. The sensor location problem has a multitude of applications, including the location of aircraft detection sensors, the placement of sentries along a border to detect enemy penetration, the detection of nuclear tests, and the detection of natural and hazardous man-made events. The problem is a difficult nonlinear nonconvex programming problem even in the case of two sensors. A fast heuristic based on Voronoi polygons is developed in this paper. The algorithm can quickly generate high-quality solutions. Computational experience is provided.
UR - http://www.scopus.com/inward/record.url?scp=34249073730&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34249073730&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2006.10.055
DO - 10.1016/j.ejor.2006.10.055
M3 - Article
AN - SCOPUS:34249073730
SN - 0377-2217
VL - 183
SP - 42
EP - 55
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -