Sensor Placement in Water Networks: A Stochastic Programming Approach
Publication: Journal of Water Resources Planning and Management
Volume 132, Issue 3
Abstract
Placement of sensors in water distribution networks helps timely detection of contamination and reduces risk to the population. Identifying the optimal locations of these sensors is important from an economic perspective and has been previously attempted using the theory of optimization. This work extends that formulation by considering uncertainty in the network and describes a stochastic programming method that is capable of determining the optimal sensor location while accounting for demand uncertainties. The problem is formulated as a two stage stochastic programming problem with recourse. The solution to the problem is achieved by using a newly proposed algorithm aimed at efficiently solving stochastic nonlinear programming problems. This makes the problem solution computationally tractable as compared to the traditional stochastic programming methods. The proposed formulation and solution methodology are tested on an example network to perform a comparative study with other formulations. The results show the importance of uncertainty consideration in decision making and highlight the advantages of the proposed stochastic programming approach.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgment
This work is funded by the National Science Foundation under Grant No. NSFCTS-0406154.
References
Berry, J., Fleischer, L., Hart, W., Phillips, C., and Watson, J. (2005). “Sensor placement in municipal water networks.” J. Water Resour. Plan. Manage., 131(3), 237–243.
Birge, J., and Louveaux, F. (1997). Introduction to stochastic programming, Springer Series in Operations Research, Springer, New York.
Dantzig, G., and Glynn, P. (1990). “Parallel processors for planning under uncertainty.” Ann. Operat. Res., 22, 1–21.
Dantzig, G., and Infanger, G. (1992). Computational and applied mathematics I, Elsevier Science, B.V., North Holland, Amsterdam, The Netherlands.
Diwekar, U. (2003). Introduction to applied optimization, Kluwer Academic, Dordrecht, The Netherlands.
Eiger, G., Shamir, U., and Ben-Tal, A. (1994). “Optimal design of water distribution networks.” Water Resour. Res., 30(9), 2637–2646.
Hesterberg, T. (1995). “Weighted average importance sampling and defensive mixture distribution.” Technometrics, 37, 185–194.
Higle, J., and Sen, S. (1991). “Stochastic decomposition: An algorithm for two stage linear programs with recourse.” Ann. Operat. Res., 16, 650–669.
Infanger, G. (1992). “Monte Carlo (importance) sampling within a benders decomposition algorithm for stochastic linear programs.” Ann. Operat. Res., 39, 69–95.
Kalagnanam, J., and Diwekar, U. (1997). “An efficient sampling technique for off-line quality control.” Technometrics, 39(3), 308–319.
Kessler, A., Ostfeld, A., and Sinai, G. (1998). “Detecting accidental contaminations in municipal water networks.” J. Water Resour. Plan. Manage., 124(4), 192–198.
Kumar, A., Kansal, M., and Arora, G. (1999). “Discussion of ‘Detecting accidental contaminations in municipal water networks.’” J. Water Resour. Plan. Manage., 125(5), 308–309.
Rossman, L. (1993). EPANET users manual, Risk Reduction Engineering Lab, Environmental Protection Agency, Cincinnati.
Sahin, K., and Diwekar, U. (2004). “Better optimization of nonlinear uncertain systems (BONUS): A new algorithm for stochastic programming using reweighting through kernel density estimation.” Ann. Operat. Res., 132, 47–68.
Savic, D., and Walters, G. (1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plan. Manage., 123(2), 67–77.
Silvermann, B. (1986). Density estimation for statistics and data analysis, Chapman and Hall, Boca Raton, Fla.
Tryby, M., Boccelli, D., Uber, J., and Rossman, L. (2002). “Facility location model for booster disinfection of water supply networks.” J. Water Resour. Plan. Manage., 128, 322–332.
Van Slyke, R., and Wets, R.-B. (1969). “L-shaped linear programs with application to optimal control and stochastic programming.” SIAM J. Appl. Math., 17, 638–663.
Varma, K., Narasimhan, S., and Bhallamudi, S. (1997). “Optimal design of water distribution systems using an NLP method.” J. Environ. Eng., 123(4), 381–388.
Wang, R., Diwekar, U., and Grégorie Padró, E. (2004). “Efficient sampling techniques for uncertainties and risk analysis.” Environ. Prog., 23(2), 141–157.
Xu, C., and Goulter, I. (1999). “Reliability-based optimal design of water distribution networks.” J. Water Resour. Plan. Manage., 125(6), 352–362.
Information & Authors
Information
Published In
Copyright
© 2006 ASCE.
History
Received: Aug 30, 2004
Accepted: Nov 14, 2005
Published online: May 1, 2006
Published in print: May 2006
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.