Tecnicas de Roteirizacao - Metodos e Estrategias para Otimizacao de Rotas

Sistemas de transporte Prof Josiane Técnicas de roteirização Técnicas de roteirização O grande objetivo das técnicas de roteirização é definir o melhor percurso a fim de encurtar distâncias e reduzir o tempo necessário para a realização de entregas Tratase de uma atividade essencial para melhorar a qualidade do serviço e reduzir o custo do transporte que pode chegar a dois terços do total dos custos logísticos 2 3 Roteirização é a elaboração sistemática de um percurso que pode envolver um ou mais destinos O grande objetivo dessa atividade é estabelecer o melhor caminho possível definindo a sequência das paradas de acordo com as necessidades da operação Dessa forma é possível otimizar o tempo de entrega encurtar distâncias e reduzir custos Técnicas de roteirização Tudo depende de fatores como tipo e peso da carga quantidade e tipo de veículos utilizados na operação condições das estradas presença de pedágios ao longo do percurso condições do trânsito distância total do percurso e entre cada uma das paradas 4 Técnicas de roteirização 5 Tratase de um método que busca encontrar a melhor sequência em uma série de paradas Seu objetivo é minimizar a distância percorrida sem precisar passar mais de uma vez por um mesmo ponto Para pôr em prática você precisa marcar em um mapa cada uma das paradas do roteiro Em seguida defina o ponto de partida e considere o destino mais próximo como a parada seguinte Faça o mesmo com demais locais de entrega até passar por todos os pontos e retornar para a origem Problema do caixeiro viajante ou método do vizinho mais próximo Exemplo1 Exemplificando o caso n 4 se tivermos quatro cidades A B C e D uma rota que o caixeiro deve considerar poderia ser saia de A e daí vá para B dessa vá para C e daí vá para D e então volte a A Quais são as outras possibilidades É muito fácil ver que existem seis rotas possíveis ABCDA ABDCA ACBDA ACDBA ADBCA ADCBA 6 Exemplo 2 Determinar a rota usando o método do viajante mais próximo 7 8 No caso da estratégia de varredura o objetivo é entregar o maior número de encomendas no menor tempo possível respeitando alguma restrição geográfica temporal ou de qualquer ordem semelhante Por exemplo entregas que devem ser feitas na parte da manhã em um determinado bairro da cidade Ou itens considerados frágeis que precisam de vias adequadas para não aumentar os riscos Método de varredura tı Essa técnica de roteirização é dividida em duas fases agrupar e roteirizar Após demarcar todas as paradas e centros de distribuição em um mapa você deve 1 agrupar os pontos de acordo com sua proximidade É importante que cada agrupamento não ultrapasse a capacidade de carregamento dos veículos que serão utilizados no transporte 2 dentro de cada grupo estabeleça o roteiro a ser seguido com base na proximidade entre os pontos de parada Método de varredura 10 O método de Varredura para Novaes 2007 é de fácil utilização e pode ser realizado por meio computacional possuindo as seguintes fases a Fase 1 Utilizar o armazém como o ponto central e estabelecer um eixo horizontal devendo este ser perpendicular àquele ponto b Fase 2 Girar o eixo em sentido horário ou antihorário até a localização de um cliente c Fase 3 Experimentar os clientes potenciais analisando se o mesmo pode ser incluso no plano de rotas d Fase 4 Na impossibilidade de inclusão iniciase um novo roteiro com o encerramento do anterior Método de varredura Exemplo 3 clientes Região atendida α ângulo variável eixo CD clientes roteiro 3 roteiro 2 roteiro 1 Região atendida CD Fonte Novaes 2004 Método das economias 12 O método Clarke e Wright é um dos mais utilizados em softwares Baseiase no conceito de ganho Essa técnica de roteirização visa a redução da distância total percorrida bem como o uso do menor número de veículos possível para a operação A ideia desse método é partir da pior situação possível imaginando um veículo indo até uma única parada e retornando para o depósito a fim de descobrir a distância máxima a ser percorrida Em seguida combinase duas paradas eliminando um veículo e reduzindo a distância 13 Posteriormente calculase todas as combinações de paradas duas a duas a fim de determinar qual é a mais econômica Para isso utilizase a seguinte fórmula SAB Ganho ou economia d0A distância do CD ao ponto A d0B distância do CD ao ponto B dAB distância entre os pontos A e B Após ter calculado todas as possibilidades monte uma lista com os resultados dos ganhos em ordem decrescente e comece a combinar os nós que apresentaram maior ganho Método das economias 14 O algoritmo de Clarke Wright pode ser dividido em 5 passos segundo Laporte 1992 e Gama 2011 Passo 1 Fazer a combinação dois a dois de todos os pontos Passo 2 Calcular os ganhos de todos os pares de pontos Passo 3 Ordenar os ganhos em ordem decrescente Passo 4 Iniciar a análise dos pontos pelo par de maior ganho passando para o segundo par de maior ganho e assim sucessivamente Passo 5 Considerar duas rotas com os arcos e caso o ganho seja maior que zero introduzir o arco e deletar os outros arcos iniciais Continuar repetindo o passo 5 até que mais nenhuma melhoria seja possível Método das economias Exemplo 4 Considere um armazém situado em 0 que tem de abastecer 5 locais localizações de 1 a 5 Atendendo às distâncias e às quantidades a transportar para cada local expressas nas matrizes dadas determine as rotas mais eficientes sabendo que a capacidade máxima de transporte do veículo é de 100 unidades 15 Exsmplo 0 1 2 3 4 5 0 1 2 3 4 5 Matriz das economias 16 Definição das rotas Pontos Economias Rotas Capacidade 23 54 13 52 12 39 14 31 24 30 15 29 17 Exercício Considere um armazém situado em 0 e que tem de abastecer 6 locais localizações de 1 a 6 Atendendo às distâncias e às quantidades a transportar para cada local expressas nas matrizes dadas determine as rotas mais eficientes sabendo que a capacidade máxima de transporte do veículo é de 100 unidades e por motivos de limitação de trabalho cada rota não deve ter mais de 100 km R 025640 18 OBRIGADA