Pipe Routing through Ant Colony Optimization
Publication: Journal of Infrastructure Systems
Volume 16, Issue 2
Abstract
As the need to better manage scarce water resources and water distribution systems increases, the problem of efficient routing of piping networks is gaining importance within the framework of an overall strategy for improving the networks’ efficiency and resilience to undesired emphoperational changes. The paper presents a methodology for optimizing flow routing in pipe networks by imitating the natural selection processes used by real-life ants in search of the shortest path to a food source. The method, known as ant colony optimization (ACO), is a population-based, artificial multiagent, general-search technique for the solution of combinatorial problems with its analogical roots based on the behavior of real-ant colonies. ACO’s mathematical background is outlined and a suggested possible implementation strategy is described for identifying “shortest paths” in water pipe networks. Such shortest paths could be not only the minimum pipe lengths between nodes of interest, but also the minimum number of valve operations required to keep a flow path active, the minimum number of customers affected during a flow reroute either because of planned (maintenance) or unplanned (water leak) conditions, and the minimum pressure drop along a path during adverse conditions. The ACO methodology should be of interest to both researchers and practitioners since it provides an alternative method to routing optimizations, with a wide range of applications. A case study of a specific urban water distribution network is also described for the proposed ACO virtual multiagent approach.
Get full access to this article
View all available purchase options and get full access to this article.
References
Andreou, S. A., Marks, D. H., and Clark, R. M. (1987). “New methodology for modeling break failure patterns in deteriorating water distribution systems: Applications.” Adv. Water Resour., 10, 2–10.
Aslani, P. (2003). “Hazard rate modeling and risk analysis of water mains.” MS thesis, Polytechnic Univ., Brooklyn, N.Y.
Castillo, L., and Gonzalez, A. (1998). “Distribution network optimization: Finding the most economic solution by using genetic algorithms.” Eur. J. Oper. Res., 108(3), 527–537.
Christodoulou, S. (2005). “Ant colony optimization in construction scheduling.” Proc., ASCE Int. Conf. on Computing in Civil Engineering, ASCE, Reston, Va.
Christodoulou, S., Aslani, P., and Deligianni, A. (2006). “Integrated water distribution network risk assessment and management.” Proc., 10th East Asia-Pacific Conf. on Structural Engineering and Construction (EASEC-10), EASEC, Bangkok, Thailand.
Christodoulou, S., Charalambous, B., and Adamou, A. (2007). “Managing the ‘replace or repair’ dilemma on water leakages in urban water distribution networks.” Proc., European Water Resources Association Conf. on Water Resources Management-New Approaches and Technologies (EWRA), EWRA, Chania, Greece.
Clark, R. M., Stafford, C. L., and Goodrich, J. A. (1982). “Water distribution systems: A spatial and cost evaluation.” J. Water Resour. Plng. and Mgmt. Div., 108(3), 243–256.
Dorigo, M., Maniezzo, V., and Colorni, A. (1996). “Ant system: Optimization by a colony of cooperating agents.” IEEE Trans. Syst., Man, Cybern., Part B: Cybern., 26(1), 29–41.
Dorigo, M., and Stutzle, T. (2002). “The ant colony optimization metaheuristic: Algorithms, applications and advances.” Handbook of metaheuristics, Vol. 57, Kluwer Academic, Norwell, Mass., 251–285.
Goulter, I. C., and Kazemi, A. (1988). “Spatial and temporal groupings of water main pipe breakage in winnipeg.” Can. J. Civ. Eng., 15(1), 91–97.
Jacobs, P., and Goulter, I. C. (1989). “Optimization of redundancy in water distribution networks using graph theoretic principles.” Eng. Optimiz., 15(1), 71–82.
Kettler, A. J., and Goulter, I. C. (1985). “An analysis of pipe breakage in urban water distribution networks.” Can. J. Civ. Eng., 12(2), 286–293.
Kleiner, Y., and Rajani, B. (1999). “Using limited data to assess future needs.” J. Am. Water Works Assoc., 91(7), 47–61.
Maier, H. R., et al. (2003). “Ant colony optimization for design of water systems.” J. Water Resour. Plng. and Mgmt. Div., 129(3), 200–209.
Maniezzo, V., Gambardella, L., and Luigi, F. D. (2004). Ant colony optimization, new optimization techniques in engineering, G. C. Onwubolu and B. V. Babu, eds., Springer, Berlin, 101–117.
O’Day, D. K. (1982). “Organization and analyzing leak and break data for making main replacement decisions.” J. Am. Water Works Assoc., 74(11), 588–594.
Shamir, U., and Howard, C. (1979). “An analytical approach to scheduling pipe replacement.” J. Am. Water Works Assoc., 71(5), 248–258.
U.S. EPA. (2006). “Decision-support tools for predicting the performance of water distribution and wastewater collection systems.” Rep. No. EPA/600/R-02/029, U.S. EPA, Washington, D.C.
Vanrenterghem-Raven, A., Eisenbeis, P., Juran, I., and Christodoulou, S. (2004). “Statistical modeling of the structural degradation of an urban water distribution system: Case study of New York City.” Proc., World Water and Environmental Resources Congress 2003 and Related Symp., ASCE, Reston, Va.
Walski, T. M., and Pelliccia, A. (1982). “Economic analysis of water main breaks.” J. Am. Water Works Assoc., 74(3), 140–147.
Zecchin, A. C., Maier, H. R., Simpson, A. R., Roberts, A., Berrisford, M. J., and Leonard, M. (2003). “Max-min ant system applied to water distribution system optimization.” Proc., Modsim 2003-Int. Congress on Modeling and Simulation, Vol. 2, Modeling and Simulation Society of Australia and New Zealand, Townsville, Australia, 795–800.
Zecchin, A. C., Simpson, A. R., Maier, H. R., Leonard, M., Roberts, A. J., and Berrisford, M. J. (2006). “Application of two ant colony optimization algorithms to water distribution system optimization.” Math. Comput. Modell., 44(5–6), 451–468.
Zecchin, A. C., Simpson, A. R., Maier, H. R., and Nixon, J. B. (2005). “Parametric study for an ant algorithm applied to water distribution system optimization.” IEEE Trans. Evol. Comput., 9(2), 175–191.
Information & Authors
Information
Published In
Journal of Infrastructure Systems
Volume 16 • Issue 2 • June 2010
Pages: 149 - 159
Copyright
© 2010 ASCE.
History
Received: Jan 21, 2008
Accepted: Oct 14, 2009
Published online: May 14, 2010
Published in print: Jun 2010
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.