Abstract
The
increasing complexity of the transmission expansion planning problem in the
restructured industry makes simulation the only viable means to evaluate and
compare the performances of different plans. Ordinal optimization is an
approach suitable for solving the simulation-based multiyear transmission
expansion planning problem. It uses crude models and rough estimates to derive
a small set of plans for which simulations are necessary and worthwhile to find
good enough solutions. In the end, reasonable solutions are obtained with
drastically reduced computational burden.
INTRODUCTION
TRANSMISSION EXPANSION PLANNING (TEP): aims at strengthening an existing transmission
network to serve power producers and customers in an optimal way. Due to the
large-scale nature of a transmission system and its inherent complexities, TEP
has always been a complex problem. It has been formulated as a large-scale
mixed-integer nonlinear optimization problem. Various optimization techniques
have been used to solve the problem, such as linear programming dynamic
programming, nonlinear programming and mixed-integer programming. At the same
time, various divide-and-conquer strategies such as Benders decomposition hierarchical
decomposition, and branch-and-bound algorithm have also been applied to solve
large-scale TEP problems.
Industry restructuring in recent
years has resulted in the separation of generation and transmission systems and
the introduction of competitive electricity markets. A comprehensive
methodology, called the Transmission Economic Assessment Methodology (TEAM),
was developed by the California ISO and London Economics to evaluate the
economic benefits of transmission expansion .
The economic impacts of alternative transmission enhancement schemes are
different for different market participants. The participants of an electricity
market include independent power producers, large customers, transmission
network owners, and the independent system operator. The interests of different
parties vary a great deal. Furthermore, other factors, such as uncertainties in
generation patterns, transmission congestions, and regulatory policy changes,
need to be considered in the evaluation. Transmission expansion planning in the
restructured industry has become much more complicated than before. No simple
mathematical model can capture all the major factors in the transmission
expansion planning. Computer simulation, in particular Monte Carlo simulation,
has become the only viable approach for assessing alternative plans for
transmission expansion.
If, on the other hand, analytical approaches
can be used to complement the simulation-based search methods so that the
search for optimum performance can be narrowed down to a set of good enough solutions,
then the computational requirements may be manageable. Ordinal Optimization
(OO) is a method that provides a theoretical foundation for such an approach.
In Section II, a TEP problem is
described. Ordinal optimization theory is introduced in Section III. In Section
IV, ordinal optimization theory is applied to solve the TEP problem. In Section
V, numerical examples are given to illustrate the approach. Conclusions are
drawn in Section VI.
TRANSMISSION
EXPANSION PLANNING PROBLEM
We
assume that there is an entity, which may be the transmission company, the
independent system operator (ISO), or the regional transmission organization
(RTO), who is responsible for planning the expansion of the transmission
network (i.e., when and where to install new lines, capacities and types,
etc.). The economic effects of TEP on various market players are different.
Transmission owners are concerned about their investment returns; generation
companies are about congestion rents affecting their profits; the system
operator is about congestion revenues; and the consumers are about electricity
prices after network enhancement. On the other hand, societal outage costs may
very well be reduced after adding line capacities in the network. The
magnitudes of the economic effects on generators, consumers, the system
operator, and the society depend on system operating conditions that change
from moment to moment. The benefit of an expansion scheme to an individual
participant may take several years to realize. To simulate the effects of
multiple years of an expansion plan on market players, an hourly-based dispatch
model is more or less necessary for the whole expansion time horizon.
Industry restructuring is an ongoing
process in many parts of the world. Its initial focus has been on the
competitive market for generation. Transmission systems remain largely
regulated, and the rules and regulations for transmission expansion are mostly
unsettled. The obligations and responsibilities of the participants are not
fully defined, except that some general characteristics can be detected. The
TEP has become an optimization problem whose variables are strongly stochastic
and lumpy (discrete), with multiple participants having different objectives.
Traditional optimization formulations and techniques are no longer appropriate.
In this paper, we propose the application of ordinal optimization to the TEP
problem. The development of OO is motivated by the complexities of large-scale,
stochastic, discrete-event nonlinear dynamic systems, such as manufacturing
systems, whose performance can only be evaluated by way of computer
simulations.
Because the TEP
problem is not fully standardized and specified, we will not attempt to give a
definitive algorithmic solution to the problem. Instead, our goal is to
demonstrate that the OO approach is viable. Therefore, our formulation of the
TEP problem and its solution algorithm are for illustration purposes only. For
that purpose and for the ease of exposition and understanding, the classical
TEP formulation which has been commonly used in the past decades is used in
this paper. The OO approach can be adopted by the planners to a formulation
that incorporates the issues and considerations relevant to individual systems
and to the development of models and performance indexes that the OO approach
requires.
A.
Classical TEP Model
For simplicity, we use the
classical optimization model in this paper to represent the multiyear TEP
problem. We assume that the objective function of the exact TEP model is to
minimize the total cost, which is formulated as (1)
Where
T represents total cost; I
represents the investment cost; G
represents production cost under the optimal dispatching condition; and L represents the cost of loss of load
as a result of contingencies.
We assume that the expanded line
capacities are added yearly in a Y-year span and that the right-of-ways planned
and authorized for building new lines are already specified. The transmission
planner has the option to decide on which right-of-ways to use in order to
build new lines and their capacities. Each combination of the lines built in
one year is called a transmission expansion scheme for that year. The annual
planning schemes over the span of Y-years are illustrated in Table I. Assume
there are right-of-ways authorized for building new lines, the number of lines
built on the right-of-way in the year is .
represents
the expansion scheme of the year. The whole table represents the expansion
scheme of the whole planning span.
1)
Investment Cost: The investment cost is
calculated as the total expansion investment over the planning span. It is
formulated as (2)
where
Iym symbol represents the expansion investment on the mth
right-of-way in year ;Iy is the investment cost in year y ;√ is the
discount rate; and is the investment value corresponding to the beginning year
of the investment. The Net Present Value (NPV) approach is used here.
2)
Production Cost: The commonly used quadratic function (3) is used to represent
the production cost Gh function of a generator. The optimal hourly production
cost can be obtained by minimizing the total generation cost for each hour h=1……,..8760,
subject to the power balance (dc load flow) and other operating constraints.
Where
gi represents the real power generation of the generator on bus i ;ai
,bi , and ci are
the constant coefficients of power generation; Dh is the total load
in hour h ; Gij represents the susceptence between node i and j ;θi
represents the phase angle of node i ; iij)‘ and iij
represent the upper and lower limits of line ij; gi and (gi)’represent
the upper and lower limits of gi ; and N is the total number of
nodes.
For year y, the total
production cost Gy is the sum of for 8760 h
The
NPV of the production cost for the whole planning span can be represented as
(5)
3)
Cost of Loss of Load: In the abnormal operation conditions, a good network
configuration may help to avoid load shedding. Providing a reliable network
under system contingencies is one of the goals of transmission expansion
planning. The dispatch modes are different for different transmission network
configurations.
The loss of load
cost (LOLC) depends on the cost of load shedding due to a system contingency.
The LOLC can be calculated using one of the three loss-of-cost functions:
exponential, quadratic, and hyperbolic functions . In this paper, the quadratic
form Ø( o) as in (6) is used to represent LOLC
Where Øn, h represents LOLC at node in hour
h ; ∆ represents the amount of lost load, ∆=(Dnh -dn
) , where Dnh is the load at node n in hour h ; and
dn is the load at node n after the contingency. ξ is a rough-estimated cost assuming that half
of the total load is lost. In south Asian, ξ is usually assumed to be 30–60 times the
regular electricity price . The value of LOLC caused by the contingency in
hour h , Lh , can be formulated as (7)
For
the given probabilities of all contingencies, we can obtain the expected hourly
LOLC for all contingencies considered. The expected hourly LOLC, E Lh is formulated as (8)
Where K is the size of the
contingency set considered; and Pk is the probability of contingency
. The yearly LOLC can be formulated as the summation of , ELh as shown in (9)
The
total LOLC over the whole planning horizon can be obtained by (10)
To
solve the proposed TEP model, (1)–(10), both the normal and abnormal operation
modes of all hours of the whole planning span need to be calculated. Obtaining
the exact solution for a multiyear TEP problem will result in a huge
computational burden.
ORDINAL OPTIMIZATION
The
ordinal optimization theory developed by Ho et al. is for
solving simulation-based complex optimization problems. It has recently been
applied to many areas in power systems such as optimal power flow (OPF) with
discrete control and bidding strategies of power suppliers in markets . In this paper, the theory is applied to solve the multiyear transmission
expansion planning problem.
The goal of ordinal optimization is to find
good enough solutions for a complex optimization problem. A good enough subset
G (θ) is the subset consisting of the top best solutions, say, the top 5% in
the solution space. However, it is difficult to find the subset G for a
simulation-based problem unless all the solutions in the solution space are
calculated and compared. The OO method uses rough estimates from a crude model
to rank the solutions. However, even with the use of a crude model, estimation of
performance values for all solutions of a large solution space θ may not be computationally feasible. Ordinal
optimization theory uses a representative set with N samples, θN ,
to represent the original solution space
. If the elements of the representative set are randomly selected, the
probability of an event where at least one of the N samples will fall within
the top 5% of the whole solution space is
If
N=1000 , then the probability that the top 5% good enough solutions are not in
N=1000 the samples is P=0.951000= 5.29 x10-23≈0, which is
extremely small (of the order x10-23 ). In this paper, we will use
N=1000 samples to represent the solution space θ . However, calculating all N=1000
accurate solutions by computer simulations is still a formidable task. The goal
of ordinal optimization is to reduce the number of necessary but
computationally costly simulations.
A.
Good Enough Subset and Selected Subset
Within
the defined finite solution space θN(|θN|=1000) the
number of top n% solutions is g=N*n% . The top solutions compose the “good
enough” subset G of θN . In
the later sections of this paper, is selected to be 1000*5%=50.
The multiyear TEP problem proposed in
Section II can symbolically be represented as finding the minimum performance
value T among all possible expansion schemes
Where
x the variable corresponds to a set of line expansion schemes. For example,
building certain lines on the approved right-of-ways in each year of the Y-year
span is referred to as an expansion scheme. Assuming there are 1000 potential expansion
schemes x1……x1000 , then a high quality solution could be
found by calculating the performance values for 1000 schemes,T1……….T1000
, and choosing for the best one. Such and exhaustive search method is what we
want to avoid. Instead, we reduce the search space to a small selected subset
S(θN) and perform simulations within the selected subset.
The
key to the determination of a selected subset is to be sure that the selected
subset intersects with the “good enough”subset. The selected subset may be
determined by using certain fast evaluation methods, such as mathematical
algorithms, heuristics, etc., based on the crude approximate models of the
system.
For example, we may first use a
crude model to obtain a rough estimate of the performance values T’1,….,T’1000
for the potential expansion schemes x1…..x1000 in problem
(11). The rough evaluation should take much less time than the accurate
calculation. Thus, the top 50 schemes found by the crude model may not be the
same as (i.e., not aligned to) the top 50 schemes (subset G) obtained from the
accurate model. However, if we select enough schemes (subset S) from the rough
estimates, the selected subset S will have a high probability of overlapping
with the elements in G. The number of overlapped elements with G is called the
alignment level . Our goal is to find a subset S including at least elements of
G. The probability of this event is called the alignment probability . For a
given alignment probability and the alignment level , the size of the selected
subset S is determined by the requirement that the probability that S overlaps
the good enough subset G with at least elements is greater than p
For a
given alignment probability and the alignment level , the size of the selected
subset S is determined by the requirement that the probability that S overlaps
the good enough subset G with at least elements is greater than P.
Obviously,
the determination of the size of the selected subset is dependent on the nature
of the underlying optimization problem. The ordinal optimization theory broadly
divides the optimization problems into several classes. The classification is
accomplished by way of constructing an ordered performance curve to be
introduced below.
B.
Ordered Performance Curve
The ordered
performance curve (OPC) may be constructed based on the estimated performance
values obtained by the crude model. The 1000 estimated performance values are
arranged in an ascending order (for minimization problem). The X axis of the
resulting plot is the scheme labels; whereas the Y axis represents the
(estimated) performance values. The shape of an OPC determines the nature of
the underlying optimization problem.
The shapes of OPC curves can be broadly
categorized into five classes: flat, u-shape, neutral, bell, and steep,
For a minimization
problem, a smaller performance value means a good scheme, and a bigger
performance value means a bad scheme. For a problem, if more small-value schemes
are found, then the problem has more good schemes. In Fig. 1, the problem with
a flat-shape OPC has more good schemes. The five OPC curves in the figure
represent five classes of optimization problems: 1) flat—many good schemes, 2)
U-shape—many good and bad schemes, 3) neutral—good and
bad
schemes equally distributed, 4) bell—many intermediate schemes, and 5)
steep—many bad schemes.
C.
Size of Selected Subset
In , through
extensive simulations and statistical analysis, a formula is derived to relate
the size of the selected subset S to i) the shape of the OPC, ii) the size of
good enough subset G, iii) the alignment level , iv) the alignment probability
, and v) the error bound w between the performance values from the crude model
and the accurate model.
Assume
the requirements for our TEP optimization problem are
From
Table II, we find that, for an optimization problem with a Bell
The exact
performance value of each individual scheme is the estimated value plus the
error in the estimation. The error terms are unknown. Adding such error terms
will change the order of the ranking of the schemes that are flat (more or less
the same performance) significantly. Therefore, more schemes need to be selected
in order to capture enough good enough schemes. On the other hand, if the OPC
is Steep, although fewer schemes out of the 1000 are needed for an exact
calculation, the quality of the 1000 samples may be lower. In this case, it may
be prudent to increase the initial sample from 1000 to a larger number in order
to capture more “good enough” schemes.
CONCLUSION
Transmission
expansion planning in the restructured industry is not standardized. However,
its complexity makes simulation the only viable approach to evaluate the
performance of alternative planning schemes. We submit that ordinal
optimization can be effectively applied for the simulation-based multiyear TEP
problem. The goal of this paper is not to document how to apply the technique
to a particular system. This was done based on the calculations made on a crude
model. The classical TEP problem is used for demonstration. Furthermore, a
brief and self-contained exposition of the ordinal optimization theory is
presented. The approach can be adopted by planners with a proper selection of
the crude and exact of the specific TEP problem.
No comments:
Post a Comment
leave your opinion