--- title: "Algorithms for Fair Load Shedding in Developing Countries" authors: - "Olabambo I. Oluwasuji" - "Obaid Malik" - "Jie Zhang" - "Sarvapali D. Ramchurn" doi: "10.24963/ijcai.2018/220" url: "https://ijcai.org/proceedings/2018/220" pdf: "https://ijcai.org/proceedings/2018/0220.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "1590-1596" track: "Main track" keywords: - "Multidisciplinary Topics and Applications: Computational Sustainability" - "Humans and AI: Personalization and User Modeling" --- # Algorithms for Fair Load Shedding in Developing Countries Olabambo I. Oluwasuji, Obaid Malik, Jie Zhang, Sarvapali D. Ramchurn *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 1590-1596. DOI: [10.24963/ijcai.2018/220](https://doi.org/10.24963/ijcai.2018/220) ## Abstract Due to the limited generation capacity of power stations, many developing countries frequently resort to disconnecting large parts of the power grid from supply, a process termed load shedding. During load shedding, many homes are left without electricity, causing them inconvenience and discomfort. In this paper, we present a number of optimization heuristics that focus on pairwise and groupwise fairness, such that households (i.e. agents) are fairly allocated electricity. We evaluate the heuristics against standard fairness metrics in terms of comfort delivered to homes, as well as the number of times they are disconnected from electricity supply. Thus, we establish new benchmarks for fair load shedding schemes. ## Full text ## 1 Introduction Load shedding entails systematically and deliberately cutting off the supply to parts of the system network, so that the strain on the system is reduced and the failure of the entire system is prevented. It is very common in developing countries, especially because generation capacity is insufficient for meeting demand, and grid infrastructure is poorly maintained or obsolete. In Nigeria for instance, the total installed capacity of generating plants is under 8000MW, which is grossly inadequate for serving a population of over 170 million people [Oyedepo, 2012]. This suggests that there is a perpetual need for implementing load shedding to maintain grid stability in some developing countries. On the other hand, energy demand is increasing globally [Mahadevan and Asafu-Adjaye, 2007]. As such, load shedding will be a prevalent problem that will be relevant for the near future. It is noteworthy that the availability of electricity presents a platform for fighting poverty, improving the welfare of individuals and progressing in development. Therefore, while on the long road towards increasing generation capacity, it is absolutely necessary to develop solutions for managing load shedding events better. Currently, solutions for load shedding involve selecting parts of the system whose consumption closely matches the deficit (i.e. the difference between electricity available for supply, and demand), then disconnecting these parts from electricity supply. For instance, artificial neural networks were used for determining the minimum amount of load to be shed in order to maintain grid stability [Mitchell et al., 2000; Hsu et al., 2005]. Following this, parts of the system that make up this load were disconnected at the supply level. By determining the minimum amount of load shedding required for maintaining grid stability, they resulted in load shedding being more optimal. However, these current approaches do not give due consideration to how fair selection processes are. As such, as far as load shedding results in the stability of the network, no priority is given to ensuring that all parts of the power system benefit from electricity allocation as equally as possible. A consequence of this is that many homes within some parts of the system may be left without supply for days or weeks. Moreover, for electricity providers, load shedding may result in revenue loss, as more load than is required may be shed when disconnecting parts of the system from supply. In light of the above, we present a novel approach to load shedding. Our approach models homes as agents, each with its own preferences for consuming energy. We build this approach on the back of intensive and extensive research into fair-division allocation of heterogeneous resources, often termed as "cakes", for which agents have different and conflicting interests [Varian, 1974; Robertson and Webb, 1998; Moulin, 2003; Brˆanzei et al., 2013]. In the research area, the objective is to allocate these heterogeneous resources to agents in a fair manner, while maximizing social welfare. As such, our model attempts to manage load shedding so that electricity is fairly allocated across agents, hence maximizing the access to electricity. In addition, our model attempts to increase revenue for suppliers through allocating electricity to agents individually. Our work advances the state of the art as follows: 1. We perform a comparative analysis on four different heuristics which consider varying, and sometimes conflicting fairness criteria. These fairness criteria include the number of times each agent is disconnected, the discomfort inflicted on individual agents by being disconnected, the number of agents disconnected and the comfort costs incurred by the power system. 2. By combiningmultiple sources of data, we create a dataset relevant to Nigeria from disaggregated electricity consumption data collected from Pecan Street's Dataport 1 . 3. Using the data described above, we evaluate our load shed- 1 Dataport is the largest provider of disaggregated customer energy data [Parson et al., 2015] ding algorithms and show how they perform in optimizing utilitarian and egalitarian social welfare, as well as in minimizing envy (defined in Section 4). Taken altogether, our heuristic algorithms establish a novel approach to load shedding algorithm design, and establish fairness benchmarks for such algorithms. The rest of the paper is organized as follows. In Section 2, we show how we create a relevant dataset by combining multiple sources of data. Section 3 presents four heuristic household load shedding algorithms, while Section 4 analyzes the performance of the algorithms against some standard fairness metrics. Section 5 concludes. ## 2 Simulating Developing Country Energy Consumption Data In order to implement and evaluate our fair load shedding schemes, we first focus on developing a realistic simulation of energy consumption that can be attributed to homes in developing countries. In particular, we focus on domestic consumption in Nigeria 2 , where the residential sector accounts for 51.3% of consumption [Nwachukwu et al., 2014]. Because consumption data of households is not currently available for households in Nigeria as well as in most, if not all African countries, we collect readily available household consumption data of households in the USA, and adapt it to the Nigerian context. We do this based on some identified similarities between how electricity is consumed in households within both countries. In 2010, the average consumption of an electrified household in Nigeria was 570kWh. In contrast, 11, 698kWh of electricity was consumed by a USA home in the same year 3 . A reason for the wide contrast is the difference between the average temperature of the two countries. The temperature in the USA is such that, on average, a home in the country expends energy on heating. For instance, in 2010, 41.5% of the average electricity consumed within a home in the USA was expended on heating, while 17.7% was expended on water heating. In turn, only about 16% of the average electricity consumed within homes in Nigeria is expended on cooling [Yohanna et al., 2013]. Another reason for the difference in the average electricity consumed between households in both countries is that, on average, homes in Nigeria are poorer than those in the USA. This factor directly impacts on the appliances used within a home. Thereupon, based on disaggregated data available on Dataport, we consider the appliances commonly used in a typical home in the USA and in Nigeria. From Dataport, Figure 1 typifies a representation of the number of occurrences of each appliance category across over 700 households in the USA [Parson et al., 2015]. Conversely, studies show that the appliances typically available in an electrified home in Nigeria include lighting, televisions, electric fans, DVD players, washing machines, electric irons, air conditioners, refrigerators, sewing machine and water pumps [Oji et al., 2012; Salmon and Tanguy, 2016; Emodi et al., 2017; Monyei et al., 2018] 4 . Hence, we extract the data for the appliances that are common to both countries from Dataport. These include the data for air conditioners, washing machines, light bulbs and refrigerators. Likewise, to factor in weather considerations, we collect the usage data of these appliances over 13 weeks of the summer (from the first week in June to the last week in August) for households in only Austin, Texas, one of the warmest states in the USA 5 . This results in the data for 372 households. We aggregate these to make up overall household electricity consumption for each of these households. In the next section, we present four heuristic household load shedding algorithms. 2 Nigeria's energy situation is representative of challenges in Africa. 3 https://goo.gl/DTJVY5 4 See also https://goo.gl/1CheJc Figure 1: Number of appliance occurrences in households (Dataport). ![Image](https://ijcai.org/proceedings/2018/fulltext/220/image_000000_c786d58c28c6559c0a7608831a3b66d390141e74b39045ec9b01f9924b258907.png) ## 3 Managing Loads at the Household Level Our approach to load shedding proposes that shedding be planned ahead. With estimates of electricity available for supply from energy suppliers (i.e. operators) and day-ahead predictions of household consumption, information that is useful for planning load shedding a day ahead is available. Additionally, our approach proposes that load be shed at the household level, rather than at substation level, where parts of the grid are disconnected from supply. This ensures that revenue is maximized for the operator, and electricity that may be wasted is instead supplied to agents. As an example, suppose the deficit is 100kWh and a part being shed constitutes a load of 150kWh. Then, a 50kWh load that would otherwise have produced revenue for the supplier and distributed among agents is lost. In contrast, if load is shed at the household level, a far more closer match to the deficit can be consistently achieved. Notably, our approach is based on previous research [Keelson et al., 2014; Azasoo and Boateng, 2015], where smart retrofitted household electric meters were designed for use in developing countries. The retrofits employ GSM (Global System for Mobile communication) modules as a medium of connection between individual meter and operator. This not only provides individual meters the ability for transmitting usage data securely, but also the ability for being remotely disconnected and re-connected. The retrofits are also inexpensive (less than $10 per unit if mass produced) and can be installed on existing meters. Based on these studies, we assume household-level load control. To this end, in the remain- 5 The average temperature in Austin over summer is roughly the same as that in Nigeria (See http://www.holidayweather.com/austin/averages/ and http://www.holidayweather.com/lagos/averages/). ``` Input : H, lt i , G, L Output: St 1 for EACH HOUR t ∈ {1, 2, . . . , 24} do 2 if dt > 0 then 3 C = H ; // Set of agents available 4 L′ = L ; // Consumption of all agents in C 5 St = P = {} ; // Create empty sets 6 L∗ = 0 ; // Initiate variable 7 while L′ > dt do 8 random.sample hi ∈ C ; // Random selection 9 St .add(hi) ; // Add agent to St 10 C.remove(hi) ; // Remove agent from C 11 L∗ = L∗ + lt i ; // Update consumption sum 12 L′ = L′ - lt i ; // Update consumption sum 13 if L∗ > dt then 14 P.add(St ) ; // Add set to set of sets 15 St = {} ; // Remove all agents in St 16 compute(NS∀St ∈ P) ; // Sum of selected times 17 houses_shed(St ) minNS ; // Shed set with minimum ``` Algorithm 1: Grouping, then selecting a group of agents for disconnection (i.e. Grouper Algorithm). der of this section, we present and assess the performance of four heuristic approaches to shedding load at the household level. ## 3.1 Heuristic Household Load Shedding Algorithms In designing the heuristics, the parameters used are herein defined. Let an agent be represented as hi and H be the set of n agents. Then, the hourly consumption for each agent at hour, t ∈ {1, . . . , 24}, is represented as lt i . Given this, the aggregated hourly demand of the population of agents is defined as L = {∑ni=1 lt=1 i , . . . , ∑ni=1 lt=24 i }. Similarly, the hourly supply capacity available for the population of agents is represented as G = {Gt=1 , . . . ,Gt=24 }. The hourly shortage (or deficit) is then calculated as the difference between the load L and the supply G as D = {Lt=1 -Gt=1 , . . . , Lt=24 - Gt=24 } = {dt=1 , . . . , dt=24 }. Let St represent the set of m agents to be disconnected at hour t, and Lt∗ represent the hourly consumption of agents in St , such that Lt∗ = ∑mi=1 lt i . Let nti be 1 or 0 for each hour an agent is disconnected or connected respectively. Let Ni represent the aggregated number of times each agent is disconnected. Let NS be the sum of the aggregated number of times all agents in set St are disconnected. We now proceed to describe the heuristic algorithms. ## Grouper Algorithm The first heuristic algorithm creates different sets of agents, such that each set's total consumption is enough to offset the deficit. Then, the algorithm selects the set with the minimum total aggregated number of sheds NS, and disconnects all agents contained in the selected set from supply. The heuristic algorithm is described in Algorithm 1. In Algorithm 1, for each hour there is a deficit, load shedding action is initiated (Line 1-2). To shed load, a set of agents whose sum of consumption is enough to offset the deficit will be disconnected from supply. To prepare for this, some empty sets and variables are created (Line 3-6). Agents are added one after the other into a set St , until the sum of consumption of agents yet to be selected is not enough to offset the deficit (Line 7-15). These agents are selected randomly from the population (Line 8), added into St (Line 9) and removed from the population C (Line 10). Every time an agent is selected, the sum of consumption of agents in St and C is updated (Line 11-12). Once the sum of consumption of agents in St is enough to offset the deficit (Line 13), St is added to another set P (Line 14). After this, all the agents in St are removed and the selection process begins again (Line 15). When all sets have been created, the total number of times the agents in these sets have been disconnected (NS) is aggregated (Line 16). The set with the minimum aggregated disconnection is taken off electricity supply (Line 17). We adopt this algorithm as the baseline. The next algorithms attempt to personalize the consideration given to the number of times households are disconnected. ## Consumption-Sorter Algorithm The second heuristic employs a scheme whereby when an agent hi is disconnected, it is not disconnected again until all other agents have been disconnected the same number of times as itself. Thus, it seeks to achieve some sort of fairness in terms of disconnections of individual agents. The heuristic algorithm is describes in Algorithm 2. Algorithm 2: Using consumption to select agents for disconnection while minimizing the difference in the number of times all agents are selected (i.e. Consumption-Sorter Algorithm). ``` Input : H, lt i , G, L Output: St 1 C = H ; // Set of agents available for shedding 2 for EACH HOUR t ∈ {1, 2, . . . , 24} do 3 if dt > 0 then 4 St = {} ; // Create empty set 5 L∗ = 0 ; // Initiate variable 6 C.descend_sort(lt ) ; // Sort using consumption 7 while L∗ < dt do 8 select_ith hi ∈ C ; // Select in order 9 St .add(hi) ; // Add agent to St 10 C.remove(hi) ; // Remove agent from C 11 L∗ = L∗ + lt i ; // Update total consumption 12 if C = {} then 13 C = H -St ; // Repopulate set 14 houses_shed(St ) ; // Shed selected agents ``` In Algorithm 2, all agents in the population are made available for selection before the first shedding event (Line 1). Then, whenever there is a deficit, load shedding action is initiated (Line 2-3). At the beginning of every shedding event, an empty set St to be populated with agents that will be disconnected is created (Line 4). A variable that represents the sum of the consumption of agents in St is also initiated (Line 5). The selection process aims to pick agents in a decreasing order of their consumption. As such, agents are sorted in this order (Line 6). Agents are added one after the other into St , until the sum of consumption of agents in St is enough to offset the deficit (Line 7-13). These agents are selected in order from the set C (Line 8), added into St (Line 9) and removed from C (Line 10). Every time an agent is selected, the sum of consumption of agents in St is updated (Line 11). Set C is repopulated with agents in the entire population H that have not already been selected, if it becomes empty in the middle of a selection process (Line 12-13). After the selection process, the agents in St are disconnected from electricity supply. The Consumption-Sorter Algorithm attempts to maintain the similarity between the number of times households were disconnected. However, the algorithm selected agents in order of their consumption. The next algorithm is designed to be agnostic to the consumption of the agents. ## Random-Selector Algorithm The Random-Selector heuristic differs from the Consumption-Sorter heuristic in that it does not arrange agents based on their consumption, and so does not select agents for disconnection in any particular order. Instead, in an attempt to avoid a bias based on consumption, it randomly selects agents for disconnection during shedding events. The heuristic algorithm is describes in Algorithm 3. Algorithm 3: Selecting agents to shed while keeping the similarity between number of times all agents are selected (i.e. Random-Selector Algorithm). ``` Input : H, lt i , G, L Output: St 1 C = H ; // Set of agents available for shedding 2 for EACH HOUR t ∈ {1, 2, . . . , 24} do 3 if dt > 0 then 4 St = {} ; // Create empty set 5 L∗ = 0 ; // Initiate variable 6 while L∗ < dt do 7 random.sample hi ∈ C ; // Random selection 8 St .add(hi) ; // Add agent to set 9 C.remove(hi) ; // Remove agent from set 10 L∗ = L∗ + lt i ; // Update total consumption 11 if C = {} then 12 C = H -St ; // Repopulate set 13 houses.shed(St ) ; // Shed selected agents ``` As aforementioned, agents are selected randomly from C (Line 7). Otherwise, the description of the algorithm is similar to that of Algorithm 2. Inasmuch as the Grouper, Consumption-Sorter and Random-Selector algorithms have, to some extent, been fair when selecting agents, they have not directly considered the comfort costs of agents when making these selections. The next heuristic aims to factor this into consideration. ## Cost-Sorter Algorithm The fourth heuristic uses comfort costs I (defined in Section 4.1) in selecting agents for shedding. The heuristic aims to select agents with the least comfort costs, while maintaining a parity between the number of times agents are disconnected. It is described in Algorithm 4. In contrast to the heuristics implemented using Algorithms 2 and 3, the comfort costs of agents for the hour of load shedding are collected (Line 4). In addition, agents are sorted in Algorithm 4: Using agent comfort costs to select agents to shed, while keeping the similarity between number of times all agents are selected (i.e. Cost-Sorter Algorithm). ``` Input : H, lt i , G, L, Ii Output: St 1 C = H ; // Set of agents available for shedding 2 for EACH HOUR t ∈ {1, 2, . . . , 24} do 3 if dt > 0 then 4 READ Ii(t) ; // Collect Comfort values for t 5 St = {} ; // Create empty set 6 L∗ = 0 ; // Initiate variable 7 C.ascend_sort(δt i ) ; // Sort by comfort values 8 while L∗ < dt do 9 select_ith hi ∈ C ; // Select in order 10 St .add(hi) ; // Add agent to set 11 C.remove(hi) ; // Remove agent from set 12 L∗ = L∗ + lt i ; // Update total consumption 13 if C = {} then 14 C = H -St ; // Repopulate set 15 houses_shed(St ) ; // Shed selected agents ``` an increasing order of comfort costs (Line 7). Then, they are selected for disconnection in this order (Line 9). Otherwise, the description of the algorithm is also similar to that of Algorithm 2. Summarily, the Grouper Algorithm randomly selects households into different groups until the aggregated consumption of the households in each group is just enough to offset the deficit, then disconnects the group with the least total number of disconnections from supply. The ConsumptionSorter, Random-Selector and Cost-Sorter algorithms keep the number of times agents are disconnected as close as possible by using a queuing system to exempt a selected agent from disconnection, until all other agents have been disconnected after it. While the Consumption-Sorter Algorithm creates an order of selection using consumption, the Cost-Sorter Algorithm does the same using cost. The Random-Selector randomly selects in no particular order. We evaluate these heuristics in the section that follows. ## 4 Performance Evaluation of Heuristic Algorithms In this section, we assess the heuristics in Section 3.1 against some fairness criteria that include the number of times each agent is disconnected, the number of agents disconnected, the individual discomfort inflicted on disconnected agents and the aggregated comfort cost incurred by the system. We do this using the utilitarian, egalitarian and envy-freeness objectives of economic model designs (defined within this section in Section 4.2). The heuristics are evaluated using the data obtained in Section 2. We begin by defining and formulating comfort costs for each agent. ## 4.1 Formulation of Comfort Costs We define the comfort costs of agents using the amount of electricity they consume within each hour of a week, with respect to other hours of a week. We begin by learning each agent's normal consumption during each hour of the week. We do this based on the premise that the correlations between electricity consumed on unique days of the week are stronger than those over different days of a week over the same season, as opined by [Truong et al., 2013; Do et al., 2016]. For this reason, we assume that an agent's consumption over a week in the same season fully represents the agent's consumption pattern in that season. We learn each agent's normal consumption pattern from historical data of every four prior weeks, so that any changes in consumption patterns is accounted for. Thus for an agent, hi, the normal weekly consumption pattern, Zi, is a vector computed using the following equation. Here, j is the number of weeks. Thereafter, we normalize the vector Zi, so that the normal consumption pattern of all agents falls within the range (ϵ, 1). This forms a vector of comfort costs Ii for each agent. The vector provide two benefits. Firstly, they create a platform on which all agents' consumption patterns can be uniquely quantified, without considering how much electricity the agent consumes with respect to others. The second benefit is an extension of the first, in that comparison between agents becomes possible because all agent's comfort costs are on the same scale. Given this, we define the comfort cost, Ii, for an agent, hi, as: Additionally, we assume that δt i is a cost incurred by the system in supplying a agent at time, t, or the discomfort caused an agent when disconnected at time, t (i.e. nti δt i ). ## 4.2 Fairness Objectives Based on Comfort Costs The computed comfort costs serve as tools for assessing our heuristics against a set of objectives. Some predominant objectives in economic model design are the utilitarian, egalitarian and envy-freeness objectives [Mas-Colell et al., 1995; Leite et al., 2009]. Specifically, [Leite et al., 2009] define the utilitarian objective as the sum of individual utilities of agents. In our domain, we use the comfort costs of agents in calculating these utilities. In calculating these utilities, we consider chore division. Chore division is a dual version of the cake-cutting problem in which the divided resource is undesirable, so that each agent wants to get as little as possible [Peterson and Su, 2009; Dehghani et al., 2018]. In this regard, for all times an agent is disconnected during k number of load sheds, an agent's negative utility is uδ = ∑ks=1 δs i , where δs i is the comfort cost of the agent during the hour of shedding event St . To capture the performance of the heuristics for the whole system, utilitarian social welfare is defined as the addition of aggregated discomfort for n agents, ∑ni=1 δ∗ i , where δ∗ i = ∑ks=1 δs i . Conversely, [Leite et al., 2009] define the egalitarian objective as the utility of the agent that is currently worst off. In our domain, we adopt the egalitarian criterion as the highest individual comfort cost incurred by the system (or highest aggregated negative utility), as defined by gδ = maxi{δ∗ i }. In addition, envy-freeness is a criterion of fair division that allocates resources to agents in such a way that no agent envies the allocation of another. However, agents do not have information of the allocation to others within our domain. For this reason, we adapt envyfreeness in terms of measuring the maximum difference between the comfort allocated to all pair of agents (or maximum difference between aggregated negative utilities), as defined by yδ = {maxi,j{∣∣δ∗ i - δ∗ j ∣∣}}. A fair load shedding scheme should result in the lowest possible eδ, so that if the all agents were aware of all allocations, the aggregate envy will be minimal. Table 1: Comparing fairness objectives, based on comfort costs. | Heuristic | Utilitarian | Egalitarian | Envy-freeness | |--------------------|---------------|---------------|-----------------| | Grouper | 49047.96 | 356.30 | 309.28 | | Consumption-Sorter | 48830.27 | 174.37 | 126.29 | | Random-Selector | 53072.97 | 192.04 | 137.77 | | Cost-Sorter | 52803.38 | 208.69 | 149.07 | Table 1 compares the utilitarian, egalitarian and envyfreeness objectives, based on comfort costs. The Grouper algorithm produces the maximum envyness, but performs admirably under the utilitarian approach to social welfare. The Random-Selector algorithms performs second best under the envy-freeness and egalitarian objectives, but generates the highest utilitarian value. The Cost-Sorter algorithm does not fulfill any of the objectives better than all others. ## 4.3 Fairness Objectives Based on Number of Times Agents are Disconnected In this section, we compare the heuristic algorithms based on the number of times each agent is disconnected. The utilitarian, egalitarian and envy-freeness objectives are adopted herein based on chore division also. In Section 3.1, we defined nti as 1, if an agent is disconnected at hour t, and Ni as the aggregated number of times each agent is disconnected. As such, the utilitarian approach is described as uN = ∑ni=1 Ni in this case. Conversely, the egalitarian approach is described as gN = maxi{Ni}. Finally, for envy-freeness, we employ the definition yN = maxi,j{|Ni - Nj |}. As with the comfort costs, any fair shedding scheme should aim to minimize these values. As seen in Table 2, the Grouper Algorithm fails to outperform others under the egalitarian objective of social welfare and in envy-freeness. The disparity between the number of times agents are disconnected is suggested by its high envyfreeness (in Table 1). However, it fulfills the utilitarian objective better than the Random-Selector and Cost-Sorter algorithms. On the other hand, the Cost-Sorter algorithm achieves its design purpose, as it causes the least discomfort for each household disconnected (as seen in Table 3). Because of the omission technique used within the algorithms, the difference between the number of times all agents are disconnected using the Consumption-Sorter, Random-Selector and Cost-Sorter algorithms is one. Table 2: Comparing fairness objectives, based on number of disconnections. | Heuristic | Utilitarian | Egalitarian | Envy-freeness | |--------------------|---------------|---------------|-----------------| | Grouper | 78159 | 317 | 180 | | Consumption-Sorter | 74857 | 202 | 1 | | Random-Selector | 86307 | 233 | 1 | | Cost-Sorter | 95538 | 257 | 1 | Table 3: Comparing comfort costs incurred per agent disconnected | Heuristic | Costs incurred per agent disconnected | |--------------------|-----------------------------------------| | Grouper | 0.63 | | Consumption-Sorter | 0.65 | | Random-Selector | 0.62 | | Cost-Sorter | 0.55 | The Consumption-Sorter algorithm minimizes all negative utilities best, including those that consider comfort costs and number of disconnections. ## 4.4 Other Performance Considerations As stated in the introduction, an efficient load shedding scheme can be described as one that sheds enough load to offset the deficit, yet minimizes the difference between the deficit and the load shed. All four heuristics work by selecting agents one after the other, until the sum of consumption of the selected agents is enough to offset the deficit. Therefore, to take a closer look at the difference between the loads cut and the deficits, we present the results obtained by the heuristic used as a baseline (i.e. Grouper algorithm) for the first 50 shedding events. Figure 2 shows that the loads cut match the deficits closely. This is because shedding load at the household level gives the heuristics a finer control over the amount of load to be shed, resulting in closer match to the deficit. With regards to this, there is the suggestion that this class of heuristics is efficient. Another consideration is to have a similar proportion of the population of agents shed, based on a factor of the number of agents cut per kWh deficit. That is, if one agent is disconnected when there is a deficit of 1kWh, 100 agents should be disconnected when the deficit is 100kWh. Of course, this factor will not be constant because consumption typically differs over each hour in a day. However, it is desirable that this proportion be similar, so that as much as is possible, an equal proportion of the grid that depends on the deficit is disconnected at each shedding event. Therefore, we compare the proportion of the population of agents shed by all heuristics during the first 50 individual shedding events in Figure 3. As seen in Figure 3, the Grouper algorithm produces the best ratios of agents disconnected to kWh load shed. Conversely, the Consumption-Sorter and Cost-Sorter algorithms produce the most varying effects on the proportion of agents disconnected. This is because the algorithms select in different orders, but maintain the similarity between the number of times agents are selected. The Consumption-Sorter algorithm selects in order of reducing consumption, while the Cost-Sorter selects in order of increasing cost. However, because they both maintain the similarity between number of times agents are shed, the number of agents they select to offset the deficit during shedding events differ more. Figure 2: Deficit and load shed for the first 50 shedding events (Grouper Algorithm). ![Image](https://ijcai.org/proceedings/2018/fulltext/220/image_000001_e2ab690d6376803e887cc5ce2b39503fcf74c0bf52a41b53d32700d775d0de42.png) Figure 3: Number of agents cut off per kWh load shed. ![Image](https://ijcai.org/proceedings/2018/fulltext/220/image_000002_d4efae3eda189a2e17b7a032331a50b4c43d26bb9ed38bb045b89a1bc806cbbf.png) It is noteworthy that we do not aim to determine which heuristic is best, but to present a number of heuristics that can be employed within different environments and conditions. For example, an environment that aims to disconnect a regular number of households during load shedding events may employ the Grouper or Random-Selector heuristic, while another that wants to disconnect as few houses as possible during every load shedding event may implement the Consumption-Sorter or Cost-Sorter. In addition, some components of these heuristics may be combined to a desired effect, as drawn in our conclusions below. ## 5 Conclusions This paper proposed a new approach to load shedding, and presented four heuristic algorithms for shedding load at the household level. Results obtained from the implementation of the heuristics showed the extent to which they satisfied predefined fairness objectives. Although none of the heuristics fulfilled all objectives better than the other, each of them produced some desirable effects. As this is a gap in literature, the proposed class of heuristics can serve as a benchmark for designing load shedding algorithms in the future, and some qualities of individual heuristics can be adapted into designs that suit different environments, based on the desired objectives. Likewise, the heuristics can serve as a benchmark in designing solutions for allocating other scarce resources (e.g. water allocation problems addressed by [Read et al., 2014; zhen Song et al., 2016]). For future work, the fair load shedding problem can be modelled as a goal programming problem where the social welfare objectives modelled in Section 4 are used as objective functions, with constraints dependent on the system's characteristics. ## References 1. [Azasoo and Boateng, 2015] Julius Quarshie Azasoo and Kwame Osei Boateng. A retrofit design science method- ology for smart metering design in developing countries. In 2015 15th International Conference on Computational Science and Its Applications, pages 1-7, June 2015. 2. [Brânzei et al., 2013] Simina Brânzei, Ariel Procaccia, and Jie Zhang. Externalities in cake cutting. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 55-61, 2013. 3. [Dehghani et al., 2018] Sina Dehghani, Alireza Farhadi, Mohammad Taghi Hajiaghayi, and Hadi Yami. Envy-free chore division for an arbitrary number of agents. In Pro- ceedings of the Twenty-Ninth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2564-2583, 2018. 4. [Do et al., 2016] Linh Phuong Catherine Do, Kuan-Heng Lin, and Peter Molnár. Electricity consumption modelling: A case of germany. Economic Modelling, 55(Supplement C):92 -101, 2016. 5. [Emodi et al., 2017] Nnaemeka Vincent Emodi, Chi- nenye Comfort Emodi, Girish Panchakshara Murthy, and Adaeze Saratu Augusta Emodi. Energy policy for low carbon development in nigeria: A leap model application. Renewable and Sustainable Energy Reviews, 68:247 - 261, 2017. 6. [Hsu et al., 2005] Cheng-Ting Hsu, M. S. Kang, and Chuin- Shan Chen. Design of adaptive load shedding by artificial neural networks. IEE Proceedings -Generation, Trans- mission and Distribution, 152(3):415-421, May 2005. 7. [Keelson et al., 2014] Eliel Keelson, Kwame Boateng, and Isaac Ghansah. A Smart Retrofitted Meter for Develop- ing Countries. International Journal of Computer Appli- cations, 90(5):40-46, 2014. 8. [Leite et al., 2009] João Leite, José Alferes, and Belopeta Mito. Resource allocation with answer-set programming. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems -Volume 1, AAMAS '09, pages 649-656, Richland, SC, 2009. IFAA- MAS. 9. [Mahadevan and Asafu-Adjaye, 2007] Renuka Mahadevan and John Asafu-Adjaye. Energy consumption, economic growth and prices: A reassessment using panel vecm for developed and developing countries. Energy Policy, 35(4):2481 -2490, 2007. 10. [Mas-Colell et al., 1995] Andreu Mas-Colell, Michael Whinston, and Jerry Green. Microeconomic Theory. Oxford University Press, 1995. 11. [Mitchell et al., 2000] Matthew Mitchell, Joao Lopes, Nuno Fidalgo, and James McCalley. Using a neural network to predict the dynamic frequency response of a power sys- tem to an under-frequency load shedding scenario. In 2000 Power Engineering Society Summer Meeting (Cat. No.00CH37134), volume 1, pages 346-351 vol. 1, 2000. 12. [Monyei et al., 2018] Chukwuka Monyei, Aderemi Adewumi, Michael Obolo, and Barka Sajou. Nige- ria's energy poverty: Insights and implications for smart policies and framework towards a smart nigeria electricity network. Renewable and Sustainable Energy Reviews, 81:1582 -1601, 2018. 13. [Moulin, 2003] Hervé Moulin. Fair division and collective welfare. MIT Press, 2003. 14. [Nwachukwu et al., 2014] Maxwell Umunna Nwachukwu, Nnena Flora Ezedinma, and Uloma Jiburum. Compara- tive analysis of electricity consumption among residential, commercial and industrial sectors of the nigeria's econ- omy. Journal of Energy Technologies and Policy, 2014. 15. [Oji et al., 2012] John Oji, Nosa Idusuyi, Theophilus Aliu, Moses Petinrin, O. A. Odejobi, and A. R. Adetunji. Uti- lization of solar energy for power generation in nigeria. International Journal of Energy Engineering, 2:54 -59, 2012. 16. [Oyedepo, 2012] Sunday Olayinka Oyedepo. Energy and sustainable development in nigeria: the way forward. En- ergy, Sustainability and Society, 2(1):15, Jul 2012. 17. [Parson et al., 2015] Oliver Parson, Grant Fisher, April Hersey, Nipun Batra, Jack Kelly, Amarjeet Singh, William Knottenbelt, and Alex Rogers. Dataport and nilmtk: A building data set designed for non-intrusive load moni- toring. In 2015 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 210-214, Dec 2015. 18. [Peterson and Su, 2009] Elisha Peterson and Francis Su. N- person envy-free chore division. page 7, 09 2009. 19. [Read et al., 2014] Laura Read, Kaveh Madani, and Bahareh Inanloo. Optimality versus stability in water resource allo- cation. Journal of Environmental Management, 133(Sup- plement C):343 -354, 2014. 20. [Robertson and Webb, 1998] Jack Robertson and William Webb. Cake-cutting algorithms -be fair if you can. A K Peters, 1998. [Salmon and Tanguy, 2016] Claire Salmon and Jeremy Tan- guy. Rural electrification and household labor supply: Evi- dence from nigeria. World Development, 82:48 -68, 2016. 21. [Truong et al., 2013] Ngoc Cuong Truong, Long Tran- Thanh, Enrico Costanza, and Sarvapali D. Ramchurn. To- wards appliance usage prediction for home energy man- agement. In Proceedings of the Fourth International Con- ference on Future Energy Systems, e-Energy '13, pages 287-288, New York, NY, USA, 2013. ACM. 22. [Varian, 1974] Hal Varian. Equity, envy, and efficiency. Journal of Economic Theory, 9(1):63 -91, 1974. 23. [Yohanna et al., 2013] Irimiya Yohanna, Humphery Iortyer, and Aondover Ierve. Assessment of energy use pattern in residential buildings of Kano and Kaduna Northern Nige- ria. American Journal of Engineering Research, 2:271- 275, 2013. 24. [zhen Song et al., 2016] Wan zhen Song, Yuan Yuan, Yun zhong Jiang, Xiao hui Lei, and Dong cai Shu. Rule-based water resource allocation in the central guizhou province, china. Ecological Engineering, 87(Supplement C):194 - 202, 2016.