SISTEMAS DE ROTEIRIZAÇÃO E PROGRAMAÇÃO DE VEÍCULOS
Seção de Software
SISTEMAS DE ROTEIRIZAÇÃO E PROGRAMAÇÃO DE VEÍCULOS
André Cristiano da Silva Melo
Programa de Engenharia de Produção / COPPE
Universidade Federal do Rio de Janeiro
Rio de Janeiro ' RJ
Virgílio José Martins Ferreira Filho
Programa de Engenharia de Produção / COPPE e
Departamento de Engenharia Industrial
Universidade Federal do Rio de Janeiro
Rio de Janeiro ' RJ
1. Introdução
A grande concentração populacional nos grandes centros urbanos tem provocado o
aparecimento de um número cada vez maior de pontos de atendimento. Ao mesmo
tempo, tentando evitar o "caos urbano", provocado por um número cada
vez maior de veículos, as companhias de engenharia de tráfego têm imposto uma
série de restrições tanto de tamanho como de horários de circulação de
veículos, nas operações de coleta e/ou entrega de produtos.
Além disso, com a era da globalização e a introdução da filosofia de Gestão da
Cadeia de Suprimentos (GCS), os clientes têm se tornado cada vez mais exigentes
no que diz respeito à qualidade e prazos de entrega, gerando uma
competitividade crescente e uma busca por serviços cada vez mais customizados
que, para as empresas de distribuição de produtos, tem se tornado um fator cada
vez mais importante na obtenção de vantagem competitiva e conquista de fatias
cada vez maiores do mercado.
Nesse sentido, muitas empresas de transporte têm tentado dar maior
confiabilidade, mais velocidade e flexibilidade, assim como praticar a
intermodalidade em todos os seus canais de distribuição, buscando maior
eficiência e pontualidade nas tarefas de entrega e/ou coleta; um melhor
aproveitamento da frota e dos motoristas; menores tempos de ciclo; menores
tempos de obtenção e melhor planejamento das rotas, gerando assim sensíveis
reduções de custos operacionais, melhoria da imagem da empresa no mercado,
maior fidelidade de clientes e, em função disso, uma conquista cada vez maior
de fatias de mercado. Nesse sentido, de modo a obter excelência nos processos
de distribuição física, muitas empresas têm adquirido os chamados os sistemas
de roteirização e programação de veículos (SRPV).
Sistemas de Roteirização e Programação de Veículos ou, simplesmente,
Roteirizadores são sistemas computacionais que, através de
algoritmos,geralmente, heurísticos e uma apropriada base de dados, são capazes
de obter soluções para problemas de roteirização e programação de veículos
(PRPV) com resultados relativamente satisfatórios, consumindo tempo e esforço
de processamento relativamente pequenos quando comparados aos gastos nos
tradicionais métodos manuais.
Atualmente tais sistemas podem considerar inúmeros tipos restrições ou
condicionantes (ex.: um ou mais depósitos, janelas de tempo, vários tipos de
veículos, tempos de parada, velocidades variáveis, limitações de capacidade,
múltiplos compartimentos por veículo, barreiras físicas, restrições de
circulação de veículos e de jornadas de trabalho, etc.) que tornam possível a
obtenção de modelos muito próximos da realidade atual. Além disso, são dotados
de poderosos recursos gráficos e podem fornecer resultados (ex.: roteiro e
programação de cada veículo, relatórios de utilização dos veículos, relatórios
de programação do motorista, etc.) que são de grande importância para o
processo de tomada de decisão.
2. Evolução Histórica
Para Bodin (1990), a mais significativa mudança com relação aos sistemas para
roteirização e programação de veículos ocorreu no ambiente computacional. Em
sua primeira geração, quando os sistemas de roteirização e programação de
veículos eram executados nos chamados mainframes, os resultados gerados nem
sempre podiam ser conhecidos imediatamente, pois dependiam tanto do tempo de
processamento como da sua prioridade na fila de espera para resolução. Além
disso, esses sistemas não apresentavam recursos gráficos e interativos,
prejudicando ainda mais o entendimento e a aceitação das soluções por parte dos
usuários. Também, não era possível testar alterações manualmente nas soluções
obtidas, de modo a atender restrições não consideradas explicitamente nos
parâmetros de entrada do modelo, sendo que alguns destes recursos só vieram a
se tomar possíveis e acessíveis com o advento e a evolução dos
microcomputadores. Ainda segundo este autor, esses primeiros sistemas eram
limitados, lentos e com muitos procedimentos heurísticos que apresentavam pouca
robustez. Enquanto alguns sistemas possuíam razoáveis recursos gráficos e de
intervenção manual, outros não possuíam virtualmente nenhum.
Logo depois, surgiram os sistemas auxiliados por computador para roteirização
de veículos, que, em vez de fornecer ao usuário uma solução pronta, auxiliavam-
no a examinar em menor tempo diferentes alternativas, permitindo ao usuário
(programador ou despachador) preocupar-se com as condicionantes do problema
mais difíceis de serem consideradas, e ainda visualizar os impactos econômicos
e operacionais decorrentes de alterações manuais. No entanto, cabia ao usuário
propor as melhores alternativas, assim como selecionar a mais adequada. Já na
segunda geração, desenvolvida em meados dos anos 80, tais sistemas consideravam
um número maior de restrições reais, sendo que alguns já apresentavam recursos
gráficos em suas resoluções. A seguir, o Quadro_I apresenta um resumo das
principais características de alguns deles. Para maiores detalhes, consultar o
trabalho de Golden & Bodin (1986).
Nos anos 90 o estrondoso avanço tecnológico, em termos computacionais,
associado às intensas pesquisas desenvolvidas na área de pesquisa operacional,
foram fundamentais tanto ao desenvolvimento de melhores soluções aos PRPV
quanto à maior e melhor integração destes sistemas aos demais sistemas de
negócios da empresa (compras, vendas, produção etc.). Nesse mesmo período
muitos desses sistemas passaram a contar com o apoio da tecnologia de Sistemas
de Informação Geográfica (SIG), permitindo, além de uma perfeita visualização e
edição de rotas e paradas em mapas já utilizados pelos motoristas, identificar
e geocodificar todos pontos de atendimento a partir dos próprios endereços dos
clientes, bem como armazenar quaisquer tipos de informações referentes aos
mesmos. A integração dos SIG aos modelos de roteirização e programação permitiu
a concepção dos chamados Sistemas de Apoio à Decisão Espacial (SADE).
Atualmente, a grande maioria dos roteirizadores disponíveis já apresenta
tecnologia baseada nos SADE, ou seja, são dotados de vários recursos
computacionais, matemáticos e gráficos que proporcionam plataformas cada vez
mais amigáveis, em termos de interface com o usuário; flexíveis, na adequação
operacional da empresa; e robustas, na medida que seus algoritmos resolvem
problemas com números de pontos de atendimento (clientes) cada vez maiores,
considerando restrições cada vez mais complexas (horários de circulação e
atendimento, tamanhos de veículos etc.). Além disso, o maior uso da Internet e
a intensificação do comércio eletrônico (e-commerce), provocado por avanços na
área de comunicação intra e inter-empresarial, tem aquecido o mercado,
provocando uma grande revolução tecnológica no sentido de melhoria de
relacionamento com o cliente final e, conseqüente, obtenção de vantagem
competitiva sobre a concorrência.
Recentemente pode ser observada uma tendência de muitos destes roteirizadores
se apresentam disponíveis como parte de um conjunto de sistemas integrados de
gestão empresarial (ERPs e os Supply Chain Software) que possibilitaria, a
partir da própria internet, disponibilizar a clientes finais informações sobre
carregamentos, localização de veículos, previsão de horários de chegada,
serviços de solicitação automática de pedidos etc.
3. Caracterização de Alguns Sistemas Disponíveis no Mercado
No Brasil atualmente são comercializados diversos sistemas de roteirização,
sendo a maioria deles ainda desenvolvida no exterior, com heurísticas de
solução que geralmente não são disponibilizadas pelos seus desenvolvedores. As
principais características possíveis de se levantar sobre estes produtos são
descritas abaixo.
OTrucks é um dos sistemas mais antigos disponível no mercado nacional e o que
se tem maiores registros de utilização. É um sistema complexo que requer a
montagem, bem como a edição e atualização de uma rede viária realizada a partir
de uma mesa digitalizadora. Com o mapa digitalizado, a malha viária é desenhada
(acompanhando o contorno das ruas), e nela os clientes podem ser localizados no
nível de quarteirão. A partir daí, este sistema define as rotas, excluindo
trechos que apresentem barreiras naturais ou artificiais (congestionamentos,
obras, acidentes, etc.), definindo velocidades de tráfego nas ruas, cadastrando
todos os clientes, reduzindo o tempo de processo como um todo. Além disso,
todas estas rotas podem ser visualizadas na tela de um microcomputador sobre a
malha viária da cidade. Segundo seu fabricante, este sistema indica as rotas
levando em conta parâmetros como:
* Horários de recebimento das mercadorias de cada veículo;
* Taxas de descarga;
* Velocidades médias por trecho;
* Distância média entre pontos.
Além disso, este sistema pode ainda tomar como referência rotas com pernoite,
tempo de trabalho do motorista e custos de horas extras, bem como obter, como
resultado final, uma estatística da roteirização, incluindo o custo total de
cada rota.
Para utilizar o Trucks é necessário ter, pelo menos, um microcomputador 486 com
sistema operacional DOS, Windows ou OS 2.
O Truckstops parece utilizar como estratégia de solução, segundo CUNHA (1997),
um método de geração de roteiros iniciais através de uma heurística do tipo
vizinho mais próximo, roteiros estes que podem ser melhorados através de uma
heurística de intercâmbios de clientes dentro de um mesmo roteiro e entre
veículos. Segundo seu fabricante, este sistema trabalha com três tipos básicos
de dados:
* Informações de paradas ' nomes, endereços, números de identificação,
latitude e longitude;
* Informações dos veículos ' fatores de custo ($/milha, $/h e $/h extra),
regras de trabalho, origem e destino;
* Informações gerais ' Defaults e dados não específicos de paradas ou
veículos individuais.
Além desses, pode-se inserir dados geográficos tais como: mapas (detalhados ou
não); barreiras geográficas naturais (rios, lagos, etc.) ou não (serviços de
infra-estrutura, desvios, etc.) e dados de redes urbanas ou rodoviárias. Este
sistema é capaz de trabalhar com mais de 1700 clientes e permite ao usuário:
indicar paradas e obter as melhores programações de rotas para cada veículo da
frota; ajustar prioridades de carregamento; indicar todos ou alguns veículos
como transportadores autônomos; consolidar paradas localizadas nos mesmos
pontos, prédios ou alamedas; particionar grandes carregamentos para um único
veículo; redespachar, se necessário, veículos de modo a suprir de forma mais
eficiente a demanda de clientes.
Segundo o fabricante, este sistema apresenta uma versão totalmente em
português, sendo disponibilizado nas versões 32-bit (recomendada para grandes
operações, onde os problemas de roteamento apresentam mais de 3000 pontos de
parada), 16-bit e LAN. Em todas as versões recomenda-se um processador Pentiun
com, pelo menos, 16 MB de RAM e 50 MB de HD, e. sistemas operacionais Windows
95, 98, NT ou 2000.
O RoadShow parece ser um sistema bastante flexível, possibilitando a tomada de
decisões baseada em custo reais de distribuição, considerando variáveis como
tempo, tráfego, condições das ruas, entre outras. Segundo seu fabricante,
utilizando-se omouse, é possível criar, editar e atualizar a malha viária (nós
elinks), assim como modificar (ex. devido à adição de um novo cliente) suas
rotas, recalculando e mostrando a nova rota, além das implicações de custo
decorrentes de tais modificações. Nesse sistema, o mapa de operação, sobre o
qual são exibidas as rotas, é scanneado do mesmo mapa usado por despachantes e
motoristas, ou seja, com todos os detalhes importantes da região em questão,
garantindo, assim, que as rotas não passem por barreiras naturais ou
artificiais.
Comercializado no Brasil desde 1993, este sistema trabalha com janelas de tempo
rígidas ou flexíveis, definindo a freqüência de atendimento e selecionando os
dias mais adequados ao atendimento. Outra peculiaridade é o uso de dois
monitores simultaneamente: um para representação gráfica do mapa scanneado e
dos roteiros, e o outro contendo informações detalhadas do que está sendo
exibido graficamente. Devido ainda a sua interface gráfica, o Roadshow pode
mostrar, além de mapas contendo rotas, paradas e caminhos a serem percorridos,
planilhas de cálculo de rotas com detalhes de custo para até 4 rotas.
O TransCAD é um sistema utilizado para armazenar, mostrar, gerenciar e analisar
dados de transporte, combinando um SIG e um sistema de modelagem de capacidades
de transporte em uma plataforma integrada (SIG-T). Trabalhando com todos os
modais de transporte, este sistema, quando aplicado a modelos de roteamento e
logística, pode ser utilizado por diferentes setores (públicos ou privados) em
aplicações tais como:
* Operações de coleta e entrega;
* Planejamento da distribuição;
* Manutenção de facilidades/oportunidades (Facility maintenance);
* Coleta e entrega porta-a-porta;
* Varrição de ruas ou remoção de neve;
* Coleta de lixo sólido e reciclável;
* Cálculo de distâncias percorridas.
Segundo seu fabricante este sistema apresenta métodos de resolução que se
baseiam na clássica heurística de "Economias" desenvolvida por Clarke
& Wright (1964), para roteirização de pontos, e na heurística do Problema
do Carteiro Chinês Misto, sugerida por Edmonds e Johnson (1973), melhorada por
Frederickson (1979) e Christofides et al. (1984), e também usada por Gendreau,
Laporte & Zhao no Windy Postman Problem, em roteamento de arcos (Melo,
2000).
O ROTAcerta foi desenvolvido pela Escola Politécnica da Universidade de São
Paulo (USP) em 1993. É um sistema com interface em português, utilizado
especialmente no contexto de roteamento e programação de veículos em áreas
urbanas, considerando fatores e restrições comumente encontrados nesse
ambiente, porém quase nunca tratados (devido à dificuldade que introduzem) na
programação manual. Suas aplicações estão ligadas a entregas domiciliares;
bebidas, cigarros, jornais ou qualquer outro produto; fretamento de
funcionários; coleta e distribuição para atacadistas; visitas de assistência
técnica, vendedores, etc.; transporte de valores; e muitos outros. A partir da
relação de clientes a atender e parâmetros dos tipos de veículos utilizados,
este sistema determina os roteiros de coleta ou entrega e seus respectivos
horários da frota, a fim de atender um conjunto de clientes ou tarefas,
minimizando os custos totais de distribuição e atendendo a restrições do tipo:
* Capacidade de cada tipo de veículo em peso e/ou volume;
* Coleta e entrega simultânea (backhaul);
* Equipamentos especiais dos veículos para realizar os atendimentos;
* Faixa de horário de atendimento;
* Horas extras, duração máxima da jornada e horário de almoço;
* Tempos de viagem e de atendimento;
* Veículo máximo por cliente.
Sua otimização considera as parcelas de custo variável com distância
percorrida, custo do tempo e custo fixo por veículo utilizado, cujos valores
unitários podem ser fornecidos pelo usuário. Além disso, este sistema ainda
fornece a seqüência de tarefas e os respectivos horários de atendimento para
cada veículo da frota.
O ArcLogistics Route,segundo seu fabricante (ESRI), é capaz de atribuir paradas
a veículos, além de construir seqüências de paradas considerando fatores como
tempo, custo, capacidade e produtividade de veículos. Esse sistema pode ser
utilizado em várias aplicações, a saber:
* Operações governamentais (estaduais e locais), permitindo redução de
custos e melhoria de serviços, ao mesmo tempo, adequando-se a questões
políticas e regulamentares;
* Gerenciamento de frotas de veículos, fornecendo suporte à tomada de
decisão referente tanto à geração quanto ao planejamento de rotas de
entrega (comercial e residencial);
* Operações relacionadas à saúde pública, possibilitando maior eficiência
tanto em serviços de transporte (emergência/transferência) de pacientes,
feitos por ambulâncias, como em coletas de material destinado a exames
laboratoriais;
* Telecomunicações, auxiliando companhias públicas ou privadas na redução
de custos, ao mesmo tempo, mantendo/aumentando níveis de infra-estrutura,
manutenção e serviços.
Além disso, seus modelos matemáticos e ferramentas computacionais permitem a
adequação às necessidades operacionais da empresa (tipos de veículos, modelos
de distribuição, custo operacionais, informações customizadas). Dentre suas
principais características tem-se sua adequação ao Open Database Connectivity
(ODBC), com o que a base de dados do sistema pode ser diretamente integrada ao
SAP R/3; e o aplicativo Seagate Crystal Reports, que gera resumos de
informações de rota de alta qualidade (mapas onde podem ser visualizadas rotas
e seqüências de paradas, mãos de ruas etc.), além de manifestos de motoristas.
Este sistema opera, segundo dados de seu fabricante, com Windows (98, 2000, NT
4.0 e Me); utilizando processadores Intel Pentium II (mínimo) ou Pentium III
(recomendado) de 266 MHz (mínimo) ou 600 MHz (recomendado); vários tamanhos de
disco rígido (HD), dependendo do tamanho da base de dados; 64 MB (mínimo) ou
128 MB (recomendado) de memória RAM, além de 200 MB de memória virtual.
O Quadro_II faz um resumo de mais algumas características de sistemas
disponíveis comercialmente no mercardo nacional.
4. Relação Custo x Benefício na Aquisição de um Roteirizador
Adquirir um sistema de roteirização pode permitir ganhos significativos, tanto
do ponto de vista financeiro, com a redução dos custos operacionais, quanto em
termos da qualidade do serviço permitindo maior quantidade e fidelidade de
clientes, ganhos estes de grande importância para a melhor integração da cadeia
de suprimentos e, conseqüente, para a obtenção de vantagens competitivas. O
Quadro_III, logo a seguir, mostra alguns casos reais de sucesso de aquisição de
sistemas de roteirização e programação de veículos, relacionando a empresa, seu
ramo de atuação, principais problemas, sistema utilizado e os resultados
alcançados.
No entanto, tanto a aquisição quanto a manutenção deste tipo sistema, assim
como da sua base de dados, geram significativos custos, caracterizando-se como
pontos negativos à sua utilização. A prática mostra que sistemas mal
implantados e mal gerenciados constituem uma fonte incessante de problemas e
prejuízos. Assim, durante o planejamento de aquisição e, posterior, implantação
é necessário considerar questões como:
* Há realmente necessidade de adquirir tal tecnologia?
* Quais os reais problemas a serem solucionados?
* Que tipos de problemas esta aquisição poderá trazer?
* Quais os reais objetivos da aquisição?
* Quais e quanto de recursos serão disponibilizados?
* Em quantas fases será feita a implantação?
* Quais as tarefas e atividades a serem desenvolvidas?
* Quais profissionais devem ser envolvidos?
* Seria melhor desenvolver um sistema ou adquirir um dos disponíveis no
mercado?
* Quais os roteirizadores disponíveis no mercado?
* Quais as principais características de cada produto?
* Quais os critérios devem ser adotados à seleção do sistema?
* Em que prazo surgirão os 1º resultados?
O que se percebe é que a maioria dos casos de insucesso são ocasionados por
falta de um bom planejamento e gerenciamento de implantação; por
"empolgação"; por falta de orientação e até mesmo por falta de uma
maior quantidade de informação em relação àscaracterísticas dos produtos
disponíveis no mercado.
Ao se pensar em adquirir um sistema de roteirização qualquer empresa deve se
preocupar em ter resposta para algumas das questões citadas acima pois, caso
contrário, pode obter resultados totalmente diversos daqueles que a idéia de
aquisição (e o próprio sistema) propõe.
