aula 11-rot-2011-02

aula 11-rot-2011-02


DisciplinaLogística e Transporte108 materiais1.540 seguidores
Pré-visualização2 páginas
TR
A
N
SL
O
G
R
o
te
ir
iz
a
çã
o
de
 
V
eí
cu
lo
s
I.
R
ed
e
de
 
Tr
a
n
sp
o
rt
e:
 
D
ef
in
iç
õe
s
e 
Pr
o
pr
ie
da
de
s
G
ra
fo
G
(N
,A
)
1
2
4
3
5
6
N
ós
: 
1,
2,
3\u2026
,
6
A
rc
o
s:
 
(1,
2),
(2,
3)\u2026
TRANSLOG Roteirização de Veículos
GRAFO ORIENTADO:
3
1
2
4
5
6
GRAFO NÃO ORIENTADO:
1
2
4
3
5
6
TRANSLOG Roteirização de Veículos
GRAFO MISTO: 3
1
2
4
5
6
TRANSLOG Roteirização de Veículos
1
2
4
3
5
6
1 e 2 NÓS ADJACENTES
(1,2) e (2,3) ARCOS ADJACENTES
3
1
2
4
5
6
GRAUS DE CONVERGÊNCIA E 
DIVERGÊNCIA
Semi-grau interior
Semi-grau exterior
TRANSLOG Roteirização de Veículos
CAMINHO : SEQUÊNCIA DE NÓS E ARCOS ORIENTADOS 
ADJACENTES 3
1
2
4
5
6
CAMINHO 1 a 6: 1,2,3,6
CAMINHO ELEMENTAR: CADA ARCO SÓ UMA VEZ NA SEQUÊNCIA
TRANSLOG
CIRCUITO: CAMINHO COM NÓ FINAL = NÓ INICIAL
EM GRAFOS NÃO ORIENTADOS TEM-SE CADEIA NO 
LUGAR DE CAMINHO E CICLO NO LUGAR DE 
CIRCUITO
3
1
2
4
5
6
Roteirização de Veículos
TRANSLOG Roteirização de Veículos
CONECTIVIDADE DE REDE
1
2
4
3
5
6
Nós i e j acessíveis se há um caminho ligando i a j
3
1
2
4
5
6
Nós i e j conectados se há uma cadeia entre eles.
TRANSLOG Roteirização de Veículos
Grafo fortemente Conectado:
Existe um caminho entre cada par i/j do grafo
SUB-GRAFO:
G\u2019 (N\u2019, A\u2019) : N\u2019 \u2282\u2282\u2282\u2282 N ; A\u2019 \u2282\u2282\u2282\u2282 A
3
1
2
4
5
6
GRAFO PARCIAL:
G\u2019 (N\u2019, A\u2019) : N\u2019 = N ; A\u2019 \u2282\u2282\u2282\u2282 A
Grafo Conectado:
Existe uma cadeia entre cada par i/j do grafo
TRANSLOG Roteirização de Veículos
ÁRVORE DE UM GRAFO: (NÃO ORIENTADO):
SUB-GRAFO CONECTADO SEM CICLOS
2
1
5
3
8
6 9
10
4
7Para k nós \u2192\u2192\u2192\u2192 k - 1 arcos
TRANSLOG Roteirização de Veículos
ÁRVORE COMPLETA DE UM GRAFO: (NÃO 
ORIENTADO):
GRAFO PARCIAL CONECTADO SEM CICLOS
1
2
4
3
5
6
TRANSLOG Roteirização de Veículos
2
1
5
3
8
6 9
10
4
7
Para n nós \u2192\u2192\u2192\u2192 n - 1 arcos
ÁRVORE COMPLETA
TRANSLOG Roteirização de Veículos
2
1
5
3
8
6 9
10
4
7
2
1
5
3
8
6 9
10
4
7
TRANSLOG Roteirização de Veículos
A CADA ARCO É ASSOCIADA UMA EXTENSÃO
REDE DE TRANSPORTE:
( )ji,l
A EXTENSÃO DE UM CAMINHO S QUE LIGA i A j É:
( ) ( )
( )
\u2211
\u2208
=
Sji
jiSL
,
,l
TRANSLOG Roteirização de Veículos
PROPRIEDADE:
Em grafo não orientado, o arco com extensão mínima
incidente a um nó qualquer sempre faz parte da árvore 
completa de extensão mínima.
10
7
6
II. ÁRVORE COMPLETA DE EXTENSÃO MÍNIMA
TRANSLOG Roteirização de Veículos
c) Entre todos os nós presentes na árvore atual, busque
um arco (i,j) incidente com extensão mínima, cujo nó
j, adjacente ainda não está na árvore. Incorporar o
arco e o nó adjacente à árvore e voltar para b).
PROCEDIMENTO (Algoritmo de PRIM)
a) Iniciar com qualquer nó i: Determinar o arco com 
extensão mínima (incidente a i); incluir arco (i, j) e nó j 
na árvore.
b) Se todos os nós já estão na árvore termine. 
Senão \u2192\u2192\u2192\u2192 vá para c).
TRANSLOG Roteirização de Veículos
2
1
5
3
8
6 9
10
4
7
1
3
4
2
4
3
5
4
6
73
8
6
3 4
3
L= 1+3+4+3+2+3+3+3+4=26
TRANSLOG Roteirização de Veículos
2
1
5
3
8
6 9
10
4
7
1
3
2
4
34
3
3
3
L= 1+3+4+3+2+3+3+3+4=26
TRANSLOG
2
1
5
3
8
6 9
10
4
7
Pergunta
4
4
3
5
2
2
6
2
5
4
2 3
Calcule a árvore de extensão mínima da rede a seguir
5
6
6
4
TRANSLOG Roteirização de Veículos
III. COBERTURA DE VIAS (CARTEIRO CHINÊS)
Coleta de Lixo: Percorrer Redes
Entrega Postal (Correio)
Limpeza de Ruas
PROBLEMA DAS 7 PONTES DE KÖNIGSBERG
TRANSLOG Roteirização de Veículos
LEONHARD EULER \u2013 TEORIA DOS GRAFOS
Problema
Grafo
TRANSLOG Roteirização de Veículos
PROBLEMA DO CARTEIRO CHINÊS (PCC)
(Chinese Mathematics, Kwan Mei-Ko )
\u2022 Grafo não orientado G(N,A); arcos com 
extensão l(i, j) > 0.
\u2022 Encontrar percurso que cubra todos os 
arcos de G pelo menos uma vez e que tenha 
extensão mínima.
L n i j l i j
i j A
=
\u2200 \u2208
\u2211 ( , ) . ( , )
( , )
n (i, j) : No de vezes que arco (i, j) é percorrido
TRANSLOG
2
1
5
3
8
6 9
10
4
7
1
3
4
2
4
3
5
4
6
73
8
6
3 4
3
1)Caminho (Cadeia) de Euler: Cadeia que cobre 
todos os arcos somente uma vez. No inicial \u2260\u2260\u2260\u2260 nó
final.
Roteirização de Veículos
ALGUMAS DEFINIÇÕES:
TRANSLOG
2
1
5
3
8
6 9
10
4
7
1
3
4
2
4
3
5
4
6
73
8
6
3 4
3
2)Roteiro de Euler: Ciclo que atravessa 
todos os arcos de G somente uma vez.
Roteirização de Veículos
TRANSLOG
3)Grau de um nó: No de arcos incidentes ao nó
2
1
5
3
8
6 9
10
4
7
1
3
4
2
4
3
5
4
6
73
8
6
3 4
3
Roteirização de Veículos
TRANSLOG
PERGUNTA
Desenhe os menores Roteiro de Euler e 
Caminho de Euler. 
TRANSLOG
1. Um grafo conexo G (não orientado) possui um 
Roteiro de Euler se e somente se não contiver 
nenhum nó impar.
TEOREMAS DE EULER
2
1
5
3
8
6 9
10
4
7
1
3
4
2
4
3
5
4
6
73
8
6
3 4
3
Roteirização de Veículos
TRANSLOG
2. Um grafo conexo G possui uma cadeia de Euler se e 
somente se G contiver exatamente dois nós de grau 
impar.
TEOREMAS DE EULER
2
1
5
3
8
6 9
10
4
7
1
3
4
2
4
3
5
4
6
73
8
6
3 4
3
Roteirização de Veículos
TRANSLOG
PROBLEMA DAS 7 PONTES DE KÖNIGSBERG
Roteirização de Veículos
TRANSLOG
2
1
3
4
Roteiro de Euler
2,3,4,1,3,1,2
1
2 4
5
3
6
Caminho (Cadeia) de Euler
2,1,6,5,3,2,4,3,1,5,4
PROPRIEDADE: NO DE 
NÓS DE GRAU ÍMPAR 
EM G É SEMPRE PAR.
Roteirização de Veículos
TRANSLOG
Roteiro saindo de depósito e cobrindo a rede (arcos) 
com custo mínimo.
Roteiro de Euler nem sempre é viável. Alguns arcos 
são usados mais de uma vez.
Tomar rede com nós de grau ímpar. Criar arcos 
fictícios ligando pares de nós impares \u21d2\u21d2\u21d2\u21d2 Rede 
G\u2019(N, A\u2019).
ARCOS ARTIFICIAIS: PERCURSOS DUPLOS
SOLUÇÃO DO PROBLEMA DO CARTEIRO CHINÊS
Roteirização de Veículos
TRANSLOG
d)Definir roteiro de Euler em G\u2019. Solução ótima 
para carteiro chinês.
QUAL CONJUNTO DE ARCOS ARTIFICIAIS DÁ A 
EXTENSÃO TOTAL MÍNIMA ?
PASSOS
a) Identificar os nós grau impar em G. Seja m o nº
de nós de grau ímpar. (m é par)
b)Determinar combinações possíveis e ligação de 
cada dois nós grau ímpar.
c) Selecionar combinação com menor extensão de 
arcos artificiais \u21d2\u21d2\u21d2\u21d2 G\u2019 (N, A\u2019).
Roteirização de Veículos
TRANSLOG
A EXTENSÃO TOTAL PERCORRIDA É IGUAL À
SOMA DAS EXTENSÕES DOS ARCOS DE G(N,A) 
MAIS AS EXTENSÕES DOS ARCOS ARTIFICIAIS 
QUE FORAM INTRODUZIDOS PARA FORMAR O 
GRAFO G\u2019(N,A\u2019).
A
B
C
D
E
F
G H
I
J K
L
M
Roteirização de Veículos
TRANSLOG
A
B
C
D
E
F
G H
I
J K
M
L
500
500
1200
1120
1100 500
500
500
500
500
700600
730
700
300
1300 700
200
Roteirização de Veículos
( )\u220f
=
\u2212=
2
1
12
m
i
c iN =1x3x5x7=105m=8
TRANSLOG
A
B
C
D
E
F
G H
I
J K
M
L500
500
1200
1120
1100 500
500
500
500
500
700600
730
700
300
1300 700
200
200
600
500
A-B-C-E-J-K-L-M-H-(H-M-L)-I-H-G-F-I-J-J-E-D-B-(B-D)-
F-(F-G)-G-A=12150+2300=14450m
Roteirização de Veículos
1000
TRANSLOG
IV. PROBLEMA DO CAIXEIRO VIAJANTE 
(P.C.V.)
Passar por todos os NÓS de uma rede com percurso 
de custo mínimo.
(Traveling Salesman Problem)
N nós: Sair de base e passar pelo menos uma vez por 
cada nó e retornar
- Distribuição Física de Produtos
- Roteiros de Serviços (ex. Telemar)
Roteirização de Veículos
TRANSLOG
MÉTODOS EXATOS POUCO EFICIENTES
\u21d3\u21d3\u21d3\u21d3
PROCEDIMENTOS HEURÍSTICOS
SIMPLIFICAÇÕES (Larson & Odoni)
a)Partida. Visita a n-1 nós e retorno
b)n Pontos: rede completamente conexa 
c) Arcos: custo l(i, j)
d)Hipótese de desigualdade triangular 
l (i, j) \u2264\u2264\u2264\u2264 l (i, k) + l (k, j)
e) Distâncias simétricas : l (i, j) = l (j, i) \u2200\u2200\u2200\u2200 i,j
Roteirização de Veículos
TRANSLOG
Procedimentos: Grafo G(N, A)
a) Determinar árvore de extensão mínima \u21d2\u21d2\u21d2\u21d2 T
b) Separar No nós de Grau Impar (No par)
c) Combinar dois a dois. Escolher a seleção com 
extensão total mínima
d) Grafo M (Só os nós e arcos de ligação)
e) Grafo T \u222a\u222a\u222a\u222aM = H Admite roteiro de Euler
f) Encontrar roteiro de Euler em H. Primeira 
solução aproximada.
g) Identificar