Skip to content

Stable power grid through planning and optimisation

Metaheuristics for short-term operational planning of power supply systems

by Ionela Knospe, PhD

Electrification is often seen as the technological achievement that has changed our lives the most. For younger generations in many parts of the world, the use of electrical energy is taken for granted and they cannot imagine their lives without it. But which power plants need to be deployed during the course of a day so that at any given moment the load on a power grid is met and its total cost of ownership is minimal? How does operational planning take into account the inaccuracy of the forecast for renewable energy sources and energy consumption? How best to coordinate the charging and discharging cycle of the energy storage systems in the power grid with the current market price for electricity? These questions are part of the daily operational planning of a power system.

Table of contents

  • Short-term operational planning of the power supply systems
  • Tabu search for short-term operational planning of power supply systems
  • Conclusion
  • Sources
  • Author
Data network

The trend towards clean and renewable energy sources, such as wind and solar energy, requires power systems to integrate more energy storage systems and flexible loads. Long-term operational planning of power systems addresses the expansion of transmission capacity and the provision of additional capacity. It intensively explores the major transformations that the power system will have to undergo in order to achieve zero net CO2 emissions by 2050. Short-term operational planning of power systems has a planning horizon of a few days to hours and deals with formulations of the Unit Commitment Problem (UCP), the Optimal Power Flow (OPF) and the day-ahead and intraday markets. In this planning, data science, optimisation and simulation come together beautifully to create an optimal operational business plan. The methods used in optimisation are exact methods as well as metaheuristics and hybrid methods. Metaheuristics are algorithms for solving optimisation problems approximately. They have proven to be well suited for solving complex and hard-to-solve concrete problems.

Electricity network

Short-term operational planning of the power supply systems

UCP and OPF problems

The Unit Commitment Problem (UCP) and the Optimal Power Flow (OPF) are among the most important and critical problems in the power industry. The UCP problem has been extensively researched since the 1940s and is still the subject of active research due to the potential operating cost savings. The OPF problem was introduced in 1962 as an extension of the optimal economic dispatch problem in traditional power systems by including equations for electric power flow. There is extensive literature on both deterministic and stochastic UCP formulations and OPF methods. We refer here to [1] and [3] and the references therein. A brief overview of the standard formulations of the two problems is given below.

UCP is concerned with the optimal scheduling of the power generation of programmable generators in the electricity grid to meet the forecast electricity demand. Scheduling is done taking into account a number of physical and technical constraints of the generators (minimum/maximum power, maximum power increase and reduction, start-up costs and shutdown costs). Usually the objective is to minimise the total cost of ownership, but additional objectives such as minimum CO2 emissions can also be considered. The solution to the UCP problem contains an on/off state for each generating unit and each time step of the planning horizon – i.e. the decision on the use of the generating units and additionally the power. There are different mathematical formulations of the UCP depending on how the transmission and operational constraints of the systems are considered. These formulations naturally lead to different computational complexity.

OPF deals with the optimal planning of the deployed generation units for one time step in the planning horizon, while respecting permissible power flows. The AC load flow calculation (AC-OPF) model is the most precise for modelling the physical power flows in the entire grid, as it takes into account line losses, grid parameters and active and reactive power. This is a non-linear, non-convex problem that is difficult to solve. The simplified form of load flow calculation (DC-OPF) is an approximation to AC-OPF, which considers the power flows in a linearised form, only takes into account the active power and no line losses. The DC-OPF is thus convex and if the objective function is linear, a linear optimisation problem that can be solved efficiently with a commercial or free solver.

With the increasing presence of renewable energy sources in power grids, UCP and OPF also received increased attention to capture, among other things, the uncertainty factors created by the intermittent nature of renewable energy.

Solution approaches for the short-term operational planning of the power supply systems

If the power grid is represented with the full AC model in UCP, then UCP already includes the OPF problem. As mentioned earlier, it is itself non-convex and non-linear, and therefore very difficult to solve. Moreover, typical real-world applications of UCP deal with large power systems – in terms of the number of generators and the size of the transmission network – which further increases the complexity of the UCP problem. For short-term operational planning of power systems, UCP is therefore often solved without the physical constraints of transmission lines or only in a linearised form. OPF is then solved in a second step in this case.

Formulations of UCP as mixed integer linear programming (MILP) have gained considerable importance over time. The reason for this is the dramatic improvements in the performance of commercial and free MILP solvers. These formulations have the advantage of generating optimal solutions when they are found. A weakness, despite the progress made, is still the computation time required for large problem instances.

Data

In addition to exact methods, metaheuristics and hybrid and iterative solution methods are also used to solve large-scale optimisation problems in the field of power and energy systems. Genetic algorithms, particle swarm optimisation, evolutionary algorithms, but also tabu search and simulated annealing (see Wikipedia article on metaheuristics) are the most commonly used metaheuristics in this field. In order to improve the performance of the algorithm, problem-specific operators often need to be added to them. In recent years, research interest in integrating machine learning into metaheuristics has increased significantly. This combination is being investigated in various areas, such as algorithm selection, initialisation, evolution or parameter setting. Therefore, it is of interest whether the combination of machine learning with metaheuristics could also lead to new solution approaches for short-term operational planning of power supply systems.

Tabu search for short-term operational planning of power supply systems

Tabu search is an iterative metaheuristic method for solving or approximating combinatorial optimisation problems that uses local search methods. These local search methods explore the solution space by moving from a feasible solution to an improved solution in its neighbourhood. The search ends when a stopping criterion is met (e.g. a trial limit or a threshold evaluation value). In most cases, however, there is no guarantee of solution quality. Local search methods tend to get stuck in suboptimal regions or plateaus where no improved neighbours are available. To avoid this, tabu search uses a memory structure that forces the algorithm to explore new areas of the search space. The solutions already visited are stored there for a certain duration, i.e. marked as forbidden or “taboo” (cf. Wikipedia article on tabu search).

In a current research project, RISC Software GmbH has investigated the application of tabu search with an adaptive neighbourhood operator selector for short-term operational planning of power systems and found it promising ([4]). The considered planning horizon covers one day with a time resolution of 15 minutes – both time frames are scalable. Power systems with the following components and technical details were analysed:

  • Programmable generators: minimum and maximum active power, minimum time periods for generation phases and rest phases, maximum power increase and reduction, maximum reserve limit, generation costs, start-up costs, shutdown costs and reserve costs;
  • Energy storage systems: maximum capacity, minimum and maximum charge and discharge power, minimum charge and discharge time, charge and discharge efficiency factors, state of charge;
  • Photovoltaics: installed capacity per unit;
  • Loads: Power consumption;
  • Transmission lines: Reactance, maximum power flow and transformation ratio if the transmission line is a transformer; they are modelled by DC power flows.

In addition to these components, the optimisation model includes two parameters, Seamless Index and Reserve Factor, which address and control the self-sufficiency of the system (see also [2]).

The load and photovoltaic generation are provided by forecast models whose database consists of real data sets and historical data. The forecast models are based on non-linear regression such as gradient boosting using state-of-the-art cloud models and additional features from weather forecast providers.

Energy storage arbitrage is a technique where electricity is purchased and stored when grid electricity prices are cheapest and used during peak hours when grid electricity prices are highest. For all energy storage systems in the power grid, the planning strategy used is arbitrage to achieve.

The proposed solution approach for day-ahead operation planning of power systems with the components defined above is based on tabu search with adaptive neighbourhood operator selector. It is a hierarchical approach in which the generation of a solution involves three steps:

  • Assignment of the on/off state for the programmable generators and energy storage devices over the entire planning horizon;
  • Planning of the energy storage systems over the entire planning horizon;
  • Solve DC-OPF for each time step of the planning horizon.

The subproblems in the second and third steps are linear programmes (LP) that can be solved, for example, with an open-source LP solver and the optimisation suite OR-Tools from Google. Tabu search uses neighbourhood operators tailored to the current problem formulation. The neighbourhood operators are assigned points based on their performance, which is measured by reducing the objective function. This point allocation has a fading memory, i.e. the longer a success is in the past, the fewer points it provides for the current evaluation. In summary, this approach can be seen as a hybrid approach that is a combination of score-based, average-based and extreme value-based point allocation.

This solution approach for day-ahead operational planning of power grids provides acceptable solutions in reasonable computation time. Although not necessarily optimal, they are a valuable alternative to the equivalent mixed integer linear programme (MILP) formulation for large power grids, especially when free or open-source MILP solvers are used. The components and technical details of the power grid can be easily extended with this approach, e.g. with other renewable energy sources such as wind farms or with flexible loads. The use of metaheuristic solutions for planning could therefore potentially find various applications, for example in the planning of microgrids or energy communities.

Conclusion

The energy sector is currently facing major upheavals that are reflected in both the long-term and short-term planning of energy systems. For the methods used in optimisation problems in these areas, research is currently being conducted on the possibility of integrating machine learning techniques. Combining metaheuristics and learning techniques aims to achieve improved solution quality with reduced computation times. While the progress made in this direction is very promising, there are still many more possibilities to explore, which could lead to more efficient ways to tackle the optimisation problems in the energy sector. It therefore remains exciting to see what innovations will come in these areas in the coming years!

Sources

[1] Abdou, I., Tkiouat, M.: Unit Commitment Problem in Electrical Power System: A Literature Review, International Journal of Electrical and Computer Engineering (IJECE) 8 (3), 1357-1372 (2018).

[2] Hosseinnezhad, V., Rafiee, M., Ahmadian, M., Siano, P.: Optimal day-ahead operational planning of microgrids. Energy Conv. Manag. 126, 142-157 (2016).

[3] Khan, B., Singh, P.: Optimal Power Flow Techniques under Characterization of Conventional and Renewable Energy Sources: A Comprehensive Analysis, Journal of Engineering (2017).

[4] Knospe, I., Stainko, R., Gattinger, A., Bögl, M., Rafetseder, K., Falkner, D.: A Tabu Search Approach to the Short-Term Operational Planning of Power Systems, Proceedings International Conference on Operations Research 2022, (akzeptiert).

Contact









    Author

    Ionela Knospe, PhD

    Mathematical Optimization Engineer