Abstract:
This paper investigates the issue of finding the best sensor locations in a drinking water distribution network for detecting harmful substances. The problem is formulated in a multi-objective optimization framework with five performance measures: time of detection, population affected prior to detection, demand of contaminated water, detection likelihood and demand coverage. In practical application, due to the large size of water distribution networks, the space of possible solutions expands dramatically, making it difficult or impossible to determine the optimal solutions. We propose the β€_x009c_Iterative Deepening of Pareto Solutionsβ€_x009d_ search algorithm, for locating β€_x009c_good enoughβ€_x009d_ solutions. The algorithm solves the problem by iteratively choosing the best non-dominant solutions, and expanding them by increasing the depth of the search tree until all the sensors have been used. Simulation experiments were performed on two water distribution networks, following the formulation defined in the β€_x009c_Battle of the Water Sensor Networksβ€_x009d_ design challenge (Ostfeld et al. 2005). Four contamination scenarios are considered and from the sets of possible solutions, the most appropriate designs are proposed.
