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;