1 Introduction

The abstraction and distribution of water to the population consume energy and monetary resources. The energy required to pump and treat water constitutes one of the largest operational costs for water suppliers (Ramos et al. 2011; Fayzul et al. 2014). Approximately 2–3 % of the world’s energy is consumed in water and wastewater operations, i.e., abstraction, treatment, transport, distribution, use, and disposal (Olsson 2012). Hence, it is no surprise that with the growth of water consumption, energy needs will also grow (Keeling and Sullivan 2012). Population and urbanization are increasing worldwide, and to face the challenges due to the growing request for both resources and to reinforce the policies of sustainability, focus has been directed recently to the search for strategies to improve the efficiency of water systems.

This paper proposes a solution for improving the energy efficiency in water supply systems that considers the use of micro-turbines for electricity generation in water supply networks (WSNs). In WSNs, particularly in cities with considerable geodesic differences, areas exist where the pressure is greater than necessary. In certain cases, energy dissipation is imperative to minimize leakage (Carravetta et al. 2012; Carravetta et al. 2013; Xu et al. 2014; Fecarotta et al. 2015). This dissipation is usually ensured by pressure reduction valves. The replacement of these valves with micro-turbines could allow the use of energy that is otherwise dissipated (McNabola et al. 2014). The adaptation of water supply systems to produce energy has the advantage of leveraging components that already exist. Furthermore, continuous supply is guaranteed by consumption throughout the day (Ramos et al. 2010; Vieira and Ramos 2008; Kougias et al. 2014).

The choice of locations for the installation of micro-hydropower is not straightforward if one considers closed WSNs. The flow demand is highly variable, not only having a direct impact on the efficiency of the turbine but also on the distribution of the flow. Limitations on pressure imposed by regulators must also be respected.

Strategies can be found in the literature for locations to install turbines in water supply systems. Carravetta et al. 2012 proposed placement in the inlet nodes of network districts. Araújo et al. 2006 suggested identification of a number of nodes with energy potential within the entire network. Sitzenfrei and von Leon 2014 developed a complex methodology with different phases that combines GIS techniques and sensitivity analyses. The first suggestion limits the placement to a particular node, the other two imply long and time-consuming analyses.

The approach of using stochastic optimization algorithms has been investigated in WSNs design and location of control valves (Ramos et al. 2010; Araújo et al. 2006; Farmani et al. 2005; Cunha and Sousa 2001). Nevertheless, the use of these techniques for the current problem has not yet been thoroughly studied.

Stochastic methods in which the generation of solutions is based on random procedures are particularly suited for problems that do not have an exploitable structure (Pardalos et al. 2000). At each moment, these algorithms use the previously gathered information to decide which candidate solution should be tested in the next iteration. As a result, these approaches offer simple application and can be applied in many different types of discrete and continuous problems (Youssef et al. 2001).

Herein, the development of a novel technique to find the location of micro-turbines within a WSN which maximizes the annual energy production is presented. The technique consists on an algorithm created which is based on the simulated annealing strategy. A strategy for the application of micro-hydropower production in WSNs is thus proposed, addressing pressure constraints, flow variability and the complexity of the networks with closed loops.

The simulated annealing approach is a heuristic strategy that has proven to be robust and versatile (Rutenbar 1989; Youssef et al. 2001). A brief review of this technique together with its implementation on the particular model of WSNs is presented in Section 2. To test the performance of the algorithm, a study was developed in a sub-grid of the Lausanne WSN presented in Section 3. Section 4 defines the main function of the model based on testing with one, two and three turbines. Finally, the main conclusions are drawn in Section 5.

2 Model

2.1 Working Principles

The goal of the model herein developed is to optimize the location of a chosen number of turbines in a network. This goal is achieved by applying a simulated annealing process coupled with a hydraulic solver to maximize the energy production through the minimization of a cost function defined as

$$ f(X)=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{${\displaystyle {\sum}_{t=1}^T{E}_t(X)}$}\right. $$
(1)

where X(x 1, …, x n ) is a vector with the position of n turbines in the network, and E t (kWh) is the energy produced during the t th hour for a total simulation time of T:

$$ {E}_t(X)=\rho g{\displaystyle \sum_{n=1}^N{\eta}_{tgn}{\eta}_{fn}{Q}_n{H}_n\varDelta t} $$
(2)

where g is the gravitational acceleration (m/s2), ρ is the water density (kg/m3), Δt is the time step (h), N is the number of turbines and, for each turbine, Qn (m3/s) is the nominal turbinated flow, Hn (m) is the available head, and η tgn and η fn are the turbine and the generator efficiencies, respectively.

The cost function of each tested solution is obtained by the flow and head drop at each turbine calculated from the hydraulic state of the network in each t th hour. The hydraulic state of the WSN is calculated using the commercial software EPANET 2.0 (Rossman 2000). Each turbine was simulated as a singular energy drop whose head-loss coefficient is calculated as a function of the turbine characteristic curve.

Simulated annealing is a probabilistic method based on the process of heating of steel and ceramics and consists of a discrete-time inhomogeneous Markov chain (Bertsimas and Tsitsikis 1993). A Markov chain is a sequence of random variables in which each variable depends only on the state of the system in the previous iteration. Moreover, simulated annealing is not a pre-defined mechanical sequence of computations but a strategy for solving combinatorial optimization problems (Rutenbar 1989).

The method begins with an initial feasible solution, in this case it is a particular position vector of a number of turbines in the network, to which a cost value is associated as given by equation (1). In each iteration, a small random change is applied to the previous solution to generate a new solution with a different cost value (Azizi and Zolfaghari 2004). The neighborhood Y(x) of a solution x is a set of solutions, known as neighbors, that can be reached from x by a simple change. This change, referred to as the neighborhood function, is user defined.

The neighborhood function strongly influences the convergence of the model, and no theoretical rules are available. For example, the size of the neighborhood should not be too small compared with the total solution space cardinality because the process might not occur sufficiently fast. Nevertheless, if the size of the neighborhood is too large, the algorithm might not be able to focus on specific areas (Henderson et al. 2003). Adaptive neighborhoods have been proposed by several authors (Martins et al. 2012; Yao 1993; Liu 1999) in which the size of the neighborhood changes according to the previously visited solutions. Finally, it was concluded that the neighborhood is heavily problem-specific (Henderson et al. 2003).

The neighborhood gives the ability to control the generation of new solutions and adapt it to the specific problem. Given these characteristics, the neighborhood function was thoroughly analyzed in this paper. Different types of neighboring properties were analyzed for the installation of one, two and three turbines in a network to access the fastest convergence for this problem. This process, carried out in two separate stages, is presented in Section 4.

Once a new solution is generated, it is subjected to an acceptance criterion: If the candidate solution Y is better than the previous solution X, it is immediately accepted; if not, then it is accepted with a probability given by

$$ {\alpha}_{XY}= \min \left(\frac{e^{-f(Y)/\theta }}{e^{f(X)/\theta }},1\right) $$
(3)

where θ is a control parameter known as temperature. If θ is high, this probability is also high, and it is easier for the algorithm to escape from local optima.

The temperature is not constant; it is classically high at the beginning and progressively decreases to speed the convergence of the method. Most theoretical papers on simulated annealing focus on the function for the temperature update, known as cooling schedule (Walid 2004). For this case, the cooling schedule presented in Van Laarhoven et al. (1992) was considered in which the temperature depends on the standard deviation of the cost values of the solutions already obtained σ k and an empirical parameter δ:

$$ {\theta}_{k+1}=\frac{\theta_k}{1+\left[{\theta}_k\raisebox{1ex}{$ \ln \left(1+\delta \right)$}\!\left/ \!\raisebox{-1ex}{$3{\sigma}_k$}\right.\right]} $$
(4)

In addition, many methods for the initial temperature θ 0 are proposed in the literature. Most of these methods are based on obtaining randomly initial solutions and extracting the statistics of the cost function (Varanelli and Cohoon 1999; Walid 2004). However, the method proposed by Kirkpatrick et al. (1983) was applied because it is one of the simplest approaches. According to Kirkpatrick, the initial temperature can be estimated as

$$ {\theta}_0=\varDelta {f}_{\max } $$
(5)

where Δf max is the maximal cost difference between any two neighboring solutions.

2.2 Input Data

The physical characteristics of the network are modeled in EPANET and the system is simulated by means of nodes and elements connected by branches. The user provides information on the demand at each node, the restrictions and the turbine characteristics.

The demand at each node of the network must be fulfilled. Simulations of a full year were considered by assuming a single average water demand for each month, which is defined at each node by an hourly curve, one for weekdays and another for weekends/holidays. The number of days considered as weekends or holidays for each month is required and depends on the year and region.

In any WSN, restrictions exist on the maximum and minimum pressures at any point and are typically imposed by regulatory organizations for design and safety reasons. These restrictions can be introduced as constraints on the algorithm. The user might also indicate particular branches at which the minimum pressure is distinct, higher or lower than the rest of the network. In addition, branches in which it is known that the installation of turbines is not possible can be excluded from the optimization process.

Finally, the turbine model consists of characteristic curves for head, discharge and efficiency, and the respective impeller diameter.

2.3 Simulation Process

Based on an initial scenario with no turbines installed, the model begins by associating an appropriate impeller diameter with each branch of the network. The definition of a diameter is accomplished by stating that the flow for which a turbine should have the best efficiency is the 70th percentile of the annual series of flows in that branch. With this information, the corresponding characteristic (H(Q)) and efficiency (η(Q)) curves are obtained by applying the similarity laws. If the diameter resulting from this process is smaller than 100 mm, then the installation of a turbine in that branch is considered impossible.

The branches are ordered by potential for energy production, corresponding to an average production calculated with the maximum and minimum flows of the initial scenario (Qi) and the head drop that would be obtained in the turbine with these flows, as shown in equation (6):

$$ P(X)=\frac{Qi{(x)}_{\max }H\left( Qi{(x)}_{\max}\right)+ Qi{(x)}_{\min }H\left( Qi{(x)}_{\min}\right)}{2} $$
(6)

Based on the potential chain, the neighborhood function is defined as follows:

  • From an initial solution X = (x 1, x 2, …, x n ), where n is the number of turbines and x i is the location of each turbine, a new solution Y = (y 1, y 2, …, y n ) is generated by applying the neighborhood function to each x i .

  • The neighborhood function is given by

$$ I\left({y}_i\right)=I\left({x}_i\right)\pm D $$
(7)

where I(x i ) is the index of the solution x i in the potential chain previously obtained.

  • D is obtained by generating a random number between D min and D max . The D max is set as 5 % of the number of branches in the network, and D min is 0 or 1, depending on whether the function allows the variable x i to remain the same or not.

For each iteration, a position vector of turbines is chosen. In these conditions, a full year is simulated to calculate the turbinated flow, the head drop, the efficiency at each hour, and finally, the produced energy.

3 Case Study Description

The current model was applied to the case study of a sub-grid of the WSN of the city of Lausanne, thus testing the convergence of the developed algorithm on a real network and with real flow values. The considered sub-grid has 335 branches and 312 nodes, with two boundary nodes represented as a reservoir and a tank (Fig. 1). It contains a total of 17 km of pipes and a maximum difference of elevation of 128 m. The network model was provided by eauservice, the water management company of the city, together with hourly flow data from 5 years of measurements.

Fig. 1
figure 1

Closed sub-grid of the WSN used as a case study

Full size image

The so-called node “tank” is a regulation tank located upstream of the network, and the so-called node “reservoir” represents the network downstream of the considered sub-grid. Because the tank represents a real infrastructure, its physical characteristics are incorporated into EPANET and, for the simulations, the tank was considered half full. In contrast, the reservoir is fictional and obliges a constant pressure downstream.

Hourly flows at the outlet of the tank for the period between 2009 and 2013, with an average of 147 l/s, were distributed through the nodes according to the average spatial distribution. For each node, the series were separated into weekdays and weekends/holidays, and an average series was obtained for each month. Figure 2 presents the average variation of flows in one randomly selected node, identified in Fig. 1. The shape of the curves is similar from month to month but slightly changes between weekdays and weekends/holidays.

Fig. 2
figure 2

Average variation of flows in one randomly selected node. Top: weekday; Bottom: weekend/holiday

Full size image

A limit of 10 m of pressure was imposed on every node, with the exceptions of the two boundary nodes and six others for which the pressures were already less than 3 m in the original EPANET files because they are nodes without consumption in particular topographic areas of the network. These exceptions to the restrictions were a consequence of the manner in which the network is explored in reality.

The model was tested by considering the installation of one to three turbines under different restriction scenarios. Without considering any restrictions, there are 335 possible combinations for the installation of one turbine, which corresponds to the number of branches, 55 945 possible combinations for two turbines and more than six million for three turbines.

A five blade tubular propeller (5BTP) turbine developed during the EU-Project HYLOW (hydropower converters with low head differences) (European Commission 2012) was considered for the simulations. Developed at Instituto Superior Técnico (University of Lisbon), the turbine design was optimized via numerical simulation using a Navier-Stokes solver, the FLUENT model, for a 100 mm impeller (Ramos et al. 2009; Ramos et al. 2012; Ramos et al. 2013a). In the current work the performance curves obtained by CFD and presented in Ramos et al. (2013b) were applied.

4 Results

4.1 Chain of Potential

For the defined neighborhood functions, it is necessary to order the branches by energy potential in what is referred to as the chain of potential. For a clearer reading of the results in the following sections, the branches were numbered between 1 and 335, and in Table 1, the 20 first positions of the chain of potential are presented, i.e., the 20 branches of the network with the highest potential. Based on Fig. 3, it becomes obvious that the highest flows occur in the connection path between the water tank and the reservoir. This order of the chain of potential, as explained in Section 2.3, is important for the generation of new solutions.

Table 1 Branches in the network ordered by decreasing potential (only 20 branches)
Full size table
Fig. 3
figure 3

Identification of the highest potential locations in the network

Full size image

4.2 First Stage of Neighborhood Definition

In an initial stage, the installation of one and two turbines without any restrictions apart from the nodal minimum pressure was considered as a reference for the definition of the neighborhood function.

The algorithm was tested for the neighborhood functions defined in Table 2. Because all variables x i may change, Dmin is allowed to be zero such that repetition of positions is allowed. The initial point was considered starting from a low position and from the highest position of the potential chain, and the direction refers to the signal ± in equation (7). The memory property refers to the recording of previous visited solutions such that they are not repeated. Allowing repetition of solutions means that the algorithm will waste iterations analyzing position vectors that have already been tested, whereas not allowing this repetition will force the algorithm to always try new solutions. Allowing repetition will have consequences on the cooling schedule, but the contrary may lead to a position vector in which all neighboring solutions have already been tried. An intermediate possibility was also considered with recording of previous solutions for only every 50 iterations.

Table 2 Definition of the neighborhood functions of the first stage
Full size table

For the installation of one and two turbines, a series of ten runs of the model up to a maximum of 100 and 200 iterations, respectively, were conducted. It was assumed that the turbines could be placed in any branch in the network, except for the installation of one turbine. Because it was verified that the optimal point for one turbine is the location with the highest potential, it was not allowed to use that particular branch when installing only one unit. Allowing the turbine to be installed in that branch would mean that the neighborhood functions that start at the highest potential would find the optimum in the first iteration.

Table 3 presents the maximum energy productions achieved, and hence, the inversion of the minimum values of the cost function f(X) (equation (1)). The fact that the input flows were averaged over the month (conf. Fig. 2) introduces an error of less than 1 % but with clear advantages on the computational effort.

Table 3 Simulations results with one and two turbines for neighborhood function definition
Full size table

Table 3 also presents the branches X corresponding to the best solutions as well as the number of runs in which they were reached and the average iteration of occurrence. The more often the maximum value is reached, the more robust the model will be. The sooner the solution is reached, the faster will be the convergence.

For the installation of one turbine, the optimal result was found in every run. Among neighborhood functions 1, 2 and 3, the difference of speed of convergence is not overly large but functions 4, 5 and 6, that begin at a high potential point, are clearly faster. The frequency of recording of the previous solutions does not strongly influence the results because the solution is reached mostly before the 50th simulation.

When two turbines are considered, starting at a high potential point proves to have the advantage of guaranteeing a good solution but does not guarantee finding the optimal one. Moreover, it is clearly better to define the neighborhood as an increase of potential whenever possible. Function 5 is faster, but is successful less frequently than functions 3 and 4. Function 3 starts with a too low potential solution, whereas function 5 is never allowed to go backwards because repetition is not permitted. Nevertheless, function 6 rarely reached the maximum, proving that it is important to record the previous solutions.

Because neighborhood function 4 gives the more frequent results, it was adopted for further testing.

4.3 Installation of Two Turbines for Different Restrictions

For the chosen neighborhood function, the installation of two turbines was simulated considering that it is not possible to install these units in certain branches of the network. The purpose of this test is to evaluate the convergence to solutions other than the unrestricted optimal point already found. In this way, the algorithm begins at a different initial points and finds different optimal solutions. Hence, the following cases types were considered:

  1. 1.

    No restrictions;

  2. 2.

    Restrict the installation in the branch with the highest potential (ID = 335 in Fig. 3 and Table 1);

  3. 3.

    Restrict the installation in the branch with the second highest potential (ID = 127 in Fig. 3 and Table 1);

  4. 4.

    Restrict the installation in ID = 335 and ID = 127;

For each case, ten runs were conducted with a maximum of 200 iterations. The results are presented in Table 4.

Table 4 Results from the installation of two turbines with neighborhood function 4
Full size table

The convergence of the algorithm is rapid and has a high probability of occurrence but was not reached in every run. Given these results, it was decided that the neighborhood function could still be improved, and thus, a second stage of neighborhood definition was performed.

4.4 Second Stage of Neighborhood Function Definition

The larger the number of turbines, the more difficult it is to find the global optimum because the degrees of freedom of the neighborhood are increased. The installation of three turbines with the algorithm previously defined (even for a maximum of 300 iterations) did not give confident results ( neighborhood function 4 of Table 5). Thus, a new neighborhood definition is needed to improve the convergence. New neighborhood functions for testing were thus defined, as presented in Table 5. Because functions 9 and 10 only allow one position to change per iteration, the minimum draw D min is no longer allowed to be zero to force the generation of a new solution.

Table 5 Definition of the neighborhood functions of the second stage
Full size table

The results of the second stage of neighborhood definition are presented in Table 6.

Table 6 Simulations results with three turbines for neighborhood function definition
Full size table

For functions 4 and 8, the optimal point is only reached three times, and for function 7, only the second best point is reached. However, for functions 9 and 10, the maximum was always reached. These functions are slower than function 4 but always found the best solution, thus proving that only changing one branch at a time is better than changing all three.

It is important to note that the definition of functions 9 and 10 only differ beyond the 50th iteration. The average iteration of occurrence for function 9 is 116, whereas for type 10, it is 142. The periodic record of previously visited solutions makes the algorithm faster, and hence, the neighborhood function 9 was adopted for further testing.

4.5 Final Results

After the second stage of neighborhood function definition, the restriction case types from Section 4.1.3 were repeated for the installation of two and three turbines. The results presented in Table 7 show the best solutions found for all considered case types. The respective positions in the network, the number of runs in which the results were reached and the average iteration of occurrence are also given.

Table 7 Results from the installation of two and three turbines with neighborhood function 9
Full size table

For all cases of two turbines, the convergence of the algorithm was improved compared with that of Table 4. Still, the convergence was not perfect because, in certain cases, the algorithm became trapped in a position vector in which all neighboring solutions had already been visited. This situation illustrates the disadvantage of not allowing the repetition of solutions. In addition, for the installation of three turbines, all cases showed good convergence, therefore validating the application of this neighborhood.

The installation of one, two and three turbines correspond to a recovery around 1, 2 and 5 %, respectively, of the energy needed to pump the average hourly flow incoming into the sub-grid, considering the elevation of the upstream water tank, the elevation of Lake Geneva and a pump with 0.6 of efficiency.

5 Conclusions

This research presents an algorithm for selecting the optimal locations to install micro-turbines in a complex network. Based on hourly simulations of the produced energy and using a simulated annealing process, the methodology was tested in a sub-grid of the WSN of Lausanne, Switzerland. The characteristics of a tubular turbine that is currently under development were used.

The case study showed rapid convergence for the cases of installing up to three turbines. The model was applied to a real network with 335 branches, 312 nodes and 76 intersections of more than two branches. The simulations proved that it is possible to locate the optimal positions for one, two and three turbines if the neighborhood function is well adapted to the problem. The sensitivity of the algorithm was tested by changing certain restrictions in selected branches of the grid such that the initial point for the optimization procedure was changed. The model still showed a good convergence.

The optimal solutions tended to choose positions for the turbines in the link between the upstream water tank and the connection with the sub-grid downstream. This corresponds to the path with the higher flows in the network, but the generalization of this result is still under study since not all networks have clear main paths of supply.

One result from the model is that although the results tended to be placed in branches with high energetic potential, the best solutions were not the combinations of the branches with highest energetic potential. This indicates the need for a detailed analysis in terms of daily variation of flow and turbine efficiency.