TRANSMISSION EXPANSION PLANNING TO ALLEVIATE CONGESTION IN
DEREGULATED POWER MARKETS
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee. This
dissertation does not include proprietary or classified information.
Sevin Sozer
Certificate of Approval:
Jorge Valenzuela
Associate Professor
Industrial and Systems Engineering
Chan S. Park, Chair
Professor
Industrial and Systems Engineering
Alice E. Smith
Professor
Industrial and Systems Engineering
Robert L. Bulfin
Professor
Industrial and Systems Engineering
Joe F. Pittman
Interim Dean
Graduate School
TRANSMISSION EXPANSION PLANNING TO ALLEVIATE CONGESTION IN
DEREGULATED POWER MARKETS
Sevin Sozer
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
December 15, 2006
iii
TRANSMISSION EXPANSION PLANNING TO ALLEVIATE CONGESTION IN
DEREGULATED POWER MARKETS
Sevin Sozer
Permission is granted to Auburn University to make copies of this dissertation at its
discretion, upon request of individuals or institutions and at their expense. The author
reserves all publication rights.
Signature of Author
Date of Graduation
iv
VITA
Sevin Sozer, daughter of Dr. M. Tekin Sozer and Dr. E. Emel Sozer, was born February
22, 1977, in Ankara, Turkey. She graduated with a Bachelor of Science degree in
Industrial Engineering (1999) from Galatasaray University in Istanbul, Turkey, as the top
student in her class. After graduation, she remained at Galatasaray University and entered
the graduate program as a research and teaching assistant. In 2001, she earned her Master
of Science degree in Industrial Engineering, also from Galatasaray University, Turkey.
Following graduation, she entered the doctoral program in Industrial and Systems
Engineering at Auburn University in Auburn, Alabama, USA. During her years at
Auburn University, she held several graduate teaching assistant positions at both the
undergraduate and graduate levels, as well as serving as a graduate research assistant for
a National Science Foundation supported project.
v
DISSERATION ABSTRACT
TRANSMISSION EXPANSION PLANNING TO ALLEVIATE CONGESTION IN
DEREGULATED POWER MARKETS
Sevin Sozer
Doctor of Philosophy, December 15, 2006
(M.S., Galatasaray University, 2001)
(B.S., Galatasaray University, 1999)
151 Typed Pages
Directed by Chan S. Park
Transmission expansion planning is a challenging task that affects all aspects of
the power generation system in different ways. Since the deregulation of the power
industry, the competition between power generators has changed the way the national
transmission grid is used. As a result, in addition to traditional power system planning
that focuses on reliability issues, planning measures to alleviate congestion must now
also be taken into account. This dissertation therefore considers transmission expansion
planning designed to reduce the economic cost of congestion on the power system.
Here, economic transmission expansion planning, which minimizes the total
investment cost as well as the congestion cost, is modeled using a multi-period decision
framework and a multi-period decision framework that helps to calculate the equivalent
cost of operation during the planning timeframe is applied. A Benders decomposition
vi
algorithm is then used to solve the resulting nonlinear mixed-integer problem. By
applying the multi-period framework and solving the transmission expansion planning
model, an investment plan that optimizes the entire power grid from a social welfare
perspective can therefore be obtained.
The new model proposed here will be particularly useful for transmission
planners who are responsible for making long-term decisions regarding power network
operations. The dissertation goes on to define measures that can be used to compare
investment plans under the proposed decision framework. Transmission expansion
planning considering uncertainty is also investigated. First, a Monte Carlo sampling
approach is used to generate possible scenarios for future market conditions after which a
set of alternative investment plans are constructed by solving the multi-period
transmission expansion model for each scenario. It is then possible to select the best
alternative plan using a statistical comparison analysis. The results of these case studies
show that the proposed multi-period model and the decision model considering
uncertainty are flexible enough to handle large and realistic power networks.
vii
ACKNOWLEDGMENTS
The author would like to thank Dr. Chan S. Park and Dr. Jorge Valenzuela for
their guidance and support throughout this dissertation. Special thanks go to Dr. Alice E.
Smith and Dr. Robert L. Bulfin for kindly consenting to serve on the dissertation
committee, to Dr. Mark Halpin for his valuable discussions and advice, and to Dr. Saeed
Maghsoodloo for his constant encouragement and trust during this dissertation. Thanks
are also due to the Industrial and Systems Engineering family, including all the faculty
and staff, and to friends for their help at various stages of this work.
Finally, the author is grateful to her parents, Dr. E. Emel Sozer and Dr. M. Tekin
Sozer; to her sister, Esin B. Sozer; and to her fianc?, Alper Ertoklar for their unlimited
love and continued support. This work could not have been completed without them.
viii
Style manual or journal used: Institute of the Electrical and Electronics Engineers
Transaction (IEEE) Transactions on Power Systems
Computer software used: Microsoft Word, Microsoft Excel, AMPL, CPLEX 9.1
ix
TABLE OF CONTENTS
LIST OF FIGURES ........................................................................................................... xi
LIST OF TABLES............................................................................................................ xii
CHAPTER 1
INTRODUCTION .............................................................................................................. 1
CHAPTER 2
LITERATURE REVIEW ................................................................................................... 8
I. Review of Transmission Expansion Planning Models ........................................... 8
A. Static Transmission Expansion Models.................................................................. 9
B. Dynamic Transmission Expansion Models .......................................................... 13
II. Background for Deregulation in the Power Industry............................................ 14
A. Deregulation and New Challenges........................................................................ 14
B. Review of Transmission and Congestion Pricing................................................. 16
Locational Marginal Pricing ................................................................................. 17
III. Transmission Investment in Deregulated Markets ............................................... 20
A. Lack of Transmission Investment......................................................................... 20
B. Impacts of Transmission Investment .................................................................... 23
C. Transmission Expansion Planning (TEP) ............................................................. 24
D. Transmission Expansion by Transmission Companies......................................... 28
CHAPTER 3
A TRANSMISSION EXPANSION PLANNING MODEL
FOR RESTRUCTURED POWER MARKETS ............................................................... 32
I. Nomenclature........................................................................................................ 33
II. Introduction........................................................................................................... 34
III. Economics-based Transmission Expansion Planning........................................... 36
A. The Context of the Model..................................................................................... 36
B. Traditional vs. Proposed Transmission Expansion Planning Model .................... 38
IV. Mathematical Models and Benders Decomposition Technique ........................... 41
A. Traditional Transmission Expansion Planning Model.......................................... 41
B. Proposed Transmission Expansion Planning Model............................................. 43
C. Benders Decomposition Technique ...................................................................... 44
V. Experimental Results ............................................................................................ 47
A. Data for the Model................................................................................................ 47
B. Illustrative Example: Garver?s 6-bus Network..................................................... 49
C. 46-bus Brazilian Power Network.......................................................................... 53
VI. Conclusions........................................................................................................... 57
x
CHAPTER 4
ECONOMIC COMPARISON OF TRANSMISSION EXPANSION PLANS IN
DEREGULATED MARKETS ......................................................................................... 59
I. Nomenclature........................................................................................................ 60
II. Introduction........................................................................................................... 61
III. A Decision Framework......................................................................................... 63
IV. Economics-Based Transmission Expansion Planning.......................................... 65
A. Mathematical Programming Approach................................................................. 65
B. Market-based Heuristic Approach ........................................................................ 67
V. Comparison of the Transmission Investment Plans.............................................. 68
A. Severity of the Transmission Congestion and Congestion Profile ....................... 69
B. Competition........................................................................................................... 69
C. Efficiency of the Investment Plan......................................................................... 70
D. Beneficiaries Analysis .......................................................................................... 70
VI. Numerical Example .............................................................................................. 71
A. Alternative Investment Plans ................................................................................ 73
B. The Profile and the Severity of the Transmission Congestion ............................. 75
C. Efficiency of the Investment Plan......................................................................... 77
D. Competition........................................................................................................... 78
E. Beneficiaries Analysis .......................................................................................... 81
VII. Conclusion ............................................................................................................ 82
APPENDIX ...................................................................................................................... 84
CHAPTER 5
CONSIDERING UNCERTAINTY IN TRANSMISSION EXPANSION
PLANNING FOR RESTRUCTURED MARKETS......................................................... 91
I. Nomenclature........................................................................................................ 93
II. Introduction........................................................................................................... 94
III. Methodology......................................................................................................... 96
IV. The Transmission Expansion Planning Model ..................................................... 99
V. Nelson and Matejcik?s Multiple Comparison with the Best Procedure.............. 101
VI. Illustrative Examples .......................................................................................... 103
A. Data for the Model.............................................................................................. 103
B. Garver?s 6-bus Power Network .......................................................................... 105
C. WECC 179-bus Power Network......................................................................... 109
VI. Conclusion .......................................................................................................... 114
CHAPTER 6
CONCLUSION............................................................................................................... 115
BIBLIOGRAPHY........................................................................................................... 120
APPENDIX..................................................................................................................... 126
xi
LIST OF FIGURES
Fig. 1. Total congestion charges reported by PJM ISO and congestion charges
as a percentage of the total cost of the electricity generated (PJM 2006)............ 3
Fig. 2. Types of Investments in Transmission System Operators (TSO) and
RTEP 2004 Numbers for PJM ........................................................................... 28
Fig. 3. Total congestion charges reported by PJM ISO and congestion charges as a
percentage of the total cost of the electricity generated (PJM 2006)................. 35
Fig. 4. Garver?s 6-bus Network ..................................................................................... 50
Fig. 5. Garver?s Network Multi-Period Analysis: Average Prices ............................... 52
Fig. 6. Brazilian Network Multi-Period Analysis: Average Prices ............................... 57
Fig. 7. Average Price Range for Alternative Investment Plans ..................................... 79
Fig. 8. Average Load Price ............................................................................................ 80
Fig. 9. Seasonal average load prices for the planning timeframe .................................. 81
Fig. 10. One-line Diagram for the WECC 179-bus Power Network............................... 84
Fig. 11. 1
st
Phase: Identify the alternative investment plans............................................ 97
Fig. 12. 2
nd
Phase: Determine the best investment plan .................................................. 98
Fig. 13. Garver?s 6-bus Network ................................................................................... 105
xii
LIST OF TABLES
TABLE 1. Notation for the Real Power Economic Dispatch Model............................... 18
TABLE 2. Discount Coefficients for Four-Season Load Profile..................................... 49
TABLE 3. Garver?s Network One-period Analysis ........................................................ 50
TABLE 4. Garver?s Network Multi-Period Analysis...................................................... 52
TABLE 5. Generation Cost Data for Brazilian Network................................................. 53
TABLE 6. Brazilian Network Optimal Investment Plans ............................................... 54
TABLE 7. 46 Bus Brazilian One-Period analysis ........................................................... 55
TABLE 8. 46-bus Brazilian Multi-Period Analysis ........................................................ 56
TABLE 9. Discount Coefficients for Four-Season Load Profile..................................... 72
TABLE 10. Investment Plans For E-TEP and Market-based Approaches...................... 74
TABLE 11. Investment Plan for Uncongested System ................................................... 74
TABLE 12. Comparison of Investment Plans ................................................................. 75
TABLE 13. Congestion Rent for the Alternative Investments........................................ 76
TABLE 14. Savings to Investment Cost Ratio ................................................................ 78
TABLE 15. Benefit/ Loss Analysis for Load .................................................................. 82
TABLE 16. Benefit/ Loss Analysis for Generators......................................................... 82
TABLE 17. Initial Peak-Load Data ................................................................................. 85
TABLE 18. Generator Maximum Capacity and Marginal Cost Data ............................. 86
TABLE 19. Circuit Data for 179-bus Power System ...................................................... 87
TABLE 20. Discount Coefficients for Four-Season Load Profile................................. 104
TABLE 21. Generation Data ......................................................................................... 106
TABLE 22. The Set Of Optimum Plans For Garver?s 6-Bus System ........................... 107
TABLE 23. Required Number of Circuits for Optimal Investment Plans..................... 107
TABLE 24. MCB Results for Garver?s Network .......................................................... 108
TABLE 25. The Parameters for Fuel Costs with a Lognormal Distribution................. 110
TABLE 26. The Set of Optimum Plans for WECC 179-bus Power System................. 110
TABLE 27. Required Number of Circuits for Optimal Investment Plans..................... 111
xiii
TABLE 28. MCB Results for WECC 179-Bus Network Considering Total
Investment and Redispatch Cost................................................................ 112
TABLE 29. MCB Results for WECC 179-bus Network Considering Total
Investment and Congestion Rent ............................................................... 113
1
CHAPTER 1
INTRODUCTION
Deregulation is changing the structure of world power markets, including their
operation, management, and development processes. However, today?s transmission
network fails to sufficiently support the resulting competition between generators,
causing congestion in the power transmission lines and leading to demands for the
restructuring of power networks. When transmission lines reach their capacity limits,
transmission congestion occurs. As a short-term solution generators can either be
redispatched in out-of-merit order and/or some of the load can be curtailed, but when
congestion becomes a persistent event, capital cost investments are required.
Transmission expansion planning to reduce these congestion costs is a challenging job for
both system operators (SO) and market participants.
The lack of transmission investment in North America has been documented by
several researchers (see, for example, (Hyman 1999; Bush 2003; Shahidehpour 2004)).
Transmission investments decreased by approximately $120 million per year in the
period between 1975 and 1999 according to an analysis of Edison Electric Institute data
(Hirst and Kirby 2001). The transmission capacity normalized by summer peak-demand
has also been decreasing steadily. Looking across regions, the normalized transmission
capacity has declined by 11%-40% in all 10 U.S. regional reliability
2
councils. Hirst and Kirby point out that the 1999 level of normalized transmission
capacity was 201 MW-miles/MW-demand, but to maintain the same level of transmission
adequacy for the next 10-year period, 26,600 GW-miles of transmission need to be built.
Based on North American Electric Reliability Council (NERC) data, the estimation of
cost for one GW-mile is $900,000. Assuming a 2% annual retirement of transmission
capacity, in order to maintain the same level of adequacy as that of 1999, at least 54,000
GW-miles of transmission must be constructed at an investment cost of $56 billion (Hirst
and Kirby 2001).
Independent System Operators (ISOs) report that there has been a constant growth
in congestion costs. Fig. 1 shows the total congestion charges by year as reported by the
Pennsylvania-New Jersey-Maryland (PJM) ISO and the congestion as a percent of the
total electricity costs. The congestion charges at the PJM Interconnection grew from $65
million in 1999 to $2,092 million in 2005. During this period, the average percentage of
the total congestion cost with respect to the total cost of energy at PJM was 8.56% (PJM
2006). These figures underscore the value and the need for economics-based investments
in power markets.
3
$0
$500
$1,000
$1,500
$2,000
$2,500
2000 2001 2002 2003 2004 2005
C
o
n
g
e
s
tio
n
Ch
a
r
g
e
s
(
m
illio
n
$
0%
2%
4%
6%
8%
10%
C
o
n
g
es
t
i
o
n
as
a
P
e
r
cen
t
a
g
e
Cong. Charg. % of Tot. Elec. Cost
Fig. 1. Total congestion charges reported by PJM ISO and congestion charges as a
percentage of the total cost of the electricity generated (PJM 2006).
Today?s deregulated power markets rely on both reliability-based transmission
planning and economics-based transmission planning to alleviate the excess costs that are
incurred due to congestion for market participants. Congestion costs have now become an
important factor affecting electricity prices in the newly deregulated markets. Several
approaches have been proposed to plan these economics-based transmission investments
(see, for example, (Wong, Chao et al. 1999); (Buygi, Balzer et al. 2004)) and the
Pennsylvania-New Jersey-Mary Land (PJM) Independent System Operator (ISO) has
incorporated projects that are intended to relieve the persistent congestion into its
regional transmission expansion planning process (Joskow 2005b). However, a common
framework for economics-based transmission expansion planning (E-TEP) has not yet
been established.
4
Transmission investments that are not required for the enhancement of system
reliability are defined as economic investments (Joskow 2005b). From the social welfare
perspective, an economic transmission investment is justified if the total cost of the
congestion relieved by the investment is higher than the cost of the investment itself.
However, it is difficult to compare these two amounts since the congestion cost, an
operational expense, occurs at every dispatch, while the transmission investment cost, a
capital expense, is allocated at the onset of the economic life of the project.
Traditional transmission expansion models generally neglect the economic effect
of congestion. Typically, traditional models seek the minimum investment cost for a
feasible peak-load dispatch without considering the generator costs explicitly (for
example, (see (Romero, Monticelli et al. 2002)). This approach needs to be updated for
deregulated markets for two reasons: First, since competition between generators is now
a factor, the least-cost dispatch should be considered. Rather than implementing any
feasible dispatch, the least-cost dispatch must be used in today?s competitive markets.
Second, when the economic effects are taken into account investment decisions should be
based on a comparison of the equivalent costs of the investment and the savings from the
investment. Consequently, a peak-load analysis does not provide sufficient information
about the economic impact of congestion in the system.
This dissertation proposes a planning framework that facilitates system operator
decision making for the transmission expansion. The new planning framework uses a
central economic dispatch model that represents the equilibrium point for the perfect
competitive market. Since transmission planning considers long-term operations of the
power market it is appropriate to assume perfect competition, as an essential objective of
5
economic transmission investments is to improve the competition. As a result, even
though a central dispatch approach is applied, this model can be taken to be a good
approximation of the future operation of the market.
The proposed transmission expansion planning model also addresses the way in
which economic investments should be validated. Most publications in this area apply
variants of the peak-load approach, even though congestion can occur at any load level.
Here, load profiles are estimated out as far as the planning horizon and the equivalent
value of all the operational costs/savings calculated related to the transmission
investment. The proposed model compares the operational costs with the investment
costs incurred, thus making it straightforward to understand and validate the optimum
level of transmission investment.
Given these objectives, this study considers transmission expansion planning in
three steps, summarized in turn in three papers: First, a transmission expansion model for
restructured markets is introduced (Sozer, Park et al. 2006a). Second, an economic
comparison of transmission expansion plans is discussed and several approaches
compared (Sozer, Park et al. 2006b). Third, an approach that takes into account
uncertainty is proposed for transmission expansion planning (Sozer, Park et al. 2006c).
The first paper (Chapter 3) proposes a planning model that facilitates the system
operator?s decisions for transmission expansion. This model not only considers
minimization of the investment and congestion costs, but also introduces a multi-period
analysis of the system. To consider the average load profiles for every period, the
equivalent economic values of operational and investment costs are calculated at the end
6
of the construction period. Rational investment decisions can then be made by comparing
the investment and the operational costs out as far as the planning horizon.
In the second paper (Chapter 4), the proposed decision framework is analyzed.
Different economics-based transmission expansion planning (E-TEP) approaches are
compared and the differences of the resulting power systems discussed. This model first
applies the proposed mixed-integer nonlinear problem that minimizes total investment
cost and total redispatch cost and takes into account the economic dispatch of the
generators during the projected lifetime. A heuristic approach is then used to plan market-
based transmission investments. Candidate transmission lines are determined based on
the price differences between the nodes in this approach and the best investment plan
within a given budget is selected. Finally, the cheapest way to relieve congestion in the
power system is considered. Given these three investment plans and the ?do-nothing?
alternative, the results of different perspectives in a power market using the defined
measures can be compared. This paper uses a realistic 179-bus power system to illustrate
each of the proposed approaches.
The third paper (Chapter 5) provides a decision model under uncertainty. An
economics-based transmission planning model is proposed that considers uncertainties in
deregulated markets with the aim of finding the best transmission expansion plan given
the criteria determined by the planner for the uncertain power system. A Monte Carlo
simulation approach is used to incorporate uncertainties into the new decision model. The
best investment plan can then be chosen based on the criteria determined by the planner
using a multiple comparison of the best procedure.
7
Chapter 2 provides the background and reviews the significant literature in
transmission expansion planning. The remainder of the dissertation manuscript is
organized as separate papers. Chapter 3 presents the transmission expansion planning
model, Chapter 4 gives details of the decision framework that is used for comparing the
different transmission investment plans, and Chapter 5 describes the new approach for
transmission planning under uncertainty. Chapter 6 summarizes the study, discusses the
conclusions and suggests potential future research areas. In the appendix, some example
AMPL codes are provided.
8
CHAPTER 2
LITERATURE REVIEW
The review of the current literature in this chapter is presented in three sections.
The first section reviews transmission expansion planning models, covering both static
and dynamic models dating to pre-liberalized markets. The second section of the
literature review provides information about the operation of the power markets in
today?s deregulated markets. Also discussed are the challenges that have arisen due to
deregulation and the consequent effects on the operation and planning of power markets.
The final section highlights the literature focused on the lack of transmission investment
and the impact of transmission investment, concluding that efficient and effective
transmission planning is required for the efficient and reliable operation of power
networks.
I. REVIEW OF TRANSMISSION EXPANSION PLANNING MODELS
In 2003, Latorre et al. published a classification of publications and models on
transmission expansion, categorizing the solution methods used for transmission
expansion models as either mathematical optimization models or heuristic models
(Latorre, Cruz et al. 2003). The mathematical optimization models include:
? linear programming
? dynamic programming
? nonlinear programming
9
? mixed integer programming
? decomposition techniques
? branch and bound methods
Many heuristic methods have also been applied to solve the model in the
literature, including:
? genetic algorithms
? object oriented models
? game theory
? simulated annealing
? expert systems
? fuzzy set theory
? greedy randomized adaptive search procedure (GRASP)
The authors also categorize the solution models as either static or dynamic based
on their treatment of the planning horizon; a model is static when the planning horizon is
considered to be unitary and a single year analysis is done, while dynamic models
consider a multiple- year analysis, seeking an optimal strategy that will cover the entire
planning period.
The following sections present a representative selection of the work that has been
published on the transmission expansion problem for both static and dynamic models.
A. Static Transmission Expansion Models
Static models have been investigated extensively in the literature. Following
several conventional optimization algorithms (Romero and Monticelli 1994; Romero and
Monticelli 1994; Haffner, Monticelli et al. 2000; Haffner, Monticelli et al. 2001), an
efficient linear programming algorithm was proposed in 2003 by Hashimoto, Romero,
and Mantovani. Their approach is composed of two steps: (a) reduce the number of
10
variables and the equality constraints, and (b) solve the resulting problem using a dual
simplex algorithm for bounded variables and a relaxation strategy (Hashimoto, Romero et
al. 2003).
Two years earlier, Binato, Pereira, and Granville (2001) proposed a new Benders
decomposition approach for the static transmission expansion problem. Their method is
based on a disjunctive model, which is a mixed (0-1) integer LP. This model is actually a
linearized DC-model and introduces the use of Gomory cuts with Benders decomposition
(Binato, Pereira et al. 2001).
Simulated annealing is another of the adaptive optimization techniques that has
been considered for transmission expansion planning. For example, Romero, Gallego,
and Monticelli present a simulated annealing method that is applied to three example
network problems (Romero, Gallego et al. 1996), while Gallego et al. propose a Parallel
Simulated Annealing (PSA) approach and discuss the conditions under which PSA is
most efficient (Gallego, Alves et al. 1997).
The use of a genetic algorithm (GA) is suggested for transmission expansion
problems by Gallego, Monticelli, and Romero, who investigate an extended genetic
algorithm for the static transmission expansion problem (Gallego, Monticelli et al. 1998).
A comparison of the adaptive optimization methods to solve transmission expansion
models is provided in the same paper. Gallego et al. solve the static transmission
expansion model using simulated annealing, a genetic algorithm and a hybrid approach
based on a tabu search. They compare the model?s performance with two initialization
methods, namely random and Garver?s algorithms. Initialization of the model with
11
Garver?s algorithm is shown to outperform the random initialization for all three of the
approaches.
A transmission expansion planning method, which includes decision analysis
tools, was developed by De la Torre et al. for Central American Interconnection (De la
Torre, Feltes et al. 1999) and by da Silva et al., who use an improved genetic algorithm
approach (Da Silva, Gil et al. 2000). Another heuristic approach to transmission planning
is given by Chung et al., who consider a multi-objective mathematical optimization
problem (Chung, Li et al. 2003). Here, the basic approach is that several schemes
(solutions) are obtained by a GA approach and an optimum scheme is determined using
fuzzy decision analysis. A third generation tabu search algorithm is proposed by Gallego,
Romero, and Monticelli (2000) for the static transmission expansion problem, who use
several advanced features in their model, including path re-linking, elite configurations,
intelligent initialization, strategic oscillations, neighborhood reduction, and hybrid
features taken from other combinatorial methods such as GA and Simulated Annealing
(Gallego, Romero et al. 2000). The tabu search approach is revisited by da Silva et al.
(2001); in addition to the main tabu search concepts such as short-term memory, a tabu
list, and aspiration criterion, they also include intensification and diversification phases,
using medium- and long-term memory concepts. Their algorithm obtains the optimal
solution for the Brazilian Southern case study with 46 buses at the end of the first
iteration. The best solution for the Brazilian Southeastern case study with 79 buses is also
obtained at the first iteration (Da Silva, Ortiz et al. 2001).
Alguacil, Motto, and Conejo derive a mixed-integer linear formulation of the
transmission expansion planning that considers losses and guarantees convergence to
12
optimality (Alguacil, Motto et al. 2003). In their model, the objective function considers
production cost of the generators, in addition to the cost of investment for the
transmission lines. Fang and Hill put forward a mathematical model in ?A New Strategy
for Transmission Expansion in Competitive Electricity Markets? (Fang and Hill 2003), in
which the static transmission planning is given in terms of a mixed integer nonlinear
optimization problem. A different version of the DC-model for traditional static
transmission planning problem is also reviewed by these authors, who go on to suggest
improvements in the model in order to apply it to a deregulated environment with a
market-driven power flow pattern. Further, they propose a new transmission expansion
strategy using this new model.
In the ?Application of Artificial Intelligent Tools to the Transmission Expansion
Problem,? Al-Saba and El-Amin formulate the transmission expansion problem as a
nonlinear problem (Al-Saba and El-Amin 2002) where the objective function consists of
minimizing both the total capital cost of new transmission lines and the total cost of
system power losses. Constraints in this model include limits on the branch power flow,
bus voltage angle, right of ways, and power balance at the network buses. The authors
solve this nonlinear problem by applying several artificial intelligence methods, including
GA, TS, and ANN, and then compare the efficiency of each of the methods.
Rau (2002), from ISO New England, wrote a paper that addresses the
identification of transmission upgrades in deregulated markets. The author points out that
the best measure of the state of the congestion in the network is the change in the
production cost (Rau 2002).
13
Leeprechanon et al. (2001) designed a transmission planning model specifically
for developing countries that utilizes a synthetic model. The model?s approach assumes
that generation is deregulated but that transmission investment, operation, and planning
are regulated, and that the country?s National Transmission Authority controls the
ownership, dispatch, and market operation functions. The proposed model includes all the
relationships between generation investment decisions, transmission investment
decisions, and the operation of the system, and takes into account the economic signals
for generation expansion and transmission expansion. (Leeprechanon, Moorthy et al.
2001)
A recent publication by Choi et al. (2005) adapts fuzzy set theorem to solve the
transmission expansion problem. Investment budget, reliability criteria, load forecasting,
and system characteristics are the uncertainties considered. (Choi, El-Keib et al. 2005)
B. Dynamic Transmission Expansion Models
The static model of the transmission expansion is actually a sub-problem of the
dynamic model, but given the complexity of the static model, the dynamic model has not
been as well studied. The static model primarily focuses on where and how many
transmission line to build, whereas the dynamic approach determines where, how many,
and when to build within a specified planning horizon.
In early work in this area, Rudnick et al. (1996) apply a Genetic Algorithm (GA)
application to dynamic transmission planning. In this work, authors use the
?economically adapted? concept that assumes that short term marginal costs equal long-
term marginal costs. The authors applied this model to a simplified Chilean transmission
system with 8 buses and 10 lines (Rudnick, Palma et al. 1996).
14
A more recent dynamic transmission expansion planning approach was presented
by Escobar, Gallego, and Romero (2004), who developed an efficient GA to solve
multistage and coordinated transmission expansion. They propose a detailed integrated
multistage planning process for generation and transmission systems, including operation
costs; however, the GA model in this paper only includes transmission planning, ignoring
generation investment and operation costs. As a result, the objective function of the
proposed model minimizes both the present value of the investment costs and the cost of
lost loads (Escobar, Gallego et al. 2004).
II. BACKGROUND FOR DEREGULATION IN THE POWER INDUSTRY
This section examines the background for the operation and planning of
deregulated markets. The type of challenges caused by deregulation are first discussed,
followed by a consideration of locational marginal pricing.
A. Deregulation and New Challenges
? Who should be responsible for transmission system planning?
? When should new transmission investment be made?
? Where should they be installed? For what purpose?
? Who will provide the funds to finance the additions?
? How should investment recovery and return be implemented?
These questions are raised by David and Wen (2001) in a discussion of the effect
of deregulation in the electricity market. Although different markets have different needs,
these questions should be discussed in order to ensure the long-term reliability and
efficiency of the network. With deregulation, the objectives of the transmission planning
process are changing, as simple maximization of social welfare is no longer sufficient for
the optimization of transmission investments. However, although investors aim to
15
maximize their benefit, social welfare is still a constraint. Least cost expansion planning
is no longer valid for deregulated markets. In addition to the reliability requirements, the
economic effects of the investment must now be taken into account among the other
criteria (David and Wen 2001).
In a review article, Wong et al. (1999) summarized the market based transmission
planning concept in a deregulated environment, noting that some of the challenges that
must be addressed to value transmission expansion include new binding constraints,
uncertainty of generation expansion, construction time of transmission projects, and
reliability. The authors suggest that the trends for transmission needs should be identified
by a detailed market analysis since construction takes several years and transmission
assets have long economic lives (Wong, Chao et al. 1999).
Hirst and Kirby (2001) also address the fact that transmission planning is
becoming more complicated because of the changes that the electrical industry is facing.
The separation of generation and transmission, the separation of both generation and
transmission from system control, and the creation of competitive market for generation
are all affecting the way that transmission planning is done. All these changes require
corresponding changes in the planning process and models. The objective of transmission
planning is now not solely the reliability but also the need to facilitate commerce in the
region. Different objectives of the actors in the market and the unavailability of data for
the planner are among other difficulties for those engaged in the transmission planning
process (Hirst and Kirby 2001).
Wolak (2001) addresses the difference of valuing transmission in vertically
integrated and wholesale market regimes, explaining that in vertically integrated regimes
16
the value of transmission expansion is defined by locational cost differences. However, in
the wholesale regime, the value of transmission expansion is the increased ability to
exploit locational price differences. Transmission expansion reduces the market power by
both increasing the number of generators that can supply the load, and decreasing the
incentive to exercise market power. Introducing competition, local generators lose their
ability to raise prices indefinitely. Additionally, transmission upgrades help to reduce
locational price differences (Wolak 2003).
Wolak (2003) also introduces the concept of ?economic reliability,? defining it as
having ?sufficient transmission capacity so that all locations in the network face
significant competition from enough independent suppliers to cause them to bid close to
their marginal cost curve the vast majority of hours of the year.? He suggests that power
networks can be improved by moving from a simple consideration of engineering
reliability to include economic reliability (Wolak 2003).
Garrity (2003) examines recent developments in transmission technology and
how these new technologies will work to improve the reliability and the efficiency of the
power system. Suggested technologies include flexible alternating current transmission
systems (FACTS), high voltage direct current (HVDC) transmission, short current
limiters, overhead lines, gas insulated transmission lines, gas insulated switchgear, and
grid connected wind generation (Garrity 2003).
B. Review of Transmission and Congestion Pricing
In vertically integrated industries, transmission costs are included in the price of
electricity with the traditional rate of return approach. With this approach, electricity and
transmission are priced uniformly throughout the network based on the operating and
17
capital cost of generation, transmission, and distribution. As a result, this model does not
provide price signals indicating the investment requirements of the market. In deregulated
markets, where generation, transmission, and distribution are separately operated, this
approach is not applicable. One of the most common congestion pricing model in today?s
power markets, Locational Marginal Pricing, will be considered in this research. Details
of this pricing mechanism are presented in this section.
Locational Marginal Pricing
The structure of today?s electricity markets is based on the pioneer work of
Scheweppe et al. on spot prices for power (Schweppe 1988). Hogan developed the theory
to include transmission rights and published several important papers on deregulated
markets using locational marginal pricing (Hogan 1992). In the U.S., Pennsylvania-New
Jersey-Maryland Interconnection (PJM) was the first market to use the Locational
Marginal Pricing concept, starting in 1997; Ott explains PJM operation, system designs
and implementation (Ott 2003). This standard market design is based on Locational
Marginal Pricing (Nodal pricing) using the security constrained economic dispatch
model. A real power economic dispatch model can be represented as follows:
min
ii
iN
vcg
?
=
?
(2.1)
subject to
( )
i
?++=Sf g r d (2.2)
()
0
ij ij i j
fY????=
( ),ij L? ? (2.3)
( )
0
ij ij ij
ff ??? ( ),ij L? ? (2.4)
??0 gg (2.5)
18
where the objective function (2.1) is the minimization of the total generation cost, with c
i
representing the cost of production of generator k and g
i
being the total generation of the
generator at bus k. The notation is shown in TABLE 1. Equation (2.2) provides the node
balance equations for every bus k, shadow price for these equations, and
i
? , represents
the nodal prices (LMPs) at each bus. The constraints (2.3) correspond to those imposed
by Kirchoff?s Voltage Law. The transmission line capacity limits in equation (2.4) are
binding if the line is congested. As a result, the shadow prices (
ij
? ) take non-zero values
only for congested lines. The generation capacity limits are shown by equation (2.5).
TABLE 1.
NOTATION FOR THE REAL POWER ECONOMIC DISPATCH MODEL
Variables
ij
n
Number of added circuits to branch (i, j)
g Vector of generated active power
i
g
Generation at node i (MW)
f Vector of active-power flows through the lines
ij
f
Flow in branch (i, j) (MW)
j
?
Voltage angle at bus j
Parameters
i
c
Cost of generation for generator at node i ($/MW)
S Node-branch incidence matrix
d Vector of estimated loads
ij
Y
Circuit susceptance for branch (i, j)
ij
f
Flow limit in branch (i, j)
g
Vector of maximum generation capacity
L
Set of circuit candidates
N Set of nodes
If a network requires more constraints on the transmission line capacities to
ensure reliability, security constraints are added to the basic economic dispatch model.
For instance, for energy deliverability reasons an interface may need to work with less
19
than a specific amount of flow. Consequently, the sum of the all the flows passing
through this interface should be less than or equal to this specific limit. Another example
of such security constraints is the need for reliability contingency constraints such as (N-
1) or multiple contingencies.
The optimum solution for an economic dispatch model, as the name suggests,
provides for the economic dispatch of the system (Chao and Peck 1996; Chao and Peck
1998). Nodal prices or locational marginal prices (LMP) are determined by shadow
prices at the nodes. In a deregulated market that adopts locational marginal pricing, users
of the market at each node pay at their nodal price or LMP. These differences at locations
arise as a result of congestion in the system. When the systems are not congested, LMPs
throughout the system are equal. The difference between what the load pays and what the
generators are paid is called the congestion rent.
LMPs allow not only operation at the economic equilibrium but also make it
possible to extract a great deal of information about various elements of the power
system. Finney, Othman, and Rutz describe how to evaluate transmission constraints in
system planning, showing how to decompose nodal prices into components such as
generation, transmission, and losses. If operating and reliability constraints are binding in
the system, congestion occurs, which may indicate the need for system expansion
(Finney, Othman et al. 1997). Chen et al. also propose a method to decompose nodal
prices to reveal all the relevant factors in the power system, noing that ?The
decomposition is unique and components of each nodal price are identical to their
incremental costs or benefits for [the] total system? (Chen, Suzuki et al. 2002).
20
III. TRANSMISSION INVESTMENT IN DEREGULATED MARKETS
This section focuses on the area of particular concern for this research. Not only
in U.S. markets, but also in any restructuring market, transmission investment and
planning face several challenges. A lack of investment is often suffered by any new
operation that requires new infrastructure and this may be exacerbated by investors
avoiding or delaying projects. There is an immediate need for an efficient method that
allows strategic planning of economic investments. The first two sections below describe
the reasons for this lack of investment in transmission networks and the impact of
transmission investments. The section concludes by considering current practices in
transmission expansion planning and how the transmission companies need to enhance
their power networks.
A. Lack of Transmission Investment
The role of the transmission system has expanded since the deregulation of the
power market. In addition to system reliability, the new Federal Energy Regulatory
Commission (FERC) regulations require all generators to have equal access to the
transmission grid. However, the continuous lack of regulations and policies had led to
uncertainties in the operation of the North American grid, with a corresponding
reluctance to invest in transmission line construction.
The Federal Energy Regulatory Commission (FERC) has recently published a
series of orders to improve competition in both the generation and transmission markets.
In 1996, Orders 888 and 889 initiated the competition in power generation and in 2000,
Order 2000 included provisions for incentives to transmission companies to improve their
grids. Based on a report prepared by Richardson in 2003 that included data from the
21
North American Electric Reliability Council (NERC), regional reliability councils,
transmission providers, and some databases online, the total cost for new transmission
projects planned is thought to be of the order of $27.5 billion (Richardson 2003). Further,
Hirst and Kirby explain that besides the transmission growth, annual transmission
investments have also been decreasing by $117 million per year according to National
Energy Reliability Council (NERC) data (Hirst and Kirby 2001). The transmission
capacity normalized by summer peak demand has been decreasing steadily in the nation
as a whole, and on the regional level the normalized transmission capacity has declined in
all 10 regions by amounts raging from 11% to 40%. Consistent with all these data, the
planned transmission investment is lower than the expected growth rate. Hirst and Kirby
point out that the 1999 level of normalized transmission capacity was 201 MW-
miles/MW demand, and to maintain the same level of transmission adequacy for next 10-
year period, 26,600 GW-miles of transmission must be built. Based on NERC data, who
estimate a cost for 1 GW-mile of roughly $0.90 million, and assuming a 2% retirement of
transmission capacity each year, in order to maintain the same level of adequacy as that
in 1999, 54,000 GW-miles of transmission must be constructed with an investment worth
of $56 billion (Hirst and Kirby 2001).
Paul McCoy of Trans-Elect, a privately own independent transmission company,
has suggested several reasons why utilities may want to sell their transmission assets. In
an interview with a trade journal (Editorial 2002), he pointed out that some utilities may
strategically decide that the transmission assets do not fit their business model and
therefore take the opportunity to increase their cash reserve, while a second reason for
22
putting transmission assets on the market is the need for a significant capital investment
to be made that the utility company is not prepared to commit themselves to.
Energy companies tend to separate their transmission business from the
generation aspect due to the current regulatory environment. Order 2000 calls for the
formation of Regional Transmission Operators (RTOs), whose main role is to adjust the
transmission planning process to fit regional needs, and proposes the use of Standard
Market Design (SMD) to provide the financial incentives to encourage investment to
meet new transmission capacities. However, although there has been a trend towards the
formation of Independent Transmission Companies (ITCs), investors prefer to understand
how exactly the transmission will be regulated before taking any action (Bush 2003).
In ?Investing in Expansion?, Shahidehpour (2004) points out the magnitude of the
nation?s under-investment in the U.S. transmission system. The capital expenditures of
electricity providers decreased to 12% during the 90s, and the projected transmission
construction growth is only 6% over the next 10-year period, although the growth of the
load is 20% (Shahidehpour 2004). This under-investment situation in transmission
facilities is likely to lead to more social costs than the cost of over-investment in
transmission. Transmission system planning has historically been a regional issue, carried
out by the vertically integrated utilities. After the introduction of competition this process
had to be changed. Since transmission operation is regional in nature, Shahidehpour
(2004) suggests that the power transmission planning should be performed by regional
transmission organizations. Under current federal law, the siting of transmission facilities
is the responsibility of state governments, although today?s transmission system is not
only regional, including several states, but also extends across international borders to
23
Canada and Mexico. The federal law does not reflect this and has not changed since
1935. This situation widens the responsibilities of the Federal Energy Regulatory
Commission (FERC). As Shahidehpour points out, access to federal land for transmission
expansion would remove the constraints on transmission siting and would facilitate the
provision of the required right-of-ways. Moreover, there is no enforceable reliability
standard for transmission, which is another limiting issue contributing to the lack of
transmission investment (Shahidehpour 2004).
B. Impacts of Transmission Investment
Deb (2004) highlights the fact that transmission investment affects both reliability
and economic efficiency issues for power systems. Reliability is closely linked to the
physical performance of the network system (Deb 2004). Hyman (1999) describes how a
robust transmission system will both enhance the competitive bidding process and
prevent local generators from exercising market power. Recent technological
developments also improve the transmission system as both hardware and software
solutions, which enhance the efficiency of the system by allowing it to operate closer to
its limits, become available (Hyman 1999). Given the uncertainties regarding the
recovery of their investment, transmission owners must make their decisions not on the
basis of the optimal economic or operating solution, but rather on the basis of which
investment they can most easily recover within the regulatory context (Hyman 1999).
(David and Wen 2001) present an economic evaluation of the transmission
planning projects with the objective of minimizing financial risk, ensuring the optimal
benefits from the plan. The authors suggest that since this investment recovery method
24
protects the revenue stream, the ability to forecast future market prices and volatility is
essential. The risks of such projects cannot be avoided, but rather need to be managed.
In a paper written a few years earlier, Crousillat et al. summarize some of the
conflicting objectives in the power system planning process. The Costa Rican electric
utility problem and the Hungarian Electricity Board problem are studied in this paper in
order to reveal the effect of different relationships between objectives using the trade off
risk method to analyze these case studies (Crousillat, Dorfner et al. 1993).
Transmission expansion can reduce power prices in two ways, first by using
cheaper resources, and second by reducing generators local market power. For example,
Nasser points out that the economically optimal transmission expansion occurs when
marginal benefit (marginal reduction of power prices) is equal to the marginal cost of the
upgrade (Nasser 1999).
C. Transmission Expansion Planning (TEP)
The effect of transmission on the economic efficiency is substantial, underlining
how essential it is to use a realistic model (Deb 2004). A realistic simulation for valuation
should incorporate security-constrained unit commitment, security constrained economic
dispatch, and several combinations of contingencies and special protection schemes.
The economic efficiency can be calculated in terms of the congestion costs.
However, simply taking the congestion value based on nodal price differences as the
investment benefit ignores two points. First, although congestion on one line is
eliminated, there may be other sources of congestion on the system, which is known as
the ?spring washer? effect. Second, flows are not always towards the high priced
location, so the numbers calculated will not reflect the actual benefit of the investment.
25
(David and Wen 2001) review the transmission line policies of several different
countries in order to examine how transmission expansion alternatives function under
different scenarios. In the UK, for example, the National Grid Company (NGC) classifies
its candidate transmission projects as either core transmission lines or flexible
transmission lines. NGC employs a two stage approach:
a. Development of scenarios for different views of the future.
b. Prediction of transmission capacity requirements using probability-based
models.
It has also been suggested that the theory and tools available for transmission
planning are still inadequate to fulfill the practical requirements of today?s complex
power markets (Latorre, Cruz et al. 2003).
The U.S. electricity industry is restructuring, along with the world power industry
(Hirst and Kirby 2001). Rather than a traditional vertically integrated structure, where
one utility performs every part of the process, including generation, transmission, and
distribution, the separation of generation and transmission is now supported by the
authorities. Hirst and Kirby suggest that this new and unclear transition is one of the
reasons that transmission has been subject to underinvestment during the last decade.
Although the growth rate of summer peak demand has been between 2-3%, the
transmission capacity growth actually fell from almost 3% during the 1980s to 0.5%
during the 1990s. The Federal Energy Regulatory Commission (FERC) highlights the
importance of regional planning of transmission, stating in Order 2000 that ?each
Regional Transmission Organization (RTO) must be responsible for planning, and for
directing or arranging, necessary transmission expansion, additions, and upgrades that
26
will enable it to provide efficient, reliable, and non-discriminatory transmission service
and coordinate such efforts with appropriate state authorities.? FERC models the market
to eliminate the exercise for both vertical and horizontal market powers, preferring to
move the transmission planning from the local to the regional level (Hirst and Kirby
2001).
It has been suggested that ?the purpose of transmission planning is to identify a
flexible, robust, and implementable transmission system that reliably facilitates
commerce and serves all loads in a cost-effective manner? (Hirst and Kirby 2001). The
reliability objectives consist of the predetermined conditions that a system should be able
to accommodate. These performance requirements are addressed by the NERC Planning
Standards (1997) and by the Mid-Atlantic Area Council (MAAC) Reliability Assessment
(2002). Before deregulation, transmission planning invoked only the worst-case scenarios
to verify these reliability requirements, but once the competitive market was introduced,
transmission system became a facilitator of the competitive market, thus making the
entire transmission planning process more complex.
Two of the key issues that add to the complexity are network reliability and the
demands of competitive commerce. With deregulation, transmission systems were
expected to not only transport the power generated to the customer, but also to serve
dynamic and rapidly expanding markets. To reduce congestion costs locational pricing is
used in some regions, but ?locational pricing eliminates the distinction between reliability
and commerce by explicitly pricing reliability? (Hirst and Kirby 2001). Solving reliability
problems may also create commercial problems, since each actor in the systems reacts
differently; for example, relieving congestion in one line may cause a higher price
27
generator to sell at a lower price and a low price load to buy at a higher cost. Congestion
costs may also serve as signals indicating possible investment alternatives.
Hirst (2004) suggests that RTO plans are generally vague and that in order to
safeguard regional grid expansion, these plans must be studied carefully. He goes on to
give a brief review of the transmission planning process in U.S. electricity markets and
discuss the resulting plans, concluding: ?Enough new transmission will likely be built to
maintain reliability. However, many economic opportunities to build low-cost power
plants in remote locations or to move power from cheap generators to distant load centers
will be foregone because sufficient transmission for economic purposes may not be built?
(Hirst 2004).
In a recent paper, Joskow discusses a range of alternative transmission investment
approaches and explains in particular how PJM?s Regional Transmission Expansion
Planning functions (Joskow 2005b). PJM prepares its Regional Transmission Expansion
Plan (RTEP) by taking into account interconnection and reliability transmission
investments. However, PJM only considers intra-ISO investments, leaving economic
investments and inter-ISO investments to merchant investors. Fig. 2 illustrates the types
of transmission investments that occur in interconnections and shows the total cost of
transmission investments for PJM?s 2004 RTEP.
28
Intra-TSO
Inter-TSO
Interconnection
$304 million
Reliability
Economic
New interconnection
$207 million
Load growth /
Generation Retirement
$274 million
Tr
ansmission I
n
v
e
stment
s
Tr
ansmission I
n
v
e
stment
s
Fig. 2. Types of Investments in Transmission System Operators (TSO) and RTEP 2004
Numbers for PJM
Merchant transmission investments are defined by Joskow as unregulated
transmission investment projects on a commercial basis in response to congestion within
the network (intra-TSO) or price differences between two networks (inter-TSO) (Joskow
2005b). PJM has started a process to encourage economic investments. ?Unhedgeable
congestion? in the market, which is the congestion cost that cannot be hedged by existing
FTRs, is monitored throughout the year. When total unhedgeable congestion exceeds
some predetermined level, this line is added to a ?market window? for one year, where a
benefit/cost analysis is conducted. PJM assesses investment proposals during the year. If
none of the proposals are accepted, PJM evaluates the investment at the end of the year
for inclusion in its RTEP. This unhedgeable congestion cost is actually an estimate of the
social cost of congestion (see (Joskow 2005b)).
D. Transmission Expansion by Transmission Companies
In a paper entitled ?The Hidden Value of Transmission Assets?, Nasser discusses
how ?Transcos?, which are for-profit transmission companies, constitute a simple
29
solution to transmission congestion problems (Nasser 1999). He defines four underlying
causes that influence the costs of transmission constraints:
? constrained regional dispatch,
? local market power,
? constrained interregional dispatch, and
? inefficient generation investment.
The first two costs are described as static and constitute roughly 2-4% of the total
cost of energy, whereas the last two are dynamic costs that have medium to long-run
implications and can be valued at more than 4% of the total cost of the energy. In
England and Wales, static congestion cost is measured by the Operational Out-turn
component of the Uplift Charges. In California, the static cost of congestion was 5-10%
of the power price during May-July 1998 (Nasser 1999).
Hyman argues that transmission policymakers disregard the importance of
transmission for the reliable and competitive operation of the power system and therefore
fail to provide any incentives to the transmission owners to improve the network or its
operation (Hyman 1999). Over the 20 years starting with the mid-1950s, high voltage
lines were constructed in line with load growth, but since the in mid-1970s, the
transmission network has grown at less than half of the pace of demand. Hyman suggests
that policymakers might produce better results for transmission expansion if they
encourage the organization of independent business entities, namely transmission
companies, rather than rely on independent system operators (ISOs), and if they set up a
regulatory scheme that encourages expansion and efficient operation, and penalizes any
failure to meet the industry?s reliability standards.
30
In an article in Public Utilities Fortnightly, Roseman and De Martini point out
that with the deregulation of the electrical industry not only reliability but also the goals
of eliminating congestion and supporting access to lower-cost wholesale power supplies
gained equal importance (Roseman and De Martini 2003). They emphasize the need for
transmission investment by showing evidence from the industry and suggest that the
expected investment for the next decade should be approximately $30 to $60 billion. This
implies a growth rate for the transmission network of 50 to 100% in the United States.
David and Wen suggest that although transmission expansion may be funded by
investments by government, transmission companies, individual investors, or ISOs, it
should be monitored by a government organization or a regulator (David and Wen 2001).
In a deregulated environment, investment recovery and return are uncertain. While
competitive environments promote short-term returns, transmission expansion requires
large investments and long recovery periods. Increased uncertainties with regard to
generation planning, load variation, and market management rules give rise to additional
challenges to potential investors. David and Wen suggest that two primary mechanisms
that need to be changed in traditional transmission planning are fixed cost recovery and
the incentives for coordination and cooperation between affected parties.
Deb discusses how extended transmission for economic efficiency reasons could
be provided in a regulated manner with guaranteed cost recovery, as opposed to being
provided in a market-based manner (Deb 2004). Several examples of different
approaches are given; for instance, the Pennsylvania-New Jersey-Maryland
Interconnection (PJM) requires regulated transmission investment to reduce congestion
costs if the investment is to be cost-effective, while the New York Independent System
31
Operator (NYISO) has established procedures to reward long-term investment but does
not mandate them for economic efficiency purposes.
Bullinger and Shetty present an overview of the investment decision making
process in the power industry from the business point of view, including a discussion of
the inputs and activities of different areas of power systems such as generation,
transmission, and distribution (Bullinger and Shetty 2004). Investment decision variables
that influence the investment selection are described in detail in this paper.
Fisher and Braun consider investment decisions concerned with bulk transmission
systems in deregulated markets and report that in deregulated markets, investment
decisions are both micro economic and competitive but that decisions based on reliability
constraints alone are not sufficient to meet the requirements of the competitive market
(Fischer and Braun 2001). They point out that an investor in the electricity sector will
reach a decision by analyzing the market and estimating the financial risk. One option for
financing a project is ?project financing based on private initiative?, the merchant
transmission investment approach. The authors suggest that there are three financial
parameters involved in assessing an investment, namely payback period and payoff time,
return on equity, and compensation for use (transmission cost), and explain these
parameters using an HVDC transmission system example. However, although their
approach is structured with realistic numbers, the equations given are not well-explained
and are unclear. The hypothesis guiding their research is that the ?special purpose
company? created for their project requires at least the calculated compensation for its
use amount in order to assure minimum annuity.
32
CHAPTER 3
A TRANSMISSION EXPANSION PLANNING MODEL
FOR RESTRUCTURED POWER MARKETS
Abstract? In today?s restructured power markets, the participants face significant
congestion costs that can best be alleviated by investing in transmission capacity.
Traditionally, transmission expansion models do not explicitly consider the economic
impact of congestion when making investment decisions. In this paper, a transmission
expansion model for the long-term planning of restructured markets is proposed. The
model minimizes the costs of investment and congestion over a planning horizon that
includes multiple load profiles. The resulting mixed-integer non-linear program is solved
using a hierarchical Benders decomposition approach. The Garver?s 6-bus network and
the 46-bus Brazilian network are examined to show the adequacy of the proposed model.
Index Terms? Benders decomposition, economic transmission planning, mixed-
integer nonlinear programming, power transmission planning, transmission expansion
planning.
33
I. NOMENCLATURE
The notation used in the paper is given below for quick reference.
Variables
ij
n
Number of added circuits to branch (i, j)
g Vector of generated active power
i
g
Generation at node i (MW)
r Vector of load curtailments
i
r
Load curtailment at node i (MW)
f Vector of active-power flows through the lines
ij
f
Flow in branch (i, j) (MW)
j
?
Voltage angle at bus j
Parameters
ij
c
Cost of adding a circuit to branch (i, j) ($)
i
c
Cost of generation for generator at node i ($/MW)
i
?
Penalty factor associated with load curtailment at bus i ($/MW)
S Node-branch incidence matrix
d Vector of estimated loads
ij
?
Circuit susceptance for branch (i, j)
0
ij
?
Initial circuit susceptance for branch (I, j)
0
ij
f
Initial flow limit in branch (i, j) (MW)
ij
f
Flow limit in branch (i, j) (MW)
g
Vector of maximum generation capacity
0
ij
n
Initial number of circuits in branch (i, j)
ij
n
Maximum number of new circuits added to branch (i, j)
,py
?
Comparison/compounding coefficient at period p year y
k
v
Present value of the operating cost at iteration k
,py
ij
?
Sensitivity coefficient for branch (i, j) at period p year y
L
Set of circuit candidates
N Set of nodes
Y Set of planning years
P Set of periods during year y
K Set of iterations
34
II. INTRODUCTION
Deregulation has significantly changed the structure of power markets, including
their operation, management, and planning processes, not only in the U.S. but also in
other countries. Today?s transmission networks do not sufficiently support the
competition of generators, causing congestion of transmission lines. Despite the need for
more transmission, the lack of transmission investment in North America has been
documented by several researchers (Hyman 1999; Hirst and Kirby 2001; Shahidehpour
2004). In restructured markets, users are paying increasing congestion costs. Independent
System Operators (ISOs) report constant growth in congestion costs. Fig. 3 shows the
total congestion charges by year as reported by the Pennsylvania-New Jersey-Maryland
(PJM) ISO and the congestion as a percent of the total electricity costs. The congestion
charges at the PJM Interconnection grew from $65 million in 1999 to $2,092 million in
2005. During this period, the percent of total congestion cost of the total cost of energy at
PJM was 8.56% on the average (PJM 2006). These figures underscore the value and the
need for economics-based investments in power markets. Transmission expansion
planning aimed at reducing these congestion costs is a challenge for both system
operators (SO) and market participants.
Transmission investments that are not required for the enhancement of system
reliability are defined as economic investments (Joskow 2005b). From the social welfare
perspective, an economic transmission investment is justified if the total cost of the
congestion relieved by the investment is higher than the cost of the investment itself.
However, it is difficult to compare these two amounts since the congestion cost, an
35
operational expense, occurs at every dispatch, while the transmission investment cost, a
capital expense, is allocated at the onset of the economic life of the project.
$0
$500
$1,000
$1,500
$2,000
$2,500
2000 2001 2002 2003 2004 2005
C
o
n
g
e
s
tio
n
Ch
a
r
g
e
s
(
m
illio
n
$
0%
2%
4%
6%
8%
10%
C
o
n
g
es
t
i
o
n
as
a
P
e
r
cen
t
a
g
e
Cong. Charg. % of Tot. Elec. Cost
Fig. 3. Total congestion charges reported by PJM ISO and congestion charges as a
percentage of the total cost of the electricity generated (PJM 2006)
This paper proposes a planning model that facilitates the system operator?s
decisions for transmission expansion. This model not only considers minimization of the
investment and congestion costs, but also introduces a multi-period analysis of the
system. Considering the average load profiles for every period, the equivalent economic
values of operational and investment costs at the end of the construction period are
calculated. The investment decisions are made by comparing the investment and the
operational costs throughout the planning period. This model makes it easy to identify,
understand and validate the necessary transmission investments.
The proposed transmission expansion planning model optimizes the transmission
investment by minimizing the sum of the investment cost and the redispatch cost (it
maximizes the social welfare). This approach represents the system operator?s view of
36
the transmission planning. Even though the model is developed from the perspective of
the system operators, the proposed decision framework allows the calculations of the
benefits/losses of any participants from a given investment. Moreover, the model could
be adapted and used by other users such as load serving entities. In this case, the
objective function will be different, but the general structure of the model would be
similar to the one proposed.
The remainder of the paper is organized as follows: Section III provides
definitions for the critical terms related to restructured power markets, and the traditional
and proposed transmission expansion planning models are introduced. In Section IV, the
mathematical models are presented for both models. Section V provides results and
compares the traditional and proposed models. Section VI presents the conclusions.
III. ECONOMICS-BASED TRANSMISSION EXPANSION PLANNING
In this section, the context of the models and definitions related to the operation
of today?s power markets are provided to clarify the authors? intent. Differences between
the traditional transmission expansion planning model and the proposed model are also
introduced.
A. The Context of the Model
A real power centralized economic dispatch model without losses is used to
estimate the operation costs that will be incurred during the planning horizon after the
expansion has been implemented. For markets where generators can carry out self-
dispatch, the model would still be suitable. When generators are self-dispatched in an
uncongested power network, the generation dispatch quantities might not be equal to the
ones obtained from a centralized dispatch model. However, considering that firms would
37
intend to reduce their generation costs by purchasing cheaper energy from other firms,
the resulting dispatch of the market?s units is expected to be close to the economic
dispatch. On the other hand, when the network is congested the independent system
operator would have to resolve the congestion by re-dispatching the units using a
centralized dispatch model. Since the objective of the investment is to reduce the total
congestion cost over the operational phase of the investment, the centralized model
would give a good estimate of this cost under the assumed simplifications of the model.
The shadow prices of this formulation are referred as the Locational Marginal
Prices (LMP), and the participants in the markets make payments based on these prices.
If the transmission lines are congested during a dispatch, LMPs vary across the system.
Under this structure, the power systems literature commonly applies two measures of
congestion: redispatch cost, and congestion rent. The redispatch cost refers to the
system?s cost due to congestion, namely the difference between the total generation cost
without transmission constraints and the total generation cost with transmission
constraints. In some publications, the term redispatch cost is also referred to as ?out-of-
merit generation cost?, ?cost of constraints?, or ?congestion cost?. The congestion rent
refers to the difference between the total payment that the load requires and the total
payment that the generators receive; this is also called ?merchandising surplus,? or
?congestion cost.? To clarify, the terms ?redispatch cost? and ?congestion rent,? which
are both costs of congestion, are specific to the definitions provided. Using the umbrella
term ?congestion cost? in lieu of either term is sometimes inaccurate, especially without
clarification. To avoid confusion, the authors will not use the term ?congestion cost?
from here on, but will refer specifically to ?redispatch cost? or ?congestion rent?.
38
In this paper, the generation redispatch cost refers to the cost of congestion of the
system. Accordingly, the transmission expansion plan from the system perspective
considers the minimization of the redispatch cost and the investment cost simultaneously.
This proposed model is explained in the following section.
B. Traditional vs. Proposed Transmission Expansion Planning Model
The traditional Transmission Expansion Planning (TEP) model, being a complex
real-world problem, has been extensively studied in the power system literature. The
static TEP model, which studies only one-period peak-load dispatch, is defined as a result
of the general transmission planning studies, which include analysis of several years and
further testing with tools such as power flow, short circuit, and stability analysis (Romero
and Monticelli 1994; Oliveira, Costa et al. 1995; Romero, Gallego et al. 1996; Binato, de
Oliveira et al. 2001; Binato, Pereira et al. 2001; Romero, Monticelli et al. 2002). The TEP
model represented in Romero et al. (Romero, Monticelli et al. 2002) minimizes the
transmission investment cost for a given peak-load demand. In traditional TEP models,
where the generation cost is not explicitly considered, the generation values are assigned
a fixed level and/or are redispatched.
In today?s modern networks, analyzing the topology of the network without
consideration of the competitive operation within markets is not appropriate. In
deregulated markets, user prices, which are determined by the least-cost dispatch, are
indirectly affected by the capacity of transmission lines as they affect the connectivity of
the load and generation. An effective model of the transmission investment problem,
hence, should seek minimum cost investments that ensure least-cost dispatch for the
entire system. Consequently, system-perspective objectives should include the
39
minimization of the investment cost and system redispatch cost, as addressed in some
recent work (Gil, da Silva et al. 2002; Alguacil, Motto et al. 2003; Braga and Saraiva
2005).
Moreover, this objective is consistent with real-life ISO applications. For
instance, the economic transmission planning process in the PJM ISO is based on a
comparison of the total unhedgeable congestion and the total cost of the investment
(Joskow 2005b; PJM website: www.pjm.com). Joskow points out that the unhedgeable
congestion is an approximation of the redispatch cost, or the social cost of congestion. In
the PJM ISO, on the other hand, the unhedgeable congestion is calculated using the total
cost figures already occurred in the system, which may lead to inaccuracies in the
calculations since the total redispatch cost occurring in the current system and the savings
realized by the redispatch cost in the invested system are not directly associated.
Accordingly, in the proposed model, the system redispatch cost is incorporated
into the objective function of the traditional TEP model. Note that the definition of the
system redispatch cost (RC) is
CU
ii ii
iG iG
RCcg cg
??
=?
??
(3.1)
where
C
i
g , the dispatch quantity (MW) of the generator i in the current congested power
system, might take different values than
U
i
g , the dispatch value of the generator i in an
uncongested power system. In a congested power system, higher cost generators (high c
i
)
may be forced to generate more power (
CU
ii
gg? ), and lower cost generators (low c
i
) to
generate lower power (
CU
ii
gg? ) than they do in an uncongested power system. As a
result, the total generation cost of a congested system will be larger than of an
40
uncongested system, i.e.
CU
ii ii
iG iG
cg cg
??
?
??
. Since the total uncongested generation cost is
independent of the transmission grid, it will remain constant under different investment
solutions. Therefore, only the term
ii
iG
cg
?
?
is included in the objective function in (3.9).
From an optimization perspective, the total redispatch cost becomes equivalent to the
total generation cost.
For TEP models, the method of comparing operating cost (incurred every hour of
the day/week/month/year) to the investment ?capital? cost (calculated over the economic
life of the system) is critical. A well-defined coefficient is needed for the generation cost
to make these two amounts comparable. Therefore, if the investment cost is calculated in
present-value terms for a given planning timeframe, the operating costs should also be in
present-value terms for the same timeframe. To the authors? best knowledge, although
similar objective functions for restructured markets have been used in the power literature
(e.g. (Alguacil, Motto et al. 2003)), this critical coefficient is not very well defined under
the TEP context. By applying the proposed multi-period approach, this coefficient can be
calculated easily and will benefit from having a well-defined economic interpretation.
The proposed multi-period model compares the present value of the transmission
investment and the present value of the generation redispatch cost during a given
planning horizon. Therefore, an investment will take place only if the savings from the
investment are higher than the total cost of the investment. Moreover, this planning
approach allows the inclusion of load growth and/or pre-planned generation capacity
expansion. In a sense, the proposed model is an improved version of the traditional model
that addresses critical issues in deregulated markets. The mathematical models for both
41
the traditional and the proposed models are presented and compared in the next section.
IV. MATHEMATICAL MODELS AND BENDERS DECOMPOSITION TECHNIQUE
Section A presents the traditional static TEP model and different approaches used
in the literature. Section B introduces the mathematical model for the proposed approach,
and Section C follows with a discussion of the solution technique.
A. Traditional Transmission Expansion Planning Model
The traditional transmission expansion planning model with DC-flow
approximation is a non-convex, nonlinear mixed-integer program presented as follows
(Romero, Monticelli et al. 2002):
()
(),
min
ij ij i i
ij L i N
vcn r?
??
=+
??
(3.2)
++=Sf g rd (3.3)
()()
0
0
ij ij ij ij i j
fnn????+?=
( )
,ij L? ? (3.4)
()
0
ij ij ij ij
f nnf?+
()
,ij L?? (3.5)
??0 gg (3.6)
??0rd (3.7)
0
ij ij
nn??
()
,ij L?? (3.8)
where the susceptances of new and existing lines are assumed to be the same for each
circuit on a branch. The additional number of circuits on a branch,
ij
n , is defined as an
integer and is limited by the maximum number of permissible right-of-ways on that
branch,
ij
n .
The objective function (3.2) of the TEP problem is the minimization of total
combined cost of investment and load curtailment. Load curtailment illustrates the
amount of infeasibility of the solution. In this model, (3.3) models Kirchhoff?s law,
which provides the balance at each node. In (3.4), Kirchhoff?s voltage law is expressed
42
for an equivalent DC network. The conservation of energy is taken into account by these
nonlinear constraints. Equations (3.5)-(3.8) are the power flow limits in the transmission
lines, the generation limits, the pseudo generation limits, and the maximum number of
circuits that can be added at each branch, respectively.
The TEP problem has been solved using various methods. Among them are zero-
one implicit enumeration (Romero and Monticelli 1994), hierarchical decomposition
(Romero and Monticelli 1994), and branch and bound techniques (Haffner, Monticelli et
al. 2000; Haffner, Monticelli et al. 2001). A constructive heuristic algorithm has been
proposed to solve short-term transmission network expansion planning (Rider, Garcia et
al. 2004). Several adaptive optimization approaches have been used to solve this mixed-
integer nonlinear combinatorial problem, including simulated annealing (Romero,
Gallego et al. 1996; Gallego, Alves et al. 1997), genetic algorithms (GA) (Gallego,
Monticelli et al. 1998), tabu search (Gallego, Romero et al. 2000), and greedy
randomized adaptive search procedures (GRASP) (Binato, de Oliveira et al. 2001). There
are also comparative studies that apply combinatorial methods (Gallego, Monticelli et al.
1998) and a few studies on dynamic transmission expansion models. In 1996, Rudnick et
al. pioneered a genetic algorithm approach (Rudnick, Palma et al. 1996), while Escobar
et al. consider multi-stage transmission expansion (Escobar, Gallego et al. 2004),
developing an efficient GA to solve a multistage and coordinated transmission expansion
problem. Although they include time value in their model, they prefer to ignore
generation investment and operation cost because of the computational complexity.
43
B. Proposed Transmission Expansion Planning Model
This multi-period TEP model seeks the most economical investment plan that still
provides the best operational conditions for the system. The investment plan is based on
comparison of the equivalent economic values of operational and investment costs at the
beginning of the planning horizon (end of the construction period). This approach is
different from the dynamic models proposed by previous researchers (Braga and Saraiva
2005); (Escobar, Gallego et al. 2004), where the investment decisions can take place at
any point. The mathematical form of the proposed model is as follows
()
()
,, ,,
,
min
py py py py
ij ij i i i i
ij L yYp P i N yYp P i N
wcn cg r???
??????
=+ +
??????
(3.9)
subject to
()
,,, , ,py py py py py
i
?++=Sf g r d ( ),, ,ij L p P y Y? ????? (3.10)
()( )
,0 ,,
0
py py py
ij ij ij ij i j
fn?? ? ??+ ? = ( ),, ,ij L p P y Y? ????? (3.11)
()()
,0 ,
0
py py
ij ij ij ij ij
ffnf ??+ ? ( ),, ,ij L p P y Y? ????? (3.12)
,py
??0 gg ,p PyY?? ?? (3.13)
,,py py
??0r d ,p PyY?? ?? (3.14)
0
ij ij
nn??
()
,ij L?? (3.15)
where p P? corresponds to the period p during the year yY? . The objective function
contains the present value of the investment and the present value of the total generation
cost during the planning horizon. The penalty factors
i
? for load curtailment are assigned
to be sufficiently large to ensure the nullification of the load curtailment value at the
optimal solution. The constraints are the same as those of the traditional model; however,
there is a new set of constraints for all PY? periods during the planning timeframe.
Since the dispatch of the generators is performed every hour, or 8760 times a
year, the occurrence of the operational cash flows can be assumed to be continuous and
44
the present value of these values should be calculated with continuous compounding.
Under these assumptions, the comparison coefficients can be treated as compounding
coefficients, as shown in (3.16), for each period p of the year y.
,
8760
e
s
p
p y ry rt
p
eedt?
?
=
?
(3.16)
where p
s
and p
e
are the starting and the ending times of period p during year y,
respectively.
If only one period is used in this model, a transmission expansion plan based on
the peak-load can be obtained. However, as explained in Section III.B, a comparison
coefficient ? is required in the objective function, as shown in (3.17).
()
(),
min
ij ij i i i i
ij L i N i N
wcn cg r? ??
???
=++
???
(3.17)
Since with one-period analysis the congestion is assumed to occur only during
that period, the coefficient ? can be interpreted as the estimated number of peak-load
dispatches during the planning timeframe. In this context, it is difficult to obtain an
accurate estimate for this critical parameter.
C. Benders Decomposition Technique
The Benders Decomposition approach has been used by several authors to address
the traditional TEP problem (Romero and Monticelli 1994; Oliveira, Costa et al. 1995;
Binato, Pereira et al. 2001). This technique has been shown to be effective by Romero
and Monticelli for dealing with the nonconvexity of the traditional TEP problem even
though an optimal solution is not guaranteed (Romero and Monticelli 1994). To
overcome the non-convexity of the TEP, Romero and Monticelli propose a three-phase
hierarchical Benders decomposition approach in which they first relax some of the
45
constraints and decision variables and then gradually increase the complexity of the
problem at each phase. Using this approach, they aim to find the global optimum for the
problem.
For the proposed TEP model, the same hierarchical approach is adopted. The
theory of the Benders decomposition and the hierarchical approach can be found in the
literature (Romero and Monticelli 1994; Floudas 1995). Applying the three-phase
Benders decomposition algorithm, the operational sub-problems take the following
general form:
min
ii ii
iN iN
vcg r?
??
=+
??
(3.18)
subject to
()
i
?++=Sf g r d (3.19)
()()
0
? 0
ij ij ij ij i j
fn?? ???+ ?=
( )
,ij L? ? (3.20)
()()
0
? 0
ij ij ij ij ij
ffnf ??+ ?
( )
,ij L? ? (3.21)
??0 gg (3.22)
??0r d (3.23)
where the investment variables ?
ij
n are given and determined in the investment sub-
problem, which is referred to as the master problem. The linear program given by (3.18)-
(3.23) is solved PY? times for a given set of ?
ij
n at each iteration for each period p and
year y.
During Phase I, constraint (3.20) is relaxed and the resulting transportation
problem is solved as the operational sub-problems. In phase II, the transmission lines are
divided into two sets, namely L
1
, the set of existing branches, and L
2
, the set of candidate
branches, while the constraint (3.20) is included only for the elements of set L
1
. Finally,
in Phase III, all of the constraints (3.19)-(3.23) for the DC-flow model are included.
46
The general form of the investment sub-problem (the master problem), which
decides on the decision variables
ij
n , is given below:
min ? (3.24)
()
()
()
()
,,
kkk
ij ij ij ij ij
ij L ij L
cn v n n??
??
?++?
??
{ }1..kK?? (3.25)
0? ? (3.26)
0
ij ij
nn??
()
,ij L?? (3.27)
where constraints (3.25) correspond to the Benders cuts generated for iterations one
through K. The investment sub-problem is a relaxed equivalent representation of the
original problem given in (3.9)-(3.15). At each iteration, a new Benders cut is added to
the investment problem. The present value of operating costs at iteration k is denoted by
v
k
in (3.28).
,,,kpypyk
ii
yYbB iN
vcg?
?? ?
=
?? ?
(3.28)
where the compounding coefficients
,py
? are calculated as in (3.16).
The sensitivity coefficients,
,py
ij
? , show the sensitivity of the total dispatch cost to
the investment variables. They take a different form for each phase, as shown in (3.29),
(3.30), and (3.31), respectively.
,,,kpypyk
ij ij ij
yYbB
f???
??
=
??
(3.29)
()
()
()
()
,,,
1
,,,,
2
,, ,,
if ,
if ,
py pyk
ij ij
yYpP
k
py pyk pyk
ij
ij i j
pyk pyk
yYpP
ij
f ij L
ij L
??
?
??? ?
??
??
??
?
?
?
?
?
=
?
??
??
?
??
?
?
?
? ??
?
??
??
(3.30)
47
()()
,,,,,,k py pyk pyk pyk pyk
ij ij i j i j
yYpP
???????
??
=??
??
(3.31)
where
,,p yk
ij
? and
,,pyk
i
? are the dual variables associated with constraints (3.19) and
(3.21) for each period p and year y at each iteration k, respectively. Moreover, the
investment variables are assumed to be continuous during Phase I and II and are assumed
to be integers during Phase III.
The results obtained by the described Benders Decomposition approach are
shown for two examples in Section V.
V. EXPERIMENTAL RESULTS
Two power networks are studied to show different aspects of the model. The
study is done just with the purpose of demonstrating the proposed approach and therefore
conclusive remarks are avoided on these two particular systems. First, the characteristics
of the model will be illustrated with Garver?s 6-bus problem. Then, a more realistic
network, the 46-bus Brazilian power network, will be examined to validate the proposed
model. The Benders Decomposition algorithm is coded using the AMPL software with
CPLEX 9.1 solver, which solves the larger multi-period 46-bus model in less than five
minutes. The next section explains the general application process, followed by detailed
explanations for each example.
A. Data for the Model
It is assumed that the entity executing the optimization model is able to estimate
all the input data, including generator cost (bid), transmission capacities, load and load
growth. It is certainly true that getting or estimating all required data for future operation
48
would be critical in any economic analysis. Because of the nature of the problem, it is
inevitable to forecast many of these data elements based on the historical data. In the
deregulated markets, historical data is often publicly available. Many of these data
elements are subject to a great deal of uncertainty and any missing data would still need
to be estimated from scratch.
The collection of data starts with the determination of the planning time frame for
the network. For illustrative purposes, the planning time is assumed to be five years for
both Garver?s 6-bus and the Brazilian 46-bus networks. During this timeframe, all the
data related to the load, the generation, and the transmission lines are forecast. In order to
estimate the total redispatch cost, seasonal load profiles are generated for both examples.
This illustrative profile consists of four periods during each year, corresponding to fall,
winter, spring, and summer, with each period lasting three months. The peak-load is
assumed to occur during summer. A normal load level of 90% of the peak-load is
assumed during the winter season, while during the fall and spring seasons, the load is
assumed to be 70% of the peak-load season.
Load growth per year is assumed to be 2% throughout the model?s five-year
timeframe, which is a realistic value for today?s networks (Hirst and Kirby 2001).
However, the load levels can be calculated individually for each year or even for each
season, depending on the characteristics of the studied network.
After the load duration data is known, the discount coefficients are calculated
using (3.16). TABLE 2 shows the discount coefficients for the periods described above
assuming a 6% discount rate, selected arbitrarily.
49
TABLE 2.
DISCOUNT COEFFICIENTS FOR FOUR-SEASON LOAD PROFILE
y p Fall Winter Spring Summer
1 2,078.01 2,109.42 2,141.30 2,173.66
2 1,957.00 1,986.57 2,016.60 2,047.07
3 1,843.03 1,870.88 1,899.16 1,927.86
4 1,735.70 1,761.93 1,788.56 1,815.59
5 1,634.62 1,659.33 1,684.40 1,709.86
,py
?
The proposed multi-period model also allows different scenarios for the
generation data throughout the five year planning timeframe. However, for the sake of
simplicity, maximum generation capacities are assumed to be constant and equal to the
given values for both the Garver?s and Brazilian networks.
The candidate transmission line data is assumed to have been determined prior to
the study. The given cost for each transmission line is assumed to be the ?present value?
of the total construction costs at the beginning of the planning period, which is the
operation start date of the planned network.
B. Illustrative Example: Garver?s 6-bus Network
This simple network, shown in Fig. 4, is used to illustrate how the proposed
model differs from the traditional TEP model. All the related data can be found in the
literature (Romero, Monticelli et al. 2002). The load profile presented in Section V.A is
used. Additionally, the generation costs are assumed to be $15/MWh, $12/MWh, and
$10/MWh for the generators located at nodes 1, 3, and 6, respectively.
50
Bus 5
Bus 1
Bus 2
Bus 3
Bus 6 Bus 4
Fig. 4. Garver?s 6-bus Network
To compare the solutions provided by the traditional and the proposed model, a
one-period analysis is conducted for the first year peak-load and the results are shown in
TABLE 3. The solution for the traditional approach presented in Section IV.A is reported
under the traditional model column. TABLE 3 further shows the optimum investment
plans with the proposed model, where the objective function (3.17) is utilized. Different
discount coefficients are used in order to study the sensitivity of the solution to this
coefficient. In addition, redispatch cost, congestion rent, and the average load prices are
reported in the same table for each investment plan.
TABLE 3.
GARVER?S NETWORK ONE-PERIOD ANALYSIS
Proposed Model n
ij
, Per Dispatch
Value
Traditional
Model ?
i j 10 50 100 500 1000
2 3 1
2 6 1 2 4 4 4
3 5 1 1 1 1 2 1
4 6 3 2 2 2 2 3
Inv. Cost ($1000) $110 $130 $140 $200 $220 $230
Redispatch Cost $1,040 $1,030 $740 $60 $20 $0
Congestion Rent $2,800 $10,240 $22,010 $33,020 $18,730 $0
Avg Price ($/MWh) $15.47 $14.89 $14.29 $14.85 $12.91 $12.00
51
Notice that even with a relatively small coefficient the optimal solution identified
by the proposed model differs from that given by the traditional approach. With ? = 100
and ? = 500 the redispatch cost becomes negligible. When ? = 1000, the congestion is
relieved. On the other hand, the congestion rent is the highest with ? = 100. Interestingly,
the congestion rent is better for the solution given by the traditional model than for the
proposed model, except when ? = 1000. However, it is difficult to discuss the best
representative coefficient for this example because of the very low investment figures. As
expected, the amount of investment increases, thus relieving congestion, when the
coefficient ? increases since the relative importance of the generation cost vs. total
investment cost increases. In the last row of TABLE 3, the average price for the load is
shown. Since the operating costs are not considered by the traditional model, its average
price is the highest. The minimum prices are obtained when the congestion is relieved
when ? = 1000.
The traditional and proposed models can also be compared considering multi-
period approach using the load profile given in Section V.A for both. For the traditional
model, the multi-period analysis considers only the minimization of the investment cost
as in the one-period analysis. For the proposed model, the minimization of the dispatch
cost is included by using the discount coefficients defined in the same section. For this
example, the coefficients are taken as one-tenth of the values shown in TABLE 2 since
the given investment costs are very low. TABLE 4 shows the optimum solutions with
their associated investment costs, as well as the corresponding redispatch costs and
congestion rents.
52
TABLE 4.
GARVER?S NETWORK MULTI-PERIOD ANALYSIS
n
ij
, Present
Value
Traditional
Model
Proposed
Model
i j
2 5 1
2 6 2 5
3 5 1 1
4 6 2 2
Investment Cost $140,000 $261,000
Redispatch Cost $2,077,300 $-
Congestion Rent $5,291,300 $-
As shown in TABLE 4, the present value of the redispatch cost calculated for the
optimal investment by the traditional model is more than two million dollars. On the
other hand, with the proposed model, the congestion is relieved completely with an
investment of only $261,000. Average prices for each season over the five years are also
calculated to further compare the two models, as shown in Fig. 5.
$9
$10
$11
$12
$13
$14
$15
Fall Winter Spring Summer
A
v
er
ag
e P
r
i
ces
(
$
/
M
W
h
)
Proposed Model
Traditional Model
Fig. 5. Garver?s Network Multi-Period Analysis: Average Prices
For the low load seasons, namely fall and spring, the average price is
$11.74/MWh with the optimal solution of the traditional model and $10/MWh with the
optimal solution of the proposed model. For the high load seasons of winter and summer
the prices increase to $14.29/MWh and $12/MWh with the traditional and proposed
model optimum solutions, respectively.
53
This simple example illustrates the importance of the discount coefficients and the
convenience of the proposed approach to model economic transmission investments. The
proposed multi-period model offers a convenient method to calculate the savings, such as
the redispatch cost savings, provided by the investment. The potential of the proposed
model is further demonstrated with a more realistic system, the 46-bus Brazilian network,
in the next section.
C. 46-bus Brazilian Power Network
A 46-bus power network representing the southern Brazil grid is used in order to
show the effectiveness of the proposed model. All related data except the generator cost
are available in the literature (Binato, Pereira et al. 2001; Romero, Monticelli et al. 2002).
The load profile presented in Section V.A is used once again, assuming a typical 2% load
growth. The generator costs used for this example are given in the TABLE 5. TABLE 6
shows the optimum solutions obtained with traditional and proposed models under the
one-period (first year peak-load level) and multi-period analysis, respectively.
TABLE 5.
GENERATION COST DATA FOR BRAZILIAN NETWORK
Node
c
i
($/MW) Node
c
i
($/MW)
14 $14.86 31 $30.11
16 $25.78 32 $11.85
17 $15.45 34 $24.73
19 $30.31 37 $13.98
27 $29.95 39 $25.15
28 $23.67 46 $12.64
54
TABLE 6.
BRAZILIAN NETWORK OPTIMAL INVESTMENT PLANS
n
ij
One-Period Analysis Multi-Period Analysis
i j Traditional Proposed Traditional Proposed
2 5 1 0 0 0
5 6 2 2 2 2
5 11 0 1 0 0
12 14 0 0 1 1
13 18 0 0 0 1
13 20 1 0 1 0
17 19 0 0 0 0
18 20 0 1 1 1
20 21 2 2 2 2
20 23 1 1 1 1
28 31 0 0 0 1
31 32 0 0 0 1
42 43 1 1 2 2
46 6 1 1 1 1
Investment Cost $million $72.87 $82.06 $96.31 $115.62
Under the one-period analysis and the traditional model, the optimal solution,
when load curtailment is not allowed, is reported (see (Romero and Monticelli 1994)).
The optimum solutions for the proposed model allows more transmission investment
under both one-period and multi-period analysis. The larger investment of $115 million is
made with multi-period analysis and using the proposed model. Notice that with this
investment plan, some of the unconnected nodes are added to the grid since the load
growth and generation costs are considered. For instance, the cheap generator located at
node 28 is only added to the network with the proposed multi-period model. Since the
cost of connecting this node is relatively expensive, the investment decision to do this
will be made only when the operating costs are considered. This illustrates not only the
necessity of the economic investments, but also the efficiency of the proposed model for
planning economic transmission investments. The optimal solutions in TABLE 6 are
55
compared first with a one-period analysis using specified important economics values for
the year-one peak-load dispatch, as summarized in TABLE 7.
TABLE 7.
46 BUS BRAZILIAN ONE-PERIOD ANALYSIS
Per Dispatch Value Traditional Proposed Difference
Total Investment Cost $72,870,000 $82,062,000 ($9,192,000)
Total Dispatch Cost $146,553 $132,641 $13,912
Total Load Payment $4,127,339 $205,313 $3,922,026
Total Generator Payment $1,281,781 $192,923 $1,088,858
Redispatch Cost $16,314 $2,402 $13,912
Congestion Rent $2,845,558 $12,390 $2,833,168
Average Price ($/MWh) $600 $30 $570
As shown in TABLE 7, the average price for a load given by the traditional model
is $600/MWh, although the generation costs range between $11.85/MW and $30.31/MW.
Since the traditional model only seeks a feasible generation dispatch, operational costs
remain very high with this optimal solution. The system remains highly congested, since
branch 18-20, which has a shadow price of $10,170/MW, is not included. The congestion
rent associated with this branch alone is higher than $2 million.
The comparison coefficient for the one-period analysis is chosen to be 9,674.04,
which is the total of the discount coefficients for the summer season. With an additional
$10 million investment, the total load payment per dispatch decreases from thousands to
hundreds of dollars, and the average price for the load decreases from $600/MWh to
$30/MWh, as suggested by the proposed model. When the optimal solution of the
proposed model is implemented rather than the traditional model, the redispatch cost
value at the peak-load dispatch decreases from $16,310 to $2,400.
56
Both the traditional and proposed model solutions obtained with a one-period
peak-load analysis become infeasible in the year five summer season because of the load
growth. To maintain a feasible network during the planning timeframe the multi-period
analysis is required. The results for the multi-period analysis are provided in TABLE 8.
TABLE 8.
46-BUS BRAZILIAN MULTI-PERIOD ANALYSIS
Present Value ($million) Traditional Proposed Difference
Total Investment Cost $96 $116 ($19)
Total Dispatch Cost $4,065 $3,992 $73
Total Load Payment $6,450 $5,730 $720
Total Generator Payment $5,929 $5,665 $264
Redispatch Cost $76 $2 $73
Congestion Rent $522 $66 $456
The proposed model requires an additional investment of $20 million. In contrast,
the redispatch cost is $73 million less with the investment suggested by the proposed
multi-period model, meaning that the system welfare is improved by this amount. In
addition, the total load payments are reduced by more than $720 million. From the load
perspective, the benefit/cost ratio is 36 for every additional dollar spent on this solution.
Since cheaper generators are being brought online, the total generation payments are also
reduced. The average prices for each season over the five years are shown in Fig. 6. For
the high seasons of winter and summer the prices are significantly higher with the
traditional model ($34/MWh, $37/MWh) than the proposed model ($26/MWh,
$27/MWh) optimum solutions. The magnitude of the price fluctuations experienced using
the proposed model are also considerably less than with the traditional model.
57
$24
$26
$28
$30
$32
$34
$36
Fall Winter Spring Summer
Av
er
ag
e
P
r
i
ce (
$
/
M
W
h
)
Proposed
Model
Traditional Model
Fig. 6. Brazilian Network Multi-Period Analysis: Average Prices
The results for the Brazilian network show that the proposed multi-period model
leads to efficient networks in terms of both the dispatch cost and the prices. It is possible
to improve both system costs and consumer costs with the relatively cheap transmission
investments determined by this model.
VI. CONCLUSIONS
An economics-based transmission expansion planning model is proposed in this
paper. Optimization from the system welfare perspective is considered, with a multi-
period planning approach. The proposed multi-period model overcomes the drawbacks of
the one-period model by considering continuous operation of the market during the
planning timeframe. When congestion is a frequent event, occurring with several load
levels during the year, a multi-period model is a more appropriate treatment. With the
proposed planning model, discount coefficients are defined to make short-term operating
costs comparable to long-term investment costs. Consequently, system operators will
now be able to accurately predict the optimum amount of transmission expansion for a
particular power market. The results for the case studies show that the proposed model is
flexible enough to handle different sized networks with different load and/or generation
58
scenarios. With the multi-period proposed model, the redispatch cost and the investment
cost are minimized effectively and a more efficient network in terms of both the dispatch
cost and the prices obtained. The proposed model should be followed by an analysis of
the optimum solutions from the perspectives of the different market participants. Such a
study will be the subject of a future paper.
59
CHAPTER 4
ECONOMIC COMPARISON OF TRANSMISSION EXPANSION PLANS IN
DEREGULATED MARKETS
Abstract? When transmission congestion reaches a high level, short-term congestion
management tools become more expensive than capital cost investments such as
generation or transmission expansion. In such cases, an economics-based investment plan
should be developed for the power system. Although there is no well accepted procedure
to accomplish this, numerous models and approaches have been proposed in the power
literature. In this paper, we develop a decision framework that can be used to model
transmission expansion planning and to make economic comparison of different
transmission investment plans feasible. We define and compare three approaches under
this framework: 1) A mathematical model from a social welfare perspective, 2) a market-
based approach under a budget constraint, and 3) an uncongested system obtained using a
market-based approach. In addition, we present several measures that can be used to
compare these transmission investment plans.
Index Terms? Benders decomposition, economic transmission planning, market-based
transmission planning, mixed-integer nonlinear programming, power transmission
planning, transmission expansion planning.
60
I. NOMENCLATURE
The notation used in the paper is given below for quick reference.
Variables
ij
n
Number of added circuits to branch (i, j)
g Vector of generated active power
i
g
Generation at node i (MW)
r Vector of load curtailments
i
r
Load curtailment at node i (MW)
f Vector of active-power flows through the lines
ij
f
Flow in branch (i, j) (MW)
j
?
Voltage angle at bus j
Parameters
ij
c
Cost of adding a circuit to branch (i, j) ($)
i
c
Cost of generation for generator at node i ($/MW)
i
?
Penalty factor associated with load curtailment at bus i
S Node-branch incidence matrix
d Vector of estimated loads
ij
?
Circuit susceptance for branch (i, j)
0
ij
?
Initial circuit susceptance for branch (i, j)
0
ij
f
Initial flow limit in branch (i, j) (MW)
ij
f
Flow limit in branch (i, j) (MW)
g
Vector of maximum generation capacity
0
ij
n
Initial number of circuits in branch (i, j)
ij
n
Maximum number of new circuits added to branch (i, j)
,py
?
Comparison/compounding coefficient at period p year y
k
v
Present value of the operating cost at iteration k
,py
ij
?
Sensitivity coefficient for branch (i, j) at period p year y
L
Set of circuit candidates
N Set of nodes
Y Set of planning years
P Set of periods during year y
K Set of iterations
61
II. INTRODUCTION
Deregulation has changed the objectives of the transmission planning process.
Transmission planning models now need to be reformulated to include new operation
rules and to reflect the objectives of the planners. In traditional transmission expansion
models the economic effect of congestion is usually neglected. Traditional models seek
the minimum investment cost for a feasible peak-load dispatch without considering the
generator costs explicitly (see (Romero, Monticelli et al. 2002)). This approach needs to
be updated for today?s deregulated markets for two reasons. First, when competition of
generators is introduced, the least-cost dispatch approach should be considered. At
present, rather than relying solely on a feasible dispatch approach, the concept of least-
cost dispatch is being used in competitive markets. Second, when the economic effects
are taken into account, investment decisions should be based on a comparison of the
equivalent costs of the investment and the savings that will be realized as a result of the
investment. Consequently, a peak-load analysis approach fails to provide sufficient
information about the cost of congestion in the system.
In deregulated power markets, in addition to the reliability-based transmission
planning that has been used in the past, economics-based transmission planning is
necessary to alleviate the excess cost of congestion. The congestion cost has become an
important factor affecting electricity prices in the new deregulated markets (see (PJM
2006); (Joskow 2005a)). Several approaches have been proposed to plan these
economics-based transmission investments (see (Wong, Chao et al. 1999); (Buygi, Balzer
et al. 2004); (Sozer, Park et al. 2006a)). The Pennsylvania-New Jersey-Mary Land (PJM)
Independent System Operator (ISO) has included projects that are intended to relieve the
62
persistent congestion in its regional transmission expansion planning procedures (Joskow
2005b). However, a common framework for economics-based transmission expansion
planning (E-TEP) has not yet been established.
In this paper, we built such a decision framework to help analyze and compare
power systems. We aim to compare different E-TEP approaches and to show the
differences in the resulting power systems. First, we use mathematical programming and
model E-TEP from a social welfare perspective as a mixed-integer nonlinear problem.
This model minimizes total investment cost and total redispatch cost, by considering the
least-cost dispatch of the generators during the planning timeframe. Second, a heuristic
approach is used to plan market-based transmission investments. In this approach, the
candidate transmission lines are determined based on the price differences between the
nodes and the best investment plan chosen within a budget. Third, the cheapest way to
relieve congestion in the power system is found. The same candidate transmission lines
are used as those determined by the market-based approach. Once these three investment
plans are obtained, it is possible to compare them with the do-nothing alternative using
the measures defined in Section V.
The remainder of this paper is organized as follows: Section III describes the
proposed decision framework for transmission expansion planning. In section IV, the
economics-based transmission expansion planning approaches are presented. Section
IV.A covers the mathematical model for transmission expansion planning in deregulated
markets and Section IV.B covers the market-based approach for transmission expansion
planning. Section V presents the measures used to compare the investment plans and
Section VI introduces a 179-bus power system and compares three alternative investment
63
plans for this power grid. The paper concludes with a summary of the findings in Section
VII.
III. A DECISION FRAMEWORK
This paper describes a real power economic dispatch model where the shadow
prices of this formulation are referred to as the Locational Marginal Prices (LMP). The
participants in the power market, namely the generators and the load, make or receive
payments based on these prices. A dc-flow approximation is preferred since only long-
term economic planning is considered. Two terms are used to measure the cost of
congestion in the power system. First, the redispatch cost represents the system?s cost due
to congestion, namely the difference between the total generation cost without
transmission constraints and the total generation cost with transmission constraints. The
term redispatch cost is also often referred to as ?out-of-merit generation cost?, ?cost of
constraints?, or ?congestion cost?. Second, the congestion rent refers to the difference
between the total payment that the load requires and the total payment that the generators
receive; this is also called ?merchandising surplus,? or ?congestion cost.? To avoid
confusion, the term ?congestion cost? will not be used in this paper, but rather we will
refer specifically to ?redispatch cost? or ?congestion rent?.
The decision framework used in this paper is decomposed into two phases: the
construction phase and the operation phase. Once the decision concerning the investment
plan is taken, the construction period begins. During this period, all of the investment
costs occur. When the planned transmission lines are ready to operate, the operation
phase starts. A planning horizon is determined to take into consideration the savings of
the investment. This approach allows us both to consider the least-cost dispatch options
64
and to make an effective economic analysis during the entire timeframe out as far as the
planning horizon.
In this approach, comparing the operating cost that is incurred every hour of the
day/week/month/year to the investment ?capital? cost calculated over the economic life
of the system is critical. A well-defined coefficient is needed for the operational costs to
make these two amounts comparable. Therefore, if the investment cost is calculated in
present-value terms for a given planning timeframe, the operating costs should also be in
present-value terms for the same timeframe. By using the proposed decision framework,
this coefficient can be calculated easily and it will have a well-defined economic
interpretation.
Since the dispatch of the generators is performed every hour, 8760 times a year,
the occurrence of operational cash flows can be assumed to be continuous and the present
value of these values calculated with continuous compounding. Under these assumptions,
the comparison coefficients can be calculated as compounding coefficients as shown in
(4.1) for each period p of the year y.
,
8760
e
s
p
p y ry rt
p
eedt?
?
=
?
(4.1)
where p
s
and p
e
are the starting and the ending times of period p in year y, respectively.
Once the planning horizon and the periods for each year out as far as this planning
horizon are determined, these compounding coefficients can be calculated and used to
calculate the present value of any operational costs, such as generation cost, redispatch
cost, or congestion rent. All the figures calculated in this paper are directly comparable,
65
since we use the same planning horizon for all the E-TEP approaches proposed in the
following section.
IV. ECONOMICS-BASED TRANSMISSION EXPANSION PLANNING
The E-TEP addresses the persistent congestion issues in a power market and aims
to alleviate congestion in order to relieve the cost of congestion to the system. Assuming
there is no reliability problem, the best transmission investment plan for the system is
selected in this section by considering first a mathematical programming approach, where
the investment cost and redispatch cost are minimized simultaneously, and then a market-
based heuristic approach, both with and without a budget constraint.
A. Mathematical Programming Approach
A multi-period TEP model that seeks the most economical investment plan can be
used to provide the best operational conditions for the system. This investment plan is
based on a comparison of the equivalent economic values of the operational and
investment costs at the beginning of the planning timeframe (end of the construction
period). This approach is presented fully in an earlier paper (Sozer, Park et al. 2006a).
The mathematical form of the mixed-integer non-linear problem is as follows:
()
()
,, ,,
,
min
py py py py
ij ij i i i i
yYpP iN yYpP iNij L
wcn cg r???
?? ? ?? ??
=+ +
??????
(4.2)
subject to
()
,,, , ,py py py py py
i
?++=Sf g r d ( ),, ,ij L p P y Y? ????? (4.3)
()( )
,0 ,,
0
py py py
ij ij ij ij i j
fn?? ? ??+ ? = ( ),, ,ij L p P y Y? ????? (4.4)
()()
,0 ,
0
py py
ij ij ij ij ij
ffnf ??+ ? ( ),, ,ij L p P y Y? ????? (4.5)
,py
??0 gg ,p PyY?? ?? (4.6)
,,py py
??0r d ,p PyY?? ?? (4.7)
0
ij ij
nn??
()
,ij L?? (4.8)
66
where p P? corresponds to the period p during the year yY? . The objective function
contains the present value of the investment and the present value of the total generation
cost during the planning timeframe. The penalty factors
i
? for load curtailment are
assigned to be sufficiently large to nullify the load curtailment value at the optimal
solution. The constraints are the same as those of the traditional transmission expansion
model (Romero, Monticelli et al. 2002); (Romero and Monticelli 1994); however, there is
a new set of constraints for all PY? periods out as far as the planning horizon. Under
the continuous operational cash flows and continuous compounding assumptions, the
comparison coefficients can be calculated as shown in (4.1) for each period p of the year
y.
A hierarchical Benders decomposition approach such as that proposed by Romero
and Monticelli (Romero and Monticelli 1994) is adopted here to solve this multi-period
TEP model. To overcome the non-convexity of the TEP, Romero and Monticelli use a
three-phase hierarchical Benders decomposition approach in which they first relax some
of the constraints and decision variables and then gradually increase the complexity of
the problem at each phase, seeking the global optimum for the problem. They have
shown that this technique is an effective way to deal with the nonconvexity of the
traditional TEP problem, even though an optimal solution is not guaranteed. The theory
behind Benders decomposition and the hierarchical approach can be found in the
literature (Romero and Monticelli 1994; Floudas 1995). The detailed application of the
method to the proposed E-TEP is presented in an earlier paper (Sozer, Park et al. 2006a).
67
B. Market-based Heuristic Approach
For deregulated markets using nodal or zonal pricing such as LMP, market-based
transmission investments have been proposed by several authors (Wong, Chao et al.
1999; David and Wen 2001; Buygi, Balzer et al. 2004). Given the price signals present in
the market, bottlenecks in the power grid can be singled out to highlight the necessary
transmission investments. The basic idea is to observe high price differences within the
power grid and the select the candidate transmission projects based on these observations.
Given the decision framework described in Section III, we can use the following
procedure to determine the best transmission investment plan to alleviate congestion:
? Determine all the parameters for the decision framework.
? Solve the real power economic dispatch models for each period p and each year y,
then compile a list of all the congested lines.
? Calculate the equivalent value of the congestion rent associated with each line (i,j)
using the following formulation
( )
,,maxpy py
ij ij ij
yYpP
CR f??
??
=?
??
? Rank the candidate lines by decreasing order of their estimated congestion rent.
? Choose an investment plan, starting from the largest
ij
CR .
If the investment plan is to remain within a budget, the number of additional
circuits for each candidate line can be chosen to relieve the congestion on that line. By
investing in the most costly transmission lines, it is possible to relieve the most
problematic congestion in the system while at the same time remaining within a budget.
68
On the other hand, if we want simply to relieve the congestion in the power
system, we can continue the above procedure by the following:
? Determine an investment plan by investing in all the congested lines to provide a
sufficient number of circuits.
? Solve the real power economic dispatch models for each period p of each year y
for the current investment plan, hence determining the new
ij
CR values.
? Repeat the first two steps until all the congestion is relieved in the power system,
i.e. until all
ij
CR is equal to zero.
? Perform a fine-tuning analysis by decreasing the number of circuits on each line
one by one.
By following this procedure it is possible to calculate the uncongested system
with the minimum investment cost. For some power systems, however, reaching this
totally congestion-free power system might be impracticably expensive. These
procedures are illustrated in the numerical example section below.
V. COMPARISON OF THE TRANSMISSION INVESTMENT PLANS
The main purpose of the E-TEP is to relieve severe congestion in the system with
the aid of economic investment plans. From this point of view, investment plans can be
compared in terms of the improvement they will cause in the power systems. In order to
achieve this objective, it is important to first define several measures in different
categories as follows:
69
A. Severity of the Transmission Congestion and Congestion Profile
Two representative measures are used here to compare the severity of the
transmission congestion. As the definitions provided in Section III explain, the redispatch
cost represents the system cost of congestion for the power network. The equivalent value
of the total redispatch cost at the beginning of the planning horizon is calculated by
,,, ,,,
?
py py py py py py
ii ii
yYpP iN yYpP iN
RCcg cg??
?? ? ?? ?
=?
?? ? ?? ?
(4.9)
where
,
?
py
i
g is the generation dispatch value of the uncongested system at node i for
period p and year y.
The congestion rent, which assesses the extra charge due to congestion for the
participants, is also used. This measure takes into account the prices for the participants
and can be calculated using shadow prices for the lines or for the nodes given in (4.10) or
(4.11).
()
()
,,max
,
py py
ij ij
ij LyYpP
CR f??
???
=?
???
(4.10)
,,, ,,,py py py py py py
ii ii
yYpP iN yYpP iN
CR d g?? ??
?? ? ?? ?
=?
?? ? ?? ?
(4.11)
It is also possible to compare the congestion profiles of the investment plans,
which represents the congested lines and the associated congestion rent. Showing the
total congestion rents side by side for each investment plan provides a better
understanding of the behavior of the resulting power network.
B. Competition
To measure the degree of competitiveness in the power networks Buygi et al.
suggest that the flatness of price profile, and/or congestion cost can be used (Buygi,
Balzer et al. 2004). When prices throughout the system differ greatly, participants face
70
more discriminative prices, and consequently competition is discouraged. In a similar
way, when the redispatch cost and the congestion rent are severe, this indicates that the
cheapest generation cannot be dispatched in the power system. On the other hand, the
average price for a load is a measure of the performance of the power network.
Accordingly, a decrease in the average price for a load shows the degree of improvement
provided by the investment. As a result, besides the redispatch cost and the congestion
rent, it is helpful to calculate the average price range of the system,
p
? , and the average
cost for load,
p
? , as shown by (4.13) and (4.12), respectively.
{} {}
,,
1
max min
ppypy
ii
iNiN
yY
Y
??
??
?
??
?= ?
??
?
(4.12)
,,
,
1
py py
ii
p iN
py
yY
i
iN
d
Yd
?
?
?
?
?
=
?
?
?
(4.13)
C. Efficiency of the Investment Plan
A simple benefit/cost ratio can be used to compare the efficiency of the
investment plans. Here, the savings for the redispatch cost or the congestion rent are
used, which consist of the decrease in the preferred congestion cost after the investment.
Dividing the savings by the total investment cost gives the estimated savings for each
dollar spent. To calculate this benefit/cost ratio, all of the terms should be in equivalent
values.
D. Beneficiaries Analysis
The total equivalent payment for each load and generator are calculated in (4.14)
and (4.15), respectively. Taking the difference of the total payment without any
investment and with the investment gives the benefit or the loss for each participant.
71
,,,py py py
iii
yYpP
Dd??
??
=
??
(4.14)
,,,py py py
iii
yYpP
Gg??
??
=
??
(4.15)
The benefit/loss profile can be used to compare proposed investment plans from
the investor?s perspective. A benefit/cost ratio can be calculated for the total benefit of
the load or the generators separately by using this formulation. The applicability of these
measures is illustrated with a numerical example in the following section.
VI. NUMERICAL EXAMPLE
The example studied here is a 179-bus system, as shown in Fig. 10, based on the
Western Electricity Coordinating Council (WECC) power network, which is used to
compare different investment plans. First, all the data throughout the planning timeframe
related to the load, the generation, and the transmission lines are forecast. The WECC
179-bus system is an equivalent reduced system with 104 demand buses and 29 generator
buses. In order to apply E-TEP models with the proposed decision framework, it is
necessary to estimate some of the required data as only peak-load dispatch data with load
and generation amounts were available, along with the voltage levels of the transmission
lines. For this study, we will assume that the given load data is the peak-load for the first
year of the planning timeframe (see TABLE 17 in the Appendix section of this chapter)
and calculate the maximum capacities of the generators by arbitrarily assigning used
capacity percentages (see TABLE 18 in the Appendix section of this chapter). The
generator marginal costs are assigned based on the guesstimated locations (see TABLE
18 in the Appendix section of this chapter). The capacities and the investment costs of the
transmission lines are calculated based on the voltage level and the distance estimates of
72
the nodes (see TABLE 19 in the Appendix section of this chapter).
In order to calculate the operational costs, the same seasonal load profiles as used
in an earlier paper (Sozer, Park et al. 2006a) were applied. This illustrative profile
consists of four periods during each year, corresponding to fall, winter, spring, and
summer, where each period lasts three months. The following assumptions are made: The
peak-load occurs during the summer. The winter load is 90% of the peak-load. During
fall and spring the load is 70% of the peak-load. After the load duration data is identified,
we can then calculate the discount coefficients using (3.16). TABLE 9 shows the
discount coefficients for the periods described above assuming a 6% discount rate,
selected arbitrarily. All of the total cost figures in this paper are shown in terms of their
equivalent value at the beginning of the planning timeframe, calculated using these
coefficients.
TABLE 9.
DISCOUNT COEFFICIENTS FOR FOUR-SEASON LOAD PROFILE
y p Fall Winter Spring Summer
1 2,078.01 2,109.42 2,141.30 2,173.66
2 1,957.00 1,986.57 2,016.60 2,047.07
3 1,843.03 1,870.88 1,899.16 1,927.86
4 1,735.70 1,761.93 1,788.56 1,815.59
5 1,634.62 1,659.33 1,684.40 1,709.86
,py
?
As stated, the cost for each transmission line is considered to be the present value
of the total construction costs at the beginning of the planning period, which is the
operation start date of the planned network. This way, we obtain both the operational
costs and the investment costs in terms of their equivalent values at the same point in
73
time.
We assume a typical 2% load growth per year during the planning timeframe.
This value is realistic for today?s networks (Hirst and Kirby 2001). However, the load
levels can be calculated individually for each year or even for each period out to the
planning horizon depending on the characteristics of the studied network. After all the
required data are set, the procedures described above can be applied.
A. Alternative Investment Plans
The calculations are performed for three different investment plans in order to
show the difference in the resulting networks for the different approaches. First, we solve
the multi-period E-TEP model from the social welfare perspective. The Benders
decomposition method is coded using the AMPL software with CPLEX 9.1 solver, which
solves the multi-period 179-bus model in around 60 minutes. Second, the market-based
transmission planning procedure is used to determine an investment plan within a budget.
To be able to compare these two investment plans, the same budget is selected as the
optimum solution of the mathematical programming model. Consequently, both
investment plans have approximately the same total investment cost. The third model is
the investment plan that relieves all the congestion in the power system by investing in all
the congested lines, as determined by the market-based approach.
The first two investment plans, E-TEP and the market-based approach with a
budget, are shown in TABLE 10 and the investment plan for the uncongested power
system is shown in TABLE 11. The total number of invested circuits is 22 for the E-TEP
model and 14 for the market-based approach and the total investment costs are $404.9
and $404.4 million, respectively. While the social welfare model optimizes the total
74
money spent to relieve congestion, the market-based model focuses on the most
congested lines, which may not lead to the cheapest solution. In order to relieve the
congestion completely it is necessary to substantially increase the level of investment; the
total number of circuits required to relieve congestion is 63, with a total investment cost
of $3,134.8 million. These results are also summarized in TABLE 12.
TABLE 10.
INVESTMENT PLANS FOR E-TEP AND MARKET-BASED APPROACHES
ij
n
i j E-TEP Market-Based
12 139 - 1
33 34 1 -
68 70 3 3
68 71 3 -
78 66 - 1
85 36 1 -
136 152 1 1
137 61 2 -
137 143 4 4
141 143 3 -
146 143 4 4
TABLE 11.
INVESTMENT PLAN FOR UNCONGESTED SYSTEM
i j Uncongested i j Uncongested i j Uncongested
12 139 1 8 17 1 88 86 2
33 34 7 28 29 1 31 80 1
68 70 3 29 14 1 83 89 1
68 71 3 50 58 1 101 113 1
78 66 1 142 64 1 89 90 1
85 36 2 150 154 2 154 143 3
136 152 1 157 161 1 31 32 1
137 61 - 90 86 1 83 168 1
137 143 2 55 41 1 168 169 1
141 143 3 78 76 1 169 114 1
146 143 5 17 5 1 82 76 1
3 8 1 87 88 2 131 119 1
7 28 1 82 87 2 130 131 1
115 130 1
75
Once all the different alternative investment plans have been constructed, the
resulting networks can be evaluated. As described earlier, the investment plans and the
resulting networks can be compared in terms of the severity of the remaining congestion,
the efficiency of the investment plan, the degree of competition, and the beneficiaries of
the proposed investment plan.
B. The Profile and the Severity of the Transmission Congestion
The initial power network is estimated to result in a total of almost $3 billion in
redispatch costs and $4.6 billion in congestion rent during the planning timeframe.
TABLE 12 summarizes the alternative investment plans, along with their predicted
congestion figures. If the investment plan produced using the E-TEP model is selected to
alleviate the congestion, the redispatch cost is expected to be significantly reduced, but if
the investment plan produced using the market-based approach is selected with the same
budget, neither the congestion rent nor the redispatch cost will be reduced sufficiently. In
order to achieve an uncongested power network, an investment of more than $3 billion
must therefore be made, an amount substantially greater than the cost of congestion for
the system.
TABLE 12.
COMPARISON OF INVESTMENT PLANS
($million) Do Nothing E-TEP Market-based Uncongested
Investment Cost 0 405 404 3,135
Number of Circuits 0 22 14 63
Redispatch Cost 2,990 550 2,392 0
Congestion Rent 4,600 3,372 3,654 0
76
A further comparison of these alternative investment plans and their resulting
congestion profiles, shown in TABLE 13, reveals the associated total congestion rent for
each line,
ij
CR . The lines are sorted in decreasing order of the initially congested lines.
TABLE 13.
CONGESTION RENT FOR THE ALTERNATIVE INVESTMENTS
($million)
ij
CR
i j Do Nothing E-TEP Market-based
78 66 652.29 464.37 0.00
146 143 512.73 0.00 0.00
136 152 467.56 0.00 0.00
12 139 455.33 1210.60 0.00
68 71 420.93 0.00 0.00
137 143 413.64 0.00 0.00
150 154 303.29 0.00 0.00
5 160 301.84 105.99 284.40
50 58 248.13 28.89 472.75
85 36 240.44 256.24 212.26
142 64 170.80 21.75 1415.25
48 55 129.78 0.00 14.45
33 34 117.52 179.04 102.92
3 8 66.58 47.71 46.85
68 70 41.06 0.00 176.63
8 17 35.98 17.88 22.74
157 161 13.94 9.51 9.15
29 14 8.39 260.99 38.14
7 28 0.00 34.61 0.00
17 5 0.00 5.44 0.00
78 76 0.00 0.00 31.44
83 89 0.00 88.15 0.00
83 168 0.00 183.53 0.00
87 88 0.00 16.31 0.00
88 86 0.00 7.67 0.00
101 113 0.00 359.45 0.00
141 143 0.00 0.00 732.14
150 154 0.00 36.99 95.05
154 143 0.00 36.43 0.00
Total Congestion Rent 4,600.25 3,371.56 3,654.17
77
The first column in the TABLE 13 represents the case where there is no
investment and the existing network is retained, with a total congestion rent of $4.6
billion dollars. The next column shows the predicted effects of the E-TEP model
implementation, with the invested lines highlighted. Although some of the highly
congested lines are not included in this plan, some of the low congested lines are
preferred and line 141-143 is included in the investment plan even though it is not
congested in the initial network. The market-based approach, on the other hand, invests in
the highly congested lines and relieves congestion on those, but does not reduce the
overall congestion of the system as much as the E-TEP approach. This emphasizes that in
order to find the optimum transmission expansion plan, it is necessary to look at the
overall power network rather than simply focusing on market signals.
C. Efficiency of the Investment Plan
A convenient way to compare the efficiencies of the different investment plans is
to calculate a benefit/cost ratio. The benefit of each alternative is calculated as the
savings relative to the do-nothing alternative. TABLE 14 illustrates the savings achieved
by each of the investment plans for each dollar spent. The E-TEP model, which takes the
social welfare perspective, produces the highest benefit/cost ratio for both the redispatch
cost savings and the congestion rent savings. This is not unexpected; to relieve the
congestion in the power system is very expensive and may not always be economically
justified from a social welfare perspective. There is thus an optimum level of congestion
that can be tolerated in power systems, and this optimum amount may not be the same for
different planners or investors.
78
TABLE 14.
SAVINGS TO INVESTMENT COST RATIO
E-TEP Market Based Uncongested
Redispatch Cost Savings 6.03 1.48 0.95
Congestion Rent Savings 3.03 2.34 1.47
D. Competition
Buygi et al. suggested that the flatness of the price profile can be use to indicate
the degree of competitiveness in a power system (Buygi, Balzer et al. 2004).
Consequently, the average price range is used here as a measure of the degree of
competitiveness in the power system models. In Fig. 7, the average LMP ranges for the
four seasons are illustrated for three of the alternative investment plans. The uncongested
case is not included in this analysis as the price throughout the power system is the same
when the congestion is completely relieved. The figure shows that the system behaves
differently for the different load profiles found for each season. For fall and spring, the
market-based investment plan works better than the current system. However, the E-TEP
model performs the best for these two seasons, with minimal price fluctuations. For
winter, all three investment plans result in a relatively high price range of around
$50/MWh, with the highest being for the E-TEP model. For the summer peak-load
season, the E-TEP model performs the best and the market-based approach the worst,
with an average LMP range of $57.34/MWh. This leads to the conclusion that the E-TEP
model is the most competitive of the three.
79
Price Range
$-
$10
$20
$30
$40
$50
$60
$70
Fall Winter Spring Summer
Do Nothing
E-TEP Model
Market-based
Fig. 7. Average Price Range for Alternative Investment Plans
Examining the average load prices reveals a clear improvement in the power
system for the customer. In Fig. 8, the seasonal average prices for all four of the options
are illustrated. For the fall and spring seasons, the prices are low for all four of the
alternative investment plans, with the minimum average price achieved by the proposed
E-TEP model. However, for the winter season, both the market-based investment plan
and the uncongested power system have lower average prices. Interestingly, for the
summer peak-load season, the highest average price is obtained for the uncongested
system. In this case, the presence of some transmission congestion results in lower prices
for the customer. The prices are again lowest with the E-TEP model.
80
Average Price
$14
$18
$22
$26
$30
$34
Fall Winter Spring Summer
Do Nothing E-TEP Model
Market-based Uncongested
Fig. 8. Average Load Price
The behavior of the LMPs over the years for load growth and seasonal effects are
shown in Fig. 9. The figure reveals that the price profile of the power network changes in
the third year. For fall and spring, for the first two years the prices are the highest if there
is no investment, but then the market-based approach becomes slightly more expensive.
The E-TEP model always has the lowest prices for fall and spring. For winter, the
average price remains the same throughout the planning timeframe only for the
uncongested system; all three of the other investment plans experience increasing prices.
For the summer, all the investment plans perform differently, and the investment plan
suggested by the E-TEP model stays the lowest until year three. By year five, however,
all of the investment plans have similar average prices.
81
Fall
10
15
20
12345
Year
Do Nothing
E-TEP Model
Market-based
Uncongested
Winter
15
20
25
30
35
12345
Year
Summe r
25
30
35
40
12345
Year
Spring
10
15
20
12345
Year
Fig. 9. Seasonal average load prices for the planning timeframe
E. Beneficiaries Analysis
The beneficiaries analysis for load is summarized in TABLE 15. The total benefit
and total loss are the sums for all beneficiaries or losers, respectively. Unsurprisingly, the
most benefit is provided by the uncongested system and the least loss is achieved by the
market-based approach. Looking at the grand totals, which represent the total of the
benefits and losses, once again the uncongested system performs the best for the load.
However, once the cost of investment is also taken into account and the alternative
investment plans compared using the benefit/cost ratio (B/C), the best performance is
again obtained with the E-TEP model.
82
TABLE 15.
BENEFIT/ LOSS ANALYSIS FOR LOAD
LOAD ($million) E-TEP Model Market Based Approach Uncongested
Total benefit 6973 3731 8777
Total loss -4546 -2604 -4333
Grand Total 2427 1127 4443
Investment Cost 405 404 3135
B/C 6.0 2.8 1.4
A similar beneficiaries analysis for generators is shown in TABLE 16. Comparing
the payments to the generators both with and without investment, losses are clearly
higher than benefits for generators. This is an expected result, since it is reasonable to
expect that cheaper generators will be dispatched and the prices will drop once the
congestion is alleviated in a power system, indicating that the degree of competition in
the power system will increase. For almost the same amount of investment cost a larger
impact on both the benefits and losses are observed with the E-TEP Model comparing
with the market-based model.
TABLE 16.
BENEFIT/ LOSS ANALYSIS FOR GENERATORS
GENERATORS ($million) E-TEP Market Based Uncongested
Total benefit 5923 2793 8123
Total loss -7122 -2974 -7966
Grand Total -1198 -181 157
Investment Cost 405 404 3135
B/C -2.96 -0.45 0.05
VII. CONCLUSION
This research examines a decision framework for transmission expansion
planning designed to alleviate congestion. Two types of E-TEP approaches are used.
First, an optimum investment strategy is defined by modeling TEP from a social welfare
83
perspective. Second, a market-based approach is applied that determines the individual
expansion values of each line. Moreover, several measures are defined to facilitate the
comparison of different investment plans under this decision framework. When
congestion is a frequent event, occurring with several load levels during the year, a multi-
period model is more appropriate. The defined discount coefficients ensure that
equivalent values for all operational costs occurring during the planning horizon can be
calculated and that these values are comparable to the investment costs. Since all the
financial cost figures are given in the same terms, a valid comparison is possible. A 179-
bus power system is used to demonstrate the applicability of this decision framework and
different approaches are used to calculate several measures for the network. A
mathematical programming approach is used to consider the entire power system from
the system welfare perspective and a market-based heuristic approach is used to consider
the individual expansion values of each line. The results show that a consideration of the
entire system is likely to produce a more effective investment plan.
84
APPENDIX
Fig. 10. One-line Diagram for the WECC 179-bus Power Network
85
TABLE 17.
INITIAL PEAK-LOAD DATA
Node
Demand
(MW)
Node
Demand
(MW)
Node
Demand
(MW)
Node
Demand
(MW)
2 1750 46 -72.8 79 100 138 100
4 100 47 100 80 5000 139 902.3
5 2350 48 121 82 -66.6 140 100
6 100 50 320 83 -339 141 3191
8 239 51 237.2 85 610 142 204.2
9 100 54 138 100 -43.3 143 377.4
10 139.7 55 807.8 101 210.4 144 100
11 100 57 117 102 50 145 3098
12 90 58 121 103 100 148 100
13 100 59 887.7 104 305 149 100
15 100 60 -2771 105 27.5 150 3118
16 793.4 61 401 106 8.01 151 1230
17 840 62 205.2 107 265 152 406
18 100 63 -129 108 55.6 154 1066
19 617 65 100 109 777.6 155 457.7
30 100 66 1700 110 40 156 33.9
31 4400 67 160 111 -189 157 148
34 3600 68 -67.5 112 100 158 116.1
35 100 69 -44.2 113 148 159 100
36 100 70 100 115 -0.7 160 -62
37 -1862 71 3137 116 100 161 255
40 100 73 -1525 117 884 162 100
41 135 75 2584 118 100 164 31.6
43 100 76 3200 119 5661 165 141.2
44 2053 77 100 136 856 166 379
45 100 78 3500 137 175 167 185
86
TABLE 18.
GENERATOR MAXIMUM CAPACITY AND MARGINAL COST DATA
Node
Max Capacity
(MW)
Marginal Cost
($/MW)
Node
Max Capacity
(MW)
Marginal Cost
($/MW)
4 941 17 70 1301 10
6 1233 14.9 77 5446 13.5
9 3323 13.5 79 9950 5.35
11 3154 17.3 103 900 5.6
13 1690 16.4 112 1057 41.139
15 4062 5.35 116 914 41.792
18 1132 16.2 118 3649 35.262
30 4684 8.7 138 1156 34.505
35 4716 16.4 140 3195 41.792
36 2187 17.3 144 2253 10.4
40 200 8.1 148 2240 13.8
43 325 41.1 149 3385 13.3
45 1780 14.1 159 2220 38.11
47 110 9.9 162 685 15
65 4477 16.7
87
TABLE 19A.
CIRCUIT DATA FOR 179-BUS POWER SYSTEM
i j IC S n
ij
f
ij
max
i j IC S n
ij
f
ij
max
5 160 128.57 7.30 1 900 37 56 38.26 59.95 1 2000
3 8 115.80 50.30 1 1200 37 64 12.46 628.93 2 2000
8 17 131.94 188.68 1 900 42 58 7.85 23.28 1 350
17 5 130.87 9.09 1 900 48 62 4.91 89.61 2 350
12 20 29.68 157.73 1 2000 50 42 9.02 29.22 2 350
20 21 30.06 55.43 1 2000 50 57 1.86 273.22 1 350
21 14 31.45 157.73 1 2000 50 58 2.55 170.65 1 350
12 22 89.92 84.18 1 2000 48 55 7.40 63.17 2 350
22 23 90.27 17.05 1 2000 39 46 14.91 29.89 1 350
23 19 89.80 84.18 1 2000 39 48 9.56 26.32 1 350
14 24 72.62 121.07 1 2000 39 59 10.99 21.38 1 350
24 25 73.06 23.56 1 2000 39 60 9.53 29.22 1 350
25 19 74.15 121.07 1 2000 48 46 5.82 230.41 1 350
14 26 80.18 55.71 1 2000 48 59 3.15 103.41 3 350
26 27 80.58 20.17 1 2000 48 60 1.41 254.45 3 900
27 139 80.61 55.71 1 2000 75 78 124.03 44.29 1 2000
16 19 130.79 104.17 2 2000 75 76 121.08 30.27 1 2000
7 28 58.40 245.10 1 2000 75 73 129.40 71.17 1 2000
28 29 58.91 23.87 1 2000 78 74 99.18 48.33 1 2000
29 14 58.95 163.40 1 2000 78 76 124.60 43.18 2 2000
31 32 130.53 14.29 1 2000 80 78 115.63 121.95 2 4000
33 34 76.10 50.00 1 350 68 71 0.43 812.71 2 350
52 63 19.29 12.65 1 350 69 72 1.16 3333.33 2 2000
53 63 20.54 12.65 1 350 69 76 115.04 222.97 2 2000
55 41 2.64 138.31 1 350 82 76 103.72 51.29 3 2000
55 58 6.69 80.39 2 350 82 87 47.71 135.69 1 2000
57 42 7.40 32.53 1 350 87 88 48.27 79.18 1 2000
57 54 4.19 97.56 2 350 88 86 49.88 96.53 1 2000
57 58 4.23 84.10 1 350 83 89 32.23 72.36 1 2000
62 55 4.36 102.15 1 350 89 90 32.86 116.55 1 2000
64 49 80.08 53.08 1 2000 90 86 32.50 420.17 1 2000
41 58 4.64 186.57 1 350 82 91 44.30 78.99 1 2000
37 38 44.30 53.73 1 2000 91 92 44.87 79.18 1 2000
88
TABLE 19B.
CIRCUIT DATA FOR 179-BUS POWER SYSTEM (CONTINUED)
i j IC S n
ij
f
ij
max
i j IC S n
ij
f
ij
max
92 93 45.45 70.03 1 2000 100 117 53.48 9.90 1 350
93 94 46.02 79.18 1 2000 101 105 28.25 10.79 1 350
94 83 44.08 66.58 1 2000 105 117 67.61 4.89 1 350
82 95 44.30 78.99 1 2000 101 106 34.15 8.79 1 350
95 96 44.87 79.18 1 2000 106 117 64.14 6.21 1 350
96 97 45.45 70.03 1 2000 119 132 77.74 132.45 1 2000
97 98 46.02 79.18 1 2000 132 133 78.15 17.49 1 2000
98 83 44.08 70.77 1 2000 133 108 79.69 75.13 1 2000
81 99 115.14 18.67 1 2000 119 134 72.62 91.07 1 2000
99 84 119.01 37.50 1 2000 134 104 74.39 27.44 1 2000
111 120 48.82 100.00 1 2000 104 135 55.30 62.50 1 2000
120 121 49.38 51.23 1 2000 135 108 55.43 100.20 1 2000
121 122 49.93 100.00 1 2000 104 102 120.40 51.63 1 2000
122 123 50.48 47.19 1 2000 102 108 132.66 47.92 2 2000
123 119 45.80 100.00 1 2000 142 153 55.86 88.89 2 2000
107 104 79.81 50.38 1 2000 142 147 76.61 32.26 1 2000
107 108 121.42 68.03 1 2000 139 142 126.14 35.98 1 2000
110 107 63.02 77.10 1 2000 147 139 129.33 70.67 1 2000
114 124 34.73 100.20 1 2000 136 152 47.38 110.50 1 2000
124 125 35.35 42.77 1 2000 142 151 57.51 78.13 1 2000
125 115 34.68 150.15 1 2000 145 151 30.05 218.82 1 2000
114 126 34.73 100.20 1 2000 151 152 50.59 107.53 1 2000
126 127 35.35 42.77 1 2000 142 145 37.19 132.80 2 2000
127 115 34.68 150.15 1 2000 150 154 15.97 28.41 1 350
115 128 57.38 89.29 1 2000 137 143 5.48 38.76 1 350
128 129 57.89 29.33 1 2000 137 150 17.34 14.22 1 350
129 119 57.48 89.29 1 2000 141 143 6.72 78.74 1 900
115 130 57.38 138.89 1 2000 154 143 18.27 25.32 1 350
130 131 57.89 47.57 1 2000 146 143 18.38 18.52 1 350
131 119 57.48 277.78 1 2000 156 167 31.23 44.25 1 900
101 113 21.43 15.11 3 350 155 167 31.10 94.34 1 900
101 117 85.94 3.65 1 350 156 155 55.12 30.12 1 900
101 100 48.15 5.90 1 350 155 160 49.16 43.23 2 900
89
TABLE 19C.
CIRCUIT DATA FOR 179-BUS POWER SYSTEM (CONTINUED)
i j IC S n
ij
f
ij
max
i j IC S n
ij
f
ij
max
158 164 91.27 11.39 1 900 81 180 55.30 37.50 1 2000
155 158 89.71 17.62 2 900 180 86 67.63 42.14 1 2000
155 165 49.95 58.14 1 900 156 85 110.11 14.86 1 900
158 166 40.37 26.74 2 900 44 160 49.34 40.82 2 900
160 166 63.69 29.41 2 900 163 8 130.34 22.94 1 900
157 161 43.29 10.36 1 350 5 11 16.42 66.67 1 15000
158 165 56.81 25.51 1 900 2 3 80.90 68.49 1 2000
31 80 67.08 41.84 1 2000 16 15 1000.00 202.02 1 15000
78 66 127.94 13.51 1 2000 2 4 1000.00 57.79 1 15000
83 168 39.60 138.89 1 2000 17 18 1000.00 166.67 1 15000
168 169 40.20 42.77 1 2000 7 8 1000.00 90.91 2 15000
169 114 42.45 138.89 1 2000 8 9 1000.00 169.49 1 15000
83 170 39.60 115.74 1 2000 8 10 1000.00 72.46 2 15000
170 171 40.20 40.49 1 2000 12 13 1000.00 150.15 1 15000
171 114 42.45 138.89 1 2000 32 33 1000.00 100.00 1 15000
83 172 51.02 100.00 1 2000 31 30 1000.00 666.67 1 15000
172 173 51.57 30.96 1 2000 34 35 1000.00 500.00 1 15000
173 111 51.49 100.00 1 2000 64 63 1000.00 42.77 1 15000
108 174 39.60 106.95 1 2000 44 45 1000.00 192.31 1 15000
174 175 40.20 37.61 1 2000 66 65 1000.00 200.00 1 15000
175 153 40.03 106.95 1 2000 84 85 1000.00 138.89 1 15000
108 176 39.60 105.93 1 2000 80 79 1000.00 400.00 1 15000
176 177 40.20 37.57 1 2000 72 71 1000.00 453.51 1 15000
177 153 40.03 106.95 1 2000 68 67 1000.00 33.44 1 15000
108 178 39.60 106.95 1 2000 69 68 1000.00 110.33 1 15000
178 179 40.20 39.73 1 2000 76 77 1000.00 266.60 1 15000
179 153 40.03 119.05 1 2000 68 70 3.70 96.72 1 350
142 64 74.21 243.90 1 2000 112 113 1000.00 43.84 1 15000
139 64 124.70 39.62 2 2000 113 114 1000.00 57.48 1 15000
150 61 4.65 84.25 2 900 118 119 1000.00 223.36 1 15000
137 61 11.02 37.88 1 900 116 117 1000.00 55.10 1 15000
12 139 132.40 47.39 1 2000 117 119 1000.00 79.99 1 15000
16 136 132.68 33.70 2 2000 109 108 1000.00 70.75 2 15000
90
TABLE 19D.
CIRCUIT DATA FOR 179-BUS POWER SYSTEM (CONTINUED)
i j IC S n
ij
f
ij
max
102 103 1000.00 102.04 1 15000
153 154 1000.00 87.03 3 15000
138 139 1000.00 66.14 1 15000
147 148 1000.00 102.04 1 15000
140 141 1000.00 273.67 1 15000
144 145 1000.00 193.76 1 15000
145 146 1000.00 200.00 1 15000
52 51 1000.00 67.07 2 15000
54 51 1000.00 75.19 2 15000
56 55 1000.00 72.15 2 15000
38 48 1000.00 144.30 1 15000
42 43 1000.00 39.45 1 15000
49 48 1000.00 72.15 1 15000
48 47 1000.00 8.72 1 15000
39 40 1000.00 42.02 1 15000
60 61 1000.00 871.08 1 15000
149 150 1000.00 97.44 1 15000
5 6 1000.00 80.78 1 15000
158 159 1000.00 172.41 1 15000
164 163 1000.00 51.28 1 15000
156 157 1000.00 55.25 1 15000
161 162 1000.00 70.92 1 15000
85 36 131.54 217.39 1 900
91
CHAPTER 5
CONSIDERING UNCERTAINTY IN TRANSMISSION EXPANSION PLANNING
FOR RESTRUCTURED MARKETS
Abstract? In today?s restructured power markets, transmission planning models need
to be reformulated to include new operation rules. Traditional transmission expansion
models generally neglect the economic effect of congestion, but congestion cost has
become an important factor affecting electricity prices in deregulated markets. Moreover,
the transmission planning process now requires particular consideration of uncertainties
such as generation expansion, load growth, and generation cost given the high impact of
the deregulation on these uncertainties. In this paper, we propose a decision model for
transmission expansion planning under uncertainty. We consider the stochastic nature of
generation expansion, load growth, and fuel costs. After sampling a set of scenarios by
the mean of Monte Carlo simulation, we formulate and solve a mixed-integer non-linear
model using a hierarchical Benders decomposition approach, adding each optimal
investment plan to the set of alternative investment plans. Next, we select the best
investment plan using a multiple comparison of the best (MCB) procedure. Garver?s 6-
bus network is used to illustrate the proposed procedure. To demonstrate the adequacy of
the proposed model, we adopt a 179-bus power network based on the Western Electricity
Coordinating Council (WECC) system.
92
Index Terms? Benders decomposition, economic transmission planning, mixed-
integer nonlinear programming, Monte Carlo simulation, multiple comparisons with the
best (MCB), power transmission planning, transmission expansion planning, transmission
expansion planning under uncertainty.
93
I. NOMENCLATURE
The notation used in the paper is given below for quick reference.
Variables
ij
n
Number of added circuits to branch (i, j)
g Vector of generated active power
i
g
Generation at node i(MW)
r Vector of load curtailments
i
r
Load curtailment at node i(MW)
f Vector of active-power flows through the lines
ij
f
Flow in branch (i, j) (MW)
j
?
Voltage angle at bus j
Parameters
ij
c
Cost of adding a circuit to branch (i, j) ($)
i
c
Cost of generation for generator at node i($/MW)
i
?
Penalty factor associated with load curtailment at bus i
S Node-branch incidence matrix
d Vector of estimated loads
ij
?
Circuit susceptance for branch (i, j)
0
ij
?
Initial circuit susceptance for branch (i, j)
0
ij
f
Initial flow limit in branch (i, j) (MW)
ij
f
Flow limit in branch (i, j) (MW)
g
Vector of maximum generation capacity
0
ij
n
Initial number of circuits in branch (i, j)
ij
n
Maximum number of new circuits added to branch (i, j)
,py
?
Comparison/compounding coefficient at period p year y
L
Set of circuit candidates
N Set of nodes
Y Set of planning years
P Set of periods during year y
?
Probability of error
k Number of alternative investment plans
?
Indifference zone
0
n
Number of initial replications
F Number of all replications
ij
Y
Value of the chosen criterion for replication i and investment plan j.
94
II. INTRODUCTION
Once deregulation has been introduced, power markets are subject to more
uncertainties, making the planning process more challenging for transmission expansion
(De la Torre, Feltes et al. 1999), (Wong, Chao et al. 1999), (David and Wen 2001).
Transmission planners now not only have to consider the uncertainties during the existing
planning process, but also to reformulate the planning models they use to take into
account the new structure of the power markets. Given the high level of congestion in
some deregulated markets, transmission investments may be required for economic
reasons in order to alleviate this congestion in the power systems Here, an economics-
based transmission planning model that considers uncertainties in deregulated markets is
proposed. The aim is to assist planners to identify the best transmission expansion plan
for their needs by considering the significant uncertainties that affect power systems.
This chapter proposes a two-phase decision model for transmission expansion
planning under uncertainty. In the first phase, a set of alternative investment plans are
constructed using a Monte Carlo simulation approach and a multi-period transmission
expansion model is solved for each sample scenario that takes into account the operation
of the deregulated market.
These scenarios are designed to consider all the significant uncertainties involved
in the transmission planning, particularly the stochastic nature of the generation
expansion, fuel costs, and load growth. In deregulated markets, information from the
generation planners is typically restricted to the transmission planners. The new
generation capacity changes both the operation of the market and the decisions made
concerning the need for new transmission capacity. Moreover, the operation of the power
95
market is directly affected by fuel costs, which follow a stochastic process. Finally, the
need for additional power capacity is naturally affected by load growth in the power
market. Therefore, transmission planning must also consider the anticipated future
growth of the load.
Several authors have used Monte Carlo simulation techniques to consider
uncertainties in the transmission planning process (Bresesti, Gallanti et al. 2003), (Buygi,
Balzer et al. 2004), (Sanchez-Martin, Ramos et al. 2005), (Attaviriyanupap and
Yokoyama 2005). Typically, the candidate lines are identified by some kind of heuristic
that does not include the overall benefit of the plan. In this approach, the candidate
investment plans are determined by considering the entire power system to maximize the
social welfare for a given planning timeframe. The new model therefore produces
alternative investment plans that are the optimal solutions for at least one of the sample
scenarios.
In the second phase of developing this decision model, a multiple comparison
procedure is performed for these alternative investment plans. The criteria that planners
need to consider are considered and the multiple comparisons with the best (MCB)
procedure developed by Nelson and Matejcik is applied (Nelson and Matejcik 1995).
This procedure selects the best plan for the given criterion by the mean of the Monte
Carlo sampling using common random numbers (CRN).
The remainder of the paper is organized as follows. Section III presents the
methodology utilized in this paper. Section IV explains the transmission expansion
planning model used to solve each scenario in the first phase, and Section V briefly
introduces the statistical procedure used for selecting the best investment plan. Section VI
96
illustrates the decision model with two numerical case examples The proposed procedure
is explained with Garver?s 6-bus network and a 179-bus power network based on the
Western Electricity Coordinating Council (WECC) system is then examined to show the
adequacy of the proposed model. The study and its results are summarized in Section VII.
III. METHODOLOGY
The best investment plan is selected according to the criteria of the transmission
planner in two phases. The goals of the two-phase decision model are:
1. To identify alternative investment plans, and
2. To select the best investment plan.
The first phase of this decision model identifies a series of alternative investment
plans, which are based on the number of circuits added to each line. Fig. 11 shows the
procedure followed in the first phase. First, the most significant uncertainties are
identified and the associated probability distributions determined, taking into account the
stochastic nature of generation expansion, load growth, and fuel cost. A scenario is then
sampled from the probability distribution functions of the previously determined random
variables and the Transmission Expansion Planning (TEP) model presented in the
following section is solved for this scenario. The TEP minimizes the total investment cost
and the redispatch cost out to the planning horizon for each scenario. To compare
operation and investment costs, the equivalent value of costs/savings relative to the
investment for the planning timeframe is calculated. This approach makes it possible to
consider least-cost dispatch, as well as an economic analysis of the transmission
investment. Finally, it is necessary to ensure that the optimal solution of this TEP model
is added to the set of alternative investment plans. When a sufficient number of scenarios
97
has been solved, the second phase is initiated.
Identify the uncertainties
Determine the probability
distributions
Generate a scenario
randomly
Solve the TEP model
Add the optimum to the
alternative investment plans set
Go to 2
nd
Phase
Yes
No
Sufficient number
of scenarios?
Fig. 11. 1
st
Phase: Identify the alternative investment plans
The multi-period TEP model provides an optimal investment plan for each
scenario. It considers the entire power system, rather than taking into account only a
small number of predetermined candidate lines. Using this approach facilitates the
process of identifying a robust investment plan that optimizes the power network as a
whole. When power networks are large and highly congested, optimum plans generally
call for investment in more than one line. It is even possible that in a consideration of the
overall power system, the optimum plan for the power system might require investing in
some lines that are not congested (Sozer, Park et al. 2006b). As a result, considering
98
individual transmission lines is unlikely to be sufficient to capture the overall economic
value of the investment. The proposed decision framework attempts to capture this
overall economic value.
The choice of the best investment is based on the criteria determined by the
transmission planner in the second phase (see Fig. 12) After the candidate investment
plans have been identified, a decision analysis is conducted depending on the planner?s
objectives. For each criterion selected by the planner, the Multiple Comparison with the
Best (MCB) procedure using the Common Random Numbers (CRN) approach proposed
by Nelson and Matejcik is utilized (Nelson and Matejcik 1995). Details of this procedure
are presented in Section V.
Identify a selection
criterion
Use NM procedure
Stop
Yes
No
Satisfied?
Fig. 12. 2
nd
Phase: Determine the best investment plan
The candidate investment plans may be analyzed for several criteria based on the
objectives of the planner. This research assumes the first criterion consists of the total
investment cost and the redispatch cost. If this single criterion is not sufficient to identify
the best investment plan, more criteria can be introduced. For example, the total
99
investment cost and congestion rent can be used as the second criterion. The redispatch
cost refers to the system?s cost due to congestion, namely the difference between the total
generation cost without transmission constraints and the total generation cost with
transmission constraints. Accordingly, the criterion ?total investment cost and the
redispatch cost? first applied seeks the most economic solution that will balance the total
investment cost and the total cost of power to the system. The congestion rent, however,
refers to the difference between the total payment that the load incurs and the total
payment that the generators receive. The criterion ?total investment cost and the
congestion rent? therefore takes into account both the investment cost and the payments
of the participants. These operational costs can be obtained by solving the optimum
power flow equations for each period during each year out to the horizon, then
calculating an equivalent value using the compounding coefficients presented in the
following section.
IV. THE TRANSMISSION EXPANSION PLANNING MODEL
For each of the sample scenarios, a multi-period TEP model is solved that seeks
simultaneously the most economic investment plan and the best operational conditions of
the system. The investment plan is based on a comparison of the equivalent economic
values of operational and investment costs at the beginning of the planning timeframe
(end of the construction phase). These equivalent economic values are calculated by
assuming the following decision framework: Once the decision regarding the investment
plan has been made, the construction begins immediately. All investment costs occur
during construction. Operational costs start after the construction is complete and are
calculated for each period representing significant load levels. The economic equivalent
100
values of the operational costs out to the planning horizon are calculated using the
compounding coefficients given below in (5.8).
Sozer et al. presented this model in detail for a deterministic case in (Sozer, Park
et al. 2006a). The mathematical form of this mixed-integer nonlinear problem is as
follows:
()
()
,, ,,
,
min
py py py py
ij ij i i i i
yYpP iN yYpP iNij L
wcn cg r???
?? ? ?? ?
?
=+ +
??????
(5.1)
subject to
()
,,, , ,py py py py py
i
?++=Sf g r d
( ),, ,ij L p P y Y? ?????
(5.2)
()()
0
0
py py py
ij ij ij ij i j
fn?? ? ??+ ? = ( ),, ,ij L p P y Y? ????? (5.3)
()()
,0 ,
0
py py
ij ij ij ij ij
ffnf ??+ ? ( ),, ,ij L p P y Y? ????? (5.4)
,py
??0 gg ,p PyY?? ?? (5.5)
,,py py
??0r d ,p PyY?? ?? (5.6)
0
ij ij
nn??
()
,ij L?? (5.7)
where p P? corresponds to the period p during the year yY? . The objective function
contains the present value of the investment and the present value of the total generation
cost during the planning timeframe. The penalty factors
i
? for load curtailment are
assigned sufficiently large values to nullify the load curtailment value at the optimal
solution. The constraints are the same as those of the traditional transmission expansion
model (Romero, Monticelli et al. 2002)-(Romero and Monticelli 1994); however, there is
a new set of constraints for all PY? periods during the planning timeframe. Under the
continuous operational cash flows and continuous compounding assumptions, we
calculate the comparison coefficients as shown in (5.8) for each period corresponding to
each period p of the year y.
101
,
8760
e
s
p
p y ry rt
p
eedt?
?
=
?
(5.8)
where p
s
and p
e
are the starting and the ending time of the period p during year y,
respectively.
To solve the proposed TEP models, we apply a three-phase Benders
decomposition algorithm. The theory of the Benders decomposition and the hierarchical
approach can be found in (Romero and Monticelli 1994; Floudas 1995) and the detailed
application for this multi-period model is explained in (Sozer, Park et al. 2006a).
Although an optimal solution is not guaranteed with this heuristic approach, it provides
very good and practical solutions for this mixed-integer nonlinear program.
V. NELSON AND MATEJCIK?S MULTIPLE COMPARISON WITH THE BEST PROCEDURE
The multiple comparison procedures aim to select the best investment plan among
the alternatives. The Nelson-Matejcik (NM) procedure requires two-phase sampling
using CRN and not only identifies the best of the alternatives, but also provides MCB
confidence intervals. This procedure guarantees a probability of correct selection greater
than or equal to 1- ? under the stated assumptions by the authors. The detailed
description and the demonstrations can be found in (Nelson and Matejcik 1995) and
(Goldsman and Nelson 1994). Nelson and Matejcik showed that this procedure is robust
even when the underlying assumptions are approximately satisfied (Nelson and Matejcik
1995). The NM procedure with MCB using CRN used for the best transmission
investment plan selection is as follows:
102
1. Specify the indifference zone, ? , the error probability, ? , and initial number of
replications,
0
n . Let
0
1,( 1)( 1),0.5kkn
gT
?
?? ?
= (see (Hochberg and Tamhane 1987),
Appendix 3, Table 4), where k is the number of alternative investment plans.
2. Take
0
n independent and identically distributed sample
0
1
,,
iin
YYK from each
alternative investment plan i.
ij
Y represents the value of the chosen criterion for
investment plan i and replication j.
3. Compute the approximate sample variance of the difference of the sample means
()
()( )
0
2
112
0
2
11
nk
ij i j
ij
YYYY
S
kn
?? ?
==
??+
=
??
??
4. Compute the final sample size
()
{ }
2
0
max ,FngS?
? ?
=
? ?
5. Take
0
Fn? additional independent and identically distributed observations from
each system, using CRN across systems.
6. Compute overall sample means for 1, 2, ,ik= K by
1
1
F
iij
j
YY
F
?
=
=
?
7. Select the investment plan with smallest
i
Y
?
as the best.
8. Simultaneously form the MCB confidence intervals for 1,2, ,ik= K by
103
( )
min
ij
ji
??
?
??
( ) ( )
min , min
ij ij
ji ji
YY YY??
? +
?? ??
??
? ?
?? ? ? +
? ?
? ?
where () {}max 0,x x
+
= and () {}min 0,x x
?
?= .
This procedure can be repeated for any desired criteria. For illustrative purposes,
the best investment plan is selected based on the total investment cost and redispatch cost
for the Garver?s 6-bus network. For the WECC 179-bus network, the model also
differentiates between investment plans based on the total investment cost and congestion
rent.
VI. ILLUSTRATIVE EXAMPLES
To show how the model operates, consider two power networks: 1) Garver?s 6-
bus system, which illustrates the characteristics of the decision model; and 2) the WECC-
based 179-bus power system, which shows the applicability of the proposed approach.
The Benders decomposition algorithm is coded using AMPL software with a CPLEX 9.1
solver, which solves each scenario for the larger multi-period 179-bus model in about 60
to 90 minutes. This section explains the general process, followed by detailed
explanations for each example.
A. Data for the Model
The collection of data starts with the determination of the planning timeframe for
the network. For illustrative purposes, a five-year planning time is assumed for both the
Garver?s 6-bus and the WECC 179-bus networks. First, all data out to the planning
horizon are forecast related to the load, the generation, and the transmission lines. In
order to estimate the operational costs, seasonal-load profiles are used for both examples.
104
This illustrative profile consists of four 3-month periods for each year corresponding to
fall, winter, spring, and summer. Additional assumptions for these load profiles are as
follows: the peak-load occurs during summer; during the winter season, the load level is
90% of the peak-load; and for the fall and spring seasons, the load is 70% of that in the
peak-load season. After the load duration data is determined, it is possible to calculate the
discount coefficients using (5.8). TABLE 20 shows the discount coefficients for the
periods described above assuming a 6% discount rate, selected arbitrarily. Here, all total
costs are calculated using these coefficients, which give the equivalent value at the
beginning of the planning horizon.
TABLE 20.
DISCOUNT COEFFICIENTS FOR FOUR-SEASON LOAD PROFILE
,p y
? Fall Winter Spring Summer
1 4,219 2,109 4,219 2,174
2 3,974 1,987 3,974 2,047
3 3,742 1,871 3,742 1,928
4 3,524 1,762 3,524 1,816
5 3,319 1,659 3,319 1,710
As stated, the planners determine the existing and candidate transmission branch
data prior to implementing the model. The cost for each transmission line is assumed to
be the present value of the total construction costs at the beginning of the planning
period, which is the operation start date of the planned network.
This decision model considers the stochastic nature of three variables. First, the
load growth per year is assumed to have a uniform distribution within the interval [0, 4%]
for illustrative purposes. Four random numbers are sampled within this interval for each
scenario, corresponding to the load growth each year during the planning timeframe. An
expected value of 2% per year for the load growth is realistic for today?s networks (Hirst
105
and Kirby 2001). The same distribution is assumed for both examples. Second, the
planner is assumed to know, or to at least be able to estimate, the location and time of the
generation expansion. However, the number of units to be expanded is assumed to follow
a uniform distribution for each generator. The third random variable is the fuel cost and a
lognormal distribution is assumed for different fuel types in the network and the marginal
cost of each generator is calculated using
,py
iit
cHP=? , where
i
H is the heat rate of
generator i, and
,py
t
P is the price of fuel type t at period p and year y. New generator
nodes can be assumed during the planning timeframe, but for the sake of simplicity
expansion of only the existing generators is assumed here.
B. Garver?s 6-bus Power Network
This simple network, shown in Fig. 13, is used to illustrate how the proposed
approach. All the related data can be found in the literature (Romero, Monticelli et al.
2002). The load profile presented in the previous section is used.
Bus 5
Bus 1
Bus 2
Bus 3
Bus 6 Bus 4
Fig. 13. Garver?s 6-bus Network
TABLE 21 shows the generation data, where generators 1 and 3 are operated by
gas and generator 6 is a coal generator. The marginal cost of the generators for each year
106
is estimated using data provided by the Energy Information Administration (EIA 2005).
Average gas and coal prices are assumed to be lognormally distributed. The mean and
standard deviations of gas prices are assumed to be $5.3/MMBtu and $1.32/MMBtu,
respectively. The mean and standard deviations of coal prices are assumed to be 1.5 and
0.1, respectively.
TABLE 21.
GENERATION DATA
Node Capacity (MW)
Heat rate
(Mbtu/MW) Type
1 150 2.83 Gas
3 360 2.26 Gas
6 600 6.66 Coal
Here, generators 1 and 3 are assumed to expand their capacity in year three. The
number of units added is assumed to have discrete uniform distributions within the
intervals [0,10], and [0,5], respectively.
Given all the required data for the first phase of the decision model, 100 scenarios
for the Garver?s 6-bus system were generated and solved with the multi-period TEP
model using the Benders decomposition method. The total number of optimal investment
plans for this network was found to be seven. The frequency of each optimal investment
plan is presented in TABLE 22. The investment plan with a cost of $270,000 is the most
frequent best investment for this scenario, with a score of 32 over 100. Other investment
plans with high frequency include $240,000, 261,000, $268,000, and $270,000. The lines
receiving investment for each of the plans are presented in TABLE 23. By analyzing this
table, the planner is able to estimate the minimum required investment. For instance, an
investment in line 2-6 is required by all of the plans and it is receives an additional 4
circuits on average. On the other hand, the decision to invest in line 2-3 is at the
107
discretion of the investor. For this example, the best investment is selected in the second
phase of the decision model according to the minimum investment cost and the
redispatch cost criterion.
TABLE 22.
THE SET OF OPTIMUM PLANS FOR GARVER?S 6-BUS SYSTEM
No
Investment Cost
($1000)
Frequency
1 240 20
2 261 11
3 268 26
4 270 32
5 279 3
6 281 6
7 288 2
Total 100
TABLE 23.
REQUIRED NUMBER OF CIRCUITS FOR OPTIMAL INVESTMENT PLANS
Link 240 279 288 268 270 261 281 Min Max Average
2 3 1 0 1 0 1 0 1 0 1 0.57
2 5 0 0 0 0 0 1 0 0 1 0.14
2 6 4 3 4 4 5 4 4 3 5 4.00
3 5 2 1 2 2 2 1 1 1 2 1.57
3 6 0 1 1 1 0 0 0 0 1 0.43
4 6 2 2 2 2 2 3 2 2 3 2.14
5 6 0 1 0 0 0 0 1 0 1 0.29
The second phase of this approach applies the NM procedure described above
with the indifference zone ? = 14 (thousand dollars), the error probability ? = 5%, and
an initial number of replications
0
n = 8. This value for the indifference zone was chosen
based on the assumption that a total of ten replications would be reasonable for this
example by trial and error. The decision maker selects these values according to their
expert knowledge or experience. Each replication consists of 10 randomly- generated
108
scenarios, where
0.95
6,42,0.5
2.37gT==. The sum of the investment cost and the redispatch
cost are the objective for the analysis. Each replication value
ij
Y is the average total cost
of investment and redispatch cost for investment plan j. After all eight replications are
completed, the approximate sample variance is calculated for the difference of the sample
means,
2
480.77S = , and the required number of replication, F = 10. TABLE 24 shows
the results with the NM procedure for all 10 replications. The traditional notation
i
Y
?
is
used for the overall average of the total investment cost and the redispatch cost over 10
replications for the investment plan i. The results suggest that the investment plan with a
total cost of $270,000 is the best among the alternatives for the given criterion. The MCB
confidence intervals show how much each investment plan is expected to be better/worse
than the best investment plan, excluding itself. For instance, for the investment plan with
$270,000 total cost, the criterion value will be $0 to $30,000 better than the others, with a
confidence level of 95%.
TABLE 24.
MCB RESULTS FOR GARVER?S NETWORK
Total Investment Cost
($1000) i
Y
?
($1000)
Lower MCB
Limit
($1000)
min
ijij
YY
? ??
?
($1000)
Upper MCB Limit
($1000)
240 293.12 0.00 22.09 36.09
261 357.87 0.00 86.84 100.84
268 290.99 0.00 19.96 33.96
270 271.03 -30.99 -16.99 0.00
279 360.92 0.00 89.89 103.89
281 301.05 0.00 30.02 44.02
288 288.02 0.00 16.99 30.99
With this simple example, it is possible to identify the best investment plan for
Garver?s 6-bus network. Since one of the investment plans is significantly better than the
109
others for the given criterion, the procedure can be stopped. For more complicated real-
world systems, repeating the NM procedure with more criteria might be useful. The
following section illustrates the operation of the proposed decision model with a larger
power network.
C. WECC 179-bus Power Network
The WECC 179-bus system is an equivalent reduced system with 104 demand
buses and 29 generator buses. In order to apply the proposed model, it was necessary to
estimate some of the required data. Only peak-load dispatch data with load and
generation amounts was available, along with the voltage levels of the transmission lines.
The load data is assumed to be the peak-load for the first year of the planning timeframe.
The maximum capacities of the generators are calculated by arbitrarily assigning used-
capacity percentages and the generator types assigned based on their estimated
geographical locations. The capacities and investment costs of the transmission lines are
based on the voltage level and the distance estimates of the nodes. Due to space
limitations, the data are not given here, but are available by sending a written request to
the author.
To take into account the uncertainties the same load growth distribution is
assumed as that used earlier for the WECC system. To select the generators to be
expanded, a simple heuristic is applied: calculate the ten generator nodes that have the
largest expected cost-price difference and assume that all of these generators have
expected expansion values that are uniformly distributed within the interval [0, 20%].
The marginal cost of generation is calculated as described earlier for the fuel cost
distributions, except for hydro generators, as shown in TABLE 25. For hydro generators,
110
the marginal cost of power is assumed to have a lognormal distribution with a mean of
$10/MW and a standard deviation of $1/MW.
TABLE 25.
THE PARAMETERS FOR FUEL COSTS WITH A LOGNORMAL DISTRIBUTION
Coal Gas Oil Nuclear Hydro
Mean 1.5 5.15 6.53 0.5 10
Standard Deviation 0.01 0.15 0.15 0.01 1
Given the lengthy computation time, only 50 scenarios are simulated for the first
phase. TABLE 26 shows the list of 18 investment plans found for the 50 scenarios by
solving the multi-period TEP problem using Benders decomposition method. The most
frequently occurring plan calls for an investment of $324.0 million, but since the number
of alternative solutions is relatively high it is necessary to conduct a careful analysis
regarding the decision maker?s preferences.
TABLE 26.
THE SET OF OPTIMUM PLANS FOR WECC 179-BUS POWER SYSTEM
No
Investment Cost
($million)
Frequency No
Investment Cost
($million)
Frequency
1 265.0 1 10 337.6 1
2 273.4 7 11 389.2 1
3 276.0 1 12 401.4 1
4 278.1 1 13 405.0 7
5 283.3 1 14 407.5 1
6 284.5 1 15 447.1 2
7 324.0 9 16 455.6 8
8 324.7 1 17 532.9 1
9 326.6 4 18 583.5 2
TABLE 27 shows the required number of circuits for each optimum plan. The
highlighted branches are typically included in the investment plans. These branches are
111
required in order to alleviate high congestion in the power system.
TABLE 27.
REQUIRED NUMBER OF CIRCUITS FOR OPTIMAL INVESTMENT PLANS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
265.0 273.4 276.0 278.1 283.3 284.5 324.0 326.6 337.6 389.2 401.4 405.0 405.0 407.5 447.1 455.6 532.9 583.5 min max
33 34 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
41 58 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
50 58 1 0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1
68 70 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
68 71 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
78 66 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1
85 36 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1
136 152 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
137 61 1 2 2 2 1 3 2 2 3 2 2 2 2 2 1 2 2 2 1 3
137 143 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
141 143 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
146 143 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 3 4
151 152 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1
154 143 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
The second phase of the approach samples new scenarios for each of the
alternative investment plans and compares the investment plans for the total investment
cost and redispatch cost, as well as the total investment cost and congestion rent.
To apply the NM procedure for the total investment cost and the redispatch cost,
assume the indifference zone ? = 7.2 (million dollars), the error probability ? = 5%,
and the initial number of replications
0
n = 5. Each replication consists of 10 random
scenarios, as before, and
0.95
17,68,0.5
2.67gT==. After the initial five replications, the
approximate sample variance of the difference of the sample means is
2
71.1S = . The
indifference zone is chosen by trial and error, assuming that a total of ten replications
would be sufficient for this large example. Accordingly, the required number of
replications, F, is determined to be 10, which requires five more replications. TABLE 28
112
shows the results for the NM procedure considering total investment costs and the
redispatch cost of the systems. In this case, there are five investment plans that have
mean averages that are not significantly different, with a probability of 95%. These are
the investment plans with a total cost of 324.0, 326.6, 337.6, 447.1, and 455.6 million
dollars, highlighted in TABLE 28. Further analysis is required to select the best
investment plan according to the decision maker?s preferences.
TABLE 28.
MCB RESULTS FOR WECC 179-BUS NETWORK CONSIDERING TOTAL INVESTMENT AND
REDISPATCH COST
Total Inv. Cost
($million)
i
Y
?
($million)
Lower MCB Limit
($million)
min
ijij
YY
? ??
?
($million)
Upper MCB Limit
($million)
265.0 1009.19 0.00 10.65 17.85
273.4 1005.74 0.00 7.21 14.41
276.0 1006.28 0.00 7.75 14.95
278.1 1010.49 0.00 11.96 19.16
283.3 1018.46 0.00 19.93 27.13
284.5 1010.76 0.00 12.23 19.43
324.0 998.53 -7.30 -0.10 7.10
324.7 1014.03 0.00 15.50 22.70
326.6 998.63 -7.10 0.10 7.30
337.6 1003.31 -2.42 4.78 11.98
389.2 1019.83 0.00 21.30 28.50
401.4 1014.15 0.00 15.61 22.81
405.0 1010.68 0.00 12.15 19.35
407.5 1011.53 0.00 12.99 20.19
447.1 1000.00 -5.73 1.47 8.67
455.6 1000.80 -4.93 2.27 9.47
532.9 1042.35 0.00 43.82 51.02
583.5 1033.12 0.00 34.59 41.79
The analysis is continued by comparing all 18 investment plans for the total
investment cost and the congestion rent, applying the NM procedure and assigning an
indifference zone ? = 27 (million dollars), the error probability ? = 5%, and initial
number of replications
0
n = 5. Although expert opinion can be used to determine the
113
indifference zone, a trial and error method is used with a total of ten replications. Again,
with each replication consisting of 10 randomly-generated scenarios as before,
0.95
17,68,0.5
2.67gT==. The approximate sample variance of the difference of the sample
means is
2
1020.6S = . The required number of replications, F, is 10, which requires five
more replications. The results are illustrated in TABLE 29.
TABLE 29.
MCB RESULTS FOR WECC 179-BUS NETWORK CONSIDERING
TOTAL INVESTMENT AND CONGESTION RENT
Total Inv. Cost
($million)
i
Y
?
($million)
Lower MCB
Limit ($million)
min
ijij
YY
? ??
?
($million)
Upper MCB Limit
($million)
265.0 4021.42 0.00 398.51 425.51
273.4 3914.42 0.00 291.52 318.52
276.0 3878.57 0.00 255.66 282.66
278.1 3921.83 0.00 298.92 325.92
283.3 4066.77 0.00 443.87 470.87
284.5 3846.74 0.00 223.84 250.84
324.0 3709.94 0.00 87.03 114.03
324.7 3743.48 0.00 120.57 147.57
326.6 3679.36 0.00 56.46 83.46
337.6 3622.91 -83.46 -56.46 0.00
389.2 4215.67 0.00 592.77 619.77
401.4 3690.45 0.00 67.54 94.54
405.0 4075.62 0.00 452.71 479.71
407.5 4043.30 0.00 420.39 447.39
447.1 3980.51 0.00 357.60 384.60
455.6 3907.84 0.00 284.94 311.94
532.9 3913.97 0.00 291.07 318.07
583.5 3762.95 0.00 140.04 167.04
The investment plan that has the minimum expected value of the total investment
cost and the congestion rent is the plan with an investment cost of $337.6 million.
Taken together with the previous results, this indicates that the investment plan
requiring $337.6 million total investment cost will perform similarly to the other
114
alternatives, while at the same time decreasing both the redispatch cost and, most
importantly, the congestion rent. As shown in TABLE 29 the $337.6 million investment
plan is expected to be better than the others within the interval [$0.0, $83.5] with a
probability of error of 5%.
VI. CONCLUSION
This chapter outlines a two-phase decision model taking into account uncertainty
for economics-based transmission expansion planning. In the first phase, a number of
scenarios are generated using Monte Carlo simulation techniques and the optimum
investment plan is obtained for each scenario. The optimization uses a multi-period
planning approach; when congestion occurs frequently, at several load levels during the
year, a multi-period model is more appropriate. The model provides an optimal
investment plan by considering the entire power system from the system welfare
perspective, rather than evaluating only a small number of pre-determined candidate
lines. In the second phase, candidate investment plans are compared using a multiple
comparison of the best (MCB) procedure. The results for the case studies show that the
proposed decision model is sufficiently flexible to handle different sized networks with
different load and/or generation distributions.
115
CHAPTER 6
CONCLUSION
The lack of transmission investment and the need for economic transmission
planning are becoming more evident every day in today?s restructured markets. However,
the decisions driving new transmission investment involve several conflicting
considerations. Not only the new structure of the markets but also the nature of the
transmission planning process challenge the planners. This research was designed to
provide an accurate and easy-to-use guideline for both systems operators and the
participants in the nation?s power systems.
This research approached the issue of transmission expansion planning from a
system welfare perspective, making use of a model that addressed the problem by
considering both the total investment cost and congestion costs in terms of an objective
function. The resulting decision framework makes it possible to calculate equivalent
values of the operational costs, thus providing an environment that makes it easy to
understand and to compare different investment plans. Such a framework is necessary in
order to be able to compare alternatives for power systems. Finally, a decision model
incorporating the uncertainties of the transmission planning was evaluated. Each step of
this research was summarized in a paper.
In Chapter 3, the first paper included in this manuscript, an economics-based
transmission expansion planning model was proposed. Using a multi-period planning
116
approach, the power system was optimized from the system welfare perspective. The
proposed multi-period model overcomes the drawbacks of the one-period model by
considering continuous operation of the market during the planning timeframe. When
congestion is a frequent event, occurring with several load levels during the year, a multi-
period model is more appropriate. The proposed planning model defines discount
coefficients that facilitate the comparison of short-term operating costs to long-term
investment costs, allowing system operators to accurately predict the necessary level of
transmission expansion for a particular power market. The results for the case studies
showed that the proposed model is flexible enough to handle different sized networks
with different load and/or generation scenarios. With the proposed multi-period model,
the redispatch cost and the investment cost are minimized very effectively and a more
efficient network in terms of both the dispatch cost and the prices is then obtained. The
proposed model should be followed by an analysis of the optimum solutions from the
perspectives of the different market participants and also a comparison of any alternative
solutions. Such a study is the subject of the second paper of this dissertation.
The second paper, provided as Chapter 4, examined a multi-period decision
framework for transmission expansion planning designed to alleviate congestion. Two
types of economics-based transmission expansion planning approaches were presented.
First, an optimum investment strategy was defined by modeling transmission expansion,
as in the first paper. This was followed by the definition of a market-based approach that
can be used to determine the individual expansion value for each line in a network.
Moreover, several additional measures were defined to enable planners to compare
different investment scenarios under this decision framework. The defined discount
117
coefficients ensure that equivalent values for all operational costs occurring during the
planning horizon are calculated and that these values are directly comparable to the
investment costs. Since all the financial information is presented in the same terms, a
valid comparison is therefore possible. A realistic 179-bus power system was used to
demonstrate the applicability of this decision framework, and different approaches were
used to calculate several network measures for comparison purposes. Both a
mathematical programming approach that considers the entire power system from the
system welfare perspective and a market-based heuristic approach that considers
individual expansion values of each line were used. The results revealed that a
consideration of the entire system is likely to result in a more effective investment plan.
In the final paper of this research, Chapter 5, a two-phase decision model under
uncertainty was proposed for economics-based transmission expansion planning. In the
first phase of the model, its optimization from the system welfare perspective is
performed using a multi-period planning approach. A number of scenarios are generated
using Monte Carlo simulation techniques and the optimum investment plan is obtained
for each scenario. The second phase of the model compares the candidate investment
plans using a multiple comparison of the best procedure. The model therefore provides an
optimal investment plan after considering the entire power system from the system
welfare perspective, rather than taking into account only a small number of pre-
determined candidate lines. The results for the case studies show that the proposed
decision model is flexible enough to handle different sized networks with different load
and/or generation distributions.
The main contribution of this research is to provide a multi-period decision
118
framework that facilitates both the modeling process and the subsequent comparison of
the candidate transmission plans that are produced. The proposed mathematical model is
flexible enough to handle complex load and generation scenarios, and different size
power networks. All of the power networks examined, namely Garver?s 6-bus, the
Brazilian 46-bus, and the WECC 179-bus networks, were solved in acceptable
computational times with the Benders decomposition method. The flexibility of the
model is also clear when the uncertainties of the transmission planning was introduced
and a decision model was developed for this study.
Another important contribution is that this research provides valuable guidance
for all the participants of the power systems. Taking into account the overall optimization
of the system, the proposed approach provides an investment plan that considers the
entire network. Expert predictions were applied in order to estimate future power
requirements to determine the data for this long-term planning model. Given that the
results are based on estimates of a very volatile market, further analysis of the solutions
obtained should be considered.
This research provides a valuable new tool for economics-based transmission
investment decisions, and a natural extension of the model would be to include a
consideration of reliability constraints. Because of the laws that govern the transmission
grid, any changes in the transmission grid will effect both the reliability and the
congestion of the system. Here, the models were solved assuming that all the reliability
criterion had already been met, thus by-passing this aspect of the transmission grid for
simplicity. However, often congestion serves as a predictor for future reliability problems
of the power grid. Accordingly, future research should investigate the interdependence of
119
the reliability and the congestion of the power system.
Furthermore, although this research examined the optimization of investment
plans to alleviate congestion, the cost allocation was not discussed. The beneficiaries
analysis proposed in the second paper could be used as a basis for determining who
should/would pay for a specific investment plan. Given the rapidly changing transmission
policies of the Federal Energy Regulatory Council, an analysis based on the proposed
decision model could be a valuable tool for policy makers seeking to determine an
equitable cost allocation procedure.
Finally, the merchant transmission investments that are made by investors aiming
to recover their costs using the assigned financial transmission rights (FTR) can be
incorporated into the economics-based transmission expansion planning process. The
proposed framework also allows merchant investors to examine and validate particular
transmission investments. Future extensions of this research may also include an
investigation of the FTR allocation and cost recovery processes for merchant investors.
120
BIBLIOGRAPHY
Al-Saba, T. and I. El-Amin (2002). "The application of artificial intelligent tools to the
transmission expansion problem." Electric Power Systems Research 62(2): 117-
126.
Alguacil, N., A. L. Motto, et al. (2003). "Transmission expansion planning: a mixed-
integer LP approach." Power Systems, IEEE Transactions on 18(3): 1070-1077.
Attaviriyanupap, P. and A. Yokoyama (2005). "Transmission expansion in the
deregulated power system considering social welfare and reliability criteria."
Transmission and Distribution Conference and Exhibition: Asia and Pacific, 2005
IEEE/PES: 1-6.
Binato, S., G. C. de Oliveira, et al. (2001). "A greedy randomized adaptive search
procedure for transmission expansion planning." Power Systems, IEEE
Transactions on 16(2): 247-253.
Binato, S., M. V. F. Pereira, et al. (2001). "A new Benders decomposition approach to
solve power transmission network design problems." Power Systems, IEEE
Transactions on 16(2): 235-240.
Braga, A. S. D. and J. T. Saraiva (2005). "A Multiyear Dynamic Approach for
Transmission Expansion Planning and Long-Term Marginal Costs Computation."
Power Systems, IEEE Transactions on 20(3): 1631-1639.
Bresesti, P., M. Gallanti, et al. (2003). "Market-based generation and transmission
expansions in the competitive market." 1: 462-465.
Bullinger, C. D. and A. A. Shetty (2004). "Power investing: How to invest in the
electricity industry?" The Electricity Journal 17(7): 55-64.
Bush, R. (2003). The future of transmission in North America. Transmission &
Distribution World. 55: 26.
Buygi, M. O., G. Balzer, et al. (2004). "Market-based transmission expansion planning."
Power Systems, IEEE Transactions on 19(4): 2060-2067.
121
Chao, H.-P. and S. Peck (1996). "A market mechanism for electric power transmission."
Journal of Regulatory Economics 10: 25-59.Chao, H.-P. and S. Peck (1998).
"Reliability management in competitive electricity markets." Journal of
Regulatory Economics 14: 189-200.
Chen, L., H. Suzuki, et al. (2002). "Components of nodal prices for electric power
systems." Power Systems, IEEE Transactions on 17(1): 41-49.
Choi, J., A. A. El-Keib, et al. (2005). "A fuzzy branch and bound-based transmission
system expansion planning for the highest satisfaction level of the decision
maker." Power Systems, IEEE Transactions on 20(1): 476-484.
Chung, T. S., K. K. Li, et al. (2003). "Multi-objective transmission network planning by a
hybrid GA approach with fuzzy decision analysis." International Journal of
Electrical Power & Energy Systems 25(3): 187-192.
Crousillat, E. O., P. Dorfner, et al. (1993). "Conflicting objectives and risk in power
system planning." Power Systems, IEEE Transactions on 8(3): 887-893.
Da Silva, E. L., H. A. Gil, et al. (2000). "Transmission network expansion planning under
an improved genetic algorithm." Power Systems, IEEE Transactions on 15(3):
1168-1174.
Da Silva, E. L., J. M. A. Ortiz, et al. (2001). "Transmission network expansion planning
under a Tabu Search approach." Power Systems, IEEE Transactions on 16(1): 62-
68.
David, A. K. and F. Wen (2001). Transmission planning and investment under
competitive electricity market environment. Power Engineering Society Summer
Meeting, Vancouver, BC Canada, IEEE.
De la Torre, T., J. W. Feltes, et al. (1999). "Deregulation, privatization, and competition:
transmission planning under uncertainty." Power Systems, IEEE Transactions on
14(2): 460-465.
Deb, R. K. (2004). "Transmission investment valuations: Weighing project benefits." The
Electricity Journal 17(2): 55-67.
Editorial (2002). Transmission owners face big decision-Interview. Transmission &
Distribution World. 54: 68.
EIA (2005). Energy Information Administration http://www.eia.doe.gov/.
Escobar, A. H., R. A. Gallego, et al. (2004). "Multistage and coordinated planning of the
expansion of transmission systems." Power Systems, IEEE Transactions on 19(2):
735-744.
122
Fang, R. and D. J. Hill (2003). "A new strategy for transmission expansion in competitive
electricity markets." Power Systems, IEEE Transactions on 18(1): 374-380.
Finney, J. D., H. A. Othman, et al. (1997). "Evaluating transmission congestion
constraints in system planning." Power Systems, IEEE Transactions on 12(3):
1143-1150.
Fischer, W. and W. Braun (2001). Investment decisions for bulk power transmission
schemes in liberalised markets. AC-DC Power Transmission, 2001. Seventh
International Conference on (Conf. Publ. No. 485).
Floudas, C. A. (1995). Nonlinear and Mixed-Integer Optimization: Fundamentals and
Applications, Oxford University Press.
Gallego, R. A., A. B. Alves, et al. (1997). "Parallel simulated annealing applied to long
term transmission network expansion planning." Power Systems, IEEE
Transactions on 12(1): 181-188.
Gallego, R. A., A. Monticelli, et al. (1998). "Comparative studies on nonconvex
optimization methods for transmission network expansion planning." Power
Systems, IEEE Transactions on 13(3): 822-828.
Gallego, R. A., A. Monticelli, et al. (1998). "Transmission system expansion planning by
an extended genetic algorithm." Generation, Transmission and Distribution, IEE
Proceedings- 145(3): 329-335.
Gallego, R. A., R. Romero, et al. (2000). "Tabu search algorithm for network synthesis."
Power Systems, IEEE Transactions on 15(2): 490-495.
Garrity, T. (2003). "Shaping the future of global energy delivery." Power and Energy
Magazine, IEEE 1(5): 26-30.
Gil, H. A., E. L. da Silva, et al. (2002). "Modeling competition in transmission
expansion." Power Systems, IEEE Transactions on 17(4): 1043-1049.
Goldsman, D. and B. L. Nelson (1994). Ranking, selection and multiple comparisons in
computer simulations. Proceedings of the 26th conference on Winter simulation,
Orlando, Florida, United States, Society for Computer Simulation International.
Haffner, S., A. Monticelli, et al. (2000). "Branch and bound algorithm for transmission
system expansion planning using a transportation model." Generation,
Transmission and Distribution, IEE Proceedings- 147(3): 149-156.
Haffner, S., A. Monticelli, et al. (2001). "Specialised branch-and-bound algorithm for
transmission network expansion planning." Generation, Transmission and
Distribution, IEE Proceedings- 148(5): 482-488.
123
Hashimoto, S. H. M., R. Romero, et al. (2003). "Efficient linear programming algorithm
for the transmission network expansion planning problem." Generation,
Transmission and Distribution, IEE Proceedings- 150(5): 536-542.
Hirst, E. (2004). "U.S. transmission capacity: A review of transmission plans." The
Electricity Journal 17(7): 65-79.
Hirst, E. and B. Kirby (2001). Transmission planning for a restructuring U.S. electricity
industry. Consulting in Electric-Industry Restructuring, Edison Electric Institute:
45.
Hochberg, Y. and A. C. Tamhane (1987). Multiple Comparison Procedures. New York,
John Wiley and Sons.
Hogan, W. W. (1992). "Contract networks for electric power transmission." Journal of
Regulatory Economics 4: 211-242.
Hyman, L. S. (1999). "Transmission, congestion, pricing, and incentives [in electricity
supply]." Power Engineering Review, IEEE 19(8): 4-10.
Joskow, P. L. (2005a). "Transmission policy in the United States." Utilities Policy 13: 95-
115.
Joskow, P. L. (2005b). Patterns of transmission investment. Electricity Infrastructure
Investment Workshop, Paris, France.
Latorre, G., R. D. Cruz, et al. (2003). "Classification of publications and models on
transmission expansion planning." Power Systems, IEEE Transactions on 18(2):
938-946.
Leeprechanon, N., S. S. Moorthy, et al. (2001). Transmission planning in deregulated
systems: a model for developing countries. Power Tech Proceedings, 2001 IEEE
Porto, Porto Portugal.
Nasser, T.-O. (1999). "The hidden value of transmission assets." The Electricity Journal
12(5): 69-78.
Nelson, B. L. and F. J. Matejcik (1995). "Using common random numbers for
indifference-zone selection and multiple comparisons in simulation."
Management Science 41(12): 1935-1945.
Oliveira, G. C., A. P. C. Costa, et al. (1995). "Large scale transmission network planning
using optimization and heuristic techniques." Power Systems, IEEE Transactions
on 10(4): 1828-1834.
Ott, A. L. (2003). "Experience with PJM market operation, system design, and
implementation." Power Systems, IEEE Transactions on 18(2): 528-534.
124
PJM (2006). 2005 State of the Market Report. M. M. Unit.
PJM. (website: www.pjm.com).
Rau, N. S. (2002). "Transmission congestion and expansion under regional transmission
organizations." Power Engineering Review, IEEE 22(9): 47-49.
Richardson, A. B. (2003). "$27.5 billion of new transmission projects planned." Platts
Transmission and Distribution Sourcebook Fall: 10-15.
Rider, M. J., A. V. Garcia, et al. (2004). A constructive heuristic algorithm to short term
transmission network expansion planning. Power Engineering Society General
Meeting, 2004. IEEE.
Romero, R., R. A. Gallego, et al. (1996). "Transmission system expansion planning by
simulated annealing." Power Systems, IEEE Transactions on 11(1): 364-369.
Romero, R. and A. Monticelli (1994). "A hierarchical decomposition approach for
transmission network expansion planning." Power Systems, IEEE Transactions on
9(1): 373-380.
Romero, R. and A. Monticelli (1994). "A zero-one implicit enumeration method for
optimizing investments in transmission expansion planning." Power Systems,
IEEE Transactions on 9(3): 1385-1391.
Romero, R., A. Monticelli, et al. (2002). "Test systems and mathematical models for
transmission network expansion planning." Generation, Transmission and
Distribution, IEE Proceedings- 149(1): 27-36.
Roseman, E. and P. De Martini (2003). In search of transmission capitalists. Public
Utilities Fortnightly. 141: 20-25.
Rudnick, H., R. Palma, et al. (1996). "Economically adapted transmission systems in
open access schemes-application of genetic algorithms." Power Systems, IEEE
Transactions on 11(3): 1427-1440.
Sanchez-Martin, P., A. Ramos, et al. (2005). "Probabilistic midterm transmission
planning in a liberalized market." Power Systems, IEEE Transactions on 20(4):
2135-2142.
Schweppe, F. C. (1988). Spot Pricing of Electricity. Boston, Kluwer Academic.
Shahidehpour, M. (2004). "Investing in expansion: the many issues that cloud
transmission planning." Power and Energy Magazine, IEEE 2(1): 14-18.
Sozer, S., C. S. Park, et al. (2006a). "A Transmission Expansion Planning Model for
Restructured Markets." Power Systems, IEEE Transactions on submitted for
125
publication.
Sozer, S., C. S. Park, et al. (2006b). "Economic Comparison of Transmission Expansion
Plans in Deregulated Markets." unpublished.
Sozer, S., C. S. Park, et al. (2006c). "Considering Uncertainty in Transmission Expansion
Planning for Restructured Markets." Power Systems, IEEE Transactions on,
special section on "Transmission Investment, Pricing and Construction"
submitted for publication.
Wolak, F. A. (2003). Transmission Investment and Access. California's Electricity
Future: Reliability, Supply, and Cost, Stanford, CA.
Wong, W., H. Chao, et al. (1999). "Transmission planning in a deregulated environment."
Transmission and Distribution Conference, 1999 IEEE 1: 350-355.
126
APPENDIX
Sample AMPL code is provided for reference purposes in this appendix for
Garver?s 6-bus example.
# ----------------------------------------------------------
# BENDERS DECOMPOSITION FROM THE SOCIAL WELFARE PERSPECTIVE
# (using primal formulation of subproblem)
# ----------------------------------------------------------
model Garvers.mod;
data Garvers_h.dat;
problem Master_cont: Newlineadd_cont, beta, Total_Cost, Cut_Defn_cont;
problem Master_int: Newlineadd_int, beta, Total_Cost, Cut_Defn_int;
problem SubOperation_tr: gen, flow, curtaildem, operationcost,
node_balance, max_flow_limit, min_flow_limit, demandcurt;
problem SubOperation_hyb: gen, flow, nodeangle, curtaildem,
operationcost, node_balance, voltage_angle_hyb, max_flow_limit,
min_flow_limit, demandcurt;
problem SubOperation_dc: gen, flow, nodeangle, curtaildem,
operationcost, node_balance, voltage_angle, max_flow_limit,
min_flow_limit, demandcurt;
problem SubOperation_dispatch: gen, flow, nodeangle, dispatchcost,
node_balance_dis, voltage_angle, max_flow_limit, min_flow_limit;
option presolve_eps 1e-7;
param T := 4;
param GAP;
param growth default 0.02; #percent growth of the load
param opcost {BLOCKS,0..T,0..nCUT};
let nCUT := 1;
param UBD {0..nCUT};
param LBD {0..nCUT};
param skip default 0;
param phs integer;
127
param total_cost;
param sigmaby {LINKS, BLOCKS, 0..T, 1..nCUT}; ##sensitivity factor
param invcost;
param oprtcost;
param loadpayment default 0;
param genpayment default 0;
param Newlineadd {LINKS} default 0;
let phs := 1;
let UBD[nCUT-1]:= Infinity;
let LBD [nCUT-1] := 0;
let {(i,j) in LINKS} linknumber_add[i,j] := Newlineadd[i,j];
repeat while phs <= 3 {
printf "\n **************PHASE*************** %d\n\n", phs
>solution.out;
repeat {
printf "\nITERATION \t%d\t PHASE \t%d\n\n", nCUT, phs
>solution.out;
printf "\nITERATION \t%d\t PHASE \t%d\n\n", nCUT, phs ;
printf "\n SOLVING PRIMAL PROBLEM\n\n" >solution.out;
printf "\n SOLVING PRIMAL PROBLEM\n\n";
let loadpayment := 0;
let genpayment := 0;
option omit_zero_rows 1;
display linknumber_add;
for {y in 0..T} {
for {b in BLOCKS} {
let {k in NODE} demand[k] := (1 +
growth)^y*seasoncoef[b]*demandinit[k];
#display demand;
if phs = 1 then {
#printf "\n Solving SubOperation1 for %d
%s",y,b >solution.out;
solve SubOperation_tr;
#printf "\n Growth %f \n", 1-
(1.02^y)*seasoncoef[b];
#for {k in NODE} {printf "\n Gen at node
\t%d\t%f \n", k,
#sum {m in GENS }(if k
= gennode[m] then gen[m]);};
#display demand, curtaildem,
node_balance, gen, max_flow_limit, min_flow_limit, flow;
#printf " total load curtailment \t%f\t
CPU time \t%f\n",
#sum {k in NODE}
curtaildem[k],_solve_time;
#display node_balance;
128
for {(i,j)in LINKS} {let
sigmaby[i,j,b,y,nCUT] :=
flow_max[i,j]*(min_flow_limit[i,j].dual+max_flow_limit[i,j].dual)
;}
} else {
if phs = 2 then {
solve SubOperation_hyb;
for {(i,j)in LINKS:
linknumber_init[i,j] < 1}
{let sigmaby[i,j,b,y,nCUT] :=
flow_max[i,j]*(min_flow_limit[i,j].dual+max_flow_limit[i,j].dual)
;}
for {(i,j)in LINKS:
linknumber_init[i,j] > 0}
{let sigmaby[i,j,b,y,nCUT] :=
linksusc[i,j]*(nodeangle[i]-nodeangle[j])*(node_balance[i].dual-
node_balance[j].dual);}
} else {
#printf "\n Solving SubOperation2
for %d %s",y,b >solution.out;
solve SubOperation_dc;
for {(i,j)in LINKS} {let
sigmaby[i,j,b,y,nCUT] := linksusc[i,j]*
(nodeangle[i]-
nodeangle[j])*(node_balance[i].dual-node_balance[j].dual);};
#printf "\n Growth %f \n", 1-
(1.02^y)*seasoncoef[b];
option omit_zero_rows 1;
#for {k in NODE} {printf "\n Gen
at node \t %d \t%f \n", k,
#sum {m in GENS }(if
gennode[m] = k then gen[m]);};
#display demand, curtaildem,
node_balance, gen;
#display max_flow_limit,
min_flow_limit, flow;
#printf "\n";
#for {k in NODE} {printf "flow into
node\t%d\t%f\n",k,sum {(i,j) in LINKS}
#((if i = k then -1 else if j
= k then 1 else 0) *flow[i,j]);};
#printf " total load curtailment
\t%f\t CPU time \t%f\n",
#sum {k in NODE}
curtaildem[k],_solve_time;
#display node_balance;
}
}
for {k in NODE} {if curtaildem[k] <0.00001 then
let curtaildem[k] := 0;}
let opcost[b,y,nCUT]:=operationcost;
129
#display min_flow_limit;
#display max_flow_limit;
let loadpayment := loadpayment +
discount[b,y]*sum {k in NODE} (node_balance[k].dual*demand[k])/10;
let genpayment := genpayment +
discount[b,y]*sum {k in NODE} (node_balance[k].dual*gen[k])/10;
printf "\n";
}
}
#display opcost;
#display flow;
let {(i,j)in LINKS} lineaddk[i,j,nCUT]:=
linknumber_add[i,j];
let {(i,j)in LINKS} sigma[i,j,nCUT] := sum {b in BLOCKS,y
in 0..T}(discount[b,y]*sigmaby[i,j,b,y,nCUT])/10;
let invcost := 1*(sum {(i,j) in LINKS}
linkcost[i,j]*linknumber_add[i,j]);
let oprtcost :=(sum {y in 0..T, b in BLOCKS
}(discount[b,y]*opcost[b,y,nCUT]))/10;
let v[nCUT]:= oprtcost;
#let UBD := if (UBD > invcost + oprtcost) then invcost +
oprtcost else UBD;
let UBD[nCUT]:= invcost + oprtcost;
display invcost, oprtcost, loadpayment, genpayment, v[nCUT]
>solution.out;
#display LBD >solution.out;
#display UBD >solution.out;
let GAP := UBD[nCUT] - LBD[nCUT-1];
display GAP >solution.out;
#if GAP <= 0.00001 then {
# let phs := phs + 1;
# printf "\n PHASE INCREASED after
SUBPROBLEM\n\n";
# break;
#};
printf "\n SOLVING MASTER PROBLEM\n\n" >solution.out;
printf "\n SOLVING MASTER PROBLEM\n\n" ;
#display linkcost; #cost of expanding link ij
#display lineaddk ; ##lines added in iteration k
#display linknumber_max ; #max number of circuits
allowed for link ij
#display v ; #aggregated objective
function of subproblems
130
#display discount; #discount rate corresponding
to block b and year y
#display sigma ; ##sensitivity factor
if phs = 1 or phs = 2 then {
#option presolve_eps 1e-7;
#option solution_round 5;
solve Master_cont;
#option solution_precision 7;
let {(i,j) in LINKS} linknumber_add[i,j] := if
Newlineadd_cont[i,j] <-0.00000000000001
then -Newlineadd_cont[i,j] else
Newlineadd_cont[i,j];
#let {(i,j) in LINKS} linknumber_add[i,j] :=
round(Newlineadd_cont[i,j],5);
option omit_zero_rows 1;
display Newlineadd_cont >solution.out;
printf "\ninv cost %f\t sumsigma \t%f\n\n", sum
{(i,j) in LINKS}(linkcost[i,j]*Newlineadd_cont[i,j]),
sum {(i,j) in LINKS } (sigma[i,j,nCUT]
*(Newlineadd_cont[i,j]-lineaddk[i,j,nCUT])) > solution.out;
printf "\ninv cost %f\t sumsigma rounded \t%f\n\n",
sum {(i,j) in
LINKS}(linkcost[i,j]*Newlineadd_cont[i,j]),
sum {(i,j)in
LINKS}(sigma[i,j,nCUT]*(round(Newlineadd_cont[i,j],5)-
lineaddk[i,j,nCUT]))>solution.out;
display Newlineadd_cont;
printf "\ninv cost %f\t sumsigma \t%f\n\n",sum {(i,j)
in LINKS} (linkcost[i,j]*Newlineadd_cont[i,j]),
sum {(i,j) in LINKS } (sigma[i,j,nCUT]
*(Newlineadd_cont[i,j]-lineaddk[i,j,nCUT]));
display _solve_time;
} else {
option presolve_eps 1e-7;
solve Master_int;
let {(i,j) in LINKS} linknumber_add[i,j] :=
Newlineadd_int[i,j];
option omit_zero_rows 1;
display Newlineadd_int >solution.out;
printf "\ninv cost %f\t sumsigma \t%f\n\n", sum
{(i,j) in LINKS} (linkcost[i,j]*Newlineadd_int[i,j]),
sum {(i,j) in LINKS } (sigma[i,j,nCUT]
*(Newlineadd_int[i,j]-lineaddk[i,j,nCUT])) > solution.out;
display _solve_time;
};
option omit_zero_rows 0;
let LBD[nCUT]:= Total_Cost;
printf "\n UBD %f\t LBD \t%f\n\n", UBD[nCUT], LBD[nCUT]>
solution.out;
let GAP := UBD[nCUT] - LBD[nCUT];
131
display GAP >solution.out;
if oprtcost> 0.0001 or skip = 1 then {
#option display_1col 0;
let nCUT := nCUT + 1;
let skip := 0;
}
else {
let nCUT := nCUT + 1;
let phs := phs + 1;
if phs = 3 then let skip := 1;
printf "\n PHASE INCREASED after MASTER\n\n"
>solution.out;
break;
};
};
};
printf "\nOPTIMUM SOLUTION FOUND \n\n" >solution.out;
display LBD ;
display UBD ;
option omit_zero_rows 1;
display linknumber_add >solution.out;
display invcost, oprtcost, loadpayment, genpayment >solution.out;
display _total_solve_time;
display _total_solve_elapsed_time;
printf "\nOPTIMUM SOLUTION FOUND: Generation Dispatch\n\n";
param totdispatchcost default 0;
let loadpayment := 0;
let genpayment := 0;
let invcost:=0;
option omit_zero_rows 0;
display linknumber_add ;
let invcost := 1*(sum {(i,j) in LINKS}
linkcost[i,j]*linknumber_add[i,j]);
display invcost;
for {y in 0..T} {
for {b in BLOCKS} {
let {k in NODE} demand[k] := (1 +
growth)^y*seasoncoef[b]*demandinit[k];
solve SubOperation_dispatch;
option omit_zero_rows 0;
printf "\nDispatch and LMP at year \t%d\t block
\t%s:\n",y,b;
132
display demand, gen, node_balance_dis;
display max_flow_limit, min_flow_limit, flow;
#printf "\nflow into node:\n";
#for {k in NODE} {printf "%d\t%f\n",k,sum {(i,j) in LINKS}
#((if i = k then -1 else if j = k then 1 else 0)
*flow[i,j]);};
printf " total load curtailment \t%f\t CPU time \t%f\n",
sum {k in NODE} curtaildem[k],_solve_time;
let totdispatchcost:=totdispatchcost+discount[b,y]*sum{k in
NODE}(gencost[k]*gen[k])/10;
let loadpayment:=loadpayment+discount[b,y]*sum{k in
NODE}(node_balance_dis[k].dual*demand[k])/10;
let genpayment := genpayment + discount[b,y]*sum {k in
NODE}(node_balance_dis[k].dual*gen[k])/10;
printf "\n";
}
}
display invcost,totdispatchcost,loadpayment,genpayment;
133
# ----------------------------------------------------------
# BENDERS DECOMPOSITION FROM THE SOCIAL WELFARE PERSPECTIVE
# (model Garvers.mod;)
# ----------------------------------------------------------
### OPERATION SUBPROBLEM ####
set NODE:= 1..6;
set LINKS within {NODE,NODE}; #set of links
set BLOCKS; #set of block of demand in a year, seasons
param gencost {NODE} >= 0; #cost of production for generators
param genmax {NODE} >= 0; #max generation capacity
#param genmin {NODE} >= 0; #min generation capacity
param demand {NODE} >= 0; #demand
param curtailcost {NODE} >=0;
param demandinit {NODE} >= 0; #demand
param seasoncoef {BLOCKS};
param linksusc {LINKS}; #susceptance of circuit ij
param linknumber_init {LINKS}>=0; #initial number of circuits for ij
param linknumber_add {(i,j) in LINKS}; #number of new added circuits
param flow_max {LINKS}; #max flow on links
param S{NODE, LINKS}; #branch-node incidence matrix
var gen {i in NODE} >= 0, <= genmax[i]; #generation i
var flow {LINKS}; #flow on ij
var nodeangle {NODE}; #nodeangle at node i
var curtaildem {i in NODE}; #dummy generation corresponding to
curtailment at node i
# objective
#minimize operationcost: sum {i in NODE} (gencost[i]*gen[i])+ sum {i in
NODE} (curtailcost[i]*curtaildem[i]) ;
minimize operationcost: sum {i in NODE} (curtailcost[i]*curtaildem[i]);
minimize dispatchcost: sum {i in NODE} (gencost[i]*gen[i]);
# contraints
#node balance equations Kirchoff's Law
subject to node_balance {k in NODE}:
sum {(i,j) in LINKS} ((if i = k then -1 else if j = k then 1 else 0)
*flow[i,j]) + gen[k] - demand[k] + curtaildem[k] = 0;
subject to node_balance_dis {k in NODE}:
sum {(i,j) in LINKS} ((if i = k then -1 else if j = k then 1 else 0)
*flow[i,j]) + gen[k] - demand[k] = 0;
134
#power flow equations
subject to voltage_angle {(i,j) in LINKS}:
flow[i,j] - linksusc[i,j]*(linknumber_init[i,j] +
linknumber_add[i,j])*(nodeangle[i]-nodeangle[j]) = 0;
#power flow equations for hybrid formulation
subject to voltage_angle_hyb {(i,j) in LINKS: linknumber_init[i,j] >
0}:
flow[i,j] - linksusc[i,j]*(linknumber_init[i,j] +
linknumber_add[i,j]) * (nodeangle[i]-nodeangle[j]) = 0;
#line flow limits
subject to max_flow_limit {(i,j) in LINKS}:
flow[i,j] - (linknumber_init[i,j] + linknumber_add[i,j]) *
flow_max[i,j]<=0;
subject to min_flow_limit {(i,j) in LINKS}:
- flow[i,j] - (linknumber_init[i,j] +
linknumber_add[i,j])*flow_max[i,j]<=0;
#load curtailment
subject to demandcurt {k in NODE}:
0 <= curtaildem[k] <= demand[k];
### INVESTMENT MASTER PROBLEM ###
param nCUT >= 0 integer;
param linkcost {LINKS}>= 0; #cost of expanding link ij
param lineaddk {LINKS,1..nCUT}; ##lines added in iteration k
param linknumber_max {LINKS}>=0; #max number of circuits allowed for
link ij
param v {1..nCUT}; #aggregated objective function of
subproblems
param discount {BLOCKS, 0..4}; #discount rate corresponding to
block b and year y
param sigma {LINKS, 1..nCUT}; ##sensitivity factor
var Newlineadd_int {(i,j) in LINKS} integer, >=0, <=linknumber_max
[i,j]; #new lines added
var Newlineadd_cont {(i,j) in LINKS} >=0, <=linknumber_max [i,j]; #new
lines added
var beta >=0;
minimize Total_Cost:
beta;
135
subj to Cut_Defn_int {k in 1..nCUT}:
beta - 1*sum {(i,j) in LINKS} (linkcost[i,j]*Newlineadd_int[i,j])
- sum {(i,j) in LINKS } (sigma[i,j,k] *(Newlineadd_int[i,j]-
lineaddk[i,j,k]))>= v[k] ;
subj to Cut_Defn_cont {k in 1..nCUT}:
beta - 1*sum {(i,j) in LINKS} (linkcost[i,j]*Newlineadd_cont[i,j])
- sum {(i,j) in LINKS } (sigma[i,j,k] *(Newlineadd_cont[i,j]-
lineaddk[i,j,k]))>= v[k] ;
# ----------------------------------------------------------
# BENDERS DECOMPOSITION FROM THE SOCIAL WELFARE PERSPECTIVE
# (data Garvers_h.dat;)
# ----------------------------------------------------------
set LINKS := 1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6;
set BLOCKS := FS W S;
#bus data input
param: gencost genmax demandinit curtailcost :=
1 15 1.50 0.80 1000
2 0 0 2.40 1000
3 12 3.60 0.40 1000
4 0 0 1.60 1000
5 0 0 2.40 1000
6 10 6.00 0 1000;
136
#link data input
param: linkcost linksusc linknumber_init linknumber_max flow_max:=
1 2 40 2.5 1 6 1
1 3 38 2.6316 0 6 1
1 4 60 1.6667 1 6 0.8
1 5 20 5 1 6 1
1 6 68 1.4706 0 6 0.7
2 3 20 5 1 6 1
2 4 40 2.5 1 6 1
2 5 31 3.2258 0 6 1
2 6 30 3.3333 0 6 1
3 4 59 1.6949 0 6 0.82
3 5 20 5 1 6 1
3 6 48 2.0833 0 6 1
4 5 63 1.5873 0 6 0.75
4 6 30 3.3333 0 6 1
5 6 61 1.6393 0 6 0.78;
param: seasoncoef:=
FS 0.7
W 0.9
S 1;
param discount (tr): FS W S:=
0 421.9305787 210.9415504 217.3656895
1 397.3592547 198.6572708 204.7072972
2 374.2188532 187.088372 192.7860723
3 352.4260437 176.1931934 181.5590855
4 331.9023487 165.9325006 170.9859074;
param: S:=
1 1 2 -1
1 1 3 -1
1 1 4 -1
1 1 5 -1
1 1 6 -1
1 2 3 0
1 2 4 0
1 2 5 0
1 2 6 0
1 3 4 0
1 3 5 0
1 3 6 0
1 4 5 0
1 4 6 0
1 5 6 0
2 1 2 1
2 1 3 0
2 1 4 0
2 1 5 0
2 1 6 0
2 2 3 -1
2 2 4 -1
2 2 5 -1
2 2 6 -1
137
2 3 4 0
2 3 5 0
2 3 6 0
2 4 5 0
2 4 6 0
2 5 6 0
3 1 2 0
3 1 3 1
3 1 4 0
3 1 5 0
3 1 6 0
3 2 3 1
3 2 4 0
3 2 5 0
3 2 6 0
3 3 4 -1
3 3 5 -1
3 3 6 -1
3 4 5 0
3 4 6 0
3 5 6 0
4 1 2 0
4 1 3 0
4 1 4 1
4 1 5 0
4 1 6 0
4 2 3 0
4 2 4 1
4 2 5 0
4 2 6 0
4 3 4 1
4 3 5 0
4 3 6 0
4 4 5 -1
4 4 6 -1
4 5 6 0
5 1 2 0
5 1 3 0
5 1 4 0
5 1 5 1
5 1 6 0
5 2 3 0
5 2 4 0
5 2 5 1
5 2 6 0
5 3 4 0
5 3 5 1
5 3 6 0
5 4 5 1
5 4 6 0
5 5 6 -1
6 1 2 0
6 1 3 0
6 1 4 0
6 1 5 0
6 1 6 1
6 2 3 0
138
6 2 4 0
6 2 5 0
6 2 6 1
6 3 4 0
6 3 5 0
6 3 6 1
6 4 5 0
6 4 6 1
6 5 6 1;