PROGRAMA DE ROTEAMENTO DE VEÍCULOS
APLICAÇÃO NO SISTEMA DE COLETA DOS CORREIOS
Glaydston Mattos Ribeiro
Instituto Militar de Engenharia – IME, Mestrado em Engenharia de Transportes.
Praça General Tibúrcio, 80 – DE/2. Praia Vermelha – Rio de Janeiro – RJ – CEP. 22.290-270.
Maria Dolores Villegas de Ruiz, MSc
Universidade Federal do Rio de Janeiro – UFRJ, Programa em Engenharia de Transportes-COPPE.
Cidade Universitária, Ilha do Fundão – Rio de Janeiro – RJ
Letícia Dexheimer, MSc
Instituto Militar de Engenharia – IME, Mestrado em Engenharia de Transportes.
Praça General Tibúrcio, 80 – DE/2. Praia Vermelha – Rio de Janeiro – RJ – CEP. 22.290-270
Abstract
This paper has the purpose to present a software to solve Vehicle Routing Scheduling
Problems using the Clarke & Wright Method. This software was made in Delphi 5.0 and it is
an improvement of another one developed by Novaes (1989). An application for the Brazilian
Mail Companies Logistical System Operations showed good results. Then we can conclude
that it is a low costs planning tool, easy to be used and suitable in small companies.
Key words: Logistics, Routing, Transportation
1. Introdução
Define-se logística como o planejamento, organização e controle de todas as operações de
movimento e estoque, relativas ao fluxo de mercadorias, desde o ponto de aquisição de
matéria-prima até o consumidor final, objetivando a máxima produtividade. Num entender
mais amplo, entretanto, suas atividades típicas são: transporte, gestão de estoques,
processamento de pedidos, compras, armazenagem, manuseio de materiais, embalagem e
programação da produção.
Em tempos de mercados competitivos e mais exigentes há uma busca por melhorias no
desempenho operacional das empresas oferecendo qualidade no atendimento ao cliente,
aproveitando ao máximo os recursos disponíveis de forma a minimizar os custos logísticos do
processo produtivo.
Em muitos casos, não são as vantagens tecnológicas ou mercadológicas que garantem o
sucesso da empresa, e sim o transporte, tanto de matéria-prima quanto de produtos acabados,
pois esta é a atividade logística mais importante representando, em média, de um a dois terços
do total dos custos envolvidos em todo o sistema (Ballou, 1993). A gerência do Transporte ou
Distribuição Física associa um conjunto de valores ao produto que, ao entregá-lo ao cliente no
lugar acertado, no momento e na quantidade acertada, sem danos e ao menor preço, garante a
qualidade do serviço e a melhoria nos ganhos da empresa, aumentando níveis de venda e
conquistando mercados.
Em face disto, surge a necessidade de otimização das rotas de um sistema de distribuição
física que consiste em transportar a carga desde o produtor até o consumidor, respeitando os
horários de entrega, que se encontram localizados em pontos geograficamente dispersos sobre
determinada região. Este tipo de problema é conhecido como Problema de Roteamento e
Programação de Veículos.
2. Objetivo
O objetivo deste trabalho é apresentar um Programa de Roteamento e Programação de
Veículos aperfeiçoado pelos autores e implementado em Delphi 5.0 utilizando a heurística de
ganhos, tendo como base o programa proposto por Novaes (1989). Para demonstrar a
utilização do mesmo, será feita uma aplicação específica no sistema de coleta da Empresa de
Correios e Telégrafos do Rio de Janeiro.
3. Problema de Roteamento de Veículos
Os problemas de roteamento de veículos de uma forma geral consistem em determinar
percursos ótimos para uma frota de veículos estacionada em um ou mais domicílios de forma
a atender um conjunto de clientes geograficamente dispersos. Um exemplo clássico aparece
nos problemas de distribuição/coleta de mercadorias, onde cada cliente possui uma demanda
específica e os veículos apresentam capacidade limitada. Busca-se a configuração das rotas
dos veículos de modo que cada cliente seja servido por um e somente um veículo,
minimizando-se o custo/comprimento do percurso total.
A este tipo de problema podem ser associadas uma série de restrições como:
- Restrições de unicidade: cada cliente só pode ser servido por um e somente um veículo;
-
Restrições de frota: cada veículo tem uma capacidade conhecida de carga, além disto o
número de veículos que compõe a frota pode ser conhecido a priori, tendo-se neste caso
que impor a condição adicional de que o número de rotas a ser gerado não pode
ultrapassar o número de veículos disponíveis;
-
Restrições de precedência: determinados clientes não podem ser visitados antes que outros
o sejam. (situação comum onde há entrega e coleta simultânea de mercadorias);
-
Restrições temporais: cada veículo só pode operar durante intervalos de tempo de duração
limitada, ou cada cliente só opera, para recebimento ou entrega de mercadoria, durante
uma faixa limitada de tempo;
Por outro lado, o problema pode ser generalizado de modo a levar em conta:
-
Múltiplos depósitos: existem vários depósitos, mas cada veículo está associado a um
depósito específico, ou os vários depósitos podem ser usados indistintamente por todos os
veículos;
-
Frota não homogênea: constituída de veículos com capacidades distintas ou diferenciados
por compartimentos especiais de armazenagem;
-
Demanda incerta dos clientes;
-
Múltiplos objetivos: por exemplo, além de minimizar o comprimento total percorrido
pelos veículos, quer se otimizar o custo total da frota, levando em conta o investimento na
frota de veículos próprios e o custo de usar veículos alugados. Pode-se supor que uma
parcela de clientes tenha maior relevância e não seja preciso visitar todos, mas somente
aqueles mais importantes.
4. Metodologia Utilizada
Diversos são os algoritmos heurísticos existentes para o Problema de Roteamento de
Veículos, neste trabalho optou-se pelo algoritmo de Clarke & Wright (1964) devido a sua
simplicidade e ao fato de fornecer bons resultados.
O método de Clarke e Wright (1964) baseia-se no conceito de “ganho” que pode ser obtido ao
se ligar dois nós de forma sucessiva em um roteiro.
Admitindo que existem n pontos a serem visitados (coleta ou entrega), partindo o veículo do
depósito D e retornando ao mesmo após um ciclo.
Suponhamos, inicialmente, que a solução preliminar do problema consiste em se ter n
veículos, sendo que cada veículo visita um único ponto e retorna ao depósito. Essa solução é a
pior.
O percurso total da frota para realizar esse tipo de serviço é dado por:
n
L = 2 × ∑ l d ,i
Onde, ld,i é à distância do ponto i até a origem d (depósito).
i =1
Supondo, agora que o veículo, ao atender o ponto i visita também o ponto j na mesma viagem.
Ou seja, obteve-se um “ganho” em termos de tempo dado por:
ld , j li , j
l
Ti , j = d ,i +
−
+ ti + t j Onde, Ti,j é o “ganho” obtido.
V
V
V
Na escolha de dois pontos i e j para constituir a seqüência de um roteiro, procura-se selecionar
o par com maior valor do ganho Ti,j. Há combinações, no entanto, que violam as restrições de
tempo, capacidade, etc, não sendo por isso factível. O método explora esse conceito, sendo
descrito a seguir:
1. Calcular os ganhos ei,j para todos os pares i, j (i ≠ j, i ≠ d e j ≠ d);
2. Ordenar os pares i, j na ordem decrescente dos valores do ganho Ti,j;
3. Começar pelo par i, j com maior ganho Ti,j e proceder na seqüência obtida em (2);
4. Para um par de nós i, j, correspondente ao Késimo elemento da seqüência (2) verificar se i e
j estão ou não incluídos em um roteiro já existente:
a) Se i e j não foram incluídos em nenhum dos roteiros já abertos, então criar um novo
roteiro com os nós i e j;
b) Se exatamente um dos pontos i ou j já pertence a um roteiro pré-estabelecido,
verificar se esse ponto é o primeiro ou último do roteiro (adjacente ao nó d,
depósito). Se isso ocorrer, acrescentar o arco i, j a esse roteiro. Caso contrário,
passar para a etapa seguinte, saltando o par i, j;
c) Se ambos os nós i e j já pertencem a dois roteiros pré-estabelecidos (roteiros
diferentes), verificar se ambos são extremos dos respectivos roteiros (adjacentes ao
nó d). Nesse caso fundir os dois roteiros em um só. Caso contrário, passar para a
etapa seguinte, pulando o par i, j;
d) Se ambos os nós i e j pertencem a um mesmo roteiro, pelar para a etapa seguinte;
e) Continuar o processo até que a lista completa de “ganhos” seja exaurida. Se sobrar
algum ponto não incluído, em nenhum roteiro, deverão ser formados roteiros
individualizados, ligando o depósito a cada ponto e retornando à base.
Com base no procedimento acima foi implementado em Delphi 5.0 um programa que,
baseado nas coordenadas geográficas dos pontos a serem visitado, na demanda desses,
capacidade do veículo, tempo de ciclo do veículo, tempo médio de parada para descarga em
cada ponto, velocidade média do veículo e no fator de correção da distância em relação à
distância Euclidiana, calcula os roteiros otimizados. Por distância Euclidiana, entende-se, à
distância em linha reta entre dois pontos.
5. Aplicação do Programa na Empresa de Correios e Telégrafos da Diretoria Regional
do Rio de Janeiro
Foi realizada uma visita aos Correios do Rio de Janeiro com a finalidade de analisar o sistema
operacional, concentrando-se nas tarefas de coleta e distribuição física de serviços postais.
Assim, é apresentado a seguir um resumo das atividades realizadas e seus responsáveis.
5.1. Distribuição e Coleta
O responsável por esta atividade é a Gerência de Operações, juntamente com as Regiões
Operacionais, responsáveis pelas unidades de distribuição. Sua atividade principal é a
entrega/coleta a domicílio dos objetos aos seus respectivos destinatários nos endereços
indicados pelos remetentes.
Dentre as ferramentas de Gestão, destaca-se o Sistema de Distritamento (SD), que
dimensiona o número ótimo de Carteiros e Distritos para atender a demanda de uma
determinada região, tomando como base o volume de objetos a ser distribuído, as
características físicas da região, a quantidade de pontos de entrega e o tempo disponível para a
execução da tarefa.
O sistema de distritamento esta sendo revisto e atualizado, inclusive com a inclusão de
Módulo de Geoprocessamento, permitindo o georeferenciamento dos pontos de entrega em
mapas da Região correspondente aos Centros de Distribuição.
O sistema de coleta dos Correios é constituído de três coletas diárias. Para cada uma dessas
coletas, são estimados, para cada ponto de coleta, a quantidade de correspondências. Essa
estimativa é feita em cima de um banco de dados e do comportamento da demanda naquele
dia. De posse desses dados, o Setor de Logística, com auxílio dos Sistema de Informações
Geográficas, faz a roteirização dos veículos para coleta das correspondências. Com isso são
estimados o número de veículos e as suas respectivas rotas de coleta. O grande problema é
que essa estimativa às vezes é falha o que obriga, muitas vezes, enviar um outro veículo para
coletar o excesso.
Existe, ainda, o Sistema de Gerenciamento Operacional - SGO, que tem como objetivo
principal facilitar o gerenciamento das Unidades de Distribuição, concentrando em um só
sistema todas informações inerentes à gestão administrativa e operacional da unidade.
5.2. Transporte
Tem como gestora a Gerência de Transportes, responsável pelas atividades de
encaminhamento aéreo e de superfície, em âmbito nacional e internacional .
A logística de transporte conta com as seguintes linhas:
RPN - Rede Postal Noturna - Linhas aéreas que transportam carga urgente e interligam as
capitais em todo o País;
LTN - Linhas Tronco Nacionais - Transportam, via superfície, cargas urgentes e não
urgentes para as Regionais de outros Estados;
LTR - Linhas Tronco Regionais - Transportam carga urgente e não urgente dentro do
próprio Estado;
LCE - Linhas de Coleta e Entrega - Linhas urbanas que interligam as unidades operacionais
da mesma cidade e, em alguns casos, são responsáveis também, pela entrega de objetos a
clientes;
LA - Linhas Auxiliares - Utilização de linhas de ônibus para transportar cargas em
localidades em que não se justifica a implantação de uma linha especial.
5.3. Aplicação
Para análise do sistema de coleta dos Correios foi utilizado o programa desenvolvido em
Delphi 5.0 que é baseado na heurística de ganhos (CLARKE e WRIGHT, 1964) com o
objetivo de obter, de forma otimizada, as melhores rotas respeitando limites de tempo de ciclo
e de capacidade do veículo e, ainda, atendendo aos horários de saída dos meios de transporte
que levarão a carga ao destino final. Para a utilização do programa são necessárias os
seguintes procedimentos:
ENTRADA DE DADOS:
•
•
•
•
•
•
•
Carga das UAs (kg);
Coordenadas das UAs (km);
Tempo de coleta nas UAs (min);
Capacidade do veículo (ton);
Velocidade média do veículo (km/h);
Tempo de ciclo (h);
Coef. de correção da distância;
• Coordenadas do depósito central (km).
•
•
•
•
•
•
•
CÁLCULOS:
Tempo de ciclo de cada rota;
Carga transportada em cada rota;
Distância total percorrida em cada rota.
RESULTADOS:
Tempo de ciclo de cada rota;
Carga transportada em cada rota;
Distância total percorrida em cada rota;
Mapa contendo as rotas calculadas.
O problema que foi proposto para a demonstração de utilização do programa apresentado é
hipotético, porém utiliza dados reais de forma que se aproxima ao máximo da realidade de
coleta dos postos de atendimento dos Correios.
Em uma zona urbana de coleta dos correios existem 30 unidades de atendimento que devem
ser visitadas por dia em um determinado período de tempo, cujas coordenadas e demais
informações são apresentadas no Quadro 1. O objetivo é determinar o(s) roteiro(s)
otimizado(s) para o(s) veículo(s) que atende(m) essa zona.
Dados:
•
Tempo de coleta (ver Quadro 5.1);
•
Capacidade do veículo: 12 ton;
•
Velocidade média dos veículos: 28km/h;
•
Tempo de ciclo: 3 h;
•
Coeficiente de correção da distância (coeficiente euclidiana): 1,35
•
Coordenadas do depósito: (0,0).
Ponto
Carga
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
550
750
860
500
900
1200
800
540
950
600
900
1000
860
1200
590
Coordenadas
X(Km) Y(Km)
4,5
9,5
9,0
8,65
6,0
6,52
8,0
-5,20
6,0
4,0
4,0
9,5
13,0
-6,0
3,7
-3,5
8,8
-8,5
5,0
5,9
6,0
7,5
8,5
8,0
3,5
-9,0
8,6
7,5
4,9
1,0
Tempo
(min)
5,0
12,0
15,0
14,6
17,0
9,0
10,0
8,0
3,5
5,9
8,7
9,8
7,0
8,5
6,4
Ponto
Carga
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
600
800
700
1000
500
590
600
780
800
900
500
750
800
390
600
Coordenadas
X(Km) Y(Km)
8,0
12,0
5,6
1,0
7,2
6,8
4,9
7,3
6,2
4,9
7,3
-8,9
7,2
4,1
-3,5
-6,8
4,9
3,6
6,3
-4,9
-6,5
-3,7
-4,8
5,6
7,6
-7,0
-9,0
-5,1
3,7
5,0
Tempo
(min)
19,0
15,6
17,0
8,9
14,0
17,6
15,2
4,3
4,6
7,6
6,4
8,5
11,4
14,6
10,0
Quadro 5.1: Dados para o exemplo de simulação do sistema de coleta dos Correios.
PROCESSAMENTO DE DADOS
Escolher a opção “Novo arquivo” e preencher os campos de acordo com os dados obtendo a
Figura 5.1.
Feito isso, selecionar a opção “Cálculos, Roteirizar”. O programa realizará o procedimento
de roteamento exibindo o resultado. A Figura 5.2 mostra os resultados obtidos.
Figura 5.1: Dados fornecidos ao programa.
RESULTADOS
Figura 5.2: Resultado da roteirização.
O programa gerou quatro roteiros obedecendo o tempo de ciclo (3h) e a capacidade do veículo
(12 ton). Assim, são necessários quatro veículos para realizar esse serviço de coleta e cada um
deles deverá seguir os pontos indicados pelo programa.
6. Conclusões
O Processo de Produção dos Correios é composto de uma série de atividades interligadas
formando uma grande e complexa cadeia logística, onde qualquer erro pode ser vital ao
funcionamento do sistema como um todo. No caso dos correios, há a necessidade de dados
confiáveis para a estimativa da demanda que, por sua vez, ainda depende da experiência dos
profissionais que atuam nesta área, podendo gerar erros de dimensionamento. Sabendo disso,
a equipe de logística dos Correios vêm trabalhando muito para que os dados representem
melhor a realidade.
Com a otimização das rotas a serem percorridas e a utilização de um Sistema de Rastreamento
de Veículos permitindo o monitoramento de todas as linhas haverá redução dos custos de
transporte e melhoria na segurança e na qualidade do serviço prestado. Assim, verificou-se
que o programa desenvolvido é de extrema importância e se mostrou bastante eficiente
tratando de dados muito próximos da realidade operacional dos Correios. É uma ferramenta
que realiza a roteirização de veículos de forma fácil e com custo baixo, aplicável a pequenas e
médias empresas, sempre fazendo as devidas adaptações.
Referências Bibliográficas
BALLOU, R. H., 1993, Logística Empresarial: Transportes, Administração de Materiais e
Distribuição Física. Atlas, São Paulo.
BARROS, J. F., 1997, “Análise de Desempenho dos Operadores Genéticos Aplicados ao
Problema do Caixeiro Viajante”. XXIX SBPO.
BOTT, K., BALLOU, R. H., 1986, “Research Perspectives in Vehicle Routing and
Scheduling”. Transportation Research, v. 20A, p. 239-243.
CLARK G., WRIGHT, J. W., 1964, “Scheduling of vehicles from a central depot to a number
of delivery points. Operations Research”, Operations Research,, v. 12, p. 568-581.
CEL. DIAS, P. R., DEXHEIMER, L: "Notas de Aula – Logística em Transportes", IME, Rio
de Janeiro, 2000.
CORREIOS, www.correios.com.br.
HOLLAND, J., 1975, “Adaptation in Natural and Artificial Systems”. The University of
Michigan Press, Ann Arbor, Mich.
LAPORTE, G., 1997A, “The Traveling Salesman Problem Na Overview of Exact and
Approximate Algorithms”. EJOR, v. 59, p.231-247.
NAGANO, M. S., AGUIAR, E. M., 1996,”Consepção de Técnicas Metaheurísticas para
Problemas de Roteirização de Veículos”. X ANPET, v. 1, p. 331-335, Brasília.
NOVAES, A. G., 1989, Sistemas Logísticos: Transporte, Armazenagem e Distribuição Física
de Produtos. Edgar Blucher, São Paulo.
NOVAES, A. G., ALVARENGA, A. C., 1997, Logística Aplicada: Suprimento e Distribuição
Física. Pioneira, São Paulo.