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

Prévia do material em texto

ROTEIRIZAÇÃO E 
PROGRAMAÇÃO DE 
TRANSPORTES 
AULA 2 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof.ª Liziane Hobmeir 
 
 
2 
CONVERSA INICIAL 
Nesta aula, vamos abordar as técnicas e iniciar o assunto sobre a 
roteirização, suas técnicas e entender sobre a importância da operação na 
logística de transportes. 
CONTEXTUALIZANDO 
As empresas em geral, no mundo todo, pensam em atender o cliente da 
melhor maneira possível, realizando as entregas mais rapidamente. Porém, 
ainda se têm problemas com os custos logísticos, e um deles é o custo com o 
transporte e o tempo que se é gasto para realização dessa atividade. 
Segundo Ballou (2001), os custos de transporte variam tipicamente entre 
um e dois terços do total dos custos logísticos. Melhorara eficiência, portanto, 
com a utilização máxima do equipamento e do pessoal de transporte é de grande 
interesse para as empresas. Um dos problemas frequentes de decisão em 
transportes é reduzir os custos dos transportes e também melhorar o serviço ao 
cliente, encontrando os melhores trajetos que um veículo deve fazer através da 
malha, seja rodoviária, aérea ou ferroviária, os quais minimizarão o tempo total 
ou a distância. 
Cordeau e Laporte (2003) citam, de forma geral, o problema de 
roteirização e programação de veículos, que compartilham vários problemas 
característicos relacionados com coleta e entrega. No entanto, tem-se um 
agravante no transporte de pessoas, que se torna mais importante e complexo, 
pois o nível do critério muda e passa a ser um nível de excelência focado em 
qualidade para as pessoas. Assim, segundo os autores, pontualidade, redução 
do tempo de espera e duração das rotas são mais críticos nesse caso do que 
em outros problemas correlatos de transporte de carga. 
Em se tratando de cargas, considerando-se o nível de demanda atual, não 
somente no Brasil, mas em todo o mundo, bem como sua esperada tendência 
de aumento, faz-se imperativo o uso de métodos automatizados de roteirização 
e programação dos veículos para otimizar esse tipo de serviço. 
Saiba mais 
Para entender o que é roteirização, assista ao vídeo “Conceito de 
Roteirização – Entenda a Importância desse Setor”. Disponível em: 
<https://www.youtube.com/watch?v=L4BAw5sHFXM>. 
 
 
3 
TEMA 1 – PROBLEMAS DE ROTEIRIZAÇÃO 
De acordo com Novaes (2000), para se efetuar um planejamento de 
transportes é necessário conhecer os seguintes elementos: 
 os fluxos nas diversas ligações da rede; 
 o nível de serviço atual e desejado; 
 a capacidade dos veículos e as características da carga. 
O planejamento se faz rota por rota. Nesse sentido é que se insere o 
Problema de Roteirização de Veículos. 
Segundo Christofides (1985), o problema pode ser definido como aquele 
em que os veículos, localizados em um depósito central, são 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 e é 
conhecido pelo nome genérico de Problema de Roteirização de Veículos (PRV). 
Segundo Partika e Hall (2000, citados por Novaes, 2000), um problema 
real de roteirização é definido por três fatores fundamentais: 
 decisões, 
 objetivos; e 
 restrições. 
As decisões são a respeito da alocação de veículos e respectivos 
motoristas, envolvendo também a programação e o sequenciamento das visitas. 
Como objetivos principais, o processo de roteirização visa propiciar um serviço 
de alto nível aos clientes, mas ao mesmo tempo mantendo os custos 
operacionais e de capital tão baixos quanto possível. 
No entanto, deve obedecer a certas restrições. Alguns tipos de restrições 
possíveis são: 
 concentração dos pontos de entrega; 
 horários (janelas de tempo); 
 capacidade do veículo; 
 jornada de trabalho dos motoristas; 
 restrições de trânsito (por exemplo: as velocidades máximas permitidas). 
 
 
 
4 
Dentre a classificação dos problemas de roteirização e programação de 
veículos, aqueles que envolvem o transporte de passageiros de seus locais de 
origem a seus destinos são conhecidos genericamente na literatura como 
problemas do tipo “dial-a-ride” (Znamensky; Cunha, 1998). 
O problema de roteirização e programação de veículos ou dial-a-ride 
problem – Darp, conforme Cordeau e Laporte (2003), consiste no 
desenvolvimento de rotas e escalas de veículos para transportar diversos 
usuários, os quais especificam requisições de embarque e desembarque (coleta 
e entrega) entre locais de origem e destino específicos. 
O objetivo desse processo é planejar um conjunto de rotas para alguns 
veículos com “custo mínimo”, capaz de acomodar o maior número possível de 
usuários, e sempre obedecendo a um conjunto de restrições. 
Em se tratando especificamente do caso de transporte de pessoas com 
deficiência, um ponto de embarque (coleta) corresponde ao endereço onde 
determinada pessoa deve ser buscada, e o ponto de desembarque (entrega) 
associado corresponde ao endereço onde a mesma pessoa deve ser entregue. 
Cada ponto de embarque e seu respectivo ponto de desembarque, juntamente 
com suas respectivas “janelas de tempo”, formam uma Requisição de Transporte 
de um cliente. 
Uma tendência comum nos modelos do Darp é deixar que os usuários 
determinem uma “janela de tempo” (isto é, janelas ou intervalos de horários para 
seu atendimento) para sua partida e sua chegada, pois, segundo Cordeau e 
Laporte (2003), os usuários devem estar aptos a especificar um intervalo de 
horários para seu embarque e desembarque, ambos em locais específicos, 
possibilitando assim um melhor planejamento da programação e roteirização dos 
veículos como um todo. 
Cada veículo possui uma capacidade, medida normalmente em número 
de assentos convencionais e número de cadeiras de rodas, por exemplo. 
Analogamente, a cada solicitação de atendimento está associada uma ocupação 
em termos de quantidade de assentos convencionais (eventuais 
acompanhantes) e em quantidade de cadeiras de rodas (Znamensky; Cunha, 
1998). 
Segundo Cordeau e Laporte (2003), e outros diversos autores, o Darp 
pode ser abordado de forma estática ou dinâmica. No primeiro caso, todas as 
requisições de transporte são conhecidas a priori, ao passo que, no segundo 
 
 
5 
caso, são consideradas requisições feitas ao longo do dia (normalmente por 
telefone), e as rotas dos veículos são ajustadas em tempo real de acordo com a 
demanda. Porém, na prática, raramente existem Darp dinâmicos “puros”, pois 
normalmente um subconjunto de requisições é conhecido com antecedência. 
O Darp pode ser considerado com vários objetivos distintos, por exemplo: 
minimizar os custos operacionais sujeitos à satisfação de toda a demanda; 
maximizar a satisfação da demanda, sujeito à disponibilidade dos veículos; ou 
outras combinações destes que geralmente buscam um equilíbrio entre custo 
operacional e qualidade do serviço prestado. 
Os problemas são resumidos entre transporte de cargas e componentes 
e o transporte de pessoas e os problemas de roteirização são: 
 problema de roteirização pura; 
 problema de programação de veículos e tripulações; 
 problema de roteirização e programação. 
Saiba mais 
Assista ao vídeo “Quais são os fatores de relevância para roteirização?” 
para ver os fatores de relevância dentro da roteirização. Disponível em: 
<https://www.youtube.com/watch?v=xWmkjhhae_k>. 
TEMA 2 – PCV – PRINCÍPIO DA NECESSIDADE DE ROTEIRIZAÇÃO 
Os problemas de roteirização pura são problemas espaciais que não 
consideram as variáveis temporais ou precedências entre as atividades para 
elaboração dos roteiros de coletas e/ou entrega. 
Em alguns casos, tem-se apenas a restrição de comprimento máximo da 
rota. Nesse tipo de problema, existe um conjunto de nós e/ou arcos para serem 
atendidos que formarão uma sequência de locais (rota), buscando alcançara 
minimização do custo total de transporte. 
Para Znamensky e Cunha (1997), a principal condicionante que determina 
a qualidade da solução dos problemas dessa categoria é a natureza espacial. 
Pertencem a esse grupo: 
 Problema do Caixeiro Viajante – PCV (Travelling Salesman Problem – 
TSP): citado por Sarkis (2000) como o mais fundamental e conhecido de 
todos os problemas, consiste em determinar uma rota de mínimo custo 
que passe por todos os nós uma única vez. Observa-se que esse tipo de 
 
 
6 
problema não possui restrições de tempo nem limitações de capacidade. 
Sua formulação original é a seguinte: existem N pontos (nós) em uma rede 
da qual o caixeiro viajante deve partir de um ponto inicial (depósito ou 
base) e visitar pelo menos uma vez os outros N – 1 pontos, voltando no 
final da viagem para o ponto inicial, conforme apresenta a Figura 1. Para 
Botelho (2003), se o custo para ir de um nó qualquer “i” para outro nó 
qualquer “j” for igual ao custo de ir do nó “j” para o nó “i”, o problema será 
denominado simétrico. Caso contrário, o problema será assimétrico. 
Nesse tipo de problema, as demandas estão nos nós e os custos estão 
nas movimentações de um nó origem até um nó destino. 
Figura 1 – Exemplo do problema do Caixeiro Viajante 
 
 
Fonte: Adaptado de Ballou, 2001. 
 Problema do Carteiro Chinês – PCC (Chinese Postman Problem – CPP): 
tem como objetivo determinar uma rota de comprimento mínimo dentro de 
uma área que parte de um ponto de origem, percorrendo pelo menos uma 
vez todas as arestas/arcos da rede, e volta à origem. 
 Múltiplos Caixeiros Viajantes: esse problema é uma generalização do 
PCV, na qual se considera mais de um caixeiro viajante. Os M veículos 
da frota originam suas rotas de um depósito comum e terminam nesse 
mesmo local. Não há restrições sobre o número de nós que cada um pode 
visitar, exceto que cada veículo visite no mínimo um nó. 
 
 
7 
 Roteirização em nós com único depósito e vários veículos: esse problema 
clássico de roteirização é também conhecido como PRV. Para Laporte et 
al. (2000), o PRV consiste em designar M rotas de veículos com menor 
custo total, cada rota começando e terminando em um depósito, de modo 
que cada cliente (nós) é visitado precisamente uma vez. A demanda total 
de qualquer rota não excede a capacidade Q do veículo, e o comprimento 
de qualquer rota não excede o comprimento máximo preestabelecido L. 
 Roteirização em nós com vários depósitos e vários veículos: esse 
problema também é uma generalização do problema de múltiplos 
caixeiros viajantes, porém com vários depósitos, em que cada veículo é 
alocado a um único depósito, originando e terminando a viagem em um 
mesmo depósito. 
 Roteirização em nós com único depósito e vários veículos com demandas 
incertas: esse problema é semelhante ao PRV, porém as demandas não 
são conhecidas com certeza, seguindo uma distribuição probabilística. 
 Carteiro Chinês com limite de capacidade: esse problema é uma 
generalização do PCC, em que há restrições de capacidade dos veículos. 
O Quadro 1 demonstra as características dos problemas de roteirização 
pura em que são classificadas a modelagem, citado anteriormente, em 
problemas específicos de cobertura de nós e em problema específico de 
cobertura de vias ou arcos. Observa-se que o Problema do Caixeiro Viajante 
(PCV) destaca-se como clássico entre os problemas envolvendo coberturas de 
nós e o PCC para cobertura de vias. 
 
 
8 
Quadro 1 – Características dos problemas de roteirização pura 
 
Fonte: Adaptado de Bodin et al., 1983. 
Os problemas de programação podem ser considerados como problemas 
de roteirização com restrições adicionais relacionadas ao tempo quando várias 
atividades precisam ser executadas (Naruo, 2003). 
Conforme Bodin et al. (1983), esse tipo de problema pode ser dividido em 
dois casos: Programação de Veículos e Programação de Tripulações. O 
primeiro se preocupa com a sequência das atividades para os veículos no 
espaço e no tempo, e o segundo com a movimentação da tripulação no espaço 
e no tempo. 
Segundo Bodin et al. (1983) e Naruo (2003), os problemas de 
programação de veículos são classificados em: 
 um único depósito, que consiste no particionamento dos nós de uma rede 
acíclica em um conjunto de caminhos, de modo que uma determinada 
função custo seja minimizada. Cada caminho corresponde a um veículo. 
Uma função objetivo que minimize o número de caminhos efetivamente 
minimiza os custos de capital, desde que o número de veículos 
necessários seja igual ao número de caminhos; 
 
 
9 
 com restrições de tamanho de rota, que considera as restrições de tempo 
máximo de viagem ou de distância máxima percorrida pelo veículo antes 
deste voltar para o depósito. Essa restrição é comumente encontrada na 
prática e corresponde às restrições de reabastecimento, considerações 
de manutenção etc.; 
 com múltiplos tipos de veículos, que considera a possibilidade de que 
veículos com diferentes capacidades estejam disponíveis para a 
realização das tarefas. É semelhante ao problema anterior; 
 com múltiplos depósitos, que ocorre quando as tarefas podem ser 
realizadas por veículos por meio de depósitos diferentes, e estes, ao final 
do serviço, retornam à sua origem. Para o tamanho da frota de cada 
depósito, deve se especificar um mínimo e o máximo. 
As restrições que determinam a complexidade do problema de 
programação no mundo real são: limite de tempo que um veículo pode estar em 
serviço antes de retornar ao depósito; tarefas que só podem ser realizadas por 
tipos específicos de veículos; e presença de diferentes depósitos. Para a 
programação de tripulações, Bodin et al. (1983) consideram os seguintes 
problemas. 
 Programação de pessoal em um local fixo: consiste em encontrar um 
conjunto de trabalho capaz de atender a todas as necessidades de tarefas 
em todos os períodos de tempo. Assume-se que os trabalhadores são 
intercambiáveis e que um determinado trabalhador possa ser deslocado 
ao final de cada período de tempo e que outro possa ser alocado no início 
de cada período. 
 Programação de veículos e tripulações no transporte público: determina a 
alocação ótima de veículos a um conjunto de viagens programadas de 
linha, e determina também as jornadas das tripulações, considerando que 
as trocas de serviço e de turno só podem ser realizadas em pontos 
específicos dos trajetos das linhas. 
 Programação de tripulações no transporte aéreo: é semelhante ao 
problema de programação de veículos e tripulações do transporte público, 
em que as tabelas de partidas e chegadas são previamente definidas. 
 Programação de pessoal em turnos de revezamento: caracteriza-se pela 
programação diária de um dia para outro, havendo um rodízio de turno de 
 
 
10 
pessoal, em função de restrições trabalhistas, sindicais, dentre outras. Há 
necessidade de uma equalização das cargas e das condições de trabalho 
para as atividades que percebem a mesma remuneração. 
Para Naruo (2003), os problemas de roteirização e programação 
envolvem relações de precedência entre as atividades envolvidas e também 
restrições de janelas de tempo para as atividades (horário de atendimento e 
outros). Esses problemas podem ser considerados como uma combinação de 
problemas de roteirização e programação. Bodin et al. (1983) apontam os 
principais problemas para essa categoria. 
 Ônibus escolares: consiste em um número de escolas, e cada uma delas 
possui um conjunto de paradas de ônibus com um dado número de 
estudantes atrelados, com janelas de tempo correspondentes aos 
horários de início e término do período escolar. O principal objetivo do 
problema é minimizar os custos de transportes para os municípios. 
 Cavalos mecânicos para carretas com carga completa: ocorre quando 
uma carreta possui apenas uma origem e um destino, com a capacidade 
de um cavalo mecânico sendopreenchida por apenas uma carreta. 
Envolve relação de precedência. 
 Cavalos mecânicos para carretas com carga parcial: esse problema é 
semelhante ao anterior, porém a carga não precisa ser completa e a 
carreta pode ser separada em diferentes origens e destinos. 
 Serviço de coleta de resíduos domiciliares e de varrição de ruas: é 
semelhante ao problema do carteiro chinês, mas com restrições de 
capacidade dos veículos, de duração máxima de jornada e janelas de 
tempo associadas aos horários de proibições de estacionamento, de 
forma a possibilitar a execução do serviço de varrição. Em geral, o objetivo 
é a minimização da frota ou um objetivo correlato. 
 Transporte de pessoas com deficiência ou transporte pré-programado: 
também conhecidos como dial-a-ride, segundo Znamensky e Cunha 
(2000), devido à possibilidade de o serviço ser acionado por telefone. 
Possui origens e destinos diferentes, em geral para serviços porta a porta. 
A precedência entre tarefas é uma restrição decisiva para a viabilidade da 
solução. 
 
 
11 
 Aeronaves: tem como objetivo programar simultaneamente rotas aéreas 
(início, final e escalas), alocar as aeronaves e definir as tabelas de 
horários, levando em consideração dados da demanda entre pares de 
cidades, frequência do serviço desejado, voos diretos x escalas etc. Esses 
problemas envolvem tanto o transporte de passageiros como o transporte 
de cargas e encomendas. 
Znamensky e Cunha (2000) enfatizam que todos os tipos de problemas 
de roteirização e programação são de natureza essencialmente operacional, ou 
seja, fazem parte das tarefas rotineiras de programação da frota, realizadas com 
frequência regular, em geral diária ou semanal. 
Esse mesmo autor ressalta que existem também, na literatura, problemas 
de roteirização de natureza mais tática ou estratégica do que operacional, tais 
como problemas integrados de localização e roteirização e problemas integrados 
de estoque e roteirização. Nesses casos, a programação dos atendimentos deve 
levar em consideração não só aspectos espaciais e os custos dos roteiros, como 
também questões como o nível de estoque e problemas de faturamento e 
roteirização, nos quais é preciso definir simultaneamente quem vai ser atendido 
a cada dia de um período de tempo pré-determinado. No problema de 
roteirização clássico, todas as demandas são conhecidas antecipadamente. 
Vídeo 
Assista ao vídeo “Algoritmo Colônia de Formigas – Aplicado Ao Problema 
do Caixeiro Viajante”, sobre o problema de Roteirização sobre o Caixeiro 
Viajante. Disponível em: <https://www.youtube.com/watch?v=UXSc0j 
wgZis>. 
TEMA 3 – TÉCNICAS DE ROTEIRIZAÇÃO 
Após apresentar os tipos de problemas, são abordados a seguir os 
possíveis métodos de solução. Os métodos de roteirização continuam em 
expansão em número de pesquisas e aplicação, comprovando sua importância 
nas organizações que buscam minimizar os custos e otimizar os tempos de 
entrega de seus produtos, consolidando suas práticas logísticas. Os principais 
métodos encontrados na literatura são os métodos heurísticos, problema do 
caixeiro viajante, método de varredura e método de Clarke e Wright. 
 
 
12 
O método de varredura, também conhecido como Sweep Algorithm, é um 
método heurístico em que se procura obter a solução dos problemas em duas 
etapas distintas: a primeira visa agrupar os pontos de demanda segundo algum 
critério de proximidade; na segunda, cada grupo é solucionado 
independentemente (Novaes, 2000). 
Para Ballou (2001), o método de varredura é recomendável pela facilidade 
de resolução dos problemas de maneira rápida e eficaz, e por apresentar uma 
margem de erro de 10%, sendo aceitável quando se pretende estabelecer uma 
solução ótima absoluta. 
O método de Varredura, para Novaes (2000), é 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 anti-horário até a localização 
de um cliente. 
c. Fase 3: Experimentar os clientes potenciais, analisando se podem ser 
inclusos no plano de rotas. 
d. Fase 4: Na impossibilidade de inclusão, inicia-se um novo roteiro com o 
encerramento do anterior. 
e. Fase 5: Aplicar, para cada roteiro, o método 3-opt com a finalidade de 
reduzir o caminho a ser percorrido. 
Segundo Ballou (2001), a desvantagem do método diz respeito à maneira 
como os roteiros são formados. É um processo de dois estágios, em que em 
primeiro lugar se atribuem as paradas a cada veículo, para somente depois 
estabelecer a sequência das paradas nas estradas. Em função desse processo 
de dois estágios, questões de tempo, como a duração total da viagem e a 
atribuição de janelas de tempo, não são adequadamente tratadas. 
O método de resolução utilizado é o Algoritmo de Clarke & Wright, 
publicado por G. Clarke e J. W. Wright (1964) no artigo “Scheduling of Vehicles 
From a Central Depot to a Number of Delivery Points”, muito aplicado e 
conhecido na resolução de problemas complexos de roteamento de veículos. 
Muito utilizado na resolução de problemas isolados, esse método aparece 
também embutido dentro de muitos softwares de roteirização. 
Segundo Ballou (2000), 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. 
 
 
13 
Este método 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. É um método baseado no 
conceito de ganho. 
 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 tapa: inicia-se com a utilização da combinação de dois nós que 
tenham apresentado o maior ganho. Posteriormente, na análise de outras 
situações, vai-se descendo na lista de combinações, sempre obedecendo 
à sequência decrescente de ganhos. 
 Quarta etapa: para um par de pontos (i, j), tirado da sequência de 
combinações, verifica-se 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, 
cria-se um novo roteiro com esses dois pontos; 
 se o ponto i já pertencer a um roteiro iniciado, verifica-se se esse 
ponto é o primeiro ou o último desse roteiro (sem contar o CD). Se 
a resposta for positiva, 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 satisfazer essa condição 
separadamente, passa-se para o próximo item dessa etapa; 
 se ambos os pontos i e j fazem parte, cada um deles, de roteiros 
iniciados, mas diferentes, verifica-se se ambos são extremos dos 
respectivos roteiros. Se a resposta for positiva, funde-se os dois 
roteiros em um só, juntando-os de forma a unir i a j. Caso contrário, 
passa-se para a quinta etapa; 
 se ambos os nós i e j pertencerem a um mesmo roteiro, passa-se 
para a quinta etapa. 
 
 
14 
 Quinta etapa: cada vez que se acrescenta um ou mais pontos em um 
roteiro, ou quando se fundem dois roteiros em um só, verifica-se se a nova 
configuração satisfaz as restrições de tempo e de 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. 
Fechamos, assim, as propostas detécnicas de roteirização escolhidas 
para essa rota. 
Saiba mais 
Vocês já sabem organizar o roteiro no Google Maps? Assista ao vídeo 
“Roteiro no Google Maps” para conhecer a ferramenta. Disponível em: 
<https://www.youtube.com/watch?v=HpqDAjeDIIU>. 
TEMA 4 – OPERAÇÕES DE TRANSPORTE E IMPACTO NOS PROCESSOS DE 
ROTEIRIZAÇÃO 
Para elaborar o modelo de roteirização, foi necessário levantar todos os 
dados de entrada, características de demanda e limitações do setor de 
distribuição. Esses dados estão associados aos parâmetros definidos na 
formulação do problema. 
Os parâmetros relevantes são a capacidade dos veículos, as demandas 
de cada cliente e os tempos de deslocamento entre dois pontos. Pode-se então 
dividir os dados necessários em três categorias distintas, a saber, recursos de 
distribuição, dados sobre os clientes e dados do processo de distribuição atual. 
Novaes (2000) comenta que, na prática, problemas de roteirização 
ocorrem com bastante frequência na distribuição de produtos e serviços, e lista 
alguns exemplos: 
 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; 
 
 
15 
 coleta de lixo urbano; 
 entrega domiciliar de correspondência; 
 transporte de pessoas. 
Como já vimos, o problema de roteirização de veículos sem restrições 
recebe o nome de PCV – Problema do Caixeiro Viajante. O PCV consiste no 
caso em que um caixeiro viajante tem de visitar um certo número de cidades 
localizadas em uma região, devendo achar a sequência que minimize o custo 
total. 
Para o problema de roteirização de veículos com restrições, de acordo 
com Ribeiro (2001), para se resolver o PRV deve-se analisar, em primeira 
instância, as seguintes variáveis envolvidas: 
 número de veículos envolvidos; 
 capacidades desses veículos; 
 pontos de paradas em cada roteiro; 
 sequências de paradas. 
Percebe-se que são muitas as variáveis a se pensar para se ter 
assertividade no processo entre operações e roteirização. 
Saiba mais 
Assista ao vídeo “Distribuição física e transportes: aprenda a gerenciar de 
forma eficaz sua estrutura de transportes”, para capacitar os gestores a planejar, 
executar e controlar a operação de transportes em suas empresas, otimizando 
os resultados logísticos e globais. Disponível em: 
<https://www.youtube.com/watch?v=jeWjq_LDdvw>. 
TEMA 5 – OPERAÇÕES DE PROGRAMAÇAO DE VEÍCULOS 
Diante do cenário atual de grande competitividade empresarial, é preciso 
estar sempre em busca de aperfeiçoamento das atividades. A logística é parte 
integrante e indispensável nesse processo, e suas atividades necessitam ser 
planejadas e geridas de forma a estarem ligadas aos demais processos da 
empresa. Assim, é de extrema relevância que o processo de entrega esteja bem 
consolidado. 
O campo da logística evoluiu de um tratamento mais restrito, voltado à 
distribuição física de matérias e bens, para um escopo mais abrangente, em que 
 
 
16 
se considera a cadeia de suprimentos como um todo e as atividades de compras, 
administração de matérias e distribuição (Bozzi Filho; Liva, 2002). 
Surge, então, o conceito de Supply Chain Management (“Gestão de 
cadeia de suprimentos”), definido por Bozzi Filho e Liva (2002) como um 
processo orientado, com abordagem integrada, para compra, produção e 
entrega de produtos e serviços aos consumidores. Esse processo inclui 
fornecedores de diversas camadas, operações internas, operações comerciais, 
atacado/varejo e consumidores finais, e, com isso, a necessidade de atender aos 
clientes, agregando valor no processo de distribuição. 
Dentro dos canais de distribuição, temos o transporte e todos os 
processos de roteirização e programação, que podem ser descritos como a 
decisão que se refere ao grupo de clientes a serem visitados, e posteriormente 
o cronograma de sequenciamento das visitas e a restrição, em que é necessário 
completar as rotas com os recursos disponíveis (Novaes, 2000). 
O objetivo é determinar rotas de veículos que minimizem os custos de 
transporte, de modo que as demandas de todos os clientes sejam atendidas, e 
que as restrições de capacidade dos veículos sejam respeitadas. A roteirização 
pode ser caracterizada por n clientes (representados em uma rede de 
transportes por nós ou arcos) que deverão ser servidos por uma frota de 
veículos, sem apresentarem restrições à ordem em que deverão ser atendidos. 
As operações de programação ocorrem em fábricas, indústrias, atacados, 
varejos e até mesmo no nosso dia a dia. 
Saiba mais 
Assista ao vídeo “Roteirização de entregas: 3 dicas para aumentar sua 
produtividade logística”, para compreender como a roteirização de carga pode 
representar um grande ganho para a logística de atacadistas e distribuidores. 
Disponível em: <https://www.youtube.com/watch?v=n_sbbXJPbfE>. 
TROCANDO IDEIAS 
Podemos analisar a importância da disciplina no processo de distribuição. 
Como citados nos objetivos, é importante trazer o processo de roteirização e 
programação para as empresas e torná-los um diferencial competitivo. 
 
 
17 
NA PRÁTICA 
O que é roteirização de transporte? 
Percebe-se a importância da roteirização de transporte por meio da 
gestão de custos das empresas. Em diversos sites e blogs de empresas e de 
gestores da área de logística, é unanime o destaque sobre esse assunto: 
roteirização de transporte. Para qualquer planejamento de custos logísticos, 
precisa-se, por exemplo, do planejamento do valor do frete. Para levar uma carga 
de uma origem até o seu destino, é necessário roteirizar e principalmente 
considerar as variantes, como melhor caminho, trânsito, distância, pedágios, 
restrições no trajeto, e riscos no transporte. 
Pode-se resumir, então, que a roteirização é o planejamento de rotas dos 
veículos da frota, de terceiros e agregados, com foco em entregas mais 
eficientes e itinerários mais otimizados. Para tanto, a atividade de roteirizar 
acaba sendo uma atividade repleta de estratégias, e muitas vezes é 
desenvolvida manualmente, mas existem softwares que auxiliam nessas 
atividades. Tais softwares realizam atividades como definição de rotas, 
otimização de trajetos, verificação da capacidade de veículos e tamanho da frota, 
tipo de carga, entregas e prioridades. 
Com a roteirização, é possível reduzir o consumo de combustível, pois as 
rotas são bem elaboradas e otimizadas, reduzir o tempo gasto nas entregas, ter 
melhor controle sobre os veículos disponíveis, e, principalmente, otimizar a 
jornada de trabalho atendendo à CLT. Essas são algumas informações com que 
as empresas de transporte se preocupam e, por isso, entendem dos benefícios 
da roteirização de transporte. 
FINALIZANDO 
Começamos a aula apresentando a roteirização e seus problemas, o 
princípio da necessidade de roteirização, apresentando técnicas de roteirização 
e comentando, ao final da aula, as operações de transporte e os impactos nos 
processos de roteirização, bem como as operações focadas em programação de 
veículos. Podemos perceber que é importante entendermos sobre a roteirização 
para podermos fazer o melhor processo de roteirização e, consequentemente, 
ter redução de custos no transporte. 
 
 
18 
REFERÊNCIAS 
BALLOU, R. H. Gerenciamento da cadeia de suprimentos: planejamento, 
organização e logística empresarial. 4. ed. Porto Alegre: Bookman, 2001. 
BODIN, L.D. et al. Routing and scheduling of vehicles and crews: the state of the 
art. Computers and Operations Research, v.10, n. 2, 1983. 
BOTELHO, L. G. Um método para o planejamento operacional da 
distribuição: aplicação para casos com abastecimento de granéis líquidos. 100p. 
Dissertação (Mestrado em LogísticaEmpresarial) – Programa de Pós-Graduação 
em Logística Empresarial, Pontifícia Universidade Católica do Rio de Janeiro, Rio 
de Janeiro, 2003. 
BOZZI FILHO, M.; LIVA, P. B. G. Supply Chain Management – I. TecHoje, uma 
revista de opinião. Disponível em: <http://www.techoje.com.br/site/techoje/ 
categoria/detalhe_artigo/304>. Acesso em: 21 set. 2019. 
CHRISTOFIDES, N. The Traveling Salesman Problem: A Guided Tour of 
Combinatorial Optimization. Hoboken: John Wiley & Sons, 1985. 
CORDEAU, J. F.; LAPORTE, G. A tabu search heuristic for the static multi-vehicle 
dial-aride problem. Transportation Research B, v. 37, p. 579-594, 2003. 
LAPORTE, G. et al. Classical and modern heuristics for the vehicle routing 
problem. International Transactions in Operational Research, v. 7, n. 4/5, p. 
285-300, 2000. 
NARUO, M. K. O estudo do consórcio entre municípios de pequeno porte para 
disposição final de Resíduos Sólidos Urbanos, utilizando Sistemas de Informação 
Geográficos. 283 p. Dissertação (Mestrado em Engenharia) – Escola de 
Engenharia de São Carlos, Universidade de São Paulo, São Carlos, 2003. 
NOVAES, A. G. N. Logística e gerenciamento da cadeia de distribuição. São 
Paulo: Atlas, 2000. 
PARTYKA, J. G.; HALL, R. W. On the road to service. OR/MS Today, Catonsville, 
2000. Disponível em: <https://www.informs.org/ORMS-Today/Archived-Issues/ 
2000/orms-8-00/On-the-Road-to-Service>. Acesso em: 21 set. 2019. 
RIBEIRO, G. M. e Campos, V. B. G. (2001) Um Procedimento para Roteirização 
e Programação de Veículos Usando a Heurística de Ganhos para o Planejamento. 
 
 
19 
XXXIII SBPO Routing Systems Informática Ltda – Manual do RoadShow Módulos 
I e II. 
SARKIS, L. F. P. G. Resíduos de serviços de saúde em cidades de médio 
porte: caracterização de sistemas de coleta e aplicação de um sistema de 
informação geográfica na roteirização e coleta de transporte. 216 p. Dissertação 
(Mestrado em Engenharia) – Escola de Engenharia de São Carlos, Universidade 
de São Paulo, São Carlos, 2000. 
ZNAMENSKY, A.; CUNHA, C. B. Um modelo para o problema de roteirização e 
programação do transporte de deficientes. In: CONGRESSO DE PESQUISA E 
ENSINO EM TRANSPORTES, 13., São Carlos. Anais… São Carlos, 1998.