teoria dos grafos logistica.pdf
TRANSCRIPT
-
Teoria dos Grafose Logstica
Exemplos de Aplicaes
Bruno Thom de Abrantes
-
Grafos Definio
Grafo: uma estrutura matemtica G = (X,A), onde:
X = conjunto de ns X = {x1, x2, ... , xn};
A = conjunto de arcos A = {a1, a2, ... , am};
Com cada arco ak ? A sendo definido por um par de ns do conjunto X, isto ak = (xi, xj).
A esses arcos so associados valores, que normalmente esto associados ao custo de se percorrer esse arco, e os algoritmos visam cumprir determinada tarefa com o menor custo total possvel.
-
Grafos Representaes
Forma Grfica
a4
a1
a3a
2
a 6a7
a 5
a8
x1
x2
x5
x3
x4
-
Grafos Representaes
A =
0
1
1
0
0
X5
1000X5
0101X4
0000X3
0100X2
0110X1
X4X3X2X1
Forma Algbrica (exemplos)
C =
0
c7
c6
X5
c8X5
0c5c4X4
0X3
c20X2
c3c10X1
X4X3X2X1
Matriz de Adjacncia
Matriz de Custos
-
Exemplos de Aplicaes
-
rvores
Problema: Determinar uma rvore expandida sobre o grafo que represente o menor custo total.
Exemplos:- Dutos ligando refinarias;- Instalao de cabos para
distribuio de energia eltrica; - Distribuio de gs no Rio;- etc...
-
10
10
9
126
3
12 4
77
5
6
3
4
15
6
1
14
2
7
7
5
84 11
rvores
Problema: Determinar uma rvore expandida sobre o grafo que represente o menor custo total.
Exemplos:- Dutos ligando refinarias;- Instalao de cabos para
distribuio de energia eltrica; - Distribuio de gs no Rio;- etc...
Curiosidade:n = 16m = 25
-
10
10
9
126
3
12 4
77
5
6
3
4
15
6
1
14
2
7
7
5
84 11
rvores
Problema: Determinar uma rvore expandida sobre o grafo que represente o menor custo total.
Exemplos:- Dutos ligando refinarias;- Instalao de cabos para
distribuio de energia eltrica; - Distribuio de gs no Rio;- etc...
Obs: Soluo qualquer.
-
Fluxo em Redes
Com o algoritmo correto, aps 6 iteraes manuais chegamos na Soluo tima! (Cmn = 300)
Problema: Encontrar um fluxo vivel de mnimo custo para determinada demanda.
Exemplos:- Cadeia Txtil (Li-Fung);- Processo Produtivo;- Transporte Intermodal;- etc...
20 20
c=3
q=15
c=5q=15
c=1q=8
c=6q=6
c=4q=13
c=7q=20
c=2
q=12
c=8q=10
c=4
q=15
20 20
14
6
8
6
2
8
12
10
4
-
1 2 3 4 6 m. . .5
1 2 3 4 n. . .
Cobertura de Conjuntos
m LINHAS
n COLUNAS
Problema:Definir um grupo de colunas que cubra as m linhas com custo mnimo.(obs: custos associados s colunas).
-
Cobertura de Conjuntos
1 2 3 4 6 m. . .5
1 2 3 4 n. . .
Exemplos:- Escolha de fornecedores;- Seleo de transportadoras (areas, terrestres...);- Contratao de motoristas;- etc...
-
Cobertura de ConjuntosExemplos:- Escolha de fornecedores;- Seleo de transportadoras (areas, terrestres...);- Contratao de motoristas;- etc...
Obs: Soluo qualquer.
1 2 3 4 6 m. . .5
1 2 3 4 n. . .
-
Localizao de p - medianas
Problema:Localizar, dentre os ns do grafo, p medianas que minimizem a soma ponderada (pelas demandas dos ns) das distncias entre os ns e suas respectivas medianas.
Exemplo:- Localizao de Centros de Distribuio;- Localizao de escolas;- etc...Obs: Uso Alternativo ? Determinao de reas de influncia.
-
Caminhos Mnimos
Problema: Encontrar um caminho mnimo entre um par de ns (s, t) do grafo.Alternativamente, pode-se querer encontrar o caminho mnimo entre o n s e todos os demais ns do grafo.
Exemplos:- Menor caminho entre duas cidades (distncia e tempo);- Alternativamente: Matriz Origem-Destino (mapas);- Operadores Logsticos;- etc...
-
Espao
Tempo
S.Fco
Rio
Stos
Rott
NY
HK
Hoje Acordo
Caminhos Mnimos
-
Espao
Tempo
S.Fco
Rio
Stos
Rott
NY
HK
Hoje AcordoTransporte
Caminhos Mnimos
-
Espao
Tempo
S.Fco
Rio
Stos
Rott
NY
HK
Hoje AcordoArmazenagem Transporte
Caminhos Mnimos
-
Caminhos Mnimos
Obs: Soluo qualquer.
Espao
Tempo
S.Fco
Rio
Stos
Rott
NY
HK
Hoje AcordoArmazenagem Transporte
-
RoteirizaoProblema do Carteiro Chins
Problema:
Definir um roteiro que passe por todos os arcos de um grafo com custo mnimo.Exemplos:- Coleta de Lixo;- Entrega / Coleta de Correspondncias (Correios);- Limpeza de ruas (caminho com escovas)- etc...
-
RoteirizaoProblema do Caixeiro Viajante
Problema:
Definir um roteiro que passe por todos os ns de um grafo com custo mnimo.
Exemplos:- Entrega de encomendas;- Separao de pedidos em grandes estantes com Transelevador;- Pontos de solda num circuito eltrico;- etc...
-
Roteirizao de Veculos
Problema:Alocar para cada veculo um roteiro onde o somatrio das demandas dos ns atendidos por esse veculo seja compatvel com a capacidade do mesmo.
Solues Alternativas:
- Cluster First Route Second:- por exemplo: p-medianas capacitado + PCV.
- Route First Cluster Second:- TSP + segmentao da rota.
-
Roteirizao de VeculosCluster First Route Second
Problema:Distribuio de material publicitrio em 1.113 postos de combustvel da rede Texaco espalhados por 682 cidades brasileiras em 22 estados diferentes.Todo o material deveria sair de Florianpolis.
Metodologia:- Agrupamentos com o algoritmo de p-medianas at que as demandas de cada grupo estivessem compatveis com as capacidades dos caminhes.
- Algoritmo de Teitz, M. B. & Bart, P (1968)
- Aplicao do algoritmo para a definio dos roteiros de cada grupo- Algoritmo: Guided Local Search Voudouris (1988)
-
Roteirizao de VeculosCluster First Route Second
Soluo Proposta:- 9 equipes de distribuio
- 2 equipes de transferncia
Durao esperada (dias) 49,47
123,6775,78
Mdia por Equipe
Postos Atendidos
Cidades Atendidas
6776,37
616,036160,33
6,18
Total Km rodados
Km rodados (cidades)Km rodados (rodovias)
Carga Movimentada
-
Roteirizao de VeculosCluster First Route Second
Zoom na equipe 9
-
Referncias
CHRISTOFIDES, NICOS (1975) - Graph Theory: An Algorithmic Approach
Notas de aula: Disciplina de Pesquisa Operacional III da UFSC (Prof. Srgio Fernando Mayerle)
-
Dvidas?Perguntas?
Muito Obrigado!!!
Bruno Thom de Abrantes