Tesina sul Traveling Repairman Problem

UNIVERSITA’ DEGLI STUDI DI MODENA E REGGIO EMILIA
Sede di Reggio Emilia
FACOLTA’ DI INGENGNERIA
Corso di Laurea in Ingegneria Gestionale
TRAVELING REPAIRMAN
PROBLEM
Francesco Torelli
Luca Zeppetella
A.A. 2010/2011
INDICE
• Definizione del problema
• Risolutore esatto del modello
• Risolutore euristico
• Risultati sperimentali su un esempio ridotto
• Risultati sperimentali su “caso CONAD”
DEFINIZIONE
Il TRP nasce come una variante del TSP, il quale si
prefigge di determinare, dato un grafo G(V,E), il
circuito hamiltoniano che minimizzi la distanza
percorsa.
Diversamente il TRP cerca di ottenere, partendo dallo
stesso grafo, un percorso capace di minimizzare i tempi
di attesa dei singoli vertici.
INPUT
• Il file .dat contiene le coordinate x e y dei
vari vertici del grafo.
• I costi tra i punti sono calcolati come
distanze euclidee tra gli stessi.
• La variabile decisionale utilizzata per il
modello è x(i,j,t) = {1 se l’arco (i,j) è
percorso in posizione t, 0 altrimenti}
RISOLUTORE ESATTO del MODELLO
• Il risolutore fa riferimento al modello risolutivo di Bianco,
Mingozzi e Ricciarelli (1993), adattato in base all’esigenza
specifica.
RISOLUTORE ESATTO del MODELLO (2)
Dato che in ultima istanza
abbiamo un arco che unisce l’nesimo vertice con il primo, che in
realtà sono lo stesso, non
Questo
vincolo è stato aggiunto
vogliamo che il tempo
di attesa
rispetto
al sia
modello originale per
relativo all’n-esimo
vertice
che dal deposito di arrivo si
considerato far
duesìvolte.
ritorni a quello di partenza
(deposito 1 e deposito n
coincidono)
RISOLUTORE EURISTICO
• L’ euristico per il TRP prende spunto dal
Closest Neighbor visto per il TSP. Ad ogni
iterazione l’algoritmo seleziona il vertice più
vicino al corrente e lo inserisce in soluzione
facendolo diventare il nuovo punto di
partenza.
• Il costo della soluzione viene aggiornato in
modo differente rispetto al caso TSP.
RISOLUTORE EURISTICO (2)
I costi sono aggiornati
secondo la logica del TRP:
un arco (i,j), percorso in
posizione(iterazione) t, è
pagato (n-t+1) volte
RISOLUZIONE di un SEMPLICE
ESEMPIO
• Consideriamo n=5 vertici t.c.
Vertici del Grafo
Questo punto coincide sia
con il deposito di partenza
che con quello di arrivo
12
10
8
6
4
2
0
0
2
4
6
8
10
RISOLUZIONE di un SEMPLICE ESEMPIO (2)
Risolvendo con il modello esatto si arriva alla
seguente soluzione:
x[1,4,1]= 1
x[2,5,4]= 1
x[3,2,3]= 1
x[4,3,2]= 1
x[5,1,5]= 1
Soluzione esatta
12
10
8
6
4
Questo arco nel grafico
corrisponde ad un punto
per le condizioni imposte
2
0
0
2
4
Il costo della soluzione è pari a 59,229
6
8
10
RISOLUZIONE di un SEMPLICE ESEMPIO (3)
Possiamo vedere come, considerando la funzione
obiettivo come è stata proposta da Bianco (1993),
sarebbero conteggiati anche i costi evidenziati in verde:
0
4,4721
4,4721
8,944
8,944
8,944
6,3246
6,3246
6,3246
6,3246
4,4721
4,4721
4,4721
4,4721
4,4721
4
3
2
5
1
Ordine con cui
sono visitati i
vertici
RISOLUZIONE di un SEMPLICE ESEMPIO (4)
La soluzione nel caso euristico è la seguente:
RISULTATI EURISTICO
zeur = 59.5113
yeur = [1,2,4,3,5]
Soluzione euristica
12
10
8
6
Questo vettore
rappresenta l’ordine con
cui i vertici sono raggiunti
4
2
0
0
2
4
6
8
Si può notare come il costo della soluzione sia in
questo caso maggiore rispetto a quello ottenuto nel
modello esatto, pari a 59,229.
10
RISULTATI SPERIMENTALI
Caso CONAD
• Per sviluppare un esempio significativo abbiamo
ipotizzato che la Parmalat S.p.A. volesse utilizzare un
modello TRP per minimizzare i tempi di attesa per la
consegna del latte da parte dello stabilimento di
Collecchio rispetto ai supermercati della catena Conad
della provincia di Reggio Emilia (approssimando che un
solo mezzo possa servire tutti i punti vendita
individuati)
RISULTATI SPERIMENTALI (2)
Caso CONAD
• Grazie alla funzione “Trova Conad” del sito
www.Conad.it abbiamo reperito gli indirizzi
di tutti i market del gruppo Conad (Conad,
Margherita e E.Leclerc) della provincia di
Reggio Emilia.
RISULTATI SPERIMENTALI (3)
Caso CONAD
• Con Google Earth abbiamo individuato le
coordinate geo-spaziali di ogni singolo
indirizzo.
• Le distanze euclidee tra le coordinate, in
questo caso, sono state moltiplicate per un
fattore centomila in modo da rappresentare
tali distanze in metri.
RISULTATI SPERIMENTALI (4)
Caso CONAD
NOME
INDIRIZZO
Deposito:
VIA NAZIONALE 109
Conad1
VIA TOLSTOJ 2
Conad2
CITTÀ
LONGITUDINE
LATITUDINE
I - 43044 COLLECCHIO (PARMA) 10,13916599975250
44,70907000034720
10,63680900000820
44,70330099939740
VIALE REGINA MARGHERITA 33 I - 42100 REGGIO NELL'EMILIA 10,63651100016080
44,68124999975130
I - 42100 REGGIO NELL'EMILIA 10,61152999953690
44,66113299943830
10,60099199988710
44,70905300011370
I - 42100 REGGIO EMILIA
Conad3
VIA MAIELLA 59
Conad4
VIA FRATELLI CERVI 72-B
Conad5
VIA PARIATI PIETRO 11
I - 42100 REGGIO NELL'EMILIA 10,62561599999030
44,69050200017850
Conad6
VIA TIRELLI EMORE 11
I - 42100 REGGIO NELL'EMILIA 10,71094899982270
44,70949199931070
Conad7
VIA MUZIO CLEMENTI, 2
I - 42100 REGGIO NELL'EMILIA 10,61004800012340
44,69478400003000
Conad8
VIA PORTELLA GINESTRE 28/C
I - 42100 REGGIO NELL'EMILIA 10,60841899991790
44,67469300011620
Conad9
VIA VICO GIAN BATTISTA 29-B
10,55180915417680
44,72601486022450
Conad10
VIA BEETHOVEN 94/E
I - MASSENZATICO (REGGIO E.) 10,69890181518170
44,73415699000190
Conad11
VIA G, BRUNO, 104
I - 42100 REGGIO NELL'EMILIA 10,51703801936370
44,73799699932240
Conad12
VIA LEONARDO DA VINCI 2
I - 42100 REGGIO NELL'EMILIA 10,63380668347740
44,68832508586510
Conad13
VIA CARLO MARX 60
I - 42100 REGGIO NELL'EMILIA 10,57772209345820
44,73389792736740
Conad14
VIA XXV APRILE 1-B
I - 42020 ALBINEA
10,60508365730290
44,62315495171910
Conad15
VIA ANDREA COSTA 1
I - 42011 BAGNOLO IN PIANO
10,67749461833620
44,77074164434340
Conad16
VIA TOSCHI, 77
I - 42031 BAISO
10,60000300015050
44,49602000008370
Conad17
VIA MORANDI 9
I - 42021 BIBBIANO
10,47559561913950
44,66093780602930
Conad18
VIA RESISTENZA 17
I - 42036 BUSANA
10,33232600385290
44,38851400732130
I - PIEVE (REGGIO EMILIA)
I - CELLA (REGGIO EMILIA)
Conad19
Conad20
Conad21
Conad22
Conad23
Conad24
Conad25
Conad26
Conad27
Conad28
Conad29
Conad30
Conad31
Conad32
Conad33
Conad34
Conad35
Conad36
Conad37
Conad38
Conad39
Conad40
Conad41
Conad42
Conad43
Conad44
Conad45
Conad46
VIA MONSIGNOR G, SACCANI 46
PIAZZA MATTEOTTI 42/44
VIA DI VITTORIO 1/8
VIA CANALE 29
VIA ROMA 6
VIA FONTANESI 19
VIA REPUBBLICA 35
VIA RIVASI 6-A
VIA TONDELLI 4
VIA DON MINZONI 27/29
VIA EDMONDO DE AMICIS
STRADA PROV. CAMPEGINE
PIAZZA CERVI 67
VIA DI VITTORIO 10
VIA CISA LIGURE
VIA TOMBA 6
GAL. MAESTRI DEL LAVORO,3
VIA ROMANA 70
VIA F,LLI CERVI 28
VIA GIUSEPPE DI VITTORIO 39/H
VIA TADDEI 11-B
VIA KENNEDY 2
VIA GUGLIELMO MARCONI 5/9
VIA NICOLINI 2
VIA ROMA, 67
VIA EMILIA EST 32/A
VIA S, MATTEO 56-2
VIA CORTI BONAVENTURA 35-D
I - 42023 CADELBOSCO SOPRA
I - CIANO D'ENZA (CANOSSA)
I - 42033 CARPINETI
I - 42016 CASALGRANDE
I - 42034 CASINA
I - FELINA (CASTELNUOVO)
I - 42025 CAVRIAGO
I - 42025 CAVRIAGO
I - 42015 CORREGGIO
I - 42015 CORREGGIO
I - 42042 FABBRICO
I - GATTATICO (TANETO)
I - 42043 GATTATICO
I - 42044 GUALTIERI
I - 42016 GUASTALLA
I - 42045 LUZZARA
I - 42017 NOVELLARA
I - 42028 POVIGLIO
I - 42020 QUATTRO CASTELLA
I - PUIANELLO (4 CASTELLA)
I - 42030 QUATTRO CASTELLA
I - 42020 QUATTRO CASTELLA
I - 42046 REGGIOLO
I - 42010 RIO SALICETO
I - 42047 ROLO
I - 42048 RUBIERA
I - 42020 SAN POLO D'ENZA
I - 42019 SCANDIANO
10,59035918342270
10,65225891284620
10,51545299971800
10,74211600009260
10,49824464366290
10,45422560616880
10,53201257094380
10,52472868704180
10,79166228340640
10,78901400007130
10,81113566357880
10,45554977652940
10,47516600030900
10,62775734020790
10,65292799980970
10,69239915737470
10,72647679099860
10,54633427298960
10,53813332146290
10,56476000011690
10,56483900013290
10,52866699982850
10,80478728105950
10,80592000002650
10,86212325671760
10,78713304667250
10,42608220440040
10,69412599987670
44,76478348750440
44,91969829700790
44,45646499997590
44,58783700017360
44,50969016821420
44,45128280433610
44,69352566684070
44,69649623590350
44,76653460064270
44,76498499992270
44,87421114134800
44,77165668206240
44,80425900010450
44,89911459015270
44,91456700015100
44,95612095600280
44,84431868738560
44,83934303532850
44,63211611632740
44,62619200036510
44,62670700006400
44,62730000017520
44,91943524157720
44,81023999991050
44,88469369228920
44,65237114509190
44,62558201542640
44,59535499950540
Conad47
VIA MAZZINI 72/1
I - 42019 SCANDIANO
10,68204995566180
44,59711711019490
Conad48
Conad49
Conad50
Conad51
VIA BERGIANTI 1
VIA BRUGNOLETTA, 16
PIAZZA MARCONI 5
VIA CASELLE, 4/A
I - ARCETO (SCANDIANO)
I - 42019 SCANDIANO
I - 42020 VETTO
I - 42030 VIANO
10,71672743393080
10,69342900021030
10,33839699985030
10,61865477024520
44,61584569447560
44,61110300009360
44,48462400033400
44,54338595214900
RISULTATI SPERIMENTALI (5)
Caso CONAD - SOLUZIONE OTTENUTA
Dopo 26 ore di risoluzione il modello non ha fornito la
soluzione esatta ma per motivi pratici abbiamo
arrestato il programma, infatti dato l’andamento
asintotico del gap non ci sono sufficienti probabilità di
colmare un valore del 23% in tempo utile.
Mostriamo la soluzione corrente al momento della
sospensione del risolutore che può essere interpretata
con un Lower Bound della soluzione ottima.
RISULTATI SPERIMENTALI (6)
Caso CONAD - SOLUZIONE OTTENUTA
Deposito
Parmalat
Grafo soluzione
corrente (LB)
RISULTATI SPERIMENTALI (7)
Caso CONAD - SOLUZIONE OTTENUTA
Andamento della
ricerca delle
soluzioni
RISULTATI SPERIMENTALI (8)
Caso CONAD - SOLUZIONE OTTENUTA
Stato della
risoluzione al
momento della
sospensione
Valore di Gap non
ancora colmato e
numero di
soluzioni trovate
Otteniamo un costo della soluzione pari a
7.54332e+006.
RISULTATI SPERIMENTALI (9)
Caso CONAD - SOLUZIONE EURISTICA
L’inizializzazione del problema e il risultato in
dettaglio sia nel caso euristico che esatto vengono
forniti tramite il file Excel allegato alla presentazione
data la difficoltà a riportare una serie così lunga di
valori.
Si ottiene in questo caso un costo della soluzione pari
a 7.70561e+006.
RISULTATI SPERIMENTALI (9)
Caso CONAD - SOLUZIONE EURISTICA
Deposito
Parmalat
GRAZIE

Download Report