Aggregating energy flexibilities under constraints

Agg ega ing Ene gy Flexibili ies unde Cons ain s Emmanouil Valsoma zis and To ben Bach Pede sen Aalbo g Uni e si y Email: {e alsoma, bp}@cs.aau.dk Albe o Abell´ o Uni e si a Poli ` ecnica de Ca alunya Email: [email p o ec ed] Ka ja Hose Aalbo g Uni e si y Email: [email p o ec ed] Abs ac —The lexibili y o indi idual ene gy p osume s (p o- duce s and/o consume s) has d awn a lo o a en ion in ecen yea s. Agg ega ion o such lexibili ies p o ides p osume s wi h he oppo uni y o di ec ly pa icipa e in he ene gy ma ke and a he same ime educes he complexi y o scheduling he ene gy uni s. Howe e , agg ega ed lexibili y should suppo no mal g id ope a ion. In his pape , we build on he lex-o e (FO) concep o model he inhe en lexibili y o a p osume (e.g., a single lexible consump ion de ice such as a clo hes washe ). An FO cap u es lexibili y in bo h ime and amoun dimensions. We de ine he p oblem o agg ega ing FOs aking in o accoun g id powe cons ain s. We also p opose wo cons ain - based agg ega ion echniques ha e icien ly agg ega e FOs while e aining lexibili y. We show h ough a comp ehensi e e alua ion ha ou echniques, in con as o s a e-o - he-a echniques, espec he cons ain s imposed by he elec ical g id. Mo eo e , ou echniques also educe he scheduling inpu size signi ican ly and imp o e he quali y o scheduling esul s. I. INTRODUCTION One o he main goals o he Sma G id is he ene gy use in- c ease om Renewable Ene gy Sou ces (RES). Howe e , due o RES being cha ac e ized by ola ile powe p oduc ion (e.g., wind powe ), Sma G id akes ad an age o he p osume s’ inhe en lexibili y o be e ma ch ene gy demand wi h supply, e med Demand Response (DR), and hus enables an inc eased sha e o RES ene gy. In ou wo k, we model lexible demand/supply de ices ( e e ed o as loads o simpli ica ion) using he lex-o e (FO) concep [1]. An FO explici ly cap u es he lexibili y in ene gy and ime o a load, as p esen ed in he ollowing example. Example 1. The owne (consume ) o an elec ic ehicle (EV) wan s o cha ge his EV a 20:00 and ha e i cha ged by 7:00 he ollowing day. The EV akes 3hou s o be cha ged and equi es 15kWh. Thus, he EV can s a i s cha ging be ween 20:00 and 4:00. The numbe o loads ha a e lexible has ecen ly inc eased due o new echnological achie emen s (e.g., EVs and hea pumps). The exis ence o app op ia e in o ma ion and com- munica ion echnology (ICT) in as uc u e [2] and a sui able hie a chical con ol a chi ec u e, o e he capabili y o ma ke ac o s o command he DR [3]. Mo eo e , he es ablishmen o a lexibili y ma ke [4] will p o ide lexibili y wi h he oppo uni y o be aded [5]. Howe e , he ene gy cap u ed by indi idual FOs om small load de ices canno be di ec ly aded in he ma ke [6]. Fo ins ance, he powe equi ed o pa icipa e in he ancilla y se ice ma ke in Denma k is in he magni ude o ew hund eds o kW whe e he consump ion capaci y o an EV is ew kW [6]. Thus, in o de o ade lexi- bili y, i is essen ial o agg ega e FOs and p oduce commodi ies ha can be aded in he eme ging ene gy lexibili y ma ke s. Fu he mo e, agg ega ion o FOs, applied be o e scheduling, is essen ial o educe he highly complex Uni Commi men (UC) p oblem [7]. Acco ding o he UC p oblem, FOs a e scheduled, i.e., he ope a ional ime and amoun is de ined, based on an objec i e unc ion. On he o he hand, lexible loads and, consequen ly, hei co esponding FOs a e connec ed o an elec ical g id. How- e e , he g id is cha ac e ized by powe capaci y limi a ions and he high powe equi emen s o new de ices, such as EVs, migh lead o g id conges ions. G id sensi i e load loca ions (bo lenecks) a e in di e en ol age elemen s. They could be in low (local dis ibu ion) and in high ol age elemen s (sup a- egional dis ibu ion). Fo ins ance, a bo leneck migh be a dis ibu ion ans o me (0.4-1kV) wi h a maximum powe alue o ew hund ed kW. Such a ans o me migh se e om ew (e.g., in No h Ame ica) o se e al hund ed households (e.g., in Eu ope) [8]. In ou wo k, we ollow he mapping applied in [9] and map a bo leneck o he oo o a ee, see R in Figu e 1. The oo is cha ac e ized by an amoun cons ain ha de ines he ole able ope a ional powe ange. Fo ins ance, he powe o a dis ibu ion ans o me (0.4kV) shall be in he in e al [-300kW, 300kW] [3]. We also map all FOs, which belong o he bo leneck, o he lea nodes, see 1 in Figu e 1. The le mos ci cle in he igu e illus a es an FO co esponding o he load o an EV. The x-axis ep esen s ime and he y- axis ep esen s powe . The ene gy equi ed o cha ging he EV is exp essed by h ee slices (one pe ime uni ). The da k- shadowed pa s ep esen he minimum ene gy equi emen s. The ligh -shadowed pa s ep esen op ional cha ging le els. Fo ins ance, he EV owne is sa is ied when cha ging le el is in he ange [60%,100%]. Mo eo e , as we see in he igu e, cha ging o he EV can s a a ime 1 a he ea lies ( es) and a ime 5 a he la es ( ls). Thus, he FO p o ile, which consis s o he h ee slices, can be ime-shi ed. Using adi ional agg ega ion echniques [10], he FOs a e agg ega ed esul ing in agg ega ed FOs (AFOs). As illus a ed in Figu e 1, he ou FOs 1 a e agg ega ed in o wo AFOs 2 . Each p o ile o an AFO is p oduced by summing up one o mo e p o iles o he 4 FOs. Wi hou conside ing cons ain s, loads migh be placed a he same ime since i may be mo e bene icial, e.g., om a inancial poin o iew. Howe e , his could lead o iola ions. Fo ins ance, we see ha he powe © 2016 IEEE. Pe sonal use o his ma e ial is pe mi ed. Pe mission om IEEE mus be ob ained o all o he uses, in any cu en o u u e media, including ep in ing/ epublishing his ma e ial o ad e ising o p omo ional pu poses,c ea ing new collec i e wo ks, o esale o edis ibu ion o se e s o lis s, o euse o any copy igh ed componen o his wo k in o he wo ks. DOI 10.1109/Sma G idComm.2016.7778808 R AFOs T ading Scheduling Viola ion No mal ope a ion T adi ional (Ou solu ion) agg ega ion 300kW -300kW ICT in as uc u e 2 0.4kV AFOs T ading Scheduling 300kW -300kW 0 + - 0 + - 2' 33' 0 + - 0 - + 0 - + 0 + - Cons ain -based agg ega ion De ices/FOs - 0 1 44' 0 + n as uc u e 0 - 0 + -300kW 300kW -300kW 300kW es ls powe alue ime 15 Powe Fig. 1: T adi ional s Cons ain -based agg ega ion. o he le AFO ( i s da k-shadowed slice in 2 ) exceeds he cons ain imposed by he g id. A e being agg ega ed, he AFOs a e aded and scheduled, see 3 . Scheduling ans o ms AFOs in o assignmen s and o ms he oo powe alue. Howe e , i is impossible o schedule he ou pu o adi ional agg ega ion and o espec he cons ain . Thus, scheduling leads o a cons ain iola ion due o inapp op ia e agg ega ion, see 4 whe e he powe alue exceeds 300kW in he i s ime slo ( ed ci cle). Consequen ly, FO agg ega ion echniques ha ake in o accoun g id cons ain s a e equi ed. In his pape , we p opose such cons ain -based agg ega ion which p oduces AFOs ha can be u he scheduled and suppo a no mal g id ope a ion, see 2' - 4' in Figu e 1. Con ibu ions. Fi s , we demons a e he p oblems ha occu wi h adi ional FO agg ega ion. Second, we in oduce he objec i es o cons ain -based FO agg ega ion and p opose wo heu is ic agg ega ion echniques ha educe he inpu by mo e han 90% while e aining lexibili y. Thi d, we e alua e he p oposed echniques in complex use case scena ios. We show ha ou echniques lead o no mal g id ope a ion whe e he exis ing s a e-o - he-a app oaches lead o g id cons ain iola ions a mo e han 15% o he examined ime ho izon. Fi- nally, we show ha in cases whe e scheduling canno p o ide a schedule ha espec s g id cons ain s wi hin a ce ain ime pe iod, ou agg ega ion echniques e icien ly na ow down he solu ion space and hus lead o alid scheduling esul s. The emainde o he pape is s uc u ed as ollows. Sec- ion II in oduces ele an concep s and de ini ions. Sec ion III discusses he p oblems o adi ional agg ega ion and in o- duces cons ain -based agg ega ion objec i es. In Sec ion IV, he wo cons ain agg ega ion solu ions a e p oposed. Thei expe imen al e alua ion is desc ibed in Sec ion V. In Sec- ion VI ela ed wo k is discussed. Finally, he pape concludes and poin s o u u e wo k in Sec ion VII. II. BACKGROUND AND PRELIMINARIES Based on [10] and using wo disc e e dimensions, i.e., ime and amoun , we de ine he ollowing. De ini ion 1. An FO is a uple = (T( ), P ( )) whe e T( )is he s a ime lexibili y in e al and P( )is he amoun p o ile. T( ) = [ es, ls]whe e es and ls a e he ea lies s a ime and la es s a ime, espec i ely. The amoun p o ile is a sequence o (m∈N>0) consecu i e slices, P( ) = hs(1), . . . , s(m)iwhe e a slice s(i)is an amoun ange [amin, amax]. The du a ion o slices is 1 ime uni . Fo ins ance, Figu e 2 illus a es FO = ([1,5],h[3,5],[2,3]i). We dis inguish wo ypes o lexibili ies Fig. 2: A lex-o e associa ed wi h an FO ha a e used as indi idual mea- su es aking in o accoun ime and amoun sepa a ely. We conside ime lexibili y ( )o an FO o be he di e ence be ween i s la es and ea lies s a ime, i.e., ( ) = ls − es. Mo e- o e , we conside amoun lexibili y a ( )o an FO o be he di e ence be ween he sum o all he maxi- mum and minimum alues o all i s slices, i.e., a ( ) = Ps∈P( )(s.amax −s.amin). Time lexibili y is measu ed in ime uni s and amoun lexibili y in amoun uni s. An FO cap u es all possible amoun demands and/o sup- plies o a de ice o a gi en ime ho izon. Howe e , du ing he scheduling p ocess, an FO is assigned o a speci ic amoun a a speci ic ime esul ing in an assignmen o he FO de ined as ollows: De ini ion 2. An assignmen o an FO is a sequence o |P( )| ∈ N>0consecu i e slices, as =hs(1), ..., s(|P( )|)i. Each slice is a 2- uple, s(i)=( s, am), i ∈[1,|P( )|]. The i s elemen , s, indica es he ac ual s a ing ime and he second one, am, he ac ual amoun o he slice. The du a ion o each slice is 1 ime uni . The s a ing ime o he i s slice o he assignmen mus be wi hin he s a ime lexibili y in e al o he FO, i.e., . es ≤as .s(1). s≤ . ls. Each slice o he assignmen has an amoun alue in he ange o he co esponding slice o he FO, i.e., .s(i).amin ≤a .s(i).am ≤ .s(i).amax, ∀i= [1 . . . |P( )|]. The e is a ini e numbe o assignmen s o an FO. We deno e he se o all he assignmen s o an FO by L( ). III. PROBLEM FORMULATION In his sec ion, we discuss how agg ega ion is applied h ough adi ional agg ega ion and in oduce he concep o cons ain -based agg ega ion. A. T adi ional FO agg ega ion We conside , based on [10], adi ional agg ega ion o FOs o be he unc ion ha gi en a se o FOs e u ns an agg ega ed one, aking in o accoun he ime and amoun lexibili ies o he FOs. Gi en a se o FOs, he e a e di e en alignmen s ′ 1 2 3 4 5 123 123 123123 123 123 1 2 3 4 1 2 3 4 1 2 3 4 5 1 2 3 4 1 2 3 4 cons ain cons ain cons ain cons ain cons ain cons ain (a) (b) Fig. 3: Di e en alignmen examples o agg ega ion. ha lead o di e en AFOs due o hei ime lexibili y. In pa - icula , gi en |F|FOs wi h ime lexibili y ( 1),..., ( |F|) espec i ely, he numbe o he agg ega ion esul s (AFOs) ha can be p oduced is: Q|F| i=1 ( i)+1. Fo ins ance, he 2 FOs, 1and 2in Figu e 3, can be di e en ly aligned and esul in di e en AFOs. Thus, o 1and 2wi h bo h ob aining 3 di e en s a imes, he e a e 3·3=9alignmen s ha lead o 9 agg ega ion esul s (AFOs). We show 2 o hem in Figu e 3. The ime lexibili y in e al o an AFO is de e mined by he chosen alignmen s. In pa icula , he amoun p o ile o an FO does no ha e any speci ied s a ing ime un il he FO is assigned. Howe e , an FO cap u es all he di e en s a ing imes in he s a ime lexibili y in e al, see De ini ion 1. As a esul , when agg ega ion is applied, FOs ha pa icipa e in agg ega ion a e aligned (a s a ing ime among he in e al is chosen o e e y FO) and he amoun anges o each aligned slice a e summed, see Figu e 3. We deno e he agg ega ion ha aligns FOs acco ding o hei ea lies s a ime as S a Alignmen (SA) agg ega ion, see Figu e 3a. Acco ding o SA agg ega ion, he ea lies s a ing ime o he AFO is he minimum ea lies s a ing ime o he non-agg ega ed FOs. The la es s a ing ime o he AFO is he sum o i s ea lies s a ing ime and he minimum ime lexibili y among he FOs. As a esul , he AFO espec s all he s a ing ime in e als o he non-agg ega ed FOs ha p oduced i . Fo ins ance, he AFO a 12 in Figu e 3 has ea lies s a ing ime 1 ( a 12. es =min( 1. es, 2. es)). The la es s a ing ime ( ls) o a 12 is equal o 3 ( a 12. ls = a 12. es +min( ( 1), ( 2))). B. Cons ain agg ega ion objec i es and complexi y As men ioned in Sec ion I, he alue o a node (ac ual load) is gi en by he assignmen s o he FOs ha belong o he node. In pa icula , du ing scheduling each FO is u ned in o an assignmen and he esul is a se o assignmen s. Consequen ly, he sum o he slice amoun s wi h he same ime o ms he node alue a ha ime. Howe e , in o de o gua an ee a no mal g id ope a ion, he ac ual loads o he g id mus be wi hin he bounds imposed by he cons ain , e.g., [-300kW, 300kW]. Fo ins ance, concu en ly cha ging a high numbe o EVs can lead o ans o me o e load. We assume ha FOs 1and 2in Figu e 3 belong o a node wi h cons ain alue 2. Mo eo e , we see ha he agg ega ion esul ( a 12 las ow column a) o SA does no enable an assignmen ha espec s he cons ain . When scheduling is applied on a 12, he e a e se e al po en ial assignmen s o a 12, e.g., as a1 12 = (1,3) and as a2 12 = (2,4), see Figu e 3a. Howe e , he cons ain alue is 2and he amoun s o all he assignmen s a e g ea e han he cons ain . They should ha e been wi hin he ange [-2,2]. Con e sely, we see ha when FO agg ega ion akes in o accoun he cons ain , i p oduces AFO b 12 (Figu e 3b) ha con ains assignmen s which espec he cons ain , e.g., as b 12 =h(2,2),(3,1)i. In his pape , we e alua e an agg ega ion esul h ough he objec i es o cons ain -based agg ega ion. Cons ain -based FO agg ega ion has 3objec i es. The p o- duced AFOs (1) shall enable scheduling esul s ha espec he cons ain o he node whe e he FOs belong (ha d cons ain ). Mo eo e , (2) agg ega ion should e ain as much lexibili y as possible and (3) a he same ime educe he numbe o FOs ha belong o a speci ic node. 1) Respec node cons ain s. All node cons ain s should be espec ed. A node cons ain iola ion co esponds o a g id mal unc ion a he poin whe e he node is. Tha esul s in se ice cu o o FOs ha belong o he iola ed node and hus he p osume s migh no be se ed. 2) Minimize lexibili y losses. Flexibili y o FOs is im- po an o scheduling because he mo e lexible FOs a e, he mo e deg ees o eedom he scheduling has o ind he op imal solu ion. Mo eo e , AFOs cap u e la ge lexibili ies and can mo e easily be aded in he ene gy ma ke . We use lexibili y as a quali y measu e o e alua e ou p oposed echniques, as AFOs migh lose lexibili y du ing agg ega ion. 3) Minimize he numbe o AFOs. FOs a e pa o he scheduling inpu ha akes place a e agg ega ion. The e o e, i is impo an o cons ain agg ega ion o educe he numbe o FOs, because i di ec ly educes he complexi y o he subsequen scheduling. Mo eo e , unless FOs a e agg ega ed o cap u e la ge ene gy amoun s, hey canno be aded in he ene gy ma ke . The abo e-men ioned objec i es migh be con adic o y and canno be sa is ied simul aneously. In pa icula , as he numbe o AFOs is educed, ime lexibili y losses migh inc ease and ime lexibili y migh be used o espec he cons ain . Fo ins ance, we see in Figu e 3a ha 1and 2ha e ime lexibili y 2. Howe e , AFO b 12 has ( b 12)=1. Cons ain agg ega ion complexi y. Due o space limi a- ions, we illus a e he compu a ional complexi y o cons ain - based agg ega ion h ough an example. In ou example, gi en a se o FOs, we compu e he o al solu ion space, i.e., he numbe o all he po en ial agg ega ion esul s. Example 2. Gi en a se Fo 4FOs, 1, 2, 3, 4, wi h ( 1)=3, ( 2)=2, ( 3)=4, ( 4)=5, he e a e B4=P4 k=1 4 k=1 1! (−1)11 004+1 2! P2 j=0 2 jj4+ 1 3! P3 j=0 3 jj4+1 4! P4 j=0 4 jj4= 1+7+6+1 = 15, pa i ions o F[11]. Mo eo e , he e a e Q4 i=1 ( i)=3·2·4·5 = 60 alignmen s. Thus, he e a e 15·60 = 900 possible agg ega ion esul s. Adding a i h FO o he se wi h ( 5)=5, he e a e B5=52 pa i ions o Fand Q5 i=1 ( i) =60 ·5=300 align- men s. Thus, he e a e 52 ·300 = 15600 possible agg ega ion esul s. The e o e, we can no ice a combina o ial explosion o he agg ega ion esul s depending on he size o he inpu and i s a e age ime lexibili y. IV. CONSTRAINT-BASED FO AGGREGATION Due o he high complexi y o cons ain -based agg ega ion, we analyze wo a ia ions o a g eedy solu ion o ackle he p oblem. In pa icula , he g eedy app oaches p ocess FOs ha belong o a node inc emen ally by e alua ing bina y agg ega ions. E alua ion is based on di e en me ics in o de o examine whe he u he agg ega ion is a o ed o no . The me ics ake in o accoun bo h he capaci y limi a ions o he node and he objec i e o he ma ke ac o who con ols he FOs o he node. A. Cons ain and a ge ela ed dis ances As men ioned in Sec ion I, in o de o gua an ee a no mal g id ope a ion, he node alue shall be wi hin he bounds imposed by he cons ain . In his pape , we handle he cons ain as a unc ion. De ini ion 3. We de ine a (cons an ) posi i e cons ain unc- ion c( ) = y, ∈Z,y∈N0, whe e is he ime and y he amoun . Fo ins ance, gi en a cons ain unc ion c( )=300, he alid amoun ange is [-300, 300]. In cases whe e he node alue is ou side he cons ain bounds, a node iola ion occu s, see o ins ance 4 in Figu e 1. When his happens, he elec ical g id is no eliable and he dis ibu ion sys em ope a o , who is esponsible o he g id, needs o expand and upda e he powe sys em in as uc u e. Upda ing he g id is a e y expensi e and ime consuming p ocedu e. In ou wo k, since he node alue is o med by he assignmen s o he FOs, we co ela e an assignmen o he cons ain unc ion. We conside he dis ance o each slice o an assignmen (posi i e o nega i e) o be ze o when i is wi hin he ange because no g id p oblems occu . O he wise, we ake in o accoun he dis ance o he cons ain unc ion. De ini ion 4. We de ine he dis ance o a slice o an assign- men ,Dc(as .s(i)), o a cons ain unc ion cas equal o ze o i he absolu e slice amoun is smalle o equal o c. O he wise, Dc(as .s(i))is equal o he di e ence be ween he absolu e amoun alue o he slice and he cons ain , i.e., Dc(as .s(i)) = max(0,|s(i).am| − c(s(i). s)) whe e as =hs(1), ..., s(|P( )|)iand i∈[1,|P( )|]. Consequen ly, we de ine dis ance o an assignmen as ,Dc(as ), o a cons ain unc ion c o be he sum o all i s slice dis ances o c, i.e., Dc(as ) = P|P( )| i=1 Dc(as .s(i)). The objec i e o he ma ke ac o con olling he FOs o a node, e.g., an agg ega o , is o mula ed h ough a a ge unc ion. Ta ge exp esses he op imal schedule, wi hou con- side ing he cons ain , and can be used o ep esen an op imal business goal, e.g., op imal p ice/amoun co ela ion. Ta ge migh con adic he cons ain and i could lead o AFOs wi h assignmen s ha iola e he cons ain , see o ins ance 2 in Figu e 1. We de ine bo h he a ge unc ion and he assignmen dis ance o he a ge unc ion as ollows: De ini ion 5. We de ine a (cons an ) signed a ge unc ion g( ) = a, whe e ∈Zis he ime and a∈Z he amoun . De ini ion 6. We de ine he dis ance o an assignmen as o a a ge unc ion g,Dg(as ), as equal o he sum o he absolu e di e ences be ween gand he amoun alues o all he slices o he assignmen , i.e., Dg(as ) = Pm i=1 |g(s(i). s)− s(i).am|, as =hs(1), ..., s(m)i. In ou wo k, we ake in o accoun bo h he capaci y lim- i a ions o he g id and he ma ke ac o ’s objec i e. Thus, we conside bo h he dis ance o he cons ain and he a ge unc ion o e alua e ou esul s. In pa icula , we ake in o accoun he sum o he dis ances ( a ge and cons ain ) and we use weigh s (coe icien s) o p io i ize he cons ain iola ion. O cou se, when cons ain is espec ed, only he dis ance o he a ge unc ion is aken in o accoun . De ini ion 7. We de ine he dis ance o an assignmen as o a a ge unc ion gand a cons ain unc ion c,Dg,c(as ), as he weigh ed sum o i s a ge and cons ain dis ances wi h weigh s αand β espec i ely, i.e., Dg,c(as ) = α· Dg(as ) + β·Dc(as ),α, β ∈R. As men ioned in Sec ion II, since an FO cap u es a se o assignmen s (L( )), he e is a leas one assignmen o ha has he smalles dis ance. De ini ion 8. We de ine he a ge o cons ain dis ance o a FO o a a ge unc ion gand a cons ain unc ion c, Dg,c( ), as he minimum dis ance among all i s assignmen s o gand c, i.e., Dg,c( ) = minas ∈L( )Dg,c(as ). Example 3. Fo ins ance, gi en α= 1,β= 10,c( ) = 2, and g( ) = 3, an assignmen o a 12 in Figu e 3 wi h he minimum dis ance is: as a 12 = [1,3] whe e Dg,c(as a 12 ) = 1·0+10·1 = 10 = Dg,c( a 12 ). On he con a y, an assignmen o b 12 wi h he minimum dis ance is: as b 12 =h[1,2],[1,2]i whe e Dg,c(as b 12 )=1·(1 + 1) + 10 ·0 = 2 = Dg,c( b 12 ). B. Agg ega ion echniques We now p esen ou 2heu is ic cons ain -based FO ag- g ega ion echniques. Bo h he echniques a e a ia ions o he same abs ac G eedy algo i hm (Algo i hm 1). They s a by selec ing (Line 2) he FO ( nom) wi h he maximum a - ge o cons ain dis ance (max ∈SF (Dg,c( )). The eason is ha apa om educing he numbe o he AFOs, agg ega ion shall also p oduce FOs ha a e close o he a ge in o de o imp o e scheduling esul s. Thus, s a ing agg ega ion wi h FOs wi h high “dis ances” (used ins ead o a ge cons ain dis ance o simpli ica ion) is desi able and inc eases he chance o educing he o e all dis ance. Then, he selec ed FO, nom, is emo ed om he ini ial se (Algo i hm 1, Line 2). Algo i hm 1 Abs ac G eedy Inpu : SF - se o FOs; g,c - a a ge and a cons ain unc ion Ou pu : SF - se o AFOs 1: mp ←null; a←null; 2: nom ←Selec NomFO(SF); SF ←SF nom; 3: while ∃ ∈SF no agg ega ed do 4: { a, mp} ←Bes Agg ega ion(SF, nom) 5: i Dg,c( a)<Dg,c( nom) hen 6: SF ←SF mp; nom ← a 7: else 8: Anno a eAsAFO( nom) 9: SF ←SF ∪ nom 10: nom ←Selec NomFO(SF); SF ←SF nom; 11: e u n SF Algo i hm 2 Simple G eedy ex ends G eedy (same inpu and ou pu as G eedy) 1: unc ion Bes Agg ega ion(SF , nom) 2: mp←Closes ToZe oDis ance(SF ) 3: a←Bina yAgg ega ion( nom, mp) 4: e u n { a, mp} A e wa ds, algo i hm con inues un il all FOs a e agg ega ed (Line 3). The wo a ia ions o G eedy examine di e en FOs o p oduce an AFO, i.e., a(Line 4). I he e is an AFO ( a) wi h smalle dis ance han nom, he algo i hm con inues agg ega ion wi h he agg ega ed one and emo es mp om he ini ial se SF (Line 6). O he wise, i anno a es nom as AFO and con inues by selec ing ano he nom om he non- agg ega ed ones (Lines 8–10). The algo i hm s ops when all he FOs a e anno a ed as AFOs (Line 3) and e u ns se SF wi h he AFOs (Line 11). Simple G eedy (SG). Apa om nom, SG also selec s a single FO mp o examine whe he i will agg ega e hem o no (Algo i hm 2, Line 2). In pa icula , i selec s he FO ( mp) among he se ha has he closes o ze o dis ance o inc ease he chances o educing he dis ance o nom. Then, in each s ep, i examines all he po en ial agg ega ions be ween he wo FOs, i.e, nom and mp o iden i y he AFO ha educes he dis ance o nom (Algo i hm 2, Line 3). Exhaus i e G eedy (EG). EG explo es a la ge solu ion space han SG. In pa icula , du ing each s ep, i examines all he po en ial bina y agg ega ions be ween nom and all he FOs in se SF (Algo i hm 3, Line 3) compa ed o SG Algo i hm 3 Exhaus i e G eedy ex ends G eedy 1: unc ion Bes Agg ega ion(SF , nom) 2: a← nom; mp ←null; 3: o each ∈SF do 4: y←Bina yAgg ega ion( nom, ) 5: i Dg,c( y)< Dg,c( a) hen 6: a← y; mp ← ; 7: e u n { a, mp} Algo i hm 4 Bes bina y agg ega ion unc ion Inpu : nom, mp - FOs Ou pu : a- an AFO 1: unc ion Bina yAgg ega ion( nom, mp) 2: a← nom 3: o each alignmen al o { nom,, mp}do 4: x←AGG-2- o-1( nom, mp, al) 5: i Dg,c( x)<Dg,c( a) hen 6: a← x 7: e u n a ha examines only he bina y agg ega ions among nom and one FO om SF. EG hen s o es he AFO wi h he smalles dis ance (Line 6). When he compa isons inish, i e u ns he AFO wi h he minimum dis ance ( a) and he FO ( mp) ha pa icipa ed in he p oduc ion o a(Line 7). Cons ain alloca ion ea u e. Since agg ega ion should lead o a alid schedule, i is desi able o examine, a e each s ep, whe he he node cons ain is espec ed o no . Howe e , his would equi e o schedule du ing each s ep he cu en FOs/AFOs, i.e., sol e he UC p oblem. Due o he ac ha he UC p oblem is an NP-comple e p oblem [12], ou agg ega ion algo i hms ins ead ac p e en i ely in e ms o cons ain handling. In pa icula , i is possible o bo h algo i hms o conside a cons ain alue lowe han he o iginal one. Fo ins ance, we ypically alloca e he cons ain o 50% o i s o iginal alue. As a esul , he alloca ion ea u e obs uc s agg ega ion o iola e he cons ain . Consequen ly, in cases whe e mo e han one AFOs ha e slice amoun s close o he cons ain , i inc eases he chance o scheduling o o m a node alue ha espec s he cons ain . V. EXPERIMENTAL EVALUATION A. Expe imen al se up We expe imen ally e alua e he p oposed echniques in complex conges ion scena ios. Ou expe imen s a e based on powe cha ac e is ics om eal loads (e.g., [13], [14]) ha show simila use beha io and a e complemen ed wi h po en ial lexibili y, e.g., [15]. One amoun uni co esponds o 0.5kW. The g id powe capaci y cons ain used in he expe imen s ep esen s medium ol age g ids, e.g., [16]. We use a mixed po olio o FOs ha ep esen s a a ie y o de ices and cha ac e is ics ega ding lexibili y and powe demand/supply. In pa icula , we gene a e 6 da ase s o FOs wi h di e en sizes o be able o examine he scalabili y o he echniques in e ms o inpu . The sizes o he da ase s ollow an a i hme ic p og ession wi h bo h ini ial e m and common di e ence equal o 500 FOs. Thus, he las da ase has 3000 FOs. In o de o c ea e imbalances and conges ion si ua ions, he numbe o he nega i e FOs is 10% o e e y da ase . In pa icula , 40% o he posi i e FOs ep esen elec ical ehicles (EVs), 30% ep esen hea pumps (HPs), and 30% clo hes washe s (CWs). The nega i e FOs ep esen wind u bines (WT) and pho o ol aics (PV) ha a e less lexible 500 1500 3000 Flex-o e s inpu -4000 -2000 0 2000 4000 6000 8000 Peaks (amoun ) a ge cons ain In. SA SAG SG EG 500 1000 1500 2000 2500 3000 Flex-o e s inpu 0 500 1000 1500 2000 Agg ega ed lex-o e s (ou pu ) SA SAG SGR EGR In. SAG SG EG In. SAG SG EG 0 4 8 12 In. SAG SG EG 0 4 8 12 Time lexibili y 3K FOs 500 FOs 1500 FOs 500 1000 1500 2000 2500 3000 Flex-o e s inpu 0 20 40 60 80 P ocessing ime (seconds) SA SAG SG EG (a) Peaks (b) #agg ega ed FOs (c) Time lexibili y box-plo s (d) P ocessing ime Fig. 4: 500 −3K FOs, a ge =3.5K, cons ain =3K, cons ain agg ega ion alloca ion = 1.5K, Dg,c( )=1·Dg+ 10000 ·Dc De ice EST #slices Min amoun s a EV (day) 6 5 4 U∗{5,7}U{0,2} EV (nigh ) N∗(18,1),[17,20] N(10,1),[8,12] U{3,4}U{5,7}U{0,2} CW (day) N(16,1),[15,17] U{1,3}U{2,4}U{3,4},U{1,2}0 CW (nigh ) N(20,1),[19,21] N(8,1),[5,10] U{2,4}U{3,4},U{1,2}0 HP (day) N(13,1),[12,14] N(3,1),[1,5] U{4,7}U{5,8}U{0,2} HP (nigh ) 17 3 U{3,6}U{5,8}U{0,2} WT, PV (day) N(14,1),[13,15] U{3,4}U{4,10}U{8,10}U{0,2} WT, PV (nigh ) N(23,1),[22,24] U{1,4}U{5,8}U{8,10}U{0,2} TABLE I: Flex-o e s cha ac e is ics, U∗: uni o m dis ibu ion, N∗: Gaussian dis ibu ion 0 10 20 30 Time ho izon -4000 -2000 0 2000 4000 Node alue (amoun ) a ge cons ain In. SAG EG Viola ions Fig. 5: 3K FOs inpu wi h longe p o iles. We alloca e FOs du ing day ime and nigh ime o all he de ices (50%-50%). De ails abou he cha ac e is ics o he da ase s a e shown in Table I. Mo eo e , o compa ison easons we use wo baseline agg ega ion echniques. We compa e ou echniques wi h S a Alignmen (SA) agg ega ion [10] (see Sec ion III-A whe e all he FOs a e agg ega ed in o one FO). We also use a S a Alignmen wi h G ouping (SAG) agg ega ion echnique whe e a g ouping phase is used in ad ance [10]. Consequen ly, FOs wi h he same ea lies s a ime and he same ime lexibili y a e g ouped oge he and SA is applied on each g oup. As a esul , o each g oup o FOs, a single AFO is p oduced. In o de o examine whe he an agg ega ion esul allows he cons ain o be espec ed o no , we implemen ed a s ochas ic scheduling echnique based on he E olu iona y Algo i hm (EA) p oposed in [17]. EA is applied on a se o FOs (agg ega ed o no ) and o ms he node alue wi h he possible minimum dis ance o a ge and cons ain unc ion. We see in Figu e 5 how he node alue is o med when EA is applied on he esul s o each agg ega ion echnique along wi h he cons ain and he a ge unc ion alues. The expe imen s we e conduc ed on a 2.9 GHz In el co e i7 p ocesso wi h wo co es, physical memo y o 8 GB, and MacOS. The echniques a e implemen ed in Ja a 1.8. B. Use case We examine ou echniques in a case whe e a ge is g ea e han he cons ain so ha a bo leneck appea s. Ta ge is 3500 and cons ain is 3000 (e.g., 6.6kV - 11kV subs a ion [16]). We also use he cons ain alloca ion ea u e. Thus, he cons ain alue used by he agg ega ion echniques is 1500. We se he a ge coe icien o 1and we use a e y high alue o he cons ain coe icien (10000) when he dis ance is compu ed, in o de o p io i ize he cons ain espec . In Figu e 4a, we see how he highes and he lowes node alues (amoun peaks) a e o med when EA is applied on he ini ial (“In.” label) non-agg ega ed se and on he agg ega ion esul o each echnique. Fo a be e illus a ion we show he cases whe e he inpu is 500,1500 and 3000 FOs. We see in Figu e 4a ha when he inpu size is 500, he peaks o med by EA (scheduling) a e qui e a away om he cons ain and as he inpu size is inc eased, he peaks app oach and inally exceed he cons ain . In he same igu e, we also obse e ha when he inpu size is small (500), all he echniques lead o scheduling ha espec s he cons ain . When he size is inc eased o 1.5K FOs, SA iola es he cons ain , and in he las case o 3K FOs only EG espec s he cons ain . Rega ding he numbe o he AFOs, we see ha SA p o- duces only one AFO in all he inpu cases (Figu e 4b) and i s ime lexibili y is always 1, i.e., he minimum among all he FOs. We also no ice ha SAG, due o he g ouping ha applies, p oduces a low numbe o AFOs and also achie es a simila o he ini ial ime lexibili y dis ibu ion among he AFOs, see Figu e 4c. Howe e , he agg ega ion esul o SAG iola es he cons ain when he inpu is inc eased o 2.5K and 3K (shown in Figu e 4a). Fu he mo e, in Figu e 5, we see how he node alue is o med based on EA when he agg ega ion inpu is 3K. In he same igu e, we no ice ha SAG no only iola es he cons ain , bu he e is also iola ion in 5ou o he 28 scheduling poin s (app oxima ely in he 18% o he ime ho izon). Rega ding SG, he numbe o AFOs scales linea ly wi h he inpu size and achie es a ime lexibili y highe han EG. Howe e , EG is he only algo i hm ha o ms a node alue ha espec s he cons ain in all he inpu cases. I main ains he numbe o AFOs low (93% inpu educ ion on a e age) and uses ime lexibili y o lead o a schedule ha espec s he cons ain . Tha is why i has he lowes a e age ime lexibili y and a dis ibu ion wi h low bounda ies, see Figu e 4c. Rega ding he p ocessing ime, EG is he slowes algo i hm due o he high numbe o compa isons i equi es. I shows a simila o linea g ow h a e beha io , see Figu e 4d. SG is as since i only compa es jus wo FOs in e e y s ep. Simila ly, SA and SAG a e he as es algo i hms due o he e y low numbe o agg ega ions hey pe o m. Expe imen al summa y. We obse e ha SG is as and espec s he cons ain while SA does no . When size inc eases (>2K FOs), bo h SG and SAG iola e he cons ain . On he o he hand, EG examines a la ge solu ion space and leads o esul s ha espec he cons ain when he inpu size is la ge, see Figu e 5, case o 3K FOs. I is indica i e ha e en when we apply EA on he ini ial se o 3K FOs o 10 minu es, i s ill canno p o ide a esul ha espec s he cons ain , see Figu e 5 label “In.”. On he con a y, EG uses app oxima ely 67 seconds o i s execu ion and EA applied a e wa ds p oduces he i s esul ha espec s he cons ain in app oxima ely wo seconds. Tha means ha EG is able o p o ide il e ed inpu s o scheduling so ha ini ially unsol able cases can be sol ed. Howe e , when he inpu is la ge, EG equi es high p ocessing imes. I equi es 24.08 minu es o p ocess a da ase o 10K FOs. VI. RELATED WORK The ole o an agg ega o ha handles lexible loads has been in es iga ed in many p e ious wo ks, e.g., [18], [19]. Such wo ks use highly complex models and ocus on con- olling and scheduling me hods. Thei main cha ac e is ic is ha he agg ega o ope a es as an agg ega ed load con olle ha ies o ollow a powe e e ence and e en ually ackles he scheduling p oblem o o e DR and ancilla y se ices, e.g., [20]. On he con a y, in ou wo k we use a low com- plexi y gene ic model o ep esen ene gy lexibili ies, namely lex-o e s (FOs). Mo eo e , he main goal o ou echniques is o p oduce lexible and non-scheduled AFOs ha can be aded as commodi ies in eme ging ene gy lexibili y ma ke s. Thus, ou p oposed echniques, SG and EG, p oduce AFOs ha can lead o no mal g id ope a ion and use a gene ic a ge unc ion ha can cap u e o e all business case scena ios. Fu he mo e, he e is an ex ensi e li e a u e ackling he uni commi men (UC) p oblem (scheduling), e.g., [21], [22]. In [17] he agg ega ion o FOs be o e scheduling showed an imp o emen o scheduling esul s compa ed o applying scheduling indi idually. Ou wo k can be also applied in ad ance o scheduling p ocess and no only educes he com- plexi y o he UC p oblem, bu in addi ion, pa ially handles scheduling goals as i “ il e s” in alid esul s and imp o es hei quali y. VII. CONCLUSION AND FUTURE WORK This pape in oduces cons ain -based agg ega ion o e a gene ic da a model ha cap u es lexibili ies in ime and amoun dimensions. I p oposes wo echniques ha ake in o accoun he powe capaci y cons ain limi a ions imposed by he g id. Mo eo e , he pape e alua es he p oposed echniques in complex conges ion scena io. The expe imen al e alua ion shows ha he p oposed echniques can e icien ly agg ega e FOs and a he same ime enable scheduling o espec he g id cons ain s, unlike exis ing echniques. In ou u u e wo k, we will ocus on enhancing ou ech- niques by au oma ing he se ing o agg ega ion pa ame e s h ough sampling echniques. Mo eo e , we will ex end ou p oposed algo i hms o in es iga e he inancial pe spec i e o cons ain -based agg ega ion on he u u e ene gy ma ke . ACKNOWLEDGMENT This wo k was suppo ed in pa by he To alFlex p ojec sponso ed by he Fo skEL p og am o Ene gine .dk. REFERENCES [1] M. Boehm, L. Dannecke , A. Doms, E. Do gan, B. Filipiˇ c, U. Fische , W. Lehne , T. B. Pede sen, Y. Pi a ch, L. ˇ Sikˇ snys, and T. Tuˇ sa , “Da a managemen in he mi abel sma g id sys em,” in EnDM, 2012. [2] M. Albano, L. L. Fe ei a, L. M. Pinho, and A. R. Alkhawaja, “Message- o ien ed middlewa e o sma g ids,” Compu e S anda ds & In e aces, ol. 38, 2015. [3] I. Diaz De Ce io Mendaza, I. Szczesny, J. Pillai, and B. Bak-Jensen, “Demand esponse con ol in low ol age g ids o echnical and comme cial agg ega ion se ices,” Sma G id, 2015. [4] L. Fe ei a, L. Siksnys, P. Pede sen, P. S luka, C. Ch ysoulas, T. le Guilly, M. Albano, A. Skou, C. Teixei a, and T. Pede sen, “A owhead complian i ual ma ke o ene gy,” in ETFA, 2014, pp. 1–8. [5] B. Neupane, T. B. Pede sen, and B. Thiesson, “E alua ing he alue o lexibili y in ene gy egula ion ma ke s,” in e-Ene gy. ACM, 2015. [6] B. Biegel, M. Wes enholz, L. H. Hansen, J. S ous up, P. Ande sen, and S. Ha bo, “In eg a ion o lexible consume s in he ancilla y se ice ma ke s,” Ene gy, ol. 67, 2014. [7] N. Padhy, “Uni commi men -a bibliog aphical su ey,” Powe Sys ems, ol. 19, 2004. [8] R. Mi a, V. A ya, B. Sulli an, R. Muelle , H. S o ey, and G. Labu , “Using analy ics o minimize e o s in he connec i i y model o a powe dis ibu ion ne wo k,” in e-Ene gy. ACM, 2015. [9] D.-J. Won and S.-I. Moon, “Op imal numbe and loca ions o powe quali y moni o s conside ing sys em opology,” Powe Deli e y, ol. 23, 2008. [10] L. Siksnys, E. Valsoma zis, K. Hose, and T. Pede sen, “Agg ega ing and disagg ega ing lexibili y objec s,” TKDE, ol. 27, 2015. [11] M. Aigne , “A cha ac e iza ion o he bell numbe s,” Disc e e Ma he- ma ics, 1999. [12] X. Guan, Q. Zhai, and A. Papalexopoulos, “Op imiza ion based me hods o uni commi men : Lag angian elaxa ion e sus gene al mixed in ege p og amming,” in Powe Enginee ing Socie y Gene al Mee ing, 2003. [13] J. Acos a, K. Combe, S. Djokic, and I. He nando-Gil, “Pe o mance assessmen o mic o and small-scale wind u bines in u ban a eas,” Sys ems Jou nal, ol. 6, 2012. [14] M. an de Kam and W. an Sa k, “Sma cha ging o elec ic ehicles wi h pho o ol aic powe and ehicle- o-g id echnology in a mic og id; a case s udy,” Applied Ene gy, ol. 152, 2015. [15] I. Sajjad, G. Chicco, and R. Napoli, “Demand lexibili y ime in e als o agg ega e esiden ial load pa e ns,” in Powe Tech, 2015. [16] W. P. Dis ibu ion, “Gene a ion capaci y egis e ,” h ps://www. wes e npowe .co.uk/Connec ions/Gene a ion/Gene a ion-Capaci y-Map/ Gene a ion-capaci y- egis e .aspx, accessed: 2016-05-05. [17] T. Tuˇ sa , L. ˇ Sikˇ snys, T. B. Pede sen, E. Do gan, and B. Filipiˇ c, “Using agg ega ion o imp o e he scheduling o lexible ene gy o e s,” in BIOMA, 2012. [18] X. Geng and P. Kha goneka , “Elec ic ehicles as lexible loads: Algo i hms o op imize agg ega e beha io ,” in Sma G idComm, 2012. [19] H. Hao, B. Sanandaji, K. Poolla, and T. Vincen , “Agg ega e lexibili y o he mos a ically con olled loads,” Powe Sys ems, ol. 30, 2015. [20] H. Cai, A. Hu e , E. Oli e o, P. Rodui , and P. Fe ez, “Load shi ing o e ia y con ol powe p o ision,” in POWERENG, 2015. [21] T. Logen hi an, D. S ini asan, and A. M. Khambadkone, “Mul i-agen sys em o ene gy esou ce scheduling o in eg a ed mic og ids in a dis ibu ed sys em,” Elec ic Powe Sys ems Resea ch, ol. 81, 2011. [22] T. Logen hi an, D. S ini asan, A. Khambadkone, and H. N. Aung, “Mul iagen sys em o eal- ime ope a ion o a mic og id in eal- ime digi al simula o ,” Sma G id, ol. 3, 2012.