Sensor Placement in Municipal Water Networks with Temporal Integer Programming Models
Publication: Journal of Water Resources Planning and Management
Volume 132, Issue 4
Abstract
We present a mixed-integer programming (MIP) formulation for sensor placement optimization in municipal water distribution systems that includes the temporal characteristics of contamination events and their impacts. Typical network water quality simulations track contaminant concentration and movement over time, computing contaminant concentration time series for each junction. Given this information, we can compute the impact of a contamination event over time and determine affected locations. This process quantifies the benefits of sensing contamination at different junctions in the network. Ours is the first MIP model to base sensor placement decisions on such data, compromising over many individual contamination events. The MIP formulation is mathematically equivalent to the well-known -median facility location problem. We can exploit this structure to solve the MIP exactly or to approximately solve the problem with provable quality for large-scale problems.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers thank Phil Meyers at Pacific Northwest National Laboratory for noting that DSP is equivalent to the -median facility location problem. Sandia is a multipurpose laboratory operated by Sandia Corporation, a Lockheed–Martin Company, for the U.S. Department of Energy under Contract No. DOEDE-AC04-94AL85000.
References
Berry, J., Fleischer, L., Hart, W. E., Phillips, C. A., and Watson, J. P. (2005). “Sensor placement in municipal water networks.” J. Water Resour. Plan. Manage., 131(3), 237–243.
Berry, J., Hart, W. E., Phillips, C. A., and Uber, J. (2004). “A general integer-programming-based framework for sensor placement in municipal water networks.” Proc., World Water and Environment Resources Conf., ACSE, Reston, Va.
Berry, J., Fleischer, L., Hart, W. E., and Phillips, C. A. (2003). “Sensor placement in municipal water networks.” Bizier, P. and DeBarry, P., eds., Proc., World Water and Environmental Resources Congress, ASCE, Reston, Va.
Carr, R. et al. (2006). “Robust optimization of contaminant sensor placement for community water systems.” Math. Program., in press.
Drage, B. E., Upton, J. E., and Purvis, M. (1998). “On-line monitoring of micropollutants in the River Trent (U.K.) with respect to drinking water abstraction.” Water Sci. Technol., 38(11), 123–130.
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. L., and Arora, G. (1999). “Discussion of ‘Detecting accidental contaminations in municipal water networks’.” J. Water Resour. Plan. Manage., 125(5), 308–309.
Lee, B. H., and Deininger, R. A. (1992). “Optimal locations of monitoring stations in water distribution system.” J. Environ. Eng., 118(1), 4–16.
Lee, B. H., Deininger, R. A., and Clark, R. M. (1991). “Locating monitoring stations in water distribution systems.” J. Am. Water Works Assoc., 60–66.
Mirchandani, P., and Francis, R., eds., (1990). Discrete location theory, Wiley, New York.
Ostfeld, A., and Salomons, E. (2004). “Optimal layout of early warning detection stations for water distribution systems security.” J. Water Resour. Plan. Manage., 130(5), 377–385.
Ostfeld, A., and Kessler, A. (2001). “Protecting urban water distribution systems against accidental hazards intrusions.” Proc., IWA Second Conf., IWA (CD-ROM).
Propato, M., Piller, O., and Uber, J. (2005). “A sensor location model to detect contaminations in water distribution networks.” Proc., World Water and Environmental Resources Congress. ASCE, Reston, Va.
Resende, M., and Werneck, R. (2004). “A hybrid heuristic for the -median problem.” J. Heuristics, 10(1), 59–88.
ReVelle, C., and Swain, R. (1970). “Central facilities location.” Geogr. Anal., 2, 30–42.
Rossman, L. A. (1999). “The EPANET programmer’s toolkit for analysis of water distribution system.” Proc., Annual Water Resources Planning and Management Conf., Available at http://www.epanet.gov/ORD/NRMRL/wswrd/epanet.html .
Schmitz, P., Krebs, F., and Irmer, U. (1994). “Development, testing, and implementation of automated biotests for the monitoring of the River Rhine, demonstrated by bacteria and algae tests.” Water Sci. Technol., 29, 215–221.
Stoks, P. G. (1994). “Water quality control in the production of drinking water from river water.” M. Adriaanse, J. van der Kraats, P. Stoks, and R. Ward, eds., Proc., Monitoring Tailor-made. RIZA, Lelystad, The Netherlands.
Walski, T., et al. (1987). “Battle of network models: Epilogue.” J. Water Resour. Plan. Manage., 113(2), 191–203.
Watson, J. P., Greenberg, H. J., and Hart, W. E. (2004). “A multiple-objective analysis of sensor placement optimization in water networks.” Proc., World Water and Environment Resources Conf., ASCE, Reston, Va.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 132 • Issue 4 • July 2006
Pages: 218 - 224
Copyright
© 2006 ASCE.
History
Received: Aug 23, 2005
Accepted: Dec 30, 2005
Published online: Jul 1, 2006
Published in print: Jul 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.