Development of a Sequential Restoration Strategy Based on the Enhanced Dijkstra Algorithm for Korean Power Systems

Abstract

When a blackout occurs, it is important to reduce the time for power system restoration to minimize damage. For fast restoration, it is important to reduce taking time for the selection of generators, transmission lines and transformers. In addition, it is essential that a determination of a generator start-up sequence (GSS) be made to restore the power system. In this paper, we propose the optimal selection of black start units through the generator start-up sequence (GSS) to minimize the restoration time using generator characteristic data and the enhanced Dijkstra algorithm. For each restoration step, the sequence selected for the next start unit is recalculated to reflect the system conditions. The proposed method is verified by the empirical Korean power systems.

1. Introduction

The current bulk power systems require a high level of reliability. To improve the reliability of a power grid, system operators analyze N-1 contingencies, monitor the system margins and develop new technologies such as High Voltage Direct Current (HVDC) and Flexible AC Transmission Systems (FACTS) which have been introduced. Nevertheless, there is the possibility of total and partial blackouts. According to recent blackouts [1,2], large blackouts can be described as cascading outages, as shown Figure 1. Cascading outages occur sequentially, and they are caused by an initial disturbance. The initial disturbance includes natural disasters, unexpected accidents, misoperation of a facility and imbalanced power systems. It causes sequential trips of facilities such as transmission lines, transformers and generators. Sequential outages are propagated until the system fails to recover due to voltage instability and thermal violations which are alleviated or drop below the operating limits. Eventually, a partial or total blackout occurs. Once the blackouts have occurred, the appropriate system restoration should be performed.

Most blackouts are partial and can be restored with the support of neighboring regions [3,4]. On the other hand, if total blackouts occur, neighboring regions may be not able to assist the system, especially for isolated power systems such as Korean power systems. For isolated systems, a reliable restoration method is more essential than interconnected power systems. When a total blackout occurs in isolated systems, the whole system is usually divided into several subsystems to restore the system as quickly as possible [5], and subsystems are restored in parallel. After the restoration of each subsystem, all subsystems are synchronized. Each subsystem must have at least one black start unit and should be balanced between generation and load [6]. Additionally, each subsystem must satisfy the following reliability criteria: real and reactive power balance, thermal constraints on transmission lines, being sustained over voltages during early restoration, and maintaining a steady state and transient stability during restoration.

Figure 2 shows the general black start procedure [7,8,9]. First, when a blackout occurs, the status of the power systems is checked through an alarm or communication. In this step, the size and status of the blackout are evaluated. Afterwards, the generators in the systems are identified using their location and capacity and the proximity to the grid. Based on the confirmed information, the sequence of the generators is established [10,11]. According to the sequence, the generators in the systems are started. While monitoring the power systems and identifying the connectivity of the system, the path for restoration is searched. The transmission lines and transformers on the paths are re-energized, and the load is restored depending on the system balance [12,13,14]. During the restoration stage, three limitations are needed to maintain the range: the voltage of the bus, the overload rate of the transmission lines and the frequency of the grid.

The restoration sequence of non-black start units, transmission lines, and transformers is different according to the objective function of each system’s restoration methodology. Many domestic and foreign studies have been performed, and each Independent System Operator (ISO) has a different restoration methodology [15,16]. After a complete blackout occurs, the Australian Energy Market Operator (AEMO) in Australia aims to supply power to major generators in 90 minutes and to restore 40% of the system peak load in four hours [17,18,19]. The Pennsylvania New Jersey Maryland (PJM) ISO in USA intends to restore 80% of the whole system load in 16 hours and to implement the system restoration with the priority of system stability [20,21]. The Electric Reliability Council of Texas (ERCOT) ISO in USA aims to restore the whole system within the shortest amount of time [22]. At the same time, the system load should not exceed 5% of the total power in every single step. Also, when a blackout occurs, the status of the system is reported to the ERCOT ISO by the transmission system operators, and the system operators carry out the restoration procedure using the specified black start units. The system is divided into small islands and all islands are synchronized after completing the restoration process of each island. Many studies related to the methodology of restoring the islands have studied the ERCOT ISO [23]. On the other hand, the Korean Power Exchange (KPX) in Korea divides the whole system into subsystems and restores the black start units and pre-assigned paths in each subsystem first. Afterwards, there is no specific restoration methodology.

It is important to perform the restoration process considering the system condition and understanding the characteristics of the blackout. The Electrical Research Institute (EPRI) proposed a generic restoration milestones (GRM) technique to restore the system depending on various system conditions [24,25]. In the GRM, there are six milestones and system operators can select a series of milestones to restore the system depending on system conditions. The Power System Engineering Research Center (PSERC) suggested restoration procedures based on optimization techniques [6]. During the power system restoration process, the optimization technique Mixed Integer Linear Programming (MILP) is used to determine the generators’ start-up sequence [26,27]. In this paper, we propose a sequential restoration strategy based on the enhanced Dijkstra algorithm for Korean power systems. In the methodology, we determine the generator start-up sequence (GSS) using generator characteristic data and an enhanced Dijkstra algorithm. To determine the GSS, we compare the characteristic data of generators, including the cranking power, start-up time, and ramping rate. Additionally, we create an adjacency matrix and consider the charging current as a weighting factor to establish power grids quickly [28]. The proposed method is verified by Korean power systems.

2. Enhanced Dijkstra Algorithm

In order to minimize damage after blackouts occur, restoration should be fulfilled reliably and quickly. For fast restoration, it is important to reduce the time taken for the selection of generators, and the time taken for the transmission lines and transformers should be considered.

First, to restore the generators, the connectivity between two different buses should be verified using an adjacent matrix [25,29]. We can find the path from the energized block which is already restored to a generator that can be restored. The adjacent matrix $A\left(k\right)$ based on the transformation of the connection matrix can be presented as follows [12]:

$$A\left(k\right)=\left[lin{e}_{ij}^k\right]=\{\begin{array}{cc}1\hfill & \hfill i=jori\&jareconnecteddirectly\hfill \\ 0\hfill & \hfill i\&jarenotconnecteddirectly\hfill \end{array}$$

(1)

where $lin{e}_{ij}$ is a line between bus $i$ and bus $j$. After generating the adjacent matrix, we utilize a Dijkstra algorithm to find the shortest path to the generator. At the same time, we consider the charging current of each transmission line as a weighting factor to avoid excessive charging currents.

$$B\left(k\right)=\{\begin{array}{c}0\\ achargingcurrentof{line}_{ij}\\ alargenumber\mathsf{\rho }\end{array}\begin{array}{c}iandj\in {\mathrm{\Omega }}_{E\left(S\right)}\\ iorj\notin {\mathrm{\Omega }}_{E\left(S\right)}\\ {line}_{ij}isatransformerandiorj\notin {\mathrm{\Omega }}_{E\left(S\right)}\end{array}$$

(2)

where ${\mathrm{\Omega }}_{\mathrm{E}\left(\mathrm{S}\right)}$ is the energized block that is already restored. If the number of transformers in a path is increased, the likelihood of ferroresonance may increase. However, transformers usually have small charging currents. Therefore, they should be assigned a large number of $\mathsf{\rho }$ as weighting factors. In this paper, we use the R program to generate the adjacent matrix.

For example, in Figure 3, if we find the paths from bus 2 to 16, we can consider two different paths. The one that is marked with the red line is the shortest path which does not consider the weighting factor, while the other that is marked with the blue dashed line is the path with the smallest weighting. Even though the red line is shorter, we will select the blue dashed line. The blue and yellow balls illustrated in Figure 3 represent the buses with bus numbers and generators respectively.

3. Sequential Restoration Strategy

3.1. Problem Formulation

The object function is used to minimize the total time taken to restore generators [30]. It should select the generator that can be restored in the shortest time. The object function can be denoted with the following equation:

$$min{\displaystyle \sum }_{i=2}^N\Delta t_{{\mathrm{GEN}}_{i+1}}-t_{{\mathrm{GEN}}_i}$$

(3)

where N is the total number of generators; $t_{{\mathrm{GEN}}_i}$ is the time to re-start the $i$th generator at the $i$th step; and $\Delta t_{{\mathrm{GEN}}_{i+1}}-t_{{\mathrm{GEN}}_i}$ means the time taken to start the $i+1$th generator from the $i$th generator. The object function can be formulated as the minimization of the restoration time. While restoring the system, we must satisfy the following constraints.

• Solving power flow equations

  $$PowerFlow\left(P_{\mathrm{GEN}},P_{\mathrm{LO}},Q_{\mathrm{GEN}},Q_{\mathrm{LO}}\right)=0$$

  (4)
• No violation of generation, transmission and voltage limits

  $$V_{\mathrm{MIN}\_\mathrm{BU}}\le V_{\mathrm{BU}}\le V_{\mathrm{MAX}\_\mathrm{BU}}$$

  (5)

  $$P_{\mathrm{MIN}\_\mathrm{LO}}\le P_{\mathrm{LO}}\le P_{\mathrm{MAX}\_\mathrm{LO}}$$

  (6)

  $$P_{\mathrm{MIN}\_\mathrm{GEN}}\le P_{\mathrm{GEN}}\le P_{\mathrm{MAX}\_\mathrm{GEN}}$$

  (7)

The second equation means the system balance $P_{\mathrm{GEN}},P_{\mathrm{LO}}$ are the active power of the generator and load, and $Q_{\mathrm{GEN}},Q_{\mathrm{LO}}$ are the reactive power of the generator and load, respectively. Equations (5)–(7) represent the need to maintain a range of voltage and power; $V_{\mathrm{BU}}$ is the voltage of the bus. $V_{\mathrm{MIN}\_\mathrm{BU}}$, $V_{\mathrm{MAX}\_\mathrm{BU}}$ denote the minimum and maximum, respectively. $P_{\mathrm{LO}}$ means the power of the load, and $P_{\mathrm{MIN}\_\mathrm{LO}}$ and $P_{\mathrm{MAX}\_\mathrm{LO}}$ are the minimum and maximum, respectively. In the same way, Equation (5) is the range of the generator.

The criteria for selecting the next generator are required as in the following equations: $\sum P_{\mathrm{gen}}^i$ is the amount of output in MW from the $i$th generator; $P_{\mathrm{start}}^{i+1}$ is the power needed to start the $i+1$th generator. When the generation amount of the system is large enough to supply the cranking power of the generator to be committed, the sequential process of the restoration is performed. If the generation amount of the system is insufficient, it will take some time to meet the cranking power. In summary, we can select the next generator when the total amount of power to the $i$th is greater than the cranking power of the $i+1$th generator.

$${\displaystyle \sum }{P}_{\mathrm{gen}}^i-P_{\mathrm{start}}^{i+1}\ge 0$$

(8)

To restore the generator in a short amount of time, the generator must calculate the time required for the re-energizing. The estimation of the time for cranking the generator is performed in each step. The time can be formulated as the following equation. The generator that takes the shortest time to start is selected as the next generator by comparing the time calculated as shown below:

$$t_{{\mathrm{GEN}}_i}=S{T}_{\mathrm{GEN}}^i+ET{L}_i^{i-1}+ET{r}_i^{i-1}$$

(9)

where $S{T}_{GEN}^i$ is the start-up time for the $i$th generator; $ET{L}_i^{i-1}$ is the energizing time of the transmission lines to restore the path from $i-1$th to $i$th; $ET{r}_i^{i-1}$ is the restoration time of the transformers to the $i$th generator; $S{T}_{\mathrm{GEN}}^j$ may be described in the equation and Figure 4 as follows.

$$S{T}_{\mathrm{GEN}}=T_{\mathrm{start}}+\frac{P_{\mathrm{start}}}{Rr}$$

(10)

When supplying power from the grid at time $T_{\mathrm{on}}$, the generator starts power generation after the time required for cranking the generator. In the case of a black start unit that can be started without any external power from the power system, the $T_{\mathrm{on}}$ value is zero. Once the generator starts power generation at time $T_{\mathrm{start}}$, it generates the power up to the maximum power according to its ramp rate, $Rr$.

3.2. Optimal Restoration Approach

We will propose a new sequential restoration strategy, as shown in Figure 5. First, if a blackout occurs, the restoration process is started. We set the recovery time $t=0$ and the restoration step $i=1$. In the next stage, the black start unit is started, and we confirm the generator that can be restored in the next step. If all generators are restored, the flow is terminated. Otherwise, the flow is continued to determine the generator start-up sequence (GSS), and the start-up time of each generator to be restored is calculated. At this time, the time taken to re-energize the transmission lines and transformers is calculated. To consider this, we search for the shortest path to the generator by considering the charging currents as a weighting factor. The time taken to restore the transmission lines and transformers is calculated by counting the amount of equipment in the path and multiplying it by a certain value. Afterwards, we compute the time to re-start the generator in accordance with the generator characteristic data. By adding the respective times that are calculated, the generator with the shortest restoration time is selected for the next unit. During the process of restoration, the constraints expressed in Equations (5)–(7) must be satisfied. Unless the constraints are satisfied, the corrective actions such as power generation or load adjustment should be performed. The restoration of the next unit is started, and the load is restored in order to maintain the system balance and stability. At this time, the sum of the time to re-energize transmission lines and transformers and the time until the generator can supply the power is added to the recovery time. In the same way, the flow of the GSS is repeated until the available generators exist in the systems.

4. Case Study: Eastern Regions of South Korea

In Korea, when a total blackout occurs, the whole system is divided into seven regions to restore the whole system (Figure 6). Each subsystem has at least one black start unit and pre-assigned paths. Black start units are usually hydroelectric power or pumped storage power. If a blackout occurs, the black start unit and pre-assigned paths are restored first. After the black start unit and pre-assigned paths are restored, the rest of the generators are ordered to be restored.

In this section, we assume that a total blackout has occurred, and we choose one subsystem, which is the eastern regions, among the subsystems to restore it. The black start unit and pre-assigned paths are restored first, and the rest of the generators in the eastern regions are ordered to be restored. To find the restoration sequence of the rest of the generators, the information on the generators and the charging currents of the transmission lines are used.

Table 1. Information about the generators in the eastern regions.

Generator	Capacity (MW)	Rr (MW/h)	Pstart (MW)	Tstart (h)
G1	183	24.5	0.18	0.55
G2	186	24.5	0.14	1.05
G3	830	28.4	6.72	0.70
G4	150	1.5	4.14	1.70
G5	200	1.5	7.15	1.88
G6	280	100.0	0.42	0.05
G7	260	100.0	0.45	0.07
G8	255	100.0	0.50	0.09
G9	240	100.0	0.55	0.10
G10	100	22.5	0.05	0.30
G11	100	22.5	0.04	0.35
G12	35	15.0	0.00	0.08
G13	37	15.0	0.00	0.07
G14	282	18.0	0.00	0.20
G15	29	18.0	0.00	0.15
G16	30	18.0	0.00	0.18
G17	32	18.0	0.00	0.15
G18	210	1.0	11.88	7.20
G19	200	1.0	12.04	7.00
G20	180	24.5	0.15	0.89

shows the information about the generators in the eastern regions. It does not display the exact name of the generators due to confidentiality. G6 is a black start unit, and its capacity is 280 MW. The rest of the 19 generators are non-black start units. In the table, there is information about 20 generators, such as the capability and ramping rate in MW/h, to calculate the start-up time for the next units.

In order to determine the GSS, the time taken to energize each generator is calculated. The generator that takes the shortest time to start is selected as the next generator. When the time is calculated, the restoration time of the transmission lines to the generator and the restoration time of the transformers to the generator are considered together, and the charging current of the transmission lines and transformers is used. Figure 7 illustrates the adjacency matrix of the eastern regions. The bus numbers are re-assigned to generate the adjacency matrix. Using this matrix, we can consider the shortest path to the non-black start unit.

Table 2. Example of the generator start-up sequence of the eastern regions.

Gen	STEP 3			STEP 4			STEP 5			STEP 6
	$\mathit{S}{\mathit{T}}_{GEN}$	$\mathit{E}\mathit{T}\mathit{L}\mathit{r}$	Total	$\mathit{S}{\mathit{T}}_{GEN}$	$\mathit{E}\mathit{T}\mathit{L}$r	Total	$\mathit{S}{\mathit{T}}_{GEN}$	$\mathit{E}\mathit{T}\mathit{L}\mathit{r}$	Total	$\mathit{S}{\mathit{T}}_{GEN}$	$\mathit{E}\mathit{T}\mathit{L}\mathit{r}$	Total
G1	0.55	0.17	0.72	0.55	0.17	0.72	0.55	0.17	0.72	0.18	0.17	0.35
G2	1.05	0.17	1.22	1.05	0.17	1.22	1.05	0.17	1.22	0.14	0.17	0.31
G3	0.70	0.17	0.87	0.70	0.17	0.87	0.70	0.17	0.87	6.72	0.17	6.89
G4	1.70	0.08	1.78	1.70	0.08	1.78	1.70	0.08	1.78	4.14	0.08	4.22
G5	1.88	0.08	1.96	1.88	0.08	1.96	1.88	0.08	1.96	7.15	0.08	7.23
G7	0.08	0.00	0.08	-	-	-	-	-	-	-	-	-
G8	0.10	0.00	0.10	0.10	0.00	0.10	-	-	-	-	-	-
G9	0.11	0.00	0.11	0.11	0.00	0.11	0.11	0.00	0.11	-	-	-
G10	0.30	0.67	0.97	0.30	0.67	0.97	0.30	0.67	0.97	0.05	0.67	0.72
G11	0.35	0.67	1.02	0.35	0.67	1.02	0.35	0.67	1.02	0.04	0.67	0.71
G12	0.09	0.92	1.00	0.09	0.92	1.00	0.09	0.92	1.00	0.00	0.92	0.92
G13	0.08	0.92	0.99	0.08	0.92	0.99	0.08	0.92	0.99	0.00	0.92	0.92
G14	0.20	0.92	1.12	0.20	0.92	1.12	0.20	0.92	1.12	0.00	0.92	0.92
G15	0.16	0.92	1.08	0.16	0.92	1.08	0.16	0.92	1.08	0.00	0.92	0.92
G16	0.19	0.92	1.11	0.19	0.92	1.11	0.19	0.92	1.11	0.00	0.92	0.92

shows an example of the GSS in the eastern regions of South Korea. $S{T}_{\mathrm{GEN}}$ means the start-up time for each generator, and $ETLr$ is the energizing time of the transmission lines and transformers for restoring the generator. Total means the total time taken to restore the generator, including the time taken to restore the transmission lines and transformers. The highlighted cells are the generators that are selected as the next units in each step. In the eastern regions, the pre-assigned paths are G6 (Black start unit) →58→6→19→20→30→25→26→29→73→G20, and G6 is started as the black start unit in the first step. In the second step, G20 is started as well. Afterwards, we calculate the total times for all available generators and compare them. In the third step, G7, which has the shortest total time, is restored. At the end of the third step, the total times of all generators are compared again, and in the next step, G8 is restored. G7–G9 are sequentially restored, since these are located near each other and are the same type. In the same way, the restoration sequence is repeated until the available generators exist in the systems.

Table 3. The results of the simulation: The eastern regions.

Step	Restored Generators	Restoration Path
1	G6	-
2	G20	58→6→19→20→30→25→26→29→73
3	G7	60
4	G8	57
5	G9	59
6	G2	74
7	G1	75
8	G3	76
9	G11	43→41→17→18→15→16→67
10	G10	68
11	G14	13→14→64
12	G15	63
13	G16	65
14	G17	66
15	G12	12→61
16	G13	62
17	G4	21→69
18	G5	70
19	G18	27→34→31→23→71
20	G19	72

shows the results of the simulation. According to the strategy, the generator start-up sequence (GSS) is determined using generator characteristic data and the enhanced Dijkstra algorithm. All the generators in the system are restored sequentially, and at each restoration step, the system conditions are reflected to calculate time taken. Additionally, in order to maintain the system balance and stability, sufficient load is restored during the restoration, and the total load restored in the proposed restoration strategy of the eastern regions is 2728.80 MW.

Table 4. Comparison of generator start-up sequence.

Step	Proposed Method	Existing Method
1	G6	G6
2	G20	G20
3	G7	G7
4	G8	G8
5	G9	G9
6	G2	G1
7	G1	G2
8	G3	G3
9	G11	G18
10	G10	G19
11	G14	G4
12	G15	G5
13	G16	G10
14	G17	G11
15	G12	G12
16	G13	G13
17	G4	G14
18	G5	G15
19	G18	G16
20	G19	G17

shows the comparison of the generator start-up sequence between the proposed method and the existing method using mixed integer programming (MIP). The GSS is determined through the MIP. The existing method only considers the restoration of the maximum system capacity. The case studies from both methods are shown in the table below.

As the proposed method aims to restore the system within the shortest amount of time, the generators that can be activated in a very short time are restored preferentially. On the other hand, the existing method intends to restore the system with the maximum capacity restoration.

The time to commit all generators is 36 min for the proposed method and 55 min for the existing method. Also, the total time is 657 min using the proposed method and 643 min using the existing method when all generators reach the maximum power-generating outputs. In the proposed method, the recovery times of transmission lines and transformers are included in the restoration time; on the other hand, the time using the existing method only takes into account the start-up time of the generators.

5. Conclusions

In Korean systems, there are the pre-assigned paths and black start units in each subsystem to restore the systems. However, there is no specific restoration methodology afterwards. Therefore, it is essential to develop a restoration strategy for determining the generator start-up sequence (GSS) and the paths that can re-energize the generators according to the GSS. Also, this restoration strategy should be performed within the shortest time to minimize the economic and social loss. In this paper, we propose a sequential and systematic restoration strategy that can minimize the generator restoration time and considers the characteristics of the Korean power system.

In this paper, we propose a sequential restoration strategy based on an enhanced Dijkstra algorithm for Korean power systems. The new methodology is intended to minimize the time taken to restore the generators that can be restored. At this time, some loads are restored to maintain the system voltage and the stability of generating units. In the methodology, we developed a strategy for the determination of the generator start-up sequence in order to restore the system in the shortest time, an adjacency matrix was created, and the charging current of the path was considered as the weighting factor. The proposed method was verified by an empirical system (in the eastern regions of South Korea). In the future, we will apply the proposed methodology to other regions.