The sewer network design problem consists of determining both the layout and the hydraulic design of the system. This paper aims to find an optimal hydraulic design for a specific layout consisting of a series of pipes. An optimal hydraulic design of a series of pipes is that which satisfies all the hydraulic, commercial, and construction constraints, while minimizing the construction costs. The present paper proposes a graph modeling framework in which the result of a shortest path problem coincides with the hydraulic design, and the underlying graph models the diameter and slope of each pipe in the series. To assess the performance of the methodology, several numerical examples are presented varying the pipe material, the topography, and the number of pipes in the series.

## INTRODUCTION

The sewer network design problem consists of determining both the layout and the hydraulic design of the system. The layout of the network is defined by the initial pipes and the flow direction of each pipe. The hydraulic design determines the diameter and the slope of the pipe to be installed at each link of the sewer network, where a link refers to the span between two manholes. Moreover, pipe diameters are chosen from a discrete set of commercial diameters and the slope of a pipe is related to the elevation gap of its extremes. In this paper, the layout is assumed to be a series of pipes that might belong to a complete sewer network. The challenge is to find a minimum-cost design that accomplishes all hydraulic and construction constraints established by the corresponding national legislation. In the following, it is assumed that the design flow rate for each pipe is known beforehand. The design flow rate for a pipe corresponds to the inflow at the upstream manhole of the pipe plus the flow rate coming from the upstream pipes. The input information of the problem includes topographic information (horizontal length of the links and ground elevation of the manholes), commercial characteristics (available pipe materials and diameters), physical characteristics of the fluid (water density and viscosity), and hydraulic characteristics (flow resistance formula and pipe's internal roughness). In this work, the hydraulic constraints that must be fulfilled are: a minimum pipe diameter, a maximum filling ratio, a minimum wall shear stress, a minimum and maximum velocity, and a minimum and maximum slope.

Sewer network design involves two different problems (the layout definition and the hydraulic design), and due to their complexity it is not common practice to solve them simultaneously. Available solution strategies in the literature propose solving both problems sequentially, but the hydraulic design problem has received more attention through both exact and heuristic methodologies.

Several exact approaches have been proposed for both problems. Haith (1966) used dynamic programming (DP) to obtain an optimal design of a series of pipes by considering a single pipeline divided into different segments, each with constant inflow and cost parameters. Decision variables in the model include the invert elevation at the end of each pipe and its diameter. However, this methodology had computational limitations due to the technology at that time. Kulkarni & Khanna (1985) also used a DP approach to design a minimum-cost gravity-pumped sewer network using a modification of the Hazen–Williams equation. The authors simplified the design problem based on the concept of cost-effective feasible groupings at junctions. This DP approach consists of two parts: the first one fixes control variables associated with each link, and the second one calculates the hydraulic and cost statements. DP methodologies often suffer from the well-known curse of dimensionality, which limits their ability to solve large-scale instances. Li & Matthew (1990) used a nonlinear programing model to establish both topographic and hydraulic factors such as flow rate, size, and gradient of pipes. In this methodology, the authors divided the problem into two submodules. Given a layout, the first submodule optimizes the size and gradient of the pipes and the location of on-line pumping stations. The second submodule determines the flow rate using a searching direction method that looks for pipes where the flow rate can be modified to decrease the value of the objective function. To set the initial layout, Dijkstra's algorithm is used to create a shortest path-spanning tree, with the links weight being the product between its length and its average ground elevation. More recently, Swamee & Sharma (2013) used linear programming (LP) to obtain an optimal design for a series of pipes without linearizing the objective function or the constraints. To do so, lengths and diameters of each pipe are fixed to the commercially available diameters. The authors tested their methodology over a series of five pipes and obtained an optimal (yet simplified) design.

Heuristic approaches have also been proposed for this design problem. Holland (1966) used a general optimization routine to design a sewer network. This optimization routine performs a random search that works with continuous diameters, which are then rounded to the closest commercial diameter available. Elimam *et al.* (1989) used an LP-based heuristic approach, which relies on a piecewise linearization of the nonlinear terms such as the cost and some hydraulic constraints. As a result, continuous diameters are obtained and rounded to the nearest commercial diameter in order to satisfy all the hydraulic constraints. This methodology was evaluated over a network with 896 manholes, with a reduced diameter range from 0.2 to 0.4 meters (), and additional simplifications. The most popular method, used by numerous authors, is genetic algorithms (GAs). Haghighi & Bakhshipour (2012) and Palumbo *et al.* (2014) used GAs to design urban drainage networks, deciding the size and ground elevation of the pipes. Cimorelli *et al.* (2013) combined a GA with hydrologic and hydraulic models that evaluate the water depth and water discharge through the network. Cozzolino *et al.* (2015) used a GA combined with a steady and uniform flow hydraulic module to achieve a minimum-cost design of drainage networks. This methodology was tested over networks with nine and 37 pipes, conveying to a near-optimal solution in around 1,700 generations of the GA.

Another line of heuristic schemes combines GA with other approaches. Cisty (2010) proposed a hybrid between GA and LP; Pan & Kao (2009) mixed GA with quadratic programming; and Haghighi *et al.* (2011) used GA with integer programing applied to water distribution networks. Afshar (2012) developed a rebirthing GA that performs a first quick design using a standard GA, narrowing the search space around the best solutions, and then creating a new random population that is evaluated over the narrowed search space in order to find near-optimal solutions quickly. This methodology reduces the sensitivity of the GA to the number of individuals in its population. Cimorelli *et al.* (2014) used an enhanced genetic algorithm to find a near-optimal design of rural drainage networks while making a simultaneous evaluation of the design discharges that vary due to climatic and hydrologic characteristics. Sanchez *et al.* (2014) combined a cellular automata (CA) model of urban growth, the evolutionary algorithm non-dominated sorting genetic algorithm-II, and a hydraulic simulator (Storm Water Management Model, SWMM) to design the pipes for future expansions of an existing sewer network. This multi-objective algorithm provides a set of non-dominated solutions, and the one that has the cheapest design cost and produces no flooding is ultimately selected. Other heuristic methods such as ant colony optimization algorithm (Afshar 2010; Moeini & Afshar 2012), simulated annealing (Sousa *et al.* 2002; Yeh *et al.* 2011), and Tabu Search (Yeh *et al.* 2011; Haghighi & Bakhshipour 2015) have also been used in sewer systems design.

Additional problems, closely related to the sewer network design, have been addressed in the literature. Fu *et al.* (2010) used artificial neural networks to describe urban wastewater systems and to predict combined sewer overflows discharges and treatment effluent characteristics. Likewise, Austin *et al.* (2014) proposed a CA model to simulate sewer flow as figurative water blocks with a finite volume. Additionally, Mortazavi-Naeini *et al.* (2015) developed efficient multi-objective ant colony optimization-I in order to solve operational and infrastructure problems of urban water resources. Cimorelli *et al.* (2015) used a GA approach to find a near-optimal location and size of detention tanks in urban drainage networks. All of these aspects are related and relevant for sewer systems design, and are suitable for further extensions in more complex and broad designs.

In summary, available exact methods for the design problem often require multiple assumptions and the simplification of components. Additionally, they do not always scale for large instances. Heuristic approaches are more flexible and scalable, but do not offer an optimal (exact) solution. This paper proposes an exact, exhaustive, and flexible framework to find the cost-optimal design of a series of sewer pipes using a DP-based optimization engine. The design problem is modeled as a shortest path problem (cf., Bellman 1958; Ahuja *et al.* 1993), where the underlying graph considers every feasible combination of diameter and slope for each pipe in the series. Thus, a shortest path on the graph encodes an optimal hydraulic design decision. Hydraulic aspects that guarantee the proper operation of the system are taken into account in the construction of the underlying graph, and additional side constraints of the system can be addressed in the proposed methodology. Finally, different cost functions can be flexibly modeled in order to accurately estimate the construction cost according to the country where the sewer network is located.

The rest of the paper is organized as follows: the following section presents the proposed methodology. Then, the solution strategy is explained in detail. Finally, several numerical experiments over theoretical series of pipes are presented, followed by the last section that concludes the paper and outlines future research.

## METHODOLOGY

### The shortest path problem

*shortest path problem*is defined over a graph , where is a set of nodes, is a set of arcs, and is the cost (e.g., distance, time, etc.) of traversing arc . The objective is to find a minimum-cost path (e.g., shortest distance or minimum travel time) from a specific initial node to a destination node (Bellman 1958). Main applications of this optimization model arise in transportation and routing problems. Formally, the shortest path problem is defined as follows: where is a binary variable valued as one if the arc belongs to the shortest path and valued at zero otherwise. The objective function (1) minimizes the costs of the path. This is subject to Equation (2) that establishes the flow balance constraints that guarantee the structural properties of a path, and Equation (3) that restricts the variables to be binary-valued.

*et al.*1993). In this work, the Bellman–Ford algorithm is used due to the particular structure of the underlying graph, i.e., a directed-acyclic graph that is ordered in a topological fashion ( for every arc ). This label-correcting method starts setting a cumulative cost (label) for the initial node and for the remaining nodes of the graph. Then, each node is evaluated by scanning every outgoing arc . If , then the label for is updated with the new minimum cumulative cost and its parent (predecessor) node . When all the nodes of the graph are evaluated, the cost labels are optimal (Ahuja

*et al.*1993).

### Graph modeling

To build the underlying graph of the shortest path problem, several parameters are utilized as input data. Let be the set of manholes comprised in the series of pipes, where manhole is the starting point, manhole is the discharge point of the sewer system, and and are the inflow and ground elevation at manhole , respectively. Due to the sequential structure of the sewer system, the design flow rate for a pipe between manholes and is precomputed as . Additionally, let be the set of commercial diameters available and *l* be the length of each pipe in the series.

In the underlying graph that models the series of pipes, each manhole is represented by a subset of nodes and each arc connects two nodes of consecutive manholes to represent a pipe with a particular diameter and slope. Formally, is the set of all nodes in the graph, and is the subset of nodes arranged at manhole . Each node in comprises two attributes: an elevation , which represents the invert elevation of the pipe at manhole , and a commercial diameter , where represents the diameter of an incoming pipe to manhole that starts at manhole . Figure 1 shows an example of the subset for a given manhole

*V*is the excavation volume required for placing the pipe (Navarro 2009). It is worth noting that without affecting the methodology, this equation can be replaced by any other equation or value that better fits the construction costs of the country in which the system is going to be constructed. Also, the equation could include the costs of manholes and pumping stations, as proposed by Marchionni

*et al.*(2014).

Basic hydraulic constraints are taken into account as the graph is built. Feasible arcs between nodes must satisfy that to prevent obstructions in the system. Additionally, each arc satisfies that to avoid adverse slopes. For manhole there is only one possible placement at the upper excavation limit. Also, for the first pipe of the series the diameter of the upstream node must match the diameter of the downstream node.

It is noteworthy that the solution space of the problem is very large due to the exponential growth of design alternatives (i.e., hydraulically feasible paths from the first to the last manhole). However, state-of-the-art algorithms that solve the shortest path problem manage networks with several millions of nodes and arcs (Demetrescu *et al.* 2006). Moreover, due to the particular acyclic-forward-directed structure of the graph, a specialized version of the shortest path algorithm discussed before is used to accelerate the solution strategy. This specialized algorithm is discussed in detail in the solution strategy section.

*V*. The latter is computed using the elevation values of the corresponding nodes and . Pipes are joined by their invert elevation in order to avoid hydraulic jumps into the system that might cause erosion of sewer materials and release gases (Butler & Davies 2011).

### Hydraulic constraints

The graph presented in Figure 3 takes into account basic hydraulic constraints that prohibit decreasing diameters and adverse slopes. However, there is also a set of hydraulic constraints that are usually considered in the literature (and legislation) of sewer systems design that must be addressed. In this work, the hydraulic design uses the Darcy–Weisbach resistance equation (Brown 2002); nonetheless, the methodology could use any other resistance equation such as Manning's equation.

Hydraulic constraints ensure a proper operation of the sewer networks. They establish bounds for the constraints exhibited in Table 1. The minimum allowed diameter prevents obstructions in the system. The maximum filling ratio precludes surcharge problems and ensures ventilation in the system to avoid environmental difficulties. The minimum wall shear stress and velocity ensure a cleaning process inside the pipes; while the maximum velocity prevents problems such as erosion, cavitation, air entrapment, hydraulic jumps, among others. The minimum and maximum slope constraints are limited by the minimum and maximum velocities, respectively.

Constraint | Value | Condition |
---|---|---|

1 Minimum diameter | 200 mm | Always |

2 Maximum filling ratio | 0.7 | |

0.8 | 0.7 ≤ ≤ 1.5 | |

0.85 | Other cases | |

3 Minimum wall shear stress | 2 | |

4 Minimum velocity | 0.75 | |

5 Maximum velocity | 5 | > 0.0001 |

10 | < 0.0001 | |

6 Minimum slope | The one for which the minimum velocity and shear stress are obtained | |

7 Maximum slope | The one for which the maximum velocity is obtained |

Constraint | Value | Condition |
---|---|---|

1 Minimum diameter | 200 mm | Always |

2 Maximum filling ratio | 0.7 | |

0.8 | 0.7 ≤ ≤ 1.5 | |

0.85 | Other cases | |

3 Minimum wall shear stress | 2 | |

4 Minimum velocity | 0.75 | |

5 Maximum velocity | 5 | > 0.0001 |

10 | < 0.0001 | |

6 Minimum slope | The one for which the minimum velocity and shear stress are obtained | |

7 Maximum slope | The one for which the maximum velocity is obtained |

Finally, there is a constraint that bounds the depth at which pipes can be placed. These allowed depths are measured from the ground to the crown elevation of the pipes. The minimum depth () protects the structure of the pipes and ensures that domestic discharges drain by gravity. The maximum depth () limits axial loads over the pipes. These excavation bounds are presented in Table 2, according to RAS (2000).

Road classification | h_{min} (m) | h_{max} (m) |
---|---|---|

Pedestrian or green area | 0.75 | 5.0 |

Vehicular | 1.2 | 5.0 |

Road classification | h_{min} (m) | h_{max} (m) |
---|---|---|

Pedestrian or green area | 0.75 | 5.0 |

Vehicular | 1.2 | 5.0 |

### Solution strategy

This section presents the solution strategy as a three-step procedure based on the graph modeling and the shortest path algorithm presented above. The first step consists in generating the nodes for each manhole. In the second step, the graph that represents all the possible solutions is built with only feasible arcs while Bellman–Ford algorithm is executed simultaneously. The third step extracts the optimal solution from the graph.

*D*, the set of manholes

*P*, and the ground elevation of each manhole. Lines 1–19 generate the nodes for each manhole . Lines 2 and 3 set the upper and lower excavation bounds. Lines 4–8 create the nodes for the first manhole (one node per diameter in ), and are placed at the upper limit. For the other manholes, the node generation process is presented in lines 9–18. In these manholes there is one node for each combination of diameter and elevation . Line 10 shows the propagation over all diameters in

*D*and line 11 sets the starting elevation to the first feasible invert elevation at which a pipe could reach manhole . This process continues until reaches the lower limit ( below the ground level), which is evaluated in line 12. This procedure generates as many nodes at each elevation as available diameters. The number of evaluated elevations depends on the elevation change used (). For example, if and the pipe is placed below a vehicular road (see Table 2), there are 380 elevations to evaluate in a range of (from to above the ground level). Similarly, if , there are 38 elevations to evaluate. Therefore, there is a tradeoff between the precision of the design versus the computational effort to create the graph and solve the corresponding shortest path problem.

*Q*for the pipe represented by the arc (see Algorithm 4). Line 10 verifies that the computed flow rate is at least the design flow rate of the current link (). Line 11 calculates the normal flow depth required to (exactly) meet the design flow rate of the link (see Algorithm 5). Finally, the label correcting process continues as shown in lines 12–14 if the arc satisfies all the hydraulic constraints presented in Table 1 and validated in Algorithm 6. Line 13 sets the new minimum cumulative cost of node and line 14 saves node as the parent node of the former.

Note that the cumulative weight of all the hydraulic constraints validated in Algorithm 3 ultimately defines whether the arc is feasible or not. Additionally, the optimal path (optimal design) only considers feasible arcs. Notice also that the algorithm applies the Bellman–Ford verification at line 8, before the hydraulic verifications. Since the arc cost is much easier to compute than the validation of hydraulic feasibility, it is worth verifying first the labels of the shortest path algorithm because it might save several hydraulic verifications of suboptimal solutions.

Algorithm 4 presents the method that calculates the flow rate *Q* transported through the arc . Lines 1–4 set the maximum flow depth according to the maximum filling ratio (85% or 70% depending on the pipe diameter). Lines 5–8 calculate the geometric properties that describe a pipe with partial flow: central angle , flow area *A*, wetted perimeter *P*, and hydraulic radius *R*. Finally, lines 9–11 calculate the following hydraulic properties: wall shear stress, velocity, and flow rate. In this case, the flow rate represents the maximum capacity of the pipe.

After verifying that the maximum flow is greater than the design flow rate in Algorithm 3 (line 10), the exact normal flow depth is calculated in order to transport exactly the design flow rate. Algorithm 5 presents a binary search procedure to find the exact normal flow depth of a particular pipe with a tolerance of . Line 1 sets the lower bound for the flow depth to 0, and line 2 sets the upper bound to . Line 3 sets the new normal flow depth as the average between both bounds. Lines 4–18 define the binary search with the corresponding tolerance. In lines 5–11, all the geometric and hydraulic properties are recalculated with the new normal flow depth . Lines 12–16 set a new search range for the normal flow depth that is adjusted according to the calculated flow rate *Q* and the design flow rate . Finally, line 17 sets a new normal flow depth that is either used in the next step of the search or accepted by the algorithm if the tolerance is met.

Once the normal depth and all the hydraulic properties are updated, the hydraulic constraints established in Table 1 must be verified, as shown in Algorithm 6. A Boolean flag is used in line 1 to verify that a pipe satisfies all the hydraulic constraints. If there is at least one constraint that is not satisfied, the arc that represents that pipe is considered infeasible and is discarded for the design. Lines 2 and 4 verify the maximum velocity for rough and smooth materials, respectively. The minimum wall shear stress and minimum velocity are evaluated in lines 6 and 8. Finally, line 10 verifies that the filling ratio is below 80% when having critical flow.

## NUMERICAL EXAMPLES

### Experiment setup

The algorithm is tested over 16 theoretical instances that are generated varying the number of pipes in the series (5, 10, 15, and 20), using two different materials (concrete and PVC) and two different topographies (steep and flat ground). The algorithm is coded in Java and compiled using Eclipse SDK version 4.2.1. The experiments are performed on a computer with an Intel Core i7-3770 CPU @3.4 GHz with 8GB of RAM allocated to the memory heap size of the Java Virtual Machine on Windows 7. Computational time to solve the design problem measures the three steps of the proposed methodology, and this performance metric is reported individually for each instance.

Table 3 presents the inflow and ground elevation for each of the 21 manholes conforming the series of pipes (including manhole ). Table 4 presents the design flow rate , the length *l*, and the corresponding upstream and downstream ( manholes for each of the 20 pipes of the series. The first six, 11, and 16 manholes of the dataset are used to build smaller experiments with five, 10, and 15 pipes, respectively.

Manhole | [] | ∇_{k} | |
---|---|---|---|

Steep ground [] | Flat ground [] | ||

0 | 0.0246 | 161.5 | 160.6 |

1 | 0.0114 | 160.5 | 160.7 |

2 | 0.0170 | 160.2 | 160.7 |

3 | 0.0230 | 160.2 | 160.7 |

4 | 0.0145 | 160.2 | 160.6 |

5 | 0.0125 | 160.2 | 160.5 |

6 | 0.0336 | 160.2 | 160.5 |

7 | 0.0332 | 159.9 | 160.7 |

8 | 0.0692 | 159.8 | 160.7 |

9 | 0.0246 | 159.8 | 160.9 |

10 | 0.0582 | 159.6 | 160.8 |

11 | 0.1552 | 159.6 | 160.7 |

12 | 0.0372 | 159.6 | 160.7 |

13 | 0.0283 | 159.2 | 160.7 |

14 | 0.0506 | 158.3 | 160.8 |

15 | 0.0360 | 158.2 | 160.6 |

16 | 0.0546 | 158.0 | 160.8 |

17 | 0.0460 | 157.9 | 160.6 |

18 | 0.1190 | 157.9 | 160.7 |

19 | 0.0215 | 157.6 | 160.8 |

20 | – | 157.6 | 160.7 |

Manhole | [] | ∇_{k} | |
---|---|---|---|

Steep ground [] | Flat ground [] | ||

0 | 0.0246 | 161.5 | 160.6 |

1 | 0.0114 | 160.5 | 160.7 |

2 | 0.0170 | 160.2 | 160.7 |

3 | 0.0230 | 160.2 | 160.7 |

4 | 0.0145 | 160.2 | 160.6 |

5 | 0.0125 | 160.2 | 160.5 |

6 | 0.0336 | 160.2 | 160.5 |

7 | 0.0332 | 159.9 | 160.7 |

8 | 0.0692 | 159.8 | 160.7 |

9 | 0.0246 | 159.8 | 160.9 |

10 | 0.0582 | 159.6 | 160.8 |

11 | 0.1552 | 159.6 | 160.7 |

12 | 0.0372 | 159.6 | 160.7 |

13 | 0.0283 | 159.2 | 160.7 |

14 | 0.0506 | 158.3 | 160.8 |

15 | 0.0360 | 158.2 | 160.6 |

16 | 0.0546 | 158.0 | 160.8 |

17 | 0.0460 | 157.9 | 160.6 |

18 | 0.1190 | 157.9 | 160.7 |

19 | 0.0215 | 157.6 | 160.8 |

20 | – | 157.6 | 160.7 |

Pipe | Manhole | |||
---|---|---|---|---|

[] | [] | [-] | [-] | |

1 | 0.0246 | 180 | 1 | 2 |

2 | 0.0360 | 121 | 2 | 3 |

3 | 0.0530 | 205 | 3 | 4 |

4 | 0.0760 | 200 | 4 | 5 |

5 | 0.0905 | 123 | 5 | 6 |

6 | 0.1030 | 142 | 6 | 7 |

7 | 0.1366 | 115 | 7 | 8 |

8 | 0.1698 | 135 | 8 | 9 |

9 | 0.2390 | 168 | 9 | 10 |

10 | 0.2636 | 172 | 10 | 11 |

11 | 0.3218 | 120 | 11 | 12 |

12 | 0.4770 | 123 | 12 | 13 |

13 | 0.5142 | 136 | 13 | 14 |

14 | 0.5425 | 196 | 14 | 15 |

15 | 0.5931 | 115 | 15 | 16 |

16 | 0.6291 | 180 | 16 | 17 |

17 | 0.6837 | 121 | 17 | 18 |

18 | 0.7297 | 205 | 18 | 19 |

19 | 0.8487 | 195 | 19 | 20 |

20 | 0.8702 | 200 | 20 | 21 |

Pipe | Manhole | |||
---|---|---|---|---|

[] | [] | [-] | [-] | |

1 | 0.0246 | 180 | 1 | 2 |

2 | 0.0360 | 121 | 2 | 3 |

3 | 0.0530 | 205 | 3 | 4 |

4 | 0.0760 | 200 | 4 | 5 |

5 | 0.0905 | 123 | 5 | 6 |

6 | 0.1030 | 142 | 6 | 7 |

7 | 0.1366 | 115 | 7 | 8 |

8 | 0.1698 | 135 | 8 | 9 |

9 | 0.2390 | 168 | 9 | 10 |

10 | 0.2636 | 172 | 10 | 11 |

11 | 0.3218 | 120 | 11 | 12 |

12 | 0.4770 | 123 | 12 | 13 |

13 | 0.5142 | 136 | 13 | 14 |

14 | 0.5425 | 196 | 14 | 15 |

15 | 0.5931 | 115 | 15 | 16 |

16 | 0.6291 | 180 | 16 | 17 |

17 | 0.6837 | 121 | 17 | 18 |

18 | 0.7297 | 205 | 18 | 19 |

19 | 0.8487 | 195 | 19 | 20 |

20 | 0.8702 | 200 | 20 | 21 |

### Numerical results

Costs achieved in the steep topography are below the costs obtained in the flat topography. This is expected because in a steep topography, ground slopes can reduce the excavation volume required to place the pipes. In a flat topography, instead, pipes always require deeper excavation or increased diameter with every new link. The opposite occurs with the computational time, in which flat topographies are solved faster than the steep ones, and computational time does not grow exponentially, unlike the number of pipes in the series which increases. This occurs because for a long series of pipes the solution space between the excavation limits (i.e., 3.8 *m* in this experiment) is very small, and therefore, thousands of feasible partial alternatives reach the lower excavation limit before reaching the outfall manhole.

Table 5 presents the design of a series of 20 pipes on flat ground using PVC pipes and . The downstream invert elevation of each pipe determines the upstream invert elevation for the next pipe. For the first pipe, the upstream invert elevation corresponds to the ground elevation minus the minimum depth ) and the pipe diameter. In this case, the invert elevation of the first pipe is 159.17 *m*.

Pipe | Invert elevation downstream [] | [-] | [] | [-] | [ | [] | [-] | [] | Cost [$USD] |
---|---|---|---|---|---|---|---|---|---|

1 | 158.873 | 0.002 | 0.250 | 0.628 | 0.757 | 1.137 | 0.659 | 0.025 | $1,395.84 |

2 | 158.720 | 0.001 | 0.350 | 0.497 | 0.753 | 1.081 | 0.651 | 0.036 | $1,182.84 |

3 | 158.507 | 0.001 | 0.350 | 0.700 | 0.757 | 1.056 | 0.511 | 0.054 | $2,384.75 |

4 | 158.301 | 0.001 | 0.400 | 0.690 | 0.822 | 1.195 | 0.525 | 0.076 | $2,678.61 |

5 | 158.130 | 0.001 | 0.400 | 0.697 | 0.968 | 1.608 | 0.612 | 0.091 | $1,522.13 |

6 | 157.893 | 0.002 | 0.500 | 0.689 | 1.237 | 2.416 | 0.707 | 0.179 | $2,233.80 |

7 | 157.717 | 0.002 | 0.500 | 0.695 | 1.179 | 2.212 | 0.669 | 0.172 | $1,914.00 |

8 | 157.532 | 0.001 | 0.530 | 0.689 | 1.154 | 2.108 | 0.641 | 0.187 | $2,675.43 |

9 | 157.334 | 0.001 | 0.600 | 0.691 | 1.148 | 2.040 | 0.598 | 0.239 | $4,234.47 |

10 | 157.147 | 0.001 | 0.700 | 0.841 | 1.239 | 2.271 | 0.482 | 0.428 | $5,224.04 |

11 | 157.024 | 0.001 | 0.700 | 0.807 | 1.200 | 2.142 | 0.494 | 0.399 | $3,352.66 |

12 | 156.913 | 0.001 | 0.800 | 0.813 | 1.217 | 2.147 | 0.464 | 0.532 | $3,936.57 |

13 | 156.797 | 0.001 | 0.800 | 0.807 | 1.184 | 2.042 | 0.456 | 0.514 | $4,656.99 |

14 | 156.627 | 0.001 | 0.800 | 0.850 | 1.192 | 2.068 | 0.426 | 0.543 | $7,808.37 |

15 | 156.539 | 0.001 | 0.900 | 0.841 | 1.197 | 2.043 | 0.411 | 0.683 | $4,508.99 |

16 | 156.396 | 0.001 | 0.900 | 0.818 | 1.226 | 2.133 | 0.437 | 0.683 | $8,163.22 |

17 | 156.303 | 0.001 | 0.900 | 0.833 | 1.208 | 2.078 | 0.420 | 0.684 | $5,057.06 |

18 | 156.122 | 0.001 | 0.900 | 0.827 | 1.298 | 2.369 | 0.456 | 0.730 | $10,080.24 |

19 | 155.897 | 0.001 | 0.900 | 0.831 | 1.502 | 3.098 | 0.524 | 0.849 | $10,096.17 |

20 | 155.654 | 0.001 | 0.900 | 0.828 | 1.545 | 3.263 | 0.542 | 0.870 | $10,986.96 |

Total | | $94,093.14 |

Pipe | Invert elevation downstream [] | [-] | [] | [-] | [ | [] | [-] | [] | Cost [$USD] |
---|---|---|---|---|---|---|---|---|---|

1 | 158.873 | 0.002 | 0.250 | 0.628 | 0.757 | 1.137 | 0.659 | 0.025 | $1,395.84 |

2 | 158.720 | 0.001 | 0.350 | 0.497 | 0.753 | 1.081 | 0.651 | 0.036 | $1,182.84 |

3 | 158.507 | 0.001 | 0.350 | 0.700 | 0.757 | 1.056 | 0.511 | 0.054 | $2,384.75 |

4 | 158.301 | 0.001 | 0.400 | 0.690 | 0.822 | 1.195 | 0.525 | 0.076 | $2,678.61 |

5 | 158.130 | 0.001 | 0.400 | 0.697 | 0.968 | 1.608 | 0.612 | 0.091 | $1,522.13 |

6 | 157.893 | 0.002 | 0.500 | 0.689 | 1.237 | 2.416 | 0.707 | 0.179 | $2,233.80 |

7 | 157.717 | 0.002 | 0.500 | 0.695 | 1.179 | 2.212 | 0.669 | 0.172 | $1,914.00 |

8 | 157.532 | 0.001 | 0.530 | 0.689 | 1.154 | 2.108 | 0.641 | 0.187 | $2,675.43 |

9 | 157.334 | 0.001 | 0.600 | 0.691 | 1.148 | 2.040 | 0.598 | 0.239 | $4,234.47 |

10 | 157.147 | 0.001 | 0.700 | 0.841 | 1.239 | 2.271 | 0.482 | 0.428 | $5,224.04 |

11 | 157.024 | 0.001 | 0.700 | 0.807 | 1.200 | 2.142 | 0.494 | 0.399 | $3,352.66 |

12 | 156.913 | 0.001 | 0.800 | 0.813 | 1.217 | 2.147 | 0.464 | 0.532 | $3,936.57 |

13 | 156.797 | 0.001 | 0.800 | 0.807 | 1.184 | 2.042 | 0.456 | 0.514 | $4,656.99 |

14 | 156.627 | 0.001 | 0.800 | 0.850 | 1.192 | 2.068 | 0.426 | 0.543 | $7,808.37 |

15 | 156.539 | 0.001 | 0.900 | 0.841 | 1.197 | 2.043 | 0.411 | 0.683 | $4,508.99 |

16 | 156.396 | 0.001 | 0.900 | 0.818 | 1.226 | 2.133 | 0.437 | 0.683 | $8,163.22 |

17 | 156.303 | 0.001 | 0.900 | 0.833 | 1.208 | 2.078 | 0.420 | 0.684 | $5,057.06 |

18 | 156.122 | 0.001 | 0.900 | 0.827 | 1.298 | 2.369 | 0.456 | 0.730 | $10,080.24 |

19 | 155.897 | 0.001 | 0.900 | 0.831 | 1.502 | 3.098 | 0.524 | 0.849 | $10,096.17 |

20 | 155.654 | 0.001 | 0.900 | 0.828 | 1.545 | 3.263 | 0.542 | 0.870 | $10,986.96 |

Total | | $94,093.14 |

Table 6 presents the design of another series of 20 pipes on steep ground with the same elevation change and material ( and PVC pipes). In this case, the invert elevation for the first pipe is .

Pipe | Invert elevation downstream [] | s [-] | d [m] | [-] | [ | [] | [-] | [] | Cost [$USD] |
---|---|---|---|---|---|---|---|---|---|

1 | 159.090 | 0.006 | 0.200 | 0.592 | 1.269 | 3.037 | 1.290 | 0.025 | $1,101.43 |

2 | 158.750 | 0.003 | 0.250 | 0.665 | 1.039 | 2.004 | 0.865 | 0.036 | $786.04 |

3 | 158.540 | 0.001 | 0.380 | 0.593 | 0.757 | 1.053 | 0.558 | 0.053 | $2,000.02 |

4 | 158.340 | 0.001 | 0.400 | 0.700 | 0.809 | 1.162 | 0.511 | 0.076 | $2,201.37 |

5 | 158.170 | 0.001 | 0.400 | 0.698 | 0.967 | 1.605 | 0.611 | 0.091 | $1,324.04 |

6 | 157.920 | 0.002 | 0.400 | 0.696 | 1.104 | 2.043 | 0.700 | 0.103 | $1,708.28 |

7 | 157.750 | 0.001 | 0.500 | 0.685 | 1.155 | 2.132 | 0.664 | 0.165 | $1,589.85 |

8 | 157.550 | 0.001 | 0.500 | 0.698 | 1.161 | 2.150 | 0.656 | 0.170 | $1,921.49 |

9 | 157.350 | 0.001 | 0.600 | 0.687 | 1.154 | 2.062 | 0.604 | 0.239 | $3,009.95 |

10 | 157.160 | 0.001 | 0.700 | 0.823 | 1.250 | 2.309 | 0.501 | 0.423 | $3,623.76 |

11 | 157.040 | 0.001 | 0.700 | 0.824 | 1.183 | 2.089 | 0.473 | 0.402 | $2,371.92 |

12 | 156.870 | 0.001 | 0.700 | 0.820 | 1.412 | 2.888 | 0.569 | 0.477 | $2,570.03 |

13 | 156.660 | 0.002 | 0.700 | 0.834 | 1.500 | 3.223 | 0.590 | 0.514 | $2,899.48 |

14 | 156.330 | 0.002 | 0.700 | 0.840 | 1.571 | 3.512 | 0.611 | 0.543 | $3,964.27 |

15 | 156.200 | 0.001 | 0.800 | 0.799 | 1.378 | 2.697 | 0.537 | 0.593 | $2,073.76 |

16 | 155.990 | 0.001 | 0.800 | 0.836 | 1.402 | 2.783 | 0.514 | 0.629 | $3,610.05 |

17 | 155.820 | 0.001 | 0.800 | 0.819 | 1.552 | 3.355 | 0.586 | 0.684 | $2,259.08 |

18 | 155.510 | 0.002 | 0.800 | 0.844 | 1.613 | 3.603 | 0.584 | 0.730 | $4,645.76 |

19 | 155.120 | 0.002 | 0.800 | 0.842 | 1.878 | 4.766 | 0.681 | 0.849 | $4,712.47 |

20 | 154.660 | 0.002 | 0.800 | 0.796 | 2.029 | 5.489 | 0.794 | 0.870 | $5,365.77 |

Total | | $53,738.83 |

Pipe | Invert elevation downstream [] | s [-] | d [m] | [-] | [ | [] | [-] | [] | Cost [$USD] |
---|---|---|---|---|---|---|---|---|---|

1 | 159.090 | 0.006 | 0.200 | 0.592 | 1.269 | 3.037 | 1.290 | 0.025 | $1,101.43 |

2 | 158.750 | 0.003 | 0.250 | 0.665 | 1.039 | 2.004 | 0.865 | 0.036 | $786.04 |

3 | 158.540 | 0.001 | 0.380 | 0.593 | 0.757 | 1.053 | 0.558 | 0.053 | $2,000.02 |

4 | 158.340 | 0.001 | 0.400 | 0.700 | 0.809 | 1.162 | 0.511 | 0.076 | $2,201.37 |

5 | 158.170 | 0.001 | 0.400 | 0.698 | 0.967 | 1.605 | 0.611 | 0.091 | $1,324.04 |

6 | 157.920 | 0.002 | 0.400 | 0.696 | 1.104 | 2.043 | 0.700 | 0.103 | $1,708.28 |

7 | 157.750 | 0.001 | 0.500 | 0.685 | 1.155 | 2.132 | 0.664 | 0.165 | $1,589.85 |

8 | 157.550 | 0.001 | 0.500 | 0.698 | 1.161 | 2.150 | 0.656 | 0.170 | $1,921.49 |

9 | 157.350 | 0.001 | 0.600 | 0.687 | 1.154 | 2.062 | 0.604 | 0.239 | $3,009.95 |

10 | 157.160 | 0.001 | 0.700 | 0.823 | 1.250 | 2.309 | 0.501 | 0.423 | $3,623.76 |

11 | 157.040 | 0.001 | 0.700 | 0.824 | 1.183 | 2.089 | 0.473 | 0.402 | $2,371.92 |

12 | 156.870 | 0.001 | 0.700 | 0.820 | 1.412 | 2.888 | 0.569 | 0.477 | $2,570.03 |

13 | 156.660 | 0.002 | 0.700 | 0.834 | 1.500 | 3.223 | 0.590 | 0.514 | $2,899.48 |

14 | 156.330 | 0.002 | 0.700 | 0.840 | 1.571 | 3.512 | 0.611 | 0.543 | $3,964.27 |

15 | 156.200 | 0.001 | 0.800 | 0.799 | 1.378 | 2.697 | 0.537 | 0.593 | $2,073.76 |

16 | 155.990 | 0.001 | 0.800 | 0.836 | 1.402 | 2.783 | 0.514 | 0.629 | $3,610.05 |

17 | 155.820 | 0.001 | 0.800 | 0.819 | 1.552 | 3.355 | 0.586 | 0.684 | $2,259.08 |

18 | 155.510 | 0.002 | 0.800 | 0.844 | 1.613 | 3.603 | 0.584 | 0.730 | $4,645.76 |

19 | 155.120 | 0.002 | 0.800 | 0.842 | 1.878 | 4.766 | 0.681 | 0.849 | $4,712.47 |

20 | 154.660 | 0.002 | 0.800 | 0.796 | 2.029 | 5.489 | 0.794 | 0.870 | $5,365.77 |

Total | | $53,738.83 |

The effect of varying the elevation change from to and is also analyzed. The lowest cost is achieved with a highest precision () because more alternatives are evaluated. In this experiment, the same costs are found using and , but for the cost increases in all the instances. Table 7 presents the relative gap between the cost of the solutions obtained with and . For example, the cost of a series of 20 pipes on steep ground using PVC pipes and is $53,738.8, but using the cost rises to $61,813.4. Thus, the relative gap is 15% and is due to the accuracy reached with each elevation change .

Number of pipes | Relative gap | |||
---|---|---|---|---|

Steep ground | Flat ground | |||

Concrete | PVC | Concrete | PVC | |

5 | 1% | 4% | 3% | 3% |

10 | 6% | 8% | 5% | 8% |

15 | 12% | 13% | 13% | 13% |

20 | 16% | 15% | – | – |

Number of pipes | Relative gap | |||
---|---|---|---|---|

Steep ground | Flat ground | |||

Concrete | PVC | Concrete | PVC | |

5 | 1% | 4% | 3% | 3% |

10 | 6% | 8% | 5% | 8% |

15 | 12% | 13% | 13% | 13% |

20 | 16% | 15% | – | – |

For the flat ground setup, no feasible solutions are found for the series of 20 pipes using (neither for concrete pipes nor for PVC pipes). This occurs because there are fewer alternatives in the 3.8 *m* range above the ground to place the deeper pipes.

*y*axis) is presented in a logarithmic scale, and the construction cost is exhibited in the

*x*axis. Each point in the figure represents the solution of a particular setup.

This figure shows that a design that uses an elevation change of is roughly 100 times faster than a design that uses an elevation change of ; but a slightly higher cost is obtained. The former situation is due to exponential growth of the graph as the elevation change gets smaller. For instance, assuming five available diameters, the graph to solve the design problem encompasses 1,900 nodes per manhole with (380 possible placements in 3.8 *m* by 5 available diameters), but only 190 nodes per manhole with (38 possible placements in 3.8 *m* by 5 available diameters). However, a relative gap in costs might represent thousands of dollars. For example, the design of the series of 20 pipes with steep ground and using PVC pipes takes 186.65 seconds using a and 1.85 seconds using a , but there is a relative gap of 15% in the cost of both solutions. Moreover, this gap increases proportional to the number of pipes. Therefore, it is worth spending more computational time minimizing the total cost as exhibited in Table 7, but it is also important to account for the computational time because it gives an insight into how the proposed methodology scales.

## CONCLUSIONS AND FUTURE WORK

In this work, a graph modeling framework is proposed in order to obtain the minimum-cost design of a series of pipes as a shortest path problem. The proposed graph takes into account every possible diameter and slope combination found in each of the series' pipes. A path on the graph additionally encodes a complete design. The graph modeling allows the representation of discrete commercial diameters, which avoids the use of continuous diameters that need to be rounded. The graph grows exponentially as the number of pipes increases, and this particular growth is taken advantage of by applying a highly efficient shortest path algorithm to the problem. Aside from the hydraulic and construction constraints considered in this work, this methodology allows the consideration of additional constraints by discarding arcs of the graph (for instance, a constraint related to the intersections with other utility networks).

The proposed methodology ensures the global optimal solution from an economic point of view because the graph considers all possible alternatives and the Bellman–Ford algorithm implicitly explores all of them. Without having to simplify hydraulic constraints, this methodology still obtains the optimal solution in a very short computational time using a standard desktop computer.

The elevation change used in the hydraulic design (, , or ) affects both the solution and the computational time. With a small value for the elevation change , our methodology finds that the design with lower construction costs is the one that spends the most computational time. Therefore, there is a tradeoff between the solution quality and the computational time required to solve the problem. Additionally, the relative gap between the costs of those solutions obtained with different values of the elevation change are more significant as the number of pipes in the series increases. This is due to the fewer number of alternatives that are explored with larger values of . Finally, computational time is drastically reduced by first evaluating the economic feasibility according to the Bellman–Ford algorithm, and the hydraulic constraints afterwards. Latter evaluations are more expensive in terms of computational time, so it makes sense to verify the cost first in order to avoid hydraulic verifications of suboptimal solutions.

We suggest future work should extend this methodology for a complete sewer network; although several concepts of the methodology can already be extended in a straightforward fashion, there are plenty of new considerations that must be addressed. Layout decisions, such as the flow direction, definition of initial pipes, and intersections between two or more series in the network are some of the challenges that must be tackled to adapt the proposed methodology for complete sewer networks.