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

The 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:
1

2

3
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.
To solve this problem, there are different algorithms such as Bellman–Ford algorithm (Algorithm 1) or Dijkstra's algorithm that use labels (DP) to find an optimal solution (Ahuja 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).
Algorithm 1

Bellman–Ford algorithm.

Algorithm 1

Bellman–Ford algorithm.

### 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

Additionally, there is a set of arcs that represents the pipes between two consecutive manholes. Each arc is defined between nodes and , where is the node at manhole and is the node of the immediately following manhole . Each arc has a cost attribute , which represents the total construction costs of the pipe. The arc cost corresponds to the cost of the pipe plus the excavation cost. In our study, the cost function established by Equation (4) is the one used for sewer systems in Colombia:
4
where is the pipe diameter and 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).
Figure 1

Subset of nodes that belong to manhole .

Figure 1

Subset of nodes that belong to manhole .

Given that the information of the diameter is saved as an attribute of the nodes, Equation (5) states that the diameter associated with arc takes the value of the head node . Likewise, Equation (6) describes the slope associated with arc as a function of the elevation of the corresponding nodes. Figure 2 shows a representation of a pipe as an arc and its corresponding attributes.
5
Figure 2

Representation of a pipe in a sewer system as an arc.

Figure 2

Representation of a pipe in a sewer system as an arc.

6
Figure 3 shows an illustrative example of a graph that represents a sewer system with three manholes () and three different commercial diameters (i.e., ). At each manhole, nodes are grouped in smaller rectangles to represent different depths at which the pipes can be placed, while the nodes within the groups represent different pipe diameters in an increasing order. For instance, nodes , and satisfy that and . Nodes , and are placed units below the previous group of nodes and represent the same three commercial diameters, i.e., and . The elevation change is an input parameter of the methodology that establishes a numeric tolerance of the designs.
Figure 3

Graph representing a sewer system with two pipes in series for three commercial diameters and three possible invert elevations.

Figure 3

Graph representing a sewer system with two pipes in series for three commercial diameters and three possible invert elevations.

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.

After solving the shortest path problem, the solution obtained is a minimum-cost path that encodes the design decisions of the complete series. Notice that since the solution is a path, the methodology selects a single pipe (arc) for each link among all possible alternatives. By associating this graph representation with the mathematical formulation (Equations (1)–(3)), the objective function can be rewritten to detail the cost of a path (design). Equation (7) establishes the cost of an arc using the graph representation, while Equation (8) use this cost definition in the objective function.
7

8
Notice that Equation (7) depends on the pipe diameter and on the excavation volume 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.

Table 1

Hydraulic design constraints

ConstraintValueCondition
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
ConstraintValueCondition
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).

Table 2

Excavation limits

Pedestrian or green area 0.75 5.0
Vehicular 1.2 5.0
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.

Given the input data described in the graph modeling section, the first step is to generate all the nodes of the graph and organize them in subsets at every manhole . Algorithm 2 presents the nodes generation process for every manhole , which receives as input parameters the set of commercial diameters 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.
Algorithm 2

Create nodes for each manhole.

Algorithm 2

Create nodes for each manhole.

The next step is to create only those arcs that satisfy all the commercial and hydraulic constraints presented in Table 1. Algorithm 3 presents the procedure that builds the graph and solve the shortest path problem. The process evaluates all arcs between two consecutive manholes as described in lines 1–3. First, line 4 guarantees that the diameter of the downstream node is always greater than or equal to the diameter of the upstream node to avoid obstructions. Line 5 calculates the slope at which the pipe will be placed in the case of selecting the current arc as part of the optimal path. Line 6 evaluates if the slope is positive, i.e., in favor of gravity. Line 7 calculates the arc cost following Equation (7); where the pipe diameter is set as in Equation (5) and the excavation volume is calculated according to the elevations of the nodes and the length of the pipe. While building the graph, the Bellman–Ford algorithm is simultaneously executed in order to find the shortest path. Line 8 applies the label correcting algorithm, however, before updating the cumulative cost and parent labels (see lines 13 and 14), the hydraulic constraints must be validated. Line 9, computes the flow rate 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.
Algorithm 3

Build the graph and execute Bellman–Ford algorithm.

Algorithm 3

Build the graph and execute Bellman–Ford algorithm.

Algorithm 4

Calculate hydraulics.

Algorithm 4

Calculate hydraulics.

Algorithm 5

Calculate normal flow depth.

Algorithm 5

Calculate normal flow depth.

Algorithm 6

Validate constraints.

Algorithm 6

Validate constraints.

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.

Finally, the graph that includes all feasible arcs is explored in a backwards manner, in order to extract the solution as shown in Algorithm 7. Lines 1–8 search over all the nodes at the last manhole in order to find the minimum cumulative cost node that stands for the minimum-cost alternative. Lines 9–15 recover the complete path by finding the parent nodes that belong to the shortest path .
Algorithm 7

Get optimal solution.

Algorithm 7

Get optimal solution.

Figure 4 shows the shortest path of the example presented in Figure 3. Path encodes a design in which both pipes use the second commercial diameter () and the slopes of the pipes are in favor of gravity.
Figure 4

Design solution of two pipes in series of a sewer network.

Figure 4

Design solution of two pipes in series of a sewer network.

## 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.

Table 3

Manhole input data

Manhole []k
Steep ground []Flat ground []
0.0246 161.5 160.6
0.0114 160.5 160.7
0.0170 160.2 160.7
0.0230 160.2 160.7
0.0145 160.2 160.6
0.0125 160.2 160.5
0.0336 160.2 160.5
0.0332 159.9 160.7
0.0692 159.8 160.7
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.0246 161.5 160.6
0.0114 160.5 160.7
0.0170 160.2 160.7
0.0230 160.2 160.7
0.0145 160.2 160.6
0.0125 160.2 160.5
0.0336 160.2 160.5
0.0332 159.9 160.7
0.0692 159.8 160.7
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
Table 4

Pipe input data

PipeManhole
[][] [-] [-]
0.0246 180
0.0360 121
0.0530 205
0.0760 200
0.0905 123
0.1030 142
0.1366 115
0.1698 135
0.2390 168 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
PipeManhole
[][] [-] [-]
0.0246 180
0.0360 121
0.0530 205
0.0760 200
0.0905 123
0.1030 142
0.1366 115
0.1698 135
0.2390 168 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

Figure 5 summarizes the results for the design of various different series of pipes using PVC pipes and an elevation change of . The figure shows how the cost (bars) and the computational time (lines) grow as the size of the series of pipes increases for both types of topographical setups.
Figure 5

Construction cost and computational time for the designed series of pipes using PCV pipes and .

Figure 5

Construction cost and computational time for the designed series of pipes using PCV pipes and .

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.

Table 5

Design of a series of 20 pipes on flat ground using PCV pipes and

PipeInvert elevation downstream [] [-] [] [-] [ [] [-] []Cost [$USD] 158.873 0.002 0.250 0.628 0.757 1.137 0.659 0.025$1,395.84
158.720 0.001 0.350 0.497 0.753 1.081 0.651 0.036 $1,182.84 158.507 0.001 0.350 0.700 0.757 1.056 0.511 0.054$2,384.75
158.301 0.001 0.400 0.690 0.822 1.195 0.525 0.076 $2,678.61 158.130 0.001 0.400 0.697 0.968 1.608 0.612 0.091$1,522.13
157.893 0.002 0.500 0.689 1.237 2.416 0.707 0.179 $2,233.80 157.717 0.002 0.500 0.695 1.179 2.212 0.669 0.172$1,914.00
157.532 0.001 0.530 0.689 1.154 2.108 0.641 0.187 $2,675.43 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
PipeInvert elevation downstream [] [-] [] [-] [ [] [-] []Cost [$USD] 158.873 0.002 0.250 0.628 0.757 1.137 0.659 0.025$1,395.84
158.720 0.001 0.350 0.497 0.753 1.081 0.651 0.036 $1,182.84 158.507 0.001 0.350 0.700 0.757 1.056 0.511 0.054$2,384.75
158.301 0.001 0.400 0.690 0.822 1.195 0.525 0.076 $2,678.61 158.130 0.001 0.400 0.697 0.968 1.608 0.612 0.091$1,522.13
157.893 0.002 0.500 0.689 1.237 2.416 0.707 0.179 $2,233.80 157.717 0.002 0.500 0.695 1.179 2.212 0.669 0.172$1,914.00
157.532 0.001 0.530 0.689 1.154 2.108 0.641 0.187 $2,675.43 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 .

Table 6

Design of a series of 20 pipes on steep ground using PVC pipes and

PipeInvert elevation downstream []s [-]d [m] [-] [ [] [-] []Cost [$USD] 159.090 0.006 0.200 0.592 1.269 3.037 1.290 0.025$1,101.43
158.750 0.003 0.250 0.665 1.039 2.004 0.865 0.036 $786.04 158.540 0.001 0.380 0.593 0.757 1.053 0.558 0.053$2,000.02
158.340 0.001 0.400 0.700 0.809 1.162 0.511 0.076 $2,201.37 158.170 0.001 0.400 0.698 0.967 1.605 0.611 0.091$1,324.04
157.920 0.002 0.400 0.696 1.104 2.043 0.700 0.103 $1,708.28 157.750 0.001 0.500 0.685 1.155 2.132 0.664 0.165$1,589.85
157.550 0.001 0.500 0.698 1.161 2.150 0.656 0.170 $1,921.49 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
PipeInvert elevation downstream []s [-]d [m] [-] [ [] [-] []Cost [$USD] 159.090 0.006 0.200 0.592 1.269 3.037 1.290 0.025$1,101.43
158.750 0.003 0.250 0.665 1.039 2.004 0.865 0.036 $786.04 158.540 0.001 0.380 0.593 0.757 1.053 0.558 0.053$2,000.02
158.340 0.001 0.400 0.700 0.809 1.162 0.511 0.076 $2,201.37 158.170 0.001 0.400 0.698 0.967 1.605 0.611 0.091$1,324.04
157.920 0.002 0.400 0.696 1.104 2.043 0.700 0.103 $1,708.28 157.750 0.001 0.500 0.685 1.155 2.132 0.664 0.165$1,589.85
157.550 0.001 0.500 0.698 1.161 2.150 0.656 0.170 $1,921.49 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 .

Table 7

Relative gap between the solutions obtained with and

Number of pipesRelative gap
Steep ground
Flat ground
ConcretePVCConcretePVC
1% 4% 3% 3%
10 6% 8% 5% 8%
15 12% 13% 13% 13%
20 16% 15% – –
Number of pipesRelative gap
Steep ground
Flat ground
ConcretePVCConcretePVC
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.

On the other hand, the computational time is far less for a design with an elevation change of than with an elevation change of or . Figure 6 presents the computational time and construction cost for each of the 24 numerical examples with PVC pipes. These examples correspond to the combination of two different topographies (flat ground and steep ground), four values for the number of pipes in the series (5, 10, 15, or 20), and three values for the elevation change . Computational time (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.
Figure 6

Elevation change effect over the performance metrics.

Figure 6

Elevation change effect over the performance metrics.

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.

## REFERENCES

REFERENCES
Afshar
M.
2010
.
41
(
2
),
188
195
.
Afshar
M.
2012
.
Scientia Iranica
19
(
1
),
11
19
.
Ahuja
R. K.
Magnati
T. L.
Orlin
J. B.
1993
Network Flows: Theory, Algorithms, and Applications
.
Prentice-Hall
,
,
USA
.
Austin
R.
Chen
A.
Savić
D.
Djordjević
S.
2014
.
J. Hydroinform.
16
(
6
),
1359
1374
.
Bellman
R.
1958
On a routing problem
.
Quart. Appl. Math.
16
(
1
),
87
90
.
Brown
G.
2002
The history of the Darcy-Weisbach equation for pipe flow resistance
. In:
Environmental and Water Resources History Sessions at ASCE Civil Engineering Conference and Exposition
.
Washington, DC
,
USA
, pp.
34
43
.
Butler
D.
Davies
J. W.
2011
Urban Drainage
. 3rd edn.
Spon Press
,
New York
,
USA
.
Cimorelli
L.
Cozzolino
L.
Covelli
C.
Mucherino
C.
Palumbo
A.
Pianese
D.
2013
.
J. Irrig. Drain. Eng.
139
(
2
),
137
144
.
Cimorelli
L.
Cozzolino
L.
Covelli
C.
Della Morte
R.
Pianese
D.
2014
.
J. Irrig. Drain. Eng.
140
(
6
),
04014015
.
Cimorelli
L.
Morlando
F.
Cozzolino
L.
Covelli
C.
Della Morte
R.
Pianese
D.
2015
.
J. Irrig. Drain. Eng.
142
(
1
),
04015028
.
Cisty
M.
2010
.
Water Resour. Manage.
24
(
1
),
1
24
.
Cozzolino
L.
Cimorelli
L.
Covelli
C.
Mucherino
C.
Pianese
D.
2015
.
Water
7
(
2
),
546
567
.
Demetrescu
C.
Goldberg
A.
Johnson
D.
2006
9th DIMACS implementation challenge – shortest paths. Available at: www.dis.uniroma1.it/challenge9/
.
Elimam
A.
Charalambous
C.
Ghobrial
F.
1989
.
J. Environ. Eng.
115
(
6
),
1171
1190
.
Fu
G.
Makropoulos
C.
Butler
D.
2010
.
J. Hydroinform.
12
(
2
),
140
149
.
Haghighi
A.
Bakhshipour
A. E.
2012
.
Water Resour. Manage.
26
(
12
),
3441
3456
.
Haghighi
A.
Bakhshipour
A. E.
2015
.
J. Water Resour. Plann. Manage.
141
(
1
),
04014045
.
Haghighi
H.
Samani
M. V.
Samani
Z.
2011
.
Water Resour. Manage.
25
(
7
),
1791
1808
.
Haith
A.
1966
Vertical Alignment of Sewer and Drainage Systems by Dynamic Programming
.
Master thesis
,
Massachusetts Institute of Technology
,
Boston, MA
,
USA
.
Holland
M.
1966
Computer Models of Wastewater Collection Systems
.
Master thesis
,
Harvard University
,
Cambridge, MA
,
USA
.
Kulkarni
V. S.
Khanna
P.
1985
.
J. Environ. Eng.
111
(
5
),
589
601
.
Li
G.
Matthew
R.
1990
.
J. Environ. Eng.
116
(
5
),
927
944
.
Marchionni
V.
Lopez
N.
Mamouros
L.
2014
.
Water Resour. Manage.
28
(
13
),
4415
4431
.
Moeini
R.
Afshar
M. H.
2012
.
51
,
49
62
.
Mortazavi-Naeini
M.
Kuczera
G.
Cui
L.
2015
.
J. Hydroinform.
17
(
1
),
36
55
.
Navarro
I.
2009
Optimized Network of Urban Drainage Design
.
Master thesis
,
,
Bogotá, Colombia
.
Palumbo
A.
Cimorelli
L.
Covelli
C.
Cozzolino
L.
Mucherino
C.
Pianese
D.
2014
.
Civil Eng. Environ. Syst.
31
(
1
),
79
96
.
Pan
T.
Kao
J.
2009
.
J. Environ. Eng.
135
(
1
),
17
24
.
Sanchez
A.
Medina
N.
Vojinovic
Z.
Price
R.
2014
.
J. Hydroinform.
16
(
2
),
319
340
.
Sousa
J.
Ribeiro
A.
Cunha
M. C.
Antunes
A.
2002
An optimization approach to wastewater systems planning at regional level
.
J. Hydroinform.
4
(
2
),
115
123
.
Swamee
P. K.
Sharma
A. K.
2013
.
Appl. Math. Modell.
37
(
6
),
4430
4439
.
Yeh
S. F.
Chu
C. W.
Chan
Y. J.
Lin
M. D.
2011
.
Eng. Optim.
43
(
2
),
159
174
.