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
© Copyright 2024 ExpyDoc