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
Top Related