Teoria dos Grafos Logistica.pdf

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




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




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...


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


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)


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


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

Documents

Teoria dos Grafos Logistica.pdf