Efficient Tabu Search Procedure for Short-Term Planning of Large-Scale Hydropower Systems
Publication: Journal of Water Resources Planning and Management
Volume 145, Issue 7
Abstract
Short-term hydrogeneration scheduling aims at minimizing water consumption for the next 7–15 days on an hourly basis, while satisfying the electrical load as well as many operational, regulatory, and safety requirements. In an ever-changing environment, planners need to make decisions quickly and often adapt their schedules to new conditions. They need a tool that is fast, reactive, and flexible. This paper presents a new solution approach that provides, within a few minutes of computation, near-optimal solutions to hard problems, in which one seeks to determine the number of committed generating units and turbined and spilled flows on an hourly basis for a planning horizon of 10 days. Our solution approach is based on tabu search with new neighborhoods, allowing simultaneous modifications for several plants and time periods. It can handle multiobjective problems, as well as nonlinear and nonconvex constraints. A decomposition mechanism allows parallelism and search acceleration for long horizons and large production systems. Computational experiments on real instances from Hydro-Québec show that even with the most naïve initial solution, our approach finds solutions almost as good as mixed integer linear programming solutions up to 235 times faster than conventional solvers and with less modeling limitations. Starting from a previous planning solution yields even better results.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This work was supported by NSERC/Hydro-Québec Industrial Research Chair on the Stochastic Optimization of Electricity Generation, Hydro-Québec Production, and Mitacs through the Mitacs Accelerate program. We also wish to thank the anonymous referees who reviewed this paper for their insightful comments.
References
Ahuja, R. K., T. L. Magnanti, and J. B. Orlin. 1989. “Chapter IV network flows.” In Vol. 1 of Handbooks in operations research and management science, 211–369. New York: Elsevier.
Boddy, M., and T. L. Dean. 1994. “Deliberation scheduling for problem solving in time-constrained environments.” Artif. Intell. 67 (2): 245–285. https://doi.org/10.1016/0004-3702(94)90054-X.
Borghetti, A., A. Frangioni, F. Lacalandra, A. Lodi, S. Martello, C. Nucci, and A. Trebbi. 2001. “Lagrangian relaxation and tabu search approaches for the unit commitment problem.” In Vol. 3 of Proc., IEEE Porto Power Tech Proceedings 2001, 1–7. Piscataway, NJ: IEEE.
Catalão, J. P. S., H. M. I. Pousinho, and V. M. F. Mendes. 2010. “Mixed-integer nonlinear approach for the optimal scheduling of a head-dependent hydro chain.” Electr. Power Syst. Res. 80 (8): 935–942. https://doi.org/10.1016/j.epsr.2009.12.015.
CPLEX. 2017. CPLEX Optimizer; release 12.7. Armonk, NY: IBM ILOG.
Dorigo, M., M. Birattari, and T. Stutzle. 2006. “Ant colony optimization.” IEEE Comput. Intell. Mag. 1 (4): 28–39. https://doi.org/10.1109/MCI.2006.329691.
Dubost, L., R. Gonzalez, and C. Lemaréchal. 2005. “A primal-proximal heuristic applied to the French Unit-commitment problem.” Math. Programm. 104 (1): 129–151. https://doi.org/10.1007/s10107-005-0593-4.
Finardi, E., and E. da Silva. 2006. “Solving the hydro unit commitment problem via dual decomposition and sequential quadratic programming.” IEEE Trans. Power Syst. 21 (2): 835–844. https://doi.org/10.1109/TPWRS.2006.873121.
Ford, L. R., and D. R. Fulkerson. 1956. “Maximal flow through a network.” Can. J. Math. 8 (3): 399–404. https://doi.org/10.4153/CJM-1956-045-5.
Ge, X.-l., L.-z. Zhang, J. Shu, and N.-f. Xu. 2014. “Short-term hydropower optimal scheduling considering the optimization of water time delay.” Electr. Power Syst. Res. 110 (May): 188–197. https://doi.org/10.1016/j.epsr.2014.01.015.
Gendreau, M., and J.-Y. Potvin. 2010. “Tabu search.” In Vol. 146 of International series in operations research and management science, handbook of metaheuristics, edited by M. Gendreau and J.-Y. Potvin, 41–59. New York: Springer.
Glover, F. 1986. “Future paths for integer programming and links to artificial intelligence.” Comput. Oper. Res. 13 (5): 533–549. https://doi.org/10.1016/0305-0548(86)90048-1.
Glover, F. 1989. “Tabu search—Part I.” ORSA J. Comput. 1 (3): 190–206. https://doi.org/10.1287/ijoc.1.3.190.
Glover, F. 1990. “Tabu search—Part II.” ORSA J. Comput. 2 (1): 4–32. https://doi.org/10.1287/ijoc.2.1.4.
Hedar, A.-R., and A. F. Ali. 2012. “Tabu search with multi-level neighborhood structures for high dimensional problems.” Appl. Intell. 37 (2): 189–206. https://doi.org/10.1007/s10489-011-0321-0.
Hidalgo, I. G., P. B. Correia, F. J. Arnold, J. P. F. Estrócio, R. S. de Barros, J. P. T. Fernandes, and W. W.-G. Yeh. 2015. “Hybrid model for short-term scheduling of hydropower systems.” J. Water Resour. Plann. Manage. 141 (3): 04014062. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000444.
Holland, J. 1973. “Genetic algorithms and the optimal allocation of trials.” SIAM J. Comput. 2 (2): 88–105. https://doi.org/10.1137/0202009.
Hydro-Québec. 2017. Annual report 2017. Montréal, QC, Canada: Hydro-Québec.
Karimanzira, D., D. Schwanenberg, C. Allen, and S. Barton. 2016. “Short-term hydropower optimization and assessment of operational flexibility.” J. Water Resour. Plann. Manage. 142 (2): 04015048. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000577.
Kennedy, J., and R. Eberhart. 1995. “Particle swarm optimization.” In Vol. 4 of Proc., ICNN’95—Int. Conf. on Neural Networks, 1942–1948. Piscataway, NJ: IEEE.
Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi. 1983. “Optimization by simulated annealing.” Science 220 (4598): 671–680. https://doi.org/10.1126/science.220.4598.671.
Mahor, A., and S. Rangnekar. 2012. “Short term generation scheduling of cascaded hydro electric system using novel self adaptive inertia weight PSO.” Int. J. Electr. Power Energy Syst. 34 (1): 1–9. https://doi.org/10.1016/j.ijepes.2011.06.011.
Mantawy, A., Y. Abdel-Magid, and S. Selim. 1998. “Unit commitment by tabu search.” IEE Proc. Gener. Transm. Distrib. 145 (1): 56–64. https://doi.org/10.1049/ip-gtd:19981681.
Marchand, A., M. Gendreau, M. Blais, and G. Emiel. 2018. “Fast near-optimal heuristic for the short-term hydro-generation planning problem.” IEEE Trans. Power Syst. 33 (1): 227–235. https://doi.org/10.1109/TPWRS.2017.2696438.
Osorio, G., J. Matias, and J. Catalao. 2013. “A review of short-term hydro scheduling tools.” In Proc., Power Engineering Conf. (UPEC), 2013 48th Int. Universities, 1–6. New York: IEEE.
Saravanan, B., S. Das, S. Sikri, and D. Kothari. 2013. “A solution to the unit commitment problem: A review.” Front. Energy 7 (2): 223–236. https://doi.org/10.1007/s11708-013-0240-3.
Senjyu, T., K. Shimabukuro, K. Uezato, and T. Funabashi. 2003. “A fast technique for unit commitment problem by extended priority list.” IEEE Trans. Power Syst. 18 (2): 882–888. https://doi.org/10.1109/TPWRS.2003.811000.
Shawwash, Z. K., T. K. Siu, and S. D. Russell. 2000. “The BC Hydro short term hydro scheduling optimization model.” IEEE Trans. Power Syst. 15 (3): 1125–1131. https://doi.org/10.1109/59.871743.
Tahanan, M., W. van Ackooij, A. Frangioni, and F. Lacalandra. 2015. “Large-scale unit commitment under uncertainty.” 4OR 13 (2): 115–171. https://doi.org/10.1007/s10288-014-0279-y.
Taktak, R., and C. D’Ambrosio. 2017. “An overview on mathematical programming approaches for the deterministic unit commitment problem in hydro valleys.” Energy Syst. 8 (1): 57–79. https://doi.org/10.1007/s12667-015-0189-x.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 145 • Issue 7 • July 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: Mar 29, 2018
Accepted: Oct 22, 2018
Published online: Apr 29, 2019
Published in print: Jul 1, 2019
Discussion open until: Sep 29, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.