ROTEIRIZAÇÃO

Prévia do material em texto

*
ROTEIRIZAÇÃO
Prof. André Luis Ribeiro de Medeiros, M.Sc.
*
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 
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
Prof. André Luis Ribeiro de Medeiros, M.Sc.
*
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:
	- 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.
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
Exemplode 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.
*
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; 
	 
Método de Clarke e Wright
Seqüência de Procedimentos
Prof. André Luis Ribeiro de Medeiros, M.Sc.
*
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 Wright
Seqüência de Procedimentos
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 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
Prof. André Luis Ribeiro de Medeiros, M.Sc.
*
Método de Clarke e Wright versus Método de Varredura (comparação de resultados)
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:
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:
Alguma contribuição para melhorar o cenário? 
Prof. André Luis Ribeiro de Medeiros, M.Sc.