MBA EM LOGÍSTICA EMPRESARIAL
OPERAÇÕES E SISTEMAS DE
DISTRIBUIÇÃO
AULA III
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização
Planejamento
Operacional
Poucas informações
Muitas informações
Dimensionamento da Frota
(Zonas de Distribuição)
Contornos gerais já definidos
Informações estimadas sobre
localização e demanda dos clientes
Informações precisas sobre
localização e demanda dos clientes
Análise Agregada
Análise de Redes
(Roteirização)
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização
Três fatores Fundamentais
Decisões:
Alocação de um grupo de clientes, que devem ser visitados, a um conjunto de veículos, com
seus respectivos motoristas, envolvendo também a programação e o seqüenciamento das
visitas
Objetivos:
Serviço de alto nível aos clientes, atentando para manter os custos operacionais e de capital
tão baixos quanto possível
Restrições:
deve-se completar as rotas com os recursos disponíveis, mas cumprindo totalmente os
compromissos assumidos com os clientes;
deve-se respeitar os limites de tempo impostos pela jornada de trabalho dos motoristas e
ajudantes;
Deve-se respeitar as restrições de trânsito, no que se refere às velocidades máximas, horários
de carga e descarga, tamanho máximo dos veículos nas vias públicas, etc.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização
Exemplos
- Entrega, em domicílio, de produtos comprados nas lojas de varejo ou
pela Internet;
- Distribuição de produtos dos CDs para as lojas de varejo;
- Distribuição de bebidas em lojas e restaurantes;
- Distribuição de dinheiro para caixas eletrônicos de bancos;
- Distribuição de combustíveis para postos de gasolina;
- Coleta de lixo urbano;
- Entrega domiciliar de correspondência
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
A separação dos diversos clientes pelos roteiros já foi
realizada, ou seja, a questão da restrição de capacidade e de
tempo já está resolvida
Problema que falta ser resolvido:
Encontrar a seqüência de visitas que torne mínimo o percurso
dentro da zona pré-estabelecida.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Casos mais simples (Figura a seguir): Problema pode ser
resolvido por inspeção
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Casos com esquemas de distribuição mais complexos ou com
maior número de clientes: métodos mais sofisticados,
operacionalizados em computador.
Literatura: Roteirização sem restrições é chamada de problema
do caixeiro viajante (PCV).
Grupos de métodos de resolução do PCV:
- métodos de construção dos roteiros;
- métodos de melhoria dos roteiros.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Métodos de Construção do Roteiro
Os métodos de construção partem de um ou dois pontos e vão formando
o roteiro através do acréscimo paulatino de pontos adicionais.
Sistemática mais simples: ir ligando cada ponto ao seu vizinho mais
próximo. (Figura a seguir)
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Métodos de Construção do Roteiro
Um método de construção mais eficiente do que o do vizinho mais
próximo é o método do ponto mais distante.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Métodos de Melhoria do Roteiro
Os métodos de melhoria partem da solução obtida com o auxílio de um
outro método qualquer, procurando aperfeiçoar o resultado obtido pela
utilização de uma sistemática pré-definida.
Métodos de melhoria mais utilizados:
2-opt;
3-opt.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Métodos de Melhoria do Roteiro
Fluxograma do Método 2-opt
Roteiro gerado por algum
método de construção
Remove-se 2 arcos do roteiro e reconectam-se, por tentativas, os nós, que
compõem esses arcos, alterando as ligações
SIM
Substituir o roteiro original pelo
roteiro modificado
Obteve-se um roteiro de
extensão menor que o
anterior?
NÃO
Já foram realizadas todas as
trocas de ligações possíveis?
SIM
Prof. André Luis Ribeiro de Medeiros, M.Sc.
NÃO
Roteiro otimizado
Roteirização Sem Restrições
Métodos de Melhoria do Roteiro
Método 2-opt:
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Métodos de Melhoria do Roteiro
Método 3-opt:
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Sem Restrições
Métodos de Melhoria do Roteiro
Método
3-opt aplicado ao exemplo do resultado do método do vizinho mais próximo:
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Com Restrições
A roteirização com restrições se aplica aos casos em que é preciso
roteirizar os veículos sem que haja uma prévia divisão da região em zonas
de distribuição, ou seja, sem que tenham sido levado em conta as
restrições de capacidade e tempo envolvidas no processo.
Na literatura, são descritos diversos métodos para resolver este
tipo de problema. Neste estudo serão abordados dois métodos
relativamente simples. São eles:
- Método de Varredura;
- Método de Clarke e Wright
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Com Restrições
Método de Varredura
Método fácil de usar e de computação rápida. No
entanto, segundo Ballou, apresenta uma incerteza de 10%
nos resultados.
Solução Razoável num prazo curto
Versus
Solucão ótima num perído de tempo incompatível
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Com Restrições
Método de Varredura
Seqüência de procedimentos:
Primeira Etapa: tomando o depósito como centro, definir um eixo passando por ele. Este
eixo geralmente coincide com a linha horizontal;
Segunda Etapa: vá girando o eixo em torno do CD no sentido anti-horário até que inclua
um cliente;
Terceira Etapa: Testar o cliente em potencial, verificando se o mesmo pode ser incluído no
roteiro em formação, respondendo às seguintes perguntas:
por dia ?
- o tempo de atendimento ao novo cliente estoura a jornada de trabalho permitida
- a quantidade de mercadoria a transportar para o novo cliente estoura o limite de
capacidade do veículo ?
Se ambas as restrições não forem violadas, o novo cliente poderá ser incorporado
ao roteiro e o processo (segunda e terceira etapas) continua.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Com Restrições
Método de Varredura
Quarta Etapa: Se o o novo cliente não puder ser incluído no roteiro em formação,
é sinal que as possibilidades desse roteiro se esgotaram. Nesse caso, fechamos o
roteiro e iniciamos um novo. O processo termina quando todos os clientes tiverem
sido incluídos num roteiro.
Quinta Etapa: Para cada roteiro, aplicar um método de melhoria de forma a
minimizar os percursos.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Varredura
Exemplo de Aplicação
Dados do problema:
Informações a respeito de cada um dos 60 clientes (tabela em anexo):
- coordenadas x e y da localização;
- quantidade q de mercadoria demandada por entrega
Informações operacionais:
- tempo de descarga, em cada cliente, admitido uniforme e igual a 15 minutos;
- coordenadas do CD igual a (0;0);
- capacidade útil do veículo: 4 toneladas;
-Jornada de trabalho: 8 horas por dia;
- a distância entre dois pontos quaisquer foi estimada multiplicando-se a distância
em linha reta por um fator k1=1,40.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Varredura
Exemplo de Aplicação
Resolução:
Neste problema, em particular, o CD está situado ao sul,
relativamente longe da zona de distribuição. A distância média do CD aos
clientes é de 77,6 km, estando o ponto mais próximo a uma distância de
75,2 km e o mais distante a 79,8 km.
Utilizando o método de varredura, os roteiros resultantes ficarão
extremamente alongados na direção do depósito, o que não é desejável.
Para contornar este problema, pode-se adotar o centro de
gravidade como centro do eixo horizontal a ser utilizado.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Varredura
Exemplo de Aplicação
Situação Inicial
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Varredura
Exemplo de Aplicação
Resultado Preliminar
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Varredura
Exemplo de Aplicação
Resultados Obtidos após a aplicação do 3-opt:
-Número de roteiros: 7;
-Quilometragem total diária da frota: 1101,9;
-Custo médio por cliente visitado (R$): 16,58
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Roteirização Com Restrições
Método de Clarke e Wright
Método muito utilizado na resolução de problemas isolados,
aparecendo também embutido dentro de muitos softwares de roteirização
Segundo Ballou, enquanto o método de varredura produz um erro
médio de 10%, o de Clarke e Wright reduz esse nível a 2% do ótimo
absoluto.
Tem como objetivo gerar roteiros que respeitem as restrições de
tempo e capacidade, mas visando, ao mesmo tempo, minimizar a distância
total percorrida pela frota.
À medida que o método vai construindo os roteiros de forma
inteligente, buscando reduzir ao máximo a distância percorrida, o número
de veículos necessários para realizar o serviço tende também a ser
minimizado, reduzindo assim os investimentos e o custo de operação.
Método baseado no conceito de Ganho.
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Seqüência de Procedimentos
Primeira Etapa: combinam-se todos os pontos (que representam os
clientes) dois a dois e calcula-se o ganho para cada relação;
Segunda Etapa: ordenam-se todas as combinações (i,j) de forma
decrescente segundo os valores dos ganhos;
Terceira Etapa: Esta etapa tem início com a utilização da combinação de
dois nós que tenha apresentado o maior ganho. Posteriormente, na análise
de outras situações, vai-se descendo na lista de combinações, sempre
obedecendo à seqüência decrescente de ganhos;
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Seqüência de Procedimentos
Quarta Etapa: Para um par de pontos (i,j), tirado da seqüência de combinações, verificar se
os dois pontos já fazem parte de um roteiro iniciado:
- se i e j não foram incluídos em nenhum dos roteiros já iniciados, criar um novo
roteiro com esses dois pontos;
- se o ponto i já pertencer a um roteiro iniciado, verificar se este ponto é o primeiro
ou o último deste roteiro (sem contar o CD). Se a resposta for positiva, acrescentar o par de
pontos (i,j) na extremidade apropriada. Fazer a mesma análise com o ponto j. se nenhum
dos dois pontos satisfizer essa condição separadamente, passar para o próximo item desta
etapa;
- se ambos os pontos i e j fazem parte, cada um deles, de roteiros iniciados, mas
diferentes, verificar se ambos são extremos dos respectivos roteiros. Se a resposta for
positiva, fundir os dois roteiros em um só, juntando-os de forma a unir i a j. Caso contrário,
passar para a quinta etapa;
etapa;
- se ambos os nós i e j pertencerem a um mesmo roteiro, passar para a quinta
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Seqüência de Procedimentos
Quinta Etapa: Cada vez que se acrescentar um ou mais
pontos num roteiro, ou quando se fundir dois roteiros num só,
verificar se a nova configuração satisfaz as restrições de
tempo e dec capacidade. Se atender aos limites das
restrições, a nova configuração é aceita.
Sexta Etapa: O processo termina quando todos os pontos
(clientes) tiverem sido incluídos em um roteiro
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Evolução da Resolução
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Resultado Preliminar
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright
Exemplo de Aplicação – Resultado melhorado com o 3opt
Resultados Obtidos após a aplicação do 3-opt:
-Número de roteiros: 6;
-Quilometragem total diária da frota: 950,7;
-Custo médio por cliente visitado (R$): 14,24
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Método de Clarke e Wright versus Método de Varredura
(comparação de resultados)
Clarke e
Wright
Varredura
Número de roteiros
6
7
Quilometragem
total diária da frota
(km)
950,7
1101,9
Custo médio por
cliente visitado (R$)
14,24
16,58
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Impactos das restrições de Tempo e de Capacidade
Simulação de Configurações
O problema de atendimento aos 60 clientes discutido até o
presente momento, possui as seguintes características:
- capacidade útil do veículo utilizado: 4 ton;
- jornada de trabalho: 8 horas;
- distância média do CD à zona de distribuição 77,6 km;
- tempo de descarga, em cada cliente, admitido uniforme e igual a 15
minutos.
Além disso, apresentou os seguintes resultados:
- 6 roteiros;
- Os roteiros foram restritos por tempo, devido ao fato de grande parte
do tempo de ciclo ser gasto no deslocamento do depósito à zona de
distribuição e vice-versa;
- Carregamento máximo dos veículos igual a 1,8 ton.
Alguma contribuição para melhorar o cenário?
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Impactos das restrições de Tempo e de Capacidade
Simulação de Configurações
Analisando o mesmo problema com a única diferença de a
distância média do CD aos clientes ser igual a 3,8 km.
Obtém-se os resultados apresentados na tabela a seguir:
Roteiro
Número
Número de
Clientes
Tempo de Ciclo
Diário
Lotação do
veículo (t)
1
21
5 h 42
3,9
2
22
6h
4,0
3
17
4 h 36
3,90
Alguma contribuição para melhorar o cenário?
Prof. André Luis Ribeiro de Medeiros, M.Sc.
Impactos das restrições de Tempo e de Capacidade
Simulação de Configurações
Analisando o mesmo problema com a única diferença de a
distância média do CD aos clientes ser igual a 3,8 km e a capacidade do
veículo ser igual a 8 t.
Obtém-se os resultados apresentados na tabela a seguir:
Roteiro
Número
Número de
Clientes
Tempo de Ciclo
Diário
Lotação do
veículo (t)
1
31
8 h 18
5,9
2
29
7 h 48
5,9
Alguma contribuição para melhorar o cenário?
Prof. André Luis Ribeiro de Medeiros, M.Sc.