Graph-Based Genetic Algorithm for Localization of Multiple Existing Leakages in Water Distribution Networks

Abstract

Water utility operators prioritize timely repairs of leakages, an activity that refers to a challenging task by the spatial localization of multiple existing leakages within a water distribution network (WDN). In the literature, genetic algorithms (GAs) are applied to find the best combinations of leakages, typically in combination with a reduced number of candidate leakage nodes to reduce computational effort. To address this limitation, a graph-based GA is proposed in this work by considering the topological relationship between the leakage candidate nodes and sizes for the creation of the offspring. In greater detail, each gene in the graph-based GA consists of a leakage place and leakage size, and two random genes are selected based on the roulette wheel selection for the creation of the offspring. Afterward, possible offspring nodes are selected within the shortest path between these two leakage places or in spatial proximity connected to the shortest path, where the leakage size is set to a random value between the leakage sizes of the two genes. The developed approach was tested on part of a WDN with 100 different leakage scenarios and varying number of leakages, sizes, and locations. As the results showed, the graph-based GA significantly improved leakage localization compared with a classic GA and linear programming solver, with a median distance of 44 m between suspected and actual leakage locations given perfect conditions while also being computationally efficient. However, the achievable performance was strongly affected by measurement errors, model uncertainties, and partially unknown nodal demands and was more accurate for localizing leakage places near exactly measured locations and with larger leakage sizes.