School Work

7 pages
9 views

A kernel-oriented algorithm for transmission expansion planning

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
A kernel-oriented algorithm for transmission expansion planning
Transcript
  1434 IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 15, NO. 4, NOVEMBER 2000 A Kernel-Oriented Algorithm for TransmissionExpansion Planning Javier Contreras  , Member, IEEE  and Felix F. Wu  , Fellow, IEEE   Abstract— With deregulation sweeping all over electricalsystems around the world, transmission planning has undergonedramatic changes during this decade. Centralized cost allocationmethods have become obsolete and new procedures are neededto deal with intelligent and self-sufficient players. In this paperwe study the allocation of transmission costs in a decentralizedmanner. For this purpose we have developed a multi-agentsystem that is based on a well known cooperative game theoryprocedure, the kernel. Using our approach, the agents are ableto form kernel-stable coalitions and the cost allocation procedureis performed at every step of the kernel- algorithm. A six busexample and an IEEE 24 bus case illustrate our model.  IndexTerms— Cooperativegametheory,kernel,multi-agentsys-tems, transmission planning. I. I NTRODUCTION T RANSMISSION planning has been traditionally central-izeduntilderegulationhasbeenadoptedbydifferentcoun-tries around the world.Historically, a seminal work by Garver formulated thetransmission expansion problem in mathematical notationin the early seventies [1]. During this decade, mixed-integerprogramming techniques using Benders decomposition [2]–[4], simulated annealing [5], genetic algorithms [6], and artificial neural networks [7] are among the latest contributions to thefield.However, in the new deregulated environment, new featuresrelated to transmission expansion and also connected to trans-mission pricing have been pointed out by several authors [8].In particular, economies of scale and synergies in the expansionmay become crucial in decentralized planning models.On the other hand, not only expansion plans but also fairways to split lines’ usage costs have been recently studied[9]–[11]. The MW-mile method and other embedded cost methods are currently under heavy modifications in orderto account for wheeling transactions among the users of thenetwork.Game theory has also been used to model the sharing of costsamong the users of new transmission lines. Gately modeled acentralized cooperative game theory framework where the in-vestments were shared according to the Shapley values of the Manuscript received September 23, 1999.J. Contreras is with the E.T.S. de Ingenieros Industriales, Universidad deCastilla-LaMancha,13071CiudadReal,Spain(e-mail:javier@ind-cr.uclm.es).F. F. Wu is with the Department of Electrical and Electronic Engineering,University of Hong Kong, Hong Kong (e-mail: ffwu@eee.hku.hk).Publisher Item Identifier S 0885-8950(00)10382-7. game of expansion [12]. However, this approach was not appli-cable to an environment where the players take their decisionslooking for their own benefit only.Distributed Artificial Intelligence has proved a valuable toolto aid game theory coping with multi-agent decision systemsin decentralized environments. The combination of both tech-niqueshasbeenalreadyappliedtosolvetransmissionexpansionsimple scenarios [13], [14]. The use of bilateral Shapley values and a cost allocation technique based on a backward inductionmethod has been successful with simple examples.This paper is anextension of the srcinal transmission expan-sion problem studied in [13] that explores a new methodology:the kernel approach. The kernel is a concept from cooperativegame theory that splits a common resource among the playersin terms of the “strength” of the members of the coalition. Inparticular, for the transmission expansion game, it rewards themembers that are less costly to the expansion of the system.The structure of the paper is as follows. Section II coversthe mathematical model of the transmission planning problem.Section III describes multi-agent settings and their connectionto game theory. Section IV analyzes the kernel approach andthe cost allocation procedure. Section V shows the results froma 6 bus example and an IEEE 24 bus case. Finally, Section VIdraws several conclusions.II. T HE T RANSMISSION P LANNING P ROBLEM A simplified formulation of the transmission expansionproblem can be expressed as follows [15]:(1)subject to(2)(3)whereis the cost of adding line to the network,is the active power (in p.u.) flowing through the addedline , i.e. the th element of , andis the flow vector for the possible new lines.is the number of possible new lines, is the matrix whoseelements are the imaginary parts of the nodal admittance matrixof the existing network, is the phase angle vector, is the 0885–8950/00$10.00 © 2000 IEEE  1436 IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 15, NO. 4, NOVEMBER 2000 where is the payoff of each player and the coalition config-uration. There are two coalitions that include but exclude ,namely coalitions and . The excess of coalition A with re-spect to is , while the excessof coalition is .The maximum surplus of player over player is therefore. Similarly, . Sinceand , player outweights playerwith respect to and the payoff configuration is not inthe kernel of the game.Now consider another payoff configuration for the samegame, this time one with the grand coalition, orThe maximum surplus of player over player isThe converse maximum surplus is . Sinceand , player outweights player with respect to, and the payoff configuration is not in the kernel. Butconsider now the payoff configurationHere, we find that .Therefore, all players are in equilibrium, and the payoff config-uration is a point of the kernel.In the transmission planning problem considered as a coop-erative game, the steps that are taken to build coalitions and toallocate costs are based on the Kernel-oriented Coalition Algo-rithm (KCA) developed by Klusch and Shehory [18], [19]. This is a new formulation of the same problem as seen in [14] wherea Bilateral Shapley Value (BSV) algorithm was presented.As said above, the KCA is a decentralized, negotiation-ori-ented coalition algorithm which determines akernel-stable pay-ment. The coalition negotiation is round-based, which meansthat all agents are synchronized at specified points in the nego-tiations. At the end of each round a new coalition is formed outoftwooldcoalitionsortherearenoacceptedcoalitionproposalsand the algorithm stops with a kernel-stable payment configu-ration. For more details on how the agents are defined at thebeginning of the game see [14].Each round of the KCA can be divided in three phases:  A. Calculating and Sending Coalition Offers Initially, all players are single coalitions. The coalitionchooses the strongest (in the kernel sense) representative tocalculate coalition offers.Her task is to calculatethe new payoff vector of every joint coalition that may be possible to create.Then, a K-stable payment configuration is calculated for eachcoalition structure that can be formed out of the old structure by joining the own coalition with one in the ranking list. Later, therepresentative sends a proposal to every promising coalition. Fig. 1. 6 bus Garver test system.  B. Coalition Formation If the payment to all members of the joint coalition is greaterthan their current payoffs in their srcinal coalitions, and if thereceived offer is the first in the ranking list, then the proposalis accepted. This local decision is broadcasted to all currentcoalitions. C. Cost Allocation and Stopping Rules Cost are allocated at every iteration using the K-stable con-cept, and when the coalition formation process ends, the al-located cost is the last one calculated. Negotiation continuesuntil all proposals of all coalition entities of the current coali-tion structure are rejected, or a grand coalition has been alreadyformed, or a pre-defined time period has been exceeded.V. N UMERICAL T ESTS To test the KCA model we have run simulations with two dif-ferent transmission expansion planning examples. A dual soft-ware platform has been implemented with that purpose. Thefirst component simulates the coalition formation process andthe second one the cost allocation procedure. The software im-plementation is shown in great detail in [20], [21].  A. 6 Bus Garver Test System KCA Solution The first example is the classical 6 bus example from Garver[1], as shown in Fig. 1. Cost data and coalitional values are pre-sented in Tables I and II, respectively. Note that the costs areequivalent to negative values in Table II.The kernel algorithm rewards strong agents from the begin-ning, and this is the case of agent 6. Bus 6 is constantly neededto supply the load for most of the other buses and it is rewardedby the kernel method because agent 6 excesses with respect topossible coalition partners are high.Following the kernel-stable algorithm formulated above, thecoalition formation process is as follows: [1, {2-6}, 3, 4, 5][{1-2-6}, 3, 4, 5] [{1-2-4-6}, 3, 5] [{1-2-3-4-6}, 5]  CONTRERAS AND WU: A KERNEL-ORIENTED ALGORITHM FOR TRANSMISSION EXPANSION PLANNING 1437 TABLE I6 B US G ARVER T EST S YSTEM D ATA TABLE IIC OALITION E XPANSION V ALUES FOR THE 6 B US S YSTEM [{1-2-3-4-5-6}]. The final cost allocation is: (16.25, 76.25,16.25, 60, 40, 13.75).  B. 6 Bus Garver Test System BSV Solution Previous work based on Bilateral Shapley Values [13],[14] showed several possible grand coalition cost alloca-tion solutions:From Table III, it is observable that the BSV method does notfavorbigplayersasmuchasthekernel.Morefairnessinthecostallocation can be expectedfrom BSV’s, acting in aShapley-likefashion. This fact is observed in the allocation of cost to buses4, 5 and 6, where Table III shows that bus 6 must always pay incontrast to the kernel solution where the other agents subsidizebus 6 (the strongest) increasing their own payments. C. 6 Bus Garver Test System Sunk Costs Allocation A variation of the six bus example is the cost allocation of all lines: existing and possible new ones, assuming a total ex-pansion cost of 130 monetary units, the grand coalition scheme.Table IV shows the new costs. Kernel allocation results are asfollows: (0, 90, 0, 60, 40, 0). The simulation shows thatonly buses 2 and 6 form a coalition and the process ends after1 step. The reason is that sunk costs exceed the cost limits that TABLE III6 B US B ILATERAL S HAPLEY V ALUE A LGORITHM R ESULTS TABLE IVS UNK C OSTS FOR THE 6 B US G ARVER T EST S YSTEM makebusesattractivetopossiblepartners.Therefore,sunkcostscannotbecalculatedusingthealgorithmproposedinSectionIV.BSV’s would lead to similar conclusions.  D. IEEE 24 Bus RTS Example The final example is taken from the IEEE 24 bus ReliabilityTest System (RTS), as shown in Fig. 2 and Tables V–VII. Notethat Fig. 2 presents the IEEE 24 bus system divided in four ini-tial coalitions that fulfill the self-sufficiency axioms describedin [14]. Table V shows the possible new lines in shadowed greycolor and total generation ( ) and demand ( ) for each coali-tion are also shown in Fig. 2. It is also assumed that line thermallimits are equal to 3333 MW for all lines.The KCA produces the coalition formation process and finalcost allocation as presented in Fig. 3.These results indicate that self-sufficient players, like coali-tion 4, with no need to expand their own system, will benefitfrom other player’s gradual expansion plans. In particular, totalsystem reliability is greatly enhanced with player 4 and that iswhy player 4 gets a positive reward whilst players 1, 2, and 3have to pay for expansion, although much less than in isolation.VI. C ONCLUSION Thispaperhasshownanewdecentralizedcoalitionformationand cost allocation procedure based on a kernel approach.  1438 IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 15, NO. 4, NOVEMBER 2000 Fig. 2. IEEE 24 bus RTS example.
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x