[MÚSICA]

[MÚSICA] [MÚSICA]

Anteriormente analisàmos o problema da distribuição com base generalizações.

Essas generalizações são fundamentais na fase de planejamento logístico.

Quando analisamos e dimensionamos as questões

relacionadas à escolha do modal e do tipo de rede que será empregada.

Porém, quando o enfoque é operacional, ou seja,

o sistema já foi dimensionado relação aos seus aspectos gerais,

o problema específico a ser resolvido, conhecidas as localizações e as

demandas do cliente, passa a ser o da roteirização dos veículos.

A roteirização pode ser feita com restrições ou sem restrições.

Vamos observar as características, inicialmente,

de uma roteirização sem restrições.

Roteirização sem restrições: neste tipo de roteirização o problema a ser resolvido é

determinar a sequência de visitas que torne o percurso de transporte

o menor possível dentro de uma área de distribuição.

Esse problema é conhecido como o problema do caixeiro viajante.

Imagine que vendedor quer determinar a rota menos despendiosa ou a rota mais

curta, para visitar uma determinada quantidade de clientes diferentes cidades,

passando por cada cidade exatamente uma única vez.

Para exemplificar a complexidade desse problema,

vamos observar os três pontos abaixo, que representam três diferentes cidades.

Tomando como origem o ponto de quantas formas diferentes

o vendedor pode visitar os seus clientes nas cidades dois e

três e retornar ao ponto de origem, isso na cidade?

Inicialmente, podemos adotar como

a primeira cidade a ser visitada, a cidade dois.

Então, a partir da cidade dois a próxima cidade a ser visitada

seria a cidade três e ele retornaria para a cidade inicial.

A outra forma possível seria iniciando o

circuito na cidade visitar o cliente na cidade três,

se dirigir à cidade dois, e retornar à cidade de origem.

Então, temos para três pontos duas possibilidades de rota.

O problema é o aumento de complexidade à medida que incluímos mais cidades

no roteiro de nosso vendedor.

Como podemos observar na tabela, para cinco cidades,

temos 24 opções de rotas que podem ser escolhidas pelo nosso vendedor.

O problema cresce de complexidade à medida que aumentamos o número de

cidades a serem visitadas.

Para cinco cidades existe a possibilidade de 24 rotas.

Para 13 cidades, o número de rotas é próximo de 479 milhões.

Para 20 cidades o número possível de rotas é maior do que 100 quadrilhões.

Esse número é bastante significativo porque vários veículos

realizam diariamente mais do que 20 entregas por roteiro.

Como podemos observar,

encontrar uma solução para esse problema é algo bastante complexo.

Se considerássemos uma estratégia de busca exaustiva da solução desse problema,

teríamos que listar todas as possíveis soluções, para cada

possível solução calcular o custo total com relação a tempo e distância,

e identificar a solução ótima: a de menos custo, tempo, ou distância.

Esta forma de busca de solução é conhecida como Algoritmo de Força Bruta.

Esse é exemplo de método ineficiente para solucionar o problema do

caixeiro viajante.

Uma forma de se buscar uma solução para esse problema de roteirização é o emprego

dos métodos heurísticos.

Casos simples, com poucos clientes a serem visitados no roteiro,

podem ser resolvidos facilmente por inspeção.

Quando o número de clientes aumenta, ou seja,

a complexidade das restrições assumem esquemas mais complexos,

a resolução desse problema exige métodos computacionais.

Os métodos Heurísticos que podemos empregar para resolver esse problema

são agrupados duas categorias: os métodos de construção de roteiro e os métodos de

melhoria de roteiro.

Os métodos de construção de roteiro partem de

ou dois pontos e vão formando o roteiro através do acréscimo de pontos adicionais.

Desses métodos é o vizinho mais próximo.

Sua sistemática é bastante simples.

Ela é baseada na inclusão do vizinho mais próximo.

Inicialmente elege-se ponto e se procura entre os demais

pontos aquele mais próximo desse ponto inicial.

Toma-se então segundo ponto e se repete o procedimento,

tomando cuidado de excluir todos aqueles que já fazem parte do roteiro.

Esse método não é dos mais eficazes mas é rápido e fornece uma solução,

que pode ser adotada como uma configuração inicial.

A outra abordagem é a inserção do ponto mais distante.

Nessa abordagem também se adota a escolha de ponto inicial.

Porém, diferentemente do vizinho mais próximo, procura-se, agora,

o ponto mais distante deste ponto inicial.

Uma vez encontrado, ligam-se esses dois pontos formando o roteiro embrionário.

A seguir, busca-se o ponto mais distante deste roteiro inicialmente formado.

Quando encontrado, inclui-se esse ponto no roteiro.

O processo é repetido até que todos os pontos sejam incluídos no roteiro.

Esse método conduz a uma solução mais eficiente que a do vizinho mais próximo.

Os dois métodos discutidos anteriormente são métodos para a formação de

roteiro inicial.

Porém, esses métodos normalmente não conduzem a roteiro ótimo.

Para aperfeiçoar o resultado desses métodos,

normalmente se empregam diferentes abordagens.

Os métodos mais utilizados para melhoria são conhecidos como 2-opt e o 3-opt.

O objetivo desses métodos é melhorar uma solução inicialmente empregada.

A partir do roteiro inicial formado,

promove-se a alteração da solução e busca-se resultado melhor.

A troca entre as diferentes ligações da rota é feita de forma

sucessiva até que se produza uma melhora nos resultados.

É importante destacar que a resolução da maioria dos problemas de distribuição

física está condicionada às restrições relacionadas ao tempo,

à capacidade do veículo e à janela de tempo.

Nesses casos, muitas vezes é preciso roteirizar os veículos

sem que haja uma prévia divisão das regiões bolsões.

Nessas situação, o processo de roteirização ocorre

simultâneamente com o processo de divisão da área zonas de entrega.

Diversos métodos podem ser empregados para a solução desse complexo problema.

Dois métodos simples são bastante eficazes e podem ser empregados: o

método da varredura e o método das economias.

O método da verredura tem como vantagem sua facilidade de utilização e computação.

Porém, ele é menos preciso que o método de economias.

tomando como base a solução ótima absoluta para problema,

esse método apresenta erro médio de 10%.

O método da varredura pode ser executado cinco etapas.

Primeira etapa, tomando o CD ou a fábrica como centro,

definir eixo passando por ele.

Este eixo coincide com a linha horizontal ou eixo das abscissas.

Segunda etapa, gira-se o eixo torno do centro escolhido,

sentido anti-horário ou horário, até que a linha inclua cliente.

Terceira etapa,

verifica-se a possibilidade de incluir o cliente no roteiro formação.

Para isso, considera-se se o tempo de atendimento do cliente excede a jornada

de trabalho permitida por dia, se a quantidade de mercadoria a transportar

para o cliente excede o limite de capacidade do veículo, ou se

ambas as restrições não forem violadas, o cliente poderá ser incorporado ao roteiro.

E o processo, etapas 2 e 3, se repetem.

Quarta etapa, roteiro.

Se o cliente não puder ser incluído no roteiro formação,

é sinal que as opções deste roteiro se esgotaram.

Nesse caso, fecha-se o roteiro e inicia-se novo.

O processo termina quando todos os clientes tiverem sido incluídos num

roteiro.

Quinta etapa, para cada roteiro formado,

aplica-se método de melhoria de forma a minimizar os percursos.

Métodos das economias.

Esse método tem sido empregado com grande sucesso na resolução de problemas

de roteirização e aparece muitas vezes embutido

softwares de roteirização comerciais.

Seu sucesso se deve à capacidade de incorporar de forma eficiente diversos

tipos de restrição e construir roteiros de forma engenhosa.

Enquanto o método da varredura produz roteiros com erro médio de 10%,

o método das economias possui erro médio de 2%.

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

Esse método se baseia no conceito de ganho.

Por exemplo, partimos da pior situação, que veículo sai, hipoteticamente,

do centro de distribuição somente com a mercadoria destinada a único cliente.

Após fazer a entrega, o veículo retorna ao depósito.

É claro que esta situação vai levar número excessivo de veículos e uma

quilometragem elevada para a frota.

Suponhamos, por exemplo, que o cliente 'j' seja atendido logo seguida do cliente 'i'.

Segundo essa regra conservador, o veículo faria as duas viagens na sequência,

conforme mostrado na figura.

Uma possibilidade de melhoria desse esquema Seria unir os dois

clientes 'i' e 'j' único roteiro.

Nesse caso, conforme é mostrado na figura (b), o veículo faria percurso total menor.

Ao integrar os clientes 'i' e 'j' num único roteiro faremos uma economia de

percurso, ou seja, teremos ganho igual à diferença de percurso L-L'.

Na escolha de dois pontos 'i' e 'j' para formar uma sequência no roteiro,

procura-se selecionar o par com maior ganho.

Há combinações, no entanto, que violam as restrições de tempo ou de capacidade,

portanto, são situações não factíveis.

O método das economias se inicia com a análise de todas as combinações

possíveis entre os nós, dois a dois.

Seguida, são ordenadas as combinações na ordem decrescente dos ganhos.

As combinações com maiores ganhos tendem a ser formadas por pontos distantes do CD,

mais próximos entre si, ou seja, os roteiros vão sendo formados a partir dos

pontos mais distantes do depósito, vindo paulatinamente na direção do CD.

O método das economias consiste das seguintes etapas.

Etapa 1: combinam-se todos os pontos que representam os clientes,

dois a dois, e calcula-se o ganho para cada combinação.

Etapa 2: ordenam-se todas as combinações 'i', 'j',

de forma decrescente segundo os valores dos ganhos.

Etapa 3: começamos a combinação com dois nós que apresentaram maior ganho.

Posteriormente, na análise de outras situações, vai-se descendo na lista

de combinações, sempre obedecendo a sequências decrescentes de ganhos.

Etapa 4: para par de pontos (i, j), tirado da sequência de combinações,

verifica-se se os dois pontos já fazem parte de roteiro iniciado.

Se 'i' e 'j' não foram incluídos nenhum dos roteiros já iniciados, cria-se,

então, novo roteiro para esses dois pontos.

Se o ponto 'i' já pertence a roteiro iniciado, verifica-se se esse

ponto é o primeiro ou o último desse roteiro, não contando o CD.

Se a resposta for afirmativa, acrescenta-se o par de pontos (i,

j) na extremidade apropriada.

Faz-se a mesma análise com o ponto 'j'.

Se nenhum dos dois pontos satisfizer essa condição separadamente,

verifica-se se ambos são extremos do respectivo roteiro.

Caso a resposta seja afirmativa, funde-se os dois roteiros só,

juntando-os de forma a unir 'i' a 'j'.

Caso contrário, se ambos os nós 'i' e 'j' pertencerem a mesmo roteiro, verifica-se

se a nova configuração satisfaz as restrições de tempo e capacidade.

Se atender aos limites das restrições, essa nova configuração é aceita.

O processo termina quando todos os pontos tiverem sido incluídos nos roteiros.

Para realizar uma boa roteirização e programação de veículos oito princípios

devem ser observados.

Carregar os caminhões com volumes destinados às paradas que estejam mais

próximas entre si.

Paradas dias diferentes devem ser combinadas para produzir agrupamentos mais

concentrados.

Começar os roteiros a partir da parada mais distante do depósito.

O sequenciamento das paradas num roteiro devem ter a forma de lágrima.

Os roteiros mais eficientes são aqueles que fazem uso dos maiores veículos

disponíveis.

A coleta, se possível, deve ser combinada nas rotas de entrega

vez de reservada para o final desses roteiros.

Uma parada removível de agrupamento de rota é uma boa

candidata a meio alternativo de entrega.

As pequena janelas de tempo de paradas devem ser evitadas.

Para implementar método de roteirização e programação de veículos, podemos

adotar uma técnica de três estágios baseada previsão, solução e revisão.

Primeiro lugar, o analista prevê o eventual problema para as exceções,

entregas que exijam manuseio especial ou, entregas e coletas que são óbvias,

a movimentação de caminhões com carga completa.

A seguir, com o auxílio de sistema computacional,

o problema reduzido é resolvido e tem sua solução colocada à disposição do analista.

Por fim, o analista revisa a solução matemática e nela introduz todas as

modificações indispensáveis para que se torne prática.

Esse processo é cíclico e deve se repetir os estágios a cada ciclo.

As informações da equipe de campo devem ser consideradas, para melhorar o

processo de parametrização do sistema e deixá-lo mais próximo ao problema real.

Nesse vídeo,

falamos a respeito do processo de roteirização e programação de veículos.

Vimos duas abordagens de roteirização: com restrição e sem restrição.

Também pudemos perceber que, à medida que o número de pontos a serem visitados

aumenta, cresce a complexidade do problema, e abordagens diferentes

devem ser empregadas na busca da solução.

[MÚSICA]

Roteirização

Conceitos Básicos de Logística e Supply Chain

Meet the Instructors