The Applications of Graph Algorithms to Modeling of Integrated Urban Water Management System

• Autorzy: Łazuka Ewa , Futa Anna , Jastrzębska Magdalena , Łagód Grzegorz , Szeląg Bartosz , Fatone Francesco

Identyfikatory

DOI

10.12913/22998624/155036

• Języki publikacji: EN

Abstrakty

EN

The application of methods using graphs to model a variety of engineering issues has been known for several decades, but the application of graph algorithms to model the urban water management issues is a completely new approach. The article reviews the scientific literature on integrated urban water management systems in terms of the use of graph theory algorithms in this topic. Such a review has not been done before and constitutes a completely novel study. Some of the algorithms presented are directly derived from graph theory, while others were developed from other sciences, including environmental engineering or genetics, to solve specific engineering problems. The paper presents a general scheme and a brief description of the most important components of an integrated urban water management system. The necessary concepts of graphs were defined, the origin and the principle of graph algorithms used in modeling water management issues (Loop-By-Loop Cutting Algorithm, Hanging Gardens Algorithm, Tree Growth Algorithm, Dijkstra’s Algorithm, Genetic Algorithm, and Bayesian Networks Algorithm) were described. Their use in modeling the issues in stormwater, sanitary sewage and water distribution system was described. A complete list of scientific literature in this field was provided.

Słowa kluczowe

EN

graph modeling; graph algorithms; integrated analysis; network modeling; urban water

• Wydawca: Lublin University of Technology ; Polish Society of Ecological Engineering (PTIE), Branch of PTIE in Lublin
• Czasopismo: Advances in Science and Technology. Research Journal
• Rocznik: 2022
• Tom: Vol. 16, no 5
• Strony: 277--289
• Opis fizyczny: Bibliogr. 63 poz., fig., tab

Twórcy

autor

Łazuka Ewa

• Department of Applied Mathematics, Faculty of Technology Fundamentals, Lublin University of Technology, Nadbystrzycka 38, 20-618 Lublin, Poland

• https://orcid.org/0000-0002-2415-7454

autor

Futa Anna

• Department of Applied Mathematics, Faculty of Technology Fundamentals, Lublin University of Technology, Nadbystrzycka 38, 20-618 Lublin, Poland

• https://orcid.org/0000-0001-6144-1799

autor

Jastrzębska Magdalena

• Department of Applied Mathematics, Faculty of Technology Fundamentals, Lublin University of Technology, Nadbystrzycka 38, 20-618 Lublin, Poland

• https://orcid.org/0000-0001-8906-6388

autor

Łagód Grzegorz

• Department of Water Supply and Wastewater Disposal, Faculty of Environmental Engineering, Lublin University of Technology, Nadbystrzycka 40B, 20-618 Lublin, Poland

• https://orcid.org/0000-0002-0621-7222

autor

Szeląg Bartosz

• Department of Geotechnics and Water Engineering, Faculty of Environmental, Geomatic and Energy Engineering, Kielce University of Technology, Aleja Tysiąclecia Państwa Polskiego 7, 25-314 Kielce, Poland

• https://orcid.org/0000-0002-0559-5475

autor

Fatone Francesco

• Department of Science and Engineering of Materials, Environment and Urban Planning-SIMAU, Polytechnic University of Marche Ancona, Via Brecce Bianche 12, 60121 Ancona, Italy

• https://orcid.org/0000-0003-0745-282X

Bibliografia

• 1. Pfister A., Stein A. Schlegel S., Teichgraber B. An integrated approach for improving the wastewater discharge and treatment system. Water Science and Technology 1998; 37(1): 341-346.
• 2. Ashley R.M., Hvitved-Jacobsen T., Bertrand-Krajewski J.–L. Quo vadis sewer process modeling?. Water Science and Technology 1999; 39(9): 9-22.
• 3. Hvitved-Jacobsen T. Sewer Processes: Microbial and Chemical Process Engineering of Sewer Networks. CRC PRESS, 2002.
• 4. Dąbrowski W. The influence of sewage networks on the environment (in Polish). Wydawnictwo Politechniki Krakowskiej, 2004.
• 5. Łagód G., Widomski M., Suchorab Z., Wróbel K. Modeling of transport and biodegradation of pollutants in sewer systems (in Polish). Monografie Komitetu Inżynierii Środowiska PAN, 2010.
• 6. Szeląg B., Drewnowski J., Łagód G., Majerek D., Dacewicz E., Fatone F. Soft Sensor Application in Identification of the Activated Sludge Bulking Considering the Technological and Economical Aspects of Smart Systems Functioning. Sensors 2020; 20(7), 1941-1965.
• 7. Wojciechowski J., Pieńkosz K. Graphs and networks (in Polish). Wydawnictwo Naukowe PWN, 2013.
• 8. Butler D., Davies J. W. Urban Drainage. Spon Press, 2004.
• 9. Reyes-Silva J. D., Zischg J., Klinkhamer C., Rao P.
• S. C., Sitzenfrei R., Krebs P. Centrality and shortest path length measures for the functional analysis of urban drainage networks, Applied Network Science 2020; 5(1): 1-14.
• 10. Deuerlein J., Piller O., Montalvoc I. Improved Real-Time Monitoring and Control of Water Supply Networks by Use of Graph Decomposition. Procedia Engineering 2014; 89: 1276-1281.
• 11. Ulusoy AJ. , Stoianov I., Chazerain A. Hydraulically informed graph theoretic measure of link criticality for the resilience analysis of water distribution networks. Applied Network Science 2018; 3(31): 1-22.
• 12. Di Nardo A., Giudicianni C., Greco R., Herrera M., Santonastaso G. F. Applications of Graph Spectral Techniques to Water Distribution Network Management. Water 2018; 10(1): 45-60.
• 13. Giudicianni C., Di Nardo A., Di Natale M., Greco R., Santonastaso G. F., Scala A., Topological Taxonomy of Water Distribution Networks. Water 2018; 10(4), 444-462.
• 14. Ciaponi C., Creaco E., Di Nardo A., Di Natale M., Giudicianni C., Musmarra D., Santonastaso G. F. Optimal Sensor Placement in a Partitioned Water Distribution Network for the Water Protection from Contamination. Proceedings 2018; 2(11), 670-676.
• 15. Jacobs P., Goulter I. C. Optimization of redundancy in water distribution networks using graph theoretic principles. Engineering Optimization 2007; 15(1); 71-82.
• 16. Herrera M., Abraham E., Stoianov I. A GraphTheoretic Framework for Assessing the Resilience of Sectorised Water Distribution Networks. Water Resour Manage 2016; 30; 1685-1699.
• 17. Deuerlein J., Wolters A., Roetsch D., Simpson A. R. Reliability Analysis of Water Distribution Systems Using Graph Decomposition. In: World Environmental and Water Resources Congress 2009, Kansas City, Missouri, USA 2009, 272-282.
• 18. Hajebi S., Roshani E., Cardozo N., Barrett S., Clarke A., Clarke S. Water distribution network sectorisation using graph theory and many-objective optimization. Journal of Hydroinformatics 2016; 18(1): 77-95.
• 19. Pelda J., Holler S. Methodology to evaluate and map the potential of waste heat from sewage water by using internationally available open data. Energy Procedia 2018; 149: 555-564.
• 20. Berko A., Zhuk V., Sereda I. Modeling of sewer networks by means of directed graphs, Environmental Problems 2017; 2(2):97-100.
• 21. Turan M. E., Bacak-Turan G., Cetin T., Aslan E. Feasible Sanitary Sewer Network Generation Using Graph Theory. Hindawi Advances in Civil Engineering 2019; 2019 : 1-15.
• 22. Sarvari H., Chan D. W.M., Banaitiene N., Md Noor N., Beer M. Barriers to development of private sector investment in water and sewage industry. Built Environment Project and Asset Management 2021; 11(1): 52-70.
• 23. Hesarkazzazi S., Hajibabaei M., Sitzenfrei R. Functional Properties of Stormwater Systems Based on Graph Theory. In: 17th International Computing & Control for the Water Industry Conference, Exeter, United Kingdom 2019.
• 24. Notaro V., Fontanazza C.M., La Loggia G., Freni G. Flood frequency analysis for an urban watershed: comparison between several statistical methodologies simulating synthetic rainfall events. J. Flood Risk Manag. 2018; 11: 559-574.
• 25. Petit-Boix A., Sevigné-Itoiz E., Rojas-Gutierrez L.A., Barbassa A.P., Josa A., Rieradevall J., Gabarrell X. Floods and consequential life cycle assessment: Integrating flood damage into the environmental assessment of stormwater Best Management Practices. J. Clean. Prod. 2017; 162: 601-608.
• 26. Szeląg B., Kiczko A., Łagód G., De Paola F. Relationship between rainfall duration and sewer system performance measures within the context of uncertainty. Water Res Manage. 2021; 35: 5073-5087.
• 27. Szeląg B., Suligowski R., De Paola F., Siwicki P., Majerek D., Łagód G. Influence of urban catchment characteristics and rainfall origins on the phenomenon of stormwater flooding: Case study. Environ. Model. Softw. 2022; 150: 105335-105357.
• 28. Wilson R. J. Introduction to Graph Theory. Longman, 1998.
• 29. West D. B. Introduction to Graph Theory. Rashtriya Printers, 2002.
• 30. Haghighi A. Loop-by-Loop Cutting Algorithm to Generate Layouts for Urban Drainage Systems. American Society of Civil Engineers 2013; 139: 693-703.
• 31. Bakhshipour A. E., Bakhshizadeh M., Dittmer U., Haghighi A., Nowak W., Hanging Gardens Algorithm to Generate Decentralized Layouts for the Optimization of Urban Drainage Systems. Journal of Water Resources Planning and Management 2019; 145(9): 1-12.
• 32. Bakhshipour A. E., Hespen J., Haghighi A., Dittmer U., Nowak W. Integrating Structural Resilience in the Design of Urban Drainage Networks in Flat Areas Using a Simplified Multi-Objective Optimization Framework. Water 2021; 13: 269-290.
• 33. Bakhshipour A. E., Dittmer U., Haghighi A., Nowak W. Hybrid green-blue-gray decentralized urban drainage systems design, a simulation-optimization framework. Journal of Environmental Management 2019; 249: 1-13.
• 34. Cheraghalipour A., Hajiaghaei-Keshteli M. Tree Growth Algorithm (TGA): An Effective Metaheuristic Algorithm Inspired by Trees’ Behavior. In: 13th International Conference on Industrial Engineering, Babol, Iran 2017, 1-10.
• 35. Cheraghalipour A., Hajiaghaei-Keshteli M., Paydar M. M. Tree Growth Algorithm (TGA): A novel approach for solving optimization problems. Engineering Applications of Artificial Intelligence 2018; 72: 393–414.
• 36. Dijkstra E. W. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1959; 1: 269-271.
• 37. Li-sang Liu, Jia-feng Lin, Jin-xin Yao, Dong-wei He, Ji-shi Zheng, Jing Huang, Peng Shi. Path planning for smart car based on dijkstra algorithm and dynamic window approach. Wireless Communications and Mobile Computing 2021; 2021: 1-12.
• 38. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. The MIT Press, 2009.
• 39. Holland J. H. Adaptation in natural and artificial systems: An introductory analysis
• 40. with applications to biology, control, and artificial intelligence. The MIT Press, 1975.
• 41. De Jong, Kenneth A. Analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis. University of Michigan, 1975.
• 42. Holland J. H. Genetic Algorithms and Adaptation, In: Selfridge, O.G., Rissland, E.L., Arbib, M.A. (eds) Adaptive Control of Ill-Defined Systems. NATO Conference Series, Springer, Boston, 1984; 16: 317-333.
• 43. Albadr M. A., Tiun S., Ayob M., AL-Dhief F. Genetic Algorithm Based on Natural Selection Theory for Optimization Problems. Symmetry 2020; 12(11): 1758-1788.
• 44. Höschel, K. Lakshminarayanan V. Genetic algorithms for lens design. Journal of Optics 2018; 48: 134-144.
• 45. Pearl J. Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning. In: Proceedings of the 7th Conference of the Cognitive Science Society, Irvine, California 1985 , 329-334.
• 46. Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988.
• 47. Heckerman D. , A Tutorial on Learning Bayesian Networks. In: Holmes D. E., Jain L. C. Innovations in Bayesian Networks Theory and Applications. Springer 1995; 156: 33-82.
• 48. Wiegerinck W., Kappen B., Burgers W. Bayesian networks for expert systems: theory and practical applications. In: Babuska R., Groen F. C. A. Interactive collaborative information systems. Springer 2010; 281: 547-578.
• 49. Jensen F. V., Nielsen T.D. Bayesian networks and decision graphs. Springer, 2007.
• 50. Tang K., Parsons D. J., Jude S. Comparison of automatic and guided learning for Bayesian networks to analyse pipe failures in the water distribution system. Reliability Engineering and System Safety 2019; 186: 24-36.
• 51. Yang Xin-She. Introduction to Algorithms for Data Mining and Machine Learning. Academic Press, 2019.
• 52. Savic A. D., Waiters G. A., Atkinson R.M., Smith M. R. Genetic Algorithm Optimization of Large Water Distribution System Expansion, Measurement and Control 1999; 32(4): 104-109.
• 53. Afshar M.H. Application of a Genetic Algorithm to Storm Sewer Network Optimization. Scientia Iranica 2006; 13(3): 234-244.
• 54. Meijer D., M. van Bijnen, Langeveld J., Korving H., Post J., Clemens F. Identifying Critical Elements in Sewer Networks Using Graph-Theory. Water 2018; 10(2), 136-164.
• 55. Huang J., James W., James W. R. C. A Lifecycle Cost-based Design Optimization Model for Stormwater Management Systems. Journal of Water Management Modeling 2005.
• 56. Haghighi A., Bakhshipour A. E. Reliability-based layout design of sewage collection systems in flat areas. Urban Water Journal 2015; 790-802.
• 57. Hassan W. H., Attea Z. H., Mohammed S. S. Optimum layout design of sewer networks by hybrid genetic algorithm. Journal of Applied Water Engineering and Research 2020; 8(2): 1-17.
• 58. Moeini R., Afshar M. H. Constrained Ant Colony Optimisation Algorithm for the layout and size optimisation of sanitary sewer networks. Urban Water Journal 2013; 10(3): 1-32.
• 59. Liu K. F.R., Chen C.W., Shen Y.S. Using Bayesian belief networks to support health risk assessment for sewer workers. International Journal of Environmental Science and Technology 2013; 10: 385-394.
• 60. Kozelj D., Deuerlein J., Klasinc R., Steinman F. Application of Graph Theory in Calibration of Water Supply System Models. In: HIC 2009, the 9th International Conference on Hydroinformatics, Chile 2009.
• 61. Bi W., Dandy G.C., Maier H.R. Improved genetic algorithm optimization of water distribution system design by incorporating domain knowledge. Environmental Modelling & Software 2015; 69: 370-381.
• 62. Di Nardo A., Di Natale M. A heuristic design support methodology based on graph theory for district metering of water supply networks. Engineering Optimization 2011; 43(2): 193-211.
• 63. Gao J., Yao F., Xu Y., Sun G., Zheng C., Qi S., Cui F. PMA Partition Method of Water Distribution Network Combined with Graph Theory. Procedia Engineering 2017; 186: 278-285.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).