Il problema del commesso viaggiatore: da Ulisse alla

Il problema del commesso viaggiatore:
da Ulisse alla Logistica integrata
Luca Bertazzi
1
0
3
Ulisse: da Troia a Itaca
Troia
Itaca
509 km
Quale è stato invece il viaggio di Ulisse?
Il viaggio di Ulisse
Troia
Itaca
9404 km – 10 anni
Un’Odissea!!
Ottimizzare il viaggio di Ulisse
Ulisse
• poteva percorrere 509 km per tornare a Itaca
• ne ha percorsi 9404 visitando 16 location
Qual è il percorso minimo che parte da
Itaca, visita le 16 location una sola
volta e ritorna a Itaca?
Le 16 location da visitare
Itaca
La soluzione di Ulisse
Troia
Itaca
9404+509 = 9913 km
Qual è invece il percorso ottimo?
Il percorso ottimo
Itaca
6859 km
3054 km in meno!!
1
0
Logistica
3
1
0
1) Gestione della produzione
3
1
0
3
Drilling problems:
Quale percorso
minimizza il tempo
totale di perforazione
del circuito?
1
0
2) Gestione magazzini e scorte
3
Picking problems:
Quale percorso
minimizza il tempo
totale di picking
nel magazzino?
1
0
3) Gestione dei trasporti
3
1
0
3
Routing problems:
Quali percorsi
minimizzano la
distanza totale per
servire i clienti?
1
0
3
1
0
3
4) Logistica integrata
1
0
3
Strategie di
produzione e
spedizione che
ottimizzino:
• Produzione
• Trasporto
• Scorte
sistemi integrati di produzione e distribuzione
RMI: Retailer-Managed Inventory
Ogni retailer decide
la propria politica
di approvvigionamento
VMI: Vendor-Managed Inventory
Il supplier monitora le
scorte dei retailer e
decide quando e come
servire ogni retailer
Da Ulisse alla Logistica integrata
1
0
3
Come determinare il percorso minimo che
parte da Itaca, visita le 16 location una sola
volta e ritorna a Itaca?
Come determinare il percorso minimo
che parte dal produttore, visita i clienti una
sola volta e torna al produttore?
Il problema del commesso viaggiatore
TSP (Traveling Salesman Problem)
Un commesso viaggiatore deve visitare un certo
numero di città. Vuole partire da casa e ritornare
a casa dopo aver visitato ogni città una sola volta,
percorrendo la distanza minima.
2
1
5
3
4
circuito hamiltoniano
a costo minimo
Dati
n : numero di città
cij : distanza dalla città i alla città j
n = 16
Matrice delle
distanze:
Come determinare un circuito hamiltoniano
a costo minimo?
Algoritmo di Nearest Neighbor
- Parto da Itaca
Vado verso la città più vicina (Zakinthos)
- Da Zakinthos vado verso la città più
vicina (Corfù)
- Da Corfù …
-…
- Torno a Itaca
Nearest Neighbor (NN)
Itaca
9988 km
Più di Ulisse (9404)!!
L’algoritmo di NN può generare
soluzioni non ottime
Come determinare un circuito hamiltoniano
a costo minimo?
Un percorso è una delle permutazioni degli n nodi
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16
1-2-3-4-5-6-7-8-9-10-11-12-13-14-16-15
…
Algoritmo di completa enumerazione
- Genero tutte le permutazioni corrispondenti
a soluzioni diverse
- Scelgo la permutazione a costo minimo
L’algoritmo di completa enumerazione genera
sempre una soluzione ottima, ma…
Numero di soluzioni ammissibili:
# permutazioni: n!
# soluzioni diverse: (n-1)!/2
n = 16 ⇒ 15!/ 2 = 653.837.184.000
4 giorni di calcolo su una potente
workstation
Come varia il tempo di calcolo al variare di n?
n
Tempo di calcolo
8
< 1 secondo
16
4 giorni
24
2.076.245 secoli
L’algoritmo di completa enumerazione
può essere impraticabile
Non per questo si deve esagerare…
E. Hofmann, La Repubblica, 24 settembre 2001
“Le farò allora un esempio elementare. Supponga di avere
alle sue dipendenze un rappresentante di commercio che
debba visitare quattro città. Naturalmente vorrà calcolare
il percorso che questo signore deve fare nel modo più
efficiente possibile, in modo da rendere minimi gli
spostamenti e quindi il costo.
Ebbene, con i computer normali, di oggi,
il problema non è risolvibile. Ci si può impazzire sopra
notti intere. Non è risolvibile. Non le dico cosa succede se
poi le città invece di quattro diventano venti.
Le conviene non cominciare nemmeno”.
Il più grande TSP risolto all’ottimo:
85900 nodi
Aprile 2006
Georgia Tech
Alcuni record precedenti:
1987: 666 posti interessanti nel mondo
1998: 13509 città negli USA
2001: 15112 città in Germania
2002: 16862 città in Italia
2004: 24978 città in Svezia
È il più grande
TSP geografico
risolto all’ottimo
Soluzioni ottime nel tempo
Riassumendo…
L’algoritmo di Nearest Neighbor può
generare soluzioni non ottime
L’algoritmo di completa enumerazione
genera sempre una soluzione ottima,
ma può essere impraticabile
E’ stato risolto all’ottimo un problema
con 85900 città
Come è stato possibile ottenere
questo risultato?
Ricerca operativa
metodi quantitativi e scientifici nei
processi decisionali
Logistica
Finanza
Telecomunicazioni
Data Mining
Bio-informatica
Gestione delle Risorse Umane
Gestione dei Servizi Sanitari
…
What-if?
What-is-best?
PROBLEMA
MODELLO
ALGORITMI
software
1) Definizione del problema
Dato un grafo completo e
pesato G=(V,A),
determinare un circuito
hamiltoniano a costo
minimo
PROBLEMA
MODELLO
2
1
1
1
3
2
1
2
1
4
ALGORITMI
software
Dati:
n : numero di città
cij : distanza dalla città i alla città j
n = 16
Matrice delle
distanze:
2) Formulazione di un modello
1) Variabili decisionali:
PROBLEMA
2
1
1
1
3
2
1
2
MODELLO
1
4
L’arco (i,j) appartiene
al circuito?
ALGORITMI
software
Per ogni arco (i,j) si introduce una variabile
binaria che può valere 0 o 1
2
1
1
1
3
2
1
2
1
xij
0 (i,j) non
appartiene
1 (i,j) appartiene
4
x12 ∈ {0,1} x13 ∈ {0,1} x14 ∈ {0,1} x23 ∈ {0,1} x24 ∈ {0,1} x34 ∈ {0,1}
x21 ∈ {0,1} x31 ∈ {0,1} x41 ∈ {0,1} x32 ∈ {0,1} x42 ∈ {0,1} x43 ∈ {0,1}
2) Funzione obiettivo:
PROBLEMA
minimizzare il costo totale
0 se xij = 0
MODELLO
Costo arco (i,j)
cij se xij = 1
n n
Costo totale: ∑ ∑ cij xij
i =1 j =1
ALGORITMI
software
2
1
1
x12 = 1 x13 = 0 x14 = 1
1
3
2
2
1
1
4
x23 = 1 x24 = 0 x34 = 1
x21 = 0 x31 = 0 x41 = 0
x32 = 0 x42 = 0 x43 = 0
Costo totale di questa soluzione:
n n
∑ ∑ cij xij = 1*1 + 2 * 0 + 1*1 + 1*1 + 2 * 0 + 1*1 +
i =1 j =1
+ 1* 0 + 2 * 0 + 1* 0 + 1* 0 + 2 * 0 + 1* 0 = 4
Funzione obiettivo:
minimizzare il costo totale
min
PROBLEMA
MODELLO
n n
∑ ∑ cij xij
i =1 j =1
ALGORITMI
software
3) Vincoli:
PROBLEMA
a) Si deve entrare in
ogni nodo una sola volta
n
∑ xij = 1
i =1
j = 1,2,..., n
b) Si deve uscire da ogni
nodo una sola volta
n
∑ xij = 1 i = 1,2,..., n
j =1
MODELLO
ALGORITMI
software
c) Subtours elimination
PROBLEMA
2
1
1
1
3
2
1
2
1
4
∑ ∑ xij ≤ S − 1 ∀S ⊂ {1,2,..., n}
i∈S j∈S
MODELLO
ALGORITMI
software
Modello:
PROBLEMA
n n
min ∑ ∑ cij xij
i=1 j =1
n
∑ xij = 1 j = 1,2,...,n
MODELLO
i=1
n
∑ xij = 1 i = 1,2,...,n
j =1
∑ ∑ xij ≤ S −1 ∀S ⊂ {1,2,...,n}
i∈S j∈S
xij ∈{0,1} i = 1,2,...,n
j = 1,2,...,n
ALGORITMI
software
3) Applicazione di algoritmi
a) Esatti
PROBLEMA
soluzione ottima
MODELLO
x12 = 0 x12 = 1
Completa enumerazione
Branch-&-Bound
Branch-&-Cut
…
x =1 x = 0 x =1
x13 = 0
13
14
14
ALGORITMI
software
b) Euristici
PROBLEMA
soluzione buona
Nearest Neighbor
Insertion
Lin-Kernighan
Tabu search
Algoritmi Genetici
Simulated Annealing
…
MODELLO
ALGORITMI
software
Obiettivo ideale:
PROBLEMA
- Soluzione ottima
- Tempo polinomiale
MODELLO
ottima
soluzione
euristica
ALGORITMI
software
0
costo
polinomiale
Es: Nearest Neighbor
esponenziale
Es: Completa
enumerazione
tempo
tempo
Per il TSP:
Tempo/Sol.
Ottima
Nearest Neighbor
Insertion
Lin-Kernighan
…
Polinomiale
Esponenziale
Euristica
Completa enumerazione
Branch-&-Bound
Branch-&-Cut
…
Algoritmi esatti polinomiali
Non è mai stato ottenuto un algoritmo
in grado di fornire la soluzione ottima
del TSP in tempi polinomiali
(algoritmo esatto polinomiale)
Inoltre:
Il TSP è NP-hard
Il TSP è NP-hard
Appartiene ad una classe di problemi per i quali:
- non è mai stato trovato un algoritmo esatto
polinomiale
- se si trovasse un algoritmo esatto polinomiale
per uno di questi problemi, ogni problema
della classe avrebbe un algoritmo esatto
polinomiale
Teoria della complessità computazionale
È altamente probabile
che un algoritmo
esatto polinomiale
per il TSP non esista
PROBLEMA
MODELLO
Potenziare gli
algoritmi esatti
algoritmi euristici
ALGORITMI
software
Algoritmi esatti:
PROBLEMA
Risolvere all’ottimo TSP
sempre più grandi
MODELLO
1954: 49 città
2007: 85900 città
ALGORITMI
software
Algoritmi euristici:
PROBLEMA
Trovare soluzioni
sempre più vicine
all’ottimo
MODELLO
Nearest Neighbor: 20%
ALGORITMI
Farthest Insertion: 9%
software
Lin-Kernighan: 1%
4) Utilizzo di software
Gli algoritmi esatti ed
euristici sono implementati
in software
PROBLEMA
MODELLO
ALGORITMI
software
Concorde
Concorde per il TSP:
PROBLEMA
MODELLO
ALGORITMI
software
Ricerca operativa e Ulisse
Soluzione
Distanza
Ulisse
9404
Nearest Neighbor
9988
Lin-Kernighan
6859
Ottima
6859
PROBLEMA
MODELLO
ALGORITMI
Soluzione ottima in
meno di un secondo!
software
1
0
3
Ricerca operativa e Logistica
13.000 componenti
20.000 fornitori
164 impianti
11.000 rivenditori
PROBLEMA
MODELLO
ALGORITMI
Risparmio del 26%
del costo logistico!
software
1
0
3
Il TSP è solo uno dei sottoproblemi della
logistica integrata
La vera sfida consiste nel trovare la soluzione
migliore per l’intero sistema
1
0
3
Conclusione
Un antico proverbio recita:
Se un problema non ha
soluzioni, perchè preoccuparsi?
Se un problema ha soluzioni,
perchè preoccuparsi?
Il problema di Ulisse ha
653.837.184.000
soluzioni…
La soluzione di Ulisse costa
il 43.8% più dell’ottimo…
PROBLEMA
MODELLO
ALGORITMI