A Facility Location Approach to Sensor Placement Optimization

The general sensor placement problem (SPP) for contaminant warning system (CWS) design involves placement of a limited number of sensors such that the expected impact of an attack is minimized. We cast the SPP in terms of the well-known p-median problem from discrete location theory. The p-median formulation assumes a fixed number of attack scenarios, each specifying a probability of occurrence, a set of injection sites, injection strengths, and injection durations. The impact of each potential attack is determined via contaminant transport simulation. Specifically, EPANET is used to generate a time-series of contaminant concentration at each network junction for each attack. For each combination of attack and network junction, the resulting time-series are then used to compute the network-wide impact of the attack assuming detection via a hypothetical contaminant sensor placed at the network junction. In conjunction with the attack probabilities, the resulting "impact coefficients" completely specify the input to our p-median formulation of the SPP. We solve the p-median SPP using domain-specific heuristics based on a combination of GRASP and local search. Extensive computational tests indicate that the heuristics consistently locate globally optimal solutions, as verified via solution of the corresponding mixed-integer program (MIP) using commercially available solvers. Further, the heuristic executes in seconds to minutes for networks ranging from 100 to 10,000 junctions, respectively, subject to large numbers (on the order of the number of network junctions) of hypothetical attack scenarios. By isolating objective-specific information to the impact coefficients, our approach seamlessly allows for optimization of disparate performance objectives, e.g., detection likelihood and population exposed. The use of general-purpose contaminant transport simulators allows us to handle arbitrarily complex attack scenarios, e.g., multiple simultaneous injection sites with different contaminants at variable injection strengths and durations. Certain response strategies, such as delays incurred due to manual verification of sensor hits, can be incorporated via appropriate modification of the impact coefficients. Through the use of side constraints,we are able to generate solutions to then p-median formulation of the SPP that simultaneously yield high-quality performance with respect to a range of performance objectives. Finally, in contrast to competing approaches to solving the SPP, we are able to provide provable bounds on the quality of solutions generated by our heuristic via formulation and solution of the SPP as a p-median MIP. This paper was presented at the 8th Annual Water Distribution Systems Analysis Symposium which was held with the generous support of Awwa Research Foundation (AwwaRF).