Abstract

The operation of cascaded reservoirs is a complex problem, and lots of algorithms have been developed for optimal cascaded reservoir operation. However, the existing algorithms usually have disadvantages such as the ‘curse of dimensionality’ and prematurity. This study proposes a grey discrete differential dynamic programming (GDDDP) algorithm for effectively optimizing the cascaded reservoir operation model, which is a combination of the grey forecasting model and discrete differential dynamic programming (DDDP). Additionally, a modification of the grey forecasting model is presented for better forecast accuracy. The proposed method is applied to optimize the Baishan-Fengman cascaded reservoir system in the northeast of China. The results show that GDDDP obtains more power generation than DDDP with less computing time in three cases, i.e., dry years, wet years and the whole series. Especially in the case of the whole series, the power generation of GDDDP is 2.13 MWH more than that of DDDP, while the computing time is decreased by 66,161 ms. Moreover, the power generation of GDDDP is comparable with that of dynamic programming but the computing time is much less. All these indicate GDDDP has high accuracy and efficiency, which implies that it is practicable for the operation of a cascaded reservoir system.

INTRODUCTION

As more cascaded reservoirs are constructed, their operation is becoming more complex (Zhang et al. 2014). Thus, a large number of optimization algorithms have been proposed to enhance the operation of complex reservoir systems (Li et al. 2014). Generally, these optimization algorithms can be divided into two categories.

One category is conventional optimization methods, such as linear programming (Yoo 2009), non-linear programming (Lopes et al. 2003), dynamic programming (DP) (Mujumdar & Ramesh 1997) and its modified algorithms (Ahmad-Rashid et al. 2007). The DP model has been successfully applied to reservoir operations due to its characteristic of global convergence. However, the biggest obstacle for the DP model is the ‘curse of dimensionality’ (Bellman 1957), which is that the number of dimensions will grow exponentially as the number of reservoirs increases. This results in an exponential increase of computer memory and computation time, which makes the DP models potentially unusable in the operation of cascaded reservoirs. Therefore, a series of modified algorithms for dimension reduction has been proposed, such as dynamic programming with successive approximation (Yi et al. 2003; Opan 2011), progressive optimization algorithm (POA) (Howson & Sancho 1975; Turgeon 1981) and discrete differential dynamic programming (DDDP) (Heidari et al. 1971; Chow et al. 1975; Li et al. 2013). These modified algorithms usually need initial solutions, the quality of which will affect the efficiency of the algorithms significantly. Given this, it is highly possible that these algorithms may converge to a local optimum when the initial solution is not reasonable.

The other category is heuristic algorithms, including genetic algorithm (GA) (Hınçal et al. 2011), nondominated sorting genetic algorithm (NSGAII) (Aboutalebi et al. 2015), particle swarm optimization (Kumar & Reddy 2007), ant colony optimization (Jalali et al. 2007), differential evolution (DE) (Qin et al. 2010), weed optimization algorithm (WOA) (Asgari et al. 2016), and bat algorithm (BA) (Bozorg-Haddad et al. 2015), which have been widely used in reservoir operations in general and in the real-time operation of single and multi-reservoir systems in particular. However, heuristic algorithms have the problem of premature convergence, because their search ability will decrease rapidly in the later stage of the iterative process (Lu et al. 2010). Therefore, in order to solve the problems of the ‘curse of dimensionality’ and prematurity for the optimization of cascaded reservoir operation models, it is necessary to develop optimization algorithms with high efficiency and reliability.

The DDDP is a classical method that can reduce or alleviate dimensions (Cheng et al. 2014). However, DDDP is sensitive to the initial solution (initial trajectory). To improve the efficiency of the DDDP algorithm, many studies have been conducted. For example, Xie et al. (2015) proposed a hybrid algorithm for hydro plant operation by combining DDDP with POA. Tospornsampan et al. (2005) proposed a hybrid method by combining GA with DDDP for the optimal operation of a cascaded reservoir system; in this method, GA is used to obtain feasible solutions that satisfy all system constraints, and then the most feasible solution is introduced to DDDP as the initial trial trajectory. From this literature, it can be concluded that the main way to improve DDDP's efficiency is to conduct a hybrid algorithm that can take advantage of both DDDP and other algorithms.

The grey system is designed purposefully to model uncertain systems and complex systems and to study problems with small samples and low-quality information (Deng 1989). In recent years, it has been widely used in industry, agriculture, energy, and transportation (Hamzacebi & Es 2014). However, there are few studies on applying the grey system in reservoir operations, especially the grey forecasting model, which is an important part of grey system theory.

The novelty of this paper lies in presenting an optimal algorithm, termed as the GDDDP algorithm, for the operation of cascaded reservoir systems. This algorithm is a combination of the grey forecasting model and DDDP, using the grey forecasting model to forecast the trajectory and DDDP to search for an improved trajectory with the forecasted trajectory as the initial trial trajectory. That is, the difference between GDDDP and DDDP is that the former searches for the optimal solution around the forecasted trajectories obtained using the grey forecasting model, while the latter searches for the optimal solution around the trajectories obtained from the previous iteration. In addition, a method for modifying the grey forecasting model is also presented. The Baishan-Fengman cascaded reservoir system, which is located in the northeast of China, is used to test the feasibility and validity of the proposed algorithm.

OPTIMIZATION PROBLEM FORMULATION

Power generation is the most important benefit derived from a cascaded reservoir system, so the aim of cascaded reservoir system operation is to maximize total power generation over the entire operation period without violating the system constraints (Zhang et al. 2015). The objective function and constraints of the optimization model for cascaded reservoir systems are provided in the supplementary material (available with the online version of this paper).

SOLUTION PROCEDURE

DDDP

DDDP, proposed by Heidari et al. (1971), is an improved DP method to ease difficulties such as memory and computer time requirements by reducing computational dimensions. The details of the DDDP procedure are provided in the supplementary material (available with the online version of this paper). As we all know, the DDDP procedure starts with a feasible initial trajectory, which may be acquired through engineering judgment or other simplified methods (Cheng et al. 2014). In the present study, the feasible initial trajectory is generated by DP, which is a traditional method. Instead of searching for the optimal trajectory over the entire state-stage domain, as is the case in DP, DDDP converges successively to the optimal trajectory and thus saves a considerable amount of computing time and memory (Chow et al. 1975).

Grey forecasting model

Grey forecasting models are a type of recent prediction methods. Although there are many different grey prediction models, the most widely used is GM(1,1), which is part of the grey system theory. GM(1,1) is a time series prediction model. It does not require any prior knowledge, such as the probability distribution of the input data, and requires less data. Therefore, it has been used in several different contexts, such as in predicting the risk of fatal accidents (Mao & Chirwa 2006), in the global integrated circuit industry (Hsu 2003), and in runoff (Yu et al. 2007). The procedures of GM(1,1) are provided in the supplementary material.

Although GM(1,1) has the capability of making accurate predictions for a monotone sequence, it has some problems when it comes to handling an oscillation sequence. In the present study, GM(1,1) is used to forecast a trajectory, which is an oscillation sequence. So, to improve the forecast accuracy, some modification of GM(1,1) is made. The procedures of the modified GM(1,1) for cascaded reservoir operation are described below.

  • (1)

    Assume that the initial sequence is X(0) = {x(0)(1), x(0)(2), …, x(0)(m)}, which is composed of the local optimal trajectories and forecasted trajectories for time period t of reservoir p. m represents the total number of trajectories used as the inputs of the grey forecasting model, x(0)(m) represents the value of trajectory m (i.e., the storage) for the time period t.

  • (2)

    Check the monotonicity of the initial sequence X(0).

  • (3)
    If X(0) is a monotone sequence, the forecasted value of trajectory m + 1 for the time period t can be obtained:  
    formula
  • (4)
    If X(0) is an oscillation sequence, some modification is needed. First, the values before the change point are removed, and then the value of trajectory m + 1 for the time period t is forecasted using the following equation:  
    formula
  • (5)

    Repeat step (1) to step (4), and the forecasted value of trajectory m + 1 for other time periods can be obtained. Set p = p + 1.

  • (6)

    Repeat step (1) to step (5), and the forecasted value of trajectory m + 1 for other reservoirs can be obtained.

GDDDP

The idea of GDDDP includes two parts: trajectories forecast using the modified grey forecasting model and optimal search using DDDP. At each iteration, the DDDP algorithm will construct a new corridor in the neighborhood of the initial solution (for the first iteration, the initial solution is obtained using DP, while for other iterations, the initial solution is the optimal solution obtained from the previous iteration, if the terminal criteria are not satisfied). An improved optimal solution will be obtained if the current iteration gives a better value of the objective function than the previous optimal solution. In such cases, the DDDP model is prone to converge to a local optimal solution if the initial solution is distant from the global optimal solution. But in GDDDP, the corridor is constructed in the neighborhood of the forecasted solution, which ensures that the search can jump out of the local optimal region. That is, the obvious difference between GDDDP and DDDP is that the former searches for the optimal solution around the forecasted trajectories, while the latter searches for the optimal solution around the trajectories obtained from the previous iteration.

Compared to the time needed for the iteration process, the time consumed by the prediction process is low and negligible, especially in the optimization of the cascaded reservoir operation model. Therefore, GDDDP converges to a satisfied solution more quickly than DDDP.

The procedures of GDDDP are shown in Figure 1 and are described as follows.

  • Step 1: Initialization. Configure the parameter settings such as the discrete state number K, the max iteration number c (c = 200), and termination precision ɛ (ɛ = half of the discrete storage).

  • Step 2: Generate initial trial trajectories. Generate initial trial trajectories that satisfy all constraints using DP, i.e., the initial storage of all reservoirs at all periods.

  • Step 3: Initialize the iteration number. Set the iteration number for the whole system I = 0.

  • Step 4: Check the criterion. If I < 2, go to Step 5; otherwise, build the grey forecasting model for every period of all reservoirs with the previous optimal and predicted trajectories obtained by using the grey forecasting model as the input data, and then predict new trajectories for the reservoirs. Save the predicted trajectories and update the initial trial trajectories with the predicted trajectories.

  • Step 5: Search for an improved trajectory. Construct a corridor around the initial trial trajectory and search for the improved trajectory with a better objective function value than the initial trial trajectory. Save the improved trajectory as the optimal solution and then set I = I + 1.

  • Step 6: Check the terminal criteria, i.e., I > c or the change of water storage . If the terminal criteria are not satisfied, return to Step 4; otherwise, terminate the iteration and output the optimal trajectory.

Figure 1

The procedures of GDDDP.

Figure 1

The procedures of GDDDP.

CASE STUDY

The Baishan-Fengman cascaded reservoir system, which is located in the northeast of China, is used to verify the efficiency of the proposed GDDDP model in the present study. Two reservoirs, Baishan and Fengman, constitute the cascaded hydropower system. The upstream reservoir, the Baishan reservoir, is 250 km away from the Fengman reservoir. Both reservoirs are primarily for hydropower generation and secondarily for flood control and water supply for irrigation, industry and urban areas. The location of the cascaded reservoir system and the basic characteristics of the two reservoirs are provided in the supplementary material (available with the online version of this paper).

The observed monthly inflow data of the two reservoirs are available from 1983 to 2005, among which years 2004 and 2005 are dry and years 1995 and 1996 are wet. Therefore, the whole data series from 1983 to 2005, with dry years from 2004 to 2005 and wet years from 1995 to 1996, are all selected as examples to evaluate and compare the efficiency of the GDDDP, DDDP and DP models. The time interval of the hydropower generation simulation is one month in this study. That is, for the dry years and the wet years, there are 12 × 2 × 2 = 48 variables (i.e., the storage of the reservoirs) to be optimized, and for the whole series, there are 12 × 23 × 2 = 552 variables to be optimized.

RESULTS AND DISCUSSION

Performance evaluation for dry years

In order to comprehensively compare the performances of DP, DDDP and GDDDP for the dry years from 2004 to 2005, various discrete state numbers are tested. The results are shown in Table 1. It can be seen that due to the high discrete state numbers, DP obtains the highest power generation but computes much more time. For all discrete state numbers, GDDDP performs better than DDDP with higher power generation and less computing time. This demonstrates that GDDDP not only has a higher global search capability, but also has a higher convergence rate. This is due to the fact that in each iteration, GDDDP adopts the trajectory predicted by the grey forecasting model as an initial trial trajectory, which enhances the algorithm, allowing it to search more efficiently.

Table 1

Results of GDDDP, DDDP and DP for dry years and wet years across different discrete numbers

Dry years
Wet years
Discrete state numbersAlgorithmPower generation (MWH)Computing time (ms)Power generation (MWH)Computing time (ms)
200 DP 3,007.38 1,650,818 5,921.3 1,639,802 
GDDDP 2,941.39 186 5,901.89 160 
 DDDP 2,940.75 209 5,901.71 202 
GDDDP 2,984.35 276 5,913.23 239 
 DDDP 2,949.9 337 5,907.19 285 
GDDDP 2,999.81 477 5,918.81 428 
 DDDP 2,965.19 561 5,917.59 519 
GDDDP 3,005.35 1,064 5,919.05 652 
 DDDP 2,975.82 1,601 5,918.65 1,088 
Dry years
Wet years
Discrete state numbersAlgorithmPower generation (MWH)Computing time (ms)Power generation (MWH)Computing time (ms)
200 DP 3,007.38 1,650,818 5,921.3 1,639,802 
GDDDP 2,941.39 186 5,901.89 160 
 DDDP 2,940.75 209 5,901.71 202 
GDDDP 2,984.35 276 5,913.23 239 
 DDDP 2,949.9 337 5,907.19 285 
GDDDP 2,999.81 477 5,918.81 428 
 DDDP 2,965.19 561 5,917.59 519 
GDDDP 3,005.35 1,064 5,919.05 652 
 DDDP 2,975.82 1,601 5,918.65 1,088 

For GDDDP and DDDP, both the power generation and computing time will increase as the discrete state number increases. This is because an increasing discrete state number will increase the diversity and complexity of the feasible solutions; thus, the optimal solutions found by DDDP and GDDDP are more accurate, and more computing time is needed. It should be noted that when the discrete state number changes from 7 to 9, the power generation of DDDP and GDDDP only increases by 10.63 MWH and 5.54 MWH, i.e., 0.35% and 0.18%, respectively, while computing time increases by 1,040 ms and 587 ms, i.e., 185.38% and 123.06%, respectively. This indicates that the increased power generation is not worth the cost of the computing time. Therefore, in the present study, the best discrete state number is 7.

The evolutionary processes of GDDDP and DDDP for the dry years across various discrete state numbers are shown in Figure 2(a)2(d). It can be observed that for the same discrete state number, there are significant differences between the evolutionary processes of the two algorithms. Compared to DDDP, in all cases, GDDDP can approach the optimal solution more quickly during the first 50 iterations and ultimately can obtain a better optimal solution with a higher power generation, which indicates that GDDDP consistently performs better than DDDP. As discrete state numbers increase, the differences become more significant since the searching space becomes denser and the amount of calculation increases rapidly.

Figure 2

The evolutionary processes of GDDDP and DDDP for dry years and wet years when discrete state numbers are 3, 5, 7, 9, respectively; (a)–(d) are the results for dry years, (e)–(h) are the results for wet years.

Figure 2

The evolutionary processes of GDDDP and DDDP for dry years and wet years when discrete state numbers are 3, 5, 7, 9, respectively; (a)–(d) are the results for dry years, (e)–(h) are the results for wet years.

Figure 2(a) shows that although GDDDP is quicker than DDDP during the first iterations, the optimal solution found by DDDP can approach the optimal solution found by GDDDP with an increasing number of iterations. This reveals that when the discrete state number is small, both algorithms can obtain the approximate optimal solution, and thus there is no significant difference between the two optimal solutions. Figure 2(b)2(d) show that with an increase in the discrete state number, the difference between the optimal solutions of DDDP and GDDDP becomes more significant because the searching rate of GDDDP is quicker than DDDP. This, consequently, enlarges the gap between the optimal solutions obtained by GDDDP and DDDP.

Performance evaluation for wet years

The results of the three algorithms for the wet years from 1995 to 1996 across various discrete state numbers are shown in Table 1. As in the case of dry years, it can be concluded that DP obtains the highest power generation with much more computing time and GDDDP performs better than DDDP for all discrete state numbers. When the discrete state number increases from 3 to 5, the gap between the optimal solutions obtained by DDDP and GDDDP widens. This reveals that GDDDP approaches the optimal solution more quickly than DDDP as the discrete state number increases. When the discrete state number increases from 5 to 9, the power generation of GDDDP reaches the optimal value and remains stable around 5,919 MWH; meanwhile, that of DDDP increases slowly and reaches a value close to that of GDDDP until the discrete state number increases to 9. These facts demonstrate that both algorithms can obtain the optimal solution for the wet years, but GDDDP obtains it with a smaller discrete state number while DDDP obtains it with a larger discrete state number. In this study, DDDP obtains the optimal solution when the discrete number is 9 and the computing time is 1,088 ms. On the other hand, GDDDP obtains the optimal solution when the discrete state number is 7 and the computing time is 428 ms, which is only 39.3% of the computing time required by DDDP.

The evolutionary processes of GDDDP and DDDP for the wet years across various discrete state numbers are shown in Figure 2(e)2(f). It can be seen that GDDDP approaches the optimal solution more quickly than DDDP during the first 40 iterations in all cases. GDDDP obtains the global optimal solution when the discrete states number is 7 and soon stabilizes near the global optimal solution when the discrete state number is 9, while DDDP's search efficiency is low during the first iterations and cannot obtain the optimal solution until the discrete state number changes to 9.

Performance evaluation for the whole series

The above analysis shows that the best discrete state number for GDDDP in this study is 7. Therefore, the performance of the proposed GDDDP is also verified using the whole series from 1983 to 2005 when the discrete state number is set as 7, and the results show that the annual power generation obtained by GDDDP is 3,677.15 MWH and the computing time is 56,120 ms, while the annual power generation obtained by DP and DDDP is 3,678.05 MWH and 3,675.02 MWH respectively and the computing time is 38,227,835 ms and 122,281 ms, respectively. All these indicate that GDDDP exerts an obvious advantage in calculating long series.

CONCLUSIONS

In this paper, to solve the problem of cascaded reservoir operation, the present paper proposes a GDDDP, which is a combination of the grey forecasting model and DDDP. The Baishan-Fengman cascaded reservoir system, located in the northeast of China, is used to test the potential ability of GDDDP to optimize cascaded reservoir system operations in the future. The conclusions can be summarized as follows.

  • (1)

    GDDDP has the merits of DDDP, such as searching in small ranges and having few computing tasks and low computing time, because it uses DDDP to search for improved trajectories.

  • (2)

    The modified grey forecasting model is a method that can effectively avoid converging to a local optimum and shorten the computation time. Taking the predicted trajectories obtained by the modified grey forecasting model as trial trajectories can enhance GDDDP to converge to the global optimal solution, and thus improves its global search ability and convergence speed.

  • (3)

    GDDDP can achieve a power generation that is comparable with DP with much less computing time and performs better than DDDP in three cases, including dry years, wet years, and the whole series, with better power generation and less computing time. This proves that GDDDP is a competitive method to optimize cascaded reservoir system operations.

ACKNOWLEDGEMENTS

This work was supported by the National Natural Science Foundation of China (Grant No. 91547111, 51379027, 51609025), Natural Science Foundation of Liaoning Province (Grant No. 2015020608), National Science and Technology Pillar Program during the Twelfth Five-year Plan Period (Grant No. 2015BAB07B03) and Scientific Research Foundation for High-level Talents of North China University of Water Resources and Electric Power (Grant No. 201702013).

REFERENCES

REFERENCES
Aboutalebi
,
M.
,
Bozorg-Haddad
,
O.
&
Loaiciga
,
H. A.
2015
Optimal monthly reservoir operation rules for hydropower generation derived with SVR-NSGAII
.
J. Water Res. Plan. Manage.
141
(
0401502911
).
Ahmad-Rashid
,
K.
,
Diacon
,
A. G.
&
Popa
,
B.
2007
Optimal operation of large hydropower reservoirs with unregulated inflows
.
University ‘Politehnica’ of Bucharest, Scientific Bulletin Series C: Electrical Engineering
69
(
2
),
25
36
.
Asgari
,
H.
,
Bozorg Haddad
,
O.
,
Pazoki
,
M.
&
Loáiciga
,
H. A.
2016
Weed optimization algorithm for optimal reservoir operation
.
J. Irrig. Drain Eng.
142
(
2
),
4015055
.
Bellman
,
R.
1957
Dynamic Programming
.
Princeton University Press
,
Princeton
.
Bozorg-Haddad
,
O.
,
Karimirad
,
I.
,
Seifollahi-Aghmiuni
,
S.
&
Loaiciga
,
H. A.
2015
Development and application of the bat algorithm for optimizing the operation of reservoir systems
.
J. Water Res. Plan. Manage
.
141
(
040140978
).
Cheng
,
C.
,
Wang
,
S.
,
Chau
,
K.
&
Wu
,
X.
2014
Parallel discrete differential dynamic programming for multireservoir operation
.
Environ. Modell. Softw.
57
,
152
164
.
Chow
,
V. T.
,
Maidment
,
D. R.
&
Tauxe
,
G. W.
1975
Computer time and memory requirements for DP and DDDP in water-resource systems-analysis
.
Water Resour. Res.
11
(
5
),
621
628
.
Deng
,
J.
1989
Introduction to grey system theory
.
Journal of Grey Systems
1
(
1
),
1
24
.
Heidari
,
M.
,
Chow
,
V. T.
,
Kokotovi
,
P. V.
&
Meredith
,
D. D.
1971
Discrete differential dynamic programing approach to water resources systems
.
Water Resour. Res.
7
(
2
),
273
.
Hınçal
,
O.
,
Altan-Sakarya
,
A. B.
&
Metin Ger
,
A.
2011
Optimization of multireservoir systems by genetic algorithm
.
Water Resour. Manag.
25
(
5
),
1465
1487
.
Howson
,
H. R.
&
Sancho
,
N. G. F.
1975
A new algorithm for the solution of multi-state dynamic programming problems
.
Math. Program.
8
(
1
),
114
116
.
Hsu
,
L.
2003
Applying the Grey prediction model to the global integrated circuit industry
.
Technological Forecasting and Social Change
70
(
6
),
563
574
.
Jalali
,
M. R.
,
Afshar
,
A.
&
Mariño
,
M. A.
2007
Multi-colony ant algorithm for continuous multi-reservoir operation optimization problem
.
Water Resour. Manag.
21
(
9
),
1429
1447
.
Kumar
,
D. N.
&
Reddy
,
M. J.
2007
Multipurpose reservoir operation using particle swarm optimization
.
American Society of Civil Engineers
133
(
3
),
192
201
.
Lopes
,
J. E. G.
,
Barros
,
M. T. L.
,
Tsai
,
F. T.
,
Yeh
,
W. W.
&
Yang
,
S.
2003
Optimization of large-scale hydropower system operations
.
Journal of Water Resources Planning & Management
129
(
3
),
178
188
.
Mao
,
M.
&
Chirwa
,
E. C.
2006
Application of grey model GM(1, 1) to vehicle fatality risk estimation
.
Technological Forecasting and Social Change
73
(
5
),
588
605
.
Mujumdar
,
P. P.
&
Ramesh
,
T.
1997
Real-time reservoir operation for irrigation
.
Water Resour. Res.
33
(
5
),
1157
1164
.
Opan
,
M.
2011
Real-time optimal operation of multiple reservoirs system
.
Tek. Dergi.
22
(
2
),
5359
5385
.
Xie
,
M.
,
Zhou
,
J.
,
Li
,
C.
&
Lu
,
P.
2015
Daily generation scheduling of cascade hydro plants considering peak shaving constraints
.
Journal of Water Resources Planning & Management
142
(
4
),
04015072
.
Yi
,
J.
,
Labadie
,
J. W.
&
Stitt
,
S.
2003
Dynamic optimal unit commitment and loading in hydropower systems
.
Journal of Water Resources Planning & Management
129
(
5
),
388
398
.
Yu
,
P. S.
,
Chen
,
C. J.
,
Chen
,
S. J.
&
Lin
,
S. C.
2007
Application of grey model toward runoff forecasting
.
J. Am. Water Resour. Assoc
.
37
(
1
),
151
166
.
Zhang
,
R.
,
Zhou
,
J.
,
Zhang
,
H.
,
Liao
,
X.
&
Wang
,
X.
2014
Optimal operation of large-scale cascaded hydropower systems in the upper reaches of the Yangtze River, China
.
J. Water Res. Plan. Manage.
140
(
4
),
480
495
.

Supplementary data