Optimization heuristics for residential energy load management

The MS thesis is concerned with the problem of scheduling the daily energy loads in a multihouse environment from the point of view of an energy retailer. We assume that the residential users own a set of home appliances (washing machines, dishwashers, ovens, microwave ovens, vacuum cleaners, boilers, fridges, water purifiers, irons, TVs, personal computers and lights) that are supposed to be used during the day. Houses can also be equipped with Photo Voltaic (PV) panels, which produce energy in a discontinuous way, and batteries that allow the system to store and release energy when required. The day is subdivided into 96 timeslots of 15 minutes each. For each appliance, we suppose to know the load profile, that is, a set of successive timeslots with the corresponding amount of energy required. Given the load profile of each appliance, the time windows in which the appliances must be executed, the physical characteristics of the batteries, the energy amount produced by the PV systems, the problem is that of scheduling the various appliances (assigning their starting timeslots) so as to minimize an appropriate objective function while respecting the maximum capacity of the meters (usually 3 kW). We consider minimizing the total maximum peak. This Residential Energy Load Management Problem is a challenging extension of the classical Generalized Assignment Problem (GAP). Since the Mixed Integer Linear Programming (MILP) formulation can be solved within reasonable computing time only for small instances, we developed various methods to tackle medium-to-large size instances: a Greedy Randomized Adaptive Search Procedure (GRASP) to generate initial feasible solutions, a meta-heuristic à la Tabu Search (TS) to improve initial solutions, and other techniques based on the solution of reduced MILP problems. In the TS algorithm we proposed different types of moves (appliances shift, batteries charge or discharge...) to explore the neighbourhood. We have tested our methods on a data set of 180 realistic instances with different number of houses (20, 200 and 400), PV panels and batteries. The solutions provided by the heuristics are compared with those obtained by solving the MILP model by using a state-of-the-art solver. For instances without batteries all our heuristics yield high quality solutions - within 3% from the reference solution - in a short computing time for the largest instances. Heuristics that solve reduced MILPs achieved the same results even for instances with batteries.

La tesi riguarda il problema di organizzare i carichi di energia giornalieri in un ambiente multi case da punto di vista del grossista di energia. Si assume che gli utenti domestici possiedono un set di dispositivi (lavatrici, lavastoviglie, forni, forni a microonde, aspirapolvere, scaldabagno, frigoriferi, purificatori per acqua, ferri da stiro, TV, computer e luci) che vengono utilizzati durante il giorno. Le case possono anche essere dotate di Pannelli Fotovoltaici (PV), che producono energia in modo discontinuo, e batterie che permettono al sistema di immagazzinare energia per rilasciarla quando necessario. Il giorno è suddiviso in 96 timeslot di 15 minuti ciascuno. Per ogni dispositivo si suppone di conoscere il profilo di carico, i. e., un set di timeslot successivi con il corrispondente ammontare di energia richiesta. Dato il profilo di carico di ogni dispositivo, le finestre temporali in cui i dispositivi devono essere attivati, le caratteristiche fisiche delle batterie, l’ammontare di energia prodotta dai sistemi fotovoltaici, il problema è di schedulare le varie attività (assegnando i timeslot di inizio) in modo da minimizzare una funzione obiettivo appropriata e da rispettare la capacità massima (solitamente 3 kW). Si considererà la minimizzazione del picco massimo totale. Il problema della gestione del carico domestico è un’impegnativa estensione del classico Problema di Assegnamento Generalizzato (GAP). Dato che la formulazione di Programmazione Lineare Mista Intera (MILP) può essere risolta in tempo ragionevole solamente per piccole istanze abbiamo sviluppato diversi metodi per affrontare istanze medio-grandi: un algoritmo Greedy Randomized Adaptive Search Procedure (GRASP) per generare soluzioni iniziali ammissibili, una meta-euristica à la Tabu Search (TS) per migliorare le soluzioni iniziali, ed altre tecniche basate sulla risoluzione di problemi MILP ridotti. Abbiamo proposto diversi tipi di mosse (spostamento dei dispositivi, carica e scarica delle batterie...) per esplorare il vicinato nell’algoritmo TS. Abbiamo testato i nostri metodi su un data set di 180 istanze realistiche con un diverso numero di case (20, 200, 400), pannelli fotovoltaici e batterie. Le soluzioni fornite dall’euristica sono confrontate con quelle ottenute risolvendo il modello MILP con un risolutore allo stato dell’arte. Per istanze senza batterie tutte le nostre euristiche hanno prodotto soluzioni di alta qualità – entro il 3% dalle soluzioni di riferimento – in breve tempo di esecuzione per le istanze più grandi. Le euristiche che risolvono MILP ridotti hanno raggiunto gli stessi risultati anche per istanze con batterie.