## Abstract

One way to mitigate the risk of consumption of contaminated water in water distribution networks is optimal placement of the quality sensors. A considerable challenge in this respect is the significance of contamination at a junction. Beside the population affected and the volume of the contaminated water consumed, importance of each junction is a parameter that must be taken into account in placing the sensors. This parameter directly concerns the service provided by each junction as well as the sensitivity and social consequences of junction contamination. The present study defines a new objective function for minimizing the effect of junction contamination with respect to its importance. Using a robust approach, this study applied the NSGA-III algorithm to solve a 5-objective problem. The algorithm was tested on a hypothetical network and a benchmark network and the Pareto response was selected for each scenario based on the slope of the different points. The proposed method suggested 12, 12, and 11 sensors for the three scenarios in the hypothetical network. The results show that sensor placement by this method yielded good performance in comparison with the other solutions presented in a benchmark network.

## HIGHLIGHTS

A NSGA-III algorithm for five-objective sensor placement based on the robust optimization models is proposed.

By employing two typical water distribution networks, the benefits of the proposed algorithm are illustrated and some critical factors are also addressed.

A new objective function describes the impact of contamination of important nodes.

Uncertainty at the point of entry and the entry time of the contamination are considered.

## INTRODUCTION

Water distribution networks are vulnerable to intentional or accidental contamination given the wide range of the points they could be accessed from. Contamination of a network can lead to serious health, economic, and social consequences for the target community and result in psychological insecurity and erosion of public trust. There are several incidents recorded across the world for intentional or accidental damages to water networks. A recent contamination incident occurred in Lanzhou, China, in April 2014, where the gasoline from a chemical plant accidentally leaked into the urban water distribution network. Unfortunately, failure in early detection of the contamination endangered the general health of many people (He *et al.* 2018). Early detection and warning of contamination reduce the adverse consequences of contaminated water consumption. Development of any contamination alarm system is directly related to the optimal placement of the quality sensors (Bazargan-Lari 2014; Ohar *et al.* 2015; Hu *et al.* 2017; Naserizadeh *et al.* 2018). Two important steps in sensor placement optimization are determining the objective function and developing the optimization approach. Adedoja *et al.* (2019) outlined the objectives set by other researchers in a review paper. The objectives generally considered and discussed so far concern minimization of the effect of contamination, including the following: (1) minimizing the detection time (Kumar *et al.* 1999; Krause *et al.* 2008; Austin *et al.* 2009; He *et al.* 2018; Khorshidi *et al.* 2019a), (2) minimizing the population at risk (Comboul & Ghanem 2013; Ohar *et al.* 2015; Naserizadeh *et al.* 2018); (3) minimizing the volume of the water consumed (Ostfeld & Salomons 2004; Berry *et al.* 2006, 2009; Wu & Walski 2006; Guidorzi *et al.* 2009); (4) maximizing the likelihood of detection (Huang *et al.* 2006; Propato & Piller 2006; Preis & Ostfeld 2008; Austin *et al.* 2009; Dorini *et al.* 2010; Kim *et al.* 2010; Xu *et al.* 2010; Winter *et al.* 2018); and (5) maximizing the demand coverage (Lee & Deininger 1992; Rathi & Gupta 2014). Sensors can also be placed based on the location of the contamination source. For example, Di Cristo & Leopardi (2008) formulated a simple method for identifying the source location of an accidental contamination in a water distribution network.

Solving optimization problems in previous studies has often been carried out using various tools such as Mixed-Integer Programming (MIP), genetic algorithm (GA), Ant Colony Optimization (ACO), and local search (Adedoja *et al.* 2019). Recent research on optimal placement of quality sensors has directly used contaminant transfer simulations to minimize contamination risk (Adedoja *et al.* 2019). Such optimizations require a large number of simulations of contamination events. However, optimization methods like evolutionary algorithms are very costly as each new arrangement of the sensors must be simulated. Therefore, offline simulation prior to optimization has received attention. This method allows for separating the time required for simulation from the time required to run the optimization program. Although these studies have served an important role in development of approaches and sensor placement objectives, they have not paid enough attention to the parameters exerting an effect on the occurrence of contamination. Any contamination event can occur from any junction at any time. In most previous studies, all junctions were assumed to be of the same importance as regards contamination mainly because of the scarcity of information available about junctions; however, this is far from the reality. Some parts of water supply systems have more sensitive usages, e.g., hospitals, schools, governmental offices, military bases, and water industry centers. In addition, the social effects and services of junctions are different. As Bahadur *et al.* (2003) note, contamination of some junctions exert greater effects and consequences than others, which may be taken into consideration by terrorists for sabotage attacks. Having pointed out the importance, they urged taking user sensitivity into account in contamination detection; yet, they did not propose a specific framework and function for such sensitivity. Berry *et al.* (2005) proposed an algorithm in which the probability of attacks to some junctions is considered to be higher than at others. Similarly, they did not provide any details or a framework for the probability function of the junctions. Nor did they account for the importance and risk of contamination of the junctions. This study developed an integer programming method for placing sensors to minimize the population at risk. A recent study by Jafari *et al.* (2020) zoned and divided the junctions examined into five categories based on their importance and assigned a coefficient to each junction, called the coefficient of importance, as the weight of the junction. The study considered a dual-purpose algorithm: minimizing the damage caused by the effective population and minimizing the number of the sensors. The coefficient of importance was defined within the objective function, allowing for virtual estimation of the population affected by contamination. In contrast, the objective function of the importance of each junction in the present study is developed independently, which improves the method proposed by Jafari *et al.* (2020) whilst using the same hypothetical network. This network consists of 81 junctions, 121 pipes, all of which are hypothetical; furthermore, the geometry and topography of this network is not real.

Many of the studies conducted so far have modeled placement of sensors by assuming a fixed number of sensors or by limiting the number of junctions serving as the entry of contamination to avoid high computational processes and a high complexity of the model. Such an assumption, however, is far from correct (Bazargan-Lari 2014; Afshar & Khombi 2015; Janke *et al.* 2017; Tinelli *et al.* 2017). Quintiliani *et al.* (2017) proposed a method for estimating vulnerability with respect to users’ exposure to disinfection byproducts in water distribution systems. The five vulnerability indexes adopted include the following: (1) maximum actual total trihalomethanes (TTHMs) concentration, (2) demand weighted average TTHMs concentration, (3) dimensionless exposure time, (4) normalized contaminated volume, and (5) contaminated mass load, all of which furnish different kinds of information about the exposure for identifying the higher risk nodes. The approach used by Quintiliani *et al.* (2017) is very effective identifying areas and users at risk and managing different parts of a network by controlling and optimizing chlorine dose; however, it is not very efficient in selection of the best location of sensors due to node uncertainty and uncertain time of contamination by the injected pollution. One objective is obviously not enough as several goals are needed to achieve a balanced solution. Wu & Walski (2008) combined detection time (DT), volume of contaminated water consumed (VC) and detection likelihood (DL) in a single objective optimization using a genetic algorithm (GA). The detection time for undetected events was taken as the duration of a simulation and the contamination events were randomly generated using the Monte Carlo simulation. Rathi *et al.* (2016) included the risk of contamination in a unified objective, determined by using an improved risk assessment model that considers the risk of contamination of a pipe line based on the pipe condition, path of contaminant travel from nearby foul water bodies like ditches, sewer line and storm water line, and contaminant zone. Selecting too many objectives at a time complicates computational analyses. The choice of objectives should be such that a balanced design can be achieved according to the different objectives. Single-objective formulation (Aral *et al.* 2009) takes into account the different parameters influencing the location of a sensor in a way that simplifies the problem formulation and is successful in selecting an answer from among the non-dominated ones.

Each objective function can exert a different effect on sensor placement. Many studies have made provisions only for objective functions that minimize the detection time (Cozzolino *et al.* 2006; Khorshidi *et al.* 2019b). Nonetheless, population density is not the same for all junctions. The main goal in some studies (Ostfeld & Salomons 2004) has been to minimize the consumption of contaminated water. Typically, junctions with more water consumption are associated with more densely populated areas and are more likely to be contaminated. Yet, some junctions may be used by important or sensitive users, whose security for high quality water should be provided despite their low water consumption. In other words, contamination inflicted on these users has far more severe social effects/consequences than for common users (He *et al.* 2018). Aral *et al.* (2008) introduced a sub-domain concept which identifies a subset of junctions for candidate sensor locations. The sub-domains were determined using the roulette wheel method based on junction water demand values. The junctions with larger water demand have higher probabilities to be selected for the candidate sensor subset. An improved approach based on the non-dominated sorting genetic algorithm (NSGA-II) was used for the solution of the model. This assumption can be challenged with the concept of the importance of nodes since the importance of each node does not depend only on demand. This means that one node may have less demand than the others, but if it is contaminated, it will have more severe consequences for the community. Therefore, protection of important nodes against contamination can be considered as a separate objective function. Although significant objectives for optimization have been noted in different studies, our research shows that no objective has yet been developed to decrease the risk of critical node contamination. The approach adopted by the present study is the optimal placement of quality sensors for the most critical scenario possible based on optimization models using NSGA-III. In a robust optimization, the obtained answer is justified for all scenarios. This study uses a robust approach to develop a new objective function: the risk of network contamination with respect to importance of each junction. Accordingly, a five-objective optimization model is presented to resolve the problem of sensor placement using the simulator-optimizer approach, which directly uses contaminant transfer simulation. The objectives of this algorithm are as follows: (1) minimizing the maximum possible damage resulting from consumption of contaminated water (the ‘maximum possible damage’ is calculated by damage matrices and prior to optimization), (2) minimizing the time of contamination detection, (3) minimizing the cost regarding the quantity of the sensors, (4) minimizing the risk of contamination for important junctions, and (5) minimizing the likelihood of failed detections. Since a new objective was developed in this study, it was necessary to demonstrate the balance of this objective function with other objective functions in various aspects. Among the objective functions intended, detection time and VC functions are complementary and the contamination of important nodes (CIN) and VC functions are in conflict. The NSGA-III multi-objective approach makes it possible to use managerial opinions and decisions to select the answers and compare them well. Although the time of detection and the volume of contaminated water are complementary objectives, they do not have the same weight in making decisions. However, each of these approaches is an option with its own advantages and disadvantages. In this approach, contamination can begin from any junction and at any time. Four consumption patterns were envisaged based on the usages of the junctions. The performance of the proposed model was evaluated on two networks.

## METHOD

Figure 1 illustrates the presented method. A sensor network in a water distribution system is expected to (1) minimize the amount of contaminated water consumed before the contamination is detected to protect a large population and (2) detect the occurrence of contamination as soon as possible to allow for a timely response. These goals, either individually or collectively, have been pursued by many studies (Ostfeld & Salomons 2005; Krause *et al.* 2006).

The prime goal of sensor placement is minimizing the population at risk; however, it is difficult to estimate the actual population when dynamic and time-related simulations are used; instead the volume of the contaminated water consumed can be used (Xu *et al.* 2010). The breadth of network objectives allows for practical application of the results by taking different dimensions into account. In this paper, formulation of a five-objective optimization is carried out using NSGA-III. Two networks are tested below to prove the performance of the method.

### Optimization model

#### NSGA-III algorithm

Multi-objective optimization is the process of simultaneously optimizing two or more conflicting objective functions while accounting for a number of limitations. Due to conflicting or incomparable objectives in this optimization, it is not possible to achieve an answer which optimizes all the functions at the same time. Therefore, the non-dominated or Pareto answer is used. In order to improve the results, this study uses an advanced evolutionary algorithm known as the Non-dominated Sorting Genetic Algorithm (NSGA-III). A refined version of NSGA-II, this algorithm is designed for multi-objective optimizations. A multi-objective optimization produces a set of possible solutions, thus the concept ‘indirect solutions’, also called Pareto solutions, which are a set of solutions that do not govern the other solutions. To maintain the uniform distribution and the diversity of the Pareto assemblage in NSGA-II, NSGA-III suggests crowding distance (i.e., the distance between a solution and its neighbors), in which the solution with the longer distance is preferred. This is achieved by determining the relative distance between the solutions and reference points. Since NSGA-III easily generates the first solution, it is faster and more efficient than NSGA-II in solving many optimization problems (Deb & Jain 2014; Jain & Deb 2014). See Deb & Jain (2014) and Jain & Deb (2014) for more details.

### Formulation of a multi-objective optimization model

A general simulation framework is presented before describing the sensor placement model for formulation of hypotheses to evaluate the effects of junction contamination. Although this general framework may look simple, the selection and detection of hypotheses are complicated. Overall, modeling contamination of water distribution systems is a difficult task and an open research subject. A contamination event is described by random variables including location, start time, strength, and duration.

The results in this study are presented with regards to the conservative nature of the contaminant. This assumption may be consistent with the worst scenario of intentional attacks as the contamination strength is not reduced by the reactions occurring in the water but only by dilution and mixing. Notwithstanding, reactions of contaminants, which produce harmful by-products, may also be very important (1).

Real detection of a contamination event by a sensor network is a great challenge. Despite rapid scientific advances, existing sensor devices still have limited capabilities. The assumptions in this paper are that the sensors are capable of detecting contamination quickly and that an alarm signal is sent when the concentration of the contaminant exceeds the minimum acceptable level. Unfortunately, the actual effect and response of a contaminant cannot be easily predicted. The studies conducted have accounted for various indicators for designing sensor networks (Watson *et al.* 2004):

**Detection time**: the time interval between the contamination onset and contamination detection by the first sensor. This objective accelerates management and disposal of the contaminated water besides decreasing the consumption of the contaminated water by users.**Volume of the contaminated water consumed**: the total volume of the contaminated water consumed by the population before the contamination is detected.**Likelihood of failed detection**: this ratio is the number of contamination incidents not detected by sensors to the total number of events occurring in the network.**Cost of installation and supply of sensors**: this cost depends on the number of sensors.**Contamination of junctions with respect to the importance of each junction**: each junction is different from the others regarding its importance, which depends on the usage of each junction, health level of the delivered water, and maintenance of service after the attack. More important junctions may serve less populated areas.

*k*and at any time

*h*.

*X*is the decision variable, indicating the number of the junction where sensor

_{s}*s*is installed. X is the vector of the decision variables, whose length equals the number of junctions.

#### Minimizing the average time of detection (ATD)

*k*which is for the first time placed in a sensor in junction

*i*is the shortest travel time by a contaminant from junction

*k*to reach junction

*i*.where

*nk*is the number of junctions from which the contamination has entered,

*nh*is the total number of time steps for the contamination to enter, is the detection time by the first sensor when the contamination enters from junction

*k*in time step

*h*. ATD is the average time of detection of the contamination (Kumar

*et al.*1999). indicates the total contamination scenarios.

#### Minimizing the volume consumed

Calculation of the damage caused by consumption of contaminated water depends on the time of detection. The important point is that the affected population consume contaminated water before the contamination is detected by the sensors, after which no water is consumed. Therefore, in this study, the matrices pertaining to the damage caused by the consumption of contaminated water are calculated before optimizing the placement of the sensors. ‘Damage matrix’ refers to the amount of damage in all possible cases of contamination (junction *k* and time step *h*). For example, if the network in question has 10 junctions and 48 time steps, the dimensions of each damage matrix will be 48*10, so a total of 480 damage matrices must be calculated.

*j*and step

*t*due to entrance of the contamination from junction

*k*in time step

*h*, is the observed concentration in junction

*j*and step

*t*resulting from the entrance of the contamination from junction

*k*and in time step

*h*, is the consumption pattern coefficient, is the water consumption vector (liters per second).

*nj*and

*nt*are the total number of harvest junctions and simulation steps in the network, respectively.

Placement of the sensors should be determined in such a way that minimizes . In other words, the placement should minimize the worst possible damage caused by the contaminated water.

#### Minimizing sensor placement costs

#### Minimizing contamination of important nodes (CIN)

*et al.*2018). In other words, junctions more likely to be contaminated gain more importance in reducing the contamination effects. The importance and sensitivity of each junction depends on the impact and consequences of the contamination at that junction. For instance, a hospital is important both for the service it provides and for the sensitivity of its population. Furthermore, its contamination brings about social effects, including mass panic.

*α* = 0.05 to ensure that the junctions in question are large enough compared to the others.

#### Minimizing failed detection likelihood (FDL)

*A*is the total incidents of contamination. The supplement of

*DL*can be defined as the probability of failed detection (PFD), as follows:

## COMPUTATIONAL EXPERIMENT

### Case studies

The proposed algorithm is implemented on a medium network which is shown in Figure 2. This network has a reservoir and is hypothetical. i.e. the geometry and topography of this network is not real. The placement of the reservoir, diameter and pipe materials are designed according to existing standards. Due to the size of the distribution network and its intended area, the population is estimated at about 324,000 people. The network does not have a contamination detection sensor and consists of 81 junctions and 121 pipes, all of which are hypothetical. Three 24-hour demand patterns have been assumed for this network. The battle of the water sensor networks (BWSN) benchmark network is a relatively simple water distribution system consisting of 169 pipes, 129 junctions, a reservoir, two elevated storage tanks, and two pumping stations (Ostfeld *et al.* 2006). The full networks are shown in Figure 2. The proposed algorithm is evaluated on both networks. The proposed method has no limitations and can be evaluated for very large networks as well.

### Scenario design

EPANET.2 was used to prepare the hydraulic model of the network. The software has an EPANET Programmers Toolkit, which is a Dynamic Link Library (DLL), allowing users to modify the EPANET computing engine according to their needs. The output of this software bears the extension (.inp), which is used as an input file in MATLAB. EPANET uses a gradient for solving the hydraulic equations of a network and a Lagrangian transfer algorithm for the qualitative equations (Rossman 2000).

Water distribution network simulations were carried out statically until 2004, where the system response was simulated only for a certain flow condition (Watson *et al.* 2005). In this case, only a particular moment, such as the maximum or minimum hourly flow, was take into account without considering qualitative analyses. However, the present study uses a dynamic flow analysis to directly simulate the contaminant transfer for qualitative analyses. Contaminants are mixed with the water mass in a water distribution system. Assuming that the contaminant does not react with water, its dynamics are expressed by such parameters as water flow direction, water flow intensity, and dilution of the contaminant on the way between the entry point and water consumption point. Contaminant transfer simulation in the optimization requires analyses of a vast number of contamination occurrences. Needless to say, running simulations to evaluate any new arrangement will make optimization methods very costly. To overcome this problem, simulations are conducted according to scenarios which are defined before performing the optimization. This divides the time required for the simulation from the time required to run the optimization program.

In line with Naserizadeh *et al.* (2018) and Khorshidi *et al.* (2018), arsenic was selected as the contaminant in this study. They considered volume flow reaction (0.05 day^{−1}) in their qualitative simulations yet did not consider the wall reaction coefficient for the qualitative simulations as arsenic does not react with pipe wall materials. The approach to the current problem is the optimal placement of qualitative sensors for the most critical scenario possible based on robust optimization models. The contamination may be injected from any junction and at any time step, i.e., each junction can be a potential location for the placement of a quality sensor. To facilitate the analysis of sensor placement, it is assumed that the sensors function properly and can detect contaminant concentration within the allowable range (0.01 mg/L) without any negative or positive errors. To ensure the stability of water quality parameters in each junction throughout the simulation period, the simulation time is regarded to be 96 hours (He *et* al. 2018). According to previous studies (Ostfeld & Salomons 2008), the time step for quality simulation is 5 minutes. In addition, to account for the sensitivity of the model to the uncertainty of the input dose, three scenarios are defined for both networks. The dose of the contamination in these scenarios varies between 200 and 300 mg/s. Hu *et al.* (2018) hypothesized that the quality sensor produces an alarm so that the response to separate and flush the contaminated water takes place immediately. In this study, it is assumed that the reaction has a 15-minute delay, i.e., as long as 3 time steps. Moreover, the existing junctions are divided into three categories based on water consumption usage (namely commercial, industrial, and housing) based on which three demand patterns were defined.

### Compromise programming (CP) technique

*k*is the index of the objective function,

*nof*is the number of the objective functions,

*Z*is the value of the

_{i}^{k}*k*objective function for the

^{th}*i*answer, and and respectively represent the maximum and minimum values of the

^{th}*k*objective function. Yu (1973) and Zeleny (1974) defined the ideal solution. The ideal point is the point where the values of all the objective functions are at their best and is usually inaccessible, here shown with for the

^{th}*k*objective function.

^{th}*γ*is the distance of the

_{i}*i*answer from the ideal point,

^{th}*w*is the weight of the

_{k}*k*objective function,

^{th}*ρ*indicates the type of distance, for which values 1 and 2 represent the Manhattan distance and the Euclidean distance, respectively. Finally, the answer with the lowest

*γ*value is selected as the final answer from the Pareto front answers (Wills & Perlack 1980).

_{i}## RESULTS and DISCUSSION

NSGA-III was used to solve a five-objective problem in designing sensor networks for two networks in order to minimize the (i) maximum potential critical damage caused by consumption of contaminated water, (ii) average detection time, (iii) likelihood of failed detection, (iv) contamination of important junctions, and (v) sensor placement costs. The results of the three contamination injection scenarios are presented for each of the networks. , , and show the results for 200, 250, and 300 mg/s injections, respectively. The results are presented in the following sections.

### Case A: A hypothetical network

To gain a better understanding of the five-objective Pareto front, the results for Network A are presented in pairs in five graphs in Figure 3. As can be clearly seen, as the number of the sensors increases, the values of the other four objectives drop. The relatively uniform distribution of the points on the Pareto-fronts indicates that NSGA-III had a good performance. In an urban water supply network, some junctions may not face much demand but have important or sensitive users, whose high water quality must be secured. These include schools, hospitals, religious centers, and governmental administrations. Contamination reaching these users has grave social effects. The relationship between each of the five objectives, Z1–Z5, is shown in Figure 3 in form of graphs. Overall, the damages estimated in scenario 3 are more than the other two scenarios. Obviously, as the contamination detection time increases, the volume of the contaminated water consumption increases. After 2,175 minutes (about 37 hours), the greatest volume of contaminated water was consumed, and then the contamination was flushed from the network. Graph Z2–Z3 shows that the Pareto front is formed well. Damage (consumed contaminated water) for 0 and 81 sensors vary from 63,000 liters to 1,379,874 liters in the S3 scenario. There is less damage in the two other scenarios.

The effect of the objective function could be observed more clearly in graph Z2–Z4. Despite the correlation between the changes in the volume of the contaminated water consumption and contamination of important junctions in the overall scheme, the scattered points below the bisector line show that the damage of the junctions does not only depend on the density of water consumption, but also on the other factors defined for the importance function. Graph Z5–Z2 illustrates the probability of failed detections against the damage caused by the volume of the contaminated water consumed. As with an increase in the probability of failed detections, the volume of the contaminated water consumed increases. The Pareto front in graph Z1–Z3 also illustrates the correlation between the two objective functions. Graph Z3–Z5 shows that the probability of failed detection by 81 sensors moves toward zero. When there are no sensors in the network, the value of this objective function is 1. The proper distribution of the values between these two boundary values indicates the proper performance of the NSGA-III algorithm. As can be clearly seen in graph Z1–Z5, there is a direct relationship between the detection time of contamination and probability of failed detections.

Graph Z3–Z4 shows the inverse relationship between the two objective functions including contamination of important junctions and the quantity of sensors. Z4 is equal to 1 when there are no sensors in the network, and it moves toward 0 when there are 81 sensors in the network, i.e., when there are sensors in all junctions. Furthermore, Z4 has higher values in scenario S3 in comparison to the other scenarios. The direct correlation between the objective function of contamination of important junctions and the objective function of contamination detection time and the way they are scattered around the bisector line in graph Z1–Z4 are remarkable.

Finally, no significant relationship could be found between the two objective functions in graph Z4–Z5. Since the interpretation of the five-dimensional Pareto front is difficult, similar to Hu *et al.* (2018), the five-dimensional Pareto front has been examined in the form of several two-dimensional diagrams. For each network, three scenarios have been considered and for the same number of sensors, several non-dominated answers have been obtained, which are presented in Table 1 for better display of the details. As can be seen in the table, sometimes other target functions show different values for the same number of sensors. In scenario S_{1}, three sets of answers are obtained for two sensors. Also in scenarios S_{2} and S_{3}, three and two sets of sensor solutions are obtained, respectively. Choosing a solution from among the several proposed categories of solutions is a major challenge. Table S1 and Table S2.

Scenarios . | Junction ID . | . | . | . | . | . |
---|---|---|---|---|---|---|

637 | 483,582.6 | 12 | 56 | 25 | ||

895 | 574,214 | 12 | 52 | 39 | ||

428 | 647,981.1 | 11 | 52 | 15 |

Scenarios . | Junction ID . | . | . | . | . | . |
---|---|---|---|---|---|---|

637 | 483,582.6 | 12 | 56 | 25 | ||

895 | 574,214 | 12 | 52 | 39 | ||

428 | 647,981.1 | 11 | 52 | 15 |

The primary goal of any multi-objective design of a water distribution system is finding the optimal solution in terms of single-objective functions. Therefore, it is necessary to select and report one of the Pareto solutions. There are many conflict resolution methods used for selection of this point. This study follows Yu (1973) and Zeleny (1974), in which the optimal performance distributed for each objective function, one of which is selected by maximizing a mathematical function according to the slopes of different Pareto points. The optimal results for the selected points are reported in Table 1.

As can be seen in Table 1, the changes in the values of the objective functions obtained in different scenarios induce changes in the results obtained from the placement of the sensors.

It is remarkable that although the detection time in S3 is much shorter than in S2 (half the detection time in S2) and although it has 1 more sensor than S2, the volume of the contaminated water consumed in this scenario is greater. It follows that a change in the dose of the input contaminant exerts a strong effect on the objective function of contaminated water consumption damage and consequently the optimal arrangement of the sensors in the water distribution network. Figure 4 illustrates the distribution of the sensors in the first network based on the points suggested in Table 1. In the first scenario (S_{1}), there are 11 sensors placed in the network. According to Figure 4, the most probable damage in S_{1} is inflicted on the network when the contamination enters from junction 30. However, in S_{2} and S_{3}, the greatest damage is inflicted on the network when the contamination enters from junctions 61 and 58, respectively. The arrangement of the sensors is different in all the three scenarios. The figure shows the scattering of the sensors around the junction from which the contamination has entered.

### Case B: The battle of the water sensor networks (BWSN) benchmark network

The solutions submitted to the BWSN conference (Ostfeld *et al.* 2006), included the application of various models and algorithms for the optimal sensor placement problem discussed above. At the conference, most writers identified the best sensor locations using their preferred algorithms. Some of these solutions focused on optimizing all four measures; others selected some or, in some cases, only one of the four measures as the criterion for optimization.

The comparison of the results obtained in this study with those in Ostfeld *et al.* (2006) was carried out according to the method adopted by Aral *et al.* (2009). The comparison provided below should not be interpreted as an effort to identify which solution is the best or optimal because it cannot be known what the true optimal solution is for this problem, and no solution is perfect for all the measures. The next phase of the comparative analysis is the normalization of the results presented in Table 1.

*Z*

_{i}from the solutions submitted (

*Z*

_{i max}) and calculate the normalized values

*Wi*using Equation (19) (Aral

*et al.*2009):

The basis of comparison in this method is that the comparison is carried out for the same objective functions. It is possible to compare these solutions based on the four criteria identified (four criteria out of five) in this paper which were the primary criteria to satisfy for the BWSN challenge (which was first called by Ostfeld & Salomons (2008) with the purpose of objectively comparing the performance of different teams’ sensor network designs, as applied to two water distribution system examples). As it is assumed that the coefficient of importance is the same for all nodes (for this reason, W_{4} is equal to zero, and excluding Z_{4} from Table 2 calculations has no effect), the results of the present study are compared with the BWSN research according to Table 2. In this comparison, the values of the target function of the infected population were not included. It should be noted that this objective function was one of the objectives of BWSN.

Sensor placement method . | Sensor placement (nodes) . | (minutes) . | (lit) . | (%) . | W_{avg}
. |
---|---|---|---|---|---|

. | |||||

Present Study | 9–68 – 83–98 – 105 | 565 | 13910.13 | 66.74 | 0.65 |

31–68 – 81–97 – 105 | 625 | 17200.89 | 77.23 | 0.64 | |

10-31-83-102-126 | 915 | 24645.6 | 76.65 | 0.48 | |

Guan et al. (2006) | 17–31 – 81–98 – 102 | 632.8 | 9744.84 | 66.32 | 0.66 |

Dorini et al. (2008) | 10–31 – 45–83 – 118 | 1067.1 | 31347.16 | 80.17 | 0.39 |

Berry et al. (2006) | 17–21 – 68–79 - 122 | 533.9 | 9741.438 | 61.07 | 0.67 |

Huang et al. (2006) | 68–81 – 82–97 – 118 | 535.3 | 17363.05 | 67.67 | 0.63 |

Krause et al. (2006) | 17–83 – 122–31 – 45 | 836.4 | 20923.43 | 62.48 | 0.48 |

Eliades & Polycarpou (2008) | 17–31 – 45–83 – 126 | 762.0 | 26206.74 | 77.35 | 0.52 |

Ghimire & Barkdoll (2008a) | 126–30 – 118–102 – 34 | 429.9 | 16512.17 | 37.04 | 0.54 |

Ghimire & Barkdoll (2008b) | 126–30 – 102–118 – 58 | 424.6 | 15512.74 | 40.12 | 0.57 |

Wu & Walski (2006) | 45–68 – 83–100 – 118 | 699.6 | 32916.61 | 78.76 | 0.49 |

Ostfeld & Salomons (2008) | 117–71 – 98–68 – 82 | 705.1 | 32140.58 | 77.98 | 0.49 |

Propato & Piller (2006) | 17–22 – 68–83 – 123 | 704.0 | 12394.24 | 72.70 | 0.64 |

Gueli (2008) | 112–118 – 109–100 – 84 | 768.0 | 35028.12 | 72.70 | 0.43 |

Preis & Ostfeld (2008) | 68–101 – 116–22 – 46 | 739.3 | 38415.38 | 66.12 | 0.38 |

Trachtman (2008) | NA | – | – | – | NA |

Sensor placement method . | Sensor placement (nodes) . | (minutes) . | (lit) . | (%) . | W_{avg}
. |
---|---|---|---|---|---|

. | |||||

Present Study | 9–68 – 83–98 – 105 | 565 | 13910.13 | 66.74 | 0.65 |

31–68 – 81–97 – 105 | 625 | 17200.89 | 77.23 | 0.64 | |

10-31-83-102-126 | 915 | 24645.6 | 76.65 | 0.48 | |

Guan et al. (2006) | 17–31 – 81–98 – 102 | 632.8 | 9744.84 | 66.32 | 0.66 |

Dorini et al. (2008) | 10–31 – 45–83 – 118 | 1067.1 | 31347.16 | 80.17 | 0.39 |

Berry et al. (2006) | 17–21 – 68–79 - 122 | 533.9 | 9741.438 | 61.07 | 0.67 |

Huang et al. (2006) | 68–81 – 82–97 – 118 | 535.3 | 17363.05 | 67.67 | 0.63 |

Krause et al. (2006) | 17–83 – 122–31 – 45 | 836.4 | 20923.43 | 62.48 | 0.48 |

Eliades & Polycarpou (2008) | 17–31 – 45–83 – 126 | 762.0 | 26206.74 | 77.35 | 0.52 |

Ghimire & Barkdoll (2008a) | 126–30 – 118–102 – 34 | 429.9 | 16512.17 | 37.04 | 0.54 |

Ghimire & Barkdoll (2008b) | 126–30 – 102–118 – 58 | 424.6 | 15512.74 | 40.12 | 0.57 |

Wu & Walski (2006) | 45–68 – 83–100 – 118 | 699.6 | 32916.61 | 78.76 | 0.49 |

Ostfeld & Salomons (2008) | 117–71 – 98–68 – 82 | 705.1 | 32140.58 | 77.98 | 0.49 |

Propato & Piller (2006) | 17–22 – 68–83 – 123 | 704.0 | 12394.24 | 72.70 | 0.64 |

Gueli (2008) | 112–118 – 109–100 – 84 | 768.0 | 35028.12 | 72.70 | 0.43 |

Preis & Ostfeld (2008) | 68–101 – 116–22 – 46 | 739.3 | 38415.38 | 66.12 | 0.38 |

Trachtman (2008) | NA | – | – | – | NA |

*Note*: NA, not available, .

The overall performance of the results submitted to the BWSN session with the use of normalization and averaging methods are presented in Table 2. More important, these evaluation scores are linear and not biased based on a domination ranking process such as Pareto front analysis, as was presented during the BWSN session in Cincinnati in 2006 (Ostfeld *et al.* 2008).

The solutions provided by Berry *et al.* (2006) and Guan *et al.* (2006), this study, Propato & Piller (2006), and Huang *et al.* (2006) are ranked as the top five solutions, respectively. On the other hand, the answers provided by Dorini *et al.* (2008) and Preis & Ostfeld (2008) have the lowest rank. The other solutions are not close to the high ranks. The discrepancy between the answers is most likely due to the fact that some of these solutions did not equally consider all of the optimization criteria or did not neglect the undiagnosed ones, which has affected the overall scores of the solutions. This emphasizes the strength of the robust approach and the NSGA-III algorithm for finding the best solutions and balancing all optimization criteria, as they consider all criteria as equally important. For more information regarding the comparing of the optimal solution and performance for WBSN case with 20 sensors see Supplementary Data Table S3.

The development of the Z_{4} objective function requires information about the location of important centers in the city. But no additional information is available on the BWSN benchmark network. So, we randomly considered network nodes according to Equations (11) and (12) with the probability in the set and the other nodes in the set. The results for 5 and 20 sensors are presented in Table 3.

. | Sensor placement . | (minutes) . | (lit) . | . | . | . | . |
---|---|---|---|---|---|---|---|

2, 4.40, 6, 11, 12, 15, 22, 33, 45, 57, 74, 95, 101, 103, 104, 114, 116, 122, 123, 124 | 17, 18, 30, 49, 103 | 3855 | 490 | 5 | 0.18 | 0.78 | 0.37 |

0.25 | 0.08 | 5 | 0.14 | 1.00 | |||

22, 69, 20, 109, 115 | 5155 | 535 | 5 | 0.21 | 0.66 | 0.21 | |

0.00 | 0.00 | 5 | 0.00 | 0.85 |

. | Sensor placement . | (minutes) . | (lit) . | . | . | . | . |
---|---|---|---|---|---|---|---|

2, 4.40, 6, 11, 12, 15, 22, 33, 45, 57, 74, 95, 101, 103, 104, 114, 116, 122, 123, 124 | 17, 18, 30, 49, 103 | 3855 | 490 | 5 | 0.18 | 0.78 | 0.37 |

0.25 | 0.08 | 5 | 0.14 | 1.00 | |||

22, 69, 20, 109, 115 | 5155 | 535 | 5 | 0.21 | 0.66 | 0.21 | |

0.00 | 0.00 | 5 | 0.00 | 0.85 |

*Note*: , A set of nodes whose important coefficients according to Equation (10) is = .

As can be seen, the answer was obtained for five sensors in two categories. Similar to the single-objective analysis in the previous sections, the results are normalized as single-objective between [0,1]. A comparison of the results in Tables 2–3 clearly shows the effect of the development of the proposed objective function. Compared to the values presented in Table 2, W_{avg} has significantly changed in Table 3. A very important reason is that this objective function is thoroughly independent of the other objective functions. For more information regarding the optimal solutions in BWSN with 20 sensors see Supplementary Data Table S4.

## CONCLUSIONS

This study was developed with the goal of improving the optimal placement of sensors. The algorithm was tested on a benchmark network and a hypothetical network i.e. the geometry and topography of this network is not real and the network does not have a contamination detection sensor and consists of 81 junctions, 121 pipes, all of which are hypothetical. To this end, an objective function was introduced beside the four other objective functions for the damage of contamination in important junctions. In this paper, the change in the dosage of the input contaminant was studied in three scenarios. Uncertainties about contamination from an unknown source and time were also taken into account. Another goal of the study was evaluating the performance of the NSGA-III algorithm in solving a 5-objective problem of sensor placement. This study revealed the need for developing an objective for ‘importance of each junction’ to reduce the likelihood of the contamination of the junction in question beside the other objective functions. Another feature of this method is defining variable consumption patterns with respect to junction use. The proposed algorithm was tested on two networks, and one point was selected based on the slope of different points in the Pareto front obtained for each scenario. The proposed method suggested 12, 12, and 11 sensors for the three scenarios in the case A, respectively. The proposed location for the sensors was different in all the scenarios.

The suggested model was able to account for the effects of contamination entry from several respects. The findings demonstrated that by using the proposed model, the minimum number of sensors can be estimated and their safe placement can be achieved to minimize the effects of contamination entering a water distribution system, including the possibility of failed detection, detection time, and damage caused by consumption of contaminated water. The use of two separate stages of simulation (contamination matrix extraction) and optimization (placement of sensors based on the simulation results) in this research prevented processing problems and reduced computation time. Also, a BWSN water distribution network was used to demonstrate the performance of the model and the solution algorithm proposed. Similar to Aral *et al.* (2009), a single objective function was used in this model. The proposed objective function reflects the requirements of the four criteria identified in the BWSN challenge and may achieve the purpose of a multi-objective function with a reduced computational effort. This objective function is not linked to the specific solution methodology suggested in this study, thus it can be embedded in other solution methods to achieve the same effect and can even be used in Pareto analyses. An important characteristic of the model is that the imbedded trade-off coefficients in the objective function are defined in terms of the four measures of the problem and they are optimized as the solution progresses. Finally, the results of this study provide a set of optimal non-dominated methods for decision-makers. It is suggested that the effect of other uncertainties, such as water need, duration of contamination injection, and the effect of reaction of the contaminant with disinfectants be investigated for further research.

## DATA AVAILABILITY STATEMENT

Interested readers are asked to contact the corresponding author if needed.

## REFERENCES

*Water Distribution Systems Analysis Symposium 2006*

*Water Distribution Systems Analysis Symposium 2006*

*Water Distribution Systems Analysis Symposium 2006*

*Water Distribution Systems Analysis Symposium 2006*

*Water Distribution Systems Analysis Symposium 2006*