Il problema del commesso viaggiatore e problemi di vehicle ... · Introduzione TSP asimmetrico VRP...

Introduzione TSP asimmetrico VRP

Il problema del commesso viaggiatore

e problemi di vehicle routing

Laura GalliDipartimento di Informatica

Largo B. Pontecorvo 3, 56127 [email protected]

http://www.di.unipi.it/~galli

2 Dicembre 2014Ricerca Operativa 2

Laurea Magistrale in Ingegneria GestionaleUniversita di PisaA.A. 2014/15

L. Galli Corso di Ricerca Operativa 2 - Laurea Magistrale in Ingegneria Gestionale Universita di Pisa 1 / 33


Problema del commesso viaggiatore (TSP)

Problema

Grafo (N ,A) completo; cij = costi sugli archi.Trovare un ciclo di costo minimo che passi su tutti i nodi una ed una sola volta(ciclo hamiltoniano).

Teorema

Questo problema e NP-hard.

Quante sono le soluzioni ammissibili?



Problema del commesso viaggiatore (TSP)

Applicazioni

• trasporti, logistica: (N ′,A′) rete stradale. S ⊆ N ′, cerco ciclo di costo

minimo che passi su tutti i nodi di S . Il problema e un TSP sul grafo (N ,A),dove N = S , A = S × S , cij = costo cammino minimo da i a j sul grafo(N ′

,A′).

• scheduling (problema 1|sjk |Cmax)

• produzione di circuiti integrati

• data analysis

• sequenze DNA

• . . . (vedi http://www.tsp.gatech.edu/)



Perche ciclo hamiltoniano?

William Rowan Hamilton (1805-1865): in un dodecaedro regolare e possibilepartire da un vertice e, passando sugli spigoli, toccare tutti i vertici una ed unasola volta e tornare al vertice di partenza?



Perche ciclo hamiltoniano?

Icosian game: in un dodecaedro regolare e possibile partire da un vertice e,passando sugli spigoli, toccare tutti i vertici una ed una sola volta e tornare alvertice di partenza?



TSP simmetrico e asimmetrico

Se la matrice dei costi e simmetrica, cioe cij = cji per ogni arco (i , j), il problemae detto simmetrico; altrimenti e detto asimmetrico.

TSP asimmetrico

1 2

3 4

2

7

45

6

6

8

3

54

7

6

TSP simmetrico

1 2

3 4

2

4

5

6

7

8

Prima tratteremo il problema asimmetrico (piu generale) e poi quello simmetrico(caso particolare).



Modello 1

Variabili: xij =

{

1 se arco (i , j) ∈ ciclo hamiltoniano,

0 altrimenti.

min∑

(i ,j)∈A

cij xij

∑

i∈N\{j}

xij = 1 ∀ j ∈ N (1)

∑

j∈N\{i}

xij = 1 ∀ i ∈ N (2)

∑

(i ,j)∈A: i∈S, j /∈S

xij ≥ 1 ∀ S ⊆ N , S 6= ∅,N (3)

xij ∈ {0, 1} ∀ (i , j) ∈ A

(1)-(2): per ogni nodo deve esistere un arco entrante e un arco uscente(3): eliminazione di sottocicli.



Modello 2

Variabili: xij =

{

1 se arco (i , j) ∈ ciclo hamiltoniano,

0 altrimenti.

min∑

(i ,j)∈A

cij xij

∑

i∈N\{j}

xij = 1 ∀ j ∈ N (4)

∑

j∈N\{i}

xij = 1 ∀ i ∈ N (5)

∑

(i ,j)∈A: i∈S, j∈S

xij ≤ |S | − 1 ∀ S ⊆ N , S 6= ∅,N (6)

xij ∈ {0, 1} ∀ (i , j) ∈ A




Modello 3

Variabili: xij =

{

1 se arco (i , j) ∈ ciclo hamiltoniano

0 altrimenti

ui ≥ 1 per ogni i ∈ N , dove ui = k se i e il k–esimo nodo visitato nel ciclo.

min∑

(i ,j)∈A

cij xij

∑

i∈N\{j}

xij = 1 ∀ j ∈ N (7)

∑

j∈N\{i}

xij = 1 ∀ i ∈ N (8)

|N | xij + ui − uj ≤ |N | − 1 ∀ (i , j) ∈ A, j 6= 1 (9)

xij ∈ {0, 1} ∀ (i , j) ∈ A

u1 = 1

2 ≤ ui ≤ |N | ∀ i ∈ N , i 6= 1




Modello 3

Perche il vincolo

|N | xij + ui − uj ≤ |N | − 1 ∀ (i , j) ∈ A, j 6= 1 (9)

elimina i sottocicli?Se xij = 1, con j 6= 1, allora uj ≥ ui + 1. Se xij = 0 allora ui − uj ≤ |N | − 1.

Se x soddisfa i vincoli (7)-(8) ma non e un ciclo hamiltoniano, allora e unafamiglia di sottocicli, quindi esiste un sottociclo S che non passa per il nodo 1.Applicando il vincolo (9) agli archi di S si ottiene una contraddizione sulle variabiliu, quindi (9) non e soddisfatto.

Il vincolo (9) e soddisfatto da ogni ciclo hamiltoniano. Infatti, al ciclo1− 4− 2− 3− 1 corrisponde la soluzione x14 = 1, x42 = 1, x23 = 1, x31 = 1,u1 = 1, u4 = 2, u2 = 3, u3 = 4 che soddisfa il vincolo (9).

Il vincolo (9) e costituito da O(n2) disequazioni (polinomiale)I vincoli (3) e (6) sono costituiti da O(2n) disequazioni (non polinomiale)



Modello 4

Variabili: xij =

{

1 se arco (i , j) ∈ ciclo,

0 altrimenti,yij = flusso inviato lungo (i , j)

min∑

(i ,j)∈A

cij xij

∑

i∈N\{j}

xij = 1 ∀ j ∈ N (10)

∑

j∈N\{i}

xij = 1 ∀ i ∈ N (11)

∑

j∈N\{i}

yji −∑

j∈N\{i}

yij = 1 ∀ i ∈ N , i 6= 1 (12)

0 ≤ yij ≤ (|N | − 1) xij ∀ (i , j) ∈ A (13)

xij ∈ {0, 1} ∀ (i , j) ∈ A

(10)-(11): per ogni nodo deve esistere un arco entrante e un arco uscente(12)-(13): eliminazione di sottocicli.



Metodo Branch and Bound: rilassamenti

• Rilassamenti continui dei modelli 1, 2, 3, 4.

• Eliminare i vincoli di connessione dal modello 1: si ottiene un problema diassegnamento di costo minimo:

min∑

i∈N

∑

j∈N

cij xij

∑

i∈N

xij = 1 ∀ j ∈ N

∑

j∈N

xij = 1 ∀ i ∈ N

xij ∈ {0, 1} ∀ i , j ∈ N

Questo problema e un flusso di costo minimo e quindi e risolubile in tempopolinomiale.

La soluzione ottima e una famiglia di cicli orientati che coprono tutti i nodi.



Metodo Branch and Bound: rilassamenti

Esempio

Consideriamo la seguente matrice dei costi:

1 2 3 4 51 – 33 13 25 332 33 – 46 58 763 39 33 – 12 304 35 29 12 – 235 60 54 30 23 –

1

2

34

5

La soluzione ottima del rilassamento e formata da due cicli:

x13 = 1, x32 = 1, x21 = 1, x45 = 1, x54 = 1,

e ha valore 125 = vI (P).



Metodo Branch and Bound: metodi euristici

Metodo greedy sugli archi

Dispongo gli archi in ordine crescente di costo.Seguendo l’ordine, inserisco un arco se vengono rispettati tutti i vincoli.

Esempio

1 2 3 4 51 – 33 13 25 332 33 – 46 58 763 39 33 – 12 304 35 29 12 – 235 60 54 30 23 –

1

2

34

5

x34 = 1, x43 = 0, x13 = 1, x45 = 1, x54 = 0, x14 = 0, x42 = 0, x35 = 0, x53 = 0,x12 = 0, x15 = 0, x21 = 1, x32 = 0, x41 = 0, x31 = 0, x23 = 0, x52 = 1.

Il ciclo trovato e 3-4-5-2-1-3 di costo 135.




Algoritmo del nodo piu vicino

Parti da un nodo i . Il nodo successivo e il piu vicino a i tra quelli non ancoravisitati. E cosı via.

Esempio

1 2 3 4 51 – 33 13 25 332 33 – 46 58 763 39 33 – 12 304 35 29 12 – 235 60 54 30 23 –

Partendo dal nodo 1 si ottiene il ciclo 1–3–4–5–2–1 di costo 135.

Partendo dal nodo 5 si ottiene il ciclo 5–4–3–2–1–5 di costo 134.




Algoritmi di inserimento

Costruisco un ciclo su un sottoinsieme di nodi. Estendo questo ciclo inserendo unoalla volta i nodi rimanenti fino ad inserire tutti i nodi.

L’implementazione di questo schema dipende da:

• come costruisco il ciclo iniziale: ciclo qualsiasi, ciclo sui 3 nodi che formano iltriangolo piu grande, ciclo che segue l’involucro convesso dei nodi (quandocij = distanza euclidea tra i e j), . . .

• come scelgo il prossimo nodo da inserire: il piu vicino al ciclo, il piu lontanodal ciclo, quello il cui inserimento causa il minimo incremento nella lunghezzadel ciclo, . . .

• dove inserisco il nodo scelto: di solito e inserito nel punto che causa ilminimo incremento nella lunghezza del ciclo




Esempio

1 2 3 4 51 – 33 13 25 332 33 – 46 58 763 39 33 – 12 304 35 29 12 – 235 60 54 30 23 –

Scelgo un ciclo a caso: 1-2-3-1.Il nodo 4 ha distanza 12 dal ciclo, mentre il nodo 5 ha distanza 30. Scelgo il nodopiu vicino al ciclo: 4.Dove inserisco il nodo 4?Se inserisco 4 tra 1 e 2, la lunghezza del ciclo aumenta di 25 + 29− 33 = 21Se inserisco 4 tra 2 e 3, la lunghezza del ciclo aumenta di 58 + 12− 46 = 24Se inserisco 4 tra 3 e 1, la lunghezza del ciclo aumenta di 12 + 35− 39 = 8Quindi inserisco il nodo 4 tra 3 e 1. Il ciclo diventa 1-2-3-4-1.Dove inserisco il nodo 5? Conviene inserirlo tra 3 e 4, quindi il ciclo hamiltonianoe 1-2-3-5-4-1 di costo 167.




Algoritmo basato sulla soluzione ottima del rilassamento.

Algoritmo delle toppe (patching)

1. L’assegnamento di costo minimo e formato da una famiglia di cicli orientatiF = {C1, . . . ,Cp}.

2. Per ogni coppia di cicli Ci ,Cj ∈ F , calcola l’incremento di costo γij

corrispondente alla fusione di Ci e Cj nel modo piu conveniente possibile.

3. Effettua la fusione dei due cicli Ci e Cj ai quali corrisponde il minimo valoredi γij . Aggiorna F .

4. Se F contiene un solo ciclo allora STOPaltrimenti torna al passo 2.




Esempio

1 2 3 4 5

1 – 33 13 25 332 33 – 46 58 763 39 33 – 12 304 35 29 12 – 235 60 54 30 23 –

1

2

34

5

La soluzione ottima del rilassamento e formata da due cicli: 1–3–2–1 e 4–5–4.Le possibili fusioni dei due cicli sono le seguenti:

sostituire gli archi con gli archi si ottiene il ciclo di costo

(1, 3) e (4, 5) (1, 5) e (4, 3) 1-5-4-3-2-1 134(1, 3) e (5, 4) (1, 4) e (5, 3) 1-4-5-3-2-1 144(2, 1) e (4, 5) (2, 5) e (4, 1) 1-3-2-5-4-1 180(2, 1) e (5, 4) (2, 4) e (5, 1) 1-3-2-4-5-1 187(3, 2) e (4, 5) (3, 5) e (4, 2) 1-3-5-4-2-1 128(3, 2) e (5, 4) (3, 4) e (5, 2) 1-3-4-5-2-1 135

La fusione piu conveniente trova il ciclo 1-3-5-4-2-1 di costo 128.



Metodi euristici: ricerca locale

Dopo aver trovato una soluzione ammissibile, provo a migliorarla.

1. Trovo una soluzione ammissibile x

2. Genero un insieme N(x) di soluzioni “vicine” ad x (intorno)

3. Se in N(x) esiste una soluzione ammissibile x ′ migliore di xallora x := x ′ e torno al passo 2

altrimenti STOP (x e una soluzione ottima locale)




Nel caso del TSP, come definisco un intorno N(x)?

Una possibile scelta e:

N(x) = {cicli hamiltoniani che hanno 2 archi diversi da x}.

1 2

3

45

6

x

1 2

3

45

6

x ′ ∈ N(x)




Esempio

Consideriamo il TSP sul grafo

1

2

34

5

112336

31

15

25

24

27

34

29

Effettuiamo la ricerca locale a partire dal ciclo 1-3-5-2-4 di costo 142.




Esempio

x costo elimino archi inserisco archi x ′ costo1-3-5-2-4-1 142 (1,3) (5,2) (1,5) (3,2) 1-5-3-2-4-1 1411-5-3-2-4-1 141 (1,5) (2,4) (1,2) (5,4) 1-2-3-5-4-1 1251-2-3-5-4-1 125 (1,2) (3,5) (1,3) (2,5) 1-3-2-5-4-1 127

(1,2) (5,4) (1,5) (2,4) 1-5-3-2-4-1 141(2,3) (5,4) (2,5) (3,4) 1-2-5-3-4-1 132(2,3) (4,1) (2,4) (3,1) 1-3-5-4-2-1 122

1-3-5-4-2 122 . . . . . . . . . . . .



Problemi di vehicle routing

Servire un insieme di clienti utilizzando una flotta di veicoli, localizzati in uno opiu depositi, che si spostano su una rete stradale.

Rete stradale

Grafo completo (N ,A), dove N={clienti, depositi}, A ={tratti stradali},cij = lunghezza del cammino minimo da i a j → vale disuguagliaza triangolaretij = tempo di viaggio da i a j

Clienti

- il cliente i ha una domanda di- tempi di carico/scarico- eventuali finestre temporali (orari apertura, orari accesso ZTL, . . . )- eventuali veicoli non utilizzabili




Veicoli

- veicoli di dimensione fissa o variabile (rimorchio?)- veicolo puo ritornare in un deposito diverso da quello di origine- capacita di carico (volume, peso, unita, . . . )- archi che un veicolo non puo attraversare- costi (per km, per ora, . . . )

Autisti

- dipendenti o ditte esterne- vincoli su orario di lavoro, durata pause, . . .




Vincoli operativi

- capacita dei veicoli- e permessa solo la consegna di merce ai clienti, oppure solo il ritiro, oppureentrambe le operazioni- massima lunghezza/durata dei viaggi- rispetto finestre temporali- precedenze tra clienti (pickup and delivery): la merce prelevata da un clientedeve essere consegnata ad un altro cliente dallo stesso veicolo- precedenze tra clienti (vehicle routing with backhaul): tutte le consegne di mercedevono essere effettuate prima dei ritiri di merce

Obiettivi

- minimizzare costo totale di trasporto (distanza percorsa + costi veicoli)- minimizzare numero dei veicoli utilizzati- minimizzare penalita associate al mancato servizio di clienti




Applicazioni

• distribuzione di merci a clienti dislocati in diverse zone geografiche

• distribuzione di merci ai negozi di una citta

• raccolta rifiuti solidi urbani

• . . .



VRP capacitato

un solo deposto (nodo 0) da cui partono e in cui tornano i veicolin clienti (nodi 1, . . . , n)solo consegne di merce di un unico tipodi = domanda del cliente i

K veicoli identici di capacita C , un solo viaggio per veicoloobiettivo: minimizzare lunghezza totale percorsa

0

1

2

3 4 5

6

7

Questo problema e NP-hard (perche il TSP e un caso particolare per K = 1).



Modello 1

Variabili: xij =

{

1 se arco (i , j) ∈ sol. ottima

0 altrimenti

min∑

(i,j)∈A

cij xij

∑

i∈N\{j}

xij = 1 ∀ j ∈ N \ {0} (14)

∑

j∈N\{i}

xij = 1 ∀ i ∈ N \ {0} (15)

∑

i∈N\{0}

xi0 = K (16)

∑

i∈S

∑

j /∈S

xij ≥

⌈∑

i∈Sdi

C

⌉

∀ S ⊆ N \ {0}, S 6= ∅ (17)

xij ∈ {0, 1} ∀ (i , j) ∈ A

(14)-(15): un arco entrante e un arco uscente per ogni cliente. (16): K veicoli usati.(17): capacita dei veicoli ed eliminazione di sottocicli.



Modello 2

Variabili: xij =

{

1 se arco (i , j) ∈ sol. ottima

0 altrimentiui = carico veicolo prima di visitare i

min∑

(i,j)∈A

cij xij

∑

i∈N\{j}

xij = 1 ∀ j ∈ N \ {0} (18)

∑

j∈N\{i}

xij = 1 ∀ i ∈ N \ {0} (19)

∑

i∈N\{0}

xi0 = K (20)

uj − ui + C xij ≤ C − di ∀ i , j ∈ N \ {0}, i 6= j (21)

xij ∈ {0, 1} ∀ (i , j) ∈ A

di ≤ ui ≤ C ∀ i ∈ N \ {0}

(18)-(19): un arco entrante e un arco uscente per ogni cliente. (20): K veicoli usati.(21): capacita dei veicoli ed eliminazione di sottocicli.



Modello 3

Variabili: xijk =

{

1 se veicolo k passa sull’arco (i , j)

0 altrimentiyik =

{

1 se i assegnato al veicolo k

0 altrimenti

min∑

(i,j)∈A

cij

K∑

k=1

xijk

K∑

k=1

yik = 1 ∀ i ∈ N \ {0} (22)

K∑

k=1

y0k = K (23)

∑

j∈N\{i}

xijk =∑

j∈N\{i}

xjik = yik ∀ i ∈ N, k = 1, . . . ,K (24)

∑

i∈N\{0}

di yik ≤ C ∀ k = 1, . . . ,K (25)

∑

i∈S

∑

j /∈S

xijk ≥ yhk ∀ S ⊆ N \ {0}, h ∈ S, k = 1, . . . ,K (26)

xijk ∈ {0, 1}, yik ∈ {0, 1} ∀ i , j , k

(22): ogni cliente e assegnato a un solo veicolo. (23): K veicoli usati. (24): se i e assegnato ak, allora k entra ed esce da i . (25): capacita dei veicoli. (26): eliminazione sottocicli.



Modello 4

Indichiamo con R = {R1, . . . ,Rq} l’insieme di tutte le rotte ammissibili (Rj e unciclo che include il deposito e rispetta le capacita) e cj = costo della rotta Rj .

Definiamo aij =

{

1 se i ∈ Rj

0 altrimentiVariabili: xj =

{

1 se scelgo la rotta Rj

0 altrimenti

min

q∑

j=1

cj xj

q∑

j=1

aij xj = 1 ∀ i ∈ N \ {0} (27)

q∑

j=1

xj = K (28)

xj ∈ {0, 1} ∀ j

(27): ogni cliente e assegnato a una sola rotta. (28): K veicoli usati.



Metodi euristici

Costruttivi: trovano gradualmente una soluzione ammissibile, senza fasi dimiglioramento

A due fasi:

• cluster-first-route-second: prima si dividono i clienti in sottoinsiemiammissibili (rispettando le capacita), poi per ogni sottoinsieme si determinala rotta (risolvendo un TSP)

• route-first-cluster-second: prima si trova un ciclo hamiltoniano su tutti iclienti (TSP), poi si suddivide il ciclo in pezzi ammissibili (rispettando lecapacita)

Ricerca locale: prima trovano una soluzione ammissibile, poi cercano di migliorarlaesplorando un intorno, fino a trovare una soluzione ottima locale


Il problema del commesso viaggiatore e problemi di vehicle ... · Introduzione TSP asimmetrico VRP...

Documents

Transcript of Il problema del commesso viaggiatore e problemi di vehicle ... · Introduzione TSP asimmetrico VRP...