A multi-step genetic algorithm model for ensuring cost-effectiveness and adequate water pressure in a trunk/limb mains pipe system

Water supply is of crucial importance for sustainability of human life and economic development. In countries with growing populations, water utilities face enormous challenges to meet water demand both in quantity and quality (Mugabi 2007). When the water demand grows, the pipes already installed are no longer able to supply sufficient water and need to be replaced with larger diameter pipes, or new pipelines need to be installed. Water utilities must adapt to the conditions quickly by preparing adequate water distribution network (WDN) facilities (Sargaonkar 2012). Developing countries are confronted by the problem of how to optimize the distribution network while at the same time meeting increasing water demand (Vairavamoorthy 2008). Conversely, genetic algorithms (GAs) have been used successfully in optimal design of WDNs across the globe. The main approach taken has been minimum cost, subject to hydraulic constraints. In contrast to traditional methods where design of WDNs has been based on the experience of planners or engineers, a GA searches the optimal solution for the network based on natural selection and the mechanism of biological background (Goldberg 1953). Simpson (1994) presents a methodology for optimizing pipe networks using GAs and investigates a three-operator GA, comprising reproduction, crossover, and mutation. Frey (1996) applied GAs to minimize capital and/or life-cycle costs for design and operation of a WDN. Furthermore, Savic & Walters (1997) described the development of a computer GA model to the problem of least-cost design of WDNs. Their studies show that the GA is effective in finding global optimal or near-optimal solutions requiring only a relatively small number of evaluations. Recently, GAs have been modified according to the objective and the application. Eusuff & Lansey (2003) introduced a shuffled frog-leaping algorithm for solving discrete optimization problems. Prasad & Park (2004) presented a multi-objective GA approach to the design of a WDN. The objectives considered are minimization of the network cost and maximization of a reliability measure. Babayan (2005) proposed a methodology for the least-cost design of WDNs under uncertain demand. Kadu (2008) optimized WDNs using a modified GA, proposing how to reduce space of the diameter option using a critical path method. In undertaking the appropriate reinforcement of water pipelines in a developing country, ‘selection and concentration’ strategy is needed from the following two standpoints. One is to satisfy the hydraulic constraints of the WDN dealing with future water demand. The other is to reduce life-cycle costs. This study intends to show that the trunk/limb mains reinforced (TMR) concept is effective when making possible ‘selection and concentration’ of the reinforcement process. Achieving the objective of the concept, a multi-step GA is developed to determine not only the most effective pipe diameter but also proper selection of pipeline mains. In other words, the GA in this paper needs to select the most effective pipeline mains to be rehabilitated and discard others while at the same time search for the optimal diameter solution for the pipeline to ensure cost-effectiveness and adequate water pressure at each node. The first, hybrid genetic algorithm I (HGA I), is applied, considering the rapid growth of the future water demand. The second, HGA II, focuses on selection of trunk/limb mains pipelines. A cost analysis is then performed to clarify effectiveness of the concept.

The study was conducted in Kota Makassar, capital of South Sulawesi province in the eastern part of the Republic of Indonesia. The area is developing rapidly as a center of administration, industry, commerce, and education in east Indonesia. Its population in 2010 was 1,339,374 people, with an annual growth rate of 2.2% (2004–2010), much higher than Indonesia's 1.6% national average growth rate (BPS-Statistic Indonesia 2011). The water supply system in this area is serviced by Perusahaan Daerah Air Minum (PDAM) Makassar (water utility). There are numerous problems faced by the PDAM in the water distribution system (Bakri 2012a). Due to the rapid increase in customers, the alignment of distribution pipelines is inadequate. Many people, particularly in the northern and western parts of the city, suffer from chronic water shortage and low water pressure (0–0.5 kg/cm²). They tend to have suction pumps on their premises to supplement the pressure. The inadequate water pressure results from the existence of many pipes with improper diameters in the network. In the ideal water distribution system, pipes are laid out suitably with trunk mains having the largest diameter, followed by limb mains and then service mains. In the case of the distribution network in the study area, however, such a clear distinction is not built into the network design concept. The problem is that trunk and limb mains do not have a large enough diameter. The hydraulic problem arising from this situation is the large friction head loss in pipes at the upstream portion, so that sufficient water pressure cannot be obtained in downstream pipes. The other problem is the high rate of non-revenue water (NRW), 45% in 2010. The high rate of NRW may be attributed to the old pipe mains. Many old pipes in the central area installed in the 1920s, more than 90 years ago, are still in use. In addition, to reduce replacement costs, the water authority installed smaller mains of the PVC pipes in the newly developing areas, which at 100–150 mm, are not sufficient to achieve a stable and continuous water supply. The PDAM, although recognizing the urgent need for rehabilitation and reinforcement of the existing distribution pipe network, is not capable of allocating sufficient funds. Thus, in undertaking the rehabilitation of water pipelines in the study area, replacement or reinforcement of the existing distribution pipe network at minimum cost and to meet future water demand increases are considered essential for overcoming all of the above problems. This study intends to focus on analysis of the Somba Opu Distribution (SOD) system, one of the two major distribution systems in Kota Makassar. Its service area includes the city center (commerce and administration) and newly developing residential areas. Figures 1 and 2 show the existing pipe reticulation of the SOD system and its node demand, respectively. Water demand in 2090 will be applied to analyze the effectiveness of the rehabilitation and expansion plan worked out under the concept.

It is particularly important that the rehabilitation and expansion of pipeline for the study area meet future water demand and ensure cost-effectiveness, thus, it will be necessary to select trunk/limb mains pipes and at the same time change their inappropriate pipe diameters. Replacement of all pipe mains for rehabilitation and expansion may be an effective way and requires sufficient budget for rehabilitation. Conversely, proper selection of pipeline and optimally routed trunk/limb mains pipes of the existing distribution pipe network may be more effective than, and hydraulically preferable to, replacement of all mains for rehabilitation. Existing small diameter mains may be no longer practical as mains pipes, and may be used as service mains or replaced by larger mains. To attain this goal, we propose the concept of TMR (Bakri 2012a). This concept emphasizes selective reinforcement of trunk/limb mains in the network, and therefore requires proper selection of pipelines and trunk/limb mains pipe diameters. It is necessary first to identify trunk/limb mains on the network and then to seek a solution for proper diameter of mains to improve the overall network (Bakri 2013). To find the optimal solution from the many possible alternatives for pipeline mains in a network, we applied a multi-step GA. The next step, rehabilitation or reinforcement of the pipelines, is then carried out selectively based on results of the GA. Figure 3 shows a conceptual pipeline alignment of TMR pipe systems.

To facilitate the optimization problem for meeting the objective function expressed in Equation (1) and subject to the hydraulic constraints, this paper developed an HGA model. This model evaluates both of the optimization problems, cost-effectiveness and hydraulic analysis, simultaneously. Incorporation of pipe network analysis into a GA has two advantages: first, it supports a combination of discrete decision variables and non-linear objective functions for the optimization problem; second, parallel calculation of the GA and hydraulic analysis establishes alternative planning that can be verified from the engineering perspective (Arai 2009).

A binary number is generated as the initial population of the GA. This study takes a 2-bit binary number such as 0 and 1. Diameter pipe candidates D_i for each pipeline i based on the present diameter, with 16 pipe diameter options for the diameter changing stage, are shown in Table 1. Search space is the most important element for controlling efficiency and effectiveness of a GA (Kadu 2008). Since the binary numbers consist of 2 bits, there is a maximum of four diameter options. A multi-step GA was developed for finding the most effective solution in the study area. The first is HGA I, which aims to address increasing water demand; thus, the pipe diameter options may be equal or larger than the present diameter. The second is HGA II, with the main objective of selecting trunk/limb pipelines for rehabilitation or reinforcement. It is used to select some trunk/limb mains and discard others. At the same time, this HGA is used to search for the optimal diameter solution for the pipeline of trunk/limb mains. To find the objectives, setting a minimum diameter is one of the options of this HGA. If HGA II selects that option for a pipe, the pipe will be discarded for the next process. In this study, 150 mm is set as the minimum diameter option. Since the number of pipes will end up being reduced as some pipes are discarded, it is necessary to include a larger diameter than those existing as one of the diameter options. Table 2 shows diameter setting options and binary numbers of HGA I and II.

Fitness function and penalty method are used to evaluate merits and demerits of each generated individual (Castillo & Gonzalez 1998). Achievement of the highest fitness value (FV) is the objective of this model. FV is calculated as the inverse of the total network cost, while the total cost (T_c) is taken as the sum of the cost of the pipe in the network. If an individual does not satisfy the objective function of hydraulic as minimum pressure H^min at each node j and maximum velocity V^max at each pipe i, a penalty cost will be assigned for the individual by multiplying its FV by 0.1. For achieving sufficient water pressure at all customer taps, the head requirement at a node is fixed at a minimum 17 m, while maximum velocity at all pipes is fixed at 3.0 m/s.

The initial population and generation reproduce new members of the generation by selection processes. The processes will repeat to generate the best generation. Population and generation of HGA I in this study are set at 2,000 and 3,000, respectively, while that of HGA II are 1,300 and 3,000. The process selection involves crossover and mutation as a standard GA (Simpson 1994). Generally, crossover probability (P_c) is distributed in the range 0.0–1.0 (Simpson 1994), while mutation probability (P_m) is distributed very low at 0.01–0.1 (Savic & Walters 1997). In this study, crossover and mutation are set at 0.8 and 0.03, respectively.

To clarify the cost-effectiveness of this concept, this study presents a cost analysis. In the analysis, overall costs of the alternatives include those for installation and leak repair required up to the year 2090 (Bakri 2012b). To minimize the effects of price escalation, the present study assumes a social discount rate of 0% in the future.

Figure 5 shows alterations to the network. Finding the optimal solution requires six iterations of HGA II. In order to verify that hydraulic constraint was meeting the objective function, we conducted hydraulic analysis to determine the water pressure at each node and velocity at each pipe as given in Figure 6. From the figure, we can clarify that the diameter of the existing network is not sufficient to cope with increasing water demand. The existing distribution pipe network needs to be rehabilitated and reinforced for meeting the water demand. With the solution proposed by HGA I (Figure 5(b)) and HGA II (Figure 5(h)), the nodal water pressures of both methods match the pressure requirements standards and are nearly equal at each node as shown in Figure 6(a). Differences are seen between the methods in nodes 3, 12, 22, 23, 24, 26, 31, 36, 37, 38, 39, 40, 41, 42, and 43 where HGA I is higher than HGA II, while in nodes 4, 5, 13, 14, 27, 29, 30, 33, and 34, HGA II is higher than HGA I. However, we can see that the differences are not significantly large. These models can therefore be seen as a means of equalizing water pressure at each node in a WDN. As well as pressure, velocity at each pipe of HGA I and II also matches the velocity requirements standards, as envisaged in Figure 6(b). Judging from the HGA I and II process, obtaining the solution proposed by HGA would be far more difficult and time-consuming using the common method of network design with a number solution space. The application is uncomplicated and does not require a high degree of mathematical sophistication to understand its mechanism (Savic & Walters 1997).

Figure 7 indicates that although water demand increases three-fold, to cope with the increase the water authority does not need to replace the overall pipeline in the network with larger diameter than that existing. Out of 77 nodes, the solution selects 43 trunk/limb mains pipes and discards 34 others, as shown in Figure 5(h). The diameters of four pipes are downsized by 50–150 mm, pipes 8, 27, 75, and 31, and three pipes retain their existing diameters, namely, pipes 10, 12, and 66. Pipeline rehabilitation/reinforcement is therefore concentrated on the remaining 36 pipes, out of which, 17 pipe numbers, pipes 16, 18, 21, 23, 37, 49, 2, 33, 1, 3, 5, 24, 29, 34, 36, 52, and 57 are upsized to a diameter of 200–300 mm from that existing, and 19 pipes, including pipes 7, 9, 42, 44, 48, 50, 58, 69, 11, 13, 25, 40, 71, 53,54, 62, 64, 76, and 77 are also upsized to diameters of 50–150 mm.

Figure 8 shows the material, civil work, and leakage repair cost required for pipe replacement according to pipe diameter, number, and length of HGA I and HGA II methodologies. Total HGA I pipe is 77 pipes with 77 km pipe length while HGA II is 43 pipes and 42 km, respectively. HGA I represents replacement of all mains for rehabilitation while HGA II is in line with the TMR system, namely, selective reinforcement of trunk/limb mains and installation of an integrated pipeline. The installation and repair costs with the HGA II solution are more cost-effective than HGA I, and the rehabilitation plan devised using HGA II was able to reduce total cost by approximately 11% in comparison with HGA I. Although, in some cases, installation by parallel pipe is more cost-effective than one pipe, the total cost of each viewpoint shows that the combination of one pipe alignment with selective reinforcement of trunk/limb mains is a more effective way, not only in cost and hydraulics but also in reducing pipeline numbers and length of main pipes, and the simplified network contributes to substantial reduction of labor, procurement, and operation and maintenance costs. The result, as proposed by HGA II, indicates that proper selection of pipeline of trunk/limb mains and installation of an integrated pipeline is effective for ensuring cost-effectiveness and water pressure in the network.

This paper focuses on WDNs in developing countries, proposes how to rehabilitate and expand the distribution network thus meeting future water demand and also ensuring cost-effectiveness. Replacement or reinforcement of the properly selected existing distribution mains is more effective than, and hydraulically preferable to, replacement of all mains for rehabilitation. Conversely, GA methodology has been used successfully for the optimal design of the pipe diameter of a distribution network. Use of a GA enables the complex design of WDNs to be handled while presenting a minimum cost solution and accounting for hydraulic constraints. Achieving the objective of the concept, the GA in this paper was developed not only for proper selection of pipe diameter but also proper selection of pipeline mains. HGA I addresses increasing water demand, while HGA II focuses on selection of trunk/limb mains pipelines. Due to the weak financial condition and the expensive rehabilitation of the distribution network, the rehabilitation process of WDNs in the study area should be implemented accurately and carefully. Conversely, low water pressure caused by the high NRW and inadequate alignment of distribution pipelines due to a rapid increase in customers should be addressed as soon as possible to improve the water supply conditions. The application of this method helps PDAM Makassar in planning rehabilitation and expansion of WDNs. The water authority can easily clarify which are the optimal pipelines and diameter of trunk/limb mains pipes in the network, and then, replacement or expansion can be concentrated on the pipelines that will improve the overall network, without replacing all pipe mains. Selection and concentration of trunk/limb mains pipe selects 43 trunk/limb mains pipes and discards 34 others. The water pressure at each node of this solution (HGA II) is nearly equal to replacement of all mains for rehabilitation (HGA I), nevertheless, the installation and repair costs with the HGA II solution are more cost-effective than HGA I. Reducing the number of pipes as proposed by HGA II also contributes to simplifying the network, which can achieve a substantial reduction in labor, procurement, repair, and operation and maintenance costs and is easier to control water losses. Briefly, meeting future water demand, achieving cost-effectiveness, attaining simplicity of the pipe network, and retaining sufficient water pressure can be achieved at the same time by application of this method. This study is a preliminary step for rehabilitation and expansion of WDNs in the study area. It reveals how to select the main pipelines and the diameters that are most important from hydraulic and economic viewpoints assuming use of DCIP as pipe material. In reality, there are many kinds of material pipe, and since there are upper limits on the pipeline upgrading budgets in each project period, it is not possible to upgrade all the main pipelines in a single period. However, it is necessary to consider budget constraints of the water authority for rehabilitation and expansion of the WDN and the combination of diameter and other pipe materials in each project period for reducing life cycle in future studies. In addition, as the current study estimates pipe leakage frequency by assumption will be constant with time per year and kilometer, it is necessary to look into the details of leakage frequency according to pipe aging, material, and diameter in the study area. Greater insight into sufficiently detailed data of leakage frequency may probably ensure the effectiveness of the concept, contributing to substantial reduction of leakage repair costs.