Efficient exact A* algorithm for the single plant Hydro Unit Commitment problem

• Autorzy: Heintzmann Alexandre , Artigues Christian , Bendotti Pascale , Ngueveu Sandra Ulrich , Rottner Cécile

Identyfikatory

DOI

10.15439/2023F5158

• Języki publikacji: EN

Abstrakty

EN

The Hydro Unit Commitment problem (HUC) specific to hydroelectric plants is part of the electricity production planning problem, called Unit Commitment Problem (UCP). More specifically, the studied case is that of the HUC with a single plant, denoted 1-HUC. The plant is located between two reservoirs. The horizon is discretized in time periods. The plant operates at a finite number of points defined as pairs of the generated power and the corresponding water flow. Several constraints are considered. Each reservoir has an initial volume, as well as window resource constraints, defined by a minimum and maximum volume per time period. At each time period, there is an additional positive, negative or zero intake of water in the reservoirs. The case of a price-taker revenue maximization problem is considered. An efficient exact A* variant, so called HA*, is proposed to solve the 1-HUC accounting for window constraints, with a reduced search space and a dedicated optimistic heuristic. This variant is compared to a classical Resource Constrained Shortest Path Problem (RCSPP) algorithm and a Mixed Integer Linear Programming formulation solved with CPLEX. Results show that the proposed algorithm outperforms both concurrent alternatives in terms of computational time in average on a set of realistic instances, meaning that HA* exhibits a more stable behavior with a larger number of instances solved.

Słowa kluczowe

EN

shortest path problem; computer science; upper bound; production planning; hydraulic systems; reservoir; mixed integer linear programming

PL

problem najkrótszej ścieżki; informatyka; granice; planowanie produkcji; systemy hydrauliczne; zbiornik; programowanie liniowe

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 533--543
• Opis fizyczny: Bibliogr. 20 poz., wykr., rys.

Twórcy

autor

Heintzmann Alexandre

• LAAS-CNRS, Université de Toulouse, CNRS, INP, Toulouse, France
• EDF Lab Paris-Saclay, 7 Bd. Gaspard Monge, 91120 Palaiseau, France

autor

Artigues Christian

• LAAS-CNRS, Université de Toulouse, CNRS, INP, Toulouse, France

autor

Bendotti Pascale

• EDF Lab Paris-Saclay, 7 Bd. Gaspard Monge, 91120 Palaiseau, France

autor

Ngueveu Sandra Ulrich

• LAAS-CNRS, Université de Toulouse, CNRS, INP, Toulouse, France

autor

Rottner Cécile

• EDF Lab Paris-Saclay, 7 Bd. Gaspard Monge, 91120 Palaiseau, France

Bibliografia

• 1. A. Renaud, “Daily generation management at Electricité de France: from planning towards real time,” IEEE Transactions on Automatic Control, vol. 38, no. 7, pp. 1080–1093, 1993.
• 2. G. Hechme-Doukopoulos, S. Brignol-Charousset, J. Malick, and C. Lemaréchal, “The short-term electricity production management problem at EDF,” Optima Newsletter, vol. 84, pp. 2–6, 2010.
• 3. W. van Ackooij, C. d’Ambrosio, D. Thomopulos, and R. S. Trindade, “Decomposition and shortest path problem formulation for solving the hydro unit commitment and scheduling in a hydro valley,” European Journal of Operational Research, vol. 291, no. 3, pp. 935–943, 2021.
• 4. G. Ardizzon, G. Cavazzini, and G. Pavesi, “A new generation of small hydro and pumped-hydro power plants: Advances and future challenges,” Renewable and Sustainable Energy Reviews, vol. 31, pp. 746–761, 2014.
• 5. Y. Sahraoui, P. Bendotti, and C. d’Ambrosio, “Real-world hydro-power unit-commitment: Dealing with numerical errors and feasibility issues,” Energy, vol. 184, pp. 91–104, 2019.
• 6. J. I. Pérez-Díaz, J. R. Wilhelmi, and L. A. Arévalo, “Optimal short-term operation schedule of a hydropower plant in a competitive electricity market,” Energy Conversion and Management, vol. 51, no. 12, pp. 2955–2966, 2010.
• 7. P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.
• 8. W. Fan, X. Guan, and Q. Zhai, “A new method for unit commitment with ramping constraints,” Electric Power Systems Research, vol. 62, no. 3, pp. 215–224, 2002.
• 9. R. Taktak and C. D’Ambrosio, “An overview on mathematical programming approaches for the deterministic unit commitment problem in hydro valleys,” Energy Systems, vol. 8, no. 1, pp. 57–79, 2017.
• 10. R. Bellman, “On a routing problem,” Quarterly of applied mathematics, vol. 16, no. 1, pp. 87–90, 1958.
• 11. W. van Ackooij, C. d’Ambrosio, L. Liberti, R. Taktak, D. Thomopulos, and S. Toubaline, “Shortest path problem variants for the hydro unit commitment problem,” Electronic Notes in Discrete Mathematics, vol. 69, pp. 309–316, 2018.
• 12. C. Barrett, K. Bisset, M. Holzer, G. Konjevod, M. Marathe, and D. Wagner, “Engineering label-constrained shortest-path algorithms,” in Algorithmic Aspects in Information and Management: 4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings 4. Springer, 2008, pp. 27–37.
• 13. A. Arce, T. Ohishi, and S. Soares, “Optimal dispatch of generating units of the Itaipú hydroelectric plant,” IEEE Transactions on power systems, vol. 17, no. 1, pp. 154–158, 2002.
• 14. C.-T. Cheng, S.-L. Liao, Z.-T. Tang, and M.-Y. Zhao, “Comparison of particle swarm optimization and dynamic programming for large scale hydro unit load dispatch,” Energy Conversion and Management, vol. 50, no. 12, pp. 3007–3014, 2009.
• 15. M. Kruber, A. Parmentier, and P. Benchimol, “Resource constrained shortest path algorithm for EDF short-term thermal production planning problem,” 2018. [Online]. Available: https://arxiv.org/abs/1809.00548
• 16. L. Turner, “Variants of the shortest path problem,” Algorithmic Operations Research, vol. 6, no. 2, pp. 91–104, 2011.
• 17. C. C. Ribeiro and M. Minoux, “A heuristic approach to hard constrained shortest path problems,” Discrete Applied Mathematics, vol. 10, no. 2, pp. 125–137, 1985.
• 18. J. E. Beasley and N. Christofides, “An algorithm for the resource constrained shortest path problem,” Networks, vol. 19, no. 4, pp. 379–394, 1989.
• 19. X. Zhu and W. E. Wilhelm, “Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context,” European journal of operational research, vol. 183, no. 2, pp. 564–577, 2007.
• 20. X. Zhu and W. E. Wilhelm, “A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation,” Computers & Operations Research, vol. 39, no. 2, pp. 164–178, 2012.

Uwagi

1. Thematic Tracks Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).