Prof. André Luis Ribeiro de Medeiros, M.Sc. MBA EM LOGÍSTICA EMPRESARIAL OPERAÇÕES E SISTEMAS DE DISTRIBUIÇÃO AULA III

Prof. André Luis Ribeiro de Medeiros, M.Sc.

MBA EM LOGÍSTICA EMPRESARIAL

OPERAÇÕES E SISTEMAS DE

DISTRIBUIÇÃO

AULA III


Roteirização

Planejamento OperacionalPoucas 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)


RoteirizaçãoTrê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.


RoteirizaçãoExemplos

- 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


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.



Casos mais simples (Figura a seguir): Problema pode ser resolvido por inspeção



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.


Roteirização Sem RestriçõesMé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)


Roteirização Sem RestriçõesMé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.


Roteirização Sem RestriçõesMé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.


Métodos de Melhoria do RoteiroFluxograma 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

Obteve-se um roteiro de extensão menor que o

anterior?

Já foram realizadas todas as trocas de ligações

possíveis?

Substituir o roteiro original pelo roteiro modificado

Roteiro otimizado

SIM

SIM

NÃO

NÃO



Método 2-opt:



Método 3-opt:



Método 3-opt aplicado ao exemplo do resultado do método do vizinho mais próximo:


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


Roteirização Com RestriçõesMé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



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:

- o tempo de atendimento ao novo cliente estoura a jornada de trabalho permitida por dia ?

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



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.


Método de VarreduraExemplo 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.




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.



Situação Inicial



Resultado Preliminar



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


Roteirização Com RestriçõesMé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.


Método de Clarke e WrightSeqüê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;


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;

- se ambos os nós i e j pertencerem a um mesmo roteiro, passar para a quinta etapa;



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



Método de Clarke e WrightExemplo de Aplicação


Método de Clarke e WrightExemplo de Aplicação – Evolução da

Resolução



Resolução



Resolução



Resolução



Resolução



Resolução



Resolução



Resolução


Método de Clarke e WrightExemplo de Aplicação – Resultado

Preliminar


Método de Clarke e WrightExemplo de Aplicação – Resultado melhorado

com o 3-opt

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


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


Impactos das restrições de Tempo e de CapacidadeSimulaçã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?



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:

RoteiroNú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 6 h 4,0

3 17 4 h 36 3,90




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:

RoteiroNú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


Documents

Prof. André Luis Ribeiro de Medeiros, M.Sc. MBA EM LOGÍSTICA EMPRESARIAL OPERAÇÕES E SISTEMAS DE DISTRIBUIÇÃO AULA III