A two-phase network design heuristic for minimum cost water distribution systems under a reliability constraint

This paper presents a two-phase design and optimization procedure for constructing a pipe network water distribution system having a built-in degree of reliability. The first phase is comprised of an algorithm called TREESEARCH which iteratively constructs a tree pipe network. Starting with a shortest-path based tree, the procedure employs a linear programming subproblem to systematically modify this tree by adding and deleting one link at a time, with the aim of reducing the cost of the network while satisfying the flow continuity, energy balance, and pressure head requirement constraints. The second phase of the algorithm, called REDUNDANCY, is concerned with the issue of reliability. In this phase, the tree network constructed by the algorithm TREESEARCH is augmented through the addition of links so that there are at least two arc-disjoint paths from each source node to every demand node it serves. This augmentation is performed through the use of a set covering problem which recommends the links to be added, and