A heuristic algorithm for minimax sensor location in the plane
作者： Tom M. Cavalier , Whitney A. Conner , Enrique del Castillo , Stuart I. Brown
DOI: 10.1016/J.EJOR.2006.10.055
关键词: Heuristic (computer science) 、 Mathematics 、 Minimax 、 Finite set 、 Nonlinear programming 、 Heuristics 、 Voronoi diagram 、 Nonlinear system 、 Mathematical optimization 、 Convex polygon
摘要: This paper addresses the problem of locating a finite number sensors to detect an event in given planar region. The objective is minimize maximum probability non-detection where underlying region consists convex polygon. sensor location has multitude applications, including aircraft detection sensors, placement sentries along border enemy penetration, nuclear tests, and natural hazardous man-made events. difficult nonlinear nonconvex programming even case two sensors. A fast heuristic based on Voronoi polygons developed this paper. algorithm can quickly generate high-quality solutions. Computational experience provided.
elsevier.com
sci-hub.se 参考文章(22)
Masao Iri, Kazuo Murota, Takao Ohya, A fast Voronoi-diagram algorithm with applications to geographical optimization problems System Modelling and Optimization. pp. 273- 288 ,(1984) , 10.1007/BFB0008901
Simon R. Saunders, Saunders R Simon, Antennas and Propagation for Wireless Communication Systems ,(1999)
Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure ACM Computing Surveys. ,vol. 23, pp. 345- 405 ,(1991) , 10.1145/116873.116880
ZVI DREZNER, GEORGE O. WESOLOWSKY, On the best location of signal detectors Iie Transactions. ,vol. 29, pp. 1007- 1015 ,(1997) , 10.1080/07408179708966419
Vladimir F. Demjanov, Algorithms for some minimax problems Journal of Computer and System Sciences. ,vol. 2, pp. 342- 380 ,(1968) , 10.1016/S0022-0000(68)80034-0
Z. Drezner, G. O. Wesolowsky, A New Method for the Multifacility Minimax Location Problem Journal of the Operational Research Society. ,vol. 29, pp. 1095- 1101 ,(1978) , 10.1057/JORS.1978.241
Michael Ian Shamos, Dan Hoey, Closest-point problems foundations of computer science. pp. 151- 162 ,(1975) , 10.1109/SFCS.1975.8
Atsuo Suzuki, Zvi Drezner, The p-center location problem in an area Location Science. ,vol. 4, pp. 69- 82 ,(1996) , 10.1016/S0966-8349(96)00012-5
Jack Elzinga, Donald Hearn, W. D. Randolph, Minimax Multifacility Location with Euclidean Distances Transportation Science. ,vol. 10, pp. 321- 336 ,(1976) , 10.1287/TRSC.10.4.321
Stephen D. Brady, Richard E. Rosenthal, Donovan Young, Interactive Graphical Minimax Location of Multiple Facilities with General Constraints Iie Transactions. ,vol. 15, pp. 242- 254 ,(1983) , 10.1080/05695558308974641