Modelo de Roteamento de Veículos

Prévia do material em texto

Aula 36
Módulo 4.7 – Roteamento de Veículos:Modelo by A.A.
Pesquisa Operacional II
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
2
1
3
4
3
4
2
6
3
1
3
3
3
1
10
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
2
1
3
4
3
4
2
6
3
1
3
3
3
1
10
10
10
10
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
C = {1, ..., n}
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
N = C{0, n+1}
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
E = {(i,j): i, jN, ij, 
in+1, j0}
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n+1
E = {(i,j): i, jN, ij, 
in+1, j0}
Roteamento de Veículos
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n+1
E = {(i,j): i, jN, ij, i n+1, j0}
Roteamento de Veículos
i
j
xij
Variáveis de Decisão
Xijk = 1 se o veículo k vai do nó i para o nó j.
xi jk
Origem
(Cidade i)
Destino
(Cidade j)
Veículo k
Roteamento de Veículos
10
1
5
2
3
x131
x121
Variáveis de Decisão
x151
4
Xijk = 1 se o veículo k vai do nó i para o nó j.
x141
x411
x311
x211
x511
Roteamento de Veículos
11
1
5
2
3
x131
x121
Dado o veículo 1 na cidade 1, qual será a próxima cidade?
x151
4
x141
x121 + x131 + x141 + x151
Veículo 1
Roteamento de Veículos
12
1
5
2
3
x132
x122
Dado o veículo 1 na cidade 1, qual será a próxima cidade?
x152
4
x142
x122 + x132 + x142 + x152
Veículo 2
Roteamento de Veículos
13
1
5
2
3
x133
x123
Dado o veículo 1 na cidade 1, qual será a próxima cidade?
x153
4
x143
x123 + x133 + x143 + x153
Veículo 3
Roteamento de Veículos
14
1
5
2
3
x134
x124
Dado o veículo 1 na cidade 1, qual será a próxima cidade?
x154
4
x144
x124 + x134 + x144 + x154= 1
Veículo 4
Roteamento de Veículos
15
i
5
2
3
xijk
4
Dado o veículo k na cidade i, qual será a próxima cidade j?
Roteamento de Veículos
16
MAS...
1
4
2
3
5
6
7
As restrições anteriores permitem a existência de sub-rotas !!
1
4
2
3
5
6
7
Roteamento de Veículos
17
1
5
2
3
x211
Eliminação de sub-rotas com dois nós
4
x121
x121 + x211  1
Roteamento de Veículos
18
1
2
x211
Eliminação de sub-rotas com dois nós
x121
x121 + x211  1
Roteamento de Veículos
19
1
2
x211
Eliminação de sub-rotas com dois nós
x121
x121 + x211  1
1
2
x211
x121
ou
Roteamento de Veículos
20
1
2
x211
Eliminação de sub-rotas com dois nós
x121
x121 + x211  1
1
2
x211
x121
1
2
x211
x121
ou
ou
Roteamento de Veículos
21
1
5
2
3
x211
Eliminação de sub-rotas com dois nós
4
x121
x131
x311
x141
x411
x511
x151
xijk + xjik  1
Roteamento de Veículos
22
1
5
2
3
Eliminação de sub-rotas com três nós
4
x121
x231
x311
x121 + x231 + x311  2
Roteamento de Veículos
23
1
5
2
3
Eliminação de sub-rotas com três nós
4
xijk + xjtk + xtik  2
Roteamento de Veículos
24
1
5
2
3
Eliminação de sub-rotas com três nós
4
Eliminação 
sub-rotas
Roteamento de Veículos
25
A demanda total da rota não excede a capacidade do veículo k
1
2
3
4
0
2
1
3
4
10
x301
x041
x421
x211
x131
d0x041 + d4x421 + d2x211 + d1x131 + d3x301  10
Roteamento de Veículos
26
Problema de Designação
1
2
3
4
0
2
1
3
4
10
A demanda total da rota não excede a capacidade do veículo k
27
5
2
3
x133
x123
x153
4
x143
x023 + x033 + x043 + x053= 1
Veículo 3
0
Restrição de Fluxo em Redes: Veículo sai do depósito 1 só vez
Roteamento de Veículos
28
5
2
3
x133
x123
Restrição de Fluxo em Redes: Veículo sai do depósito 1 só vez
x153
4
x143
Veículo 3
0
Roteamento de Veículos
29
1
Restrição de Fluxo em Redes: Deixar o nó somente se entrou
x213 + x313 + x413 + x513= 0
x213
x313
x413
x513
Veículo 3
Roteamento de Veículos
30
1
Restrição de Fluxo em Redes: Deixar o nó somente se entrou
Roteamento de Veículos
31
5
2
3
x133
x123
x153
4
x143
X2,n+1,3 + x3,n+1,3 + x4,n+1,3 + x5,n+1,3= 1
Veículo 3
n+1
Restrição de Fluxo em Redes: Veículo sai do depósito 1 só vez
Roteamento de Veículos
32
Restrição de Fluxo em Redes: Retornar ao nó n+1 somente 1 vez
5
2
3
x3,n+1,3
x2,n+1,3
x5,n+1,3
4
x4,n+1,3
Veículo 3
n+1
Roteamento de Veículos
33
S.a.:
MODELO COMPLETO GERAL
Min 
custo para realizar percorrer a rota i-j
Roteamento de Veículos
34
Aula 36
Módulo 4.7 – Roteamento de Veículos:Modelo by A.A.
Pesquisa Operacional II
35
C
i
 
,
 
1
Î
"
=
å
å
Î
Î
K
k
N
j
ijk
x
K
k
S
C
S
S
x
S
j
i
ijk
Î
"
ú
û
ú
ê
ë
ê
£
£
Ì
-
£
å
Î
;
2
n
2
;
 
,
1
,
K
 
,
 
Î
"
£
å
å
Î
Î
k
Q
x
d
C
i
N
j
ijk
i
K
k
x
N
j
jk
Î
"
=
å
Î
,
1
0
K
 
C,
 
,
 
0
Î
"
Î
"
=
-
å
å
Î
Î
k
h
x
x
N
i
N
j
hjk
ihk
K
k
x
N
i
k
n
i
Î
"
=
å
Î
+
,
1
,
1
,
C
i
 
,
 
1
Î
"
=
å
å
Î
Î
K
k
N
j
ijk
x
K
k
x
N
i
k
n
i
Î
"
=
å
Î
+
,
1
,
1
,
E
K
ijk
B
x
Î
å
å
=
Î
K
k
E
j
i
ijk
ij
x
c
1
)
,
(