## Abstract

Water in sufficient quantity and quality is indispensable for multiple purposes like domestic and industrial use, irrigated agriculture, hydropower generation and ecosystem functioning. In many regions of the world, water availability is limited and even declining. Moreover, water availability is variable in space and time and often does not match with the spatio-temporal demand pattern. To overcome the temporal discrepancy between availability and consumption, reservoirs are constructed. Monitoring and predicting the water available in the reservoirs, the needs of the consumers and the losses throughout the river and water distribution system are necessary requirements to fairly allocate the available water to the different users, prevent floods and ensure sufficient water flow in the river. In this paper, this surface water allocation problem is considered a Network Flow Optimisation Problem (NFOP) solved by spatio-temporal optimisation using linear programming techniques.

## INTRODUCTION

Water is required for multiple purposes such as domestic and industrial use, irrigated agriculture, hydropower generation and ecosystem functioning. The availability of surface water is variable in space and time and this variability often does not match with the spatially and temporally distributed demand pattern of the water consumers. For example, agriculture requires irrigation when precipitation is low and power needs to be generated throughout the year, also when the river discharge is low. To overcome the temporal discrepancy between water availability and consumption, reservoirs have been or need to be constructed. Monitoring the water present in the reservoirs, the needs of the consumers and the losses throughout the water system is indispensable for fair water allocation. The collection and processing of the related data is a tedious issue not only because of the spatially and temporally distributed nature but also due to the fact that various measurements and communication devices are needed (Hanasaki *et al*. 2006).

Water allocation problems have challenged water managers for decades (e.g. Yeomans & Gunalay 2009). Allocation can become controversial when competition for water increases between multiple water users. Increased population shifts and shrinking water supplies magnify this type of user competition in many regions across the globe. Moreover, the competition will be aggravated if natural conditions become more unpredictable and as concerns for water quantity and quality grow. Hence, a poorly-planned system for allocating water can be at the origin of serious societal problems. All this has led decision-makers to the point that tools are needed for optimising the water resource allocation. It is now recognised that the efficiency, equity and environmental soundness of water allocation and management must be improved by developing innovative techniques for environmental policy implementation including water allocation for various levels of complexity (Ahmad *et al.* 2014).

## SCIENTIFIC CONTEXT

In order to cope with the spatio-temporal variability of surface water availability and the mismatches of this availability with the demand pattern of water consumers, reservoirs are built to store water and to distribute it when it is needed. In order to get a fair allocation process, several criteria have been used such as economic efficiency, equity, priorities, etc. (Karimi & Ardakanian 2010). Among them, the most common allocation criterion is using priorities or penalties (Chou & Wu 2014). Several studies have addressed the optimisation of the allocation of water resources. For example, Tinoco *et al.* (2016) studied the Macul basin in the north of Ecuador. The objective was to optimise the operation of a river system including three connected reservoirs. Water is transferred from one reservoir to another to allocate it in an optimal way to the different irrigation projects. This modelling approach consists of a trial-and-error process to identify the optimal amount of water and consists of the following steps: (1) river/reservoir system modeling to simulate and to optimise water availability for a period of historical data, (2) post-statistical analyses of each of the resultant reservoir outflows and reservoir water levels, and (3) extreme value analysis of the minimum reservoir water levels. Authors stated that the approach consists in an easy and practical way to optimise water allocation from reservoirs.

However, the most common way to optimise the allocation of water resources is through mathematical programming models (Spitter *et al.* 2005; Samani & Mottaghi 2006; Liu *et al.* 2011; Das *et al.* 2015; Roozbahani *et al.* 2015; Veintimilla-Reyes *et al.* 2016). Labadie (2004) compared the most used methods to optimise water distribution: (1) implicit stochastic optimisation, (2) linear programming (LP) models, (3) network flow optimisation models, (4) nonlinear programming models, (5) discrete dynamic programming models, (6) explicit stochastic optimisation, (7) real-time control with forecasting and (8) heuristic programming models. The author concluded that the most promising approaches are based on the use of neural networks or genetic algorithms due to their ability to learn based on the conditions.

Morsi *et al.* (2012), introduced a mixed integer linear modeling approach for the optimisation of dynamic water supply networks (WSN) based on piecewise linearisation of the nonlinear constraints. One advantage of applying mixed integer linear programming (MILP) techniques is that these methods are nowadays very mature, that is, they are fast, robust, and are able to solve problems with a huge number of variables. In addition, these methods have the potential of finding global, optimal solutions or at least to provide guarantees for the solution's quality.

Chou & Wu (2014) presented a method to establish the objective function of a network flow LP model for simulating river–reservoir system operations and associated water allocation based on a non-zero coefficient cost. Their model was created and validated for the water allocation in the Feitsui and Shihmen reservoirs in northern Taiwan. Also, this paper presents an LP model for optimising the allocation of the water supplied by multiple rivers to a reservoir, to multiple downstream uses. The optimisation model is based in the Network Flow Optimisation Problem (NFOP) and uses the WSN approach to address it (Qiao *et al.* 2007; Sarkis 2012). This WSN provides a structured mechanism to identify all components of the water management system in order to create a generic optimisation model to be applicable in different regions. To develop this water allocation model artificial data have been used. Artificial, rather than real world, data help to identify strengths and weaknesses. However, the final aim of this research is to apply this model to real world cases, but this is beyond the scope of this paper. Moreover, this optimisation model considers that water availability and water demands are variable in time.

## METHODOLOGY

### Approach

The water allocation problem, addressed in this paper, has the following characteristics: (1) multiple spatially distributed demands which vary in time must be met by the water in the reservoirs and the river system; (2) floods must be prevented, assuming that each river segment has a maximum capacity; (3) the penalties connected to unmet demands and to flood events must be minimised.

A conceptual representation of the problem is shown in Figure 1. This abstraction includes two main components: operational optimisation including *in situ* sensors and the strategic optimisation including the water allocation model itself. The first component (*in situ* sensors) is directly related with the meteorological, hydrological and hydraulic information registered by sensors. Thus, the system under study must include several sensors located in different places to get enough information to have a complete representation of it.

The second component (water allocation optimisation model) includes the optimisation model for the WSN (Qiao *et al.* 2007; Shafroth *et al.* 2010; Coulthard & Van De Wiel 2012; Sarkis 2012; Merkuryeva *et al.* 2015). This WSN is a general abstraction of all activities in the river water management process. The model as conceived in this paper relies on time series of observations from sensors (real time and/or historical archives) or forecasted data (e.g. using machine learning methods) as inputs to determine the exact amount of water coming to a specific reservoir. It uses an operations research (Winston & Goldberg 1994; Frizzone *et al.* 1997; Labadie 2004; Kolb *et al.* 2012; Chou & Wu 2014) approach and more precisely LP methods to allow optimisation of the allocation of the available water to the different demand points. This WSN takes into account the spatial configuration and the hydrology of the river basin since it is assumed that sensor measurements of the water discharges in the rivers and the amounts of water present in the reservoirs are available at a sufficiently high temporal resolution. In addition, the ecological role of the river is taken into account. The ecosystem is modelled as a downstream demand node while simultaneously continuity constraints are set to ensure that, in each time step, a minimum amount of water should remain present in the river segments.

As the goal of the optimisation is to manage the reservoir levels and to allocate available water resources so that spatially and temporally distributed demands are optimally met with no floods, the water allocation problem is conceived to be of the type ‘Minimum cost flow problem (MCFP)’ (Chou & Wu 2014) to be solved with the LP technique. In this kind of problem, the aim is to get the cheapest possible way to send a specific amount of flow through a flow network.

### Generic model

The development of a generic optimisation model requires the definition of a generic WSN, as shown in Figure 2.

Equation (1) is composed by two terms: the first one is related to the total number of monetary units to be paid when a flood occurs and the second one refers to the unmet demands and the related penalties. The main objective of the model is to optimally meet water demands while simultaneously avoiding floods, given the available water, and a set of penalties related to not meeting the mentioned demands or to the magnitude of the floods. In this paper, the penalty values are established in a way that the largest values are assigned to the demands that have the highest priority. If it is not possible to meet all demands, the model minimises the sum of the penalties. The objective is to minimise all costs caused by not meeting demands as well as by floods in river segments. A flood of the reservoir is not considered since we are assuming that the excess water must flow directly into the next river segment.

Constraints are introduced to regulate the water flow in the studied WSN. These constraints can be grouped according to two different types: constraints regulating the mass balance of the water flowing between locations; and constraints considering the physical and regulatory limitations such as capacity restrictions of reservoirs and river segments. The time horizon for the modelling is discretised in time steps which correspond to the time required for the water to flow from one node to another. Figure 4 shows the configuration of the network from a spatio-temporal point of view.

#### Flow balance constraints

#### Limitation and capacity constraints

#### Capacity constraints

*Set*

: input node .

: reservoir node .

: demand node .

: river node .

: time step .

*Parameters*

[monetary units]: the penalty of not meeting one unit of demand (k).

[monetary units]: the penalty of a unit of flood in link (n, n + 1).

: is loss factor associated a river segment from node n to node n + 1 in time (t).

: is the percentage of water that must leave the nth node to the next one in time (t).

: is the percentage of water that must remain in the nth node to the next time step (t).

[m

^{3}]: is the amount of water needed to meet demand (d) in time (t).[m

^{3}]: is the minimum capacity of the n, n + 1th river segment at time (t).[m

^{3}]: is the maximum capacity of the n, n + 1th river segment at time (t).[m

^{3}]: is the minimum capacity required in the reservoir (r) at time (t).[m

^{3}]: is the maximum capacity allowed in the reservoir (r) at time (t).[m

^{3}]: is the amount of water arriving at the input node (i) at time (t).

*Variables*

[m

^{3}]: volume in river segment (n) at time (t).[m

^{3}]: volume in the reservoir (r) at time (t).[m

^{3}/s]: flow between two nodes, (n) and (n + 1) at time (t).[m

^{3}/s]: flow between two nodes, a reservoir (r) and river node (n) at time (t).[m

^{3}/s]: flow between two nodes, a river node (n) and a reservoir (r) at time (t).[m

^{3}/s]: flow between two nodes, (i) input (rainfall) and a river node (n) at time (t).[m

^{3}/s]: flow between two nodes, (i) input (rainfall) and a reservoir node (r) at time (t).[m

^{3}/s]: flow between two nodes, (n) and demand node (d) at time (t).

*Slack variables*

[m

^{3}]: is the amount of water that cannot be allocated to demand (d) at time (t).[m

^{3}]: is the amount of water that exceeds the capacity of the node (n) at time (t).[m

^{3}]: is the amount of water that exceeds the capacity of the reservoir (r) at time (t).

Equations (4)–(6) represent the limitations and capacity of the nodes/segments. Equation (5) considers water coming directly from a river to a specific node. Equation (6) is related to the amount of water allocated to a specific demand . This equation considers the water that cannot be allocated and the amount of water lost during the transportation process from the previous node . From Equation (6), we can notice that the excess water in a specific node must be equal to zero. This is to avoid sending extra water to a specific demand. Equation (7) establishes the amount of water present at a certain time (t) in a reservoir node (r). This equation considers the previous volume and the current one . Finally, Equations (2) and (3) model the amount of water passing by each node. These equations are flow balance constraints and also model the behaviour of the transportation process. This means that the amount of water coming in is equal to the amount of water going out minus a loss value.

Equations (10)–(12) establish the minimum and maximum amount of water that should be present in a reservoir at a specific time. Through Equations (8) and (9), a limitation capacity is set. Hence, water flowing in each river segment must be less than and greater than in order to avoid floods and to ensure water to the ecosystem. To calculate the total penalty to pay, is used. This variable stores the exact amount of water that exceeds the capacity of the above-mentioned segment. Finally, in order to enforce a continuous water movement, Equations (13) and (14) are used.

### Case study

The network configuration studied is shown in Figure 3. There are three types of nodes: reservoir, transportation and demand nodes. In Figure 3, two reservoirs (nodes 1 and 11) are present. These reservoirs can store water coming from several rivers (inputs I1 to I5). The total amount of water available to be allocated to the entire network is the water coming through time in the first reservoir while in the second reservoir (node 11) extra water from I4 and I5 and water from rainfall is added to the flow coming from the first reservoir. Both reservoirs have a maximum and minimum capacity. The minimum level of water must be present at all times to guarantee a correct aquatic ecosystem functioning of the reservoir. Furthermore, several users (nodes 4, 7, 10, 13, 16 and 18) demand water either directly from the reservoir or from the river downstream of the reservoir. In addition, each river segment along of the river has a maximum transportation capacity. If exceeded, floods will occur.

Each node, segment and reservoir lose water through evaporation and seepage. This means that a specific amount of water is lost during the transportation process; to deal with this, a loss value has been included. In further model development, this default value will be replaced by a function depending on parameters such as the length of the segment, ambient temperature, evaporative demand of the atmosphere, etc. The configuration includes 15 time steps. Figure 4 only shows the first eight time steps. The number of time steps depends on the network configuration; it is assumed that the water needs at least one time step to move to a new node. Water flows from node 1 (reservoir node) to node 2 where the link between node 1 and 2 is named . Node 2 receives in t = 1 an additional input from the same node (N2). Hence, each node is receiving a specific amount of water from the previous time step. For instance, in node 3 and t = 2, two links are connected with node 4 (demand node) and node 5 (transfer node); in this specific case, the total amount of water flowing in that segment is divided into a part corresponding to the allocation to node 4 and the remaining part flowing directly into link 35 and therefore to the other nodes downstream.

Figure 4 shows how the water flows in the different time steps from the initial node (reservoir) to the final node (the ecosystem demand node in this use case). For simplification, only the first eight time steps have been included and water added to the upstream reservoir is only available after the first four time steps. Each node has at least two inputs: water remaining in the node after the previous time step and water coming directly from the previous river segment . In the special situation that the current node is a reservoir node some extra inputs can be present. All nodes in this configuration have at least two outputs. First output is the water flowing to next node in time and the second one is related to the water losses. Furthermore, a third output can be present when a demand node is directly connected to a specific transfer node.

The optimisation problem is solved using the optimisation solver Gurobi (Gurobi 2015). This solver was selected as a main solver due its Python programming language support as well as the availability of referential material.

Summarising, this use case includes three inputs (I1, I2 and I3) directly to the reservoir and two extra-inputs downstream of the reservoir (I4 and I5) and three demands nodes (4, 7 and 10) immediately downstream from the reservoir, two more along of the river (13 and 16) and one extra node (18) related directly to the ecosystem. The values of the above-mentioned demands are: 20 (D1), 50 (D2), 30 (D3), 40 (D4), 20 (D5) and 100 (D6) m^{3} of water. In every time step, the same amount must be delivered to the demand node. Furthermore, a value related to the amount of water that is lost during the transportation from the reservoir to the demand through the river has been included in the model . This loss factor reduces the current amount of water by 10%. In this sense, the model must allocate the demand value plus this loss value while considering a limitation in the capacity of 2,000 m^{3}/s in each river segment. In order to avoid floods, a penalty value of 2 monetary units per m^{3} must be paid when the maximum capacity of a link is exceeded. Besides, a second type of penalty must be paid if a unit (m^{3}) demand (uses) is not met.

## RESULTS AND DISCUSSION

To execute and validate the model, artificial data has been selected (15 time steps). Results of the execution of the optimised water allocation model are summarised in Figure 5. In addition, from Figure 5, it is noticeable that in the initialisation stage (i.e. the first time step), only in demand node D6 (X1718) the demand was partially, not fully, met. In this specific case, water received as an input is used directly to meet the demand. Figure 5 also shows that from time step 5 onwards, penalties are becoming lower due to a direct contribution from the first reservoir (node 1). In addition, from Figure 5, we can see that from time step 11 onwards, all demands are met.

Figure 5 (orange line) demonstrates that penalties must be paid during the initial time steps (1072 monetary units in time step 1) while at the end of this initialisation process, the amount of money to be paid is reduced drastically. This is due the optimal use of the water present in the reservoirs.

Figure 6 illustrates how water is flowing within the river segments. The model starts with an initial condition where 10,000 m^{3} (Figure 7) is present in the first reservoir at time step t = 0. This value is the cumulative amount of water that in the previous time period has come to the reservoir directly from the rivers (inputs). Each of the nodes along the network is receiving an additional amount of water in the initialisation process. In time step 1 (t = 1), the amount of water flowing directly from node 1 to node 2 through segment 1 (X12_0) is 600 m^{3}/s (Figure 6); this means that 9,400 m^{3} of water will remain in the reservoir for the next time step.

Figure 6 also shows that the amount of water flowing through the whole system is getting reduced when there is a demand node associated. For instance, between time step 2 and time step 3, there is a demand node (X34_3) and the required water at this point is exactly 100 m^{3} per time step. This pattern becomes constant until the end of the river segment at node (18). In this node, there is also a demand of 100 m^{3} per time step.

Figure 7 shows a graphical representation of the water present daily in the first reservoir (node 1). In this specific use case, maximum and minimum capacity constraints were reached, maintaining reservoir levels between 500 m^{3} and 10,000 m^{3}. Additionally, an extreme rainfall/input has not been present during this period and, due to this effect, flooding did not occur. So, no flood penalties had to be paid.

## CONCLUSIONS AND FUTURE WORK

In this paper, we conceived the spatio-temporal allocation of surface water in a dammed river system to multiple users as a network flow optimisation problem. A generic LP model was formulated addressing spatially and temporally distributed inputs of and demands for water to and from the system and specifying reservoir and transportation capacity constraints. The model was tested by means of a hypothetical use case and revealed a satisfactory behaviour. Encouraged by these results, we plan to introduce more complexity into the model in order to make it applicable to real world cases. One of the extensions considered is to incorporate the capability to determine the best location among different possible locations of additional reservoirs. To this end, the LP-approach will be upgraded to an MILP approach.

## ACKNOWLEDGEMENTS

The authors want to thank the University of Cuenca and the National Secretariat of Higher Education, Science, Technology and Innovation of Ecuador (SENESCYT) for supporting this research project.

## REFERENCES

*et al.,*eds), vol. 162. Birkhäuser, Basel, Switzerland, pp

*,*pp.

*.*