Placement of Near-Optimal Sets of Sampling Locations to Maximize Information Gain in Water Supply Systems

The use of surveillance response systems, or contamination warning systems, to protect potable water systems have been based primarily on water quality sensors distributed throughout a water distribution system. Many studies have investigated the placement of fixed sensor locations for use in the identification, localization, and forecasting of a contamination event. However, confirmatory sampling, such as manual grab sampling or placing temporary sensors, can improve the characterization of a potential ongoing contamination event and improve response actions. This research presents a genetic algorithm (GA) and proposes an updating greedy algorithm (UGA) to determine the near-optimal location of multiple confirmatory sampling locations (CSLs) based on a metric derived from information theory known as expected network entropy, E[NE]. Although GAs perform a global search to simultaneously identify multiple CSLs, these approaches may be computationally inefficient for real-time implementation. The proposed UGA uses an approximation to the E[NE] objective function and a local search to identify CSLs sequentially that is applicable for real-time implementation. Both approaches were tested on a common small network with the GA and UGA algorithms identifying similar CSLs, and both demonstrated the ability of CSLs to improve the characterization of network contamination and forecasts. More importantly, the UGA provided almost identical solutions to the GA, with only slight variations in the selection (for one injection scenario) and ordering of the CSLs, with negligible differences in E[NE], and was solved in seconds, whereas the GA required hours to days.