Università degli Studi di Bologna
FACOLTÀ DI INGEGNERIA
Corso di Laurea in Ingegneria Gestionale
Ricerca Operativa
Algoritmi euristici per
l’ottimizzazione dell’offerta nella
raccolta di rifiuti
Tesi di laurea di Nicola Bindini
Relatore: Chiar.mo Prof. Ing. DANIELE VIGO
Correlatori: Chiar.mo Prof. Ing. PAOLO TOTH
Chiar.mo Prof. Ing. ALBERTO CAPRARA
Obiettivo della tesi
Realizzazione di uno strumento software, per la gestione
del servizio di raccolta dei rifiuti, con un’ interfaccia
utente semplice ed immediata.
 Lo strumento è stato realizzato con Visual Basic 6.0
Il programma si compone di 18 progetti integrati, gestiti da un
progetto principale (main).
Ogni progetto è chiamato per svolgere specifiche funzioni, al
termine delle quali restituisce il controllo al main.
Nello stadio finale il software si interfaccia con un ottimizzatore
per la determinazione della soluzione ottima
Il servizio di raccolta di rifiuti
I rifiuti sono accumulati in contenitori di diversi tipi e con
differenti capacità
I contenitori sono riuniti in postazioni, destinate a soddisfare la
domanda di un bacino di utenza
Le postazioni appartengono a zone, servite con lo stesso profilo di
svuotamento, durante un unico viaggio
Pianificazione del servizio di raccolta:
Individuazione delle Frequenze di servizio da adottare nelle varie
zone
Dimensionamento delle postazioni (numero e tipo di contenitori
impiegati)
Dati di partenza
E’ stata necessaria una riorganizzazione dei dati forniti dalle aziende
erogatrici del servizio di raccolta rifiuti con cui si è collaborato
Costruzione di un database relazionale con Microsoft Access
La base di dati si compone di più tabelle referenziate, le principali
sono:
• Tabella ANAGRAFICA CASSONETTO
• Tabella POSTAZIONE
• Tabella OSSERVAZIONI
Architettura del programma
Il programma si compone di 4 fasi principali :
Fase 0: interfacciamento con la base di dati
Fase 1: analisi della domanda
Fase 2: scelta dei profili di svuotamento
Fase 3: determinazione della configurazione
ottima
Una generica fase si presenta all’utente sotto questo
aspetto:
FASE 0
In questa fase si eseguono 2 operazioni fondamentali:
1) Creazione di un nuovo progetto
• Nome del progetto
• Cartella di lavoro
• Data di inizio pianificazione
2) Creazione di una connessione col database
2 dei 18 progetti componenti il programma sono dedicati alla gestione
della connessione all’esportazione di informazioni tramite query
Nella fase 0 viene generata una copia clone del database di
origine su cui si eseguiranno gli update dovuti alle scelte
dell’utente e propri del particolare progetto in esecuzione
Ad esempio la scelta
delle postazioni da
includere nell’analisi
richiede un’operazione
di aggiornamento della
base di dati
FASE 1
In questa fase viene eseguita l’analisi della domanda
Sulla base dei dati raccolti nella campagna di osservazioni, tramite regressione
lineare, si determina una legge di riempimento per ogni postazione
All’utente vengono mostrate le situazioni che presentano tassi di
riempimento poco attendibili e viene data la possibilità di correggere tali
valori manualmente
5000
4000
3000
2000
1000
0
16/04/01
17/04/01
18/04/01
19/04/01
FASE 2
In questa fase vengono determinate le frequenze di
servizio di ogni zona sulla base di due passi:
PASSO 1: individuazione delle frequenze ideali per ogni postazione
PASSO 2: determinazione della frequenza attuale ideale di zona che
coincide con quella delle postazioni critiche di tale zona
La determinazione dei
profili è ottenuta sulle base
di regole di associazione di
un frequenza ad un
intervallo di svuotamento.
FASE 3
E’ la fase conclusiva del programma, termina
con l’individuazione della configurazione ottima,
si compone dei seguenti passaggi:
• raccolta dei parametri di costo di servizio
• Preparazione file di input per il risolutore
• Chiamata dell’ottimizzatore
• Recupero e interpretazione del file di output contenente i
risultati
Ottimizzatori
L’utente per eseguire la fase 3
deve scegliere quale dei due
ottimizzatori a disposizione
utilizzare
RSUeur: è un eseguibile scritto in linguaggio c, integrato al
programma, che basa la ricerca della soluzione ottima su un
algoritmo di tipo euristico
RSUopt: si appoggia a CPLEX, un risolutore commerciale
esterno al programma che attraverso un’ esplorazione
intelligente dei nodi corrispondenti alle soluzioni ammissibili
va a determinare quella ottima.
Sperimentazione: il caso Firenzuola
SITUAZIONE ATTUALE
Il territorio è suddiviso in 24 zone:
23 servite con frequenza bisettimanale
1 servita sei volte alla settimana
Sono presenti 344 cassonetti, collocati in 270 postazioni.
Sono a disposizione tre tipi di cassonetti : 1100lt, 1300lt, 1700lt.
L’attuale mix di utilizzo è il seguente:
Tipo di cassonetto
Cassonetti utilizzati
1100lt
1300lt
1700lt
2
339
5
SOLUZIONE PROPOSTA DALL’ALGORITMO EURISTICO
1106
Conf. Attuale
942
710
346
738
Sol. RSUopt
369
Totale
Contenitori
Totale Svuot.
Totale Visite
Mantenimento delle frequenze di servizio attuali
Aumento del numero di cassonetti e conseguentemente del numero
di svuotamenti dovuto al attuale sottodimensionamento di molte
postazioni
Aumento del numero di visite settimanali
I costi di servizio passano da 9244€ a 10273€ (incremento del 11%)
SOLUZIONE DEL MODELLO CON CPLEX
1135
Conf. Attuale
942
Sol. CPLEX
710
612
494
346
Totale
Contenitori
Totale Svuot.
Totale Visite
Un aumento considerevole del numero di cassonetti ha consentito ad
11 zone il passaggio da frequenza 2 a frequenza 1.
Riduzione del numero di visite settimanali
I costi variabili di servizio passano da 9244€ a 9047€ con una
riduzione del 2%, a fronte dell’acquisto di numerosi cassonetti
Conclusioni
Si è realizzato un software di ausilio in un’attività come quella
della pianificazione della raccolta dei rifiuti in cui le variabili
in gioco sono molteplici
Lo strumento è utilizzabile sia come ripianificatore di una
situazione attuale inefficiente, sia come analizzatore di scenari
per una piena comprensione dell’impatto sul sistema di scelte
differenti .
Testando il programma in più situazioni ha sempre mostrato
di poter generare soluzioni che consentono efficienze di
costo pur garantendo la qualità del servizio.