aula 11-rot-2011-02

aula 11-rot-2011-02


DisciplinaLogística e Transporte105 materiais1.506 seguidores
Pré-visualização2 páginas
com os nós visitados mais de uma vez e 
utilizar a desigualdade triangular.
Roteirização de Veículos
TRANSLOG
8
7
6
5
4
3
2
1
ÁRVORE DE EXTENSÃO MÍNIMA
D
Roteirização de Veículos
TRANSLOG
1 2 3 4 5 6 7 8 D
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5
4 - - - - 43,3 70,5 44,3 94,3 120,5
5 - - - - - 42,1 42,9 70,3 108,2
6 - - - - - - 35,6 28,3 68,6
7 - - - - - - - 52,5 76,5
8 - - - - - - - - 43,5
MATRIZ DE DISTÂNCAS em km
Roteirização de Veículos
TRANSLOG
8
7
6
5
4
3
2
1
D
65,0
43,3 64,8
68,6
1ª TENTATIVA L\u2019 =241,7 km
Roteirização de Veículos
TRANSLOG
8
7
6
5
4
3
2
1
D
2ª TENTATIVA L\u2019=224,3 km
65,0
40,7
42,1
76,5
Roteirização de Veículos
TRANSLOG
8
7
6
5
4
3
2
1
D
34,1
3ª TENTATIVA L\u2019=198,2 km
64,8
68,6
30,7
ROTEIRO DE EULER: D-8-6-5-1-5-4-2-4-3-7-6-D
Roteirização de Veículos
TRANSLOG
8
7
6
5
4
3
2
1
D
ROTEIRO DE EULER: D-8-6-5-1-5-4-2-4-3-7-6-D
l14< l15 + l54
l12< l14 + l42
l7D< l76 + l6D
Roteirização de Veículos
TRANSLOG
1 2 3 4 5 6 7 8 D
1 - 65,0 102,0 61,5 30,7 67,9 73,5 95,6 136,2
2 - - 54,9 34,1 62,8 99,5 77,9 125,5 154,3
3 - - - 40,7 82,5 99,3 64,8 116,7 130,5
4 - - - - 43,3 70,5 44,3 94,3 120,5
5 - - - - - 42,1 42,9 70,3 108,2
6 - - - - - - 35,6 28,3 68,6
7 - - - - - - - 52,5 76,5
8 - - - - - - - - 43,5
MATRIZ DE DISTÂNCAS em km
Roteirização de Veículos
TRANSLOG
8
7
6
5
4
3
2
D
1
L=425,7 km
ROTEIRO FINAL OTIMIZADO
Roteirização de Veículos
TRANSLOG Roteirização de Veículos
VI. ROTEIRIZAÇÃO COM RESTRIÇÕES MÚLTIPLAS
USO DO MÉTODO DE 
CLARKE & WRIGHT CONCEITO DE GANHO
Depósito : n pontos, com retorno a D
1ª Solução:
n veículos; 1 por ponto com o roteiro : D \u2192\u2192\u2192\u2192 ponto \u2192\u2192\u2192\u2192 D
Percurso Total: \u2211
=
=
n
i
iDlL
1
,
2
TR
A
N
SL
O
G
C
D
6
1
2
5
3
4
TRANSLOG Roteirização de Veículos
i
j
D
i
j
D
(a) (b)
Ganho S(i, j) = La - Lb
=2 . dD,i + 2.d D, j - [ dD, j + di, j + dj, D ]
S (i, j) = dD, i + dD, j - di, j
Buscar par de pontos i, j com maior valor de ganho que 
não violem restrições de tempo e capacidade.
TRANSLOG Roteirização de Veículos
Roteiro
Um roteiro é uma sequência de arcos e nós, saindo 
do depósito, visitando um conjunto de pontos e 
retornando ao depósito. Um roteiro pode, em geral , 
ser percorrido nos dois sentidos. Trata-se portanto 
de um ciclo.
Os pontos, ou nós, do roteiro, vizinhos ao depósito 
serão considerados como pontos extremos do roteiro.
D
extremo
extremo
TRANSLOG Roteirização de Veículos
Método de Clarke & Wright
a. Calcular ganhos s(i,j) para 
todo i e j, i\u2260D, j\u2260D.
b. Ordenar pares de nós, na 
ordem decrescente de 
ganhos.
c. Enquanto não terminar a 
lista de ganhos: Tomar 
pares i,j na ordem.
TRANSLOG Roteirização de Veículos
1. Se i e j não estão em nenhum roteiro então
criar um roteiro com i e j . (D-i-j-D).
Método de Clarke & Wright
D
i
j
No k ésimo par da lista:
TRANSLOG Roteirização de Veículos
2. Se somente um nó, ou i ou j, está em um roteiro então
Se este nó é um extremo de um roteiro então
agrega o arco (i,j) ao roteiro.
k
ji
l
D
Método de Clarke & Wright
TRANSLOG Roteirização de Veículos
3. Se somente um nó, ou i, ou j, está em um roteiro então
Se este nó não é um extremo de um roteiro então
abandona i,j.
Método de Clarke & Wright
k
ji
l
D
TRANSLOG Roteirização de Veículos
4. Se i e j estão em roteiros diferentes então
Se i e j são extremos de seus roteiros então
Une os dois roteiros.
Método de Clarke & Wright
k
j
i
l
D
h
TRANSLOG Roteirização de Veículos
5. Se i e j estão em roteiros diferentes então
Se i ou j ou ambos não são extremos de seus 
roteiros então
abandona i,j.
k
j
i l
D
h
TRANSLOG
Se ao terminar a lista, sobrar algum nó k não 
incluído em roteiro, criar roteiros individualizados: 
D-k-D.
Sempre testar as restrições de capacidade e 
tempo de ciclo
TRANSLOG Roteirização de Veículos
D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
TRANSLOG Roteirização de Veículos
Pontos de 
Entrega
X (km) Y (km) Peso médio
por entrega
(t)
1 14 40 3,0
2 10 83 2,7
3 27 60 0,9
4 67 80 1,2
5 80 57 0,8
6 90 93 2,6
TRANSLOG Roteirização de Veículos
\ufffdCapacidade do veículo (c)= 6 t
\ufffdFator de correção (m. euclidiana) = 1,20
\ufffdTempo de ciclo: 12 h
\ufffdTempo médio parada para desc : 1,5h
\ufffdVelocidade média: 60 km/h
\ufffdCoordenadas do Depósito: (0,0)
TRANSLOG Roteirização de Veículos
1 (4,6) 248,8
2 (5,6) 228,3
3 (4,5) 211,4
4 (2,6) 158,9
5 (2,4) 157,0
6 (3,4) 150,5
7 (3,6) 148,9
8 (2,3) 144,9
9 (3,5) 133,1
10 (2,5) 128,6
11 (1,3) 101,2 
12 (1,2) 99,3 
13 (1,4) 96,4
14 (1,6) 95,0 
15 (1,5) 86,9 D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
Testar 4-6-5
TRANSLOG
· tempo do depósito ao primeiro ponto da rota 
· mais o tempo do último ponto da rota ao depósito 
· mais o tempo de percurso entre pontos sucessivos 
na rota 
· mais o tempo total perdido em paradas nos pontos 
(tp).
TEMPO DE CICLO
Ao ser criada uma rota TC=tDi+tij+tjD+2tp
Ao ser incluído um par 
qualquer j,k em rota 
existente, com o nó j já
pertencente à rota: o novo 
tempo de ciclo
T\u2019C=TC-tjD+tjk+tkD+tp
TRANSLOG Roteirização de Veículos
Testar 4-6-5
TC=9,8 < 12h
Carga=1,2+2,6+0,8=4,6 < 6t
D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
TRANSLOG Roteirização de Veículos
1 (4,6) 248,8
2 (5,6) 228,3
3 (4,5) 211,4
4 (2,6) 158,9
5 (2,4) 157,0
6 (3,4) 150,5
7 (3,6) 148,9
8 (2,3) 144,9
9 (3,5) 133,1
10 (2,5) 128,6
11 (1,3) 101,2 
12 (1,2) 99,3 
13 (1,4) 96,4
14 (1,6) 95,0 
15 (1,5) 86,9 
D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
Testar 2-4-6-5
TC=12,1 > 12h
Carga=2,7+4,6=7,3 > 6t
TRANSLOG Roteirização de Veículos
1 (4,6) 248,8
2 (5,6) 228,3
3 (4,5) 211,4
4 (2,6) 158,9
5 (2,4) 157,0
6 (3,4) 150,5
7 (3,6) 148,9
8 (2,3) 144,9
9 (3,5) 133,1
10 (2,5) 128,6
11 (1,3) 101,2 
12 (1,2) 99,3 
13 (1,4) 96,4
14 (1,6) 95,0 
15 (1,5) 86,9 
Testar 3-4-6-5
TC=11,5 < 12h
Carga=0,9+4,6=5,5 < 6t
D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
TRANSLOG Roteirização de Veículos
1 (4,6) 248,8
2 (5,6) 228,3
3 (4,5) 211,4
4 (2,6) 158,9
5 (2,4) 157,0
6 (3,4) 150,5
7 (3,6) 148,9
8 (2,3) 144,9
9 (3,5) 133,1
10 (2,5) 128,6
11 (1,3) 101,2 
12 (1,2) 99,3 
13 (1,4) 96,4
14 (1,6) 95,0 
15 (1,5) 86,9 
Testar 2-3-4-6-5
TC > 12h
Carga > 6t
Testar 1-3-4-6-5
TC > 12h
Carga > 6t
TRANSLOG Roteirização de Veículos
1 (4,6) 248,8
2 (5,6) 228,3
3 (4,5) 211,4
4 (2,6) 158,9
5 (2,4) 157,0
6 (3,4) 150,5
7 (3,6) 148,9
8 (2,3) 144,9
9 (3,5) 133,1
10 (2,5) 128,6
11 (1,3) 101,2 
12 (1,2) 99,3 
13 (1,4) 96,4
14 (1,6) 95,0 
15 (1,5) 86,9 
Testar 1-2
TC=6,4 < 12h
Carga=5,7< 6t
D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
TRANSLOG Roteirização de Veículos
1 (4,6) 248,8
2 (5,6) 228,3
3 (4,5) 211,4
4 (2,6) 158,9
5 (2,4) 157,0
6 (3,4) 150,5
7 (3,6) 148,9
8 (2,3) 144,9
9 (3,5) 133,1
10 (2,5) 128,6
11 (1,3) 101,2 
12 (1,2) 99,3 
13 (1,4) 96,4
14 (1,6) 95,0 
15 (1,5) 86,9 
Testar 3-4-6-5-1-2
TC=16,4 > 12h
Carga=11,2 > 6t
D
100
100
50
50
25
25
75
75
1
2
3
4
5
6
TRANSLOG Roteirização de Veículos
Até dia 11/11!!!