1 Introduction

A sewer network has a tree-like structure which collects wastewater from industrial, commercial and residential areas and transports to wastewater treatment plant. A Huge amount of investment is required for construction and maintenance of large scale sewerage networks. Thus, reduction by a few percent of the cost of a network may result in substantial reduction in the project cost. Design optimization of sewer network problem includes two sub problems (i) optimal sewer network layout determination and (ii) optimal design of sewer network components. These two sub problems are strongly coupled and should be solved simultaneously for an optimal solution to the whole problem. Simultaneous sewer network layout and its component size optimization problem consist of many constraints which are generally nonlinear, discrete and sequential. Due to the complex nature of the problem, most of the researchers have focused on only the component size optimization of sewer network (Walsh and Brown 1973; Dajani and Hasit 1974; Price 1978; Walters and Templeman 1979; Kulkarni and Khanna 1985; Elimam et al. 1989; Swamee 2001; Afshar 2006, 2007, 2010; Guo et al. 2007, 2008; Izquierdo et al. 2008; Pan and Kao 2009; Haghighi and Bakhshipour 2012; Karovic and Mays 2014). Only a few researchers have addressed the problem of layout and the combined layout and component size optimization of sewer network (Argaman et al. 1973; Tekeli and Belkaya 1986; Li and Matthew 1990; Walters and Lohbeck 1993; Walters and Smith 1995; Diogo and Graveto 2006; Moeini and Afshar 2012; Haghighi 2013; Steele et al. 2016).

The present work describes a method to optimally solve the problem of the layout and component size determination of sewer networks. The optimization has been done in four steps: (1) An algorithm is applied to find a predetermined number of sewer layouts of a base sewer network in order of increasing length of sewer line; (2) For all layouts total cumulative flow (CQ) is obtained by adding flows in each sewer; (3) These layouts are sequenced in ascending order of total cumulative flow; (4) The modified PSO is then applied to get optimal sewer component sizes of each of these sequenced sewer layout. The optimal cost of the sewer system with modified PSO is compared with original PSO.

2 Optimal Sewer Layout Selection Method

The sewer network layout is a graph with specific properties. Therefore, it is necessary to review some basic definitions and principles of the graphs (Clark and Holton 1995; Deo 2005):

  • Graph: An undirected graph G = (V, E) consists of a set of vertices V (V = v1, v2, . .,vn) and another set of edges E (E = e1, e2, . ., em), such that each edge eij is identified with an unordered pair (vi, vj) of vertices.

  • Tree: A graph G is called a tree if it is a connected acyclic graph. In acyclic graph, one and only one path between any pair of vertices.

  • Weighted Graph: A weighted graph is a graph G in which each edge e is assigned a real number w(e) called the weight of e.

  • Spanning Tree: A spanning tree of a graph G is a tree containing all vertices of a graph G.

  • Minimum spanning tree (MST): A spanning tree with the minimum weight in a weighted graph is called a minimum spanning tree.

The layout of the sewer system is a sub graph extracted from a predefined base graph of city or town drainage system. In a base graph, all possible locations of manholes (vertices) and sewer lines (edges or links) are identified and this graph is a connected cyclic graph. With respect to the urban street configurations, topology, barriers, locations of the outlets, an undirected base graph can be drawn. Nevertheless, for generating a feasible layout from a base graph two basic constraints to be satisfied are: (i) graph should be acyclic and (ii) all manholes (vertices) must be included in the layout (spanning tree).

There are number of greedy algorithms for finding the minimum spanning tree (MST) of an undirected weighted graph G, Kruskal’s and Prim’s algorithms are well known (Clark and Holton 1995). Each sewer line constitutes the edge with weight equal to its length. MST represents minimum length layout of a base sewer network (graph). The MST does not guarantee an optimal solution of the sewer system.

2.1 Algorithm – Generation of a Predefined Number of Spanning Trees

The algorithm is based on the assumption that a base sewer network (graph) including all possible edges of the network is given i.e. locations of manholes have been identified. The flow chart shown in Fig. 1 presents the simplified representation of the ‘generation of a predetermined spanning trees’ algorithm:

Fig. 1
figure 1

Generation of a predefined number of spanning trees algorithm

Full size image

2.2 Optimal Layout Selection

All constraints of the layout problem are systematically satisfied during the generation of layouts. A large number of alternative layouts are available, and it is very difficult to identify which layout should be selected first for component size optimization. Therefore, a strategy to sequence these alternatives needs to be developed. The Eq. 1 is used to calculate total cumulative flow (CQ j ) of ith layout.

$$ C{Q}_j={\displaystyle \sum_{i=1}^{i=N}{q}_{ij}} $$
(1)

Where, N = the total number of links (edges) in the layout, q ij  = flow in the ith link of the jth layout, and CQ j is the sum of cumulative flows in all links of the jth layout.

The total cumulative flow (CQ) is calculated for all generated layouts, and then these layouts are sequenced in ascending order of CQ. Each layout is optimized for component size optimization in this sequence.

The applicability of the proposed algorithm is tested against a benchmark example in the literature. The first example (network 1) to be considered is a simple network illustrated in Fig. 2. The network 1 consists of 9 manholes (vertices), 12 links (edges) and an outlet located at manhole number 9. This example has been considered as a test example by Afshar and Mariño (2006) to test the performance of ant algorithms for layout optimization of tree network. The wastewater contribution at each node of the network is given in table 1.

Fig. 2
figure 2

Base layout of network 1

Full size image
Table 1 Nodal wastewater contribution for network 1
Full size table

By applying the proposed approach, all alternative layouts are sequenced in ascending order of CQ. The top 4 solutions (minimum CQ) of the network 1 are shown in Fig.  3 .

Fig. 3
figure 3

Top four layout alternatives with CQ = 260 l/s

Full size image

3 Formulation of Optimal Sewer Design Problem for Component Sizing

3.1 Sewer Hydraulics

In circular sewer Steady-state flow is described by the continuity principle (Q = VA) and Manning’s equation which is:

$$ V=\frac{1}{n}{R}^{2/3}{S}^{1/2} $$
(2)

where Q = discharge in sewer, V = velocity of sewage flow, A = flow cross-sectional area, n = Manning’s coefficient, R = hydraulic mean depth and S = sewer slope.

Common partially full parameters for circular sewer sections are also determined from the following equations:

$$ K=Qn{D}^{-8/3}{S}^{-1/2} $$
(3)
$$ \theta =\frac{3\pi }{2}\sqrt{1-\sqrt{1-\sqrt{\pi K}}} $$
(4)
$$ \left(\frac{d}{D}\right)=\frac{1}{2}\times \left(1- \cos \frac{\theta }{2}\right) $$
(5)
$$ r=\frac{D}{4}\left(\frac{\theta - \sin \theta }{\theta}\right) $$
(6)

where K = constant, D = sewer diameter, (d/D) = proportional sewage depth, r = hydraulic mean depth, and θ = the central angle from the center of the section to the sewage surface (in radian). Equation 4 is applicable for K values less than (1/π) = 0.318 (Saatci 1990).

3.2 Design Constraints

For a given layout, a feasible sewer design is defined as a set of sewer diameters, slopes and excavation depths which satisfies all the constraints. Typical constraints of sewer network design are:

  1. (1)

    Sewer cover depth: It is necessary to provide minimum cover depth (CDmin) to avoid damage to the sewer line and also to provide adequate fall for house sewer connections. Further in order to reduce the excavation, manhole cost and pumping cost, cover depth should be less than prescribed maximum cover depth (CDmax).

    $$ \begin{array}{cc}\hfill {\mathrm{CD}}_{\min}\le {\mathrm{CD}}_{\mathrm{i}}\le {\mathrm{CD}}_{\max}\hfill & \hfill \mathrm{i}=1,\dots,\ \mathrm{N}\hfill \end{array} $$
    (7)

    Where CDi = average cover depth of the ith sewer link, and N = total number of links. The minimum cover depth of 0.9 m and maximum cover depth of 5.0 m has been adopted in the present paper.

  2. (2)

    Sewer flow velocity: For each sewer, flow velocity must be greater than the minimum permissible velocity (Vmin) to prevent the deposit of solids in the sewers and less than the maximum permissible velocity (Vmax) to prevent sewer scouring.

    $$ \begin{array}{cc}\hfill {\mathrm{V}}_{\min}\le\ {\mathrm{V}}_{\mathrm{i}}\le\ {\mathrm{V}}_{\max}\hfill & \hfill \mathrm{i}=1,\dots,\ \mathrm{N}\hfill \end{array} $$
    (8)

    Minimum permissible velocity of 0.6 m/s and maximum velocity of 3.0 m/s has been adopted in the present paper.

  3. (3)

    Flow depth ratio: wastewater depth ratio of the sewer should be less than 0.8.

    $$ \begin{array}{cc}\hfill \frac{d_i}{D_i}\le 0.8\hfill & \hfill \mathrm{i}=1, \dots, \mathrm{N}\hfill \end{array} $$
    (9)

    Where Di = diameter of ith sewer and di = sewage flow depth in ith sewer.

  4. (4)

    Sewer diameters: The diameter of a sewer should not be less than the minimum prescribed size (Dmin). The minimum diameter of 0.2 m has been adopted in the present paper.

    $$ \begin{array}{cc}\hfill {\mathrm{D}}_{\min }-{\mathrm{D}}_{\mathrm{i}}\le 0\hfill & \hfill \mathrm{i} = 1,\ .\ .\ .,\ \mathrm{N}\hfill \end{array} $$
    (10)
  5. (5)

    Progressive sewer diameters: The diameter of ith sewer (Di) should not be less than diameter of immediately preceding sewer (Dp)

    $$ \begin{array}{cc}\hfill {\mathrm{D}}_{\mathrm{p}}-{\mathrm{D}}_{\mathrm{i}}\le 0\hfill & \hfill \mathrm{i}=1,\ .\ .\ .,\ \mathrm{N}\hfill \end{array} $$
    (11)

Constraints (Eqs. 9, 10 & 11) are satisfied while selecting pipe diameters and as such not included for penalty cost.

The optimal design of a sewer system for a given layout is to determine the feasible sewer diameters, excavation depths and sewer slopes in order to minimize the total cost of the sewerage system. The cost of the sewerage systems mainly depends upon sewer diameters, excavation depths, and manhole construction.

Total Cost: The total cost (TCi) of ith link would be

$$ {\mathrm{TC}}_{\mathrm{i}}={\left(\mathrm{Cost}\ \mathrm{of}\ \mathrm{sewer}\right)}_{\mathrm{i}}+{\left(\mathrm{Cost}\ \mathrm{of}\ \mathrm{manhole}\right)}_{\mathrm{i}}+{\left(\mathrm{Cost}\ \mathrm{of}\ \mathrm{earthwork}\right)}_{\mathrm{i}} $$
(12)

The problem of optimization of a sewer network with N number of links may be expressed as

$$ \mathrm{Minimize}\ \mathrm{C}={\displaystyle \sum_{i=1}^N\left(T{C}_i+P{C}_i\right)} $$
(13)

where C = cost function of sewer network, TCi = total cost of a sewer network for the ith link, and PCi = penalty cost for the ith link.

$$ P{C}_i={(PD)}_i+{\left(P{V}_{\min}\right)}_i+{\left(P{V}_{\max}\right)}_i $$
(14)

Where (PD) i is penalty due to maximum depth, (PV min ) i is penalty due to minimum velocity, and (PV max ) i is penalty due to maximum depth for the ith link. Penalty for violation of minimum velocity constraints has not been applied for discharge less than 0.0014 m3/s.

These penalties are applied by multiplying a very large number (such as Rs. 108) to the violated constraint and are added to the total cost (TC) if the maximum cover depth constraint, minimum, and maximum velocity constraints are violated.

4 Modified Particle Swarm Optimization (MPSO)

An evolutionary algorithm, Particle swarm optimization was introduced by Kennedy and Eberhart (1995). In PSO, each problem solution is a bird of the flock and is referred to as a particle. In PSO algorithm, the birds having individual and social behaviour and mutually coordinate their movement towards a destination (Izquierdo et al. 2008; Shi and Eberhart 1998). PSO has some common evolutionary computation features, such as (a) initialization with a population (swarm) of random solutions, (b) updating positions in search of optima and (c) with some specific strategy particles evolution through the problem space (Izquierdo et al. 2008).

An initial group of particles starts their movement in the first iteration randomly. Then they try to determine the optimum solutions through the method described below.

The current position of the ith particle in the d-dimensional space at tth iteration is denoted as:

$$ {x}_{\mathrm{i}}\left(\mathrm{t}\right)=\left\{{x}_{\mathrm{i}1}\left(\mathrm{t}\right),{x}_{\mathrm{i}2}\left(\mathrm{t}\right),\ .\ .\ ., {x}_{\mathrm{i}\mathrm{d}}\left(\mathrm{t}\right)\right\} $$
(15)

Its best position reached so far,

$$ {x}_{\mathrm{i}\_\mathrm{best}}\left(\mathrm{t}\right) = \left\{{x}_{\mathrm{i}1\_\mathrm{best}}\left(\mathrm{t}\right),{x}_{\mathrm{i}2\_\mathrm{best}}\left(\mathrm{t}\right),\ .\ .\ ., {x}_{\mathrm{i}\mathrm{d}\_\mathrm{best}}\left(\mathrm{t}\right)\right\} $$
(16)

Its velocity,

$$ {v}_{\mathrm{i}}\left(\mathrm{t}\right)=\left\{\left({v}_{\mathrm{i}1}\left(\mathrm{t}\right),{v}_{\mathrm{i}2}\left(\mathrm{t}\right),\ .\ .\ ., {v}_{\mathrm{i}\mathrm{d}}\left(\mathrm{t}\right)\right.\right\} $$
(17)

Individual particle’s position in the search space is updated by

$$ {x}_{\mathrm{i}}\left(\mathrm{t}+1\right)={x}_{\mathrm{i}}+{v}_{\mathrm{i}}\left(\mathrm{t}+1\right) $$
(18)

Where the new velocity

$$ {v}_{\mathrm{i}}\left(\mathrm{t}+1\right)=\upomega \left(\mathrm{t}\right).{v}_{\mathrm{i}}\left(\mathrm{t}\right)+{\mathrm{c}}_1{\mathrm{r}}_1\left\{{x}_{\mathrm{i}\_\mathrm{best}}\left(\mathrm{t}\right)\hbox{--} {x}_{\mathrm{i}}\left(\mathrm{t}\right)\right\}+{\mathrm{c}}_2{\mathrm{r}}_2\left\{{x}_{\mathrm{g}\_\mathrm{best}}\left(\mathrm{t}\right)\ \hbox{--} {x}_{\mathrm{i}}\left(\mathrm{t}\right)\right\} $$
(19)

Where, I = 1, 2, . . ., P (P = total number of particles in a swarm); t = 1, 2,. ., T (T = total number of iterations or time intervals). In each time interval, the particle’s velocity v i (t) changes the position of the particle. The best position of each particle up to time t is xi_best(t) and the best position of a particle among all particles (from 1 to P) up to time t is xg_best(t). The previous velocity v i(t) is biased with inertia (ω), and the other parts are biased with two acceleration coefficients c1 and c2, with the random numbers (r1 and r2) which are uniformly distributed between 0 to 1 (Ostadrahimi et al. 2012).

The inertia weights ω(t) and acceleration coefficients (c1 and c2) are updated in each time interval with the following equations:

$$ \omega (t)={\omega}_{\max }-\frac{\omega_{\max }-{\omega}_{\min }}{T}\times t $$
(20)
$$ {c}_1(t)={c}_{1, max}-\frac{c_{1, \max }-{c}_{1, \min }}{T}\times t $$
(21)
$$ {c}_2(t)={c}_{2, max}-\frac{c_{2, \max }-{c}_{2, \min }}{T}\times t $$
(22)

where ωmax is the maximum and ωmin is the minimum inertia weight and their values have been taken as 0.7 and 0.2, respectively in the present problem. c1, max and c2, max are the maximum accelerations, and their values have been taken as 2. c1,min and c2,min are the minimum accelerations, and their values have been taken as 0.5.

Particle’s velocity in each dimension is limited to minimum and maximum velocities:

$$ {v}_{\min}\le {v}_{\mathrm{i}}\le {v}_{\max } $$
(23)

Particle velocity is a very important parameter. The value of v max and v min must be in limit otherwise the search space may not be explored fully. v max is generally set to about 10-20% of the range of the variable in each dimension (Eberhart and Shi 1998). v min is generally considered to avoid stagnancy of the particles in exploration of a new solution space. The above adjustable parameters (vmax, ωmax, ωmin, c1, and c2) must be fixed. These adjustable parameters should be adjusted by trial and error, according to the sensitivity of the problem and the model performance. Moreover, these adjustable parameters, the number of iteration and number of particles affect the final solution. Generally, the searching process is terminated after a specified number of iterations or when the best result of the objective function remains unchanged for a specific number of consecutive iterations. In the modified PSO methodology adjustable parameters change in each time interval, whereas in original PSO they remain fixed throughout the optimization process. The modified PSO methodology is as follows:

  1. Step 1

    Initialize the particle swarm by randomly assigning initial velocity and position of each particle.

  2. Step 2

    Calculate the fitness function for each particle.

  3. Step 3

    For each particle, update its best position so far x i_best(t), if its current position is better than its earlier best one.

  4. Step 4

    Update the globally best particle of the swarm that has the swarm’s best fitness value and set its index as g and its position at x g_best(t) .

  5. Step 5

    Calculate velocities of all the particles using equation (19).

  6. Step 6

    Update the new position of each particle using equation (18).

  7. Step 7

    If the problem involves discrete variables, the new position needs to be changed to discrete position in each dimension by selecting the nearest discrete position in that dimension

  8. Step 8

    If the stopping criterion is met stop else repeat steps 2–7

  9. Step 9

    Show the result given by the best particle (xg_best)

Above mentioned modified PSO methodology deals with both continuous and discrete variables, as requisite for the design of sewer networks.

5 Optimization of Sewer System

The second example network 2 (Sudarshanpura sewer network) as shown in Fig.  4 has been considered to for application of the proposed ‘generation of a predefined number of spanning trees’, their sequencing and MPSO algorithm. The Sudarshanpura sewer network (network 2) collects only domestic wastewater from the Sudarshanpura residential colony, Jaipur, India through gravity. It consists of 105 nodes (manholes), 116 links (sewer pipes), and STP is located at node number 0. The Link number, nodal connectivity, link length and nodal wastewater contribution are given as input.

Fig. 4
figure 4

Base network of Sudarshanpura (network 2)

Full size image

The network 2 is solved in two phases. In the first phase, the ‘generation of a predefined number of spanning trees’ algorithm is applied to finds a predetermined number of layouts of the network in order of increasing length of sewer line; after this, by using Eq. 1 these alternative layouts are sequenced in ascending order of CQ. In the second phase, the proposed MPSO methodology is applied to the sequenced sewer layouts for component size optimization. The following steps have been followed to optimize the sewer system for component sizing:

  1. 1.

    Start with the first iteration (t = 1).

  2. 2.

    Select particle i = 1 (consisting of all sewer link diameters and slopes)

  3. 3.

    Calculate sewer hydraulis for complete sewer system.

  4. 4.

    Calculate invert levels of upstream and downstream node of a link

  5. 5.

    Calculate cost of sewers, cost of manholes and cost of earthwork

  6. 6.

    Calculate total cost of sewer network (TC)

  7. 7.

    Add the respective penalty costs in TC where contraints (maximum depth, maximum velocity, and minimum velocity) are violated.

  8. 8.

    Calculate fitness value of the particle and update pbest.

  9. 9.

    Increase the value of i by one. If it exceeds maximum number of particles go to step 10 else go to step 3

  10. 10.

    Calculate gbest among all particles for all time steps.

  11. 11.

    Calulate new particle velocities and their positions. Increase t by one. If t value exceeds maximum number of iterations go to step 12 else set i =1 and go to step 3.

  12. 12.

    Output the gbest and stop.

Table 2 shows the cost of NP4 class RCC sewer pipes (including the cost of their transportation, lowering & laying in trenches, aligning & jointing of pipes), cost of manholes (it depends on the depth of excavation and the diameter of the manhole and material of construction), and cost of earthworks (it includes the cost of trench excavation, dressing of sides, ramming of bottoms, getting out the excavated material, refilling after laying pipe and disposal of surplus excavated material). The cost of pipe (RCC NP4 class), manhole and earth work have been taken from Schedule of Rates (2013).

Table 2 Sewer network cost details
Full size table

6 Results

The performance of the proposed generation of a predefined number of spanning tree and MPSO algorithm is tested in this section by applying the both algorithms to find optimal design of network 2.

Table 3 clearly shows that the layout having minimum CQ has the minimum total cost. The total cost of sewer layout is generally increasing with the CQ of a layout. The cost of optimal layout (CQ = 3639.13 l/s) is Rs. 8.371 × 106 with modified PSO as compared to the cost of original PSO Rs. 8.473 × 106. Further the 2nd alternative layout (CQ = 3642.34 l/s) thses cost are Rs. 8.477 × 106 and Rs. 8.547 × 106 respectively, for 90 iterations. Figure 5 shows the Optimal sewer layouts of a base network 2.

Table 3 Total cumulative discharge vs. Total cost at different iterations
Full size table
Fig. 5
figure 5

Optimal sewer layouts of network 2 (a) CQ = 3639.13 l/s (b) CQ = 3642.34 l/s

Full size image

Results of MPSO are compared with original PSO in order to compare the efficiency of the proposed algorithm. The original PSO parameter values of c1 and c2 have been taken as 2 and ω has been taken as 0.8. The results are obtained using swarm size 1000 and 30, 60 and 90 iterations respectively for each sewer layout. Table 3 compares the results of the proposed MPSO with original PSO. It is clearly seen that the proposed MPSO algorithm was able to obtain a better solution as compared to an original PSO algorithm in all the layouts.

Optimal sewer layout of a base network 2 as shown in Fig. 5a is selected for the detailed design. Figure 6 a, b, c and d show that the minimum solution cost obtained by the modified and original PSO algorithm against the swarm sizes for different iterations. The minimum cost obtained by the original PSO in 90 iterations for 1000 swarm size is Rs. 8.473 × 106, whereas the cost obtained by the MPSO is reduced to Rs. 8.371 × 106.

Fig. 6
figure 6

Variations of the minimum cost with swarm sizes at (a) 30 iterations (b) 60 iterations (c) 90 iterations (d) 120 iterations

Full size image

It is seen that the solution obtained by MPSO algorithm is better than the solution of the original PSO algorithm when the swarm size is 1000. Figure 7 shows the solution cost obtained with modified particle swarm optimization, the best solution produced when the swarm size is 1000. Table 4 shows the details of the optimal design of sewer component sizing of a layout Fig. 5a with 1000 swarm size and 90 iterations.

Fig. 7
figure 7

Variations of the minimum cost with swarm sizes at different iterations, MPSO

Full size image
Table 4 Daimeters & slopes of the optimal sewer network obtained by MPSO
Full size table

7 Conclusions

This paper presents the generation of a predefined number of spanning trees with their sequencing and modified PSO algorithm to optimally solve the problem of the layout and component size determination of sewer networks. An algorithm ‘generation of a predefined number of spanning tree’ is applied to generate a predetermined number of alternative layouts of a base network in order of increasing length. These layouts are sequenced in ascending order of total cumulative flows. After the layouts are sequenced, a modified PSO algorithm is applied to optimaly size sewer components of the sewer system. The proposed methods for optimal layout and component size determination were applied to a problem of Sudarshanpura sewer network design.

The results indicated that the layout having minimum CQ has the minimum total cost and the total cost of sewer layout generally increases with the CQ of a layout. It is also seen that the proposed modified PSO algorithm solution was better as compared to an original PSO algorithm in all the layouts for swarm size 1000. The minimum cost obtained by the original PSO is Rs. 8.473 × 106, whereas the cost obtained by the Modified PSO is reduced to Rs. 8.371 × 106. The results showed that the ability of the proposed methods to optimally solve the problem of the layout and component size determination of sewer networks.