DISCRETE OPTIMAL DESIGN OF WATER PIPELINE SYSTEMS BY MEANS OF EVOLUTION

Zheng Y. Wu

Supervising Software Engineer, MW Soft Inc, 300 North Lake Ave, Suite 1200,

Pasadena, CA 91001, USA, Tel. 1-626-5686637, Fax 1-626-5686870,

E-mail: zheng.wu@mw.com.

Abstract: This paper presents an approach for discrete optimal design and rehabilitation of water distribution systems. A simple analysis showing a comparison of continuous and discrete optimization is presented. It indicates that there is no guarantee, in general, that the continuous optimization model using a fitted cost function will reach the least cost design solution. A discrete pipeline optimization model has been proposed and implemented by integrating a genetic algorithm with a hydraulic network simulator. The model is formulated to search for the least cost combination of available pipe sizes. It has been tested on an example for the optimal design of water distribution systems. The results have shown that the discrete optimization model developed in this paper is effective at producing the optimal and near optimal solutions.

Keywords: water distribution systems, genetic algorithms, optimal design and optimal rehabilitation

1    INTRODUCTION

A water distribution system has been one of the major requirements in urban and regional economic development. It is essential that a systematic hydraulic analysis is carried out to achieve a cost-effective design and upgrade of a water distribution system. A computer model is usually established to perform the hydraulic simulation of a water distribution system. It is the wide application of the hydraulic modeling technique that enables a water engineer to answer what-if questions for design and construction of a water system. Due to the tremendous large combinations of possible scenarios, it is practically impossible that a cost-effective solution can be found by trial and error of answering the what-if questions. In profit-driven industry, as well as in government authorities, the objective is to maximize the value or to reduce the cost of the system, while satisfying constraints on resources, performance, and human limitations. Once the cost function or measure of value is chosen and the constraints are identified, the system designer would like to have a method by which optimum design is found.

Over decades, the optimization of water distribution networks has been studied by using enhanced optimization techniques. Optimization models developed for optimal design of water distribution systems can be generally classified into a discrete pipe model and a continuous pipe model. Both types of the models have been formulated to minimize the total cost of water pipelines by searching for the optimum combination of pipe sizes. The continuous model treats a pipe size as a continuous variable taking a value between the minimum and maximum diameters, while the discrete pipe model allows the pipeline to be designed by directly using a commercially available pipe size. A continuous optimal solution is often converted to a hydraulically equivalent discrete solution (a solution of two adjacent pipe sizes used for upstream pipe segment and downstream pipe segment between a pair of nodes). However, a continuous pipe size is not the real lower cost pipeline design. This paper presents a discrete optimization approach in a framework of a genetic algorithm for the optimal adjacent design of a water distribution network.

2    CONTINUOUS MODEL

For a continuous pipe diameter formulation, the pipe cost function is generally fitted as:

                                  (1)

by using a set of commercially available discrete pipe sizes and a set of corresponding unit length costs , where a and b are fitted coefficients, and b > 0, a > 1.0 (for example b =1.1 and a =1.24 for the New York water supply tunnels problem¹. It is assumed that the fitted curve of Eq. (1) is a convex function (i.e. a > 1.0). The cost for a pipe n with a continuous diameter  and a length  is:

                                      (2)

The pipe n with a continuous diameter  and length , however, can be divided into two segments with discrete diameters  and  where superscript u refers to the upstream segment and d to the downstream segment of pipe. The following constraint must hold such that the pipe of larger diameter is in the upstream segment. The lengths of the two segments between a pair of nodes are and , where . The lengths of both upstream and downstream pipe segments are found by applying a head loss equation to keep the same total head loss in the continuous diameter system as in the discrete pipe system, given as:

                                          (3)

where represents the head loss of a pipe using a continuous diameter, and are the head losses of the two segments of the equivalent pipe. The head loss is given by the most commonly used Hazen Williams formula, expressed as:

                               (4)

where Q_n  is discharge in the pipe, and C_n  is Hazen Williams coefficient for pipe n. Thus the equivalent discrete pipe sizes and the length of its corresponding pipe segment cam be found by Eq. (3) and (4). The cost of the pipeline with two adjacent discrete pipe sizes is evaluated as:

                                 (5)

where is the unit length cost of pipe size  and is the unit length cost of pipe size . The cost difference, between the continuous solution evaluated by Eq.(2) and the equivalent discrete solution given by Eq.(3) to (5), is exempted by comparing the optimal pipe solutions^1,2 for the New York water supply tunnels problem. The pipeline cost for this problem was evaluated for continuous and equivalent discrete pipe diameters. Table 1 gives a comparison of the costs for both continuous design and equivalent discrete design. It shows that the network costs of the equivalent discrete pipe design are greater than that given by the continuous model using the fitted cost function. It indicates that the cost of a continuous pipe solution increases as the solution is converted to its equivalent discrete pipe solution. This has been proven for the general case of a continuous model³. It is, therefore, believed that there is no guarantee that the continuous model using a fitted cost function (i.e. a > 1.0 in Eq.(1)) will reach an optimal discrete pipeline solution.

Table 1    Comparison of discrete and continuous pipe costs ($million)

3    DISCRETE PIPELINE DESIGN

The discrete pipeline design model is formulated to select pipe diameter sizes ={dn, n=1,..., N}, where N = number of all new pipes added to a water system, and to choose rehabilitation actions (e.g. duplicating or replacing a pipe or cleaning a pipe) and the associated pipe sizes ={er, dr, r=1,...R }, where R = number of all possible rehabilitated pipes. The pipe diameters d_n and d_r take on the values in an interval between the minimum and maximum pipe sizes namely d_n, d_r Î [d^min, d^max], where  = minimum diameter of pipe sizes; and  = maximum diameter of pipe sizes. The cost of a new pipe or a rehabilitated pipe is evaluated by discrete pipe sizes given by Eq. (3) to (5). Thus the objective of the optimization procedure is to minimize the total cost of the network pipeline materials, installation and rehabilitation actions, given as:

search for    

minimize      

subject to    

where D⁰ = the set of commercially available pipe sizes;  = k-th commercially available pipe diameter in set D⁰; K = number of the commercially available pipe sizes; E ⁰ = the set of possible rehabilitation events;  = m-th rehabilitation event that may applied to the existing pipe r in set E⁰ and M = number of the rehabilitation events applicable to pipes. The optimization variables are the pipe diameters and rehabilitation actions for pipes. They are automatically calculated by a competent genetic algorithm⁴ to minimize the cost objective function. To maintain an adequate level of water supply service, a set of implicit system performance constraints (e.g. the minimum required pressures) are applied to possible design solutions.

4    COMPETENT GENETIC ALGORITHM

A genetic and evolutionary algorithm is the optimization method based upon the principles of genetic recombination and evolution. It searches from an entire population of possible solutions (individuals). A population of the individuals is created and reproduced by mimicking genetic reproduction and Darwin’s natural selection principle of survival of the fittest. Each individual in the population is represented by either alphabetic or binary string that encodes one possible solution. The number of bits in one string is referred to as the string length. The string length remains unchanged during the search process in simple GA. It creates a tidy representation of a solution space. A competent genetic and evolutionary algorithm the messy genetic algorithm (mGA)⁴ was developed by using a variable-length string representation. It delivers reliable solutions in sub-quadratic time and has been found more efficient than the tidy-represented genetic algorithm optimization for water distribution systems^5,6.

5    APPLICATION AND RESULTS

A network with two water supply sources and fourteen pipes has been studied by Simpson et al.⁷. Figure 1 shows the layout of the system. It contains two reservoirs, five new pipes to be sized, and nine existing pipes, three of which may be rehabilitated by duplication, cleaning or alternatively left as they are. In Figure 1, solid lines represent the existing system, and dashed lines represent the parts of the system where pipe links [1], [4] and [5] may be rehabilitated, and pipe links [6], [8], [11], [13] and [14] are to be sized with at least the minimum diameter pipe. The design is constrained by three demand cases including two fire loading cases and one peak day loading case with the associated minimum required pressures.

Table 2    Optimal discrete pipe solutions for the two-reservoir network

The genetic based discrete optimization approach has been applied to the two-reservoir network, a number of near optimal solutions have been identified and the results are given in Table 2. The best discrete pipe solution was found with the total cost of $1.7145 million. It is the best solution so far comparing to the previous methods³. The other solutions found by the GA approach are slightly different in cost, but various in pipe sizes. They provide an engineer alternatives to the lower cost design of the network. This is one of the advantages of the GA optimization technique. It produces a set of near optimal, rather than one solution by traditional methods. Figure 2 illustrates the convergence behavior of the GA optimization for the two-reservoir network. It shows that the GA quickly detected the optimal solution region and effectively located the optimal solution.

6    CONCLUSIONS

A discrete optimal design model for water distribution systems has been developed in the framework of genetic algorithm optimization. It eliminates the need for fitting a continuous cost function to discrete values. A continuous cost function may lead the search process to a lower cost design solution, but the continuous solution is not desirable for practical application in most of cases. The discrete optimization model allows any combination of available pipe sizes to be used for a pipeline design during the search process. It delivers the pragmatic optimal solution for water pipeline systems.

This model has been tested on a benchmark problem for the optimization of a water distribution system. The results have shown that the genetic algorithm discrete optimization for the design and rehabilitation of water distribution networks is effective at achieving the least cost solutions. It is a powerful technique for water industry to achieve the sound economic design and rehabilitation strategy for water distribution systems.

References

[1]    Fujiwara O. and Khang D. B. (1990). A Two-Phase Decomposition Method for Optimal Design of Looped Water Distribution Networks. Water Resources Research. Vol. 26, No. 4, 539-549.

[2]    Bhave, P. R. (1985). Optimal expansion of water distribution systems. J. of Environmental Engineering, ASCE, 111(2), 177-197.

[3]    Wu, Z. Y. (1997) “Messy Genetic Algorithms for Optimization of Water Distribution Systems Including Water Hammer”,  Ph.D Thesis, University of Adelaide, Australia.

[4]    Goldberg, D. E., Korb, B., & Deb, K. (1989). “Messy genetic algorithms: Motivation, analysis, and first results.” Complex Systems, 3, 493-530.

[5]    Wu, Z. Y. and Simpson A. R. (2000). “Competent Genetic Algorithms for Optimization of Water Distribution Systems.” Accepted by J. of Computing in Civil Engineering, ASCE.

[6]    Wu, Z. Y., Boulos, P., Orr C.-H. and Ro J.-J. (2000) “An Efficient Genetic Algorithm Approach to an Intelligent Decision Support System for Water Distribution Networks.”, Proc. of Hydroinformatics 2000, Iowa, July 24-28, USA.

[7]    Simpson A. R., Dandy G. C. and Murphy L. J. (1994). “Genetic algorithms compared to other techniques for pipe optimization.” J. of Water Resource Planning and Management, ASCE, Vol. 120, No. 4, 423-443.

Fig. 1    Layout of two-reservoir network

Fig. 2    Convergence rate of discrete genetic algorithm optimization for the least cost design solution $1.7145 million ¾ two-reservoir network