Merged two-level optimization for optimal pump operation of large scale urban water distribution system

The operational cost of pumps in a water distribution system (WDS) represents a significant fraction of the total expenditure incurred in the operational management of WDSs worldwide. Pumps consume large amounts of electrical energy for pumping water from source to storage tanks and to demand nodes. Therefore, the goal of a pump scheduling problem is to minimize the total pump operational cost, while guaranteeing a competent network service. In most cases, this problem is equivalent to the minimization of pumping cost, while supplying water to consumers at adequate pressures (López-Ibáñez et al. 2008). In recent years, a significant amount of research has been focused on optimizing pump operation schedules. Since 1970, a variety of conventional methods such as dynamic programming, linear programming (LP) and nonlinear programming were developed to address this problem. A review of some early optimization approaches to pump scheduling can be found in Ormsbee & Lansey (1994). Price & Ostfeld (2013) developed an algorithm which enables iterative linearization of increasing or decreasing convex nonlinear equations and incorporating them into LP optimization models, which results in short solution times. However, the discrete (binary) nature of some variables and the size of the solution space are among the main difficulties of optimizing water distribution systems operation (Van Dijk et al. 2008). Conventional optimization methods are not directly applicable for solving such problems, because these methods are suitable mostly for optimization problems which have only continuous variables, therefore population based methods such as evolutionary algorithms and various meta-heuristics were introduced to deal with the optimal pump scheduling problem. Mackle et al. (1995) presented a single objective optimization (electric energy cost) using genetic algorithms (GAs). Then, Savic et al. (1997) proposed a hybridization of a GA with a local search method, in order to optimize two objectives: electric energy cost and pumps maintenance cost. Fang et al. (2011) solved optimization of the pump system with constant and variable speed pumps with multi-objective evolutionary algorithms (MOEAs) combined with a repair mechanism. As a result, evolutionary computation has proven to be a powerful tool to solve optimal pump-scheduling problems (Benjamin et al. 2005). Although the methods mentioned above give theoretic methods for solving the optimal pump scheduling problem of WDSs, population based algorithms have the following drawbacks. First, they require a large number of the objective and constraint function evaluations which are not acceptable when these evaluations are expensive. Second, they are inefficient for solving large scale problems. Third, these algorithms sometimes cannot locate a solution with high accuracy and as a result, they may produce only suboptimal solutions (Bagirov et al. 2012). In this situation, a two-level optimal concept was addressed on better effectiveness and efficiency of solving the optimal pump scheduling problem. In a methodology based on a two-level optimal concept, the optimal outflow and head of source nodes or elevated storage trajectory are determined in the first optimal level, and the optimal pump schedules will be determined in the second level, so that a complex optimal problem is divided into several relative simpler optimal problems. Ormsbee et al. (1989) proposed a two-level optimal methodology using elevated tank trajectory as the first level objective, and pump combinations as the second level objective. The optimal trajectory is determined using dynamic programming while the associated pump combination is determined using an explicit enumeration scheme. Kevin & Kofi (1994) developed a two-level optimal methodology based on Ormsbee's concept, and considered pump switches as a constraint of optimization model. Pump combinations were solved by dynamic programming. Due to the problem of the variables dimension, these methods are only applicable to small to mid-size systems with elevated storage. Zheng (1997) developed a two-level optimal methodology regarding outflow and head of source nodes as the decision variables of the first level optimal problem. The first level optimal problem is solved by the variable-metric method, and the pump combination result is obtained by the enumeration scheme. Zhang et al. (2000) presented a method using different algorithms to solve optimal pump combination problems for pump stations with or without variable speed pumps in the second level, so that the pump rotary speed can be regarded as decision variables and more rational and efficient pump combinations can be obtained. Yuan et al. (2010) proposed a two-level methodology which determines outflow variables in the first level using the Wilson–Han–Powell method, and determines pump combination and pump rotary speed with a reduced gradient method. With the development of the two-level methodology, more effective and efficient optimal models addressed on large scale WDS optimal operation problems are presented. However, there are still some problems that hinder the optimization method to be applied in practice. In these problems, the most outstanding ones are as follows. (1) Since there is no determined pump schedules, only meta-models can be used in the first level optimization. However, the meta-model is not as robust as a hydraulic model, so the reliability of optimization result is low. (2) Another problem of the two-level optimization is discordant of results in different levels. Since the two levels are solved in totally different phases, the feasibility of the first level result cannot be examined by pump combination information. So sometimes there is no feasible pump combination that can match the result of the first level.

For the purpose of solving these problems, a modified hydraulic model and pump combination database are introduced into the two-level method. By regarding pump stations as high level reservoirs, the hydraulic model of WDSs can be modified into a modality that can be used in the first optimal level of the two-level method, so that the defects of poor effect and low reliability of optimal results of the first optimal level solved with meta-models will be resolved. By building a database on feasible pump combination, a new optimal method in the second optimal level will be proposed. The solving process of the second optimal level will be embedded into the first optimal level, so that the problem of discordant results in different levels will be solved.

The only purpose of optimal operation of WDSs is to reduce the electricity cost while meeting hydraulic constraints. In the single objective optimization method, constraints will be added into the evaluation value by the weighting method or punish functions. Previous studies (Mackle et al. 1995; Boulos et al. 2010) dealt with constraints by penalizing the objective function. This requires the definition of a penalty function and appropriate penalty values. Moreover, different penalty values are required for different types of constraints and the degree of violation of some of these constraints cannot be easily quantified. To avoid this, a multi-objective optimal model is built with three objectives: minimum electricity cost, minimum amount of lower pressure service nodes and minimum error between two optimal levels. A multi-objective oriented solving method is used in the optimization.

In order to obtain feasible pump schedules, the optimization model must satisfy system constraints that represent its performance criteria. These include hydraulic constraints representing conservation of mass and energy, minimum and maximum limits on tank storage levels, minimum pressures requirements at demand nodes, and a balance between supply and demand from tanks. The hydraulic simulator implicitly handles some of these constraints. In the proposed method, the minimum pressure requirement is regarded as an objective value, so there are no constraints about demand nodes pressure criteria in the optimal model. In this study, EPANET is used as the hydraulic simulator for handling the constraints.

The pump combination database will be used in the second optimal level. The records of running conditions of each pump combination are stored in the database. For each source node, the pumps will first be organized into a set of pump combinations. Then the characteristic curves (Q-H, Q-E curves) of the parallel pump running conditions of each pump combination will be calculated by using characteristic curves of each pump of the combination. In the database, the characteristic curves for each pump combination are recorded by discrete running condition sample points. In each running condition point, the parameters of flow, head, efficiency and power are recorded. The detailed process of building a pump combination database is described below. In general, it is rare to run all pumps in one pump station simultaneously, so a maximum amount of running pumps can be set for the pump station. With this limitation, the records in the pump combination dataset will be smaller, and the efficiency of the enumeration algorithm for the pump combination selection can be enhanced. The pumps and combinations of example pump station are shown in Table 1.

In the example pump station, there are three pump types A, B and C and the maximum number of running pumps is 4. The total combinations are listed in the ‘combination’ column. Each element in the ‘combination’ column is combined by pump type and its number (the number in brackets after the pump type), and there is no number and bracket if the number is 1.

After calculation of all parameters of sample points in the pump combination characteristic curves, the results will be stored in database in the format shown in Table 2.

In the case of multi-objective optimization, instead of obtaining a unique optimal solution, a set of equally good (non-dominating) optimal solutions is usually obtained (Pareto sets). Several methods, such as meta-heuristic algorithm (Kim et al. 2004), versions of GA (Khu & Keedwell 2005; Alvisi and Franchini 2006), NSGA-II (Deb et al. 2002) and particle swarm optimization algorithm (Liu et al. 2008) are available to solve multi-objective optimization problems. NSGA-II is used here to obtain the Pareto set.

In the evolving process, the three objective values of each solution are obtained in different levels. In the first optimal level, by decoding chromosome string into reservoirs' water level and by hydraulic simulation, the objective value of lower pressure service nodes amount can be obtained. Since the outflow of each reservoir is calculated in hydraulic simulation, so the optimal pump combination for each reservoir can be selected from the pump combination database according to outflow, head and neighbourhood region. After the pump combination is selected, the electricity cost objective value and error objective value can be calculated. The pump combinations of the simulated period are determined. The pump combinations will be stored in the individual of each solution. After calculation of objective values, solutions will be sorted by a non-dominated sorting method, and assigned rank value.

The pump operation schedules of each reservoir in the simulated period will be obtained after a run of the merged two-level optimal method. For an extended period of pump schedules operation, the merged two-level optimal method should be run several times equal to time steps in total duration.

A real WDS in North China is used here as a case study network. This WDS serves a population of nearly 3 million. Daily water consumption is in the range of 0.7–0.9 million m³. In the daily water consumption pattern, there are two consumption peaks, generally at 10 am and 7 pm. The studied WDS has seven pump stations (each pump station has a reservoir) and 48 pumps. In total, the network consists of 3732 nodes and 4522 links with a total length of 764.76 km. Details of the pump stations are shown in Table 3.

In Table 4 the maximum relative error of the two models is less than 0.05. It shows that there is little error between the hydraulic simulation results of the two models. So it is feasible to use a modified model and pump combination database for calculation of objective values in the optimal process as a surrogate of the original hydraulic model.

From Figure 5 it can been seen that the hydraulic error objective converges to the feasible solution space rapidly and searches for better solutions in the feasible solution space. The transparent blue box defines the feasible solution space. In this space, the objective value of ‘hydraulic error between two optimal levels' is less than 1. This means that solutions found in this space all have feasible pump combinations for every reservior of WDS. Generally, after 30–40 generations evolution the average objective values can enter the feasible solution space, and use the rest of the evolving process to search the feasible solution space thoroughly. If considering the best solutions generated during the evolving process, some best solutions reach the feasible solution space much earlier than the average solutions, so the search process in the feasible solution space should start much earlier than the situation shown in Figure 5. This performance is a result of merged two-level optimization. By embedding the second optimal level into the first optimal level, the solutions without a feasible pump combination and solutions with poor hydraulic performances are eliminated in the initial generations of the evolving process, and lead the search direction to the feasible solution space. This prevents the possibility of generating unfeasible results in the whole optimal process.

The second concern is the quality of the optimal result. The quality of the optimal result can be evaluated from two aspects: electricity cost and hydraulic performance of WDS. A comparison between the optimized optimal pump schedules and the original pump schedule from the aspect of electricity cost is shown in Table 5.

The solid line and dashed line express the maximum and minimum electricity cost reduction among 10 runs. The area between the two lines is the band that represents the electricity cost potentiality found by the merged two-level optimization. Most of the band area is above the abscissa axis, it means in most cases the optimal method found pump combinations with lower electricity cost. For the case network, most cost reductions were achieved at night. This indicates that the original pump schedule for the night hours has room for improvement.

Table 6 shows the comparison of lower service pressure nodes between the original pump schedule and the optimal pump schedules.

It can be seen from Table 6 that lower service head nodes in the test network with optimal pump schedules are much less than the situation with the original pump schedule. It shows that the proposed method has the ability to find solutions which not only reduce the electricity cost but also enhance the hydraulic performance of WDS. By transforming the lower service pressure constraint into an objective function in the optimal process, better solutions in both cost saving and hydraulic performance enhancement were found. Since there are no penalty functions or weighted coefficients used in the optimal process, the unreasonable setting of penalty functions or weighted coefficients is avoided. This makes the merged two-level optimal method a robust method in finding better solutions of lower cost and high hydraulic performance.

One thing that should be considered but is not discussed in this study is pump ON/OFF switch times. Because the optimization for each 1-hour simulation step is implement isolated, so the pump switch times during the 24 h pump scheduling optimization could not be concerned in the optimal process. Table 7 shows the average times of each pump type in the pump stations. Since the optimal result is shown in the format of pump combination with pump type and its number for each pump station, the optimal result does not give the operation schedule for each pump, so the average times of each pump type in the pump station is used here to evaluate pump switch times. Average times of each pump type is calculated by dividing total switch times of certain pump type by pump number of that pump type. There are 10 runs of optimal method, and the maximum, minimum and average values of ‘average switch times of each pump type’ is shown in Table 7, and the average pump switch times of original pump schedule are also shown as a comparison.

From Table 7 it can be seen that the pump switch times of optimal result is obviously higher than switch times in the original pump schedule. A reasonable explanation for the increase of pump switch times is that to meet the objective of electricity cost reduction, the selected pump combination for each 1-hour simulation step should meet the water consumption in WDSs more precisely, so that running pumps can stay in a high efficiency state, however, this can also cause a situation of high frequency of ON/OFF switches of pumps. So when consumption demand changes the pump combination tries to find a high efficiency pump combination to attain the minimum electricity cost objective. The important thing is that the pump switch times should stay in an acceptable range. Since there is no tradeoff between electricity cost reduction and pump switch times, so the result of high pump switch times occurred in the proposed methodology. Although the pump switch times are higher than the original pump schedule, the optimal schedules of most pump stations are acceptable. The maximum number of simultaneously running pumps in each pump station in the WDSs is set as 4, so certain pump types with spare pumps have a relatively lower average pump switch time because the total switch times can be shared by relatively more pumps, for example, there are seven pumps of type 10-LN-13 in PS7, and the maximum pump switch times of this type is 11 during a whole 24 h pump schedule period. Divided by seven, each pump only experienced 1.57 ON/OFF occurrences in 1 day. An extreme case of high switches is the pump of 14sh-13A in PS4, because there is only one pump of that type in the pump station, so all switches will act on this pump. In this case, an operation schedule modification for certain pumps should be carried out manually.

The computational effort required by the merged two-level optimal method was measured when run on a Core 2 Duo T6500 (2.10 GHz) with 2048 kb of cache size running under Windows XP. The mean computation time required for one run of one hydraulic simulation step of the case network was 1198 s, while it was 7.99 hours for a 24 h pump schedules optimization with a hydraulic step of 1 h. Since each optimal process for every simulation step is run totally separately, the total computation time can be shortened by parallel runs of optimal program in one computer or several computers.

By introduction of a hydraulic model and pump combination database, a merged two-level optimal method for WDS optimal pump operation is proposed. By transforming the pump station of the original hydraulic model into an elevated reservoir, the modified model can be used in the first optimal level for evaluation of hydraulic performance of candidate solutions, and the defects of fallibility and incomplete hydraulic performance evaluation of meta-model are avoided and more reliable solutions can be obtained. By building a pump combination database, the enumeration algorithm is used in the second optimal level, and the complexity of second optimal level is reduced significantly. This makes it possible to run the second optimal level process to each solution in each evolving step of evolution algorithms, so that the second optimal level can be embedded into the first optimal level to form a merged two-level optimal methodology. Be embedding the second optimal level into the first optimal level, the solutions without a feasible pump combination will be eliminated and lead the solving process to converge on the feasible solution space so that a generation of impracticable results can be avoided. A multi-objective optimal model and solving method NSGA-II are used in this study, hydraulic constraint of lower service node count and hydraulic errors between two levels are regarded as objectives in parallel with electricity cost objective in the multi-objective model. These measures solve the problems of unreasonable penalty functions or the setting of weighted coefficients that occur in optimization methods using single objective optimal models.

Since there is no limitation for maximum pump switch times in the optimal process, sometimes results with a high frequency of pump switches will be obtained by the proposed method. In this case, a manual modification to optimal results should be carried out before pump schedules are put into effect.

The authors acknowledge the support from Seventh Framework Programme (FP7) Marie Curie Actions International Research Staff Exchange Scheme- Smart Water (PIRSES-GA-2012-318985) and FP7-WatERP (EC-318603), and also acknowledge the support from the Project of Construction Science and Technology-Component Based Software Development of Information Management Platform of Water Distribution System (2010-53).