TSP - Università di Bologna

Problemi di routing di veicoli:
2 – Modelli e rilassamenti per il TSP
Daniele Vigo
DEIS, Università di Bologna
[email protected]
Problema del Commesso Viaggiatore (TSP)
• caso particolare:
• 1 deposito
• 1 veicolo di capacità illimitata
• minimizzare il costo per servire tutti i clienti
Circuito a costo minimo
passante per tutti i vertici
Circuito Hamiltoniano
D. Vigo
TSP−Modelli.2
1
TSP
• Soluzione ≡ permutazione di {1, …, n}
• se G completo ⇒ (n−1)! soluzioni
• 2 casi per la matrice dei costi:
• simmetrica:
• asimmetrica:
cij = cji ∀i, j∈V Î STSP o TSP
cij ≠ cji ∀i, j∈V Î ATSP
D. Vigo
TSP−Modelli.3
TSP simmetrico (STSP)
Grafo non orientato G(V, E):
V={1,…,n}
vertici
|V|=n
lati (edges) |E|=m
E={e1,…,em}
ce ≥ 0 costo lato e
α(e)
S
D. Vigo
e
β(e)
δ (S) = insieme Lati incidenti in S
σ (S) = insieme Lati interni ad S
TSP−Modelli.4
2
Circuito Hamiltoniano
• Cammino elementare chiuso che visita tutti i
vertici del grafo
• ogni vertice deve avere grado 2
• ogni vertice deve essere raggiunto
• ogni “taglio” deve essere attraversato almeno 2 volte
S
D. Vigo
TSP−Modelli.5
Modello matematico
• Variabili decisionali:
soluzione = sottoinsieme di archi
per ogni lato e∈E
⎧1 se lato e in soluzione
xe = ⎨
⎩0 altrimenti
• Funzione obiettivo:
Minimizzare il costo degli archi scelti
z = min
∑ ce xe
e∈ E
D. Vigo
(1)
TSP−Modelli.6
3
Vincoli di grado
• Ogni vertice deve avere due archi incidenti
∑xe = 2
e∈δ (i )
∀ i ∈V
(2)
i
δ(i)
D. Vigo
TSP−Modelli.7
Soluzione non ammissibile
Subtour isolato
D. Vigo
TSP−Modelli.8
4
Vincoli di connessione 1
• Vincoli di taglio (CUT):
Ogni taglio deve essere attraversato almeno 2 volte
∑ xe ≥ 2
e∈δ ( S )
∀ S ⊂V, S ≥ 2
(3)
S
D. Vigo
TSP−Modelli.9
Vincoli di connessione 2
• Vincoli di Subtour Elimination (SEC):
il numero di archi interni ad un sottoinsieme S
selezionati deve essere minore di |S|
∑ xe ≤ S − 1
e∈σ ( S )
∀ S ⊂V, S ≥ 2
(4)
S
D. Vigo
TSP−Modelli.10
5
Equivalenza CUT e SEC
• I vincoli di tipo CUT e SEC sono equivalenti
∑ xe ≥ 2
e∈δ ( S )
∀ S ⊂V, S ≥ 2
⎛
∑ xe = ∑ ⎜⎜ ∑ xe −
i∈S ⎝ e∈δ (i )
e∈δ ( S )
2S − 2
∑ xe ≥ 2
e∈σ ( S )
∑ xe ≤ S − 1
e∈σ ( S )
=2
⎞
⎟≥2
⎟
e∈(δ (i )∩σ ( S ) ) ⎠
∑ xe
∀ S ⊂V, S ≥ 2
∀ S ⊂V, S ≥ 2
D. Vigo
TSP−Modelli.11
Modello STSP
(STSP1)
z = min ∑ ce xe
(1)
e∈E
∑ xe = 2
∀ i ∈V
(2)
∀ S ⊂V, S ≥ 2
(3)
e∈δ (i )
∑ xe ≥ 2
e∈δ ( S )
0 ≤ xe ≤ 1 ∀ e ∈ E
(5’)
∀e∈ E
(5’’)
xe intera
D. Vigo
TSP−Modelli.12
6
Asymmetric TSP (ATSP)
• Variabili decisionali:
per ogni arco (i,j)∈A
⎧1 se arco (i, j ) in soluzione
xij = ⎨
⎩0 altrimenti
• Funzione obiettivo:
assumiamo grafo completo: (i,j)∈A ∀ i,j =1,…,n
z = min
n
n
∑ ∑ c ij x ij
(1)
i =1 j =1
D. Vigo
TSP−Modelli.13
Vincoli di grado
• Ogni vertice deve avere un arco entrante ed uno
uscente
n
∑xij = 1
j=1
i
n
∑xij = 1
i=1
D. Vigo
∀ i = 1,K, n
(2’)
∀ j = 1,K, n
(2’’)
TSP−Modelli.14
7
Vincoli CUT
• Vincoli di taglio (CUT):
Ogni taglio (orientato) deve essere attraversato
almeno 1 volta
∑ ∑ xij ≥1
∀ S ⊂V, S ≥ 2
(3’)
∑ ∑ xij ≥1
∀ S ⊂V, S ≥ 2
(3’’)
i∈S j∉S
i∉S j∈S
Basta imporre una sola
famiglia perchè (3’) per S
equivale a (3’’) per V\S
S
D. Vigo
TSP−Modelli.15
Vincoli SEC
• Vincoli di Subtour Elimination (SEC):
il numero di archi interni ad un sottoinsieme S
selezionati deve essere minore di |S|
∑∑ xij ≤ S − 1
∀ S ⊂V, S ≥ 2
(4)
i∈S j∈S
S
D. Vigo
TSP−Modelli.16
8
Modello ATSP
n
n
z = min ∑∑ cij xij
(ATSP1)
n
(1)
i =1 j =1
∑xij = 1
∀ i = 1,K, n
(2’)
∑xij = 1
∀ j = 1,K, n
(2’’)
∀ S ⊂V, S ≥ 2
(3’)
j=1
n
i=1
∑ ∑ xij ≥1
i∈S j∉S
0 ≤ xij ≤ 1 ∀ i, j = 1,K, n
xij intera
∀ i, j = 1,K, n
D. Vigo
(5’)
(5’’)
TSP−Modelli.17
Varianti
• I grafi non completi possono essere trattati
ponendo il costo degli archi/lati non esistenti a +∞
• Il modello ATSP può essere facilmente adattato al
caso di grafi sparsi impiegando sommatorie estese
ai soli archi esistenti: (i,j)∈A e j∈Γ+(i)
• Il modello STSP può anche essere scritto con la
doppia sommatoria sui vertici ma considerando
solo le coppie di indici in cui i < j
(STSP' )
n
z = min ∑
n
∑ cij xij
i =1 j =i +1
D. Vigo
TSP−Modelli.18
9
Inconvenienti
• I vincoli CUT o SEC sono in numero esponenziale
Infatti S={S⊂V: |S| ≥ 2} se |V| = n allora |S|=O(2n)
• Modello alternativo (Miller, Tucker, Zemlin, 1960)
• Richiede un numero di vincoli polinomiale
i
ui variabile continua
(libera) che rappresenta
la posizione del vertice i
nel circuito
j
D. Vigo
TSP−Modelli.19
Subtour Elimination di MTZ
Se xij = 1 Î uj ≥ ui + 1
Se xij = 0 Î nessuna relazione tra uj ed ui
Ossia
(uj − ui − 1) xij = 0 Î non lineare !
Si può linearizzare in
(6)
uj − ui − 1 + (1 − xij) n ≥ 0 ∀ (i,j) ∈A, i,j ≠ 1
• Se xij = 1 Î uj ≥ ui + 1
• Se xij = 0 Î uj − ui ≥ − n + 1 Î sempre verificato!
•
•
•
•
i
ui
D. Vigo
j
uj
TSP−Modelli.20
10
Subtour Elimination di MTZ
• Data E' soluzione ammissibile (tour) Î
∃ ui ∀i∈V \{1}, tali che (6) siano soddisfatti
• Es. (1,4,5,2,3) Î u1=0, u4=1, u5=2, u2=3, u3=4
• Se consideriamo una soluzione inammissibile
i
j
k
1
Non esistono ui, uj , uk che
soddisfino simultaneamente :
uj − ui − 1 ≥ 0
uk − uj − 1 ≥ 0
ui − uk − 1 ≥ 0
D. Vigo
TSP−Modelli.21
Modello ATSP con MTZ
(ATSP2)
n
n
z = min ∑∑ cij xij
∑xij = 1
j=1
n
n
(1)
i =1 j =1
∀ i = 1,K, n
(2’)
(2’’)
∑xij = 1 ∀ j = 1,K, n
i=1
u j − ui − 1 + (1 − xij ) n ≥ 0 ∀(i, j ) ∈ A; i, j ≠ 1 (6)
0 ≤ xij ≤ 1 ∀ i, j = 1,K, n
D. Vigo
xij intera
∀ i, j = 1,K, n
ui ≥ 0
∀ i = 1,K, n
(5’)
(5’’)
(7)
TSP−Modelli.22
11
Modello STSP con MTZ
(STSP2 )
z = min ∑ ce xe
(1)
e∈E
∑xe = 2
e∈δ (i )
∀ i ∈V
(2)
u β (e ) − uα (e ) − 1 + (1 − xe ) n ≥ 0 ∀e ∈ E ;α (e ), β (e ) ≠ 1 (6)
0 ≤ xe ≤ 1 ∀ e ∈ E
(5’)
xe intera
∀e∈ E
ui ≥ 0
∀ i = 1,..., n
(5’’)
(7)
D. Vigo
TSP−Modelli.23
Confronto tra modelli
Variabili
ATSP1
ATSP2
n2
n2 + n
Vincoli n+ n2 + 2n n2 + n (+n)
• Per STP1 e 2 considerazioni analoghe
• In realtà il rilassamento continuo di ATSP1 è
molto più tight di quello di ATSP2
D. Vigo
TSP−Modelli.24
12
Rilassamento continuo di ATSP1
•
Il rilassamento continuo di ATSP1 può essere
risolto in modo iterativo:
1. Si risolve C(ATSP1) senza (3’)
2. Si determina se esiste un vincolo (3’) violato (si
può fare in tempo polinomiale)
a. se trovato lo si aggiunge al modello corrente, si
risolve il nuovo rilassamento continuo e si torna a 2)
b. altrimenti STOP
D. Vigo
TSP−Modelli.25
Bound per Modello STSP1
Il modello può essere rilassato come segue:
(STSP1)
∑x
e∈E
e
=n
∑ ( e∈δ (i )
i∈V
e∈δ ( S )
D. Vigo
e∈E
∑ xe = 2 ) ∀ i ∈ V
∑ xe ≥ 21
xe ∈ {0,1}
z = min ∑ ce xe
∀ S ⊂V, S ≥ 2
1
(1)
(2)
(3)
0 ≤ xe ≤ 1 ∀ e ∈ E
(5’)
∀e∈ E
(5’’)
xe intera
TSP−Modelli.26
13
Bound per Modello STSP1
Il problema è uno Shortest Spanning Tree più un
arco di costo minimo (n archi in totale)
z = min ∑ ce xe
R1(STSP1)
(1)
e∈E
∑ xe = n
(2s)
e∈E
xe ≥ 1
∑
e∈δ ( S )
∀ S ⊂V, S ≥1
(3i)
0 ≤ xe ≤ 1 ∀ e ∈ E
(5’)
∀e∈ E
(5’’)
xe intera
D. Vigo
TSP−Modelli.27
Esempio
11
2
3
2
1
2
3
3
2
4
D. Vigo
5
10
v(SST)= 2+2+2+10=16
v(R1)=v(SST) + 3 = 19
TSP−Modelli.28
14
Bound Lagrangiano
• I vincoli di grado eliminati possono essere rilassati
in modo Lagrangiano portandoli nella funzione
obiettivo (moltiplicatori λi liberi perchè vincoli di
uguaglianza):
⎛
⎞
Lλ (STSP1) z = min ∑ ce xe + ∑ λi ⎜⎜ ∑ xe − 2 ⎟⎟
e∈E
i∈V
⎝ e∈δ (i )
⎠
= min ∑ ce xe − 2∑ λi + ∑ λi ∑ xe
e∈E
i∈V
i∈V
e∈δ ( i )
• il lato e=(α(e),β(e)) compare due volte, una per
ogni vertice estremo
D. Vigo
TSP−Modelli.29
Bound Lagrangiano
Lλ (STSP1)
⎛
⎞
z = min ∑ ce xe + ∑ λi ⎜⎜ ∑ xe − 2 ⎟⎟
e∈E
i∈V
⎝ e∈δ (i )
⎠
= min ∑ ce xe − 2∑ λi + ∑ λi ∑ xe
e∈E
i∈V
i∈V
e∈δ ( i )
= min ∑ ce xe − 2∑ λi + ∑ (λα ( e ) + λβ (e ) ) xe
e∈E
i∈V
e∈E
i∈V
= min ∑ ce′ xe − 2∑ λi
dove
D. Vigo
e∈E
ce′ = ce + λα ( e ) + λβ (e )
TSP−Modelli.30
15
Bound Lagrangiano
Lλ (STSP1) z = min ∑ ce′ xe − 2∑ λi
e∈E
x
∑
∈
i∈V
=n
(2s)
∑ xe ≥1 ∀ S ⊂ V , S ≥ 1
(3i)
e
e E
e∈δ ( S )
xe ∈ {0,1}
∀e∈ E
(5’’’)
Lλ (STSP1) = v(SST ) + ce′ − 2∑ λi
dove
ce′ = min{ce′ : e ∉ SST}
i∈V
D. Vigo
TSP−Modelli.31
Bound r-SST
si sceglie un vertice r∈V
∑x
∈δ ( )
e
e
r
x
∑
∈ δ{ }
e
e E\
=2
(STSP1)
z = min ∑ ce xe
e∈E
=n−2
r
( ∑ xe = 2 ) ∀ i ∈ V
∑
∈ { }e∈δ (i )
∑x
D. Vigo
(2)
i V\ r
e∈δ ( S )
xe ∈ {0,1}
(1)
e
≥2 ∀ S ⊂ V \ {r}, S ≥ 2
1
1
0 ≤ xe ≤ 1 ∀ e ∈ E
xe intera
∀e∈ E
(3)
(5’)
(5’’)
TSP−Modelli.32
16
Bound r-SST
(r − SST)
z = min ∑ ce xe
∑x
e∈δ ( r )
∑x
e
e
S
=2
(1)
(2r)
=n−2
(2’)
≥ 1 ∀ S ⊂ V \ {r}, S ≥ 1
(3)
e
e∈E \δ {r }
x
∑
∈δ ( )
e
e∈E
xe ∈ {0,1}
(5’’’)
• SST’= SST su G’=(V \{r},E \δ(r))
• 2 archi a costo minimo incidenti in r: (r,r1), (r,r2)
D. Vigo
TSP−Modelli.33
Esempio
11
2
3
2
1
2
3
3
2
4
D. Vigo
5
10
v(1−SST) = (3+3+10)+(2+2) = 20
TSP−Modelli.34
17
Esempio
11
2
3
2
1
5
2
3
3
2
4
10
v(5−SST) = (2+2+2)+(10+11) = 27
D. Vigo
TSP−Modelli.35
Bound Lagrangiano
• I vincoli di grado eliminati possono essere rilassati
in modo Lagrangiano come fatto precedentemente:
Lλ (r - SST ) = v(SST′) + cr′ + cr′ − 2∑ λi
1
dove
D. Vigo
ce′ = ce + λα ( e ) + λβ (e )
2
i∈V
TSP−Modelli.36
18
Determinazione dei λi
λi = α (di−2)
•
•
•
•
•
•
Dove di
λi > 0
λi < 0
λi = 0
Inoltre
i =1, …, n ed α > 0
grado del vertice nella soluzione corrente
se di > 2
se di < 2
se di = 2
n
n
i =1
i =1
∑ λi = α ∑ (di − 2) = α (2n − 2n ) = 0
D. Vigo
TSP−Modelli.37
Ottimizzazione subgradiente
1.
2.
3.
4.
5.
6.
Poni λi=0 per i=1, …, n; Poni k=0, L=0;
Calcola r−SST(λ) e poni L=max{L,v(r−SST(λ))};
Calcola di per i=1, …, n;
If di = 2 per i=1, …, n then z*=L e STOP;
Poni k = k + 1; if k > kmax then STOP;
Poni λi=λi +α (di−2) per i=1, …, n e vai al passo 2.
n
α = f (k ) = β (U − L) / ∑ (di − 2)2
con 0 < β ≤ 2
i =1
D. Vigo
TSP−Modelli.38
19
Esempio
2
2
3
5
2
3
2
1
11
2
3
2
λ =(0, 0, 0, 0, 0)
3
2
10
4
1
v(5−SST) = (2+2+2)+(10+11) = 27
d = (3, 2, 2, 1, 2), α =1
λ =(1, 0, 0, -1, 0)
D. Vigo
TSP−Modelli.39
Esempio
2
2
3
5
2
3
3
1
11
3
3
2
2
4
1
10
2
ce′ = ce + λα ( e ) + λβ (e )
λ =(1, 0, 0, -1, 0)
v(5−SST) = (2+2+3)+(10+11) = 28
d = (2, 2, 2, 2, 2), STOP !
D. Vigo
TSP−Modelli.40
20