Università degli Studi di Padova
Dipartimento di Tecnica e Gestione dei Sistemi Industriali
Tesi di laurea magistrale in Ingegneria Gestionale
TECNICHE EURISTICHE PER UN PROBLEMA DI
ROUTING CON FINESTRE TEMPORALI E
CAPACITA’ LIMITATE
Relatore: Ch.mo Prof. GIORGIO ROMANIN JACUR
Laureando: LUCA GELLI
Anno Accademico 2013-2014
Definizione
 Classe di problemi che ha per oggetto lo studio di
tecniche per la pianificazione dei percorsi di una flotta
di veicoli, che svolgono un servizio di distribuzione di
beni materiali, servizi o informazioni tra un insieme di
depositi ed un insieme di clienti caratterizzati da una
domanda nota, nel rispetto di determinati vincoli.
 minimizzare i costi di routing
e di assegnamento dei veicoli
Veichle Routing Problem with Time Windows
(VRPTW)
Versione del VRP che considera i seguenti vincoli:
 Vincolo di capacità: ogni mezzo ha una capacità
limitata;
 Vincolo di tempo: ogni cliente deve essere servito
all'interno di un certo intervallo di tempo rappresentato
dalle finestre temporali (Time Windows).
Risoluzione di un VRP
Algoritmi esatti
 Soluzione ottima
Algoritmi euristici
 Soluzione buona, che si
avvicina all’ottimo
 Tempi di esecuzione
lunghi (ore), che
 Tempi di esecuzione
aumentano
brevi (nell’ordine dei
esponenzialmente
secondi)
all’aumentare delle
 Utilizzo di software
dimensioni del problema
maggiormente diffusi e
 Utilizzo di software
conosciuti che non
specifici, non di uso
richiedono licenze
comune e che
costose (es. Excel)
richiedono licenze d’uso
costose
Ambiente del problema
Deposito/i: luogo dove
sostano e dal quale partono i
mezzi
Macelli: forniscono le pelli
bovine fresche
Conceria: punto di arrivo
delle pelli per la loro
lavorazione
Vincoli
 vincoli di viaggio:
 ogni macello può essere servito da un solo mezzo;
 ogni mezzo deve terminare il proprio percorso alla
conceria;
 vincoli temporali:
 finestre temporali;
 tempo di scarico massimo;
 vincoli di capacità:
 la capacità massima di un mezzo non può essere
superata.
Obiettivo
Trovare un tragitto per ogni camion in uscita dal
deposito in modo da minimizzare il costo totale
Costo totale =
Costo di uscita mezzo +
∑ Costi di carico/scarico +
∑ Costi di viaggio +
Costo del tempo impiegato +
∑ Costi di attesa
Inizializzazione
• Primo macello: macello che presenta il minore costo
dal deposito
Costo =
Costo di carico (i) +
Costo di viaggio (i, j)+
Costo di attesa (i, j)
• Primo mezzo: camion per il quale si genera tale costo
Assegnazione
 Macello con costo di inserzione minore nei percorsi
in costruzione
costo di inserzione =
costo (i, u) + costo (u, j) – costo (i, j)
Oppure: nuovo percorso se
costo dal deposito (u) < costo di inserzione (u)
(per un percorso non
ancora inizializzato)
(per un percorso già
in costruzione)
Calcolo del costo totale finale
Costo di uscita del mezzo
+
Costo complessivo di carico
+
Costo complessivo fisso di viaggio
+
Costo complessivo variabile di viaggio
+
Costo di attesa per il primo macello
Risultati
4
Prima prova: 8 macelli
Algoritmo esatto
Algoritmo euristico di inserzione
(GAMS – Cplex)
(Excel-VBA)
N° camion: 3
• Soluzione: 1010.5
• Tempo impiegato: ~ 4 s
• Soluzione: 1047.3
• Tempo impiegato: ~ 3 s
Scostamento: 3.5%
N° camion: 2
• Soluzione: 1060.1
• Tempo impiegato: ~ 4 s
• Soluzione: 1090.3
• Tempo impiegato: ~ 3 s
Scostamento: 2.8%
Seconda prova: 11 macelli
Algoritmo esatto
Algoritmo euristico di inserzione
(GAMS – Cplex)
(Excel-VBA)
N° camion: 3
• Soluzione: 1152.05
• Tempo impiegato: ~ 11 min
• Soluzione: 1248.15
• Tempo impiegato: ~ 4 sec.
Scostamento: 7.7%
Terza prova: 13 macelli
Algoritmo esatto
Algoritmo euristico di inserzione
(GAMS – Cplex)
(Excel-VBA)
N° camion: 3
• Soluzione: 1226
• Soluzione: 1395.15
• Tempo impiegato: ~ 20 min
• Tempo impiegato: ~ 5 s
Scostamento: 12%
N° camion: 3 (con variazione finestra temporale Macello 8)
• Soluzione: 1226
• Soluzione: 1642.75
• Tempo impiegato: ~ 17 min
• Tempo impiegato: ~ 5 s
Scostamento: 25.4%
N° camion: 2
• Soluzione: 1265.95
• Soluzione: 1335.1
• Tempo impiegato: ~ 8 min
• Tempo impiegato: ~ 5 s
Scostamento: 5.2%
Quarta prova: 20 macelli
Algoritmo esatto
Algoritmo euristico di inserzione
(GAMS – Cplex)
(Excel-VBA)
N° camion: 5
• Soluzione: • Tempo impiegato: -
• Soluzione: 2004.9
• Tempo impiegato: ~ 17 s