Ricerca Operativa e Logistica

Ricerca Operativa e Logistica
Dott. F.Carrabs e Dott.ssa M.Gentili
Modelli per la Logistica Distributiva a breve
distanza:
The Travelling Salesman Problem
The Vehicle Routing Problem
The Chinese Postman Problem
Problemi di distribuzione a
breve distanza (1/3)
Riguardano il problema di raccolta e consegna merci in
aree limitate (città, provincia) attraverso una flotta di
veicoli.
In generale:
I veicoli, partono e ritornano da un singolo deposito
Ogni veicolo effettua il suo tour in un unico turno di lavoro
Ogni tour può contenere diverse fermate per la raccolta (pick-up)
e diverse fermate per la consegna (delivery)
Problemi di distribuzione a
breve distanza (2/3)
Importanti per:
Compagnie di distribuzione:
Consegna attraverso veicoli di piccole medie dimensioni dai
magazzini ai dettaglianti o direttamente ai clienti
Consegna della posta
Raccolta dei rifiuti
Servizi a chiamata (dial a-ride: per i trasporto di anziani o
disabili)
Servizi di emergenza (incluse anche le rotte di
ambulanze e/o vigili del fuoco)
…..
Problemi di distribuzione a
breve distanza (3/3)
Problemi decisionali:
A livello strategico:
Le decisioni principali sono strettamente collegate alla
localizzazione dei magazzini
Decisioni riguardanti la localizzazione che tengano in
considerazione anche le rotte dei veicoli
A livello tattico:
Decisioni riguardanti la grandezza della flotta (i.e., numero dei
veicoli)
A livello operativo:
Decisioni riguardanti la definizione delle rotte per ogni veicolo
della flotta per soddisfare tutte le richieste degli utenti (Vehicle
Routing Problems)
Vehicle Routing Problems
Problema:
determinare un insieme di rotte per una flotta di veicoli per servire un
insieme di utenti
Problemi Statici: la domanda di servizio è fissata a priori e nota
Problemi dinamici: tutta la domanda o parte della domanda di servizio può
essere nota quando i veicoli hanno già cominciato il servizio (i percorsi dei
veicoli possono essere definiti o modificati on-line)
Vehicle Routing Problems:
Componenti e caratteristiche principali
COMPONENTI PRINCIPALI
- Rete stradale
- Clienti
- Veicoli
- Depositi
- Autisti
- Vincoli Operativi:
Globali
Per le singole rotte
- Ottimizzazione degli obiettivi
La rete stradale
La rete stradale:
- Un grafo G=(V,E)
- I vertici indicano: clienti, intersezioni, depositi
- Gli archi indicano le strade ed hanno un valore
associato che indica un costo o un tempo di
viaggio
- Il deposito, dove gli m veicoli sono inizialmente
posizionati, è generalmente indicato con il
vertice {0}
La rete stradale:
disuguaglianza triangolare
Clienti
I clienti che richiedono un servizio, possono essere
associati agli archi o ai nodi
La domanda di servizio: quantità di un bene che deve
essere prelevata o consegnata
Caratteristiche:
- Finestre temporali (time windows)
- Tempo preferito per il servizio (con delle penalità se non
rispettato)
- Tempo di servizio (Service time)
Veicoli
Grandezza della flotta (Fleet size): fissa o variabile
Flotta in outsourcing o getsita in proprio
Numero di depositi: singolo deposito, multi- deposito
Capacità dei veicoli
Compatibilità dei beni da trasportare (beni deperibili,
materiali pericolosi…)
Procedura di carico/scarico
Costi (associati con la distanza, tempo, il carburante, il
carico)
Vincoli Operativi
Vincoli locali (singola rotta)
Capacità del veicolo
Massima durata/ lunghezza del tempo di servizio del veicolo
Vincoli temporali (tempo di arrivo, tempo di partenza, time windows)
Tipologia di servizio (pickup, delivery o entrambi)
Vincoli di precedenza tra i clienti:
pickup and delivery
linehaul/backhaul
Vincoli globali (tutte le rotte)
Numero massimo di veicoli
Numero massimo di rotte (per veicolo o per deposito)
Bilanciamento del carico di lavoro
Turni di lavoro
Obiettivi da ottimizzare
Minimizzare costo di trasporto totale + costi
fissi
Minimizzare numero di veicoli
Bilanciare le rotte
Minimizzare le penalità o i clienti non serviti
Vehicle Routing Problems in generale
-
un grafo G=(V,E)
Un deposito indicato con il vertice {0}
Un sottoinsieme ܷ ⊆ ܸ di REQUIRED VERTICES
Un sottoinsieme ܴ ⊆ ‫ ܧ‬di REQUIRED ARCS
Determinare un insieme di m rotte di costo totale minimo che inizino
e finiscano nel deposito e visitino tutti i vertici in U e tutti gli archi in R.
Vehicle Routing Problems
Se = ∅ NODE ROUTING PROBLEMS
Se = ∅ ARC ROUTING PROBLEMS
Casi particolari senza vincoli operativi:
- se = 1, = ∅, = Travelling Salesman Problem:
Trovare un tour di costo minimo che visiti tutti i nodi esattamente una volta
- se = 1, = , = ∅ Chinese Postman Problem:
Trovare un tour di costo minimo che visiti tutti gli archi almeno una volta
- se = 1, ⊂ , = ∅ Rural Postman Problem:
Trovare un tour di costo minimo che visiti tutti gli archi in R almeno una volta
NODE ROUTING
PROBLEMS
NODE ROUTING PROBLEMS
NODE ROUTING PROBLEMS
Travelling Salesman Problem
(TSP)
MSOffice1
A→B →C →D →E →A 42
A →C →D →B →E →A 21
A
10
5
3
E
10
5
B
9
10
15
6
D
2
C
Diapositiva 18
MSOffice1
; 29/11/2006
UN PO’ DI STORIA DEL TSP
1800’s
1930’s
Irish Mathematician, Sir William Rowan Hamilton
Studied by Mathematicians Menger, Whitney, Flood etc.
1954
Dantzig, Fulkerson, Johnson, 49 cities (capitals of USA
states) problem solved
1971
1975
64 Cities
100 Cities
1977
120 Cities
1980
318 Cities
1987
666 Cities
1987
2392 Cities (Electronic Wiring Example)
1994
7397 Cities
1998
13509 Cities (all towns in the USA with population > 500)
2001
15112 Cities (towns in Germany)
2004
24978 Cities (places in Sweden)
19
USA Towns of 500 or more population
13509 cities 1998
Applegate, Bixby, Chvátal and Cook
20
Towns in Germany 15112 Cities 2001
Applegate, Bixby, Chvátal and Cook
21
Sweden 24978 Cities 2004
Applegate, Bixby, Chvátal, Cook and Helsgaun
22
TSP – 2 casi
TSP – funzione obiettivo
Sia G=(V,E) il nostro grafo input.
Dove l’insieme V dei vertici contiene anche il nodo {0} deposito
min ௜௝ ௜௝
1 se l’arco e fa parte
=
della soluzione
௜,௝ ∈ா
0 altrimenti
Costo dell’arco e
TSP- vincoli (1/3)
௜௝ = 1∀ ∈ ௜∈஻ௌ(௝)
௝௜ = 1∀ ∈ Ogni nodo ha:
esattamente un arco entrante
ed esattamente un arco uscente
[DEGREE CONSTRAINTS]
௜∈ிௌ(௝)
I sottocicli non vengono eliminati
TSP – vincoli (2/3):
per eliminare i sottocicli
௜௝ ≤ − 1 ∀ ⊂ , ≥ 2
௜∈ௌ ௝∈ௌ
Subtour elimination Constraints
TSP – vincoli (3/3):
per eliminare i sottocicli
௜௝ ≥ 1 ∀ ⊂ , ≥ 2
௜∈ௌ ௝∉ௌ
Connectivity
Constraints
TSP-formulazione
min ௜௝ ௜௝
௜,௝ ∈ா
௜௝ = 1∀ ∈ ௜∈௏/{௝}
௝௜ = 1∀ ∈ ௜∈௏/{௝}
௜௝ ≤ − 1 ∀ ⊂ , ≥ 2
௜∈ௌ ௝∈ௌ
௜௝ ∈ 0,1 ∀(, ) ∈ Il modello visto ha dimensione
esponenziale nel numero di vertici
Per escludere l’esistenza di sottocicli nella
soluzione ci serve un vincolo per ogni
sottoinsieme proprio non vuoto di V
Sappiamo che se un insieme ha cardinalità n il
suo insieme delle parti ha cardinalità 2n
Esempio: T = {A,B,C} →
P(T)= {{Ø},{A},{B},{C},{A,B},{A,C},{B,C},{A,B,C}}
Il numero di vincoli relativi ai sottocicli sarà O(2|V|)
TSP: modello Miller-TuckerZemlin
C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulations and traveling
salesman problems,” J. ACM, 7 (1960), pp. 326–329.
Si considera un nuovo insieme di variabili: ௜ , ∀ ∈ /{0} ௜ ≥ 0
E si considerano i seguenti vincoli:
௜ − ௝ + ௜௝ ≤ − 1∀ ≠ ∈ / 0
Questi vincoli escludono tutti i tour che non includono il vertice {0}
TSP: modello Miller-TuckerZemlin
௜ ௝ ௜௝ 1∀ ∈ / 0
Ciclo non
ammesso
Le nuove variabili definiscono l’ordine con cui i nodi vengono visitati
௜ ௝ ௜௝ 1∀ ∈ / 0
TSP: modello Miller-TuckerZemlin
min ௜௝ ௜௝
௜,௝ ∈ா
௜௝ = 1∀ ∈ ௜∈௏/{௝}
௝௜ = 1∀ ∈ ௜∈௏/{௝}
௜ − ௝ + ௜௝ ≤ − 1∀ ≠ ∈ / 0
௜௝ ∈ 0,1 ∀(, ) ∈ ௜ ≥ 0∀ ∈ / 0
Travelling Salesman Problem (TSP) –
riformulazione come problema di flusso
Cerchiamo una formulazione alternativa che ci
consenta di trovare un modello di dimensione
polinomiale nell’input
Un nodo sorgente invia |V| unità di flusso lungo
la rete
Ogni nodo trattiene una unità di flusso, l’ultima
deve tornare alla sorgente
Vogliamo che il flusso segua un percorso di
costo minimo
MSOffice2
Travelling Salesman Problem (TSP) –
riformulazione come problema di flusso
Flusso 2 -1= 1
Flusso 5
A
10
Flusso 3 -1= 2
5
3
E
10
5
B
9
Flusso 4 -1= 3
10
15
6
D
2
C
Flusso 5 -1= 4
Diapositiva 35
MSOffice2
; 29/11/2006
TSP modello singlecommodity flow –
funzione obiettivo e definizioni
Resta immutata la funzione obiettivo
min ௜௝ ௜௝
௜,௝ ∈ா
Variabili di flusso f ij = unità di flusso inviate dal nodo i al
nodo j
s nodo sorgente
n numero di nodi nel grafo
TSP – vincoli del modello single
commodity flow (1)
௜௝ = 1∀ ∈ ௜∈௏/{௝}
Due vicini per ogni nodo
nel ciclo
௝௜ = 1∀ ∈ ௜∈௏/{௝}
଴௝ −
଴,௝ ∈ிௌ ଴
௜,௝ ∈ிௌ ௜
௝଴ = − 1
௝,଴ ∈஻ௌ ଴
௜௝ −
௝,௜ ∈஻ௌ ௜
௝௜ = −1 ∀ ∈ /{0}
La differenza tra flusso
uscente e flusso entrante
per la sorgente è n-1
Gli altri nodi trattengono
una unità di flusso
TSP – vincoli del modello
single commodity flow (2)
( + 1)
௜௝ =
2
Somma totale dei flussi sulla rete pari
alla somma dei primi n numeri naturali
௜,௝ ∈ா
௜௝ ≤ ௜௝ ∀ , ∈ ௜௝ ∈ 0,1 ∀(, ) ∈ ௜௝ ≥ 0
∀(, ) ∈ Flusso da i a j minore o uguale ad n, e
diverso da 0 solo se (i,j) fa parte della
soluzione
Variabili di selezione degli archi
booleane (si/no)
Variabili di flusso intere
ARC ROUTING PROBLEMS
The Chinese Postman Problem (CPP)
ARC ROUTING PROBLEMS
I vincoli operativi sono gli stessi che si hanno
per i Node Routing Problems
Se non si considerano i vincoli operativi:
Servire tutti gli archi: the Chinese Postman
Problem (CPP)
Servire un sottoinsieme di archi: the Rural
Chinese Postman Problem (RCPP)
The Chinese Postman Problem
Caratteristiche:
Un solo veicolo
Servire tutti gli archi
La domanda di servizio non si considera (cosi come la capacità
del veicolo)
Soluzione:
un ciclo di costo minimo che visiti tutti
gli archi almeno una volta
Problema correlato:
ESISTE UN CICLO CHE VISITA TUTTI GLI
ARCHI ESATTAMENTE UNA VOLTA?
Il problema dei ponti di
Könisberg (Eulero, 1707-1783)
E’ POSSIBILE ATTRAVERSARE TUTTI
I PONTI ESATTAMENTE UNA VOLTA
INIZIANDO E FINENDO NELLO
STESSO PUNTO?
(EULERO 1736)
=
QUESTO (MULTI)GRAFO E’
EULERIANO?
Il problema dei ponti di
Könisberg (Eulero, 1707-1783)
EULERO HA DIMOSTRATO CHE:
1. UN GRAFO NON ORIENTATO È EULERIANO ↔ TUTTI I NODI HANNO
GRADO PARI
2. UN GRAFO ORIENTATO È EULERIANO ↔ TUTTI I NODI HANNO GRADO
USCENTE UGUALE AL GRADO ENTRANTE
Se un grafo è euleriano la soluzione ottima del CPP è pari
alla somma dei costi di tutti gli archi del grafo Come trovo il ciclo euleriano?
Come trovare un ciclo
euleriano?
End-Pairing Algorithm
1. Trace a first simple T1 tour in G (that may not contain all
vertices). If all the edges are traversed then stop
2. Consider any vertex v on T1 which is incident to an edge
not on the tour, and form a second tour T2 from v not
overlapping T1
3. Merge T2 with T1: starting from v follow T1 and then
continue with T2
4. If all the edges are traversed then stop, otherwise
continue with step 2
End-Pairing Algorithm
ଵ ଶ ଵ ଶ C D A
ଷ D G E D
ଵ ଶ ଷ C D G E D A
Cammino Euleriano e CPP
Un tour euleriano in un grafo è un tour che contine tutti gli archi
esattamente una volta
Un postman tour in un grafo è un tour che contine tutti gli archi
almeno una volta
Se un grafo G è euleriano il valore della soluzione ottima del CPP è
pari alla somma dei pesi di tutti gli archi del grafo ed il problema
diventa quello di individuare il ciclo euleriano
Se G non è euleriano allora la soluzione di CPP è un tour che visita
un sottoinsieme di archi più di una volta
Quindi il problema si riduce a quello di aggiungere copie di archi a G
in modo tale che G diventi euleriano
CPP: formulazione matematica
su grafi non orientati
Input
= (, ) grafo non orientato
௘ costo associato ad ogni arco in G
଴ ⊆ sottoinsieme dei vertici di grado dispari
ீ = ௜௘ matrice di incidenza del grafo G (௜௘ = 1
se l’arco e incide il nodo i)
Variabili
௘ :numero di volte che l’arco e viene aggiunto al grafo G
per renderlo euleriano
௜ ≥ 0
intero associato ad ogni nodo
CPP: formulazione matematica
su grafi non orientati
min ௘ ௘
௘∈ா
௜௘ ௘ = 2௜ + 1∀ ∈ ଴
௘∈ா
௜௘ ௘ = 2௜ ∀ ∉ ଴
௘∈ா
௘ ≥ 0∀ ∈ ௜ ≥ 0∀ ∈ CPP: problema polinomiale
Risolvere CPP su grafi non orientati (ed orientati):
Se G è euleriano:
- determina un tour euleriano attraverso l’end-pairing
algorithm
Se G non è euleriano:
- aggiungi archi a G per farlo diventare un grafo Euleriano
G’ (risolvi il problema formulato precedentemente)
- trova il tour euleriano in G’
Esistono algoritmi polinomiali per risolvere il problema del CPP su
grafi orientati e non orientati CPP è un problema risolubile in
tempo polinomiale.