Aula 4 - Roteirização e Programação de Transportes

Prévia do material em texto

ROTEIRIZAÇÃO E 
PROGRAMAÇÃO DE 
TRANSPORTES 
AULA 4 
 
 
 
 
 
 
 
 
 
Profª Liziane Hobmeir 
 
 
2 
MÉTODOS DE ROTEIRIZAÇÃO E PROGRAMAÇÃO DE VEÍCULOS 
CONVERSA INICIAL 
O transporte é uma das informações mais aparentes nas operações 
logísticas, tendo como principal objetivo movimentar produtos de um local de 
origem até um determinado destino. A roteirização é uma atividade que busca 
os melhores trajetos que um veículo deve fazer, por meio de uma malha, que 
busca minimizar o tempo e/ou a distância. Dessa forma, reduz custos para o 
processo, sendo uma decisão frequente na logística empresarial. 
Essa decisão não se reflete somente no transporte e no custo, mas como 
um efeito cascata. Tem influência no tempo em que produto está em trânsito, no 
número de entregas/coletas que o mesmo veículo pode realizar, entre outros 
fatores. Como exemplos, podemos citar produtos perecíveis, que devem ficar o 
menor tempo possível em transporte. 
CONTEXTUALIZANDO 
Junto com o crescimento populacional, ocorre um aumento de demanda 
de entrega e/ou coleta de produtos. Muitas entregas devem ser feitas em centros 
urbanos, nos quais órgãos governamentais impõem restrições em relação ao 
tamanho e ao horário de circulação de alguns tipos de veículos. 
A qualidade e o prazo de entrega/coleta acarretam numa competitividade 
crescente e sadia entre os prestadores de serviço, uma vez que os clientes têm 
se tornado cada vez mais exigentes. 
TEMA 1 – OS PRINCIPAIS MÉTODOS DE ROTEIRIZAÇÃO DE VEÍCULOS 
Roteirizar veículos não é um elemento logístico novo, mas um elemento 
que vem crescendo nos últimos tempos, devido ao aumento da demanda. 
Christofides (1985) entende que o problema é o fato de os veículos localizados 
em um depósito central serem requisitados para visitar, durante um dado período 
de tempo, clientes geograficamente dispersos, para cumprir suas exigências. 
Esse problema aparece em um grande número de situações práticas, relativas 
à distribuição de mercadorias, sendo conhecido como “problema da roteirização 
de veículos” (PRV). 
 
 
3 
Problemas de roteirização ocorrem com bastante frequência na 
distribuição de produtos e serviços. Novaes (2000) lista alguns exemplos 
comuns: 
 Entrega, em domicílio, de produtos comprados em lojas de varejo ou pela 
internet; 
 Distribuição de produtos dos centros de distribuição para as lojas de 
varejo; 
 Distribuição de bebidas em bares 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. 
Desde meados do século XX, abordagens matemáticas para os 
problemas persistentes da roteirização vêm sendo desenvolvidas. Uma 
abordagem primordial buscava um roteiro que abrangesse o maior número de 
pontos com a menor distância possível, sem repetir nenhum dos pontos 
anteriormente visitados, questão posteriormente intitulada como “problema do 
caixeiro-viajante”. Branco e Gigioli (2014) afirmam que problemas de roteirização 
começaram a ser abordados na literatura com base nessa teoria. Essa 
abordagem não permitia a repetição dos nós rotulados já visitados (Figura 1). 
Figura 1 – Caixeiro-viajante 
 
Fonte: Wikipédia, 2009. 
 
 
4 
Outra forma é o MilkRun, método que consiste em coletas programadas. 
Um veículo transporta peças ou componentes, coletando-as em alguns 
fornecedores com horários programados (Figura 2). 
Figura 2 – MilkRun 
 
Fonte: Notbad/Shutterstock. 
Dessa forma, é possível incorporar as restrições de capacidade do 
veículo, janelas de entrega e de coleta no problema. Assim, mantém-se uma rota 
regular para coleta de cargas distintas em diferentes fornecedores e aumenta-
se a frequência de entregas, sem a necessidade de aumentar os lotes fornecidos 
por cada fornecedor. 
A roteirização e a programação de veículos são somente uma extensão 
da roteirização do veículo. Nesse caso, a cada acréscimo de restrição imposto, 
o problema fica mais perto da realidade. Obviamente, as restrições dificultam a 
obtenção de uma solução ótima, mas, com algum procedimento lógico ou uma 
boa programação e roteirização, é possível chegar a resultados satisfatórios 
(Silva, 2003). 
Sistemas de roteirização e programação de veículos, ou simplesmente 
“roteirizadores”, são algoritmos computacionais que auxiliam na solução de 
problemas de roteirização e programação de veículos. Com eles, é possível 
obter o tão desejado resultado satisfatório, se comparados a meios manuais, 
além da redução de esforço e tempo. Tavares (1998) explica que um algoritmo 
 
 
5 
não é necessariamente um programa de computador, e sim um apanhado de 
passos necessários para realizar uma tarefa. 
Uma situação de roteirização pode ser definida por três fatores 
fundamentais: decisões, objetivos e restrições. As decisões tomadas se referem 
à alocação de veículos e de seus respectivos motoristas, abrangendo a 
programação e a sequência a ser seguida, chamada “sequência de paradas”. O 
sequenciamento busca encontrar uma rota que passe por pontos relacionados a 
cada rota, ou seja, é preciso encontrar a melhor sequência de passagem por 
uma série de pontos, respeitando todas as restrições. Geralmente, essa 
sequência é representada em forma de gráficos ou tabelas. 
Os objetivos tentam propiciar um serviço de qualidade aos clientes 
mantendo o custo operacional e de capital o mais baixo possível. E não podemos 
nos esquecer de obedecer a certas restrições. Alguns tipos de restrição: 
concentração dos pontos de entrega; horários para entrega (janelas de tempo); 
aspectos espaciais e geográficos; capacidade do veículo; jornada de trabalho 
dos motoristas; restrições de trânsito (como permissões de ingresso de veículos 
pesados em centros urbanos); velocidades máximas permitidas; tipos de carga; 
duração máxima de roteiros; entre outros. 
Um exemplo de definição de rotas pode ser visto na Figura 3, sendo 
possível visualizar um gráfico que mostra a roteirização e sequência de cinco 
rotas distintas, intituladas A, B, C, D e E. Além de mostrar a imagem a ser 
seguida, também temos a sequência de paradas de cada veículo. 
Figura 3 – Exemplo de rota 
 
Fonte: Garcia, 2018. 
 
 
6 
Além de incentivar a concorrência direta, o transporte barato e de alta 
qualidade incentiva indiretamente a concorrência, ao disponibilizar produtos num 
mercado que normalmente não teria condições de arcar com os custos de 
transporte. Isso aumenta a venda de outros produtos, com a entrada em 
mercados normalmente inacessíveis. Os bens de fora da região têm efeito 
estabilizador sobre os preços de todos os artigos semelhantes disponíveis no 
mercado (Ballou, 2006). 
TEMA 2 – DECISÃO DE ROTAS: TEMPO E DISTÂNCIA 
Após a compreensão e a listagem dos fatores fundamentais do problema 
de roteirização apresentado, é preciso definir qual rota será executada. Reduzir 
a distância e o tempo de entrega permite reduzir a jornada de trabalho e custos 
com horas extras e diárias da mão de obra. 
Com a alta competitividade do mercado atual, as marcas deixaram de ser 
prioridade entre os clientes, uma vez que há uma grande variedade de marcas 
com grande similaridade entre os produtos da mesma linha. Nesse cenário, a 
prioridade do cliente passa a ser a qualidade do serviço e o custo, forçando as 
empresas a aderir a meios mais eficazes de solução de problemas, satisfazer o 
cliente e, consequentemente, obter sua fidelidade (Branco; Gigioli, 2014). 
Na maior parte das empresas, o transporte é o principal custo logístico, 
absorvendo cerca de dois terços desse total. Então, para a empresa, um bom 
sistema de transportes é fundamental para expandir mercados (Ballou, 1993). 
Dessa forma, é essencial que a empresa tenha uma boa decisão de rota. 
Ballou (2001) afirma que utilizar o racional humano na determinação de roteiros 
agrega resultados positivos,como evitar que rotas se cruzem ou que o formato 
da rota seja abaulado, convergindo para um formato de gota, quando possível. 
 
 
7 
Figura 4 – Exemplo de paradas boas e ruins 
 
Fonte: Ballou, 2001. 
Conforme Branco e Gigioli (2014), a pesquisa operacional, capaz de 
abordar problemas muito complexos, está sendo utilizada amplamente para 
solucionar problemas de roteirização de veículos. Muitos deles têm 
complexidade exponencial, ou seja, o esforço computacional a ser realizado 
cresce exponencialmente com o tamanho do problema, tanto é que ainda 
existem questões sem soluções ótimas, devido ao seu grau de complexidade. 
Por causa do avanço da tecnologia de informações, das necessidades de 
otimizar a cadeia logística e das exigências cada vez maiores por parte dos 
consumidores, os estudos sobre roteirização são sempre importantes. 
Sabe-se que a variedade dos serviços de transporte é ilimitada. Hoje 
existem cinco modais que podem ser usados em combinação: ferroviário, 
rodoviário, hidroviário, dutoviário e aeroviário. Cada um deles tem suas 
variações e deve ser definido de acordo com as necessidades de cada cliente, 
as quais precisam ser analisadas. 
Alguns elementos importantes para análise são: 
 Tarifa dos fretes; 
 Confiabilidade; 
 Tempo em trânsito; 
 Perdas, danos, processamento das respectivas reclamações e 
rastreabilidade; 
 Considerações de mercado do embarcador; 
 Considerações relativas aos transportadores. 
 
 
8 
No Brasil, o transporte rodoviário é o principal meio para deslocar cargas, 
sendo responsável por quase 63% das toneladas por quilômetro útil 
movimentado pelo país, como apresenta o Gráfico 1. O grande volume 
movimentado e o fato de ser um dos modais com preço unitário mais elevado, 
perdendo apenas para o aéreo, fazem com que o transporte rodoviário de cargas 
tenha ampla representatividade nos custos logísticos pelo país. Em 2008 os 
gastos com a movimentação de carga pelas rodovias brasileiras foram de 
R$ 164,5 bilhões, ou 5,7% do produto interno bruto (PIB) brasileiro (Hijjar; Lobo, 
2011). 
Gráfico 1 – Matriz de transportes do Brasil 
 
Fonte: Hijjar; Lobo, 2011. 
Ainda segundo Hijjar e Lobo (2011), mesmo sabendo da má conservação 
das rodovias no país e que isso seja alvo de reclamações de 90% dos executivos 
de logística, uma vantagem do transporte rodoviário é que ele chega a 
praticamente todos os pontos do país, ao contrário do ferroviário e hidroviário. 
Também é capaz de responder de forma muito mais rápida à demanda das 
empresas, pois evita certas formalidades necessárias em outros modais. 
Nos temas a seguir será possível entender alguns métodos utilizados para 
definir a roteirização. 
TEMA 3 – MÉTODO DA VARREDURA 
O método da varredura é considerado simples por não exigir grande 
esforço computacional durante sua aplicação. Sendo assim, pode ser calculado 
à mão rapidamente para roteiros não muito grandes. Porém, é um meio menos 
preciso. Ballou (2006) afirma que o índice médio de erro para esse método é de 
 
 
9 
cerca de 10%. Se optarmos, em vez de uma ótima, por uma boa solução, 
considerando o curto espaço de tempo que o método exige, esse erro pode ser 
aceitável. 
A maneira como são formados os roteiros é considerada uma 
desvantagem do método. O primeiro passo é a definição das paradas de cada 
veículo e, posteriormente, a definição da sequência de paradas (você verá mais 
detalhes posteriormente, na Figura 8). Dessa forma, alguns fatores fundamentais 
não são considerados, como as questões de tempo total da viagem, janelas de 
tempo, entre outros (Branco; Gigioli, 2014). 
TEMA 4 – MÉTODO DAS ECONOMIAS 
O método das economias, também conhecido como “método de Clarke e 
Wright”, é utilizado em larga escala por possuir uma grande flexibilidade na 
resolução de problemas com diversas restrições, tendo um método consistente 
de construção de roteiros. O método, assim como os outros, respeita 
principalmente o tempo e a capacidade. 
Esse método é um dos mais importantes da categoria, pois produz uma 
saída muito próxima da realidade, ou seja, seu erro em relação à solução ótima 
é muito baixo (Silva, 2003). Enquanto o método da varredura produz um erro 
médio de 10%, este apresenta somente 2% (Novaes, 2003). 
Seu objetivo é gerar roteiros com distâncias mínimas para realizar as 
entregas, pois baseia-se no conceito de ganho, em que a pior situação é quando 
o veículo sai do centro de distribuição (CD) e atende apenas um cliente (você 
verá mais detalhes posteriormente, na Figura 5). O método assume que um 
único veículo serve um único cliente, ou seja, conforme os clientes são 
cadastrados, os caminhões são solicitados. Resumindo, para um conjunto de 
n clientes, o método assume que n veículos serão necessários (Toigo; Valle 
Filho; Lavratti, 2007). Para atender todos os clientes, obviamente seria 
necessária uma quantidade muito grande de veículos e de pessoal. 
A lógica do método está em começar com um veículo fictício que sirva 
cada parada e volte ao depósito (Branco; Gigioli, 2014). Isso mostra a distância 
máxima a ser abordada no problema apresentado pela roteirização. O próximo 
passo é combinar duas paradas no mesmo roteiro (Figura 6), possibilitando a 
eliminação de um dos veículos e reduzindo a distância percorrida. Para 
 
 
10 
determinar quais são as paradas necessárias em um roteiro, a distância 
economizada é calculada antes e depois da combinação (Ballou, 2006). 
Figura 5 – Rota antes da aplicação do método das economias 
 
Fonte: Branco; Gigioli, 2014. 
Figura 6 – Aplicação do método das economias 
 
Fonte: Branco; Gigioli, 2014. 
TEMA 5 – APLICAÇÃO DE MÉTODOS E GANHOS DE PRODUTIVIDADE 
5.1 Método da varredura 
O método da varredura, aplicado segundo os princípios de Ballou (2006), 
segue a seguinte sequência de procedimentos (Figuras 7 e 8): 
1. Adota-se o terminal de carga como centro, traçando um eixo passando 
por ele; 
2. Gira-se o eixo em torno do terminal de carga no sentido anti-horário, até 
que a linha inclua um centro de distribuição; 
3. Testa-se o centro de distribuição em potencial, verificando se poderia ser 
incluído no roteiro em formação. Para isso, deve-se verificar questões 
 
 
11 
essenciais, como: a) A parada incluída no roteiro poderá ultrapassar a 
capacidade do veículo? Se a resposta for negativa, continua-se com a 
rotação da linha até a intersecção da próxima parada; b) O volume 
cumulativo ultrapassará a capacidade do veículo? Se verificarmos que 
ambas as restrições não foram violadas, o novo cliente poderá ser 
incorporado ao roteiro respeitando o tempo de chegada, e o processo 
continua (Etapas 2 e 3); 
4. Se o novo centro de distribuição não pode ser incluído no roteiro em 
formação, é sinal de que suas possibilidades se esgotaram. Nesse caso, 
fecha-se o roteiro e inicia-se um novo. O processo termina quando todos 
os clientes forem incluídos no roteiro (Figura 7b); 
5. Para cada roteiro, aplica-se um método de melhoria, de forma a minimizar 
os percursos. 
Figura 7 – Método da varredura 
Fonte: Novaes, 2007. 
 
 
12 
Figura 8 – Aplicação do método das varreduras 
 
Fonte: Branco; Gigioli, 2014. 
5.2 Método das economias 
Segundo Novaes (2003), o ganho cresce proporcionalmente com o 
afastamento dos pontos i e j do CD, e também quando os pontos i e j estão mais 
próximos. O método se inicia com a análise de todas as combinações possíveis 
entre os pontos, dois a dois. 
O método então calcula a economia em distância, que pode ser obtida 
unindo os clientes i e j e atendendo a eles com um único veículo. A economia 
(Sij) é calculada com a seguinte fórmula: 
𝑆𝑖𝑗 = 𝑆𝑗𝑖 = 𝑑𝑖1 + 𝑑𝑗1 − 𝑑𝑖𝑗 
Sendo: 
𝑆𝑖𝑗 ou 𝑆𝑗𝑖 economia de percurso gerada (ganho); 
𝑑𝑖1 distância entre o centro de distribuição e o ponto i; 
𝑑𝑗1  distância entre o centro de distribuição e o ponto j; 
𝑑𝑖𝑗 distância entre o ponto i e o j.Novaes (2003) apresenta as seguintes etapas para utilizar o método: 
1. Combinar todos os pontos, dois a dois, e calcular o ganho para cada 
combinação; 
 
 
13 
2. Ordenar todas as combinações i e j, de forma decrescente, segundo o 
valor dos ganhos; 
3. Iniciar com a combinação de dois pontos que apresentar o maior ganho. 
Depois, vai descendo na lista de combinações, sempre obedecendo a 
sequência decrescente de ganhos; 
4. Tirar a sequência de combinações para um par de pontos, verificar se os 
dois pontos fazem parte de um roteiro iniciado; 
5. Para cada vez que se acrescentar um ou mais pontos no roteiro, ou 
quando dois roteiros se fundirem, verifique se a nova configuração 
satisfaz as restrições impostas. 
Obviamente, essa abordagem não garante uma solução ótima, mas 
aumenta a probabilidade de alcançar uma boa solução. 
TROCANDO IDEIAS 
O documento Decisões sobre transportes (2013), elaborado por Mayara 
Murça, do ITA, traz informações de extrema relevância em termos logísticos de 
decisões sobre transportes. No que tange a esta aula, traz, além de conteúdo 
explicativo, inúmeros exemplos de aplicações, com suas respectivas soluções, 
agregando uma ótima experiência de aprendizado e aplicabilidade do conteúdo 
estudado. 
Saiba mais 
Acesse o documento na íntegra em: <http://www2.ita.br/~correia/TRA-
53/semana_3.pdf>. Acesso em: 10 out. 2019. 
NA PRÁTICA 
Branco e Gigioli (2014) estudaram as rotas elaboradas por uma 
distribuidora de tintas que não possuía um plano de rota, a qual apresentou 
diferenças visíveis com os métodos de roteirização. 
Essa distribuidora ficava no centro-oeste do estado de São Paulo, na 
cidade de Pederneiras. Os autores analisaram a rota feita pela empresa 
normalmente e a rota depois da aplicação do método matemático de Clarke e 
Wright, utilizado em softwares de roteirização. Verificaram os custos, o tempo e 
algumas outras restrições importantes para a empresa, antes e depois da 
aplicação do método. 
 
 
14 
Depois de aplicá-lo, compararam os resultados obtidos com os anteriores. 
Dessa forma, foi possível reduzir o custo total mensal de R$ 3.680,34 para 
R$ 3.392,19, valor que no final de um ano resultaria num montante economizado 
de R$ 3.457,80, além de o custo médio por cliente ter uma redução mensal de 
R$ 22,19. Foram gastas, antes do método, 597,60 horas no tempo de duração 
do experimento para os transportes. Depois do método, esse número caiu para 
531,76 horas – uma economia de 65,84 horas, ou seja, praticamente três dias. 
FINALIZANDO 
No cenário atual, as empresas que atuam no ramo da logística se 
esforçam para se manter competitivas no mercado. Para isso, buscam formas 
de reduzir custos e melhorar o nível da prestação de serviços. O papel da 
roteirização dentro de uma organização é importante para que isso ocorra. 
É possível utilizar métodos para melhorar a roteirização e obter um 
resultado mais satisfatório, melhorando custos, qualidade do serviço, tempo de 
distribuição, entre outros. 
 
 
 
15 
REFERÊNCIAS 
BALLOU, R. H. Logística empresarial: transporte, administração de materiais 
e distribuição física. São Paulo: Atlas, 1993. 
_____. Gerenciamento da cadeia de suprimentos: planejamento, organização 
e logística empresarial. 4. ed. Porto Alegre: Bookman, 2001. 
_____. Gerenciamento da cadeia de suprimentos/Logística empresarial. 5. 
ed. Porto Alegre: Bookman, 2006. 
BRANCO, F. J. C.; GIGIOLI, O. A. Roteirização de transporte de carga: estudo 
de caso – distribuidora de tintas e seu método de entregas. FAE, Curitiba, v. 17, 
n. 2, p. 56-81, jul./dez. 2014. 
CHRISTOFIDES, N. The Traveling Salesman Problem: A Guided Tour of 
Combinatorial Optimization. Hoboken: John Wiley & Sons, 1985. 
GARCIA, A. Maplink torna ferramenta Minhas Rotas gratuita. Frota&Cia Online, 
[S.l.], 19 jun. 2018. Disponível em: <http://www.frotacia.com.br/maplink-torna-
ferramenta-minhas-rotas-gratuita/>. Acesso em: 11 out. 2019. 
HIJJAR, M. F.; LOBO, A. Cenário da infraestrutura rodoviária no Brasil. Rio 
de Janeiro: Ilos, 2011. 
MURÇA, M. C. Decisões sobre transportes: parte I. São José dos Campos: 
ITA, 2013. Disponível em: <http://www2.ita.br/~correia/TRA-53/semana_3.pdf>. 
Acesso em: 10 out. 2019. 
NOVAES, A. G. N. Logística e gerenciamento da cadeia de distribuição. São 
Paulo: Atlas, 2003. 
_____. Logística e gerenciamento da cadeia de distribuição: estratégia, 
operação e avaliação. 3. ed. Rio de Janeiro: Elsevier, 2007. 
PROBLEMA do caixeiro-viajante. Wikipédia. Disponível em: 
<https://pt.wikipedia.org/wiki/Problema_do_caixeiro-viajante>. Acesso em: 11 
out. 2019. 
SILVA, V. Logística e transporte na indústria brasileira de laticínios: estudo 
de casos. [S.l.]: [s.n.], 2003. 
TAVARES, P. C. Algoritmo. In: Enciclopédia Verbo Luso-Brasileira da Cultura 
– Edição Século XXI. Braga; Rio de Janeiro: Editorial Verbo, 1998. v. II. 
 
 
16 
TOIGO, R.; VALLE FILHO, A. M.; LAVRATTI, F. B. Sistema de roteirização de 
entregas. Hífen, Uruguaiana, v. 31, n. 59-60, p. 51-56, 2007.