ROTEIRIZAÇÃO ESTÁTICA COM JANELAS DE TEMPO USANDO O TRANSCAD

Gabriela R. Thedim

Rafaela G. Ourofino

Hugo M. RepolhoDepartamento de Engenharia Industrial

PUC-Rio - Pontifícia Universidade Católica do Rio de Janeiro

RESUMO A proliferação das vendas em e-commerce representa uma nova área de negócio para empresas de distribuição e

operadores logísticos. A distribuição neste negócio caracteriza-se por uma elevada frequência de pequenas

entregas dispersas numa determinada região, o que origina problemas de roteirização, tendo em conta as janelas

de tempo de entregas dos clientes. Neste artigo serão estudados os problemas de roteirização de veículos com

janelas de tempo do ponto de vista formal e sua resolução com recurso a softwares comerciais (TransCAD). O

objetivo último é a resolução do problema de distribuição de uma empresa de produtos de e-commerce. A

resolução irá recorrer ao modelo de roteirização estática com janelas de tempo, o qual adota rotas elaboradas no

dia anterior à entrega, não levando em consideração mudanças que ocorrem ao longo do dia. Este artigo é

resultado de uma monografia final de graduação em Transportes e Logística.

ABSTRACT

The proliferation of sales in e-commerce represents a new business area for distribution companies and logistics

operators. The distribution inherent to this business is characterized by a high frequency of small deliveries

dispersed in a given region. This creates problems concerning the definition of routes, given the time windows

set for customer deliveries. This paper will approach the theory concerning vehicle routing problems with time

windows as well as their resolution using a commercial software, TransCAD. The goal is to solve the

distribution problem of a delivery transportation company that works with e-commerce products. For that matter,

we will recur to a static routing model with time windows where no changes are allowed during the operation

period. This paper is the result of a graduation conclusion work in Transportation and Logistics.

1. INTRODUÇÃO

Os grandes aglomerados urbanos brasileiros são palco de congestionamentos cada vez

maiores devido aos milhões de veículos que circulam pelas ruas e estradas do país. Esse

aumento do número de veículos nos grandes centros tem consequências muito mais graves do

que os atrasos e transtornos enfrentados diariamente pelos motoristas. Os congestionamentos

custam muito dinheiro, prejudicam a saúde da população e atrapalham o crescimento do país.

Portanto, resolver (ou minimizar) o problema não é apenas uma questão de conforto e bem

estar, mas acima de tudo um importante incentivo ao desenvolvimento econômico e social.

Um dos maiores impactos negativos para os custos logísticos é a ociosidade dos caminhões

retidos no trânsito Os caminhões retidos nos engarrafamentos implicam um custo maior

porque gastam mais, rodam menos e fazem, portanto, menos entregas. Como esses caminhões

cumprem menos ciclos de entrega, as empresas de distribuição precisam aumentar a frota ou

subcontratar serviços de entrega adicionais para atender seus clientes e, com isso, colocam

ainda mais veículos nas ruas. O planejamento de rotas nestas circunstâncias torna-se uma

tarefa árdua, com consequências no nível de serviço oferecido, isto é, no cumprimento dos

horários previamente agendados com os clientes.

O desafio de encontrar um conjunto de rotas iniciando e terminando no depósito, cumprindo a

demanda e minimizando o custo total é denominado problema de roteirização de veículos

(VRP). Esses problemas têm recebido muita atenção na literatura em função de sua

aplicabilidade e importância econômica na determinação de estratégias eficientes de

distribuição, com o objetivo de reduzir os custos operacionais no sistema de distribuição.

Vários modelos de roteirização foram desenvolvidos a partir dos trabalhos de Clarke e Wright

(1964), e com eles diversos softwares de roteirização. Alguns dos softwares disponibilizados

no mercado não atendem às necessidades das empresas usuárias devido às especificidades de

seus clientes e às suas próprias políticas de distribuição. Identificar inadequações do software

após tê-lo adquirido resulta em prejuízos consideráveis, tanto de recursos financeiros, como

humanos, sem considerar as expectativas criadas que não são atendidas.

Este artigo discute o problema de roteirização de veículos com janelas de tempo de uma

empresa distribuidora de artigos de e-commerce e analisa as soluções fornecidas pela

utilização do software de roteirização TransCAD.

2. ROTEIRIZAÇÃO DE VEÍCULOS

O sistema de roteirização, ou roteamento, é caracterizado pela criação de rotas de coletas e/ou

entregas que partem de um ou vários depósitos para um certo número de clientes dispersos

geograficamente de forma a otimizar uma determinada função objetivo (Laporte, 1992). De

acordo com Da Cunha (2000), o termo, em geral, pode ser utilizado para os mais diversos

fins, como criação de um ou mais roteiros com sequências de paradas para entregas, e com

um ou mais depósitos para abastecimento de cargas. Os pontos a serem visitados pelos

veículos estão separados geograficamente e deverão ser visitados em uma sequência

determinada a priori através de uma rota criada a partir do processo de roteirização.

O objetivo do problema de roteirização de veículos é definido por um “custo mínimo”, o qual

pode ser definido através da minimização do custo, risco, tempo e/ou distância, entre outras

características resultantes do atendimento total de uma rota. Cada cliente é visitado, no

máximo, uma vez e o veículo inicia e finaliza o trajeto em um determinado ponto,

considerado como o depósito de cargas e/ou base dos veículos.

Existem diversas definições do problema de roteirização com base nas restrições, variáveis e

características específicas de cada problema. De acordo com Oliveira da Silva (2007), para

cada caso, um tipo de algoritmo, seja exato, heurístico ou metaheurístico, será escolhido para

encontrar a solução do problema As principais restrições, variáveis e características podem

estar relacionadas com qualquer elemento da rota, a saber (Oliveira da Silva, 2007):

Restrições: Limite da capacidade dos veículos; Quantidade de veículos disponíveis; Janela de

tempo dos clientes; Tempo máximo permitido de viagem de um veículo; Limitações legais de

circulação de veículos de carga.

Variáveis: Roteiro a ser definido; Tipo de demanda de cada cliente; Tempo inicial e final para

atendimento ao primeiro e último cliente da rota, respectivamente.

Características: Tipo de operação (coleta e entrega separadamente ou simultaneamente); Tipo

de demanda (determinística ou estocástica); Localização da demanda (arcos e/ou nós); Tipo

da frota (homogênea ou heterogênea); Quantidade de depósitos; Estrutura da rede

(direcionada, não direcionada, mista, ou euclidiana).

A existência de um grande número de artigos publicados na literatura especializada ao longo

dos anos, os quais citam algoritmos que buscam resolver os problemas de roteirização,

evidencia a importância da história da roteirização de veículos. Entre os problemas de

roteirização existentes, neste artigo serão citados apenas os problemas de roteirização

estáticos, os quais buscam formar rotas a partir de informações previamente estabelecidas.

Os problemas estudados neste artigo, de uma forma mais ampla, e que irão contribuir para o

estudo de caso mostrado no capítulo 6 são: o Problema do Caixeiro Viajante (TSP -

Travelling Salesman Problem), Problema de Roteirização de Veículos (VRP – Vehicle

Routing Problem) e Problema de Roteirização de Veículos com Janela de Tempo (VRPTW –

Vehicle Routing Problem With Time Windows).

3. PROBLEMA DO CAIXEIRO VIAJANTE

Até aos dias de hoje, a origem do TSP continua incerta. Held e Karp (1971) dizem que o TSP

provém do jogo desenvolvido por William Rowan Hamilton na década de 1800, onde o

objetivo era encontrar um ciclo hamiltoniano, i.e., caminho de um grafo iniciando-se e

terminando-se no mesmo vértice e em que todos os vértices são visitados uma única vez. Já

segundo Gaglani (2012), primeiramente, o problema foi formulado matematicamente por Karl

Menger na década de 30, e só foi popularizado posteriormente, no ano de 1994, quando o seu

livro a respeito da formulação matemática TSP foi publicado.

O TSP foi o primeiro problema de roteirização a ser estudado pelos matemáticos (Da Cunha,

2000). Applegate et al. (2007) definem TSP como o problema de encontrar a forma mais

eficiente de visitar um conjunto de cidades e no final retornar ao ponto de partida, em que a

função de impedância é dada pela distância entre cada par de cidades. A solução ótima será o

caminho em que a ordem das cidades visitadas resulta no menor custo total de viagem, sendo

que cada cidade só pode ser visitada uma única vez.

A assimilação da definição do modelo do TSP é bastante acessível, sendo este um dos

principais motivos da sua popularidade. Apesar da sua simplicidade o TSP continua a ser um

dos problemas mais investigados na matemática computacional. Com o aumento da

complexidade logística presente na distribuição física, diversas restrições foram e estão sendo

incorporadas ao TSP, de modo a melhor representar os diferentes problemas envolvendo

roteiro de pessoas, veículos e cargas. E com isso, surgem novos problemas de roteirização,

como o chamado Vehicle Routing Problem (VRP), ou Problema de Roteirização de Veículos.

A principal diferença entre o VRP e o TSP é a quantidade de veículos utilizados na

roteirização. No VRP são utilizados múltiplos veículos enquanto no TSP é utilizado apenas

um. De acordo com Da Cunha (2000), os problemas de roteirização de veículos são,

normalmente, definidos como “problemas de múltiplos caixeiros viajantes com restrições

adicionais de capacidade, além de outras que dependem de cada aplicação”.

4. PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS

O desafio de criar rotas onde os veículos devem realizar visitas em pontos específicos é um

problema logístico denominado problema de roteirização de veículos (VRP). O VRP pode ser

definido, como um problema de distribuição que busca o conjunto de rotas que atendem um

dado conjunto de clientes, minimizando o custo total de viagem, a distância total percorrida e

o número de veículos. A distribuição é feita a partir de um depósito central, utilizando uma

frota de veículos com capacidades limitadas que devem passar pelos clientes, satisfazendo

integralmente suas demandas, e retornar ao depósito. A demanda é determinística, ou seja,

cada nó é atendido uma única vez, por um único veículo, e cada veículo possui capacidade

limitada (Belfiore e Fávero, 2006).

Segundo Laporte (2007), “O VRP foi introduzido há cerca de 50 anos por Dantzig e Ramser e

desde então tem dado origem a um farto conjunto de pesquisa” de modo a incorporar

características dos problemas de redes de distribuição complexas. O primeiro trabalho que

abrangia a modelagem de problemas de roteirização e programação de veículos foi

apresentado por Bodin et al. (1983). Posteriormente, Golden e Assad (1988) e Ronen (1988)

também trataram de aspectos relacionados à classificação dos diferentes tipos de problemas

de roteirização (Da Cunha e Gualda, 1997). Nos últimos anos, esse problema tem recebido

muita atenção em função de sua aplicabilidade e importância econômica na determinação de

estratégias eficientes com o objetivo de reduzir os custos operacionais de distribuição.

Segundo Laporte (2007), ao contrário do que acontece com os problemas conhecidos de

otimização combinatória, não existe uma definição universalmente aceita para o VRP devido

à variedade de restrições encontradas na prática. A maioria das pesquisas concentra seus

esforços numa versão padronizada do problema, conhecida como VRP clássico, com a ciência

de que muitos dos algoritmos desenvolvidos para esse caso, em sua maior parte heurísticos,

possam ser adaptados para situações reais de maior complexidade.

O VRP clássico é definido a partir de um grafo não direcionado (pares não ordenados de

vértices) G = (V, A), onde V = {0, 1, ..., n} é o conjunto de vértices e A = {(i, j) : i, j𝜖 V, i ≠

j} é o conjunto de arcos. O vértice 0 representa um depósito em que são localizados, no

máximo, m veículos idênticos de capacidade Qk. Cada cliente i 𝜖 V\ {0} é associado a uma

demanda não negativa qi ≤ Qk. A matriz de custos cij é definida no conjunto de arco A.

Quando a matriz de custos é simétrica, isto é, cij = cji para todo i, j, é comum definir o

problema num grafo não direcionado G = (V, E), onde E = {[i, j]: i, j 𝜖 V, i < j} é o conjunto

de arestas. O problema consiste na determinação do conjunto de m rotas de veículos que

começam e terminam no mesmo depósito. Cada cliente é visitado por exatamente um veículo,

a demanda total de cada rota não excede a capacidade Qk e o custo total de rota é minimizado.

4.1. Métodos de soluções

Dada a complexidade dos problemas de roteirização de veículos, foram desenvolvidos

métodos de solução baseados em procedimentos heurísticos, ou seja, métodos que não

asseguram a obtenção de soluções ótimas. Muitas heurísticas baseiam-se em algoritmos

gulosos (greedy) para obter rapidamente uma solução inicial viável, complementadas por um

algoritmo de melhoria baseado em trocas ou em busca na vizinhança (Da Cunha, 2006).

Em geral, as estratégias de soluções heurísticas apoiam-se em abordagens intuitivas, nas quais

a estrutura particular do problema pode ser considerada e explorada de forma inteligente, a

fim de se obter uma solução satisfatória, e considerando-se o compromisso qualidade versus

esforço computacional. As heurísticas clássicas do VRP são divididas em heurísticas

construtivas e heurísticas de melhoria. As heurísticas construtivas são aquelas em que uma ou

mais soluções são construídas elemento a elemento e seguindo algum critério heurístico de

otimização, até que se tenha uma solução viável. As heurísticas de melhoria partem de uma

solução inicial viável e tentam melhorar esta solução através de operações de troca, remoção

ou inserção, até que não seja mais possível a melhoria ou algum outro critério de parada seja

satisfeito. Uma heurística construtiva clássica para resolução do VRP é o algoritmo de Clarke

e Wright (1964) (Laporte, 2000).

4.1.1. Heurística de Clarke e Wright

Segundo Miura (2008), o algoritmo de Clarke e Wright é um método heurístico do tipo saving

(economia) que busca substituir arcos com maior custo dentro da rota por arcos de menor

custo, de forma a criar uma rota melhorada. A utilização deste algoritmo em problemas com

um número limitado de restrições pode resultar em soluções próximas a 2% em relação à

solução ótima. Por outro lado, “ele é flexível o suficiente para lidar com uma larga gama de

restrições e relativamente rápido para problemas com um número moderado de paradas”

(Miura, 2008). O método de Clarke e Wright não é o mais preciso, mas é o mais rápido e

simples de se implementar (Laporte, 2000).

5. PROBLEMA DE ROTEIRIZAÇÃO DE VEÍCULOS COM JANELAS DE TEMPO

O VRPTW é uma extensão do problema de roteirização de veículos em que os clientes devem

ser atendidos a partir de um depósito central dentro de um determinado intervalo de tempo. A

função objetivo do VRPTW conjuga a minimização do número de veículos com a

minimização da distância total de viagem (Gehring e Homberger, 1999). As informações

referentes aos clientes (demanda e janelas de atendimento) são conhecidas à priori e não

sofrem alterações durante o percurso. Caso contrário, o problema de roteirização seria

classificado como dinâmico (Oliveira da Silva, 2007).

Solomon (1987) propôs e avaliou diferentes heurísticas para problemas de roteirização com

janelas de tempo. O autor concluiu que as heurísticas de inserção sequencial apresentavam um

bom desempenho e seus resultados até hoje são utilizados para comparação e avaliação de

heurísticas desenvolvidas para essa mesma finalidade. Revisões sobre problemas de

roteirização de veículos com janelas de tempo podem ser encontradas nos trabalhos de

Solomon e Desrosiers (1988), Laporte (1992) e Desrosiers et al. (1995) e Cunha (1997)

(Cunha e Gualda, 1997).

5.1. Métodos de soluções

Os métodos de solução encontrados na literatura para problemas de roteirização de veículos

com janelas de tempo são classificados em três categorias: métodos exatos, métodos

heurísticos e métodos especializados (Belfiore e Fávero, 2006). Este último é considerado um

método heurístico que reúne técnicas mais recentes e avançadas, como as metaheurísticas

busca tabu, algoritmos genéticos, simulated annealing, etc (Da Cunha, 1997).

Os métodos exatos têm a vantagem de garantir a solução ótima do problema, porém ao custo

de um grande tempo de execução, e um elevado esforço computacional (Ranito, 2009).

Encontrar a solução ótima dos algoritmos de tempo polinomial só é possível com a resolução

de problemas de pequeno porte, os quais não refletem a realidade e, por isso, pouca atenção

tem sido dada à busca dessas soluções.

Os métodos heurísticos não garantem a solução ótima, mas geralmente resultam em soluções

de alta qualidade junto de um esforço computacional aceitável (Belfiore e Fávero, 2006).

Revisões sobre métodos heurísticos utilizados para resolver problemas de roteirização de

veículos podem ser encontradas nos trabalhos de Solomon e Desrosiers (1988), Laporte

(1992) e Desrosiers et al. (1995), Da Cunha (1997) e Da Cunha e Gualda (1997).

6. ESTUDO DE CASO

A Frilog, uma empresa do ramo da distribuição, tem vindo a dedicar-se cada vez mais à

distribuição de produtos com origem no e-commerce. O mercado virtual apresenta-se hoje

como uma aposta em franco crescimento que coloca novos desafios à logística de

distribuição. A elevada frequência de entregas, baixo volume/peso e a dispersão geográfica

dos clientes, aliado às necessidades crescentes de elevar os níveis de serviço prestados aos

clientes, tornam as decisões de roteirização cada vez mais complexas. O estudo de caso

aborda assim a procura das novas soluções de roteirização para o emergente mercado de

distribuição de produtos de e-commerce pela empresa Frilog.

De acordo com a consultoria e-bit, especializada em informações de comércio eletrônico,

98% das reclamações dos consumidores de lojas virtuais referem-se a atrasos da entrega da

mercadoria. A capacidade de distribuição com cumprimento dos prazos de entrega é por isso

um diferencial competitivo de destaque. Este fato ressalta a importância do estudo de caso, o

qual busca a melhoria da roteirização de veículos na empresa.

6.1. Caracterização da empresa

A Frilog é uma empresa do ramo de transporte rodoviário de cargas, fundada no ano de 2004

com matriz localizada na cidade de Nova Friburgo e nove filiais espalhadas pelos estados do

Rio de Janeiro e São Paulo. O principal foco da distribuição é no estado do Rio de Janeiro.

A filial da Frilog no Rio de Janeiro (RJO) apresenta atualmente uma percentagem de acurácia

de entregas realizadas baixa, 66% (Tabela 1). Por esse motivo foi escolhida como estudo de

caso. A filial RJO é responsável por, aproximadamente, 70 % de toda a distribuição do estado.

Filial NFs Agendamento % Agendamento Fora Agenda % Fora Agenda % Acurácia

Teresópolis 46 12 26% 2 4% 96%

Barra Mansa 328 0 0% 0 0% 100%

Itaperuna 73 13 18% 0 0% 100%

Itaboraí 94 40 43% 2 2% 98%

Nova Friburgo 146 44 30% 10 7% 93%

Rio de Janeiro 2.780 2.613 94% 934 34% 66%

São Pedro da Aldeia 207 124 60% 4 2% 98%

As principais causas da falta de acurácia na filial do Rio de Janeiro podem ser divididas em

duas categorias: responsabilidade da Frilog e causas não controláveis. A primeira categoria

abrange “não entregas” por falta de tempo hábil, erro operacional e/ou quebra de veículo. Já a

segunda categoria consiste em problemas na entrega que podem estar relacionados com

cliente ausente, endereço não localizado e problemas com pedido. A falta de tempo hábil para

entrega pode ser resultante de um fator externo, como performance da equipe de entrega,

trânsito, obras e demais particularidades que aumentam o congestionamento na cidade, ou por

falta de planejamento de roteirização com janelas de tempo para cada entrega. O objetivo

deste trabalho é recorrer a modelos de roteirização estáticos com janelas de tempo para

diminuir a quantidade de entregas não realizadas por falta de tempo hábil.

A Frilog cumpre a Lei Estadual 3.669, de 10 de outubro de 2001, que estabelece que

fornecedores de bens e serviços localizados no estado do Rio de Janeiro têm a obrigação de

fixar data e hora, no ato da compra, para a entrega dos produtos comercializados via mercado

Tabela 1: Tabela do desempenho das filiais da Frilog em Janeiro de 2014

virtual (ALERJ, 2001). A empresa realiza este agendamento de entregas de mercadorias

manualmente e diariamente, via telefone ou via mensagem de texto de celular, sendo que

neste último caso, não há confirmação do cliente. A partir das notas fiscais das mercadorias

agendadas, a roteirização da empresa é feita por um funcionário, que com base na sua

experiência no ramo separa as notas fiscais a serem entregues por bairro e por horário de

agendamento. Dependendo da rota criada para o dia, o principal critério a ser seguido deve ser

a entrega das cargas de maior valor em primeiro lugar. O agendamento empírico utilizado

pela Frilog é eficaz para as pequenas filiais. A Tabela 1 mostra que as filiais pequenas (todas

com exceção da filial RJO) apresentam acurácia perto dos 100%. No entanto é insatisfatório

para as grandes filiais como é o caso da RJO que apresenta apenas 66% de acurácia.

6.2. Coleta de Dados e Geração de Cenários

Os dados do problema foram cedidos pela empresa que teve como base 510 produtos e-

commerce entregues em um dia escolhido aleatoriamente do mês de Janeiro de 2014, as quais

totalizavam um peso de 90.788 kg. As informações coletadas incluem endereço e coordenada

do depósito e dos clientes a serem visitados; quantidade, peso (kg), tempo de serviço (min),

tempo unitário (min), horário de início do atendimento e horário limite para atendimento de

cada uma das 510 entregas; horário de abertura e fechamento do depósito; tipo, capacidade,

quantidade, custo e velocidade média da frota de veículos utilizados nas entregas.

Foram considerados dois cenários para a roteirização das entregas de e-commerce com base

na consideração de restrições de circulação automóvel em determinados horários e com base

na velocidade média de circulação dos veículos. Os dois cenários são os seguintes:

CENÁRIO 1: considera o Decreto Nº 37784, de 10 de Outubro de 2013, que proíbe a

circulação de veículos de carga e operação de carga e descarga em determinadas

regiões da cidade do Rio de Janeiro, nos períodos compreendidos entre 6:00 às 10:00 e

17:00 às 21:00 (SMA, 2013). Neste caso, as janelas de tempo de atendimento dos

clientes localizados nas regiões de restrição foram modificadas para o horário de 10:00

às 17:00. A velocidade média dos veículos considerada é 30 Km/h.

CENÁRIO 2: igual ao cenário 1 mas assumindo uma velocidade média dos veículos

igual a 20 Km/h. Este cenário pretende representar os elevados índices de

congestionamento observados na cidade do Rio de Janeiro durante os dias de semana.

A Figura 1 representa um mapa com a rede rodoviária, o depósito (representado pelo

asterisco), e os clientes. Os clientes que se encontram na zona de restrição estão representados

a de cor preta e os clientes que estão localizados fora desta zona são os de cor cinza.

Os dois cenários assumem que o período de atividade do depósito é das 6:00 às 22:00 e que

todos os roteiros têm origem e término no depósito (único depósito da Frilog existente na

cidade do Rio de Janeiro).

A rede rodoviária utilizada no estudo de caso corresponde à rede real existente. Para tal

recorreu-se a shapefiles com a rede rodoviária do Rio Janeiro que constam do Plano Diretor

de Transportes Urbanos de 2011 (PDTU 2011). Desta forma, as distâncias de rede e tempos

de viagem utilizados baseiam-se na estrutura rodoviária real do Rio de Janeiro.

Figura 1: Mapa da rede rodoviária com depósito e pontos de entrega

6.3.Metodologia de Resolução - TransCAD

O estudo de caso foi resolvido com recurso ao software TransCAD desenvolvido por Caliper

Corporation (Caliper, 2014). O TransCAD é um Sistema de Informação Geográfica (SIG)

utilizado para o planejamento de transportes que permite armazenar, exibir, gerenciar e

analisar dados de transporte ao combinar um SIG com uma plataforma de Sistema de

Informação Geográfica para Transportes (SIG-T). Este software tem a capacidade de integrar

totalmente o SIG com modelagem de demanda e funcionalidade logística. Entre outras, o

TransCAD possui uma ferramenta de roteirização estática com janelas de tempo.

Segundo Melo (2000), o TransCAD escolhe a ferramenta de resolução do problema de

roteirização com base nas especificações do problema. No caso de roteirização de nós com

janelas de tempo a heurística utilizada é a de Clarke e Wright (Paula, 2009).

Entre as ferramentas existentes no TransCAD, utilizamos o módulo Vehicle Routing da guia

Routing/Logistics. Esta ferramenta permite obter as rotas para cada veículo com suas

respectivas entregas, discriminadas pelo tipo (e capacidade) de veículo, horário de início e

final para o atendimento de cada cliente da rota, e horário inicial e final da rota, distância

percorrida em cada entrega e distância total da rota.

6.4. Resultados

Foram testados os dois cenários, tendo o tempo de processamento máximo do software sido

sempre inferior a 9,725 segundos. Os resultados obtidos para os dois cenários utilizando o

TransCAD estão exibidos na Tabela 2.

Tabela 2: Tabela comparativa dos cenários

Cenário

Número de

veículos

utilizados (rotas)

Número de

clientes não

atendidos

Tempo total

(hora)

Distância total

percorrida (km)

Demanda total

atendida (kg)

1 23 0 223,43 1.842,90 90.788,00

2 25 2 248,47 1.829,40 80.661,90

Das 510 entregas, 39,41% estão localizadas nas regiões que fazem parte da restrição do

Decreto Nº 37784 cumprido por toda a frota da Frilog. Vale destacar que as rotas traçadas

respeitam os horários de restrição de circulação dos veículos nas áreas específicas. Esse fato é

visível no horário de atendimento do primeiro ponto da rota, que geralmente se inicia às 8:00.

No caso de rotas que começam com pontos situados em áreas restritas, as rotas iniciam-se

mais tarde para atender as janelas de tempo dos pontos restritos.

Comparando os cenários 1 e 2 há duas conclusões imediatas. Primeiro, em virtude de

considerar uma velocidade de circulação maior, o tempo total de circulação do cenário 1 é

inferior ao do cenário 2. Segundo, no cenário 2 há dois clientes que não são visitados.

Curiosamente estes clientes são os dois maiores clientes da Frilog para o dia em análise.

Sendo a frota da empresa composta por 56 veículos, e tendo sido alocados apenas 25 veículos

no cenário 2, entende-se que o TransCAD prioriza a maximização da capacidade de cada

veículo ao invés da realização de 100% das entregas. Uma possível justificativa para essa

priorização é a criação de rotas visando a menor ociosidade dos veículos.

Tabela 3: Tabela resumo dos resultados do Cenário 2

Rota

Número de

entregas

realizadas

Capacidade

do caminhão

(kg)

Capacidade

utilizada

(kg)

Capacida

de usada

(%)

Horário de

início do

atendimento

Horário final

de

atendimento

Tempo

total

(hora)

Distância total

percorrida

(Km)

1 17 3.500 2.243,60 64,10% 08:35 17:03 13,12 159,1

2 18 1.800 1.671,20 92,84% 08:00 17:06 12,67 156,5

3 15 6.000 3.793,10 63,22% 08:00 16:48 11,93 108,5

4 28 3.500 2.167,40 61,93% 08:00 17:08 12,32 116,4

5 19 3.500 2.993,00 85,51% 08:00 17:19 11,13 95,9

6 24 3.500 2.242,00 64,06% 08:00 17:11 12,05 110,8

7 17 6.000 3.899,90 65,00% 08:15 16:59 10,28 82,2

8 30 3.500 1.898,50 54,24% 08:47 17:05 11,08 88,5

9 25 3.500 3.116,20 89,03% 08:00 17:14 11,03 77,4

10 27 3.500 3.492,20 99,78% 08:11 17:48 11,18 76,9

11 30 3.500 2.987,90 85,37% 08:03 17:31 11,57 74,8

12 24 6.000 3.776,40 62,94% 08:11 16:57 10,42 61,7

13 20 6.000 4.200,40 70,01% 08:01 17:19 10,62 59,1

14 21 6.000 3.417,30 56,96% 08:00 16:36 09,43 52,0

15 23 3.500 2.627,90 75,08% 08:00 17:10 10,42 71,5

16 24 12.000 4.783,80 39,87% 08:27 17:09 09,93 55,2

17 21 3.500 3.365,90 96,17% 08:00 17:08 10,07 64,7

18 24 3.500 2.857,50 81,64% 08:03 17:01 09,55 50,9

19 20 12.000 4.280,30 35,67% 08:00 17:05 10,18 56,9

20 20 12.000 4.504,70 37,54% 08:00 17:28 10,12 48,9

21 20 12.000 8.524,60 71,04% 08:00 17:00 09,52 40,3

22 19 3.500 3.172,00 90,63% 08:00 16:34 09,35 63,8

23 20 12.000 2.865,40 23,88% 08:00 16:03 08,52 43,7

24 1 3.500 123,00 3,51% 10:00 10:20 00,65 6,3

25 1 1.800 1.657,60 92,09% 10:00 11:00 01,37 7,4

A Tabela 3 apresenta os resultados gerados pelo TransCAD para o cenário 2. Analisando as

rotas propostas para o cenário 2, constata-se que é possível melhorar o resultado obtido

incluindo as entregas não realizadas nos roteiros criados. Na rota 23, a capacidade do veículo

é muito maior do que a capacidade da demanda, sendo estes respectivamente 12.000 kg e

2.865,4 kg. Sendo assim, esta rota poderia ser realizada pelo veículo de capacidade 3.500 kg,

já que a frota dispõe de 27 veículos com esta capacidade e apenas 13 foram utilizados neste

cenário. Com isso, as duas entregas não realizadas, com tempo de serviço de 150 min cada e

que somam 10.126,13 kg, podem ser alocadas nesse veículo de 12.000 kg de capacidade. E

esta seria a 26ª rota deste cenário, que atenderia, então, a todas as entregas. Dessas duas

entregas, apenas uma está localizada na área de restrição, com isso o veículo deve realizar a

entrega fora da área de restrição às 8:00 e terminaria o atendimento deste cliente às 10:30.

Considerando que a rota percorrida entre essas duas localidades é de 5 Km e que a velocidade

média do veículo é de 20 Km/h, este percurso tem a duração de 15 min. Então o veículo

chegaria no segundo ponto às 10:45 e terminaria o atendimento às 13:15, retornando ao

depósito antes do horário de término das atividades.

Outra possível alocação das entregas não realizadas no cenário 2 seria a utilização do veículo

da rota 23 na rota 24 e vice-versa, visto que as taxas de utilização dessas rotas são

respectivamente 23,88% e 3,51% (Tabela 3). Sendo assim, os clientes não atendidos seriam

alocados na rota 24, já que os clientes e o depósito estão geograficamente próximos. Logo, o

veículo de capacidade de 12.000 kg atenderia o primeiro cliente às 10:00 e o último cliente às

13:29, sendo este o único fora da zona de restrição. Com isso, as taxas de utilização das rotas

23 e 24 aumentariam para 82% e 85%, como pode ser visto na Tabela 4. As entregas não

realizadas poderiam também ser alocadas separadamente nas rotas 16, 19, 20 ou 23. Todavia,

essas rotas não possuem tempo hábil para essa possível alocação devido às restritas janelas de

tempo e aos tempos de serviço dessas duas entregas, que somam 300 minutos.

Além da alocação dos clientes não visitados no cenário 2, outras alterações podem ser

consideradas como proposta de melhoria do resultado apresentado pelo TransCAD, visando

as baixas porcentagens da taxa de utilização apresentadas nas rotas 14, 16, 19 e 20. Na rota 14

deveria ser utilizado um veículo de capacidade de 3.500 kg, no lugar do de 6.000 kg, o que

libertaria o veículo de capacidade de 6.000 kg para ser utilizado na rota 16 ao invés do de

12.000 kg. Nas rotas 19 e 20 o ideal seria utilizar veículos de capacidade de 6.000 kg, porém

não há mais veículos com esta capacidade disponíveis na frota. Todas estas propostas de

melhoria podem ser observadas na Tabela 4.

Tabela 4: Tabela com propostas de melhoria para o Cenário 2

Rota

Número de

entregas

realizadas

Capacidade

do caminhão

(kg)

Capacidad

e utilizada

(kg)

Capacidad

e usada

(%)

Horário

inicial de

atendiment

o

Horário

final de

atendiment

o

Temp

o total

(hora)

Distância total

percorrida

(km)

14 21 3500 3.417,3 98% 8:00 16:36 9,4 52,0

16 24 6000 4.783,8 80% 8:27 17:09 9,9 55,2

19 20 12000 4.280,3 36% 8:00 17:05 10,2 56,9

20 20 12000 4.504,7 38% 8:00 17:28 10,1 48,9

23 20 3500 2.865,4 82% 8:00 16:03 8,5 43,7

24 3 12000 10.249,1 85% 10:00 10:20 0,7 6,3

Apesar do TransCAD apresentar resultados satisfatórios, há que destacar alguns pontos

negativos:

Primeiro, ao realizar testes nas rotas inseridas no software nota-se que o mesmo não considera

os custos relativos aos veículos, já que os resultados apresentados para os dados de entrada

com e sem custos foram os mesmos. Este fato não condiz com a realidade pois o uso de

diferentes veículos na rota pode impactar na rentabilidade da empresa.

O segundo ponto relevante é a definição das janelas de tempo. Os dados reais da Frilog

contemplam intervalos de tempo específicos entre os clientes, visto que estes podem escolher

o horário de entrega da sua mercadoria. Ao inserir estes dados no software, obtivemos

resultados incoerentes e sem justificação.

Outra questão que pode ser observada negativamente na apresentação dos resultados do

TransCAD para os dois cenários é o não cumprimento integral do horário limite de circulação

em zonas restritas. Verifica-se que a chegada ao último cliente de cada rota ocorre antes das

17:00. No entanto, em 5 das 25 rotas de entrega os veículos deixam o último cliente depois

das 17:00. Com isso, conclui-se que o software considera a restrição da janela de tempo por

hora de chegada e não tempo total de atendimento dos clientes.

Uma última nota diz respeito à existência de obras de construção e melhoria das vias, eventos

pontuais, interdições e regiões de risco existentes na rede rodoviária utilizada. Todos estes

aspetos não foram tidos em consideração na formulação, o que pode adulterar os resultados. A

inclusão destes dados teria de ser feita no TransCAD através da alteração da rede rodoviária

utilizada. Com relação às regiões de risco, relata-se a possibilidade de roubo da carga. A

política atual da empresa consiste em deixar essas regiões para o final das rotas.

7. CONCLUSÃO

Neste artigo foram revisados os principais problemas de roteirização e algoritmos de

resolução, com particular destaque para os problemas de roteirização de veículos com janelas

de tempo, tendo em vista a resolução do estudo de caso. O estudo de caso trata da distribuição

de entregas de e-commerce na cidade do Rio de Janeiro. Para tal, utilizou-se o software

TransCAD. Todos os conceitos e estudos pesquisados na literatura visaram compreender a

lógica básica de configuração e funcionamento da rede de trabalho do TransCAD.

Apesar do TransCAD não analisar fatores como condições de tráfego, disposição de carga no

veículo, variação da velocidade média do veículo ao longo do percurso, entre outros, sabe-se

que os resultados são aproximados, mas servem como orientação para a operação da atividade

de distribuição de mercadorias. Comparando a maneira atual que a roteirização é feita na

Frilog e a gerada pelo TransCAD, pode-se notar que a porcentagem de acurácia aumenta

significativamente. Sendo assim, um investimento neste software contribuiria para um

aumento no nível de serviço da empresa. Mas vale ressaltar que o usuário ideal deste software

deveria ter um conhecimento considerável de roteirização e logística do local a ser estudado,

já que em alguns testes realizados foram encontrados resultados incoerentes, necessitando de

uma análise mais detalhada.

Os resultados deste trabalho visam contribuir para a distribuição das entregas de e-commerce,

visto ser uma área de comércio em expansão. Dessa forma, o resultado obtido com o software

comparado ao apresentado pela empresa reforça a recomendação da importância do uso de

ferramentas computacionais para otimizar os serviços de distribuição e entregas.

REFERÊNCIAS BIBLIOGRÁFICAS

APPLEGATE, D., L. e BIXBY, R. E. e CHVÁTAL, V. e COOK, W. J. (2007) The Traveling Salesman

Problem: A computational study. Princeton University Press, p. 1-59.

ASSEMBLÉIA LEGISLATIVA DO ESTADO DO RIO DE JANEIRO (ALERJ). Lei Nº 3669, de 10 de

Outubro de 2001. Disponível em <alerjln1.alerj.rj.gov.br/contlei.nsf/f25571cac4a61011032564

fe0052c89c/7d18a3115d659ef303256ae800672fd5?OpenDocument>. Acesso em 21 de Abril de 2014.

BELFIORE, P. P. e FÁVERO, L. P. L. (2006) Problema de roteirização de veículos com janelas de tempo:

revisão da literatura. XIII SIMPEP, São Paulo, p. 1 a 8.

BODIN, L. D. e GOLDEN, D. e ASSAD, A. e BALL, M. (1983) Routing and scheduling of vehicles and crews:

The state of the art. Computers and Operations Research, vol.10, n.2.

CALIPER CORPORATION. TransCAD Transportation Planning Software. Disponível em

<www.caliper.com/tcovu.htm#.U2uJnPldVqU>. Acesso em 01 Maio de 2014.

CLARKE, G. e WRIGHT, J. W. (1964) Scheduling of Vehicles from a Central Depot to a Number of Delivery

Points. Operations Research, v.12, p.568-581.

DA CUNHA, C. B. (1997) Uma contribuição para o problema de roteirização de veículos com restrições

operacionais. Tese de Doutorado em Engenharia de Transportes – EPUSP, 222p., São Paulo.

DA CUNHA, C. B. e GUALDA, N. D. F. (1997) Heurísticas baseadas em relaxação lagrangiana para o

problema de roteirização de veículos com restrições operacionais. EPUSP, Departamento de Engenharia de

Transporte, São Paulo, p. 2.

DA CUNHA, C. B. (2000) Aspectos Práticos da Aplicação de Modelos de Roteirização de Veículos a

Problemas Reais. Revista Transportes da ANPET – Associação Nacional de Pesquisa e Ensino em Transportes,

v.8, n.2, p.51-74.

DA CUNHA, C.B. (2006) Contribuição à Modelagem de Problemas em Logística e Transporte – Capítulo 5 –

Tese de Livre Docência em Logística e Sistemas de Transporte – Departamento de Engenharia de Transporte da

Universidade de São Paulo, São Paulo.

DESROSIERS, J. e DUMAS, Y. e SOLOMON, M. e SOUMIS F. (1995) Time constrained routing and

scheduling. Network Routing. In: Ball, M.; T.L.Magnanti; C.L.Monna e G.L.Nemhauser (eds.) Handbooks in

Operations. Research and Management Science. North Holland, Amsterdam, Países Baixos.

GAGLANI, M. S. (2012) A study on transportation problem, transshipment problem, assignment problem and

supply chain management. Saurashtra University.

GEHRING, H. e HOMBERGER, J. (1999) A parallel hybrid evolutionary metaheuristic for the vehicle routing

problem with time windows. University of Hagen, Proceedings of EUROGEN99. Vol. 2, p. 183-191.

HELD, M. e KARP, R. M. (1971) The traveling-salesman problem and minimum spanning trees: Part II,

Mathematical Programming, vol. 1, no. 1, pp. 6-25.

LAPORTE, G. (1992) The vehicle routing problem: An overview of exact and approximate

algorithms. European Journal of Operational Research, 59(3), p. 345-358.

LAPORTE, G. e GENDREAU, M. e POTVIN, J-Y. e SEMET, F. (2000) Classical and Modern Heuristics for

the Vehicle Routing Problem. Internacional Transactions in Operational Research, Oxford.

LAPORTE, G. (2007) What You Should Know about the Vehicle Routing Problem. Canada Research Chair in

Distribution Management, HEC Montréal 3000, Chemin de la Côte-Sainte-Catherine, Montreál, Canada H3T

2A7, p. 1-2.

MELO, A. C. S. (2000) Avaliação do Uso de Sistemas de Roteirização de Veículos. Dissertação de Mestrado em

Engenharia de Produção – Universidade Federal do Rio de Janeiro, Rio de Janeiro.

MIURA, M. Modelagem heurística no problema de distribuição de cargas fracionadas de cimento. Dissertação

(Mestrado em Engenharia de Sistemas Logísticos) - Escola Politécnica, Universidade de São Paulo, São Paulo,

2008. Disponível em: <http://www.teses.usp.br/teses/disponiveis/3/3148/tde-17112008-115017/>. Acesso em:

2014-04-02.

OLIVEIRA DA SILVA, R. C. (2007) Avaliação da implantação de softwares de roteirização de veículos.

Dissertação de Mestrado em Logística - Pontifícia Universidade Católica do Rio de Janeiro.

PAULA, M. A. A. F. (2009) Estudo de roteirização de veículos empregando o TransCAD: contribuição para a

distribuição urbana de cargas. Dissertação de Mestrado em Engenharia Civil – Universidade Federal de

Uberlândia, Minas Gerais.

RANITO, I. M. N. (2009) Optimização de rotas de veículos-um caso de estudo. Mestrado em Matemática e

Aplicações - Universidade de Aveiro.

RONEN, D. (1988) Perspectives on practical aspects of truck routing and scheduling. European Journal of

Operational Research, 35(2):137-145.

SECRETARIA MUNICIPAL DE ADMINISTRAÇÃO DO RIO DE JANEIRO (SMA-RJ). Decreto Nº 37784,

de 10 de Outubro de 2013. Disponível em < http://smaonline.rio.rj.gov.br/legis_consulta

/45194Dec%2037784_2013.pdf>. Acesso em 29 de Maio de 2014.

SOLOMON, M. M. (1987) Algorithm for the Vehicle Routing and Scheduling Problems with Time Windows

Constraints. Operations Research, v. 35, n. 2, p. 254-265.

SOLOMON, M. M. e DESROSIERS, J. (1988) Time window constrained routing and scheduling problems.

Transportation Science, 22(1): 1-13.

Gabriela R. Thedim (gabi_ruiz_thedim@hotmail.com)

Rafaela G. Ourofino (rafagouro@gmail.com)

Hugo M. Repolho (hugorepolho@puc-rio.br)