A new methodology for the optimal design of series of pipes in sewer systems

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.

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

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.

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

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

View Large

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

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.

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.

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

View Large

Table 4

Pipe input data

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

View Large

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

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

View Large

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

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

View Large

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

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.

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.

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.