Formazione di coalizioni per l'uso intelligente di energia

Autore: Andrea Zambon (vr092382)
Data: 24/2/2011

Introduzione

Questo progetto si concentra sulla formazione di coalizioni per l'uso intelligente dell'energia. Si vuole quindi raggruppare una serie di utilizzatori di energia in coalizioni in modo tale che il profilo di consumo di energia cumulativo per ogni coalizione sia il meno variabile possibile. Si vuole, dunque, fare in modo che i picchi di consumo di un utilizzatore di energia siano compensati dai periodi di basso consumo di altri utenti nella stessa coalizione, in modo che il profilo di consumo cumulativo sia il meno variabile possibile. Si vuole inoltre fare in modo che il consumo cumulativo per ogni coalizione non superi un determinato valore massimo.
Quello che si vuole fare è massimizzare la somma dei load diversity factor di tutte le coalizioni. Il load diversity factor di una coalizione è definito come la somma dei picchi massimi di consumo di ogni utente che fa parte di quella coalizione diviso per il picco massimo del conumo aggregato della coalizione. Massimizzando questa quantità si vuole fare in modo che il picco massimo di consumo aggregato sia il più piccolo possibile rispetto alla somma dei picchi di tutti gli utenti, facendo quindi in modo di "incastrare" i consumi degli utenti nella maniera migliore possibile.
Il programma permette, tramite un'interfaccia grafica, di caricare da un file CSV i dati di consumo di un numero specificato di utenti, di scegliere un numero di coalizioni e una dimensione massima per queste per poter poi eseguire l'algoritmo di formazione di coalizioni. L'interfaccia grafica permete anche di visualizzare la migliore soluzione trovata (tramite una serie di grafici a barre) e di modificare manualmente il colore usato per rappresentare ciascun utente (nel caso si voglia evidenziare dove viene allocato un particolare utente).

Descrizione generale dell'algoritmo

L'algoritmo utilizzato è di tipo branch and bound con forward checking, riordinamento dinamico delle variabili e dei valori di ciascuna variabile. Ogni volta che si deve scelgiere la successiva variabile da istanziare si sceglie quella con il maggior numero di valori proibiti dal forward checking, mentre i valori per ogni variabile da istanziare vengono ordinati in base al valore dell'upper bound di ciascuno di essi. La funzione di upper bound utilizzata è piuttosto complessa, quindi si rimanda alla relazione per la spegazione di tale funzione di upper bound. L'algoritmo è realizzato per essere eseguito da un thread separato rispetto a quello che gestisce l'interfaccia grafica, ma è comunque un algoritmo single thread. Altra particolarità dell'algoritmo è che non viene mai usata l'allocazione dinamica di memoria durante l'esecuzione dell'algoritmo vero e proprio (tranne quando si trova una soluzione che migliora la soluzione ottima trovata sinora). Questo permette di evitare problemi dovuti a esaurimenti della memoria e anche i tempi di allocazione dovuti all'uso dell'operatore new. Tutte le strutture dati necessarie per l'algoritmo vengono allocate prima che inizi il ciclo di elaborazione vero e proprio.

Implementazione

Il progetto è stato realizzato in java con Netbeans e usando Swing per l'interfaccia grafica. Il tutto è diviso in vari package:

Risultati

Una descrizione dettagliata dei risultati ottenuti è riportata nella sezione conclusiva della relazione. Per riassumere si può dire che l'algoritmo riesce a risolvere problemi fino a circa 20 utenti e, con certi numeri e dimensioni delle coalizioni, riesce anche a risolvere istanze del problema con un numero di utenti maggiore. Nella relazione è riportata anche una serie di grafici che mostra la qualità della soluzione trovata confrontata con quella prodotta da algoritmi non ottimi come quello che dispone gli utenti in maniera casuale e quello che mette ogni utente in una coalizione diversa.

File del progetto