Hybrid Genetic Algorithm and Linear Programming Method for Least-Cost Design of Water Distribution Systems

The problems involved in the optimal design of water distribution networks belong to a class of large combinatorial optimization problems. Various heuristic and deterministic algorithms have been developed in the past two decades for solving optimization problems and applied to the design of water distribution systems. Nevertheless, there is still some uncertainty about finding a generally trustworthy method that can consistently find solutions which are really close to the global optimum of this problem. The paper proposes a combined genetic algorithm (GA) and linear programming (LP) method, named GALP for solving water distribution system design problems. It was investigated that the proposed method provides results that are more stable in terms of closeness to a global minimum. The main idea is that linear programming is more dependable than heuristic methods in finding the global optimum, but because it is suitable only for solving branched networks, the GA method is used in the proposed algorithm for decomposing a complex looped network into a group of branched networks. Linear programming is then applied for optimizing every branch network produced by GA from the original looped network. The proposed method was tested on three benchmark least-cost design problems and compared with other methods; the results suggest that the GALP consistently provides better solutions. The method is intended for use in the design and rehabilitation of drinking water systems and pressurized irrigation systems as well. Copyright Springer Science+Business Media B.V. 2010