A HEURISTIC ALGORITHM FOR A MINIMAX SENSOR LOCATION PROBLEM ALONG A PIECEWISE LINEAR CURVE

Open Access
Author:
Liu, Qi
Graduate Program:
Industrial Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
None
Committee Members:
  • Tom Michael Cavalier, Thesis Advisor
Keywords:
  • Voronoi diagram
  • piecewise linear curve
  • minimax sensor location problem
  • heuristic algorithm
Abstract:
Facility location problems have many practical applications in the fields of urban planning, retail industry, emergency service, etc. A recent variant of this problem that has received attention in the literature is the sensor location problem. One typical sensor location problem is to place a finite number of sensors to detect an event in a prescribed domain in order to minimize the maximum probability of non-detection. The application of this problem could be the detection of hazardous events, mobile service, military planning, etc. The domain to be detected can be a unit line, a unit square, a convex polygon or even a piecewise linear curve. In this thesis the minimax sensor location problem of monitoring a piecewise linear curve is addressed. An event may occur anywhere along the piecewise linear curve; a finite number of sensors may be positioned there. The objective is to minimize the maximum probability of non-detection. Furthermore, the feasible region of sensor locations can take different forms. Unconstrained and constrained optimization problems are both studied in this thesis. It is shown that this is a difficult non-convex, non-linear, continuous optimization problem even in the case of two sensors. A heuristic algorithm utilizing the properties of Voronoi diagrams is developed in this thesis. In particular, the direction finding method and the manner followed to obtain the step-length parameters are fine-tuned. A procedure for attaining feasible solutions is also developed for constrained optimization problems. Through computational testing, it is demonstrated that the algorithm can generate high-quality solutions. Computational experience is provided.