Novel Method for Segment Identification in Water Distribution Network through Node-Based Adjacency Matrix

A water distribution network (WDN) consists of interconnected pipes, valves, and other auxiliary facilities. Among the elements, valves are used for various purposes. The control valve is installed to block the flow of water when an inappropriate event, such as leaks, breakage, or water quality problems, occurs in WDNs. Control valves, mainly the gate valve expressed as a type of valve, are fully opened at normal conditions and closed only when necessary. Ideally, control valves should be installed at both ends of all pipes to ensure that the WDN ends with only one element loss. Control valves installed at both ends of the pipe make it possible to minimize the range of impact of an inappropriate event.

However, in practice, installing control valves at both ends of all pipes is challenging owing to financial limitations. Thus, control valves are installed depending on the WDN construction budget or according to the appropriate spacing. Standards that present design criteria for WDN, such as those of the American Water Works Association (AWWA) (AWWA 1986) and the Korean Ministry of the Environment (MOE) (MOE 2021), recommend installing control valves at intervals of 150 to 200 m, exceptional special cases. In addition, rules centered on junctions (nodes), such as the $N$ and $N-1$ valving rules, regularize the control valve installation. The $N$ valving rule involves placing the same number ($N$) of valves as the number of nodes, whereas the $N-1$ valving rule involves placing one valve less than the number of nodes (AWWA 1986).

Because the control valves are not installed at both ends of all pipes in WDN, leakage or breakage of pipes not only simply causes the disconnection of pipes from the WDN but also causes the disconnection of nodes according to the $N$ or $N-1$ valving rules. Herein, the concept of a segment appears. A segment represents minimum intended isolation, an area intentionally isolated by control valves. A segment helps identify the number of nodes without water supply and locations due to the disconnection of pipes (Walski 1993, 2020). Fig. 1 shows the conceptual diagram of a segment.

By applying and extending the concept of segment, the WDN manager can recognize the unavailable supply area and devise countermeasures in inappropriate events. In previous studies, segments have been used in various studies to determine the scope of potential water-supply cutoff and analyze the reliability of the WDN in situations associated with breakage, leakage, or maintenance of water pipes (Choi and Koo 2015; Diao et al. 2016; Liu and Kang 2021). Furthermore, closing control valves to make segments to restore failed or broken water pipes may create areas without water supply. Areas without water supply unintentionally created in forming segments are defined as unintentionally isolated areas (Jun and Loganathan 2007). Unintended isolation has also been used in the studies mentioned previously because it has always been connected with the concept of a segment.

With the concept of a segment, various events occurring in the real system can be simulated more realistically. For example, suppose managers identify the segment in advance. In that case, they can decide exactly which valves to close when a water supply must be cut off to repair a leak or when a contaminant enters the network and needs to be stopped from spreading. However, to identify the segment in advance and simulate the events as realistically as possible, there should be rules for the computer to recognize how pipes or valves are connected to the WDN. In particular, this rule should be developed in advance to build a digital-twin system based on near-real-time simulation. Therefore, various methodologies have been developed for identifying segments. Because the WDN consists of vertices or nodes and edges or lines, it can be regarded as a graph. Accordingly, graph theory was used in previous studies determining the segments separated by the control valves installed in the WDN. Graph theory allows a structure defined by nodes and pipes to be expressed as a mathematical matrix or in diagrammatic form for achieving the desired calculation results.

Jun and Loganathan (2007) proposed a methodology to determine segments and unintended isolation. Three incidence matrices between a node and a pipe were used for identifying segments. After a segment was determined, the matrix between the segment and the valve was constructed. By considering the connection of the segment with the water source in the segment–valve matrix, the unintended isolation was identified. The proposed methodology is characterized by requiring input data-file conversion of a hydraulic analysis program such as EPANET to identify the locations of the control valves, in addition to the separate depiction of the node–pipe incidence matrix, node–node adjacency matrix, segment–valve matrix, and the alternate execution of the row-search and column-search recursive functions. Giustolisi and Savic (2010), Creaco et al. (2010), and Alvisi et al. (2011) proposed a methodology to identify segments according to the connection matrix for nodes, water sources, and water pipes. These previous methodologies have the advantages of identifying segments and checking whether water is supplied; however, they have the limitation that hypothetical water sources should be simulated repeatedly to determine the unintended isolation.

Gao (2014) proposed a methodology to identify segments through the node and the adjacency matrix for the node by installing additional control valves paired with the placed control valves. The methodology uses Warshall’s algorithm to obtain faster results and requires the separation of the reconstruction of the matrix between segments to determine the unintended isolation. Mahmoud et al. (2017) proposed a revised segment determination methodology considering the data storage format of EPANET. The incidence matrix between the nodes and pipes and the adjacency matrix between the pipes were used to identify the segments and unintended isolation. Liu and Kang (2021), Huang et al. (2020), and Abdel-Mottaleb and Walski (2021) separated segments using a segment–valve graph. This methodology included partitioning the pipes into shorter pipes considering the valves on the pipes, which has the advantage of clearly defining the locations of the control valves. Hernandez and Ormsbee (2021) presented a methodology using the incidence matrix for nodes and pipes and the adjacency matrix between segments to determine the segments and unintended isolation. Jeong et al. (2021) proposed a methodology to solve the limitations of the unintended isolation identification algorithm proposed by Jun and Loganathan (2007). In particular, the unintended isolation can be interpreted in a distorted way when a segment consists of a pipe only.

An adjacency matrix shows the relationships between nodes in a graph with nodes and pipes. In contrast, an incidence matrix indicates the relationships between the nodes and pipes. If both the adjacent matrix and the incidence matrix are used to identify a segment, it is hard to discern the connection status of a specific node and pipe. This is because comparing and repeatedly checking the two matrices is necessary. Therefore, the analysis efficiency can be increased by using only one of the adjacency matrix or the incidence matrix to determine the connection status of nodes and pipes. In addition, in most commercial hydraulic analysis programs for WDNs, such as EPANET, the role of a control valve is simulated by selecting Open or Close in the properties of the water pipes. Here, a throttle control valve is often used to depict control valves. This method assumes that the control valves are at the center of the water pipes.

However, in a real WDN, the control valves are often adjacent to a node (either a start or end node), and in some cases, the control valves are placed at both ends of the pipes. Because the hydraulic analysis program cannot accurately express the position of the valve, previous studies have complicatedly modeled this situation, e.g., creating new connections by partitioning existing pipes and adding a node and pipe. Because most hydraulic analysis programs consider a valve as a pipe, the valve is also expressed with a start node and an end node. Therefore, it is necessary to use the data input/output form similar to that of the hydraulic analysis program to obtain results linked with hydraulic analysis.

The previously proposed methodologies for identifying segments and unintended isolation in WDNs have strengths and weaknesses. Based on these previous approaches, this study strives to develop a methodology for conveniently determining segments and unintended isolation without comparing many matrices. The proposed methodology only uses the node–node adjacency matrix and row-first search without employing node–pipe incidence matrices or other matrices, e.g., segment–valve or segment–segment. Furthermore, a new rule is applied considering the linkage with the hydraulic analysis program to identify the control valve locations.

This paper explains and verifies the proposed methodology using a simple WDN. Next, this paper analyzes the developed methodology by applying it to large-scale WDNs and by comparing it with the method used in previous studies. Through analysis, the strengths of the developed methodology are explained.

To identify segments and unintended isolation, the adjacent matrix $\mathbf{K}$, describing the components of the WDN, is constructed. Moreover, the matrices $\mathbf{P}$ and $\mathbf{V}$ are used as auxiliaries to explain the configuration of $\mathbf{K}$. In what follows, the subscript $I$ in the $\mathbf{P}$ and $\mathbf{V}$ matrices denotes a matrix indicating the name of each pipe and valve, and the subscript $O$ denotes a matrix describing this with a numerical expression.

To check whether the developed methodology can be applied to actual networks and, at the same time, how much computational cost was required depending on the size of the pipe network, the developed methodology was applied to two actual large-scale WDNs in South Korea. Table 2 describes the characteristics of the WDNs for the two case studies.

The analyzed WDN Y supplies an average of $\mathrm{9,200}{\mathrm{m}}^3$ of tap water per day to approximately 22,000 people. The number of WDN transmission, distribution, and service pipes is 8,727 with 9,202 nodes, including 1 purification plant, 6 water tanks, 7 pump stations, and 460 valves. In addition, WDN K is a system that supplies an average of $\mathrm{68,800}{\mathrm{m}}^3$ of tap water per day to approximately 240,000 people. WDN K contains 58,452 pipes and 61,055 nodes, including 2 purification plants, 26 water tanks, 8 pump stations, and 2,454 valves.

The manual identification of segments for large-scale WDNs is inefficient. Therefore, in this study, the proposed methodology was implemented using C++ code supported by Microsoft Visual Studio 2019. The model was developed using the EPANET 2.2 toolkit to link the model with the hydraulic analysis of the WDN in the future. In particular, the EPANET .inp file was used as input data. Moreover, when the position of the valve was expressed on the network diagram, the data could be used automatically. In contrast, when the position of the valve was not expressed in the network diagram, a .csv file containing the start and end nodes could be used separately.

The analysis time includes all processes from inputting the EPANET .inp file to outputting the .csv format output file. On the other hand, the unintentional isolation zone depends on which pipe is disconnected by segments. Therefore, the analysis time was divided into the case of specifying one pipe and the case of performing analysis on all pipes. The creation of unintentional isolation by segment formation causes the shape of the original network to be changed. In this case, it is necessary to check the situation in which the water may not be normally supplied due to the decrease in water pressure. Therefore, after confirming unintentional isolations, pressure driven hydraulic analysis was performed using the pipe network diagram with the amount of water demand entered, and the analysis time included the process of confirming areas where the water supply was impossible.

Table 3 presents the results of segment identification for the two case studies. The code was executed in an AMD Ryzen 7 CPU with 3.20 GHz and 32 GB RAM running in Windows. This study analyzed the same WDNs for comparison using the methodology proposed by Jun and Loganathan (2007), which was developed first among automated algorithms to identify segments and was used in various studies. The results of identifying the segments using the model developed in this study were the same as that of the model proposed by Jun and Loganathan (2007).

Through these results, it was confirmed that the newly developed model worked well in the actual WDN. The total time spent for segment identification of WDN Y was 13,497 s. In more detail, 304 segment identification required 452 s, and unintended isolation identification required 13,045 s. For the WDN K case, 1,278 segment identification required 605 s, and unintended isolation identification required 39,980 s. In all processes, it was found that the analysis time was shorter than when using the Jun and Loganathan (2007) methodology. Figs. 14 and 15 show the studied WDN Y and WDN K diagram and the identified segment of the downtown area, respectively.

This result shows that it is possible to identify segments in a short time, even in a WDN with more than 50,000 nodes and pipes. The following discussions are based on a WDN with over 50,000 nodes and pipes. Consider the case in which segments of the target area are not identified in advance and are required to identify. When a leak, breakage, or water quality problem suddenly occurs, and the valve in WDN must be closed, the segments can be checked within 10 min using the developed model. Furthermore, in case of all segments have been identified in advance, the WDN manager can immediately know which valves should be closed when an event occurs. However, it is also necessary to identify the unintentionally isolated area caused by closing the valves. Using the developed model, unintended isolation can be identified within 1 min. Being able to see segments and unintended isolation within 10 and 1 min implies that a WDN manager can immediately plan an emergency response. There is sufficient time to respond at this speed for one particular WDN, even if the water supply system is operated in near-real-time using sensor data in units of 1 min.

On the other hand, identifying segments can also be used to reduce the range at which water cannot be supplied when an accident and restore process occurs. In the case of WDN Y, the size of one segment is relatively small. However, in the case of WDN K, the size of one segment is relatively large even though a much larger number of valves are used. In other words, it can be determined that the area where there is a high probability not to be supplied water is WDN K. In such cases, it is necessary to determine where to place the valves to reduce the size of segment. At this time, the segment identification methodology proposed in this study can be used to determine what is the best alternative.

Table 4 presents the results of comparing the advantages and disadvantages of the methodology developed in this study with the previously proposed methods. The results of applying the developed methodology to actual WDNs confirm that the methodology operates at relatively higher speed than previously proposed method; thus, it is practical for actual field implementation.

In addition, previous methodologies required repeated comparisons of several matrices to determine whether or not segments were formed. However, the method proposed in this study can be said to be more efficient by using only one matrix. Compared with the previous methods expressed using only 0 or 1 in the matrices, the rules of the method proposed in this study may feel somewhat complicated. In particular, in the procedure diagram of Fig. 2, it is necessary to pay special attention to the feedback process in the upper stage after the procedure is terminated in the middle. However, if the rules are applied accurately, the methodology developed in this study, which has advantages in terms of convenience as well as reduction of analysis time, can be used.

As water pipes deteriorate incrementally, the frequency of leaks, breakages, or water quality problems in the WDN increases. Considering the deterioration growing trend, the frequency of checking segments and unintended isolation is expected to increase. In this study, a methodology for identifying segments and unintended isolation was developed and illustrated through an example. The approach was applied to two actual WDNs and was compared with the method proposed by Jun and Loganathan (2007). The identification time of the methodology executed in C++ exhibited a level capable of responding in near-real-time. In the proposed methodology, the adjacency matrix $\mathbf{K}$, in which the connectivity of the current WDN could be easy to understand, was used for segment identification. This methodology is convenient because a single row-first search method is used and is compatible with the data storage format of hydraulic analysis software.

Recently, the concepts of segments and unintended isolation have been used in various studies for examining the risk, resilience, robustness, vulnerability, and reliability of WDNs. Even the field of partitioning the WDN to form new district metered areas uses the concept of segments. The proposed segment and unintended isolation identification methodology can be used in numerous ways to configure and analyze WDNs.

Some or all data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.

The Korea Ministry of Environment supported this work titled as “Project for Developing Innovative Drinking Water and Wastewater Technologies” (2020002700016).