Abstract: In this study, a new method is presented for transmission expansion planning in restructured power systems. In this method, the future values of maximum load demanded, bid of generators to sell power and bid of consumers to buy power are assumed uncertain. The objective of the planning problem is the minimization of the total investment cost. The constraint of the problem is satisfying two constraints with a high probability: first, the total congestion costs must be limited to a certain value and second the n-1 reliability criterion must be satisfied by the transmission network. Due to extent of the problem solution space in this study, simulated annealing algorithm is used to determine the optimal plan. In addition, a method is used to calculate the above-mentioned probability with enough accuracy by a small number of iterations. This method, with respect to the Monte-Carlo simulation method, considerably reduces the amounts of calculations. Furthermore, a number of remarks for solving the problem are employed that they reduce the solution space and strongly decrease the amount of calculations. Efficiency of the proposed method is illustrated over the IEEE-RTS power system.
INTRODUCTION
In the past two decades, deregulation (restructuring) has been introduced to many countries. In regulated environment, a vertically integrated utility has obligation to serve its customers as economically as possible with an acceptable degree of continuity and quality (Wang and McDonald, 1994). But after the restructuring, competition in generation is initiated while transmission system remains monopoly.
The objective of Transmission Expansion Planning (TEP) in the regulated environment is to serve the forecasted load demand as economically as possible, while reliability constraints must be satisfied (Wang and McDonald, 1994). Reliability constraints are usually assessed by line outage security criteria (e.g., n-1 reliability criteria) (Wood and Wollenberg, 1996).
In the restructured power systems, producers and consumers compete for trading the electricity power through an electricity market. Therefore transmission system must provide a non-discriminative and reliable environment for the market participants.
In the restructured power systems, transmission investment can be managed by monopoly management and market driven transmission investment while transmission planning can be managed by analytical tools which should have the abilities to perform economic assessment and technical assessment (Lee et al., 2006). An overview of TEP in deregulated environment can be found in Lee et al. (2006), Wu et al. (2006), Buygi et al. (2003) and David and Wen (2001).
Deregulation has increased uncertainties in power systems (David and Wen, 2001; De la Torre et al., 1999). The most important of these uncertainties are loads and bids of the market customers.
Market based approaches, meta-heuristic optimization approaches, mathematical optimization approaches and game theory approach have been used to solve TEP problem in deregulated environment.
Market based approaches is a widely used method for TEP. Market based planning concept is the integration of financial and engineering analysis that considers the economics as well as the physical laws of generation, load and transmission. For example, four market based transmission planning approaches were proposed by Buygi et al. (2004).
Meta-heuristic optimization approaches such as GA (Lu et al., 2005), Chance Constrained Programming (CCP) (Yang and Wen, 2005), Expert System (ES) (Kandil et al., 2001), fuzzy-set theory (Sun and Yu, 2000), Pareto-based solution technique (Orths et al., 2001), Simulated Annealing (Braga and Saraiva, 2005) and LP-Based Particle Swarm Optimization (Kavitha and Swarup, 2006) have been proposed to solve TEP problems.
Mathematical optimization approaches, such as Benders decomposition (Shrestha and Fonseka, 2004) and branch and bound algorithm (Choi et al., 2005a, b) are continuously used for TEP in deregulated environment.
In deregulated market, game theory (Singh, 1999) was also applied as TEP approach. Contreras and Wu (1999, 2000) and Yen et al. (2000) have presented a cooperative game theory approach to solve TEP problem in a deregulated environment.
Another algorithm was proposed by Fang and Hill (2003). Fang and Hill (2003) explored a new strategy to respond to changes in power flow patterns. De la Torre et al. (1999) have also developed a TEP approach which is able to quantify and hedge risk.
Any insufficiency in transmission network capacity can cause congestion. The congestion makes market into a discriminative environment for the market participants. Therefore, in this study, the congestion of the network is limited. The n-1 reliability criterion is also considered to provide a reliable network.
To plan the expansion of a transmission network with certain congestion and reliability levels, we may have many plans with different investment costs that we must select the cheapest plan. Therefore the investment cost is an important criterion for the transmission expansion planning.
In this study, transmission expansion is planed, in which, firstly the needed investment cost is minimized, secondly the total congestion cost is limited to a predefined value and thirdly the n-1 reliability criterion is satisfied.
In this study, uncertainties in load demanded and bids of the producers and consumers are assumed random with certain probability density functions. Uncertainties make different probable conditions for the future conditions of the system; hence we evaluate the probability of limiting the congestion cost and satisfying the n-1 reliability criterion. Also in this study, a method to calculate the probability value is presented that reduces needed computations with respect to the Monte-Carlo simulation method.
DEFINITION OF THE TRANSMISSION
EXPANSION PLANNING
Here, Transmission Expansion Planning (TEP) problem is defined, in which, we assume each transmission line of every expansion plan is included a number of the similar circuits has known specification; we want to determine the expansion plan that firstly has minimum investment cost and secondly satisfies two constraints in different system conditions with a high probability. The first constraint is that the total congestion cost of the plan must be smaller than a specified value. The second constraint is that the plan must satisfy n-1 reliability criterion. This problem can be defined as:
(1) |
Subject to:
(2) |
where, X presents an expansion plan; X is a vector of integers. Each element of the vector X corresponds to a right-of-way (line) of the transmission network, where new circuits can be constructed in or added to. Each element of the vector represents the number of new circuits that can be added to the corresponded line.
| IC (X) | : | The total investment cost of expansion plan X |
| Pr (X) | : | The probability of satisfying 2 constraints in every system condition: first, the total congestion cost of the plan X is smaller than the value CCmax (maximum acceptable limit of the congestion cost of the network), second, the plan X satisfies the n-1 reliability criterion |
| Prmin | : | Minimum acceptable probability for Pr (X) |
The number of expansion plans for a real power system is very large, so the evaluation of the probabilistic constraint (inequality constraint (2)) for all plans is impossible. Hence, we employ the simulated annealing algorithm. By using this algorithm, we can obtain optimal plan by evaluating only a small number of plans. In the next sections, we express different aspects of the TEP problem and the procedure of solving it.
UNCERTAINTIES AND DIFFERENT SYSTEM CONDITIONS IN THE FUTURE
There are many uncertainties in the transmission expansion planning for the restructured power systems (Buygi et al., 2003). In this study, maximum load demanded of consumers, bid of producers (generators) to sell power and bid of consumers to buy power are considered uncertain and probabilistic. We assume a random variable (for example with the normal probability density function) for each of the uncertainties. Because there are many random uncertainties and each random uncertainty can include a variety of values, we can form numerous various combinations of values of all uncertainties. Each combination represents a special condition of the power system, so we define it as a condition. Therefore, in each condition, the values of the random variables are known, thus the values of maximum demand of consumers, the generator and consumer bids are known. Because the uncertainties make various probable conditions for the system in the future, in the inequality (2) we evaluate the probability of satisfying the constraints (i.e., Pr (X)).
MARKET SIMULATION
As it will be expressed in the following section, to evaluate the constraint of the transmission expansion planning problem (inequality 2), we must calculate active power of generators, supplied load of consumers, flow of lines and Locational Marginal Prices (LMPs) of buses for different expansion plans and different values of uncertainties (different future conditions). These values are obtained by simulating the electricity market. Therefore, in this section, the market simulation is stated.
We consider a special expansion plan and a special condition. Without losing generalization of the problem, here we consider a pool market with nonexclusive auction where the electrical power is sold to all consumers and/or is bought from all producers based on the locational marginal prices (LMPs) of buses. In other words, here the system condition is known; so maximum load demanded in every bus, bid of every producer (generator) and bid of every consumer (load) are known. Now, the pool market is modeled by following Optimal Power Flow (OPF) (Buygi et al., 2004):
(3) |
Subject to:
(4) |
(5) |
(6) |
(7) |
| PG | : | Vector of active power of generators |
| PD | : | Vector of active power of loads |
| CG | : | Vector of bid of generators |
| CD | : | Vector of bid of loads |
| B | : | Linearized Jacobean matrix |
| H | : | Matrix of Linearized line flows |
| δ | : | Vector of voltage angles |
| : | Vectors of minimum and maximum power generation limits | |
| : | Vectors of minimum and maximum demanded load limits | |
| : | Vector of maximum line flow limits and losses are ignored |
By solving the above OPF, the generator powers (PG) and the supplied load of buses (PD) and LMPs of buses are obtained. The LMPs are the Lagrange multipliers of DC Load Flow constraints expressed in the Eq. 4. We can also calculate flows of lines (H. δ).
CONGESTION COST
The total congestion cost of lines is a good criterion to evaluate the function of the transmission network in the competitive environment for the power system. Hence, in this study, one of the constraints of the TEP is limiting the total congestion cost of all lines (inequality 2). To evaluate the inequality 2, we must calculate the congestion cost of the lines of plans for the different conditions of the system. Therefore, we consider a certain expansion plan and a certain system condition. For this expansion plan and the system condition, we simulate the electricity market, according to the previous section and we obtain the lines flows and LMPs of the buses. Then we obtain the congestion cost of every line of the plan as follows:
(8) |
| CCij | : | The congestion cost of the line between buses i and j |
| Pij | : | The transmitted power of the line between buses i and j |
| LMPi and LMPj | : | The LMPs of the buses i and j, respectively |
Now the total congestion cost of all lines of the plan is obtained as follows:
(9) |
| CCl | : | The congestion cost of the line l |
| n1 | : | The number of lines of the plan under evaluation |
n-1 RELIABILITY CRITERION
Occurring of faults in the transmission networks is unavoidable. A fault in a transmission line may cause the line is disconnected. If a transmission network does not have enough adequacy level, a line disconnection may cause overloading in other lines and bringing out the network from normal state and consequently shedding some loads. Therefore, the transmission network must be had enough reliability level. In this study, the n-1 reliability criterion has been considered to plan the transmission network (inequality 2). Hence, in continuation, the n-1 reliability criterion and its conditions are defined:
We assume that a power system is working in a certain condition with a known generation and load values, in the meanwhile, a contingency (for example a line outage) occurs. If any network security limits (including lines and voltage ratings) are not violated, the n-1 reliability criterion is satisfied. Here, we assume that the reliability of the system against the contingencies of generating units has been considered in the generation planning. In addition, because in this study the DC load flow model is used, it is assumed that the voltage constraints of all buses are usually satisfied. Therefore, here the n-1 reliability criterion is defined as if the outage of any line of a network does not cause overloading or system disconnection, then the network satisfy the n-1 reliability criterion. To evaluate the n-1 reliability criterion in a specified system condition and for a specified expansion plan, we do below stages:
| • | First using Eq. 3-7, powers of generators and loads for the plan and the condition are calculated. |
| • | One line of the considered plan is eliminated. |
| • | The Network disconnection is evaluated. If there is no disconnection, we go to the next stage. If there is disconnection, the n-1 reliability criterion has not been satisfied and the evaluation is finished. |
| • | The DC load flow is performed over the network and the flows of the lines of the network is calculated. If none of the lines do not overload, we go to the next stage, otherwise the n-1 reliability criterion has not been satisfied and the evaluation is stopped. |
| • | If the elimination of all the lines of the plan has not been evaluated, we go back to the stage 2 to evaluate the other lines; but if all the lines has been evaluated, the evaluation process has been ended and the considered plan satieties the n-1 reliability criterion. |
PROBABILITY COMPUTATION
The probability Pr (X) must be calculated for the considered plan. To calculate the probability accurately, we must have all system conditions and their probabilities. Then we must evaluate the congestion cost of lines and n-1 reliability criterion. But the numbers of the possible conditions even for a small number of random variables (uncertainties) are very large. In addition, needed computations for evaluating the lines congestion and reliability are very large. Hence, the accurate computations of this probability needs long time, especially this computation must be done for many expansion plans. Therefore, here we apply a method that can estimate the probability with enough approximation by evaluating a small number of conditions. This method of calculating the probability is expressed as follows:
| • | We generate a limited number of sample conditions (for example 30 sample). Each sample condition is obtained by randomly sampling from all the uncertainties, that is, to generate each condition, we must randomly sample from each variable depending on its probability density function |
| • | We evaluate the congestion cost constraint (CC≤CCmax) for each of the sample conditions. If this constraint is satisfied, the n-1 reliability constraint is evaluated too. If both constraints are satisfied, the number one will be referred to the sample and if one of the two constraints is not satisfied, the number zero will be referred to the sample. We call the referred number to each sample as sample number |
| • | We compute the average of the random numbers and call it to population proportion, denote P. |
| • | We obtain 95% reliable distance as (Wonnacott et al., 1977): |
| (10) | ||
| where, RD 95% reliable distance and ns is the number of samples. The 95% reliable distance means that the accuracy of considered probability (Pr(X)) locates in distance [P-RD, P+RD] with 95% probability. In the statistical theory, the 95% reliable distance is introduced using the central limit theorem in the subject of spatial estimation. | ||
| • | If the 95% reliable distance is smaller than the considered limit for it (RDmax), we consider the population proportion (P) as probability Pr (X) and we stop. Otherwise, we go to the next stage (stage 6). |
| • | We generate a new sample condition and evaluate the congestion cost and the n-1 reliability constraints for it and then we determine the sample number for the new condition. We add this sample to the previous samples and go back to the stage 3. |
In the above method, RDmax depends to needed accuracy for the probability computation. By using this method, we can calculate the probability with needed specified accuracy by a small number of samples (with respect to the Monte-Carlo simulation method). Therefore, this method reduces the computations strongly.
SIMULATED ANNEALING AN OVERVIEW
Simulated annealing is a metaheuristic optimization procedure to solve combinatorial problems. This approach usually provides good solutions in the sense that they improve a performance index, but it is not usually possible to guarantee global optimality. In the simulated annealing procedure, we move away from one solution by sampling another one. The performance index is calculated for the new solution. If the new solution improves the performance index, it will be accepted. If the new solution is worse and dose not improve the index; it can still accept, depending on a small acceptance probability. So it is avoided to locate in local optima and a wider search on the solution space is done until a more promising area is located. The acceptance probability of the worse solution is progressively reduced to avoid oscillation and to make sure that the search is more chaotic in the beginning and concentrated in a promising area as the algorithm proceeds. The simulated annealing algorithm is summarized as (Braga and Saraiva, 2005):
| • | Select an initial solution |
| • | Evaluate |
| • | Assign |
| • | Sample a new solution in the neighbourhood of the current solution
at iteration ITC and compute the evaluation function |
| • | Testing |
| • | If |
| • | If |
| • | Else, get a random number rp in [0.0, 1.0] and compute the probability of accepting worse solutions at iteration ITC by (Eq. 11): |
(11) |
where, KT is the control parameter that is called system temperature in analogy with the original application of annealing
| • | if |
| • | End if a stopping rule is reached; otherwise, let ITC = ITC+1 and go back to step 4 |
Along the algorithm, the temperature (KT) is lowered in a slow pace. Usually, the temperature evolves by levels, meaning that each one is used during a fixed number of iterations. After that, the temperature is lowered by a coefficient α, which is inferior but usually close to 1.0.
EVALUATION FUNCTION
To use the simulated annealing algorithm for solving the TEP problem, an evaluation function should be defined. Therefore, we define the evaluation function as follows:
(12) |
(13) |
where, f (X) is the evaluation function of plan X. The plan X will be better, if the corresponding function value is smaller. IC (X) is the total investment cost of the plan X and ICmax is the investment cost of the most expensive circuit. Pr (X) and Prmin were previously defined. M is a penalty factor that has been defined in (Eq. 13). According to (Eq. 13), if the plan X is acceptable (i.e., it satisfies the constraint (2)), M will be zero; But if the plan X is not acceptable, M will be a large number for example in here it is assumed equal to (10xICmax). In fact, the term M raises the value of the evaluation function for unacceptable plans. Therefore, the evaluation function has been defined so that the simulated annealing algorithm selects the plan that has the smallest investment cost among feasible plans that satisfy inequality constraint 2.
REMARKS FOR SOLVING THE TEP PROBLEM
The TEP problem was defined by Eq. 1 and 2. According to this problem definition, we want to find a plan which has minimum investment cost and satisfies the constraint Eq. 2. In the real transmission networks, a large number of expansion plans can be considered; so the evaluation of all the plans needs very long time. Hence, we employ the simulated annealing algorithm to find the optimal plan. The simulated annealing algorithm and the evaluation function that is used for it, was introduced earlier. There are some remarks to use the algorithm for solving this problem.
These remarks are expressed as follows:
| • | The initial solution is set the existence transmission network, i.e., none of lines has new circuit. |
| • | In each stage of the simulated annealing algorithm, a new solution in the neighborhood of the old solution must be generated. To generate the new solution, if the previous solution is feasible, one circuit will be reduced from a random number of its lines (elements of the vector X) and if the previous solution is unfeasible, one circuit will be increased to a random number of its lines. Furthermore in 20% of randomly selected iterations, one circuit of some randomly selected lines is exchanged, i.e., one circuit is reduced from a line and one circuit is added to another line. |
| • | Whereas in each iteration of this algorithm, for example the
iteration i, the optimal plan |
At each iteration of the simulated annealing, the generated new plan must be evaluated. To evaluate the plan, the probability Pr (X) must be compared with the Prmin. The probability Pr (X) is calculated according to the method expressed earlier. Computing of the Pr (X) needs long time. So that it is expressed, to calculate the probability Pr (X) for the various system conditions, firstly we must calculate the total congestion cost of all lines and evaluate its limit; secondly, we must evaluate the n-1 reliability criterion for the considered plan in accordance with the method expressed earlier. Hence, to reduce the calculation, we implement the below remarks:
| • | First, we simulate the electricity market for the evaluated
plan and calculate the generation and load powers, the LMPs and the
total congestion cost. Then we evaluate the constraint of limiting
total congestion cost |
| • | In the meanwhile evaluating the n-1 reliability, for eliminating each line and for various system conditions, only the generation and load powers change, but the network structure does not change. Therefore, for each plan, when we obtain the impedance matrix of the network corresponding to eliminating a line, we save it and then we use it to calculate the generation and load powers for all conditions. |
APPLICATION OF THE PROPOSED METHOD TO A TEST POWER SYSTEM
The proposed method is applied to the 24-bus test system (IEEE-RTS) (IEEE Reliability Test System, 1979) and (Fang and Hill, 2003), which is shown in Fig. 1. Figure 1 shows only existing transmission lines. The lines 1 to 34 have one or two existing circuits and the lines 35 to 41 (Table 1) are new right-of-ways (Fang and Hill, 2003) that can be constructed.
We consider below assumptions for this system:
| • | We assume that every line (right-of-ways) can be expanded up to three similar circuits. Therefore, the total combinations (plans) that can be generated from expanding the lines become more than 1.5 billions (1.5099x109). It is seen that for this comparatively small power system, the number of the expansion plans are very large so that the analysis of all the plans is impractical. Therefore, application of the Simulated Annealing algorithm is necessary to find the optimal plan. |
| Fig. 1: | 24-bus test system (IEEE-RTS) |
| Table 1: | Line data of the studied transmission network (IEEE-RTS) |
| • | We assume each bus has at most one producer and one consumer. |
| • | The maximum load demanded in each bus is assumed as random variable with the normal distribution. The present loads of all the buses are shown in Table 2. We assume the future mean load of each bus is equal to its present value multiplied by 1.1. It is also assumed the standard deviation of each load is equal to 10% of its mean value. |
| • | Bid of every producer (generator) is assumed as random variable with the normal distribution. The capacity and future mean bid of the generators are shown in Table 3. We assume that the standard deviation of each producer (generator) is equal to 10% of its mean value. |
| Table 2: | The mean load demanded of the IEEE-RTS system (Mw) |
| Table 3: | Generator`s data of the IEEE-RTS system |
| Table 4: | The parameters of solving the TEP problem for the 24-bus test system |
| • | We assume that the bids of all loads are equal to the maximum bid of generators so that the maximum load demanded at each bus is always supplied so far as possible. In fact, we assume consumers (loads) do not bid any price; in other words, all consumers agree to buy the power with the maximum bid of generators, i.e., we have one sided pool market. |
The simulated annealing algorithm was performed. The parameters of the problem definition and method of solving it are shown in Table 4. In Table 4, the rows 1 and 2 show the parameters of the TEP problem. In accordance with these parameters, we search a plan which does not have any congestion and satisfies the n-1 reliability criterion with a probability 0.99. The rows 3 and 4 of the Table 4 show the parameters of the probability calculation which are defined earlier. The rows 5 to 9 of the Table 4 express the parameters of implementation the simulated annealing method. In row 6, the initial temperature has been selected so that the initial probability of acceptance of the bad solutions becomes according to the row 8 of Table 4. The ninth row of the Table 4 shows the number of successive iterations that the temperature is hold constant.
After implementing the simulated annealing algorithm, the optimal plan was obtained. In accordance with the optimal plan, two circuits in line 11 and one circuit in line 10 must be added. The investment cost of the optimal plan is 560000. The optimal plan was obtained among 15 iterations of the simulated annealing algorithm.
CONCLUSIONS
In this study, a new method was presented for network transmission expansion planning in restructured power systems. The future values of maximum load demanded, bid of generators to sell power and bid of consumers to buy power were assumed uncertain and probabilistic. The transmission expansion planning was introduced as an optimization problem. The objective of the problem was the minimization of the total investment cost. The constraint of the problem was, in which, the solution satisfied two constraints with a high probability: first, it limited the total congestion costs to a specified value and second it satisfied the n-1 reliability criterion for the transmission network. Due to extent of the problem solution space, simulated annealing algorithm was used to determine the optimal plan. In addition, a method was used to calculate the above-mentioned probability with enough accuracy by a small number of iterations. By this method, the amount of calculations was considerably reduced with respect to Monte-Carlo simulation. Furthermore, a number of remarks for solving the problem were employed that they reduced the solution space and strongly decreased the amount of calculations. Efficiency of the proposed method was illustrated over the IEEE-RTS power system.