1 Introduction

Water is life, and the protection of the water resources of our planet is of key importance in order to achieve sustainable development and guarantee the well-being of the future generations. Within the water cycle, the rivers, the lakes and the sea are the final receivers of the waste water produced by human activity (both urban and industrial ones). In order to convert it into an effluent that can be returned to the water cycle with acceptable impact on the environment, waste water or sewage is treated to remove contaminants.

Meanwhile, the increasing population of the earth together with population movement due to immigration or urbanization leads to the necessity of redesigning existing or designing new waste water treatment networks. A lot of municipalities, prefectures or even states make plans for the future network based on estimated needs. This paper studies the network entities (pipes, treatment plants, distributed infrastructure) and offers a tool for future (re-)design through mathematical programming.

Relevant studies have been made in the past with [1] offering a detailed review of them. The different approaches include the minimization of the environmental impact and the maximization of system reliability and flexibility under uncertainty conditions. Especially, in [2], a siting model is introduced in order to locate waste water treatment facilities, and the concave cost of a treatment plant is approximated by a fixed-charge cost and one straight-line segment. Similarly, in [3], the regional waste water system is modeled as a fixed-charge network flow problem where the concave cost functions are practically linearized by using piecewise linearization. Estimating the system load in terms of population units at some target year in the future, the authors solve the linearized model for a specific region. Large gravity sewer networks are addressed in [4], where piecewise linearization is also applied on a non-linear convex function relating pipeline diameter and slope. The authors study the design only of a gravitational pipeline by combining linear programming with a diameter discretization heuristic approach. The current work resembles these studies with the main difference being that both gravitational and pumping pipelines together with distributed components are considered and all cost functions (construction and operational) of all network units are linearized by piecewise linearization.

Moreover, the optimization of the allocation and treatment of municipal waste water sludge within an existing network, as well as the optimal location(s) for new drying facilities in this chain, are addressed in [5]. The authors apply a mixed integer linear programming model, known as OPTIMASS, whereas in the current paper the waste water treatment plants’ location problem is modeled as a mixed integer non-linear problem (MINLP).

Furthermore, to deal with uncertainty, in [6], the authors introduce a multi-scale two-stage mixed integer stochastic (MSTMIS) model. The first stage involves long-term strategic decisions (location of the sludge processing center (SPC) and the type of waste water treatment Plant (WWTP)) and is solved by genetic algorithm. Through a sensitivity analysis, the most influential parameters are selected, and stochastic scenarios are generated in order to reach second-stage short-term decisions (amount of sludge transported from each city to the SPC, the revenue from reusing treated waste water and the compost sale). The model is implemented on a specific region with a 20-year projection and showed better solutions than if the long- and short-term decisions were made together using traditional optimization methods.

Some studies, such as [7] and [8], focus on the network inside an industry. The former study considers waste water and heat exchange networks design by applying a two-stage optimization approach minimizing total annual cost through a mixed integer non-linear programming (MINLP) formulation involving effluent streams containing multiple contaminants. The latter study considers distributed and centralized waste water treatment units, assessing their environmental and economic feasibility, through life cycle assessment (LCA) and life cycle costing (LCC) methods. The authors use a non-linear model to compute a combined network and compare it with a conventional waste water treatment system, where no distribution infrastructure is used. On the contrary, the herein paper addresses the combined generalized network design, including both urban and industrial clusters.

Other studies address the design of integrated water supply and waste water collection systems. In [9], a mixed scenario-based and probabilistic two-stage stochastic programming model is proposed, and it is solved by using the sample average approximation method, the Bezdek fuzzy clustering method and an accelerated Benders decomposition algorithm. In the same way, in [10], in order to deal with uncertainty, the authors propose a two-stage stochastic model, solved by a Lagrangian relaxation-based algorithm. These approaches seem to be quite efficient and suitable for this complicated problem, whereas they tend to be quite complicated and not easily applicable to various real world problems, as it is the case of the present method, which addresses only the waste water network. Similarly, the optimal location of waste water treatment plants, along with desalination and water reclamation plants, is studied in [11] through a MILP minimizing the annual total costs of the network. The model is applied to two Greek islands, which lack substantial freshwater, whereas in the current paper the mathematical formulation is implemented on a larger case study in Luxembourg.

Contrary to the centralized ones, distributed waste water treatment networks are dealt with in [12] and [13], where multi-component streams are considered in order to reduce the concentration of several contaminants in the waste water network. The authors introduce a search procedure by successively solving a relaxed linear model and the original non-convex non-linear problem in order to yield global or near global optimal solutions. Also, in [14], in order to avoid non-convex mathematical models, a typical complex distributed network superstructure is decomposed into a set of basic network superstructures, and the best treatment network design embedded in each of the basic network super structures is determined by solving a set of linear programming problems. These linear problems are generated from a structured non-convex mathematical model by fixing a small number of key problem variables. Distributed waste water treatment networks are addressed in [15], as well, where the authors propose easily applied methods, which can handle complicated examples for both single and multiple contaminant systems. Unlike these papers, in the current one both centralized and distributed components of the network are taken into consideration.

A lot of studies in the literature focus on the sewer pipeline network inside a residential area and do not consider regional design including treatment plants. As stated in [16], these problems are solved using meta-heuristic methods, such as genetic algorithms (GA) [17,18,19,20,21], simulated annealing (SA) [22], particle swarm optimization (PSO) [23, 24] and tabu search (TS) [25]. Cellular automata (CA) [26,27,28] and ant colony (AC) [29] optimization techniques are applied in such studies, as well. However, the current paper does not deal with the dense local pipeline network, but the regional pipes which end up at the treatment plants.

The herein paper deals with the strategic design of a waste water treatment network (WWTN) in a region for a specific future projection. It considers allocation of waste water treatment plants (WWTPs), their gravitational or pumping pipeline connection with residential and industrial areas and the potential integration of two distributed waste water treatment components, micro-filtration (MF) and reverse osmosis (RO). Based on the current population and surface of a region, an estimation is made in order to compute the future population and surface and thus the future waste water production. The overall design time horizon is discretized into shorter time intervals in order to be able to estimate the gradual development of the network. The problem, which involves concave cost functions as well as penalty cost functions of abandoning existing network components, is formulated as a mixed integer non-linear problem (MINLP) that is linearized using piecewise linearization.

The rest of the paper is organized as follows: Sect. 2 describes the methodology and the non-linear cost functions included. Afterwards, the MINLP formulation and its linearization approach are presented in Sect. 3. Following, the case study, where the method is applied and the computational results are displayed in Sect. 4. Finally, Sect. 5 concludes the papers and offers suggestions for future research.

2 Methodology-Cost Functions

Before applying the mathematical formulation on a given region, preprocessing calculations are made in order to compute the model’s parameters. Most of the equations used are derived from the literature, and, for better clarification, they are presented in tables together with the identification of the parameters involved.

2.1 Calculation of Projected Waste Water Production

For the estimation of the future waste water production, the region under study is divided into clusters. Each cluster contains a community, such as a city/town, a village, smaller residential areas or industrial areas.

The main idea for this computation is that, having taken into consideration the current population and the area of each cluster, a projection is made in order to compute the estimated population and area after a specific number of years. Afterwards, the mean daily waste water production per inhabitant leads to its peak production during the day from the estimated population. This value together with the total infiltration flows in the estimated cluster area is taken into account for the computation of the total amount of waste water that is produced by each cluster. To this goal, the equations used for each cluster are presented in Table 1.

Table 1 Equations for the calculation of the projected waste water production
Full size table

2.2 Cost Functions

The waste water network under study consists of three major components: (a) the waste water treatment plants (WWTPs), (b) the pipelines connecting the clusters with the WWTPs, (c) distributed components and specifically micro-filtration (MF) and reverse osmosis (RO). For all these components, installation/expansion and maintenance costs are considered. The selected model coefficients herein are empirical, based on [35] and [36], where one can find cost functions expressing the effects of design flow and treatment level on construction costs, through the analysis of 55 municipal WWTPs in the context of a case experimental study.

2.2.1 Cost of WWTPs

The waste water treatment plants are basically of 2 types: mechanical and biological. It should be noted that the mechanical sewage treatment plants are usually composed by a setting pond, where the heavier components in the waste water are being ground as sewage sludge. The mud disassembles itself biochemically, whereas a biological sewage treatment plant uses natural microorganisms, usually plants or bacteria, which feed on the wastes in the water. Thus, the wastes are devoured in this way by the bacteria. For a biological WWTP, the respective overall cost is 30% of the cost of a corresponding mechanical WWTP which attains a similar degree of treatment either a secondary or a tertiary one for the purpose of comparison [37]. The used equations are depicted in Table 2.

Table 2 Construction/expansion and maintenance cost functions of waste water treatment plants
Full size table

2.2.2 Pipeline Cost

For the construction of a pipeline between a cluster \(i\) and a WWTP \(j\), two types of connections are considered, the gravitational one and the pumping one. In order keep the computation simple, no detailed terrain following has been considered, but only the altitude difference \(\Delta h\) between the two edges of the connection. Thus, if the cluster i is at a higher altitude than a WWTP j (\(\Delta h>0\)), then their pipeline connection would be gravitational. On the other hand, if the cluster i is at a lower altitude than a WWTP j (\(\Delta h<0\)), then their pipeline connection would be a pumping one. In this case apart from the pumping pipeline, the installation and maintenance of the required pumps are considered. Obviously, the installation costs for the existing gravitational and pumping connections of the network are assumed to be zero. The used equations are depicted in Table 3.

Table 3 Construction and maintenance cost functions of pipeline connections between clusters and waste water treatment plants
Full size table

2.2.3 Cost of MF and RO Systems

In the current paper, two distributed network components are taken into consideration, the micro-filtration (MF) and reverse osmosis (RO) systems. These systems can be installed in households and reduce the amount of waste water exiting each household and ending up to a WWTP by 59% as per the results of the present study. As shown in Eq. (18), based on the literature, the installation cost of such systems was initially derived in US$ from 2000. Taking into consideration the inflation rate from 2000 to present and the current exchange rate between US$ and € and in order to compute all costs corresponding to the same measurement unit of the amount of waste water (\({\mathrm{m}}^{3}/\mathrm{h}\)) in current value, Eq. (18) is transformed into Eq. (19). Also, concerning the annual operation and maintenance cost of the MF and RO systems, according to results of the authors’ unpublished study, it is assumed to be 8% of their respective installation cost. The used equations are depicted in Table 4.

Table 4 Installation and maintenance cost functions of micro-filtration (MF) and reverse osmosis (RO) systems
Full size table

3 Mathematical Model

3.1 Non-Linear Original Problem (NLOP)

The problem of Waste Water Treatment Network Design (WWTND) is formulated as a mixed-integer non-linear problem (MINLP), thus a non-linear original problem (NLOP) due to the non-linear costs of expansion and of operational and maintenance (O&M) of WWTPs and MF and RO systems. For the mathematical model, the following notation was used:

  • Indices:

    • \(\mathrm{I}:\) set of clusters (index i);

    • \(\mathrm{J}:\) set of locations of waste water treatment plant (index j);

    • \(\mathrm{P}:\) set of types of WWTPs (p = 0 =  > mechanical, p = 1 =  > biological)

    • \(\mathrm{T}:\) set of time periods.

  • Input parameters-data:

    • \({\overline{WWP} }_{it}:\) waste water production of cluster i in time period t (m3/h).

    • \({\overline{CE} }_{p}:\) cost of expansion of a WWTP of type p per amount of waste water treatment capability (€/m3);

    • \({\overline{CM} }_{p}:\) cost of maintenance of a WWTP of type p per amount of waste water treatment capability (€/m3);

    • \({\overline{CP} }_{ij}:\) cost of construction of a pipeline from cluster i to WWTP j per amount of waste water treatment capability (€); the cost is set to 0 for existing pipelines.

    • \({\overline{CPM} }_{ij}:\) cost of maintenance of a pipeline from cluster i to WWTP j per amount of waste water treatment capability (€);

    • \({\overline{Pipe} }_{ij}:\) binary parameter that takes the value of 1 if the cluster i is already connected with WWTP j in the beginning of the design time horizon and 0 otherwise;

    • \({\overline{CPA} }_{ij}:\) penalty cost of abandoning an existing pipeline between cluster i to WWTP j (€);

    • \({\overline{CA} }_{j}:\) penalty cost of abandoning an existing WWTP j(€);

    • \({\overline{QE} }_{j}:\) continuous parameter that is equal to the waste water treatment capability of the existing WWTP at location j in the beginning of the design time horizon (i.e. the amount of waste water that can be treated in it (m3/h));

    • \({\overline{Type} }_{j}:\) general integer parameter that is equal to the type of the WWTP at location \({\stackrel{-}{J.(Type}}_{j}=0mechanical, {\overline{Type} }_{j}=1biological)\); this parameter is not directly used in the model but is utilized in a preprocessing procedure in order to compute the rest of the parameters for each WWTP.

    • \(\overline{CINMFRO }:\) cost of installation of MF and RO systems per m3/h of waste water saved (€/m3*h).

    • \(\overline{COMMFRO }:\) cost of operation/maintenance of MF and RO systems per m3/h of waste water saved (€/m3*h).

    • \({\overline{PCHouse} }_{i}:\) percentage of households in cluster i (%).

    • \(\overline{PCSave }:\) percentage of waste water that is saved if MF and RO system is applied (%).

    • \(\overline{BigM }:\) a very large number.

  • Decision variables:

    • \({x}_{ijt}:\) binary variable that takes the value of 1 if cluster (i) is decided to be connected with the WWTP j in period t and 0 otherwise (-);

    • \({u}_{ij}:\) binary variable that takes the value of 1 if a pipeline connection is constructed between cluster (i) and WWTP (j) during the whole time horizon and 0 otherwise (-);

    • \({v}_{ij}:\) binary variable that takes the value of 1 if an existing pipeline connection between cluster (i) and WWTP (j) is abandoned during the time horizon and 0 otherwise (-);

    • \({z}_{ijt}:\) continuous variable that equals the amount of waste water transferred from cluster (i) to WWTP (j) in period t (m3/h);

    • \({q}_{jt}:\) continuous variable that equals the expansion needed to be made at WWTP (j) in period t in terms of additional amount of waste water that can be treated in it. (m3/h);

    • \({y}_{jt}:\) binary variable that takes the value of 1 if a WWTP exists at location (j) in period t and 0 otherwise (-);

    • \({r}_{jt}:\) continuous variable that takes the value of the final capability (after expansion or closure) of WWTP (j) in period t in terms of the final amount of waste water that can be treated in it (m3/h).

    • \({m}_{j}:\) binary variable that takes the value of 1 if an existing WWTP (j) is abandoned during the time horizon and 0 otherwise (-);

    • \({s}_{i}:\) continuous variable that equals the maximum waste water of cluster (i) that is saved due to the installation of MF and RO (m3/h).

    • \({p}_{it}:\) continuous variable that equals the waste water of cluster (i) that is saved in period t due to the operation of MF and RO (m3/h).

The non-linear original problem (NLOP) is formulated as follows:

Objective function:

$$\begin{aligned}\mathbf{M}\mathbf{i}\mathbf{n}\mathbf{i}\mathbf{m}\mathbf{i}\mathbf{z}\mathbf{e} \sum_{i\in I}\sum_{j\in J}{\overline{CP} }_{ij}*{u}_{ij}&+\sum_{t\in T}\sum_{i\in I}\sum_{j\in J}{\overline{CPM} }_{ij}*{x}_{ijt}+\sum_{t\in T}\sum_{p\in P}\sum_{j\in J}{\overline{CE} }_{p}*{q}_{jt}^{0.71}\\&+\sum_{t\in T}\sum_{p\in P}\sum_{j\in J}{\overline{CM} }_{p}*{r}_{jt}^{0.352}+\sum_{i\in I}\overline{CINMFRO }*{s}_{i}^{0.87}\\&+\sum_{t\in T}\sum_{i\in I}\overline{COMMFRO }*{p}_{it}^{0.87}+\sum_{i\in I}\sum_{j\in J}{\overline{CPA} }_{ij}*{v}_{ij}\\&+\sum_{j\in J}{\overline{CA} }_{j}*{m}_{j}\end{aligned}$$
(21)

Subject to:

$$\sum_{j\in J}{x}_{ijt}\ge 1 \forall i\in I,t\in T$$
(22)
$${u}_{ij}\ge {x}_{ijt} \forall i\in I,j\in J,t\in T$$
(23)
$${v}_{ij}\ge {\overline{Pipe} }_{ij}-{x}_{ijt} \forall i\in I,j\in J,t\in T$$
(24)
$$\sum_{j\in J}{z}_{ijt}\ge {\overline{WWP} }_{it}-{p}_{it} \forall i\in I,t\in T$$
(25)
$$\sum_{i\in I}{z}_{ij1}\le {\overline{QE} }_{j}*{y}_{j1}+{q}_{j1} \forall j\in J$$
(26)
$$\sum_{i\in I}{z}_{ijt}\le {\overline{QE} }_{j}*{y}_{j1}+{q}_{jt-1}+{q}_{jt}+BigM*(1-{y}_{jt}) \forall j\in J,t\ge 2$$
(27)
$${z}_{ijt}\le {\overline{WWP} }_{it}*{x}_{ijt} \forall i\in I,\forall j\in J,t\in T$$
(28)
$${x}_{ijt}\le {y}_{jt} \forall i\in I,\forall j\in J,t\in T$$
(29)
$${q}_{jt}\le \left(\sum_{i\in I}{\overline{WWP} }_{it}-{\overline{QE} }_{j}\right)*{y}_{jt} \forall j\in J,t\in T$$
(30)
$${r}_{j1}\ge {\overline{QE} }_{j}*{y}_{j1}+{q}_{j1} \forall j\in J$$
(31)
$${r}_{jt}\ge {r}_{jt-1}+{q}_{jt}-BigM*(1-{y}_{jt}) \forall j\in J,t\ge 2$$
(32)
$${q}_{jt}\ge {r}_{jt}-{r}_{jt-1} \forall j\in J,t\ge 2$$
(33)
$${y}_{jt}\le \left(1/BigM\right)*{r}_{jt} \forall j\in J,t\ge 2$$
(34)
$${m}_{j}\ge (1-{y}_{jt}) \forall j\in J,t\in T$$
(35)
$${p}_{it}\le \overline{PCSave }*{\overline{PCHouse} }_{i}*{\overline{WWP} }_{it}\forall i\in I,t\in T$$
(36)
$${s}_{i}\ge {p}_{it}\forall i\in I,t\in T$$
(37)
$${x}_{ijt}\in \left\{0, 1\right\} \forall i\in I,j\in J,t\in T$$
(38)
$${y}_{jt}\in \left\{0, 1\right\} \forall j\in J,t\in T$$
(39)
$${u}_{ij},{v}_{ij}\in \left\{0, 1\right\} \forall i\in I,j\in J$$
(40)
$${w}_{j}\in \left\{0, 1\right\} \forall j\in J$$
(41)
$${z}_{ijt}\ge 0 \forall i\in I,j\in J,t\in T$$
(42)
$${q}_{jt},{r}_{jt}\ge 0 \forall j\in J,t\in T$$
(43)
$${p}_{it}\ge 0 \forall i\in I,t\in T$$
(44)
$${s}_{i}\ge 0 \forall i\in I$$
(45)

The objective function (21) is a minimization of the total cost of the network during the whole time horizon under study (e.g. for 50 years). The first term of the objective function is the total construction cost for all the pipelines, either gravitational or pumping, and all the pumping stations that will be needed in the network. It should be noted that for the existing pipelines and pumping stations, the construction cost is set to zero in the corresponding parameter’s value (i.e. \({\overline{CP} }_{{i}^{^{\prime}}{j}^{^{\prime}}}=0\), if cluster \({i}^{^{\prime}}\) is already connected with WWTP \(\left({j}^{^{\prime}}\right)\).The second term of the objective function is the total operational and maintenance cost for all the pipelines, either gravitational or pumping, and all the pumping stations that will be needed in the network. The third term is the total non-linear expansion cost of the waste water treatment plants (WWTPs). The fourth term is the total non-linear operational and maintenance cost of the WWTPs. The fifth and the sixth terms of the objective function is the total non-linear installation and operational and maintenance cost of micro-filtration (MF) and reverse osmosis (RO) systems that might be installed in the clusters respectively. The seventh term of the objective function is the penalty cost of abandoning an existing pipeline between cluster (i) to WWTP (j). Finally, the eighth term of the objective function is the penalty cost of abandoning an existing WWTP (j).

Constraint (22) guarantees that in every time period t, each cluster i will be linked with a WWTP j. Constraint (23) guarantees that if there is a pipeline connection between cluster i and WWTP (j) in a time interval during the time horizon, then variable \({u}_{ij}\) takes the value of 1. Constraint (24) guarantees that variable \({v}_{ij}\) will take the value of 1 if an existing pipeline connection between cluster (i) and WWTP (j) is abandoned during the time horizon. Constraint (25) guarantees that in every time period t for each cluster i the total amount of waste water transferred to WWTPs will be at least its waste water production minus the amount of waste water that is saved due to the use of MR and RO systems inside the cluster. Constraint (26) guarantees that in the first time period for each WWTP its initial capability plus its expansion will be at least equal to the total amount of waste water transferred to it from all clusters. Constraint (27) guarantees that in the time periods after the first one for each WWTP its capability in the previous time period plus its current expansion will be at least equal to total amount of waste water transferred to it from all clusters. Constraint (28) guarantees that in every time period t no amount of waste water will be transferred from i to j if a connection between them does not exist. Also, with this constraint, an upper bound is enforced on the amount to be transferred from i to j, which cannot be larger than the waste water produced in cluster i. Constraint (29) guarantees that in every time period t no connection between i and j is established if a WWTP at j does not exist in this time period. Constraint (30) guarantees that no expansion is made at j if a WWTP at j does not exist. Also, with this constraint, an upper bound is enforced on the expansion capability of every WWTP which cannot be larger than the total waste water produced in all clusters minus the initial capability of the WWTP. Constraint (31) guarantees that in the first time period for each WWTP its final capability will be at least equal to its initial capability plus its expansion. Constraint (32) guarantees that in the time periods after the first one for each WWTP its final capability will be at least equal to its capability in the previous time period plus its current expansion. The constraint is relaxed if the WWTP (j) does not exist in this time period. Constraint (33) guarantees that in the time periods after the first one for each WWTP its current expansion will be at least equal to its current capability minus its capability in the previous time period. Constraint (34) guarantees that in all time periods if a WWTP exists, then it must have a non-zero capability. Constraint (35) guarantees that variable \({w}_{j}\) will take the value of 1 if a WWTP (j) is abandoned during the time horizon. Constraint (36) guarantees that for each cluster the quantity of WWP that is not dropped in the network, after the installation of MF and RO systems, is not greater than the percentage of households multiplied by the percentage of WWP that can be saved in each household. Constraint (37) assigns to variable \({s}_{i}\) for every cluster i the maximum value of variables \({p}_{it}\) in order to identify the maximum capacity of MF and RO systems installed in every cluster during the whole time horizon. Constraints (38)–(45) declare the variables’ bounds.

3.2 Piecewise Linearization

3.2.1 Background

In the mathematical model presented in the previous section, the goal is to minimize a non-linear concave objective function with linear constraints. An overview of the principals and the various approaches of non-linear optimization can be found at [38]. One of the methods used to solve non-linear problems is to divide the non-linear functions into several linear sections (piecewise linearization). A review on such methods can be found in [39]. The advantage of this approach is that it results into a linear problem to which any linear programming algorithm can be applied.

For the needs of the piecewise linearization, a set of variables known as a special ordered set of type 1 (SOS1) were proposed by [40] and initially implemented by [41]. These variables are set with at most one nonzero component.

In the current paper, the special ordered set of variables of type 2 (SOS2), introduced by [42], were implemented. The SOS2 variables are continuous variables between 0 and 1, whose summation equals to 1.

This variant was chosen because it has the advantage that it does not rely on equal grid spacing. Thus, it offers the possibility to create finer grids in the area where the cost function’s gradient is steeper (i.e. in its smaller values) and wider grids in the area where the cost function’s gradient is smoother (i.e. in its larger values).

This method guarantees a global optimum solution only for maximization problems when the function to be maximized is concave or for minimization problems when the function to be minimized is convex. However, in our case, the mathematical model is a minimization of a concave objective function (Eq. (21)) and in order to better approximate it, restricted basis entry constraints are needed. As explained at [43], these constraints guarantee that at most two SOS2 variables will be positive, and if two are positive, they must be adjacent.

In order to better illustrate the necessity of these constraints, Fig. 1 depicts the piecewise linearization of a minimization of a concave function, like the terms of the objective function (21). If no restricted basis entry constraints are used, the solution would be

$${x}^{*}={w}_{1}{a}_{1}+{w}_{4}{a}_{4} \mathrm{\ and}\ f\left({x}^{*}\right)={f}_{1}$$
(46)

but this is incorrect because w1 and w4 are not adjacent and therefore \(f({w}_{1},{w}_{4})\) is not a good approximation of \(f\left(x\right)\). Restricted basis entry will prevent such solutions by forcing at most two SOS2 variables to be positive, and if two are positive, guarantee that they are adjacent. Thus, the optimal solution would be

$${x}^{*}={w}_{2}{a}_{2}+{w}_{3}{a}_{3} \mathrm{\ and}\ f\left({x}^{*}\right)={f}_{2}.$$
(47)

Obviously, from Fig. 1 one can notice that \({f}_{2}\) is a much better approximation of \(f\) than \({f}_{1}\), since the error between the blue and the black line is much smaller than the error between the green and the black line.

Fig. 1
figure 1

Piecewise linearization of a concave function to be minimized with (blue line) and without (green line) restricted basis entry constraints

Full size image

3.2.2 Piecewise Linearization in WWTND

As previously explained, in the current model the piecewise linearization by exploiting SOS2 variables with restricted basis entry constraints is applied. In order to implement the latter constraints, additional auxiliary binary variables are used [39]. So, for the linearized original problem (LOP), the following notation has to be added:

  • Indices:

    • \(B:\) set of intervals (boxes) used for the piecewise linearization (index b);

  • Input parameters−data:

    • \(\overline{{awq }_{b}}:\) general integer parameter that is equal to the value of WWTP’s expansion capability at interval b (for the expansion cost of WWTPs);

    • \(\overline{a{wr }_{b}}:\) general integer parameter that is equal to the value of WWTP’s total capability at interval b (for the O&M cost of WWTPs).

    • \(\overline{a{wp }_{b}}:\) general integer parameter that is equal to the value of MF and RO capability at interval b (for the installation and O&M cost of MF and RO).

    • \(\overline{{CE }_{bp}}:\) cost of expansion of a WWTP of type p corresponding to the capability expansion \(\overline{{awq }_{b}}\) in the interval b of the piecewise linearization (€);

    • \(\overline{{CM }_{bp}}:\) cost of maintenance of a WWTP of type p corresponding to the total capability \(\overline{a{wr }_{b}}\) in the interval b of the piecewise linearization (€);

    • \(\overline{{CINMFRO }_{b}}:\) cost of installation of MF and RO per m3/h of WW saved corresponding to the capability \(\overline{a{wp }_{b}}\) of the MF and RO in the interval b of the piecewise linearization (€).

    • \(\overline{{COMMFRO }_{b}}:\) cost of operation/maintenance of MF and RO per m3/h of WW saved corresponding to the capability \(\overline{a{wp }_{b}}\) of the MF and RO in the interval b of the piecewise linearization (€).

  • Decision variables:

    • \({wq}_{bjt}:\) continuous variable between 0 and 1 (SOS2 variable) that corresponds to the expansion made of WWTP at location j in period t in interval b of capability. (-)

    • \({wr}_{bjt}:\) continuous variable between 0 and 1 (SOS2 variable) that corresponds to the total capability of WWTP at location j in period t in interval b of capability. (-)

    • \({wp}_{bit}:\) continuous variable between 0 and 1 (SOS2 variable) that corresponds to the MF and RO capability at cluster (i) in period t in interval b of capability. (-)

    • \({ws}_{bi}:\) continuous variable between 0 and 1 (SOS2 variable) that corresponds to the maximum MF and RO capability at cluster (i) in interval b of capability. (-)

    • \({int\_wq}_{bjt}:\) binary variable that is equal to 1 if the corresponding SOS2 variable \({wq}_{bjt}\) is greater than 0 and 0 otherwise (-). Auxiliary variable in order to implement restricted basis entry constraints.

    • \({int\_wr}_{bjt}:\) binary variable that is equal to 1 if the corresponding SOS2 variable \({wr}_{bjt}\) is greater than 0 and 0 otherwise (-). Auxiliary variable in order to implement restricted basis entry constraints.

    • \({int\_wp}_{bit}:\) binary variable that is equal to 1 if the corresponding SOS2 variable \({wp}_{bit}\) is greater than 0 and 0 otherwise (-). Auxiliary variable in order to implement restricted basis entry constraints.

    • \({int\_ws}_{bi}:\) binary variable that is equal to 1 if the corresponding SOS2 variable \({ws}_{bi}\) is greater than 0 and 0 otherwise (-). Auxiliary variable in order to implement restricted basis entry constraints.

The linearized original problem (LOP) is formulated as follows:

Objective function:

$$\begin{aligned}\mathbf{M}\mathbf{i}\mathbf{n}\mathbf{i}\mathbf{m}\mathbf{i}\mathbf{z}\mathbf{e}\sum_{t\in T}\sum_{i\in I}\sum_{j\in J}{\overline{CP} }_{ij}*{x}_{ijt}&+\sum_{t\in T}\sum_{i\in I}\sum_{j\in J}{\overline{CPM} }_{ij}*{x}_{ijt}+\sum_{b\in B}\sum_{t\in T}\sum_{p\in P}\sum_{j\in J}\overline{{CE }_{bp}}*{wq}_{bjt}\\&+\sum_{b\in B}\sum_{t\in T}\sum_{p\in P}\sum_{j\in J}\overline{{CM }_{bp}}*{wr}_{bjt}+\sum_{b\in B}\sum_{i\in I}\overline{{CINMFRO }_{b}}*{ws}_{bi}\\&+\sum_{b\in B}\sum_{t\in T}\sum_{i\in I}{\overline{COMMFRO} }_{b}*{wp}_{bit}+\sum_{i\in I}\sum_{j\in J}{\overline{CPA} }_{ij}*{v}_{ij}\end{aligned}$$
(48)

Subject to:

Constraints (22)–(45) and the following constraints:

$$\sum_{b\in B}\overline{{awq }_{b}}*{wq}_{bjt}={q}_{jt} \forall j\in J,t\in T$$
(49)
$$\sum_{b\in B}\overline{{awr }_{b}}*{wr}_{bjt}={r}_{jt} \forall j\in J,t\in T$$
(50)
$$\sum_{b\in B}\overline{{awp }_{b}}*{wp}_{bit}={p}_{it} \forall i\in I,t\in T$$
(51)
$$\sum_{b\in B}\overline{{awp }_{b}}*{ws}_{bi}={s}_{i} \forall i\in I$$
(52)
$$\sum_{b\in B}{wq}_{bjt}=1 \forall j\in J,t\in T$$
(53)
$$\sum_{b\in B}{wr}_{bjt}=1 \forall j\in J,t\in T$$
(54)
$$\sum_{b\in B}{wp}_{bit}=1 \forall i\in I,t\in T$$
(55)
$$\sum_{b\in B}{ws}_{bi}=1 \forall i\in I$$
(56)
$${wq}_{bjt}\le {int\_wq}_{bjt} \forall j\in J, b\in B,t\in T$$
(57)
$${wr}_{bjt}\le {int\_wr}_{bjt} \forall j\in J, b\in B,t\in T$$
(58)
$${wp}_{bit}\le {int\_wp}_{bit} \forall i\in I, b\in B,t\in T$$
(59)
$${ws}_{bi}\le {int\_ws}_{bi}\ \forall i\in I, b\in B$$
(60)
$$\sum_{b\in B}{int\_wq}_{bjt}\le 2\ \forall j\in J,t\in T$$
(61)
$$\sum_{b\in B}{int\_wr}_{bjt}\le 2\ \forall j\in J,t\in T$$
(62)
$$\sum_{b\in B}{int\_wp}_{bit}\le 2\ \forall i\in I,t\in T$$
(63)
$$\sum_{b\in B}{int\_ws}_{bi}\le 2\ \forall i\in I$$
(64)
$${int\_wq}_{bjt}+{int\_wq}_{b+njt}\le 1\ \forall j\in J,t\in T, b\in [1,B-2], n\in [2,B-b]$$
(65)
$${int\_wr}_{bjt}+{int\_wr}_{b+njt}\le 1\ \forall j\in J,t\in T, b\in [1,B-1], n\in [2,B-b]$$
(66)
$${int\_wp}_{bit}+{int\_wp}_{b+njt}\le 1\ \forall i\in I,t\in T, b\in [1,B-2], n\in [2,B-b]$$
(67)
$${int\_ws}_{bi}+{int\_ws}_{b+ni}\le 1\ \forall i\in I, b\in [1,B-1], n\in [2,B-b]$$
(68)
$$0\le {wq}_{bjt},{wr}_{bjt}\le 1,\ \forall b\in B,j\in J,t\in T$$
(69)
$$0\le {wp}_{bit}\le 1,\ \forall b\in B,i\in I,t\in T$$
(70)
$$0\le {ws}_{bi}\le 1,\ \forall b\in B,i\in I$$
(71)
$${int\_wq}_{bjt},{int\_wr}_{bjt}\in \left\{0, 1\right\}\ \forall b\in B,j\in J,t\in T$$
(72)
$${int\_wp}_{bit}\in \left\{0, 1\right\}\ \forall b\in B,i\in I,t\in T$$
(73)
$${int\_ws}_{bi}\in \left\{0, 1\right\}\ \forall b\in B,i\in I$$
(74)

In the objective function (48), the third, fourth, fifth and sixth terms, which were previously non-linear, have been linearized by using piecewise linearization with SOS2 variables. Constraints (49) and (50) guarantee that in every time period expansion capability and the total capability, respectively, of each WWTP will be equal to the weighted summation of the multiplication of the SOS2 variables with the capability value of the corresponding interval b. Similarly, constraints (51) and (52) guarantee that the MF and RO capability in every time period and their maximum value in the whole time horizon, respectively, will be equal to the weighted summation of the multiplication of the SOS2 variables with the capability value of the corresponding interval b. Constraints (53)–(56) guarantee that the summation of the corresponding SOS2 variables will be equal to 1.

Constraints (57)–(60) guarantee that if a SOS2 variable is greater than 0, then the corresponding integer SOS2 variable will be equal to 1. These constraints are necessary for the following restricted basis entry constraints (61)–(68). Constraints (61)–(64) guarantee that no more than two SOS2 variables are greater than 0, and constraints (65)–(68) guarantee that these two non-zero SOS2 variables are adjacent. Constraints (69)–(74) declare the variables’ bounds.

4 Numerical Results

4.1 Case Study

The present model has been applied in order to optimize the existing waste water network of Luxembourg in the local and national scale. An optimal re-location of existing waste water plants network for potable water supply in Luxembourg is examined. Potable water production in Luxembourg is sourced 2/3 by ground water and 1/3 by surface water. Ground water is obtained from springs and wells [44]. Surface water is obtained by treating the waste waters in waste water plants. This water is mixed before being delivered to the customer. The main problem consists of increasing the rate of surface water in this mixture for reducing the ground water consumption, while maintaining the quality of the water.

The area under study consists of 20 residential-industrial areas belonging in the provinces of Mersch, Redange and Capellen. These 20 clusters are currently connected to 24 different mechanical and biological waste water treatment plants (WWTPs), as shown in Fig. 3.

The overall design time horizon is considered to be 50 years, which are split in 5 time intervals of 10 years each. Thus, the solution of the mathematical model will describe how the waste water network should be like at the end of each of the next 5 decades.

In Fig. 2, the initial population in year 2017 in all 20 clusters together with its projection for the next 5 decades is depicted. Similarly, a projection is made for the estimation of future developed surface of each cluster. The previous computations are made by using the equations presented in Sect. 2.1 with the final goal to compute the estimated waste water production of each of the 20 clusters in every of the next 5 decades.

Fig. 2
figure 2

The estimated population projection for the area under study

Full size image

By using the equations presented in Sect. 2.2, the construction/establishment/expansion cost of the network elements (WWTPs, pipelines, micro-filtration and reverse osmosis systems) is calculated. Also, their maintenance cost is determined for each of the next 5 decades, should they be active. Moreover, a penalty cost is computed for abandoning an existing WWTP or a pipeline connection. This penalty cost takes into account the special characteristics of the existing WWTP (waste water treatment capability) and pipeline (length, gravitational/pumping etc.) and is considered to be equal to 1/10 of the respective construction cost, which would be needed to invest in order to establish a similar facility.

As regards the distributed components of the network, 4 different scenarios of percentage of incorporating microfiltration (MF) and reverse osmosis (RO) systems within each examined cluster were considered (0% incorporation, 25% incorporation, 50% incorporation, 100% incorporation). It should be noted that this use refers to integrating such systems only to residential buildings which correspond to a typical household of 4 users.

Table 5 shows the clusters under study in the order of increasing percentage of households within each cluster. Columns 3, 4, 5 and 6 contain the percentage of reduction of waste water that ends up to the network when MF and RO systems are incorporated in household buildings in the clusters (4 scenarios of incorporating percentage). It can be easily noticed that in each cluster the more the distributed systems are integrated the bigger the reduction in waste water conveyed through the pipeline network to the WWTPs. Moreover, comparing different clusters with each other, one can observe that the more the percentage of households in a cluster the bigger the reduction in waste water produced. This means that such systems are preferable to be installed in clusters with high residential rate.

Table 5 Percentage of reduction of waste water that ends up to the network when MF and RO systems are incorporated in household buildings in the clusters (4 scenarios of incorporating percentage)
Full size table

5 Results

The model incorporating the MF and RO systems, presented in Sect. 3.2, was coded in C +  + applying CPLEX 12.10 optimizer in Visual Studio 2019. The instance was solved in a PC with Windows10 (64-bit), Intel Core i7 and 16 Gb RAM. The solution method used was the default setting of CPLEX. In this case CPLEX automatically selects an optimizer (primal simplex, dual simplex, barrier, network, sifting and concurrent optimizers), based on the characteristics of the problem. In our case, CPLEX chose the network optimizer, which is more suitable for network-flow problems.

Due to the size of the model with a large number of decision variables and constraints, a time limit of 10-h solution time was set. In this duration, a feasible solution with optimality gap 12.4% was derived. It should be noted that the main reason for the high CPU time needed to solve the model to optimality is the existence of 8 cost terms in the objective function. Each of these terms has different orders of magnitude. This results into an exponential number of feasible solutions, which have to be checked in the solution process in order to define the optimal one. In the early stages of the solution process, a feasible solution is found really quickly, and the optimality gap is dropped fast by focusing on the optimization of the terms with the higher order of magnitude. In the last stages of the solution process, a total cost refinement is attempted with the optimality gap improving in a very low rate. Overall, the 10-h limit is acceptable for this kind of network design problems, since it is not a problem that needs to be solved every day. Moreover, the optimality gap of 12.4% is also acceptable, since the most important network elements have been defined in such a solution, and only small refinements remain to be made.

In Table 6, the waste water treatment plants of the network are depicted together with their capability in m3/h. In column 4 of the table, their current capability is presented, and in the next columns the model’s solution is shown. One can notice that even from the end of the 1st decade (2027), only 3 WWTPs remain in use, and for the 2 of them their capability is gradually increased in the following decades. All the rest WWTPs are abandoned. Most of the abandoned WWTPs are the ones with the least capability, since the respective penalty cost for them is considered to be lower than the penalty cost of abandoning a relatively bigger WWTP. In addition, biological WWTPs are preferred to mechanical ones thanks to the formers’ better efficiency (cost vs capability) explained in Sect. 2.2.1.

Table 6 Waste water treatment capability (in m.3/h) of each waste water treatment plant
Full size table

As regards the pipeline connections between the clusters (i) and WWTPs (j), they are differentiated in the 1st decade, and they remain pretty much the same for the following decades. This part of the model’s solution is directly related to the one with the WWTPs. Apparently, the overall cost to expand and maintain only 3 biological WWTPs and establish new pipeline connections between the clusters and the WWTPs is lower than the cost to expand and maintain all WWTPs with no need of new pipeline connections. This is mainly due to the non-linearity of expansion and maintenance cost of WWTPs, i.e. the bigger the WWTP the lower its cost per m3/h treated in it.

In Table 7, all proposed future connections between all clusters and all WWTPs at the end to the design time horizon (2067) are presented. In .

Table 7 Proposed future pipeline connections in 2067 between clusters i and WWTPs j
Full size table

Table 8, the colors used in Table 7 are explained.

Table 8 Explanation of colors in Table 7
Full size table

In order that the solution of the model is optically compared to the current waste water treatment network, Fig. 3 depicts the existing examined network on the map. The small or medium-sized communities are painted in yellow, and their shape follows the outline of each community according to surveying maps. These clusters are connected to either biological WWTPs being represented by the green circles or mechanical WWTPs represented by the corresponding red circles. The size of each circle is proportionate to its waste water treatment capability in terms of m3/h. One can notice that the mechanical WWTPs have relatively low capability, and for this reason the red circles are so small that are barely distinguished. Moreover, it can be seen that in the existing network all communities are connected to small-sized plants and only one community is connected to a central biological plant.

Fig. 3
figure 3

Current status of waste water network in the examined area

Full size image

Similarly, Fig. 4 presents the proposed future waste water network of the same examined area at the end of the design time horizon (2067) based on the optimal solution of the mathematical formulation presented in Sect. 3.2. This solution minimizes the construction and maintenance costs of the pipelines and the WWTPs, as expressed in the objective function (48). As in Fig. 3, the size of the green bubbles, representing the future treatment plants, is proportionate to their waste water treatment capability in terms of m3/h.

Fig. 4
figure 4

Proposed future status of waste water network based on model’s optimal solution

Full size image

It can be noticed that the analysis represents as the most preferable option the grouping of neighboring clusters to be served by central treatment plants of a much larger capacity. Moreover, one can observe that no mechanical plants are proposed to be used in the future, due to their increased cost per waste water treatment capability compared to the biological ones, as explained in Sect. 2.2.1. Furthermore, the proposed plants are among the ones with the lowest altitude, which leads to more gravitational pipelines needed than pumping ones, thus results in lower pipeline construction and maintenance cost.

Moreover, the optimal solution of the mathematical formulation proposes no integration of MF and RO systems in the future network, which is explained by their large cost compared to the relatively small reduction of the waste water reaching the rest of the network. This result indicates the necessity of increasing their efficiency, while decreasing their installation and maintenance cost.

6 Conclusion−Future Work

In this paper, the Waste Water Treatment Network Design problem with both centralized and distributed components is modeled as a non-linear problem. The overall design time horizon is discretized in time intervals, so that the proposed gradual development of the network can be described. The pre-processing methodology and equations used are concise, while the piecewise linearization of the mathematical formulation is computationally affordable and easily applicable.

The results on a case study in Luxembourg show that biological plants are preferred to the mechanical ones due to the formers’ increased efficiency. Also, a small number of large WWTPs is preferred to many small ones due to the non-linearity of the expansion and operation cost. The abandoned WWTPs are the ones with the smaller capability, since their abandoning penalty cost is lower. Central larger WWTPs situated in a lower topographical altitude are proposed so that their connection with the corresponding clusters with the use of gravitational pipelines is as much as possible. These gravitational instead of pumping connections are preferred by the model due to their lower cost. Finally, no distributed components of micro-filtration and reverse osmosis systems are proposed due to their low efficiency compared to their high cost. In general, the model simulates the actual network taking into account mostly the parameters and assumptions that have been predefined during pre-processing.

For future work, a sensitivity analysis on different cost parameters should be made in order to observe how the optimal solution is altered. Finally, a more precise estimation of the pipeline cost needs to be made, taking into consideration the analytical ground terrain connecting the clusters and the WWTPs and not just their altitude difference.