1 Sistemas de definição de rotas Logística 5º ano LEEC 2ºSemestre - 2002/2003 Sistemas de definição de rotas (para distribuição) Jorge Bertocchini - 960503078

1Sistemas de definição de rotas

Logística5º ano LEEC 2ºSemestre - 2002/2003

Sistemas de definição de rotas Sistemas de definição de rotas (para distribuição)(para distribuição)

Jorge BertocchiniJorge Bertocchini - - 960503078960503078Ricardo Ferreira – 960503168Ricardo Ferreira – 960503168

Pedro Sousa - 960503183Pedro Sousa - 960503183

16 de Maio de 200316 de Maio de 2003


Geo-Logistica

Definição dada à logistica de distribuição

Planeamento do sistema de transporte• Localização, dimensão e configuração das infra-

estruturas de transporte– Inclui dimensão da frota e sua capacidade de

distribuição.

Planeamento de rotas dos veículos• Organização dos motoristas, veículos, atrelados,

etc.• Rotas dos veículos na distribuição.


Geo-Logistica

Ferramentas necessárias à implementação da geo-logistica

• Mapas– Usadas para gestão frotas e gestão de rotas

• Sistemas GPS– Para localização dos veículos da frota

• Inteligencia artificial– Para definição de rotas e gestão de frotas– Composta por algoritmos de optimização– Definição do melhor caminho entre dois pontos


Geo-Logistica

Estrutura básica de um sistema de posicionamento e locomoção


Definição de Rotas: Algoritmos

Um dos aspectos mais amplamente estudados em investigação operacional

Mais de 35 diferentes formas de estabelecer rotas

• Maior parte pouco práticas e envolvem conhecimentos avançados de métodos quantitativos– Inviabilizam o uso em redes de grandes dimensões.

• Duas excepções:– Heurística de CLARKE e WRIGHT (SIMPLES e mais

usual);– Método do Caixeiro Viajante (Não tão SIMPLES);



Método do Caixeiro Viajante– Ciclo de menor distância possível, com inicio e fim

numa dada cidade passando em todas as cidades uma única vez

Eficiência e rapidez:• Num computador com 10000 ciclos por

segundo é necessário:– 18 seg. para calcular um esquema com 10 vértices– 50 dias para 15 vértices– 2 anos para 16 vértices– 193000 anos para 20 vértices

• Muito complexo e lento



Heurística de CLARKE e WRIGHT Objectivos:

• Minimizar o caminho percorrido– É possivel ponderar as distâncias pelos tempos

necessários para as percorrer, ou mesmo pelo custo das portagens, entre outro

Método:• Heurística de poupança

– analiza-se rotas diferentes no intuito de melhorar a performance global


Heurística de Clarke e Wright

Cálculo das Poupanças: Podem ocorrer duas situações:

i j

O

i j

O

O veículo abastece i a partir de O, volta à origem, abastece j e volta novamente à origem:

O veículo abastece i a partir de O, de i segue para j, abastecendo j e por fim retona à origem:

Pij(Poupança entre i e j) = (2 DOi + 2 DOj) – (DOi + DIj + DjO) = DOi + DOj - Dij


Heurística de Clarke e Wright

Exemplo• 1 Armazém central(O)• 5 Clientes (A,B,C,D e E)• Máxima distância percorrida num dia

– Dmax= 30 km

O

A

B

C

DE

10

1810

12

10

712

12

5

5

812

10

10

10Representação gráfica das distâncias


Heurística de Clarke e WrightExemplo

– Matriz de distâncias:

O A B C D E

O - 10 5 5 10 10

A - 10 12 18 10

B - 7 12 12

C - 8 12

D - 10

E -

- Calcular a Poupança entre A e B

OABO = 10 + 10 + 5 = 25 km

OAOBO = 10 + 10 + 5 + 5 = 30 km

Poupança conseguida: 5 km (30 km – 25 km)


Heurística de Clarke e WrightExemplo

• Passo 1: Calcular a matriz das poupanças- Matriz das Poupanças (para todos os pares de clientes):O A B C D E

O - 5 3 2 10

A - 3 3 3

B - 7 3

C - 10

D -

E

• Passo 2 : Ligação entre os clientes até alcançar o limite de 30 km(por ordem decrescente de poupanças)

OAEO = 101 + 101 + 101 = 30 km (no limite)

(1) Todos os valores são retirados na matriz das distâncias, a matriz das poupanças serve apenas como guia


Heurística de Clarke e WrightExemplo 1

• Passo 3: A primeira viagem a fixar será OAEO• Passo 4: Fixar a “nova” matriz sem as colunas e

as linhas de A e EO A B C D E

A

B - 3C 3B

C - 7A

D -

E

ODCO = 10 + 8 + 5 = 23 km < 30 km

ODCBO = 10 + 8 + 5 + 7 = 30 km (no limite)

• Passo 5: Reiniciar processo agora para a “nova” matriz

• Passo 6: A segunda viagem a fixar é a ODCBO


SOFTWARE


Software de Geo-Logistica

ArcLogistics Route (ESRI-Portugal. Sistemas e Informação Geográfica)

http://www.esri-portugal.com/

• Permite a definição optimizada de percursos de entregas por veículos• Define qual a melhor sequência de paragem tendo em conta as janelas

temporais dos clientes• Permite reduzir de 10 a 40% os custos associados ao processo de entrega

Principais características– Definição de velocidade de veículos– Define percursos de entrega baseados nos tempos reais– Cosidera as características dos veículos e condutores– Importa informação de qualquer base de dados compativel com ODBC– Exporta rotas para base de dados do utilizador– Gera relatórios e mapas detalhados– Inclui cargas e descargas no percurso– ...



AXIODIS (Sys Team, System Teamworks S.R.L.- ARGENTINA)

http://www.axiodis.com.ar/

Ferramenta de planificação e optimização de transportes Permite:

– Optimizar as rotas de transportes diminuindo o custo logistico– Garantir prazos, carregamentos e entregas,etc.

Principais caracteristicas:– Gerenciamento de Centros de distribuição– Pedidos sobre encomenda– Planificação de rotas de distribuição– Modelos de necessidade de transporte– Simulação de situações logisticas– Dimensionamento de frotas


Software de Geo-Logistica: AXIODIS (cont.) Definição das Rotas

• Permite produzir rotas optimizadas:– Em custos– Quilometragem– Horas de trabalho– Quantidade de veículos utilizados

• Permite bloqueamento de rotas– Rotas indesejadas, estradas cortadas,etc.

• Permite atribuição de operações prévias a alguns dos veículos– Nomeadamente cargas e descargas

• Flexibilidade nas restrições impostas• Velocidade do trânsito

– Dependendo da zona e da hora do dia


Software de Geo-Logistica: AXIODIS (cont.)

Especialmente usado na industria de lacticinios– Mais de 40 licenças vendidas– O mais utilizado no mundo

• Usado na Planificação e Optimização de Colecta de Leite

Caracteristicas principais:– Horários de colecta dos produtores– Limites de carga, capacidade das fábricas, equipamentos

necessários, incompatibilidade de produtos– Normas sanitárias e de trânsito– Capacidade de volume nas cisternas

Outras características:– Gestão de frotas– Gere “Sitios logisticos”



ARROW – “Courier Route Optimization”(Nutech Solutions,Inc)

http://www.nutechsolutions.com/

Aposta na variedade de algoritmos para escolha de uma rota

– Reduz o tempo de gestão– Refine a análise de cenários hipotéticos

Caracteristicas:– Integra e converte informação da base de dados do utilizador– Representa gráficamente as rotas em mapas– Reporta direcções de trânsito para condutores– De fácil utilização



Gestão de Rotas V2.0 (Evolutivo, Análise e Concepção de Sistemas Informáticos)

http://www.evolutivo.online.pt/

Permite controlo horário e tratamento estatístico do percurso efectuado nas várias rotas

• Uso de equipamentos Videx– Memory button instalado num ponto de passagem

• Cruza a informação com a base de dados Objectivos:

• Alerta desvios face aos horários previstos, entre outros. Análise:

• Bom complemento para um software de definição de rotas


Recursos

“Logistica” – Professor J.M.Crespo de Carvalho(ISTE)

“Decisões de logistica” - Filipe Rodrigues (gestor de Clientes) http://www.gismedia.pt/newsletter/newsletter.cfm?edinum=3&p=4

“Planejamento Logístico de Rotas Para Sistema de Navegação Apoiado por GPS” J. K. Hasegawa, M. Galo, J. F. G. Monico, N. N. Imai.

(Universidade Estadual Paulista / Departamento de Cartografia) www2.prudente.unesp.br/dcartog/ galo/pdf/2000_gps_cobrac.PDF

“Grafos – Problema do Caixeiro Viajante” , [email protected] ww.geocities.com/ms_io/grafos_cap5.pdf

–

Documents

1 Sistemas de definição de rotas Logística 5º ano LEEC 2ºSemestre - 2002/2003 Sistemas de definição de rotas (para distribuição) Jorge Bertocchini - 960503078