UNIVERSIDADE FEDERAL FLUMINENSE
CENTRO TECNOLÓGICO
CURSO DE MESTRADO EM ENGENHARIA DE PRODUÇÃO
DAVIDSON DE ALMEIDA SANTOS
ANÁLISE COMPARATIVA DAS HEURÍSTICAS DE UM SOFTWARE DE
ROTEIRIZAÇÃO POR INTERMÉDIO DE PARÂMETROS DE PRODUTIVIDADE –
Aplicação em uma empresa distribuidora de bebidas
NITERÓI
2007
DAVIDSON DE ALMEIDA SANTOS
ANÁLISE COMPARATIVA DAS HEURÍSTICAS DE UM SOFTWARE DE
ROTEIRIZAÇÃO POR INTERMÉDIO DE PARÂMETROS DE PRODUTIVIDADE –
Aplicação em uma empresa distribuidora de bebidas
Dissertação apresentada ao Curso de Mestrado
em Engenharia de Produção da Universidade
Federal Fluminense, como requisito parcial
para obtenção do Grau de Mestre. Área de
Concentração: Apoio à Decisão Logística.
Orientador: Prof. MARCO ANTÔNIO FARAH CALDAS, Ph. D.
Niterói
2007
DAVIDSON DE ALMEIDA SANTOS
ANÁLISE COMPARATIVA DAS HEURÍSTICAS DE UM SOFTWARE DE
ROTEIRIZAÇÃO POR INTERMÉDIO DE PARÂMETROS DE PRODUTIVIDADE –
Aplicação em uma empresa distribuidora de bebidas
Dissertação apresentada ao Curso de Mestrado
em Engenharia de Produção da Universidade
Federal Fluminense, como requisito parcial
para obtenção do Grau de Mestre. Área de
Concentração: Apoio à Decisão Logística.
Aprovada em 21 de Agosto de 2007
BANCA EXAMINADORA
____________________________________________________________
Prof. Marco Antônio Farah Caldas, PhD.
Universidade Federal Fluminense
______________________________________________________________
Prof. Luiz Fleury Wanderley Soares, Ph.D.
Universidade Federal Fluminense
_____________________________________________________________
Prof. Hostilio Xavier Ratton Neto, D.sc.
Universidade Federal do Rio de Janeiro
Niterói
2007
AGRADECIMENTOS
A Deus que me concedeu, com as suas bênçãos intermitentes, a determinação
na medida necessária para concluir esse trabalho.
A Sheila que se constitui como o grande amor da minha e a pessoa que desde o
começo do mestrado, rezou, apoiou e ofereceu-me todo o amor e carinho que
eu precisava para concluir esse trabalho. Meu amor essa vitória também é sua e
você faz e fará parte dessa e de muitas outras vitórias. Com certeza sem o seu
amor os obstáculos tornar-se-iam intransponíveis. Meu amor te amo muito e
dedico esse trabalho a você.
A minha família, um dos pilares importantes em minha vida, que participou de
uma forma ou de outra para a conclusão desse trabalho.
Aos professores e funcionários do mestrado em engenharia de produção que
contribuíram com esse trabalho.
Ao Prof. Marco Caldas com suas orientações valiosas para o presente trabalho.
LISTA DE FIGURAS
Figura 1 – Principais trabalhos na área de programação linear, f. 16
Figura 2 – Representação gráfica dos tipos de grafos, f. 20
Figura 3 – Representação gráfica do grau de vértice de um grafo, f. 23
Figura 4 – Representação da rede formada em um grafo, f. 23
Figura 5 – Representação gráfica do fecho transitivo direto de x, f. 25
Figura 6 – Redução polinomial, f. 44
Figura 7 – Provável configuração das classes, f. 46
Figura 8 – Representação gráfica do método de Clark e Wright, f. 47
Figura 9 – Representação gráfica do método r-opt da troca de nós na rota, f. 49
Figura 10 – Heurística de Bellmore e Nemhauser passo a passo, f. 51
Figura 11 – Exemplificação dos movimentos 2-opt e 3-opt, f. 55
Figura 12 – Demonstração gráfica da troca de vértices para mais de uma rota, f. 56
Figura 13 – Demonstração gráfica da inserção de vértices entre duas rotas, f. 57
Figura 14 – Representação gráfica da heurística de Gillet e Miller, f. 59
Figura 15 – Representação gráfica da heurística de Mole e Jameson, f. 63
Figura 16 – Área de roteirização 8, f. 69
Figura 17 – Área de roteirização 3, f. 69
Figura 18 – Área de atendimento antiga (antes de 14/08/2006) da central de distribuição de
Jacarepaguá, f. 70
Figura 19 – Área de atendimento que passou a ser atendida pela central de distribuição de
Campo Grande, f. 71
Figura 20 – Área de atendimento que passou a ser atendida pela central de distribuição de São
Cristóvão, f. 71
Figura 21 – Área de atendimento atual da central de distribuição de Jacarepaguá, f. 72
Figura 22 – Organograma da área de logística da central de distribuição de Jacarepaguá, f. 73
Figura 23 – Representação gráfica do macro fluxo de operações, f. 75
Figura 24 – Representação gráfica da primeira etapa do Fluxo Entrega Rota, f. 76
Figura 25 – Representação gráfica da segunda etapa do Fluxo Entrega Rota, f. 77
Figura 26 – Representação gráfica da terceira etapa do Fluxo Entrega Rota, f. 77
Figura 27 – Representação gráfica da quarta etapa do Fluxo Entrega Rota, f. 78
Figura 28 – Descrição das etapas principais do fluxo entrega rota, f. 78
Figura 29 – Representação gráfica da primeira etapa do fluxo recebimento da puxada, f. 79
Figura 30 – Representação gráfica da segunda etapa do fluxo recebimento da puxada, f. 79
Figura 31 – Representação gráfica da primeira etapa do Fluxo do carregamento, f. 80
Figura 32 – Representação gráfica da segunda etapa do Fluxo do carregamento, f. 80
Figura 33 – Representação gráfica da primeira etapa do fluxo de retorno de rota, f. 81
Figura 34 – Representação gráfica da segunda etapa do fluxo de retorno de rota, f. 81
Figura 35 – Descrição do fluxo de roteirização, f. 82
Figura 36 – Ambiente de roteirização, f. 83
Figura 37 – Formação dos cenários simulados de roteirização, f. 96
Figura 38 – Fluxo relacionando as alternativas de roteamento
características básicas de resolução, f. 98
em relação as
suas
LISTA DE TABELAS
Tabela 1 – Tabela de tamanho do problema em relação ao tempo estimado para a resolução,
f. 40
Tabela 2 – Função complexidade tempo de algoritmos de tempo polinomial e exponencial,
relacionado ao tamanho da instância do problema, f. 42
Tabela 3 – Perfil de veículos utilizados pela central de distribuição de Jacarepaguá, f. 85
Tabela 4 – Resultados do cenário (1) para pontos concentrados e próximos um dos outros no
volume alto e com parâmetros obtidos da média dos dados reais consolidados,
f. 99
Tabela 5 – Resultados do cenário (1) para pontos concentrados e próximos um dos outros no
volume alto e com parâmetros obtidos do maior valor dos dados reais
consolidados, f. 99
Tabela 6 – Resultados do cenário (2) para pontos concentrados e próximos um dos outros no
volume médio e com parâmetros
obtidos
da
média dos
dados
reais
consolidados, f. 100
Tabela 7 – Resultados do cenário (2) para pontos concentrados e próximos um dos outros no
volume médio e com parâmetros obtidos do maior valor dos dados reais
consolidados, f. 101
Tabela 8 – Resultados do cenário (3) para pontos concentrados e próximos um dos outros no
volume baixo e
com parâmetros obtidos
da
média
dos
dados reais
consolidados, f. 102
Tabela 9 – Resultados do cenário (3) para pontos concentrados e próximos um dos outros no
volume baixo e com parâmetros obtidos do maior valor dos dados reais
consolidados, f. 102
Tabela 10 – Resultados do cenário (4) para pontos concentrados e afastados um dos outros no
volume alto
e
com parâmetros obtidos
da
média
dos
dados
reais
consolidados, f. 103
Tabela 11 – Resultados do cenário (4) para pontos concentrados e afastados um dos outros no
volume alto e com parâmetros obtidos do maior valor dos dados reais
consolidados, f. 103
Tabela 12 – Resultados do cenário (5) para pontos concentrados e afastados um dos outros no
volume médio e com parâmetros
obtidos
da
média dos
dados
reais
consolidados, f. 104
Tabela 13 – Resultados do cenário (5) para pontos concentrados e afastados um dos outros no
volume médio e com parâmetros obtidos do maior valor dos dados reais
consolidados, f. 104
Tabela 14 – Resultados do cenário (6) para pontos concentrados e afastados um dos outros no
volume baixo e com parâmetros obtidos
da
média
dos
dados reais
consolidados, f. 105
Tabela 15 – Resultados do cenário (6) para pontos concentrados e afastados um dos outros no
volume baixo e com parâmetros obtidos do maior valor dos dados reais
consolidados, f. 105
Tabela 16 – Resultados do cenário (7) para pontos concentrados ao redor do CDD no volume
alto e com parâmetros obtidos da média dos dados reais consolidados, f. 106
Tabela 17 – Resultados do cenário (7) para pontos concentrados ao redor do CDD no volume
alto e com parâmetros obtidos do maior valor dos dados reais consolidados,
f. 107
Tabela 18 – Resultados do cenário (8) para pontos concentrados ao redor do CDD no volume
médio e com parâmetros obtidos da média dos dados reais consolidados, f. 107
Tabela 19 – Resultados do cenário (8) para pontos concentrados ao redor do CDD no volume
médio e com parâmetros obtidos do maior valor dos dados reais consolidados,
f. 108
Tabela 20 – Resultados do cenário (9) para pontos concentrados ao redor do CDD no volume
baixo e com parâmetros obtidos da média dos dados reais consolidados, f. 108
Tabela 21 – Resultados do cenário (9) para pontos concentrados ao redor do CDD no volume
baixo e com parâmetros obtidos do maior valor dos dados reais consolidados,
f. 109
SUMÁRIO
1 INTRODUÇÃO, p. 14
1.1 OBJETIVO DO ESTUDO, p. 17
1.2 METODOLOGIA, p.17
2 REVISÃO BIBLIOGRÁFICA, p. 19
2.1 CONCEITOS FUNDAMENTAIS EM TEORIA DOS GRAFOS, p. 19
2.2 REPRESENTAÇÃO MATRICIAL DE UM GRAFO, p. 22
2.3 GRAUS DE UM VÉRTICE, p. 22
2.4 DEFINIÇÃO DE REDE, p. 23
2.5 OUTROS CONCEITOS BÁSICOS, p. 24
2.5.1 Vizinhança entre vértices, p. 24
2.5.2 Sucessores e Antecessores de um vértice, p. 24
2.5.3 Fechos transitivos, p. 24
2.6 O PROBLEMA DE ROTEAMENTO DE VEÍCULOS (PRV), p. 25
2.7 PROBLEMAS CLÁSSICOS DE ROTEAMENTO, p. 27
2.8 CRITÉRIOS PARA A CLASSIFICAÇÃO DOS PROBLEMAS DE ROTEAMENTO DE
VEÍCULOS (PRV), p. 28
2.9 CLASSIFICAÇÃO DOS PRINCIPAIS PROBLEMAS DE ROTEAMENTO
DE
VEÍCULOS, p. 31
2.10 O PROBLEMA DE ROTEAMENTO DE VEÍCULOS (PRV) BÁSICO E SUAS
EXTENSÕES, p. 32
2.11 DESCRIÇÃO DO MODELO MATEMÁTICO DO PROBLEMA DE ROTEAMENTO
AMPLIADO, p. 35
2.11.1 Em relação à estrutura da rede, p. 36
2.11.2 Em relação aos veículos, p. 36
2.11.3 Em relação aos pedidos, p. 37
2.11.4 Em relação às variáveis de otimização, p. 37
2.11.5 Função objetivo, p. 38
2.11.6 Restrições de exclusividade, p. 38
2.11.7 Limitação no número de veículos, p. 39
2.11.8 Restrições de capacidade, p. 39
2.12 COMPLEXIDADE COMPUTACIONAL, p. 40
2.13 CLASSIFICAÇÃO DOS PROBLEMAS DE DECISÃO, p. 45
2.14 ALTERNATIVAS DE ROTEIRIZAÇÃO PARA O PROBLEMA DE ROTEAMENTO
DE VEÍCULOS (PRV), p. 46
2.14.1 Métodos heurísticos, p. 46
2.14.2 Heurística de Bellmore e Nemhauser, p. 50
2.14.3 Heurística de Clark e Wright (CW), p. 51
2.14.4 Procedimentos de melhoria, p. 54
2.14.5 Heurística de Gillet e Miller (Primeiro-agrupa e segundo-roteiriza), p. 58
2.14.6 Método de primeiro-roteiriza e segundo-clusteriza, p. 61
2.14.7 Algoritmo de Fisher e Jaikumar (1981), p. 61
2.14.8 Heurística de Mole e Jameson, p. 62
2.14.9 Heurística construtiva de Solomon (1987), p. 64
3 ESTUDO DE CASO, p. 65
3.1 VISÃO NO ÂMBITO BRASIL DA EMPRESA DISTRIBUIDORA DE BEBIDAS, p. 65
3.2 ESTRUTURA FUNCIONAL DAS UNIDADES PERTENCENTES À GEOGRAFIA
RIO DE JANEIRO DA EMPRESA DISTRIBUIDORA DE BEBIDAS, p. 66
3.3 ÁREA
DE
ATENDIMENTO
DA
CENTRAL
DE
DISTRIBUIÇÃO
DE
JACAREPAGUÁ, p. 68
3.4 INFRA-ESTRUTURA ORGANIZACIONAL E LOGÍSTICA DA CENTRAL DE
DISTRIBUIÇÃO DE JACAREPAGUÁ, p. 72
3.5 MACRO FLUXO DE OPERAÇÕES, p. 73
3.5.1 Fluxo entrega rota, p. 75
3.5.2 Fluxo Recebimento de Puxada, p. 79
3.5.3 Fluxo do Carregamento, p. 80
3.5.4 Fluxo retorno de rota, p. 81
3.5.5 Fluxo de roteirização, p. 82
3.6 SOFTWARE DE ROTEIRIZAÇÃO, p. 82
3.6.1 Ambiente de roteirização, p. 83
3.6.2 Gerenciador de dados, p. 84
3.6.2.1 Cadastro de produtos, p. 84
3.6.2.2 Cadastro de veículos da empresa, p. 84
3.6.2.3 Cadastro de motoristas e ajudantes, p. 85
3.6.2.4 Perfil dos veículos cadastrados, p. 85
3.6.3 Parâmetros, p. 85
3.6.4 Regras de roteirização, p. 88
3.6.5 Roteirização dos pedidos, p. 89
4 ASPECTOS
QUE
PRECEDEM
ALTERNATIVAS DE
AS
ANÁLISES
COMPARATIVAS
ROTEAMENTO PRESENTES
DAS
NO SOFTWARE
DE
ROTEIRIZAÇÃO, p. 91
5 ANÁLISES COMPARATIVAS DAS
ALTERNATIVAS
DE
ROTEAMENTO
PRESENTES NO SOFTWARE DE ROTEIRIZAÇÃO, p. 97
5.1 PONTOS CONCENTRADOS E PRÓXIMOS UM DOS OUTROS, p. 98
5.1.1 Cenário (1): Pontos concentrados e próximos um dos outros – Volume alto, p. 99
5.1.2 Cenário (2): Pontos concentrados e próximos um dos outros – Volume médio, p. 100
5.1.3 Cenário (3): Pontos concentrados e próximos um dos outros – Volume baixo, p. 101
5.2 PONTOS CONCENTRADOS E AFASTADOS UM DOS OUTROS, p. 102
5.2.1 Cenário (4): Pontos concentrados e afastados um dos outros – Volume alto, p. 103
5.2.2 Cenário (5): Pontos concentrados e afastados um dos outros – Volume médio, p. 104
5.2.3 Cenário (6): Pontos concentrados e afastados um dos outros – Volume baixo, p. 105
5.3 PONTOS CONCENTRADOS AO REDOR DO CDD, p. 106
5.3.1 Cenário (7): Pontos concentrados ao redor do CDD – Volume alto, p. 106
5.3.2 Cenário (8): Pontos concentrados e ao redor do CDD – Volume médio, p. 107
5.3.3 Cenário (9): Pontos concentrados ao redor da central de distribuição – Volume baixo,
p. 107
5.4 ANÁLISES COMPLEMENTARES EM RELAÇÃO
ROTEIRIZAÇÃO, p. 109
6 CONCLUSÕES E RECOMENDAÇÕES, p. 112
7 REFERÊNCIAS, p. 114
ANEXOS, p. 117
ÀS
ALTERNATIVAS
DE
RESUMO
O roteamento de veículos em áreas urbanas coloca-se como um dos principais
problemas da área de logística. Esse alto nível de complexidade deve-se a multiplicidade de
restrições que devem ser consideradas para este tipo de problema e ao impacto gerado em
custos no momento em que o roteamento de veículos mostra-se pouco eficiente. Esse estudo
desenvolve uma análise comparativa em relação às alternativas de roteirização presentes em
um software de roteirização de uma empresa distribuidora de bebidas. O estudo tem como
objetivo contribuir com análises que permitirão uma melhor compreensão do problema de
roteamento em áreas urbanas e verificar em que cenários as alternativas de roteirização
adaptam-se melhor.
Palavras-chave: Software de roteirização. Alternativas de roteirização. Problema de
roteamento. Heurísticas.
ABSTRACT
The routing of vehicles in urban areas poses as a major problem in the area of
logistics. This high level of complexity due to the multiplicity of restrictions to be considered
for this kind of problem and the impact on costs generated at the time the routing of vehicles
it is inefficient. This study develops a comparative analysis of the routing alternatives in a
routing software of the company in a distributor of beverages. The study aims to contribute to
analysis for better understanding of the problem of routing in urban areas and see where the
scenarios routing alternative adapt itself better.
Keywords: Software of Routing. Routing Alternatives. Routing Problem. Heuristical.
1 INTRODUÇÃO
Segundo Eilon (1971) logística pode ser definida como a “provisão de bens e serviços
de um ponto de oferta para um ponto de demanda”. Um sistema logístico completo congrega
a movimentação da matéria-prima de fornecedores para a fábrica, a conversão desses insumos
em produtos, a movimentação desses produtos para fábricas e armazéns e a entrega desses
produtos ao consumidor final.
Segundo Ballou (1993) a logística associa estudo e administração dos fluxos de bens e
serviços e da informação que os põe em movimento. Caso fosse viável produzir todos os bens
e serviços nas áreas onde estes serão consumidos ou se as pessoas vivessem onde os produtos
são fabricados, a logística não seria tão importante. No entanto, isso não ocorre devido à
tendência que as regiões têm em especializar-se na produção de determinado bem ou serviço.
Essa tendência encontra-se diretamente relacionada às características naturais e econômicas
que a região apresenta, fazendo com que esta venha a se especializar na produção do produto
que lhe permitir obter uma maior vantagem econômica. Com isso a missão do profissional de
logística é colocar as mercadorias ou os serviços no lugar, no instante correto e na condição
desejada ao menor custo.
As atividades de distribuição de empresa compreendem toda a movimentação e
estocagem de bens. Segundo Christofides (1981) a última etapa nessa movimentação (da
central de distribuição para os consumidores), constitui-se como o elo mais caro da cadeia de
distribuição. Para Bodin (1983) o sucesso na realização dessa etapa depende do
desenvolvimento racional do planejamento e execução da atividade de transporte.
A relevância dos problemas de distribuição está relacionada à magnitude dos custos
associados a essa atividade. Conseqüentemente torna-se evidente a relevância dos problemas
de distribuição e, por conseguinte as questões referentes ao sistema de roteamento e
programação de veículos, já que estas se constituem como os fatores que determinarão o quão
15
eficiente será a distribuição de determinado produto.
O sistema de roteamento é definido como um conjunto organizado de meios que
objetiva o atendimento de demandas localizadas nos arcos e/ou nos vértices de alguma rede
de transportes. No caso de roteamento de veículos, o objetivo mais comum é utilizar-se de
uma frota de veículos para atender a um conjunto de pedidos de entrega, cujas demandas
estão localizadas nos nós da rede denominados destino. Para atender a esses pedidos, um
conjunto de restrições deve ser respeitado. Essas restrições podem ser as mais diversas, como:
capacidade limitada dos veículos; capacidade limitada dos arcos ou dos nós; tamanho da frota;
quantidade de nós; tempo de entrega; etc.
Na literatura, há inúmeros trabalhos publicados, os quais abordam os mais diversos
temas, desde modelos simples (com frota homogênea, produtos de único tipo e sem janela de
tempo) a modelos bem mais complexos (com frota não-homogênea, produtos de diferentes
tipos, janela de tempo para a entrega da encomenda, com roteamento dinâmico, etc).
Em 1987, por exemplo, a abordagem feita por Kolen, Kan e Trienekens em
“Problemas de Roteamento de Veículos” (PRV), considerou o problema com janela de tempo
(time Windows), uma frota fixa de veículos, com capacidade limitada e disponível em um
único depósito. O objetivo era atender a um conjunto de clientes com uma dada demanda, que
deveriam ser visitados dentro de um período específico de tempo.
Em 1993, Taillard observou que PRV’s eram, na maioria das vezes, problemas de alta
complexidade. Neste trabalho, o autor considerou o problema PRV formulado para veículos
idênticos (quantidade não definida), possuindo capacidade de carga fixa, com as cargas
concentradas em um único depósito. Posteriormente, Taillard considerou o mesmo problema
formulado com restrição de janela de tempo.
Em 1998, Savelsbergh e Sol apresentaram um software para planejamento de
transporte a ser incorporado em um sistema de suporte de decisão para uma grande
companhia de transporte rodoviário na região de “Benelux“ (Bélgica, Holanda e
Luxemburgo), com cerca de 1400 veículos, transportando 160 mil encomendas para centenas
de consumidores, para dezenas de centenas de endereços. O serviço dessa companhia era
grosseiramente dividido em duas partes: o sistema de transporte regular e o sistema de
transporte direto.
As inúmeras pesquisas sobre a roteirização de veículos colocam essa área de estudo
como um dos maiores sucessos da pesquisa operacional nas últimas décadas. Isso se deve a
atuação conjunta entre teoria e prática. Por um lado a pesquisa operacional tem desenvolvido
16
cada vez mais algoritmos que tem um importante papel na implementação de sistemas de
roteirização. Por um lado tem-se o desenvolvimento crescente de software e hardware que
permitem a execução dos algoritmos estruturados pela área de pesquisa operacional. Este fato
também é comprovado pelos inúmeros artigos que vêm sendo publicados ao longo dos anos
na literatura especializada. O precursor desse estudo foi o problema de roteirização do
caixeiro viajante (no inglês “traveling salesman problem” ou TSP) – Melamed (1990) e
Campello e Maculan (1994), que tem como objetivo precípuo estabelecer o roteiro ou
seqüência de cidades a serem visitadas por um caixeiro viajante, minimizando a distância total
percorrida e assegure que cada cidade seja visitada exatamente uma vez.
Abaixo é apresentada a cronologia dos eventos que permitiram o desenvolvimento de
algoritmos mais eficientes para a resolução dos Problemas de Roteamento de Veículos (PRV).
Devendo-se destacar que os recentes avanços nessa área foram propiciados em virtude dos
grandes avanços verificados na área de computação, ou seja, com computadores mais
eficientes e, por conseguinte capacidade de cálculo elevado os algoritmos mais específicos e
complexos foram desenvolvidos em sua plenitude.
Figura 1 – Principais trabalhos na área de programação linear.
Fonte: Goldbarg e Luna (2005).
17
Com o crescente avanço nos estudos que envolvem o desenvolvimento de métodos de
resolução mais eficientes para o Problema de Roteamento de Veículos (PRV) faz-se
necessário, para que a implementação dos algoritmos ocorra de forma eficiente, uma
compreensão maior dos cenários de roteirização em que esses métodos serão implementados.
O processo de adequação entre método e cenário de roteirização é de fundamental
importância, pois irá exercer um impacto considerável na qualidade do resultado obtido com a
roteirização. Além disso, o tempo de roteirização será reduzido consideravelmente permitindo
com que os processos subseqüentes a este sejam realizados com eficiência.
Com base nos elementos destacados anteriormente serão definidos a seguir os
objetivos delineados para o presente trabalho.
1.1 OBJETIVO DO ESTUDO
O presente trabalho tem como objetivo o desenvolvimento de análises comparativas
entre as alternativas de roteamento nos cenários de roteirização simulados para o presente
trabalho. Permitindo com isso estabelecimento da alternativa de roteamento que melhor se
adapta a determinado cenário de roteirização.
1.2 METODOLOGIA
O presente trabalho será dividido nos seguintes capítulos:
•
Capítulo 1: visão geral do problema de roteirização, o avanço nos métodos de
resolução e como o trabalho foi estruturado;
•
Capítulo 2: revisão bibliográfica contendo o embasamento teórico que servirá de
base para analisar as alternativas de roteirização relacionadas neste trabalho. Esse
embasamento teórico é estruturado sob os seguintes alicerces: teoria dos grafos,
visão ampla do problema de roteamento de veículos, complexidade do problema
de roteamento de veículos e métodos de resolução;
•
Capítulo 3: visão ampla da empresa que será utilizada como base para análise dos
cenários de roteirização e do software de roteamento que essa empresa utiliza;
18
•
Capítulo 4: exposição das etapas que permitiram a estruturação das análises
comparativas entre as alternativas de roteirização desenvolvidas nesse trabalho; e
•
Conclusões e recomendações: algumas conclusões extraídas das análises
desenvolvidas no trabalho e recomendações para estudos futuros.
2 REVISÃO BIBLIOGRÁFICA
Este capítulo contemplará toda a fundamentação teórica utilizada como base para
formação de análises em relação ao estudo de caso proposto para o presente trabalho.
Mediante a isso serão abordadas questões referentes a grafos, definição e modelagem do
problema de roteamento de veículos, métodos de resolução empregados para resolvê-lo e a
complexidade computacional inerente ao Problema de Roteamento de Veículos (PRV).
2.1 CONCEITOS FUNDAMENTAIS EM TEORIA DOS GRAFOS
Segundo Goldbarg e Luna (2005) o grafo pode ser definido como sendo uma
representação gráfica de interdependência entre elementos que são representados por nós.
Elementos que atendem à relação imaginada são simbolicamente unidos através de um traço
denominado “aresta”. O modelo possui uma interpretação gráfica muito confortável. Contudo
tal desenho não tem o poder, em várias situações reais, de formalizar completa e
satisfatoriamente a estrutura imaginada. De forma geral grafo é uma estrutura de abstração
que representa um conjunto de elementos denominados nós e suas relações de
interdependência ou arestas. Mediante a isso o grafo pode ser definido e representado
matematicamente conforme exposição abaixo.
Definição de Grafo: segundo Goldbarg e Luna (2005) grafo é definido como uma
estrutura de abstração que representa um conjunto de elementos denominados nós e suas
relações de interdependências ou arestas.
20
Representação Matemática: denominando X o conjunto de vértices da estrutura e A
o conjunto das arestas ou ligações o grafo pode ser representado por: G = (X, A), onde:
X = conjunto de nós X = {x1, x2, ..., xn}
A = conjunto de arcos A = {a1, a2, ..., am}
Quanto às linhas, o gráfico pode ser direcionado, ou seja, as linhas possuem uma
direção; não-direcionado, quando suas linhas não possuem uma direção ou misto com linhas
direcionadas e não-direcionadas.
As figuras a seguir ilustram os tipos de grafos:
Grafo direcionado
Grafo não-direcionado
Grafo misto
Figura 2 – Representação gráfica dos tipos de grafos.
21
Para uma melhor compreensão dos aspectos concernentes a grafos devem-se
considerar os seguintes elementos:
•
Caminho (direcionado): qualquer seqüência de arcos onde o vértice final de um é o
vértice inicial de outro;
•
Caminho simples: um arco não figura mais de uma vez;
•
Caminho elementar: o vértice não figura mais de uma vez;
•
Cadeia (não direcionado): qualquer seqüência de arestas na qual cada aresta é
conectada com suas arestas adjacentes através dos seus dois vértices terminais;
•
Grafo conexo: se existir entre quaisquer pares de nós do grafo G pelo menos uma
cadeia;
•
Custo (ou peso ou comprimento) de um caminho: se a cada arco for associado um
custo;
•
Circuito: é um caminho no qual o vértice inicial coincide com o inicial;
•
Circuito elementar: um vértice só aparece uma vez (exceto o final e o inicial que
são os mesmos);
•
Circuito Hamiltoniano: é um circuito elementar que contém todos os n vértices do
grafo G;
•
Ciclo: é uma parte não direcionada do circuito;
•
Grafo ponderado: um grafo G = (N, M) é ponderado se existem valores numéricos
associados a suas arestas ou nós;
•
Grafo rotulado: um grafo G = (N, M) é rotulado se existem atribuições associadas
a seus nós (tanto numéricas como alfabéticas);
•
Multigrafo: um grafo G = (N, M) é um multigrafo se existem mais de uma aresta
ligando o mesmo par de vértices;
•
Grafo bipartido: quando seu conjunto de nós, N, pode ser dividido em dois
conjuntos N1 e N2 tais que N1 ∩ N2 = 0 e N1
N2 = N e somente existem arestas
em G ligando algum nó de N1 com algum nó de N2 e vice-versa;
•
Ciclo Euleriano: Um ciclo que passa por todas as arestas; e
•
Ciclo Hamiltoniano: Um circuito que passa por todos os nós de G.
22
2.2 REPRESENTAÇÃO MATRICIAL DE UM GRAFO
O grafo pode ser representado matricialmente da seguinte forma:
•
Matriz de Adjacência: Para um grafo G (X, A), sua matriz de adjacência, denotada
por A= [aij] é definida como:
aij = {1, se o arco (Xi, Xj)
•
em G / 0, se o arco (Xi, Xj)
em G}
Matriz de incidência: Para um grafo G (X, A), sua matriz de adjacência, denotada
por B=[bij] é uma matriz n x m, onde m é o número de arcos, definida como:
bij = {1, se xi é o vértice inicial de aj / -1, se se xi é o vértice final de aj / 0, se xi
não é um vértice terminal de aj ou se a é um laço}.
Se G (X, A) for um grafo não direcionado, a matriz de incidência é definida como
acima, exceto trocando os “-1” por “1”.
2.3 GRAUS DE UM VÉRTICE
O grau de entrada é representado pelo número de arcos que xi tem como seu vértice
final, já o número de arcos que xi tem em seu vértice inicial representa o seu grau de saída.
Segundo Goldbarg e Luna (2005) alguns autores fazem distinção entre o conceito
de grau para grafos orientados e não orientados. No caso dos grafos orientados o grau pode
ser decomposto em duas parcelas: o grau interno ou o número de arcos chegando ao nó, e o
grau externo, ou o número de arcos partindo do nó. Essas parcelas do grau do nó são
denominadas semigrau. No caso dos grafos direcionados a soma do semigrau interior d(i)+ e
exterior d(i)- , conduz ao valor final do grau do nó. A expressão para obtenção do grau em
grafos orientados é:
d(i) = | d(i)- | + | d(i)+|
O grau do vértice 4 é:
d(4) = | d(4)-| + |d(4)+| = |-2| + |+2| = 4
23
1
6
3
4
2
5
7
Figura 3 – Representação gráfica do grau de vértice de um grafo.
2.4 DEFINIÇÃO DE REDE
Define-se rede como sendo um grafo direcionado atravessado por um fluxo que
circula em suas arestas. Na maioria das situações em uma rede temos dois nós que ganham
um maior destaque, a saber: o nó “fonte” e o nó “sumidouro”. Deve-se destacar que os arcos
da rede podem ser limitados em capacidade em relação ao fluxo. Além disso, esses mesmos
arcos podem impor custos à circulação do fluxo. De uma maneira geral uma rede poderia ser
representada conforme figura abaixo:
Nós intermediários
Nó fonte
Nó semidouro
Figura 4 – Representação da rede formada em um grafo.
24
2.5 OUTROS CONCEITOS BÁSICOS
Um dos aspectos fundamentais em grafos refere-se a ligação entre vértices. Diante
disso é essencial estabelecer vínculos ou ligações através das denominadas arestas ou arcos.
Para a compreensão da vizinhança entre os nós e arestas deve diferenciar-se o caso para o
grafo direcionado e não-direcionado.
2.5.1 Vizinhança entre vértices
Dizemos que dois vértices Xi e Xj são vizinhos ou adjacentes quando existe uma aresta
que liga Xi a Xj ou vice-versa.
2.5.2 Sucessores e Antecessores de um vértice
Dizemos que um vértice Xj é sucessor de Xi se existe pelo menos um arco ligando
Xi a Xj.
2.5.3 Fechos transitivos
Denomina-se por fecho transitivo direto do vértice x Î+ (x) (x), ao conjunto de vértices
que podem ser alcançados, a partir de x, através de sucessivas relações de vizinhança. A
figura a seguir descreve as possíveis relações de vizinhança entre os nós de um grafo.
Devendo-se destacar que as relações de vizinhança podem ocorrer em diferentes níveis, ou
seja, a relação não ocorre necessariamente entre dois nós que estão ligados diretamente,
podendo ocorrer entre um nó e outro que se encontra mais afastado deste.
25
11
5
2
6
12
7
1
13
8
3
9
10
4
Figura 5 – Representação gráfica do fecho transitivo direto de x
Analisando o grafo acima se podem constatar as seguintes relações: em relação ao
nó 1 este em um primeiro nível encontra-se relacionado aos nós 3 e 4; o nó 1 em um segundo
nível encontra-se relacionado aos nós 7, 8, 9 e 10; o nó 6 encontra-se relacionado aos nós 1, 2,
3, 4, 5, 11, 12 e 13; o nó 3 encontra-se relacionado aos nós 1, 2, 5, 4, 7 e 8.
2.6 O PROBLEMA DE ROTEAMENTO DE VEÍCULOS (PRV)
O termo roteamento de veículos constitui-se como o processo para a determinação de
um ou mais roteiros ou seqüências de paradas a serem cumpridos por veículos de uma frota,
objetivando visitar um conjunto de pontos geograficamente dispersos, em locais prédeterminados, que necessitam de atendimento. Além deste deve-se destacar o termo
roteirização de veículos que também é utilizado alternativamente por alguns autores.
Segundo Laporte (2000) o problema de roteirização de veículos consiste em definir
roteiros de veículos que minimizem o custo total de atendimento, sendo que cada um dos
quais deve iniciar e terminar no depósito ou base dos veículos, assegurando que cada ponto
26
seja visitado exatamente uma vez e a demanda em qualquer rota não exceda a capacidade do
veículo que a atende.
Em contrapartida segundo Cunha (1997) o Problema de Roteamento de Veículos
(PRV) envolve não só aspectos espaciais ou geográficos, mas também temporais, tais como
restrições de horários de atendimento nos pontos a serem visitados, os problemas são então
denominados roteirização e programação de veículos.
Para Christofides (1985) o problema de distribuição/roteamento de veículos é
considerado como sendo 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. Este tipo de problema encontra-se presente em
inúmeras situações através das quais se têm as necessidades de distribuir determinada(s)
mercadoria(s). Para alguns autores o Problema de Roteamento de Veículos (PRV) é
conhecido como “Programação de Veículos” (CLARK & WRIGHT, 1964; GASKEL, 1967),
“Despacho de caminhões” - “Trucks Dispatching” - (DANTZIG & RAMSER, 1959;
CHRISTOFIDES & EILON, 1964; KROLAK, 1972). Coexiste uma série de variações do
Problema de Roteamento de Veículos, nas quais as operações podem ser de coletas e/ou
entregas e o nível de serviço e os veículos podem assumir muitas variedades.
O roteamento de veículos constitui-se como um problema de otimização combinatória,
que tem como pressuposto básico arranjar o conjunto ótimo de rotas para determinada frota de
veículos de modo a servir um conjunto de clientes. Essa complexidade matemática dos
problemas de roteirização, assim como a sua relevância no contexto logístico atual, justifica o
constante interesse na busca de novas estratégias de solução. A importância dessa classe de
problemas está correlacionada à dificuldade de resolução e sua considerável relevância
prática. Uma alternativa para a resolução desses problemas é a utilização de métodos
heurísticos que visam encontrar uma solução em tempo computacional aceitável. Com relação
à relevância prática esta se deve a importância deste problema para empresas de bens e
serviços que objetivam distribuir um ou alguns produtos para satisfazer uma determinada
demanda que pode ser determinística (demanda conhecida) ou probabilística (demanda
desconhecida).
O Problema de Roteamento de Veículos (PRV) é considerado de natureza
combinatória devido ao espaço de soluções ser construído através de um agrupamento,
arranjo, seleção ou ordenação de objetos, normalmente finitos.
27
2.7 PROBLEMAS CLÁSSICOS DE ROTEAMENTO
Os principais problemas de roteamento de veículos, segundo BODIN (1983), são:
•
Problema do Caixeiro Viajante (PCV): tem-se como objetivo a elaboração de rotas
de mínimo custo que permitam ao caixeiro viajante visitar os nós (clientes) de uma
rede;
•
Problema do Carteiro Chinês (PCC): deve-se determinar um ciclo de custo mínimo
que permita ao carteiro passar ao menor uma vez por todos os arcos;
•
Problema dos Múltiplos Caixeiros Viajantes (PCVM): Vários caixeiros devem
visitar todos os nós da rede;
•
Problema de Roteamento de Nós com um Único Depósito e múltiplos Veículos
(PRDMV): Coexistem vários tipos de veículos, onde cada um desses deve atender
uma determinada área. Para isso será elaborada a rota com o menor custo e que
atenda a todos os clientes de uma determinada área;
•
Problema de Roteamento de Nós com Múltiplos Depósitos e múltiplos Veículos
(PRMDMV): Para esta situação existem vários depósitos e vários perfis de
veículos, ou seja, deve-se elaborar a rota com o menor custo e que atenda a todos
os clientes e retorne ao depósito pré-estabelecido para seu retorno;
•
Problema de Roteamento de Nós com Depósito Único, múltiplos Veículos e
Demanda Estocástica nos Vértices (PRDMVE): Para este caso temos vários
veículos e a demanda é estática, ou seja, a demanda é conhecida e, por conseguinte
teremos o número exato de veículo para atender a esta demanda; e
•
Problema do Carteiro Chinês Capacitado (PCCC): tem como objetivo definir rotas
para um conjunto de carteiros a fim de atender à demanda despertada no grafo G =
(V, E). Neste caso as restrições asseguram que o atendimento dos carteiros é
considerado em apenas uma das suas passadas pelo arco. O carteiro deve atender
os arcos que lhe forem designados a atender. Outras restrições devem garantir que
o atendimento dos diversos carteiros não ultrapasse sua capacidade.
28
2.8 CRITÉRIOS PARA A CLASSIFICAÇÃO DOS PROBLEMAS DE ROTEAMENTO DE
VEÍCULOS (PRV)
O output de qualquer sistema de roteirização e programação é basicamente estabelecer
para cada motorista e veículo uma rota e uma programação de entrega associada à mesma.
Neste caso a rota estabelece a seqüência de entregas a serem realizadas e a programação
determinada os horários em que ocorrerão as atividades de entrega e/ou coleta na área de
atendimento especificada. Uma das classificações clássicas é a proposta por Bodin e Golden
(1981). Segundo esses autores o Problema de Roteamento de Veículos pode ser classificado
segundo os seguintes critérios:
•
•
•
•
•
•
•
Tempo para servir um determinado nó ou arco:
•
Tempo especificado e prefixado.
•
Janela de tempo (Time Window).
Número de domicílios:
•
Um domicílio.
•
Mais de um domicílio.
Tamanho da frota de veículos:
•
Um veículo.
•
Mais de um veículo.
Localização dos veículos:
•
Em um único depósito.
•
Em vários depósitos.
Tipo de frota disponível:
•
Homogênea.
•
Heterogênea.
Natureza da demanda e parâmetros:
•
Determinística.
•
Estocástica.
Localização da demanda:
•
Nos vértices.
•
Nos arcos.
•
Arcos e nós.
29
•
•
•
•
•
•
•
•
Restrições junto aos clientes:
•
Necessidade ou não de atender toda a demanda.
•
Existência de clientes com prioridade.
•
Existência de janelas de tempo.
•
Tempo máximo permitido para carga/descarga.
•
Necessidade ou restrição de serviço em algum dia específico da semana.
Grafo de substrato:
•
Direcionado.
•
Não direcionado.
•
Misto.
Restrições dos veículos:
•
Com relação à autonomia de cada veículo.
•
Com relação ao tipo de carga.
•
Com relação à operação de carga e descarga.
Restrições aos veículos:
•
Limite de peso do veículo.
•
Limite de altura, largura e comprimento do veículo.
•
Restrições de carga e descarga.
•
Número de rotas permitido por veículo.
Restrições na capacidade de veículos:
•
Todos sujeitos as mesmas restrições.
•
Restrições diferentes.
Jornada de trabalho:
•
Duração.
•
Horário de almoço e outras interrupções.
•
Permissão para viagens com mais de um dia de duração.
Tempo de roteamento:
•
O mesmo para todos os veículos.
•
Tempos diversos.
•
Sem restrições de tempo.
Estrutura de custos:
•
Variáveis (associados à rota escolhida).
•
Fixos.
30
•
•
•
Pagamento dos tripulantes:
•
Por jornada de trabalho.
•
Por produtividade.
•
Jornada e horas extras.
Operação:
•
De entrega.
•
De recolhimento.
•
Ambas.
•
Coleta (ou entrega) com carga de retorno.
Tipo de carga:
•
•
•
•
Única.
Múltiplas cargas.
Necessidade de veículo especial para efetuar o transporte.
Objetivo:
•
Minimizar custos variáveis.
•
Minimizar custos fixos.
•
Minimizar soma de custos fixos e variáveis.
•
Minimizar duração das rotas.
•
Minimizar o número de veículos necessários.
•
Maximizar função de utilidade baseada no nível de serviço e/ou satisfação e/ou
prioridades dos clientes.
•
•
Balanceamento de rotas.
•
Minimizar o uso de frota fretada.
Restrições na capacidade dos arcos:
•
Imposta a todos os arcos.
•
Impostas a um subconjunto de arcos.
•
Sem restrições.
•
Número de tripulantes por veículo
•
Outras:
•
Necessidade de balanceamento da rota.
•
Existência de pontos de parada (descanso).
•
Proibição de contornos à esquerda por questões de segurança.
31
Assad (1988) menciona que a maior dificuldade para encontrar um esquema de
classificação adequado para problemas de roteirização deve-se a necessidade em se definir a
base que será utilizada para a classificação, ou seja, os requisitos do problema ou a técnica de
solução proposta. Outra possível classificação está baseada no tempo em que as informações
de demanda estão disponíveis. Nos problemas tradicionais supõe-se que a demanda é
conhecida (determinística), contrapondo-se a roteirização dinâmica na qual a demanda é
estocástica, ocorre em tempo real e é inserida no roteamento em andamento.
2.9 CLASSIFICAÇÃO DOS PRINCIPAIS PROBLEMAS DE ROTEAMENTO
DE
VEÍCULOS
Os problemas de roteamento de veículos podem ser subdivididos nas seguintes
categorias:
•
Problemas de Roteamento de Veículos sem restrição de janela de tempo: para esta
categoria não temos restrições temporais por parte dos clientes (ou seja, não há
nenhum horário pré-estabelecido para início e término de atendimento), não
existem relações de precedência entre os clientes (neste caso nenhum cliente
precisa ser atendido especificamente antes ou depois de algum determinado
cliente). Neste tipo de problema o objetivo é construir um conjunto de rotas
viáveis e de menor custo.
•
Problemas de Programação de Veículos: quando a definição das rotas deve levar
em consideração os horários pré-estabelecidos para cada atividade a ser executada
(horário limite para chegada e saída dos pontos de demanda, ou também o instante
programado para outras tarefas como, por exemplo, horário de saída do depósito,
parada para reabastecimento, etc). Sendo assim o processo de elaboração das rotas
levam em consideração, além dos aspectos espaciais dos problemas, também os
aspectos temporais.
•
Problemas Combinados de Roteamento e Programação de Veículos: quando existe
algum tipo de restrição de precedência e/ou janela de tempo. As relações de
precedência ocorrem quando a entrega de uma mercadoria deve ser precedida pela
sua coleta. Janelas de tempo são restrições horárias normalmente associadas ao
32
intervalo desejado para que um dado serviço seja executado num cliente. Podendo
existir outros tipos de janela de tempo, como, por exemplo, o intervalo de tempo
que um veículo fica disponível, ou o intervalo de tempo em que o depósito (ou
depósitos) fica disponível aos veículos. Em problemas combinados tanto os
aspectos espaciais quanto temporais são levados em consideração. Segundo Bodin
e Golden (1981) os problemas que ocorrem na prática normalmente estão nessa
categoria.
•
O Problema de Roteamento de Veículos (PRV) capacitado com demanda igual:
para este modelo considera-se o volume demandado como sendo igual entre os
pontos de demanda. Devendo-se destacar que os pontos de demanda são atendidos
conforme a capacidade de carregamento dos veículos, ou seja, a soma de todos os
pontos de demanda que estão sendo atendidos por um veículo deve ser inferior a
sua capacidade de carregamento.
•
O Problema de Roteamento de Veículos (PRV) capacitado com demanda desigual:
para este modelo considera-se que o volume demandado é desigual entre os pontos
de demandados. Conforme o modelo exposto anteriormente este também apresenta
restrição na capacidade dos veículos.
•
Problema de Roteamento de Veículos capacitado com restrição de janela de
tempo: para este modelo tem-se a restrição de capacidade dos veículos e janelas de
atendimento específicas para alguns consumidores.
Para todos os modelos expostos anteriormente o objetivo básico é a construção de
rotas que minimizem a distância percorrida, o tempo para a execução da operação de entrega
e o custo geral da rota para atender aos pontos de demanda.
2.10 O PROBLEMA DE ROTEAMENTO DE VEÍCULOS (PRV) BÁSICO E SUAS
EXTENSÕES
O problema básico de roteirização desconsidera uma série de restrições
freqüentemente encontradas em problemas ou situações reais. Algumas dessas restrições são
listadas a seguir:
33
•
Cada veículo pode estar presente em mais de uma rota, considerando que o tempo
total gasto de viagem deve ser inferior a um tempo T pré-determinado para aqueles
veículos;
•
Os clientes devem ser visitados durante seu horário de funcionamento (Janela de
Horário ou tempo);
•
O problema pode envolver tanto entregas quanto coletas. Podendo-se misturar
entregas e coletas em uma única rota ou pode ser estabelecido que o veículo deva
realizar primeiro todas as suas entregas e depois todas as coletas;
•
Não são só os clientes que apresentam janela de horário, os motoristas, enfim, a
equipe que trabalha nos veículos pode ter que cumprir uma janela de tempo de
trabalho restrito; e
•
O tempo de entrega pode ser subdividido nos seguintes tempos: tempo de descarga
(descarregar o produto do veículo), tempo de viagem, tempo de carregamento do
veículo no depósito e tempo de espera (aguardando o cliente por algum motivo,
como por exemplo, pagar pela mercadoria entregue).
Adicionalmente as restrições destacadas anteriormente existem algumas outras
considerações práticas que também ocorrem com certa freqüência, que não se ajustam
adequadamente ao Problema de Roteamento Básico (PRV). Devendo-se considerar que as
restrições consideradas no parágrafo anterior não alteram as características intrínsecas do
PRV básico, já as que são consideradas posteriormente não se ajustam ao PRV básico.
Algumas delas são:
•
Múltiplos depósitos: algumas empresas operam com mais de um depósito, ou seja,
um veículo pode sair de um depósito entregar e/ou coletar os produtos em todos os
clientes e retornar para outro depósito. Neste caso os depósitos não podem ser
considerados isoladamente. No momento em que o depósito tem sua própria frota
e área geográfica de atendimento, deve-se simplificar o problema de roteamento
em vários problemas similares de roteirização.
•
Nível de Serviço: pode existir uma série de fatores para atender as exigências do
consumidor, dentre eles: prazo de entrega curto (Janela de Horário de atendimento
específica para cada cliente), comportamento da equipe de entrega em relação aos
clientes, em que medida as solicitações do cliente são atendidas (dentro de quanto
34
tempo as solicitações são atendidas) e alguns incentivos promocionais (preços das
mercadorias comercializadas pela empresa).
•
Múltiplas Mercadorias: este se refere à multiplicidade de mercadorias, ou seja,
existem mercadorias que devem ser acondicionadas em uma determinada
temperatura e outras apresentam diferentes formas de serem carregadas nos
veículos. Este último aspecto deve-se aos diferentes tamanhos que as mercadorias
apresentam e com isso ocuparão diferentes espaços tanto no veículo quanto no
armazém ou central de distribuição.
•
Objetivos múltiplos e conflitantes: em algumas situações as empresas objetivam
atingir uma determinada meta que confronta com outra (trade-off). Por exemplo,
itens de produtividade estão diretamente relacionados à necessidade da equipe de
entrega em cumprir uma determinada Janela de tempo de trabalho prédeterminada. Em outras situações pode ser necessário cumprir um determinado
nível de serviço que pode ser obstruído por um pico na demanda, no qual a
empresa não consegue atender plenamente todos os clientes. Em uma situação em
que a frota fixa estabelecida não consegue atender a demanda pode ser necessário
a contratação de veículos extra para atender a esta demanda. Diante do fato a
necessidade pode ser em minimizar um dos seguintes fatores:
•
O número de veículos extras contratados.
•
A soma de clientes não servidos no dia de atendimento.
•
A distância total percorrida.
As variáveis expostas anteriormente têm seu nível de complexidade aumentado de
acordo com a natureza dinâmica do Problema de Roteamento de Veículos (PRV). Mediante a
isso se podem mencionar dois tipos de problemas de roteirização de veículos quanto ao grau
de dinamismo: o problema dinâmico de roteirização de veículos e o problema estático. Com
relação ao primeiro este apresenta como características básicas: as informações para o
planejamento das rotas não são totalmente conhecidas e a informação pode sofrer uma
modificação após a roteirização. Em contrapartida no problema estático temos como
características: todas as informações são conhecidas e não existe a possibilidade de uma
informação ser modificada após a roteirização. Além desses aspectos coexistem outros que
diferenciam esses dois tipos de problemas:
35
•
Dimensão tempo é essencial: para problemas com características dinâmicas o
tempo é uma dimensão essencial, já para problemas estáticos o tempo não é uma
dimensão essencial.
•
A questão do retorno a uma central de distribuição ou depósito: para os problemas
de característica dinâmica os veículos retornam a uma central de distribuição ou
depósito, já no caso dinâmico essa hipótese nem sempre ocorrerá e o processo
poderá ser ilimitado.
•
Informações futuras são imprecisas ou desconhecidas: uma parcela das
informações com relação à roteirização é imprecisa ou desconhecida para os
problemas de característica dinâmica, já para os problemas estáticos todas as
informações são conhecidas.
•
Um mecanismo que forneça informação atualizada é essencial: Esse mecanismo,
conforme exposto anteriormente, é essencial para problemas com características
dinâmicas.
•
Rapidez no tempo de processamento computacional é essencial: para problemas
com características dinâmicas, que se modificam conforme a inserção de
informações novas e/ou modificação de informações pré-existentes, faz-se
necessário um tempo de processamento computacional rápido, permitindo a
formulação rápida de soluções para o problema em questão.
•
As restrições referentes a tempo podem ser diferentes: Com relação aos problemas
de característica dinâmica estes podem ser mais frágeis com relação às restrições
de tempo do que os problemas com característica estática.
2.11 DESCRIÇÃO DO MODELO MATEMÁTICO DO PROBLEMA DE ROTEAMENTO
AMPLIADO
Essa descrição tem como objetivo descrever matematicamente o problema de
roteamento que será analisado no presente trabalho.
36
2.11.1 Em relação à estrutura da rede
Com relação à estrutura de rede esta se refere à descrição das variáveis que
comporão o grafo que representará as rotas do problema de roteamento. A seguir serão
descritas as variáveis que fazem parte do grafo referente ao modelo matemático do problema
de roteamento de veículos.
•
A: conjunto de arcos da malha viária.
•
S(i): conjunto de arcos que saem do nó i.
•
E(i): conjunto de arcos que chegam ao nó i.
•
I: conjunto de nós de transbordo (intermediários).
•
N: conjunto total de nós (localidades) existentes na malha.
•
CijF: custo de deslocamento do nó i para o nó j para veículos do tipo (A), (i, j U N).
•
Cijc: custo de deslocamento do nó i para o nó j para veículos do tipo (B), (i, j U N).
•
o(k): nó origem do pedido k.
•
d(k): nó destino do pedido k.
Devendo-se destacar que para o problema de roteamento que será abordado no
presente trabalho terá vários perfis de veículo, porém, para em nível de ilustração para o
modelo matemático do problema de roteamento de veículos serão apresentados somente dois
tipos de veículos.
2.11.2 Em relação aos veículos
Este se refere as variáveis que caracterizam os dois perfis de veículo existentes nesse
modelo matemático.
•
F: conjunto de veículos do tipo (A).
•
O: conjunto de veículos do tipo (B).
•
V: conjunto de veículos existentes, V = F ∪ O.
•
C: carga máxima de cada veículo do tipo F ou O.
37
2.11.3 Em relação aos pedidos
Compõem as variáveis relacionadas aos pedidos realizados pelos clientes. As variáveis
são as seguintes:
•
P: conjunto de requisições (pedidos) existentes a ser atendido.
•
Q: conjunto de cargas a ser entregue.
2.11.4 Em relação às variáveis de otimização
Estas representam as variáveis que comporão a função objetivo, que tem como meta a
minimização do custo. A seguir são descritas as duas variáveis.
•
xijkv = 1, se o pedido k
P passa pelo arco (i,j) utilizando o veículo do tipo (A) v
F e 0 caso contrário.
•
yijkv = 1, se o pedido k
P passa pelo arco (i,j) utilizando o veículo do tipo (B) v
O e 0 caso contrário.
Cada pedido k (k U P) é caracterizado por um par de nós origem/destino e por uma
commodity que deve ser transportada da origem até o destino através de arcos, utilizando-se
um determinado veículo v (v U V), com um custo de deslocamento associado conforme o tipo
de veículo utilizado. Tal pedido se enquadrará na seguinte possibilidade: uma carga qk U Q
deverá ser transportada de i para j.
38
2.11.5 Função objetivo
Minimize
(1)
(2)
(1) – Custo de transporte para veículos do tipo (A).
(2) - Custo de transporte para veículos do tipo (B).
2.11.6 Restrições de exclusividade
Continuidade de fluxo
Nó origem
Para cada nó origem de um pedido k, sempre haverá um e somente um veículo, tipo
(A) ou tipo (B), disponível para o seu atendimento. Logo, a diferença entre os somatórios de
tudo que sai e tudo que entra no nó origem é igual a 1:
Nó transbordo
Para cada nó transbordo para um pedido k, a diferença entre os somatórios de tudo que
sai e tudo que entra no nó transbordo é igual a 0:
39
Nó destino
Para cada nó destino para um pedido k, sempre haverá um e somente um veículo tipo
(A) ou tipo (B) chegando a esse nó, atendendo a esse pedido. Isto é, a diferença entre os
somatórios de tudo que sai e tudo que entra no nó destino é igual a –1:
2.11.7 Limitação no número de veículos
Sempre haverá um, e somente um, um veículo do tipo (A) ou tipo (B) atendendo ao
pedido k.
2.11.8 Restrições de capacidade
As restrições de capacidade são dadas pelas equações a seguir. Isto é, cada veículo do
tipo (A) pode transportar no arco (i,j) uma carga máxima inferior ou igual à Qv:
De forma semelhante, os veículos do tipo (B) também podem transportar no arco (i, j)
uma carga máxima inferior ou igual à Qv:
40
2.12 COMPLEXIDADE COMPUTACIONAL
O termo complexidade computacional relaciona-se com o estudo dos problemas e dos
algoritmos capazes de resolvê-los. Segundo Ziviane (2002), um algoritmo pode ser definido
como uma seqüência de ações executáveis para a obtenção de uma solução para um
determinado tipo de problema. Podendo coexistir uma diversidade de algoritmos capazes de
resolver um mesmo problema, com isso deve-se realizar a escolha do mais apropriado.
Para a identificação do algoritmo mais apropriado na resolução de um determinado
problema é necessário medir o custo de execução de cada candidato a resolução do problema.
Mediante a isso, é comum definir uma função de custo, ou função de complexidade f, onde
f(n) pode ser a medida de espaço de memória ou a medida de tempo, necessário para executar
um algoritmo para uma instância de tamanho n. No primeiro caso, f é chamada de função de
complexidade de espaço do algoritmo, enquanto que no segundo, f é chamada de função de
complexidade de tempo do algoritmo.
O custo para obter uma solução para um dado problema aumenta de acordo com o
tamanho n do problema. Em outras palavras, o tempo necessário para resolver o problema
cresce quando n cresce. Para visualizar este fato, considera-se o Problema do Caixeiro
Viajante com n municípios apresentado na tabela abaixo. Como alternativa de resolução temse o método de enumeração completa, que simplesmente lista todas as possíveis soluções
e escolhe a melhor delas. Como se pode constatar a partir de qualquer município, existe
(n – 1)! / 2 possíveis soluções para o problema (simétrico – versão onde as distâncias entre os
pares de municípios são as mesmas, independente do sentido viajado).
Tabela 1 – Tabela de tamanho do problema em relação ao tempo estimado para a resolução.
Fonte: Ziviane (2002).
41
Analisando-se os dados da tabela 1 pode-se notar que para uma pequena variação do
número de municípios ocorre uma variação gritante no tempo de resolução do problema.
Existem algoritmos melhores que o método de enumeração completa para a obtenção da
solução ótima do Problema do Caixeiro Viajante e de outros problemas.
Segundo Ziviane (2002) para valores pequenos de n, qualquer algoritmo custa pouco
para ser executado, em outras palavras, a escolha do algoritmo não é tarefa crítica para
problemas de tamanho pequeno. Sendo assim a análise de algoritmos é realizada para valores
grandes de n, estudando o comportamento de suas funções de custo para tais valores. Em
outras palavras, estuda-se o comportamento assintótico das funções de custo, que representa o
limite do comportamento do custo quando n cresce.
Para o estudo do comportamento assintótico utiliza-se a notação O que pode ser
formalizada da seguinte maneira: coloca-se que g(n) = O(f(n)) se existirem duas constantes
positivas c e uma inteira m tais que g(n) ≤ c • f(n) para n > m. Isto é, para valores de n
suficientemente grandes, g(n) não cresce mais rapidamente que f(n). Pode-se ler também, g(n)
é da ordem no máximo f(n).
Dessa forma os algoritmos podem então, ser avaliados a partir da comparação dos
seus comportamentos assintóticos. Um algoritmo com tempo de execução O(n) é melhor que
um algoritmo com tempo de execução O(n²). Contudo, constantes de proporcionalidade
podem gerar algumas exceções. Por exemplo, um algoritmo com tempo de execução 2n² pode
ser mais eficiente do que um algoritmo com tempo de execução 100n; isso ocorre para
instâncias de problemas com tamanho n < 50. Entretanto, para valores maiores de n o
algoritmo de complexidade O(n²) é muito mais lento que o algoritmo de complexidade O(n).
As principais funções de complexidade que definem o comportamento assintótico dos
algoritmos são apresentadas por Ziviani (2002) da seguinte maneira:
•
f(n) = O(1) (complexidade constante): O uso do algoritmo não depende do
tamanho de n suas instruções são executadas um número fixo de vezes.
•
f(n) = O(log n) (complexidade logarítmica): Este tipo de função ocorre em
algoritmos que resolvem um problema dividindo-o em problemas menores.
•
f(n) = O(n) (complexidade linear): Esse tipo de comportamento aparece em
algoritmos que realizam um pequeno trabalho em cada elemento de entrada.
42
•
f(n) = O(n log n) (complexidade n log n): Esse tipo de comportamento ocorre em
algoritmos que atacam um problema dividindo-o em problemas menores,
resolvendo cada um deles independentemente, ajuntando em seguida as soluções.
•
f(n) = O(n²) (complexidade quadrática): Esse tipo de função ocorre em algoritmos
em que os itens de dados são processados aos pares, muitas vezes em um laço
dentro do outro.
•
f(n) = O(n³) (complexidade cúbica): Algoritmos desta ordem de complexidade são
utilizados apenas para resolver pequenos problemas.
•
f(n) = O(2ⁿ) (complexidade exponencial): Esse tipo de função ocorre em
algoritmos que utilizam força bruta para resolver o problema.
•
f(n) = O(n!) (complexidade fatorial): Esse tipo de comportamento aparece em
algoritmos que listam todas as possíveis combinações para escolher a melhor,
como o método de enumeração completa utilizado no exemplo anterior do
Problema do Caixeiro Viajante.
Observando a tabela seguinte, pode-se visualizar a diferença de tempo entre algumas
funções de complexidade típicas para diferentes tamanhos de n, onde cada função expressa o
tempo de execução em micro segundos.
Função Complexidade
10
20
30
40
50
N
0,00001 s
0,00002 s
0,00003 s
0,00004 s
0,00005 s
n2
0,0001 s
0,0004 s
0,0006 s
0,00016 s
0,00025 s
n3
0,001 s
0,008 s
0,0027 s
0,0064 s
0,00125 s
n5
0,1 s
3,2 s
24,3 s
1,7 (min.)
5,2 (min.)
2n
0,001 s
1 (min.)
17,2 (min.)
12,7 (dias)
35,7 (anos)
3n
0,059 s
58 (min.)
6,5 (anos)
3855
2 x 108 (séc.)
tempo
(séculos)
Tabela 2 – Função complexidade tempo de algoritmos de tempo polinomial e exponencial, relacionado
ao tamanho da instância do problema.
Fonte: Garey e Johnson, 1979.
43
Um algoritmo polinomial é aquele que possui função de complexidade O(p(n)),
onde p(n) é um polinômio. Já um algoritmo exponencial, é aquele que possui função
de complexidade O(cⁿ), com c > 1. Devendo-se destacar também que a definição de
algoritmo exponencial inclui também outras funções de complexidade de tempo não
polinomiais, como por exemplo, n^log n, que normalmente não é considerada uma função
exponencial.
A partir da tabela anterior, pode-se perceber uma das razões que torna um algoritmo
polinomial mais desejável que um algoritmo exponencial. Os algoritmos polinomiais são tidos
como bons algoritmos, ou algoritmos eficientes, enquanto que, os algoritmos exponenciais
são classificados como ineficientes.
Contudo podem existir algumas exceções para tal classificação, que ocorrem
geralmente para instâncias de tamanho limitado. Por exemplo, o algoritmo de complexidade
2ⁿ é mais rápido que o algoritmo para n ≤ 20 (ver tabela anterior). De qualquer forma,
a distinção entre algoritmos eficientes e ineficientes torna-se mais significativa com o
aumento do tamanho de n.
Segundo Ziviane (2002) os algoritmos exponenciais são geralmente variações dos
métodos exaustivos, enquanto que os algoritmos polinomiais são concebidos através de um
entendimento maior das características do problema, fazendo com que eles sejam mais úteis
na prática do que os exponenciais. Apesar disso, existem algoritmos exponenciais que são
muito úteis na prática, como por exemplo, o Simplex, que possui complexidade exponencial
para o pior caso, mas que em média executa muito rápido.
Da mesma forma que um algoritmo pode ser classificado como bom ou ruim,
dependendo se ele possui ou não função de complexidade polinomial, os problemas podem
ser classificados como fáceis ou difíceis, dependendo se eles possuem ou não um algoritmo
polinomial capaz de resolvê-los.
Para o estudo da classificação dos problemas, a teoria da complexidade computacional
se restringe aos problemas de decisão, ou seja, problemas cujas soluções requerem apenas
sim ou não como resposta. Contudo, muitos problemas de otimização podem ser
naturalmente expressos como problemas de decisão, tal que se existir um algoritmo de tempo
polinomial para o problema de decisão, então existirá um também para a sua versão em
problema de otimização.
Como exemplo, pode-se gerar uma versão de problema de decisão para o Problema do
Caixeiro Viajante acrescentando um limite numérico como parâmetro adicional. Sendo que ao
44
invés de se estabelecer como objetivo gerar uma rota que passa por todas as cidades
percorrendo a menor distância, deve-se responder a seguinte questão: existe uma rota que
passa por todas as cidades com distância total que não seja maior que D? Constatando-se com
isso que a questão exige sim ou não como resposta, onde D é o nosso parâmetro adicional.
Embora a teoria tenha sido desenvolvida para os problemas de decisão, suas
implicações podem ser estendidas para os problemas de otimização. Lewis e Papadimitriou
(2000) realizaram um estudo detalhado sobre a classificação dos problemas. Os referidos
autores apresentam também o conceito de redução polinomial, necessário para o
entendimento de tal classificação.
Segundo Lewis e Papadimitriou (2000), o conceito de redução polinomial é
importante por revelar interessantes afinidades entre problemas computacionais. Pode-se dizer
que T é uma redução polinomial do problema V para o problema X quando T transforma, em
tempo polinomial, instâncias do problema V em instâncias do problema X, de maneira que Vi
é uma instância do problema V com resposta sim, se e somente se, T(Vi) for uma instância do
problema X que fornece a resposta sim.
A figura abaixo exemplifica o conceito de redução polinomial descrito por Lewis e
Papadimitriou (2000).
Figura 6 – Redução polinomial
Fonte: Lewis e Papadimitriou (2000)
Quando existe uma redução Polinomial de V para X, pode-se dizer que X é no mínimo
mais complexo que V. Se existir um algoritmo polinomial para X, esse método também
resolverá V em tempo polinomial. Se V exigir um tempo exponencial, então X exigirá um
tempo pelo menos exponencial.
45
2.13 CLASSIFICAÇÃO DOS PROBLEMAS DE DECISÃO
Grande parte dos problemas de decisão associados a problemas de interesse prático,
derivados ou não de problemas de otimização, pertencem às seguintes classes:
•
Classe P (Polynomial time): Um problema X pertence à classe P se ele pode ser
resolvido por um algoritmo de tempo polinomial.
•
Classe NP: Um problema X pertence à classe NP quando ele admite, ou apresenta
um certificado. Um certificado deve ser polinomialmente sucinto, ou seja, seu
comprimento deve ser dado no máximo, pelo valor de um polinômio sobre o
comprimento da cadeia de entrada; ele também deve ser verificável em tempo
polinomial.
•
Classe NP-Completo: Um problema X pertence à classe NP-Completo se ele for
pertencente classe NP e se qualquer outro problema V também pertencente à classe
NP puder ser reduzido polinomialmente a X. Em outras palavras, X é NPCompleto quando está em NP, e para qualquer V em NP, um algoritmo para
resolver X pode ser adaptado em tempo polinomial para resolver V (ver ilustração
anterior).
•
Classe NP-Difícil (NP-Árduo ou NP-Hard): Um problema X pertence à classe NPDifícil se qualquer outro problema V pertencente à classe NP puder ser reduzido
polinomialmente a X. Note que aqui, X não necessariamente pertence à classe NP.
Um problema NP-Difícil é pelo menos tão difícil quanto qualquer problema em
NP. A classe P está contida em NP. No entanto, existem muitos problemas em NP
para os quais não são conhecidos algoritmos que os resolvam em tempo
polinomial. Por isso não se sabe se P = NP; existe uma forte conjectura de que P ≠
NP, embora isso não tenha ainda sido provado.
A figura a seguir expõe como ocorre a configuração das classes de problemas
descritos anteriormente.
46
Figura 7 – Provável configuração das classes.
Fonte: Garey e Johnson, 1979.
2.14 ALTERNATIVAS DE ROTEIRIZAÇÃO PARA O PROBLEMA DE ROTEAMENTO
DE VEÍCULOS (PRV)
Este capítulo tem como objetivo apresentar as alternativas de roteirização para o
problema de roteamento de veículos (PRV). As heurísticas serão esmiuçadas em todas as suas
etapas de resolução, permitindo com isso uma melhor compreensão das análises comparativas
que serão realizadas em etapas subseqüentes.
2.14.1 Métodos heurísticos
Heurísticas podem ser definidas como uma técnica que busca boas soluções, ou seja,
próximo das ótimas, com um custo computacional (tempo) aceitável. Sendo que em muitos
casos não declara o quão próximo uma solução encontra-se da ótima.
A complexidade computacional de resolução dos problemas de roteamento de veículos
exposta acima e a forma de modelar os problemas precisamente, uma vez que as heurísticas
são mais flexíveis e aptas a operar com funções objetivo e restrições mais complicadas, faz
com que as heurísticas coloquem-se como os métodos de resolução mais acertados para
resolver os problemas de roteamento de veículos. Nesse caso tem-se um maior benefício com
uma solução aproximada de um modelo exato.
47
Christofides (1985) classifica as heurísticas para problemas de roteamento de veículo
da forma que será descrita abaixo.
Nos métodos construtivos a solução é estruturada com base em algumas etapas na
qual a rota é construída de forma seqüencial ou paralela. Esses métodos foram desenvolvidos,
em sua maioria, por Clark e Wright (1964). Tendo em vista que este método é simples e
flexível.
No método de Clark e Wright (1964) supõe-se inicialmente que cada cliente seria
atendido por um veículo, porém, esta configuração é inviável. Diante disso o algoritmo avalia
a possibilidade, em termos de economia em distância, em se atender um par de clientes por
intermédio de uma rota.
Para uma melhor compreensão do método de Clark e Wright (1964) a seguir serão
apresentados graficamente como esse processo de construção de rotas é realizado e a
economia obtida a cada etapa.
Rota 1
Rota 2
i
j
0
Rota 1'
i
j
0
S – refere-se à distância total percorrida, ou seja, na rota um' temos a economia descrita
acima.
S = d(i,0) + d(0,i) + d(0,j) + d(j,0)
S = d(i,0) + d(0,j) - d(i,j)
Figura 8 – Representação gráfica do método de Clark e Wright.
48
Com a inserção de um cliente a rota temos a rota 1' que gerou a economia em distância
verificada anteriormente. Neste caso é avaliada a possibilidade de inserção de um nó de
acordo com a economia que esta inserção gerará.
Outro método de construção de uma solução inicial é o do vizinho mais próximo que
se baseia na escolha dos pontos de demanda mais próximo a ser atendido constituindo-se
como uma heurística gulosa, já que busca a melhor inclusão local. Tem-se também o método
da varredura no qual uma reta é traçada partindo-se de uma origem e a mesma gira em um
determinado sentido formando grupo de pontos de demanda que serão futuramente
roteirizados com base em um algoritmo que formará uma seqüência de atendimento tendo
como base a proximidade entre os pontos de demanda. Como último exemplo pode-se
mencionar a heurística seqüencial de inserção Push Forward de Solomon (1987), nesta é
considerada as restrições de janela de tempo, calculando-se o efeito que determinado ponto de
demanda teria ao ser inserido na rota.
O método das duas-fases é baseado na lógica agrupa-roteiriza ou roteiriza-agrupa.
Neste método temos os trabalhos de Tyagi (1968) e Christofides (1979). No caso do Tyagi
(1968) os pontos de demanda são agrupados com base no conceito do vizinho mais próximo,
ou seja, o cliente a ser adicionado é o mais próximo do último que foi adicionado. Com
relação à Christofides (1979) tem-se a utilização de um algoritmo de melhoramento nas duas
etapas (agrupamento dos clientes e formação da seqüência de atendimento).
No método de otimização incompleta temos um algoritmo branch and bound,
transformando em uma heurística através da fase prematura, ou seja, são utilizados algoritmos
aproximativos que garantem uma solução viável sem garantia de otimalidade.
Devendo-se destacar que de acordo com Fisher e Jaikumur (1981) as heurísticas que
vem sendo desenvolvidas para a resolução do problema de roteamento de veículos são
modificações de heurísticas para o problema do caixeiro viajante. Com isso é adicionada mais
uma categoria as heurísticas para problema de roteamento de veículos, a saber: método de
melhorias. Essa nova categoria tem como objetivo precípuo a redução gradativa do custo da
rota. Para isso baseia-se em três conceitos fundamentais: mecanismo para alterar a solução
inicial, estratégias de soluções alternativas e critério da parada. A solução é
melhorada/aperfeiçoada por intermédio de trocas sucessivas de arestas visando à redução
do custo da rota. Esses métodos são denominados como heurísticas de busca local. Para isso
têm sido propostos vários mecanismos de melhoria das rotas, dentre esses o mais utilizado é o
49
r-opt, onde r é o número de arestas a serem trocadas. Nesse processo de geração de soluções
por intermédio da troca de arestas o objetivo é encontrar uma solução superior a anterior,
no momento que não houver mais possibilidade de melhorias tem-se a solução denominada
r-ótima. Devendo-se destacar que quanto maior o valor de r melhor será a solução obtida,
porém, maior será o tempo computacional empregado. Para uma melhor compreensão de
como o mecanismo r-opt funciona temos a representação gráfica realizada posteriormente.
Rota 1
Rota 2
a
a
b
d
c
e
0
b
d
c
e
0
Figura 9 – Representação gráfica do método r-opt da troca de nós na rota
A aplicação do movimento 2-opt a rota 1 provoca a inserção de dois clientes a rota e a
mudança ma seqüência da mesma, com isso esta solução foi aperfeiçoada comparativamente a
primeira solução na qual a rota atendia os nós com um custo superior à segunda. Mediante a
isso se tem a eliminação das arestas (a,0) e (d,c) e a adição das arestas (d,a) e (c,0).
Contrapondo-se a heurística de trocas de arestas limitadas r-opt Dror e Levy (1986)
desenvolveram um método que propõe operações de trocas e inserção de nós a sistemas com
m rotas.
Posteriormente a essas heurísticas de trocas e inserção de nós o conceito foi estendido
para λ-troca (OSMAN, 1989; CHRISTOFIDES, 1994), onde são considerados movimentos
50
de um número, a princípio, arbitrário de nós que podem ser inseridos ou trocados entre
quaisquer pares de rotas. Contudo essas múltiplas trocas que venham a ocorrer pode tornar o
tempo computacional de resolução do problema impraticável. Além disso, coexiste a questão
que refere-se ao ótimo local que é alcançado nesse tipo de heurística e que como é de
conhecimento em problemas combinatoriais nem sempre o ótimo local é o ótimo global. A
alternativa para lidar com esse tipo de problema está na utilização de metas-heurísticas que
objetivam superar a otimalidade local e alcançar soluções de qualidade superior.
2.14.2 Heurística de Bellmore e Nemhauser
No ano de 1968 foi publicado um estudo de Bellmore e Nemhauser sobre o Problema
do Caixeiro Viajante. Dentre os teoremas, métodos e técnicas de solução, os autores
apresentaram uma heurística construtiva que elege um vértice inicial de maneira arbitrária e
na seqüência inclui outros vértices no circuito em formação, seguindo o critério de escolha do
vértice ou vizinho mais próximo (Bellmore e Nemhauser).
A complexidade dessa heurística é O(n²). Existindo uma variação elaborada para
minimizar o efeito da influência da escolha do vértice inicial. Nela, o algoritmo é repetido
para todos os possíveis vértices candidatos ao início do processo. Nesse caso, a heurística
passa a ter complexidade O(n³). Devendo-se considerar que mesmo com algumas variações da
regra de escolha do vizinho mais próximo, o algoritmo pode ser escrito da seguinte forma:
•
Etapa 1: um vértice inicial será selecionado, encontre o vértice mais próximo dele
e inicie a construção do circuito por intermédio da ligação desses dois extremos;
•
Etapa 2: agora o objetivo é encontrar o vértice mais próximo de um dos vértices
extremos incluídos na solução; este vértice deve ser inserido na rota em construção
ligando-o com o seu vizinho mais próximo;
•
Etapa 3: caso todos os vértices tenham sido incluídos, complete com a aresta que
liga os vértices extremos e o processo será finalizado; e
•
Etapa 4: caso contrário deve-se retornar ao passo 2.
51
Pode-se exemplificar a execução dos passos dessa heurística fazendo uso do cenário
incluído na próxima figura, onde as distâncias entre os vértices são as seguintes: ab=15,
ac=25, ad=36, ae=37, af=56, bc=13, bd=23, be=29, bf=45, cd=11, ce=17, cf=32, de=18,
df=25, ef=20. Os valores apresentados correspondem à distância aproximada, em milímetros,
entre os centros dos vértices que formam os pares relacionados.
Figura 10 – Heurística de Bellmore e Nemhauser passo a passo.
Observando a figura anterior, nota-se que a primeira etapa da heurística é executada
com a escolha do vértice inicial c, seguido da ligação deste com o seu vizinho mais próximo
d. A rota passa então a ser expandida a partir da execução do passo 2, aonde o vizinho mais
próximo de um dos vértices extremos da solução vai sendo localizado e incluído no circuito
em formação. Os passos 3 e 4 da heurística estão relacionados com a verificação da formação
de um circuito hamiltoniano para prosseguir ou parar com a execução do algoritmo. No final
do processo, encontra-se na figura presente no quadro F um circuito hamiltoniano de custo
igual a 133 mm.
2.14.3 Heurística de Clark e Wright (CW)
A heurística das economias de Clarke e Wright (CW) (1965), bastante conhecida e
ainda muito utilizada como parte de outros procedimentos, foi originalmente desenvolvida
52
para resolver o problema clássico de roteamento de veículos. Essa heurística baseia-se na
noção de economias, que pode ser definido como o custo da combinação, ou união, de duas
sub rotas existentes.
Inicialmente, cada cliente é servido por um veículo, constituindo rotas entre o depósito
e cada cliente. Seja cij o custo de viagem partindo de um cliente i a um cliente j, podendo ser
dado em distância percorrida ou tempo de deslocamento. Segundo definição de Liu e Shen
(1999), duas rotas contendo os clientes i e j podem ser combinadas, respeitando-se as
seguintes condições: desde que i e j estejam ou na primeira ou na última posição de suas
respectivas rotas e que a demanda total das rotas combinadas não ultrapasse a capacidade do
veículo.
Em cada iteração, todas as combinações de rotas possíveis são analisadas através da
fórmula sij = ci0 + c0j - cij, onde 0 representa o depósito. As duas rotas que obtiverem a maior
economia de combinação são unidas. Como a cada nova combinação de sub-rotas as
economias são novamente calculadas e atualizadas para a próxima combinação de sub-rotas, o
método é considerado iterativo.
Segundo Goldbarg e Luna (2005) a partir do momento em que as rotas vão sendo
unidas, a distância total a ser percorrida pela frota vai diminuindo. No momento em que uma
rota vai se expandindo, ou seja, vai sendo mesclada com outras, alguns vértices passam a ficar
desligados do depósito; tais vértices são chamados de vértices internos e não são mais
candidatos a melhoria na rota, uma vez que para união das rotas só são testados os vértices
externos, ou seja, aqueles que possuem ligação com o depósito. Em alguns momentos, isso
pode ser encarado como uma fragilidade do algoritmo.
Segundo Cordeau (2002), o algoritmo se mostrou bastante simples e rápido, sendo
fácil de codificar, principalmente pela ausência de parâmetros.
Segundo Laporte e Semet (2002) um dos pontos fracos do algoritmo original de
Clarke e Wright (1965) é que ele tende a produzir boas rotas de início, mas ao se aproximar
do final, realiza uniões que podem produzir rotas menos interessantes. Além disso, para
algumas instâncias o algoritmo pode consumir um perceptível tempo de processamento para
calcular, ordenar e armazenar a lista de economias.
Em contrapartida outros pesquisadores observaram que a solução construída
apresentava baixa qualidade e um grande número de rotas longas circunferenciais. Por essa
razão, a deficiência em flexibilidade é considerada a pior característica do algoritmo.
53
Com base nessas afirmações foram apresentadas algumas melhorias para o algoritmo
CW, sendo uma delas a utilização de economias generalizadas na forma sij = ci0 + c0j - λcij,
buscando produzir rotas mais compactas, sendo λ um parâmetro positivo.
A aplicabilidade dessa heurística está associada à possibilidade em não se estabelecer
o número de veículos, podendo ser utilizada em duas versões: tanto na versão seqüencial
quanto na versão paralela. Conforme as rotas vão sendo expandidas rumo a uma solução de
melhor qualidade, é possível realizar os testes relativos às restrições do problema. Os passos
do algoritmo na sua versão seqüencial podem ser descritos da seguinte forma:
•
Etapa 1: inicie pelo depósito que corresponde ao vértice V0.
•
Etapa 2: para todos os demais vértices são criadas pequenas rotas saindo de V0,
passando, por exemplo, por Va e retornando a origem V0.
•
Etapa 3: nessa etapa deve-se obter a lista de economias relacionando o vértice V0
(corresponde a origem) e todos os possíveis pares de vértices restantes do grafo.
Como exemplo, tem-se o par de vértices Va e Vu onde a economia calculada fica
da seguinte forma: E = Ca0 + C0u – Cau, onde E representa a economia realizada se
o vértice Va for ligado ao vértice Vu sem passar pelo vértice origem V0.
•
Etapa 4: as listas de economias serão ordenadas de forma decrescente (da maior
para a menor economia).
•
Etapa 5: estabeleça uma rota que pode ser expandida.
•
Etapa 6: a lista de economias será percorrida, iniciando pela primeira da lista, e
selecione a primeira economia que pode ser usada para expandir a rota eleita no
passo anterior, respeitando as restrições do problema.
•
Etapa 7: nessa etapa será efetuada a união das rotas, por exemplo, através da
inserção da aresta (Va, Vu) e a remoção das arestas (Va, V0) e (V0,Vu), expandindose com isso a rota eleita no passo 5, por fim deve-se remover a economia utilizada
da lista de economias.
•
Etapa 8: caso a rota possa ainda ser expandida deve-se repetir o passo 6.
•
Etapa 9: caso existam rotas a serem expandidas volte ao passo 5.
A versão seqüencial percorre várias vezes as listas de economias na tentativa de
expandir uma única rota antes de iniciar a expansão da próxima contraponham-se a versão
paralela que percorre a lista de economias apenas uma vez, tentando realizar a expansão de
54
uma ou mais rotas até que a lista seja finalizada. Os passos do algoritmo da versão paralela
podem ser descritos da seguinte forma:
•
Etapa 1: idêntico ao da versão seqüencial.
•
Etapa 2: idêntico ao da versão seqüencial.
•
Etapa 3: idêntico ao da versão seqüencial.
•
Etapa 4: idêntico ao da versão seqüencial.
•
Etapa 5: a lista de economias será percorrida da primeira posição e ocorrerá a
tentativa de união das rotas, por exemplo, por intermédio da inserção da aresta
(Va,Vu) e a remoção da aresta (Va,V0) e (V0,Vu), sendo que as restrições do
problema devem ser respeitadas.
•
Etapa 6: caso não seja possível usar a economia selecionada para a união das rotas,
deve-se tentar usar a próxima economia da lista.
•
Etapa 7: o procedimento deve ser repetido até que a lista seja percorrida até o final.
2.14.4 Procedimentos de melhoria
Esses procedimentos de melhoria para o Problema de Roteamento de Veículos (PRV)
operam em uma rota específica ou em várias rotas ao mesmo tempo. No primeiro caso será
aplicada a heurística λ-Opt faz parte do grupo das heurísticas de melhoria, que são estratégias
que partem de um circuito hamiltoniano inicial e tentam melhorá-lo a partir de trocas na
ordem em que os vértices serão visitados pelo caixeiro viajante. Segundo Lin (1965) para a
realização de tais trocas deveriam ser procuradas arestas no circuito inicial para serem
retiradas e substituídas por outras que gerassem um circuito hamiltoniano de menor custo.
Segundo Lin (1965) podem ser encontradas soluções que podem ser denominadas
como de λ ótimas, para λ = 2, 3,..., n arestas ou arcos do grafo. Por exemplo, uma solução é
considerada "2 ótima" (2-Opt) quando não conseguimos mais melhorá-la substituindo dois
arcos do circuito por outros dois arcos. Já uma solução é considerada 3-Opt quando não
conseguimos melhorá-la através da substituição de três ou duas arestas do circuito.
Generalizando, uma solução é considerada λ-Opt quando não conseguimos melhorá-la
substituindo λ arestas do circuito; uma solução λ-Opt é ainda uma solução λ-Opt, onde λ’ < λ.
55
Para uma melhor compreensão dos procedimentos de melhoria as etapas desse
algoritmo são descritas a seguir:
•
Etapa 1: o circuito hamiltoniano será obtido a partir de uma heurística qualquer.
•
Etapa 2: devem ser removidas arestas do circuito inicial.
•
Etapa 3: todas as possibilidades de combinações de λ serão testadas para a
reconstrução do circuito hamiltoniano.
•
Etapa 4: caso sejam encontradas um conjunto de λ arestas que remontam o circuito
com tamanho menor em relação ao anterior, a troca será efetivada.
•
Etapa 5: deve-se agora retornar ao passo 2 até que não haja mais nenhuma melhora
a ser obtida.
Para casos em que λ é maior do que 3 são verificadas todas as possíveis substituições
de λ arestas até não existir mais nenhuma troca que melhore a solução. Entretanto, o número
de operações necessárias para esse procedimento cresce rapidamente com o aumento do
número de vértices do grafo. Diante disso, valores de λ=2 e λ=3 são mais utilizados, sendo
que soluções obtidas com λ=3 são geralmente melhores do que as obtidas com λ=2. Na figura
seguinte podemos observar exemplos de movimentos de troca utilizados nas heurísticas 2-Opt
e 3-Opt.
Figura 11 – Exemplificação dos movimentos 2-opt e 3-opt.
56
Conforme apresentados anteriormente os procedimentos de melhoria para o problema
de roteamento de veículos – PRV operam em uma rota específica ou em várias rotas ao
mesmo tempo. No primeiro caso (rota específica), qualquer heurística de melhoria para o
problema do caixeiro viajante – PCV pode ser aplicada, como por exemplo, a heurística λ-Opt
de Lin (1965), demonstrada nas etapas anteriores. Já para o segundo caso (várias rotas),
trabalhos como os de Dror e Levy (1986), Salhi e Rand (1987), Waters (1987), Fahrion e
Wrede (1990), fornecem uma descrição de uma série de estratégias que utilizam combinações
de métodos com algumas operações elementares de trocas de vértices entre rotas. Tais
operações podem ser exemplificadas da seguinte forma:
•
Troca de vértices: dois grupos de k vértices são trocados entre duas rotas; no
exemplo a seguir k=1 e a troca ocorre com o uso dos vértices w e e, sendo que as linhas claras
correspondem aos arcos substituídos nas operações.
Figura 12 – Demonstração gráfica da troca de vértices para mais de uma rota
O algoritmo pode ser descrito da seguinte forma:
Troca de vértices (k=1)
•
Etapa 1: uma solução inicial será gerada, devendo-se guardar em um vetor a
identificação de cada rota.
•
Etapa 2: percorra o vetor de rotas da primeira até a penúltima posição.
•
Etapa 3: para cada incremento realizado do passo anterior, percorra o vetor de
rotas do índice posterior ao obtido no passo 2 até a última posição.
57
•
Etapa 4: percorra os vértices da rota indicada pelo passo 2.
•
Etapa 5: para cada incremento do passo 4, percorra os vértices da rota do passo 3.
•
Etapa 6: análise da possibilidade de troca de rotas para os vértices indicados nos
passos 4 e 5 segundo ilustração anterior, se a troca for vantajosa e não ferir
nenhuma restrição do problema, a operação será efetivada.
•
Inserção de vértices: um grupo de k vértices é movido de uma para outra rota; no
exemplo seguinte k=1 e a rota (a, b, c, d, e, f) cedeu, ou doou o vértice e para a outra.
Novamente, as linhas claras correspondem aos arcos substituídos.
Figura 13 – Demonstração gráfica da inserção de vértices entre duas rotas
Para a rotina de inserção de vértices identificamos as rotas como doadoras e
receptoras. Cada rota terá o seu momento de doadora e tentará inserir um de seus vértices
(com exceção do depósito) em uma das restantes rotas receptoras. O algoritmo pode ser
descrito da seguinte forma:
•
Etapa 1: a solução inicial será gerada e guardada em um vetor apenas para a
identificação de cada rota.
•
Etapa 2: percorra o vetor de rotas da primeira a última posição (rota doadora).
•
Etapa 3: para cada incremento realizado do passo anterior, percorra o vetor de
rotas da primeira até a última posição (rota receptora).
•
Etapa 4: caso os índices dos contadores dos passos 2 e 3 sejam diferentes, deve-se
executar os passos seguintes.
58
•
Etapa 5: percorra os vértices da rota doadora.
•
Etapa 6: para cada incremento do passo 5 que ocorrer, percorra os vértices da rota
receptora.
•
Etapa 7: para cada um dos vértices da rota doadora procure na rota receptora um
par de vértices adjacentes que forneça a melhor posição para inserção do
candidato, tendo como critérios a não violação de nenhuma restrição do problema
e a consideração de quão vantajosa será essa inserção.
Além das operações ilustradas anteriormente, foram utilizadas trocas de três vértices
(um vértice de uma rota e um par de vértices adjacentes de outra), e quatro vértices (dois
pares de vértices adjacentes de rotas diferentes). Os procedimentos foram combinados e
ordenados, com base em resultados obtidos, da seguinte maneira: 1. 2-Opt; 2. Troca de dois
pares adjacentes; 3. Troca de um vértice mais um par de adjacentes; 4. Troca de vértices; 5.
Inserção ou doação de vértice.
Analisando-se as ilustrações descritas anteriormente, nota-se que para realizar a troca
de um vértice de uma rota com um de outra rota é necessário remover quatro arestas e incluir
quatro novas arestas. Para a operação de doação de vértice é necessário remover três arestas e
incluir três novas arestas. De uma forma geral, para efetivar a operação deve-se satisfazer a
seguinte condição:
Custo das arestas removidas – Custo das arestas incluídas > 0
2.14.5 Heurística de Gillet e Miller (Primeiro-agrupa e segundo-roteiriza)
A Heurística de Gillett e Miller (1974) faz parte do grupo das heurísticas de duas
fases, que utilizam a estratégia de dividir o problema em partes para resolvê-lo. Na primeira
fase dessa heurística, os vértices são organizados em grupos segundo um critério de
proximidade. Na segunda fase cada grupo é solucionado de forma independente, onde os
grupos correspondem às rotas a serem construídas. Para agrupar os vértices, é realizada uma
varredura circular a partir do depósito central, na qual os vértices vão sendo escolhidos de
acordo com o ângulo de sua coordenada polar em relação ao depósito, respeitando as
59
restrições do problema. Em seguida, as rotas são obtidas através da solução do PCV para cada
grupo de vértices. Os passos do algoritmo podem ser descritos da seguinte maneira:
•
Etapa 1: considere o depósito como a origem do sistema de coordenadas polares,
para cada um dos vértices calcule suas coordenadas polares tomando como base o
depósito e guarde-as em uma lista.
•
Etapa 2: ordene a lista contendo as coordenadas polares dos vértices em ordem
crescente de ângulo.
•
Etapa 3: agora percorra essa lista iniciando pelo topo e siga agrupando os vértices
até que alguma restrição, de capacidade, por exemplo, seja transgredida.
•
Etapa 4: o grupo formado será armazenado em um vetor e será iniciado um novo
grupamento a partir do vértice que violou a restrição, siga com a varredura até o
final da lista.
•
Etapa 5: no momento em que a lista for esgotada, obtenha as rotas resolvendo de
maneira exata ou aproximada o referido problema para cada um dos grupos
encontrados.
A ilustração descrita abaixo demonstra as duas fases dessa estratégia. Na célula A, os
grupos de vértices são organizados a partir da varredura circular. Na célula B, as rotas são
construídas a partir da solução do Problema do Caixeiro Viajante (PCV) para cada um dos
grupos escolhidos na primeira fase.
Figura 14 – Representação gráfica da heurística de Gillet e Miller.
60
Para a formação do grupo de vértices (pontos de demanda) pode-se utilizar a noção do
vértice-território, ou seja, os vértices podem pertencer a territórios específicos que serão
agrupados a fim de serem roteirizados (seqüência de entregas) posteriormente. Com o
objetivo de complementar os aspectos descritos anteriormente será descrito a seguir de forma
matemática o algoritmo de Gillet e Miller (1974).
Segundo Goldbarg e Luna (2005) o algoritmo de Gillet e Miller (1974) pode ser
descrito matematicamente da seguinte forma:
INÍCIO
Ler G = (N, A), cij . {*Nó1 é o depósito central do roteamento}
Obter as coordenadas polares dos clientes em relação ao depósito e ordená-las em
ordem de crescimento de seu valor e Fazer:
Início
F: = N \ {x1}
Ponta_Rota = {x1}
Rota1 : = {x1}
i: = 1
Fim
Enquanto F ≠ 0 Faça {“Agrupar”}
Início
Enquanto xs F atendendo as condições de viabilidade para rotai
Início
Encontrar o vértice
xs
F de coordenada polar mais próxima da
Ponta_Rota e Fazer
Início
Rotai: = Rotai {xs}
Ponta_Rota: = {xs}
F: = F \ {xs}
j: = j + 1
Se Controle (j) = Verdadeiro então aplicar Procedimento kótimo (Rotai) {*Rotear*}
Fim
Fim
61
i:= i + 1
Ponta_Rota: = {x1}
Rotai : = {x1}
Fim
Fim
2.14.6 Método de primeiro-roteiriza e segundo-clusteriza
Segundo Goldbarg e Luna (2005) este método realiza a operação inversa da anterior.
A primeira etapa da abordagem busca a identificação de uma rota (normalmente inviável) que
englobe todos os pontos de demanda. Em uma segunda fase o circuito é particionado em
pequenas rotas viáveis. Esse método é aplicado em problemas nos quais o número de veículos
é livre. Os passos desse método serão descritos abaixo:
•
Etapa 1: na primeira etapa agrupam-se todos os pontos de demanda em uma rota,
que é normalmente inviável.
•
Etapa 2: o circuito é particionado em pequenas rotas viáveis.
•
Etapa 3: as rotas viáveis que serão formadas devem respeitar as restrições impostas
ao Problema de Roteamento de Veículos e em relação aos parâmetros impostos
para o problema, como por exemplo: número de entregas, tempo máximo em rota,
distância percorrida, tempo máximo de deslocamento demais fatores que colocarão
limites para as rotas em formação.
2.14.7 Algoritmo de Fisher e Jaikumar (1981)
O algoritmo de Fisher e Jaikumar pode ser descrito da seguinte forma:
•
Etapa 1: Escolha dos grupos de vértices jk em V para inicializar cada cluster k.
•
Etapa 2: (Alocação dos consumidores para os grupos). Registrar o custo dik de
alocação de cada consumidor i para cada cluster k como dik = min (c0i + cijk + cjk0,
c0jk + cjki + ci0) – (c0jk + cjk0).
62
•
Etapa 3: (transferência generalizada). Resolver um Problema de Transferência
Generalizada (GAP em inglês) com custo dij, demanda dos consumidores qi, e
veículo de capacidade Q.
•
Etapa 4: (Solução do Problema do Caixeiro Viajante). Resolver um Problema do
Caixeiro Viajante para cada cluster correspondente com a solução do Problema de
Transferência Generalizada.
Para este algoritmo o número de veículo é fixado a priori. Os autores propuseram um
método geométrico baseado na partição do plano dentro de K cones de acordo com as
demandas dos consumidores. Uma vez que os clusters tenham sido determinados, os
problemas do caixeiro viajante são resolvidos otimamente usando uma abordagem baseada
em relaxação da restrição.
2.14.8 Heurística de Mole e Jameson
Em 1976, Mole e Jameson apresentaram uma heurística construtiva seqüencial, em
que o critério utilizado para expandir uma rota pela inclusão de novos vértices conta com duas
condições:
•
C1(i, k, j) = Dik + Dkj - µDij
•
C2(i, k, j) = λD0k - C1(i, k, j)
A primeira condição é responsável por encontrar a melhor posição para inserção de
cada vértice candidato ainda não roteado. A segunda condição é responsável pela seleção do
vértice que será incluído pelo movimento de expansão. Nas condições existem dois
parâmetros, µ e λ, que podem receber valores diferentes, fazendo com que sejam geradas rotas
de diferentes formatos e composições.
O algoritmo dessa estratégia pode ser descrito através dos seguintes passos:
•
Etapa 1: caso todos os vértices estejam incluídos nas rotas formadas o processo
será finalizado, caso contrário inicie uma nova rota (0,k,0) onde k representa o
vértice que não está contido nas rotas existentes.
63
•
Etapa 2: para a expansão da rota, deve ser encontrado para cada vértice k não
roteado o custo de inserção C1*(ik,k,jk) = min {C1(r,k,s)} para todo par adjacente
de vértices r e s da rota em formação, onde ik e jk fornecem o mínimo custo para a
primeira condição, caso não haja inserções possíveis retorne ao passo 1.
•
Etapa 3: com os valores mínimos de C1encontrados para cada vértice no passo
anterior, procure o melhor vértice candidato K* para inserção, satisfazendo a
expressão C2*(ik*,k*,jk*) = max {C2(ik,k,jk)}; o candidato k* será inserido entre
os vértices ik* e jk*.
•
Etapa 4: como último passo será aplicada uma heurística λ- Opt na rota em
formação e retorne ao passo 2.
A figura seguinte mostra um exemplo de um movimento de expansão do algoritmo.
Figura 15 – Representação gráfica da heurística de Mole e Jameson
Com o objetivo de desenvolver os cálculos relacionados acima foram utilizados
valores que representam as distâncias, em milímetros, entre os centros dos vértices do grafo.
São eles: D0a=18, D0b=26, D0c=29, D0d=13, D0e=29, D0f=37, Dab=41, Dac=47, Dad=29,
Dae=47, Daf=41, Dbc=13, Dbd=29, Dbe=29, Dbf=58, Dcd=26, Dce=18, Dcf=54, Dde=18, Ddf=29 e
Def=39.
64
Analisando-se a célula B, nota-se que o vértice a, por exemplo, pode ser inserido entre
os pares adjacentes 0c, 0f, cd e df. Contudo a melhor posição de inserção é obtida com o par
de vértices que minimizará o custo da primeira condição, com isso para o vértice em questão,
a melhor posição é entre os vértices 0 e f. Deve-se destacar que o vértice e foi escolhido para
ser inserido entre o vértice c e o vértice interno d. Esse é um dos pontos positivos dessa
heurística em relação à heurística de Clarke e Wright, onde a rota é expandida apenas a partir
de um de seus vértices extremos.
2.14.9 Heurística construtiva de Solomon (1987)
Marius Solomon (1987) desenvolveu uma heurística construtiva que inclui a restrição
de janelas de tempo nas decisões de seleção de sementes e de posição de inserção dos clientes.
Dentre a multiplicidade de variantes propostas por Solomon, descreve-se aquela que
proporcionou o melhor resultado para os problemas teste:
•
Etapa 1: defina dois conjuntos, um conjunto de clientes inseridos (I) e outro
conjunto de clientes não inseridos (NI) e coloque todos os clientes no conjunto NI.
•
Etapa 2: faça I = vazio.
•
Etapa 3: Ache o próximo cliente-semente (c_semente). Há duas opções:
•
Cliente mais distante do depósito: considera que clientes distantes do depósito são
mais difíceis de serem inseridos.
•
Cliente com o menor tempo final da janela de tempo: prioriza clientes que devem
ser atendidos com maior urgência.
•
Etapa 4: faça I = I
c_semente e NI = NI – c_semente.
•
Etapa 5: procure em NI o cliente i que ao ser inserido na rota de c_semente
proporciona o menor acréscimo de custo, respeitando as restrições de capacidade e
de janela de tempo. Para tanto, teste todas as posições de inserção do cliente e
selecione a melhor posição de inserção.
•
Etapa 6: insira o cliente i na rota de c_semente.
•
Etapa 7: faça I = I
•
Etapa 8: retorne ao passo 6 enquanto houver clientes a serem inseridos na rota de
i e NI = NI – i.
c_semente.
•
Etapa 9: volte ao passo 4 enquanto NI ≠ vazio.
3 ESTUDO DE CASO
O capítulo referente ao estudo de caso visa descrever a infra-estrutura logística no
âmbito brasileiro da empresa distribuidora de bebidas de forma geral e a estrutura funcional
presente na geografia do Rio de Janeiro. Além disso, tem-se como objetivo a exposição dos
resultados que foram obtidos por intermédio das análises que foram realizadas com base na
revisão bibliográfica.
3.1 VISÃO NO ÂMBITO BRASIL DA EMPRESA DISTRIBUIDORA DE BEBIDAS
A empresa distribuidora de bebidas é subdivida no âmbito brasileiro com base na
localização geográfica das áreas de atendimento. Para isso denominam-se cada região como
sendo uma geografia que congrega áreas próximas de atendimento. Cada uma dessas
geografias apresenta metas específicas, que se relacionam as características da sua operação.
As geografias subdividem-se da seguinte forma:
•
Geografia Sul: Apresenta as seguintes centrais de distribuição: Porto Alegre,
Sapucaia, Pelotas, Caxias do Sul e Florianópolis;
•
Geografia Rio de Janeiro: Apresenta as seguintes centrais de distribuição:
Campos dos Goytacazes, Jacarepaguá, São Cristóvão e Campo Grande;
•
Geografia Norte: Apresenta as seguintes centrais de distribuição: Fortaleza, São
Luís e Bacanal;
•
Geografia Minas Gerais e Espírito Santo: Apresenta as seguintes centrais de
distribuição: Uberlândia, Uberaba, Vitória, Contagem e Belo Horizonte;
66
•
Geografia São Paulo-Centro: Apresenta as seguintes centrais de distribuição:
Mooca, Diadema, Paulínia e Oeste paulista;
•
Geografia do Centro-Oeste: Apresenta as seguintes centrais de distribuição:
Manaus e Brasília;
•
Geografia Paraná e interior de São Paulo: Apresenta as seguintes centrais de
distribuição: Agudos, Araraquara, Ribeirão Preto, Curitiba e Londrina;
•
Geografia nordeste: Apresenta as seguintes centrais de distribuição: Olinda,
Caruaru, João Pessoa, Natal, Maceió e Aracaju;
•
Geografia Bahia: Apresenta as seguintes centrais de distribuição: Vitória da
Conquista, Ilhéus, Feira de Santa, Salvador e Jequié.
Dentre as geografias especificadas anteriormente as próximas considerações irão
circunscrever-se a geografia Rio de Janeiro e posteriormente em relação a central de
distribuição de Jacarepaguá.
3.2 ESTRUTURA FUNCIONAL DAS UNIDADES PERTENCENTES À GEOGRAFIA
RIO DE JANEIRO DA EMPRESA DISTRIBUIDORA DE BEBIDAS
A geografia Rio de Janeiro é composta por: 1 fábrica de bebidas e quatro centrais de
distribuição. A fábrica é localizada em Campo Grande e as quatro centrais de distribuição em:
Jacarepaguá, São Cristóvão, Campo Grande e Campos dos Goytacazes. Com essas quatro
centrais de distribuição tem-se o atendimento do estado do Rio de Janeiro.
Cada central de distribuição apresenta a estrutura organizacional que será descrita a
seguir:
•
Área de logística: Composta pelo coordenador de distribuição, o gerente de
operações e distribuição, coordenador do armazém, supervisores de distribuição e do
armazém, analistas de controle e do armazém e os técnicos em roteirização. Esta área tem
como objetivo precípuo realizar com os menores custos e um elevado nível de serviço a
entrega dos produtos comercializados pela empresa. Para isso tem-se a gestão das operações
de armazenagem e compra dos produtos, gestão das rotas de entrega (identificando as
67
anomalias que vem ocorrendo, procurando corrigi-las) e o estabelecimento de uma relação de
parceria com a empresa transportadora.
•
Área de vendas: Composta pelo gerente de distribuição direta, gerentes de vendas,
os supervisores de vendas e os vendedores. A área de vendas tem como objetivo estar
presente periodicamente em todos os pontos de venda para a comercialização dos produtos da
empresa, visando compreender de forma clara quais são as necessidades dos clientes. Esta
área também realiza a negociação de preços junto aos consumidores e promoções visando a
alavancagem em suas vendas. Além disso, esta área desenvolve a previsão de vendas que se
coloca como pilar principal para a estruturação de todas as metas da área de logística de uma
forma geral.
•
Área de marketing: Com relação à área de marketing esta trata essencialmente de
como a empresa é visualizada no mercado e de que forma os consumidores vêem os produtos
comercializados pela empresa. Além disso, trata da questão de patrocínios a eventos
realizados ou não pela empresa e como os produtos da empresa estão sento expostos nos
pontos de venda, orientando os pontos de venda a posicionar todo o material de exposição da
empresa em pontos estratégicos, permitindo com isso uma visualização clara e objetiva por
parte dos consumidores em relação aos produtos comercializados pela empresa.
•
Área de Recursos Humanos: Suporte em recrutamento, seleção e treinamento de
todos os funcionários da empresa.
•
Área Administrativo-Financeiro: Apuração de resultados, suporte em informática,
faturamento, gestão de riscos e cadastro de clientes e análise das informações referentes à
situação financeira dos mesmos. Essa área é subdividida da seguinte forma: tecnologia da
informação – suporte na manutenção dos computadores e nos sistemas fornecedores de
informações gerenciais, faturamento – emissão de notas fiscais e relação de entrega contendo
a seqüência de clientes a serem atendidos e os produtos que cada cliente comprou e a área de
riscos – trata essencialmente da estruturação de ações que visam a mensuração e a prevenção
de prejuízos financeiros em relação a produtos que chegam avariados da fábrica e de produtos
que se encontram avariados no armazém. Além disso, a área de riscos trata, juntamente com a
68
equipe de rastreamento, da mensuração e prevenção no roubo das cargas distribuídas pelos
caminhões.
•
Centro de assistência técnica: realiza a manutenção dos equipamentos
disponibilizados pela empresa ao cliente.
•
Central de monitoramento: realiza o monitoramento dos veículos que estão
realizando as entregas na rua, enviando para os analistas de rota e supervisores de distribuição
informações referentes a devolução de produtos, problemas de pagamento do cliente, quantas
entregas faltam para a o término da rota e demais informações pertinentes a execução das
entregas aos clientes.
Dentre as áreas descritas anteriormente as considerações a seguir ficarão circunscritas
à área de logística, em virtude do objetivo central do presente trabalho estar direcionado para
a presente área, mas especificamente ao processo que permite a entrega dos produtos aos
clientes. Com relação às centrais de distribuição o presente trabalho terá como foco a área de
atendimento da central de distribuição de Jacarepaguá. Essa área e a infra-estrutura logística
para atendê-la serão apresentadas nos tópicos subseqüentes a este.
3.3 ÁREAS DE ATENDIMENTO
DA
CENTRAL
DE
DISTRIBUIÇÃO
DE
JACAREPAGUÁ
A central de distribuição de Jacarepaguá tem sua área de atendimento circunscrita a
parte da Zona Norte e Oeste do Rio de Janeiro.
Devido ao tamanho e complexidade quanto às características de atendimento da área
da central de distribuição de Jacarepaguá, ocorre a subdivisão desta área no software de
roteirização em duas sub-áreas: área de roteirização 8 e área de roteirização 3. Essas áreas
encontram-se descritas na figura abaixo, posteriormente será apresentada uma visão geral da
área de atendimento da central de distribuição de Jacarepaguá. Devendo-se considerar que os
pontos em amarelo representam os pontos de venda e o ponto em vermelho a central de
distribuição de Jacarepaguá.
69
Figura 16 – Área de roteirização 8.
Figura 17 – Área de roteirização 3.
70
No entanto, deve-se destacar que essa área de atendimento sofreu uma modificação
considerável a partir de 14/08/2006, quando foi efetivada a retirada de duas partes dessa área
de atendimento. Essa mudança teve como objetivo desobstruir em termos logísticos a central
de distribuição de Jacarepaguá. As áreas foram para a central de distribuição de Campo
Grande e São Cristóvão. Abaixo é apresentada a área de atendimento geral antes dessa
mudança. Posteriormente são apresentadas as áreas de atendimento que foram para a central
de distribuição de Campo Grande e São Cristóvão respectivamente.
Figura 18 – Área de atendimento antiga (antes de 14/08/2006) da central de distribuição
de Jacarepaguá.
71
Figura 19 – Área de atendimento que passou a ser atendida pela central de distribuição
de Campo Grande.
Figura 20 – Área de atendimento que passou a ser atendida pela central de distribuição
de São Cristóvão.
72
As áreas que foram para a central de distribuição de Campo Grande e São Cristóvão
compreendem as seguintes regiões: entre o metrô da Pavuna e a Av. Nazaré – Campo Grande
e o bairro de Sampaio e o morro do Jacarezinho – São Cristóvão.
Com a mudança a área de atendimento da central de distribuição de Jacarepaguá
ficou conforme a figura abaixo.
Figura 21 – Área de atendimento atual da central de distribuição de Jacarepaguá.
3.4 INFRA-ESTRUTURA ORGANIZACIONAL E LOGÍSTICA DA CENTRAL DE
DISTRIBUIÇÃO DE JACAREPAGUÁ
Atualmente, em termos de infra-estrutura logística, a central de distribuição de
Jacarepaguá opera em sua área de logística com uma frota de 100 caminhões da frota fixa e 20
caminhões pertencentes à frota extra (freteiros – contratados por viagem de acordo com o
volume de vendas). Esses 100 caminhões apresentam os seguintes perfis: 10 baias alto, 10
baias rebaixado, 8 baias alto, 8 baias rebaixado, 6 baias alto, 6 baias rebaixado, 12 baias
aberto, carreta e 8 baias aberto.
73
Com relação a equipe de trabalho tem-se: 1 gerente de operações e distribuição GOD, 1 coordenador de distribuição, 1 supervisor de distribuição, 4 analistas de rota, 1
coordenador de armazém, 3 supervisores de armazém, 60 conferentes (realizam o
carregamento do caminhão), 1 analista de armazém, dois controllers (registram e analisam a
quantidade de produtos que entra e sai da central de distribuição) e dois técnicos em
roteirização que utilizam o software de roteirização para realizar a seqüência de entregas de
cada caminhão.
GOD
Coord. Armazém
Sup. Armazém
Sup. Armazém
Coord. Distribuição
Sup. Armazém
Controller
Conferentes
20
Confe
rentes
Conferentes
20
Supervisor Distrib.
Analista
Controller
Controller
Conferentes
20
Analista de Rota
(I)
Analista de Rota
(II)
Analista de Rota
(III)
Analista de Rota
(IV)
Analista de Rota
(V)
Analista de Rota
(VI)
Tec. Roteirização (I) Tec. Roteirização (II)
Figura 22 – Organograma da área de logística da central de distribuição de Jacarepaguá.
3.5 MACRO FLUXO DE OPERAÇÕES
O macro fluxo de operações congrega todas as etapas pertinentes ao processo de
entrega de produtos da empresa distribuidora de bebidas, ou seja, desde o momento em que
ocorre a venda do produto até a entrega deste ao cliente.
Inicialmente será exposta uma visão ampla do macro fluxo de operações para que
posteriormente sejam apresentados seus fluxos internos principais: fluxo entrega rota,
recebimento puxada, carregamento e fluxo de roteirização.
74
Partindo de uma visão geral do macro fluxo de operações temos os seguintes fatores
principais que o compõe e suas respectivas funções:
•
Vendas: processo através do qual o vendedor visita os pontos de venda e digita o
pedido do cliente em seu palmtop. Após essa etapa o vendedor retorna a central de
distribuição, comparece até a área de tecnologia de informação e descarrega as informações
de vendas inseridas no palmtop no sistema integrado de gestão, com o objetivo de que essas
informações de vendas sejam inseridas na grade que contemplará todos os pedidos realizados
no dia da venda.
•
Financeiro: recebimento do arquivo contendo todos os pedidos de compra dos
clientes e com isso é encerrado o processo de descarga de informações de venda do palmtop
dos vendedores no sistema integrado de gestão (“corte do link”). Como etapa subseqüente
efetua-se a crítica dos pedidos, ou seja, todos os clientes que apresentarem alguma pendência
financeira com a empresa não terão sua compra efetuada. Além disso, o financeiro realiza a
emissão das notas fiscais, boletos de pagamento e no momento em que o veículo retorna a
central de distribuição após realizar as entregas ocorrem o processo de prestação de contas
financeiras, que visa comparar o valor das mercadorias que o caminhão tinha de entregar aos
clientes em relação ao dinheiro que a equipe de entrega trouxe.
•
Entrega: roteirização e escala de equipes. Após o processo de roteirização realiza-
se a geração de uma série de relatórios gerenciais – planejamento e controle de distribuição –
PCD que visam fornecer informações com relação à operação de entrega.
•
Armazém: Nas etapas iniciais do macro fluxo de operações o armazém realiza a
gestão da grade de estoque que visa comparar quais foram os produtos vendidos e suas
respectivas quantidades demandadas em relação aos que se encontram disponíveis no
armazém. Esse processo de verificação está diretamente relacionado à programação de
puxada, que se refere ao processo de abastecimento da central de distribuição. Nas etapas
subseqüentes ocorre a separação das relações de entrega (mapas), contendo a seqüência de
clientes a serem entregues no dia por caminhão, ou seja, cada relação de entrega contém a
seqüência de clientes a serem atendidos por um caminhão no dia entrega. Além disso, deve-se
destacar que no retorno dos caminhões a central de distribuição o armazém realiza a
conferência física do caminhão que seria o processo de verificar se houve devolução de
produtos e se os produtos que apresentam embalagens retornáveis não sofreram nenhum tipo
de avaria durante o trajeto.
75
Para permitir uma melhor compreensão dos fatores mencionados acima e como estes
interagem entre si tem-se a seguir a exposição gráfica do fluxo de macro operações da
empresa distribuidora de bebidas. Nesse fluxo deve-se destacar que algumas etapas do
processo de entrega e armazém são qualificadas como sendo críticas, ou seja, são etapas que
exercem um impacto considerável na operação como um todo.
Figura 23 – Representação gráfica do macro fluxo de operações
Após a exposição do macro fluxo de operações devem-se descrever os principais
fluxos que ocorrem no interior desse macro fluxo e que permitem a entrega dos produtos aos
pontos de venda.
3.5.1 Fluxo entrega rota
O fluxo entrega rota refere-se à etapa que congrega todo o processo diretamente
relacionado à entrega dos produtos pela empresa distribuidora de bebidas, ou seja, todos os
fatores e situações que se vinculam ao processo de entrega. Neste caso o processo inicia-se
com a preparação para saída em rota que congrega a conferência da carga transportada e das
notas fiscais e termina no retorno a central de distribuição para a prestação de contas físicas e
76
financeiras. Esse fluxo opera da seguinte forma: o motorista ao chegar ao PDV confere
juntamente com o cliente a quantidade de produto demandada e o valor da nota fiscal, caso
não haja nenhuma anomalia o PDV irá receber a mercadoria e a equipe de entrega irá conferir
o vasilhame e apurar o refugo, ou seja, a equipe verificará se o PDV tem o mesmo número de
vasilhames com a marca da bebida que a equipe estará entregando neste PDV e se as garrafas
de bebidas não apresentam alguma avaria. No entanto, se houver alguma anomalia e o PDV
não receber a mercadoria a equipe de entrega deve entrar em contato com o analista de rota e
o supervisor da transportadora. A partir deste momento o fluxo pode ser direcionado para a
possibilidade de o PDV aceitar em refugar as garrafas e do vasilhame ser suficiente para a
realização da entrega. Por fim se não houver mais nenhuma anomalia equipe de entrega
continuará a seqüência de entregas sem maiores problemas. A seguir o fluxo encontra-se
graficamente esmiuçado, com o objetivo de permitir uma compreensão mais aprofundada em
relação ao fluxo entrega rota.
Figura 24 – Representação gráfica da primeira etapa do Fluxo Entrega Rota.
77
Figura 25 – Representação gráfica da segunda etapa do Fluxo Entrega Rota.
Figura 26 – Representação gráfica da terceira etapa do Fluxo Entrega Rota.
78
Figura 27 – Representação gráfica da quarta etapa do Fluxo Entrega Rota.
Com o objetivo de finalizar a exposição do fluxo entrega rota tem-se a tabela abaixo
que coloca como o processo deve ser executado pela equipe de entrega.
Figura 28 – Descrição das etapas principais do fluxo entrega rota.
79
3.5.2 Fluxo recebimento de Puxada
Esta etapa refere-se ao recebimento da mercadoria proveniente da fábrica, conferência
em termos de quantidade, se existem avarias nas mercadorias recebidas na central de
distribuição e demais ações de registro de avarias/medidas a fim de que a transportadora
venha a ressarcir a empresa distribuidora de bebidas. O fluxo encontra-se descrito
graficamente abaixo em duas etapas: fluxo de recebimento da puxada e armazenagem.
Figura 29 – Representação gráfica da primeira etapa do fluxo recebimento da puxada
Figura 30 – Representação gráfica da segunda etapa do fluxo recebimento da puxada
80
3.5.3 Fluxo do carregamento
Os fluxos referentes ao carregamento subdividiram-se em duas etapas: carregamento
dos caminhões e blitz do carregamento.
Figura 31 – Representação gráfica da primeira etapa do Fluxo do carregamento.
Figura 32 – Representação gráfica da segunda etapa do Fluxo do carregamento.
81
3.5.4 Fluxo retorno de rota
Este fluxo refere-se à etapa de prestação de contas físicas e financeiras que visam
apurar as quantidades físicas e financeiras do caminhão no momento que este chega a central
de distribuição. Abaixo se descreve graficamente a seqüência de etapas pertencentes a esse
fluxo.
Figura 33 – Representação gráfica da primeira etapa do fluxo de retorno de rota.
Figura 34 – Representação gráfica da segunda etapa do fluxo de retorno de rota.
82
3.5.5 Fluxo de roteirização
O fluxo de roteirização refere-se ao processo de importação do arquivo de pedidos e,
por conseguinte geração automática de rotas, por intermédio do software de roteirização.
Abaixo é descrito o fluxo de roteirização em todas as suas etapas e as eventuais
decisões a serem tomadas com relação à produtividade das rotas.
Figura 35 – Descrição do fluxo de roteirização
3.6 SOFTWARE DE ROTEIRIZAÇÃO
O software de roteirização constitui-se como a ferramenta utilizada para a geração das
rotas contendo um determinado número de clientes atendidos por um veículo específico.
Além disso, por intermédio de determinadas alternativas de roteirização as rotas são geradas
com o objetivo de atingir-se o menor custo total em quilometragem percorrida e tempo.
O software de roteirização em questão apresenta algumas características específicas
que serão descritas a seguir.
83
3.6.1 Ambiente de roteirização
O software de roteirização que será analisado no presente trabalho apresenta como
layout de roteirização o mapa da área de atendimento. Sobre as ruas e avenidas dessa área é
criada a chamada malha viária que se refere à conexão do mapa com as características em
relação a mãos de direção, velocidade de via e horário do rush pela manhã e pela tarde, ou
seja, a malha viária permite a caracterização das ruas e avenidas no software, objetivando com
isso a criação dos trajetos pelo mesmo.
Abaixo é apresentado o ambiente de roteirização com a malha viária que, como foi
colocado anteriormente, deve caracterizar fielmente as características de ruas e avenidas.
Figura 36 – Ambiente de roteirização
Deve-se destacar na figura exposta anteriormente que os pontos verdes representam
pontos de venda e os amarelos representam pontos de conexão da malha viária, ou seja, são
pontos indicativos de que o veículo deve passar por esse ponto para atender um outro grupo
de clientes. Nesse caso esses pontos representam as esquinas das ruas e avenidas.
Outro aspecto importante a ser destacado desse software é que o mesmo utiliza, como
84
uma das estratégias de roteirização, a associação e determinados números específicos
(territórios) aos clientes. O objetivo de associarem-se territórios aos clientes tem como foco
determinado qual perfil de caminhão irá atender determinado cliente.
3.6.2 Gerenciador de dados
O gerenciador de dados representa todas as informações referentes ao cadastro dos
produtos, frota de veículos da empresa, cadastro de motoristas/ajudantes e perfil dos veículos
cadastrados.
3.6.2.1 Cadastro de produtos
O cadastro de produtos apresenta todos os produtos inseridos na base de informações
do software de roteirização. A unidade de produto utilizada pelo software de roteirização é a
dúzia. As conversões de todos os produtos para uma unidade comum foram feitas com base
no vasilhame de cerveja. As conversões foram realizadas da seguinte forma: foram
mensurados durante vários dias quantos vasilhames de todos os produtos comercializados pela
empresa cabem em 1 baia do caminhão, após essa mensuração foi constatado que 42
vasilhames cabem em 1 baia. Na conversão para dúzias foi realizado o seguinte:
multiplicaram-se os 42 vasilhames por 2 e obteve-se 84 dúzias. Para os outros produtos a
conversão seria feita da seguinte forma: quantidade de vasilhames de cerveja 600 ml que
cabem em 1 baia dividido pela quantidade de vasilhames do outro produto que cabem em uma
baia. Em seguida multiplica-se esse valor por dois e obtém-se a conversão em dúzias do
referido produto.
3.6.2.2 Cadastro de veículos da empresa
Informações referentes a todos os veículos da central de distribuição com os
respectivos motoristas e ajudantes de cada veículo.
85
3.6.2.3 Cadastro de motoristas e ajudantes
Contém a informação de todos os motoristas e ajudantes presentes na central de
distribuição com suas respectivas remunerações.
3.6.2.4 Perfil dos veículos cadastrados
Apresenta o perfil de todos os caminhões da central de distribuição, ou seja, quanto
cada veículo pode transportar custo por hora e quilometragem e a capacidade volumétrica e de
peso dos caminhões. Abaixo são apresentados todos os perfis de veículos existentes na central
de distribuição e suas respectivas capacidades. Além disso, cada veículo apresenta uma
denominação de tipo que é representada por uma letra do alfabeto. Considerando que todos os
caminhões são de 3 eixos excetuando-se os tipos A, K, F e L, que são de dois eixos.
Tipo
Perfil
Capacidade (dúzias)
A
A BAU 8 PALLETES
672
B
B TRUCK DE CHOPP
1512
D
D BAU 10 PALLETES
840
F
F MB 914 ABERTA
360
H
H TRUCK 10 PALLETS REBAIXADO SPOT
812
I
I BAU 10 PALLETES REBAIXADO
784
J
J BAU 8 PALLETES REBAIXADO
616
K
K TOCO 8 PALLETS ABERTO
560
L
L MB 914 BAU
420
Tabela 3 – Perfil de veículos utilizados pela central de distribuição de Jacarepaguá
3.6.3 Parâmetros
São responsáveis por observar e respeitar características pré-estipuladas para as rotas.
Sendo possível a criação de diferentes conjuntos de parâmetros de roteirização para diferentes
situações de distribuição a cada dia da semana.
86
Os parâmetros congregam os seguintes fatores:
•
Fatores de ajustes: são determinados fatores registrados em percentual que
permitem o ajuste da capacidade do veículo roteirizado (refere-se à capacidade cadastrada no
gerenciador de dados), do tempo de espera no cliente (parâmetro de ajuste no tempo de espera
do cliente), do tempo de deslocamento (parâmetro de ajuste da velocidade da malha viária,
sendo que aumentando o tempo dirigindo, estaremos diminuindo a velocidade da malha
viária), do tempo de entrega (parâmetro de ajuste do tempo entregando no cliente) e do tempo
de entrega com ajudante (ajuste no tempo de entrega dos veículos com mais de um motorista
cadastrado no gerenciador de dados).
•
Dados do horário de despacho: refere-se às informações relacionadas ao horário de
saída das rotas da central de distribuição. Este grupo congrega os seguintes elementos: horário
preferencial de despacho (determina o horário preferencial para a rota sair da central de
distribuição), intervalo mínimo entre despachos (refere-se ao intervalo mínimo que deve
existir entre os horários de saída das rotas) e retardo de despacho (estabelece um tempo
mínimo entre o final da roteirização – horário configurado do equipamento – e o horário para
o início do despacho das rotas).
•
Intervalos da equipe de entrega: refere-se aos intervalos que a equipe de entrega,
pode realizar durante a sua jornada de trabalho. Este fator apresenta os seguintes elementos:
número máximo de intervalos da equipe de entrega (número máximo de paradas que a equipe
de entrega pode realizar), tempo máximo antes do intervalo (máximo de horas/minutos em
rota antes da parada programada – almoço), tempo de deslocamento máximo antes do
intervalo (máximo de horas/minutos que um motorista pode dirigir antes da parada
programada), duração do intervalo (tempo em horas/minutos de duração da parada
programada) e horário inicial do intervalo (horário preferido para a parada programada –
almoço).
•
Custos da rota: referem-se aos custos gerados pelas rotas. Esses custos
circunscrevem-se ao custo de despacho por hora (este apresenta uma faixa que vai de 0 a 650
e que quanto maior for esse fator de penalidade, maior será a prioridade para respeitar o
horário de despacho determinado), ao custo da penalidade da janela de inconveniência por
87
hora (quanto maior for essa penalidade, maior será a prioridade para respeitar o horário de
inconveniência), salário por hora (custo médio por hora de trabalho), salário por hora extra
(custo médio por hora extra) veículo por hora (custo médio do veículo pro hora) e veículo pro
quilometro (custo médio do veículo por quilometro). Deve-se acrescentar a questão de custos
que os custos por hora alta fará com que o software de roteirização privilegie caminhos de
velocidade maior. Da mesma forma, um custo por quilometro alto, fará com que o roteiro seja
criado privilegiando caminhos de distâncias menores.
•
Limites da rota: este fator refere-se aos limites impostos as rotas geradas pelo
software de roteirização. Este grupo congrega os seguintes elementos: número máximo de
rotas (número máximo de rotas permitidas para a roteirização), distância máxima por rota
(quilometragem máxima permitida por rota), número máximo de clientes por rota, tempo
máximo por rota (número máximo de horas em rota, sem considerar o tempo para parada
programada – almoço), tempo de deslocamento máximo (número máximo de horas/min que o
motorista pode dirigir em rota), tempo máximo antes da hora extra (número máximo de
horas/min em rota dirigindo e descarregando, antes da contagem da hora extra), espera
máxima por cliente (número máximo de horas/min de espera para início do serviço de entrega
no cliente, em relação ao horário de abertura do seu estabelecimento), tempo de atraso
máximo por parada (número máximo de horas/min de atraso, por cliente, em relação ao
horário de fechamento do estabelecimento dos clientes), tempo adiantado máximo por parada
(número máximo de horas/min de antecedência por cliente em relação ao horário de abertura
do estabelecimento dos clientes, com isso o software de roteirização poderá considerar o
início do serviço antes do horário de abertura estipulado para o estabelecimento do cliente),
média máxima de quilometro por hora, tempo mínimo entre clientes (intervalo mínimo entre
dois clientes em horas/min, usado para especificar um tempo mínimo de deslocamento entre
pontos) e limite da capacidade dos veículos que poderá ser realizada através de peso, volume
ou ambos.
•
Hora do rush: informar os horários em que a velocidade da malha viária sofre uma
degradação. Este grupo é composto pelos seguintes elementos: hora de rush da manhã
(intervalo de horário do rush pela manhã), hora de rush da tarde (intervalo de horário do rush
pela tarde) e degradação padrão (fator através do qual a velocidade será degradada nos
horários de rush).
88
•
Opções de rota: esse fator representa a possibilidade de serem inseridas algumas
opções de roteirização. Esse grupo congrega os seguintes elementos: hiper-rota (algoritmo
utilizado para obtenção de ligeiras melhorias no resultado final da roteirização), inventário de
veículo (ao acionar essa opção o software utilizará o número de veículos disponíveis ao invés
do número total), algoritmo de pedido grande (utilizado para dar prioridade aos maiores
pedidos durante a roteirização), % interação da rota (usado para determinar uma porcentagem
na interação do algoritmo), respeitar territórios (esta opção visa respeitar ou não os territórios
criados para os clientes), conjunto de regras de roteirização (selecionar o conjunto de regras
para roteirização). Esse elemento será mais bem esmiuçado no próximo tópico referente a
regras de roteirização.
3.6.4 Regras de roteirização
Para que a simulação e o planejamento da roteirização contemplem todas as situações
que acontecem no atendimento diário ao cliente, o software de roteirzação possibilita o
estabelecimento de algumas regras. As regras são utilizadas para impor associações entre
elementos que compõem a roteirização, como veículos, depósitos, territórios, clientes, etc.
Com isso é possível determinar, por exemplo, que determinado tipo de veículo não pode
atender determinado cliente ou que determinado veículo só pode ser associado a determinado
território, etc.
As regras de roteirização são representadas por seis categorias principais:
•
Regras em relação a produtos: as regras relacionadas com produtos referem-se à
possibilidade de um determinado produto ser ou não entregue por um veículo ou
depósito. Sendo que ainda tem-se a possibilidade do estabelecimento de um
horário de despacho específico para alguns produtos.
•
Regras em relação ao depósito: essas regras estabelecem a possibilidade de
inserção de um horário de despacho para um depósito e fixar o número de rotas
para determinado depósito.
•
Regras em relação aos motoristas: restringir que determinado motorista seja
associado a determinados territórios e veículos.
89
•
Regras referentes a custos: serve para especificar o limite de tempo usado para
calcular o custo de trabalho e o custo de hora extra de trabalho.
•
Regras de grupos de território: esta regra representa a possibilidade das rotas
atenderem clientes de diferentes territórios e que estejam inseridos no mesmo
grupo de territórios.
•
Regras referentes a tipo de veículo: estabelece a possibilidade de um determinado
tipo de veículo em atender um território específico, ou o inverso, um veículo que
não poderá atender a um território específico.
3.6.5 Roteirização dos pedidos
Após a descrição dos agentes que influenciam na roteirização dos pedidos tem-se a
última etapa que se refere à roteirização propriamente dita dos pedidos. Para isso essa opção
apresenta as seguintes alternativas:
•
Respeitar territórios por viagem: esta opção deve ser utilizada para roteirizações
com territórios e múltiplas viagens. Acione essa opção para que todas as viagens
dos veículos tenham o mesmo território como destino, caso contrário um veículo
poderá realizar cada viagem em um território diferente.
•
Respeitar regras de produtos por viagem: essa opção deve ser utilizada para
roteirizações com regras de produtos. Acione esta opção para que todas as viagens
do veículo tenham o mesmo tipo de produto, caso contrário um veículo poderá
realizar cada viagem com um tipo diferente de produto.
•
Inicializar inventário de veículos: Utilizado para deixar o número de veículos
cadastrados igual ao número de veículos disponíveis no inventário de veículos.
•
Confirmar re-roteirizar todos os clientes: com essa opção acionada, toda a vez que
os pedidos forem novamente roteirizados, uma mensagem será apresentada para
confirmar a roteirização evitando que as rotas sejam substituídas acidentalmente.
•
Executar resequenciador após geração de rotas: o acionamento desta opção pode
resultar em rotas com seqüência melhoradas, mas aumentará o tempo necessário
para geração das rotas.
90
•
Limites de rotas por território: ao roteirizar respeitando territórios (limites
máximos de rota, dos parâmetros), pode-se definir o número máximo de rotas, por
território.
•
Flexibilidade dos territórios: quando se roteiriza com territórios é possível mudar o
grau de flexibilidade destes, permitindo que clientes que estejam próximos ao
limite entre territórios possam ser atendidos por rotas do território vizinho.
4 ASPECTOS
QUE
PRECEDEM
ALTERNATIVAS DE
AS
ANÁLISES
COMPARATIVAS
ROTEAMENTO PRESENTES
NO SOFTWARE
DAS
DE
ROTEIRIZAÇÃO
As análises comparativas entre as alternativas de roteamento foram desenvolvidas por
intermédio da formação de cenários simulados de roteirização que foram subdivididos nas
seguintes categorias: pontos concentrados próximos um dos outros, pontos concentrados e
afastados um dos outros e pontos concentrados ao redor da Central de Distribuição – CDD.
Paralelamente a isso os cenários simulados apresentarão diferenciações de volume
classificadas em três níveis: alto, médio e baixo. Com isso serão formados cenários com as
três categorias (pontos concentrados próximos um dos outros, pontos concentrados e
afastados um dos outros e pontos concentrados ao redor da Central de Distribuição – CDD)
mencionadas anteriormente nos três níveis de volume citados.
Outro aspecto importante na formação dos cenários simulados de roteirização referese aos itens que compõem os parâmetros de roteirização e que se colocarão como restrições a
resolução das alternativas de roteamento. Dentre esses itens, mencionados no tópico 3.6.3,
serão utilizados os seguintes: distância por rota, número de clientes por rota, tempo em rota,
tempo de deslocamento, tempo de espera por rota e número de rotas, média máxima de
quilômetros por hora, tempo máximo antes da hora extra e remuneração por hora e por hora
extra da equipe de entrega, o custo por quilometragem percorrida e o custo por hora. Os
demais itens não serão utilizados em virtude de sua difícil mensuração e de não estarem
prontamente registrados em nenhuma fonte de informação da empresa distribuidora de
bebidas.
A mensuração dos itens que compõem os parâmetros de roteirização foi desenvolvida
da seguinte forma:
92
•
Os itens distância por rota, número de clientes por rota, tempo em rota, tempo de
deslocamento, tempo de espera por rota serão calculados por intermédio da média e o maior
valor registrado, em cada nível de volume, das rotas que realizam o atendimento das áreas
(pontos concentrados próximos um dos outros, pontos concentrados e afastados um dos outros
e pontos concentrados ao redor da Central de Distribuição – CDD) descritas no primeiro
parágrafo. Para essa mensuração foram analisados cerca de 206 dias de entrega excetuando-se
Domingo, após a separação de áreas de atendimento mencionadas no tópico 3.3, que foram
classificados em três níveis: alto volume, médio volume e baixo volume. Com relação a essas
faixas de volume estas foram determinadas tendo como base o maior volume vendido dentre
todos os dias de entrega, ou seja, as faixas percentuais foram determinadas em relação ao
maior volume, estabelecendo-se o quanto em termos percentuais o volume vendido em um dia
corresponde ao maior volume vendido dentre todos os dias. Para isso tivemos as seguintes
faixas de volume: volume vendido entre 100%-75% (alto volume) do maior volume, 75%-50
(médio volume) do maior volume e abaixo de 50% (baixo volume) do maior volume. Os itens
destacados anteriormente foram então consolidados (reunião dos dados referentes as rotas que
realizam o atendimento das áreas utilizadas para as simulações) e foi extraída uma média e o
maior valor para cada nível de volume e em relação ao conjunto de rotas que realizam o
atendimento das áreas (pontos concentrados próximos um dos outros, pontos concentrados e
afastados um dos outros e pontos concentrados ao redor da Central de Distribuição – CDD)
descritas no primeiro parágrafo.
•
Em contrapartida aos itens destacados anteriormente os demais serão fixos. Tendo
em vista que esses itens foram obtidos por intermédio da transportadora, que os considera
fixos por no mínimo seis meses. Devendo-se destacar que o número de rotas foi sensibilizado
conforme o volume vendido, ou seja, a divisão do volume total vendido em relação a
capacidade média dos veículos utilizados.
•
Para uma melhor compreensão dos itens referentes a custos da rota, remuneração
da equipe de entrega e velocidade média utilizada, são apresentados alguns esclarecimentos
importantes:
• A média de quilômetros por hora é fornecida pela transportadora que a
calcula por intermédio de acompanhamentos de consumo de combustível
93
realizados pela transportadora. Para o presente trabalho a velocidade média
utilizada foi a de 40 Km/h.
• A remuneração por hora (RH) e por hora extra (REX) é calculada da seguinte
forma:
• Horas de trabalho máxima por equipe de entrega (HTM): 10h20min.
• Salário fixo mensal (equipe de entrega = motorista + 2 ajudantes)
(SFM): R$3.270.25 (referentes a Abril de 2007).
• Dias trabalhados (excetuando-se os Domingos) (DT): 25 dias.
• A fórmula encontra-se descrita abaixo:
RH = SFM
(HTM*DT)
• Considerando que:
RH = REX
Remuneração total (RT) = RH + RE
• Com os dados descritos anteriormente a remuneração por hora e por hora
extra é de R$ 12.70 (Referentes a Abril de 2007).
•
Com relação aos dados referentes a custo do veículo esses são calculados da
seguinte forma:
Custo da Rota (CR) = Custo Hora da Rota (CHR) + Custo Quilometragem da Rota (CQR)
•
O custo quilometragem da rota foi extraído do sistema de remuneração da
transportadora (SRTRANS), sendo este custo igual a R$ 1,17/ Km (Reais de Abril
de 2007).
•
Com objetivo de não priorizar o fator tempo ou quilometragem na formação das
rotas o CHR foi igualado ao CQR. Isso se deve a possível escolha que as
alternativas de roteamento fariam conciliando o fator tempo e quilometragem, ou
94
seja, conforme o tópico 3.6.3, no qual é colocado que os custos por hora alta farão
com que o software de roteirização privilegie caminhos de velocidade maior. Da
mesma forma, um custo por quilometro alto, fará com que o roteiro seja criado
privilegiando caminhos de distâncias menores. Com isso o CHR será igual a R$
1,17/ Hora.
•
O custo quilometragem da rota (CQR) apresenta os seguintes parâmetros:
• Custo por litro de combustível.
• Manutenção do veículo por quilometragem.
• Manutenção da carroceria por quilometragem.
• Pneus (custo por quilometragem).
• Lavagem (custo por quilometragem).
•
Com os dados descritos anteriormente o custo por quilometragem da rota é
calculado da seguinte forma:
Custo Quilometragem da Rota (CQR): Quilometragem (Km) * Custo quilometragem (Rota)
•
Com os dados expostos anteriormente o custo total da rota é calculado da seguinte
forma:
Custo total da rota = CVR + RT
Complementando as questões propostas anteriormente deve-se enaltecer que a
formação dos cenários simulados de roteirização teve como base os 14 problemas de
Christofides, Mingozzi e Toth (1979), que se encontram descritos no anexo deste trabalho,
assim como a descrição do tamanho dos cenários simulados de roteirização e da demanda
total dos clientes. No entanto, deve-se destacar que a estruturação desses cenários não seguiu
os parâmetros impostos pelos 14 de problemas de Christofides, Mingozzi e Toth (1979), mas
sim a característica básica desse tipo de teste, que pressupõe variações de volume, tamanho
dos problemas teste e nos parâmetros que impõem restrições ao problema de roteamento de
veículos.
95
A seguir é apresentado um esquema que simplifica as questões expostas
anteriormente, permitindo uma melhor compreensão da formação dos cenários simulados de
roteirização. Além disso, deve-se destacar que a descrição dos cenários simulados de
roteirização em relação ao tamanho do cenário (número de clientes) e demanda total estão
inseridos nos anexos desse trabalho.
Categorias
Níveis de volume
Itens do parâmetro de roteirização
Pontos concentrados
Volume
Itens calculados com
próximos um dos outros
Alto
base na média
Cenários simulados de roteirização
Pontos concentrados próximos
um dos outros nos três níveis
de volume e para cada nível
tem-se itens dos parâmetros de
Pontos concentrados e
Volume
afastados um dos outros
Médio
roteirização calculados pela
média e pelo maior valor
Itens calculados com
base no maior valor
Pontos concentrados ao
Volume
redor da central de
Baixo
distribuição
registrado
Pontos concentrados afastados
um dos outros nos três níveis
de volume e para cada nível
tem-se itens dos parâmetros de
roteirização calculados pela
média e pelo maior valor
registrado
Pontos concentrados afastados
um dos outros nos três níveis
de volume e para cada nível
tem-se itens dos parâmetros de
roteirização calculados pela
média e pelo maior valor
registrado
96
Figura 37 – Formação dos cenários simulados de roteirização.
5 ANÁLISES COMPARATIVAS
DAS ALTERNATIVAS
DE
ROTEAMENTO
PRESENTES NO SOFTWARE DE ROTEIRIZAÇÃO
Para o desenvolvimento das análises comparativas serão consideradas 5 alternativas de
roteirização: alternativa (1) – baseado no algoritmo de Fisher e Jaikumar priorizando a
formação de grupos de pontos de venda (clusterização), fazendo com que as rotas sejam
formadas com pontos de venda do mesmo território; alternativas (2), (3), (4) e (5) são
baseadas em variações crescentes da possibilidade de inserção e redução de rotas (r-opt).
Abaixo é apresentado um fluxo que relaciona as alternativas de roteamento em relação ao
embasamento teórico que estrutura a forma de resolução das mesmas.
A seguir serão apresentadas as análises que foram divididas de acordo com as
características básicas dos cenários de roteirização: pontos de venda concentrados, pontos de
venda concentrados e afastados um dos outros e pontos de venda ao redor do CDD.
98
Alternativas de roteamento
Alternativa de
roteamento (1)
Embasamento teórico
Fisher e Jaikumar (1981) – Baseia-se
na formação de agrupamento de
clientes, fazendo com que rotas de
Alternativa de
territórios
diferentes
roteamento (2)
interação alguma.
não
tenham
Alternativa de
roteamento (3)
Baseia-se em métodos r-opt nos quais
ocorre
interação
entre
as
rotas,
Alternativa de
apresentando um grau crescente (3-4-
roteamento (4)
5) de possibilidade de inserção de
Alternativa de
clientes de outra rota.
roteamento (5)
Figura 38 – Fluxo relacionando as alternativas de roteamento em relação as suas características básicas
de resolução.
5.1 PONTOS CONCENTRADOS E PRÓXIMOS UM DOS OUTROS
Esse cenário refere-se à situação na qual existem pontos concentrados em uma
determinada área e que são muito próximos um dos outros, viabilizando a possibilidade de
interação entre as rotas que realizarão o atendimento desta área. Posteriormente as alternativas
de roteirização serão analisadas considerando variações de volume por cliente e o valor dos
parâmetros de roteirização. Devendo-se destacar que os elementos a serem indicados no
campo produtividade referem-se respectivamente a: Caixas/viagem e Caixas/Caminhão
(conversão de caixas em dúzias). Com relação aos dois últimos itens, presentes nas colunas de
todas as tabelas das análises dos cenários simulados de roteirização, estes são conceituados no
anexo (terminologias específicas) deste trabalho.
99
5.1.1 Cenário (1): Pontos concentrados e próximos um dos outros – Volume alto
Os resultados obtidos pelas alternativas de roteirização no cenário (1) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
4:46
53.70
8
841.91
2
(412) – (549)
Alternativa (2)
5:10
53.43
7
774.44
1
(471) – (549)
Alternativa (3)
5:09
54.17
7
776.63
2
(471) – (659)
Alternativa (4)
5:46
55.91
6
724.25
1
(549) – (659)
Alternativa (5)
5:46
55.91
6
724.25
1
(549) – (659)
Tabela 4 – Resultados do cenário (1) para pontos concentrados e próximos um dos outros no volume
alto e com parâmetros obtidos da média dos dados reais consolidados.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
6:34
55.48
5
657.54
1
(659) – (824)
Alternativa (2)
6:32
54.78
5
652.91
1
(659) – (824)
Alternativa (3)
6:32
54.83
5
653.10
1
(659) – (824)
Alternativa (4)
6:32
54.83
5
653.10
1
(659) – (824)
Alternativa (5)
6:32
54.83
5
653.10
1
(659) – (824)
Tabela 5 – Resultados do cenário (1) para pontos concentrados e próximos um dos outros no volume
alto e com parâmetros obtidos do maior valor dos dados reais consolidados.
Analisando-se os resultados obtidos pelas alternativas de roteirização nessa situação
específica constata-se que a alternativa (4) e (5) na tabela 4 obtiveram um resultado melhor na
situação em que os parâmetros foram restringidos com a média, já a alternativa (2) na tabela 5
obteve um resultado melhor no momento em que os parâmetros foram consideravelmente
flexibilizados por intermédio do maior valor registrado nos dados reais.
Na tabela 5 com os parâmetros restringidos pelo maior valor o melhor desempenho foi
alcançado pelas alternativas que apresentam como característica de resolução a forte interação
com as áreas de atendimento próximas. Isso se deve ao volume vendido em determinadas
áreas, que correspondiam a menos de 50% da capacidade do veículo que realiza o atendimento
100
desses pontos de venda, permitindo com isso a junção de determinadas rotas. Esse fato é
comprovado pela redução no número de rotas das alternativas (4) e (5) na tabela 5 em relação
às demais e conseqüentemente na redução do custo total.
Outro aspecto a ser destacado refere-se aos valores médios de tempo e km, que nas
alternativas (4) e (5) na tabela 4 foram superiores em relação às alternativas. Isso ocorre em
virtude da característica de resolução das alternativas (4) e (5) que conforme os resultados da
tabela 4 e por essas alternativas apresentarem como característica de resolução uma interação
forte entre as rotas, provoca com isso um aumento no tamanho das mesmas e uma elevação
nos níveis de produtividade da mesma.
Na tabela 5 com os parâmetros restringidos pelo maior valor registrado nos dados reais
o melhor desempenho foi alcançado pela alternativa (2). Nessa situação com os parâmetros
bastante flexibilizados as alternativas (4) e (5) na tabela 5 não alcançaram um resultado
satisfatório porque o aumento na quilometragem das rotas não foi contrabalanceado pela
redução no número de rotas e, por conseguinte redução no custo total. Com isso a
possibilidade de redução de uma rota na tabela 5 pela alternativa (2) não foi alcançada em
virtude da limitação acentuada nos parâmetros de roteirização e da característica de interação
entre rotas ser mínima nessa alternativa.
5.1.2 Cenário (2): Pontos concentrados e próximos um dos outros – Volume médio
Os resultados obtidos pelas alternativas de roteirização no cenário (2) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
05:04
56.49
6
456.76
0
(307) – (307)
Alternativa (2)
05:02
55.82
6
454.70
0
(307) – (307)
Alternativa (3)
05:51
55.77
5
439.38
0
(369) – (369)
Alternativa (4)
05:51
55.77
5
439.38
0
(369) – (369)
Alternativa (5)
05:51
55.77
5
439.38
0
(369) – (369)
Tabela 6 – Resultados do cenário (2) para pontos concentrados e próximos um dos outros no volume
médio e com parâmetros obtidos da média dos dados reais consolidados.
101
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
6:43
57.77
4
401.66
1
(461) – (614)
Alternativa (2)
8:13
61.61
3
368.52
0
(614) – (614)
Alternativa (3)
8:29
60.41
3
380.48
0
(614) – (614)
Alternativa (4)
8:29
60.41
3
380.48
0
(614) – (614)
Alternativa (5)
8:29
60.41
3
380.48
0
(614) – (614)
Tabela 7 – Resultados do cenário (2) para pontos concentrados e próximos um dos outros no volume
médio e com parâmetros obtidos do maior valor dos dados reais consolidados.
Na tabela 7 o melhor resultado alcançado em termos de custo total e produtividade
foram alcançados pelas alternativas (3), (4) e (5). Isso se deve a característica de resolução
dessas alternativas, que são baseadas em uma interação muito maior entre as rotas em relação
às alternativas (1) e (2). Contrapondo-se a situação anterior a alternativa (3) também obteve
um desempenho superior em virtude da composição do volume que permitiu a redução de
uma rota em virtude do volume inferior a 50% do veículo que realiza o atendimento de
determinada área estar localizado no perímetro de inserção característico dessa alternativa, ou
seja, os pontos de venda estão localizados em uma área que dada a característica de resolução
da alternativa (3) foi permitida a inserção desses pontos de venda.
Na tabela 7 a situação assemelha-se a verificada na tabela 5, na qual a flexibilização
ampla dos parâmetros de roteirização fizeram com que o aumento da quilometragem das rotas
não fosse compensado pela redução de custo total. Conclui-se que a elevação na interação
entre rotas é interessante no momento em que os parâmetros venham a sofrer determinado
nível de interação que permita a redução de rotas e conseqüentemente redução do custo total.
5.1.3 Cenário (3): Pontos concentrados e próximos um dos outros – Volume baixo
Os resultados obtidos pelas alternativas de roteirização no cenário (3) encontram-se na
tabela descrita a seguir respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
102
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
4:19
56.53
6
606.26
2
(296) – (444)
Alternativa (2)
4:19
56.53
6
606.26
2
(296) – (444)
Alternativa (3)
4:19
56.53
6
606.26
2
(296) – (444)
Alternativa (4)
4:48
58.80
5
546.63
1
(355) – (444)
Alternativa (5)
4:48
58.80
5
546.63
1
(355) – (444)
Tabela 8 – Resultados do cenário (3) para pontos concentrados e próximos um dos outros no volume
baixo e com parâmetros obtidos da média dos dados reais consolidados.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
6:45
62.28
3
416.94
0
(592) – (592)
Alternativa (2)
6:45
62.28
3
416.94
0
(592) – (592)
Alternativa (3)
6:45
62.28
3
416.94
0
(592) – (592)
Alternativa (4)
6:55
60.44
3
419.61
0
(592) – (592)
Alternativa (5)
6:55
60.44
3
419.61
0
(592) – (592)
Tabela 9 – Resultados do cenário (3) para pontos concentrados e próximos um dos outros no volume
baixo e com parâmetros obtidos do maior valor dos dados reais consolidados.
Na tabela 9 o fenômeno observado nas análises dos cenários (1) e (2), para parâmetros
limitados pela média dos dados reais consolidados, é repetido no cenário (3). Nesse caso
novamente as alternativas (4) e (5) obtiveram o melhor desempenho dentre as outras em
virtude essencialmente da característica de resolução ser baseada na interação entre as rotas e
do volume vendido no perímetro até o qual essas alternativas permitem a inserção de pontos
de venda, ou seja, provavelmente esse perímetro obteve um volume de vendas abaixo de 50%
do veículo que atende a área e com isso houve a junção de rotas e conseqüentemente redução
do custo total.
5.2 PONTOS CONCENTRADOS E AFASTADOS UM DOS OUTROS
Esse cenário refere-se à situação na qual se tem pontos concentrados em uma
determinada área, porém, afastados um dos outros. Posteriormente as alternativas de
roteirização serão analisadas considerando a faixa de volume e o valor dos parâmetros de
roteirização.
103
5.2.1 Cenário (4): Pontos concentrados e afastados um dos outros – Volume alto
Os resultados obtidos pelas alternativas de roteirização no cenário (4) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
4:35
62.62
7
763.91
1
(477) – (557)
Alternativa (2)
4:33
62.05
7
757.51
1
(477) – (557)
Alternativa (3)
5:07
63.52
6
703.80
1
(557) – (668)
Alternativa (4)
5:12
65.18
6
717.04
1
(557) – (668)
Alternativa (5)
5:12
65.18
6
717.04
1
(557) – (668)
Tabela 10 – Resultados do cenário (4) para pontos concentrados e afastados um dos outros no volume
alto e com parâmetros obtidos da média dos dados reais consolidados.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
5:06
62.93
6
700.06
0
(557) – (557)
Alternativa (2)
5:06
63.03
6
700.29
0
(557) – (557)
Alternativa (3)
5:06
62.73
6
698.72
0
(557) – (557)
Alternativa (4)
5:55
65.03
5
647.62
0
(668) – (668)
Alternativa (5)
5:55
65.03
5
647.62
0
(668) – (668)
Tabela 11 – Resultados do cenário (4) para pontos concentrados e afastados um dos outros no volume
alto e com parâmetros obtidos do maior valor dos dados reais consolidados.
Na tabela 10 a alternativa (3) obteve o melhor desempenho dentre as demais,
alcançando um custo total de 703.80 e uma produtividade equivalente as alternativas (4) e (5),
porém, essas atingiram um custo total que foi 2% superior a alternativa (3). Neste caso têm-se
pontos concentrados que estão afastados um dos outros, fazendo com que uma expansão
maior da rota nas alternativas (4) e (5) tenha como contrapartida um custo total maior. Com
isso a diferença em 2% no custo total da alternativa (3) em relação a (4) e (5) deve-se a como
os pontos de venda foram selecionados e a seqüência de atendimento dos pontos de venda.
Conclui-se com isso que nessa situação na qual os pontos estão concentrados, mas afastados
um dos outros e os parâmetros de roteirização apresentam encontram-se consideravelmente
104
restringidos, vale a pena a expansão da rota até um determinado patamar que faça com que a
elevação na quilometragem venha a ter como contrapartida uma redução no custo total.
Na tabela 11 com o aumento dos parâmetros de roteirização o aumento da
quilometragem por rota verificada nas alternativas (4) e (5) passam a valer a pena, pois ocorre
o processo de redução de uma rota e a produtividade sofre uma elevação comparativamente as
outras alternativas.
5.2.2 Cenário (5): Pontos concentrados e afastados um dos outros – Volume médio
Os resultados obtidos pelas alternativas de roteirização no cenário (5) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
5:58
58.17
6
750.51
0
(460) – (460)
Alternativa (2)
6:48
60.04
5
690.76
0
(551) – (551)
Alternativa (3)
8:14
61.94
4
637.37
0
(689) – (689)
Alternativa (4)
8:14
61.94
4
637.37
0
(689) – (689)
Alternativa (5)
8:14
61.94
4
637.37
0
(689) – (689)
Tabela 12 – Resultados do cenário (5) para pontos concentrados e afastados um dos outros no volume
médio e com parâmetros obtidos da média dos dados reais consolidados.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
5:59
58.57
6
753.39
0
(460) – (460)
Alternativa (2)
8:28
62.85
4
652.97
0
(689) – (689)
Alternativa (3)
8:25
61.72
4
646.91
0
(689) – (689)
Alternativa (4)
8:25
61.72
4
646.91
0
(689) – (689)
Alternativa (5)
8:25
61.72
4
646.91
0
(689) – (689)
Tabela 13 – Resultados do cenário (5) para pontos concentrados e afastados um dos outros no volume
médio e com parâmetros obtidos do maior valor dos dados reais consolidados.
105
Conforme ocorreu nas análises anteriores as alternativas (3), (4) e (5) obtiveram os
melhores resultados dentre as demais, alcançando o menor custo total e uma produtividade
consideravelmente superior. Nessa situação essas alternativas foram favorecidas pelo volume
vendido nas áreas que permitiu a redução de rotas (volumes abaixo de 50% do veículo que
atende uma determinada área), fazendo com que houvesse a junção de rotas. Em contrapartida
para a alternativa (1) que prioriza a clusterização, ou seja, formação das rotas com base em
territórios iguais está é prejudicada porque o volume de venda em cada território não é
superior a 50% da capacidade do veículo que atende os pontos de venda inseridos naquele
território. Isso provoca a formação de rotas improdutivas e com um custo total alto.
5.2.3 Cenário (6): Pontos concentrados e afastados um dos outros – Volume baixo
Os resultados obtidos pelas alternativas de roteirização no cenário (6) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
4:58
63.99
3
346.69
0
(429) – (429)
Alternativa (2)
6:45
66.83
2
284.41
0
(644) – (644)
Alternativa (3)
6:45
66.72
2
284.26
0
(644) – (644)
Alternativa (4)
6:45
66.72
2
284.26
0
(644) – (644)
Alternativa (5)
6:45
66.72
2
284.26
0
(644) – (644)
Tabela 14 – Resultados do cenário (6) para pontos concentrados e afastados um dos outros no volume
baixo e com parâmetros obtidos da média dos dados reais consolidados.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
6:47
67.33
2
286.06
0
(644) – (644)
Alternativa (2)
6:44
66.34
2
283.47
0
(644) – (644)
Alternativa (3)
6:43
65.67
2
281.80
0
(644) – (644)
Alternativa (4)
6:43
65.67
2
281.80
0
(644) – (644)
Alternativa (5)
6:43
65.67
2
281.80
0
(644) – (644)
Tabela 15 – Resultados do cenário (6) para pontos concentrados e afastados um dos outros no volume
baixo e com parâmetros obtidos do maior valor dos dados reais consolidados.
106
Com base nos resultados apresentados nas tabelas 14 e 15 constata-se que as
alternativas (3), (4) e (5) atingiram o melhor desempenho em relação a custo total
produtividade, isso se deve a formação de pequenas rotas improdutivas nas alternativas (1) e
(2) e que são eliminadas nas alternativas (3), (4) e (5). No entanto, a tabela 17 apresenta
resultados muito próximos entre as alternativas em relação tanto a custo total quanto a
produtividade, com isso envolve também uma decisão gerencial em relação a qual alternativa
será selecionada. Com isso caso seja priorizado a formação de rotas mais concentradas e que
permitirão um atendimento mais eficiente por parte da equipe de entrega (que apresenta um
conhecimento em termos de localização de pontos de venda maior da rota, já que existem
poucos pontos de venda de outras rotas) serão privilegiadas as alternativas (1) e (2), caso
contrário as demais alternativas ganham prioridade.
5.3 PONTOS CONCENTRADOS AO REDOR DO CDD
Esse cenário refere-se à situação na qual se tem pontos concentrados ao redor da
central de distribuição. Posteriormente as alternativas de roteirização serão analisadas
considerando a faixa de volume e o valor dos parâmetros de roteirização.
5.3.1 Cenário (7): Pontos concentrados ao redor do CDD – Volume alto
Os resultados obtidos pelas alternativas de roteirização no cenário (7) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
3:38
13.19
9
540.34
1
(405)- (456)
Alternativa (2)
4:01
13.95
8
528.23
0
(456) – (456)
Alternativa (3)
4:10
18.04
8
568.15
0
(456) – (456)
Alternativa (4)
4:07
18.04
8
562.65
0
(456) – (456)
Alternativa (5)
4:08
17.23
8
559.78
0
(456) – (456)
Tabela 16 – Resultados do cenário (7) para pontos concentrados ao redor do CDD no volume alto e
com parâmetros obtidos da média dos dados reais consolidados.
107
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
Alternativa (2)
4:11
4:42
17.42
18.87
8
7
565.50
553.26
1
0
(456) – (521)
(521) – (521)
Alternativa (3)
Alternativa (4)
4:42
4:42
18.87
18.87
7
7
553.26
553.26
0
0
(521) – (521)
(521) – (521)
Alternativa (5)
4:42
18.87
7
553.26
0
(521) – (521)
Tabela 17 – Resultados do cenário (7) para pontos concentrados ao redor do CDD no volume alto e
com parâmetros obtidos do maior valor dos dados reais consolidados.
Com base nos resultados alcançados nas tabelas 16 e 17 constata-se que a alternativa
(2) obteve o melhor desempenho em ambas as situações. Nesse caso não foi a redução no
número de rotas que permitiu a redução no custo total, mas sim a forma como os pedidos
foram selecionados e como ficaram as seqüências de atendimento dos pontos de venda.
A alternativa (2) tem como característica essencial de resolução a interação entre as
rotas por intermédio dos pontos de venda que fazem a fronteira entre as rotas. Em
contrapartida as alternativas (3), (4) e (5) possuem como pressuposto básico uma interação
maior entre as rotas, que não ficará circunscrita aos pontos de venda localizados nas fronteiras
das rotas. Com isso e combinado a questão do volume vendido nas áreas de atendimento, para
essa situação a alternativa (2) obteve o melhor desempenho nas duas circunstâncias propostas
nas tabelas 17 e 18.
5.3.2 Cenário (8): Pontos concentrados e ao redor do CDD – Volume médio
Os resultados obtidos pelas alternativas de roteirização no cenário (8) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
4:24
15.90
6
435.75
0
(449) – (449)
Alternativa (2)
Alternativa (3)
4:24
4:24
16.19
16.19
6
6
437.25
437.25
0
0
(449) – (449)
(449) – (449)
Alternativa (4)
Alternativa (5)
4:24
4:24
16.19
16.19
6
6
437.25
437.25
0
0
(449) – (449)
(449) – (449)
Tabela 18 – Resultados do cenário (8) para pontos concentrados ao redor do CDD no volume médio
e com parâmetros obtidos da média dos dados reais consolidados.
108
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
4:22
15.34
6
431.22
0
(449) – (449)
Alternativa (2)
4:22
15.63
6
432.71
0
(449) – (449)
Alternativa (3)
4:22
15.63
6
432.71
0
(449) – (449)
Alternativa (4)
4:22
15.63
6
432.71
0
(449) – (449)
Alternativa (5)
4:22
15.63
6
432.71
0
(449) – (449)
Tabela 19 – Resultados do cenário (8) para pontos concentrados ao redor do CDD no volume médio
e com parâmetros obtidos do maior valor dos dados reais consolidados.
Analisando-se os resultados alcançados nas tabelas 18 e 19 a alternativa (1) obteve o
melhor desempenho dentre as demais. Isso se deve a como o volume vendido ficou distribuído
para essa situação específica, ou seja, nesse caso cada área de atendimento (dividida em
territórios) alcançou um volume de vendas superior em 50% a capacidade do veículo que
realiza o atendimento dessa área, fazendo com que a alternativa (1) que prioriza a
clusterização (formação de rotas com pontos de venda dos mesmos territórios) viesse a levar
certa vantagem em relação as demais, já que tende com isso a formar rotas mais concentradas
e com uma média de quilometragem menor por rota e, por conseguinte um custo total menor.
5.3.3 Cenário (9): Pontos concentrados e ao redor da central de distribuição – Volume baixo
Os resultados obtidos pelas alternativas de roteirização no cenário (9) encontram-se na
tabela descrita abaixo respectivamente nas seguintes circunstâncias: parâmetros com os
valores médios e o maior valor.
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
2:37
89.36
6
239.18
1
(197) – (236)
Alternativa (2)
2:31
78.30
6
230.26
0
(197) – (197)
Alternativa (3)
3:01
78.30
5
225.15
0
(236) – (236)
Alternativa (4)
3:01
78.30
5
225.15
0
(236) – (236)
Alternativa (5)
3:01
78.30
5
225.15
0
(236) – (236)
Tabela 20 – Resultados do cenário (9) para pontos concentrados ao redor do CDD no volume baixo
e com parâmetros obtidos da média dos dados reais consolidados.
109
Alternativas
Média de Tempo
(h: mm)
Média de Km
Nº Rotas
Custo total
(R$)
Recarga
(nº viagens)
Produtividade
(Dúzias)
Alternativa (1)
3:47
19.26
4
229.59
0
(295) – (295)
Alternativa (2)
3:46
19.09
4
228.84
0
(295) – (295)
Alternativa (3)
3:46
19.09
4
228.84
0
(295) – (295)
Alternativa (4)
3:46
19.09
4
228.84
0
(295) – (295)
Alternativa (5)
3:46
19.09
4
228.84
0
(295) – (295)
Tabela 21 – Resultados do cenário (9) para pontos concentrados ao redor do CDD no volume baixo
e com parâmetros obtidos do maior valor dos dados reais consolidados.
Os resultados apresentados nas tabelas 20 e 21 colocam as alternativas (3), (4) e (5)
como as melhores alternativas de roteirização dentre as demais, alcançando um custo total
menor e uma produtividade maior em relação às demais. Novamente, como já ocorreu em
outras análises a diferença entre o custo total obtido pelas alternativas é muito pequena,
fazendo com que a decisão em adotar uma determinada alternativa em detrimento das demais
esteja relacionada unicamente a uma decisão gerencial, como já mencionada no tópico 4.4.3.2.
5.4 ANÁLISES COMPLEMENTARES EM RELAÇÃO
ÀS
ALTERNATIVAS
DE
ROTEIRIZAÇÃO
As análises desenvolvidas no tópico 4.4 demonstraram em grande parte dos cenários
uma prevalência das alternativas (3), (4) e (5) dentre as demais e nas circunstâncias em que o
aumento da média de quilometragem das rotas não era contrabalanceado pela redução no
custo total, os métodos (1) e (2) passam a obter o melhor desempenho. Quando é considerada
a questão do valor dos parâmetros de roteirização, conforme os mesmos são restringidos pelo
valor médio obtido dos dados reais as alternativas (1) e (2) obtêm um desempenho melhor.
Isso ocorre essencialmente nas situações em tem-se os pontos concentrados e afastados um
dos outros e quando os pontos são concentrados ao redor da central de distribuição.
Devendo-se destacar que mesmo nas situações em que as alternativas (3), (4) e (5)
obtêm um desempenho melhor, isso pode ser alterado caso sejam consideradas outras
variáveis como:
110
•
Prioridade para a jornada líquida – os gestores da área de logística podem
priorizar o retorno mais cedo a central de distribuição das equipes de entrega em virtude de
altos custos trabalhistas ou possibilidade de absenteísmo no dia seguinte. Neste caso as
alternativas (1) e (2) ganham prioridade em relação às demais, pois apresentam uma redução
da quilometragem e tempo médio por rota, fazendo com que as equipes de entrega venham a
retornar mais cedo para a central de distribuição.
•
Fidelização de freteiros – quando é previsto uma elevação no volume em
determinado mês a empresa distribuidora de bebidas realiza a contratação de um determinado
número de freteiros, que terão no mês previsto para alta de volume um determinado número
de viagens garantidas. Nesse caso e essencialmente nos dias de queda de volume (SegundaFeira) ocorre a prioridade por uma roteirização de um número maior de rotas visando garantir
o número de viagens acordado. Tendo em vista que nem sempre nos dias de pico de volume
todos os freteiros serão utilizados, já que em alguns dias o volume vendido não ultrapassa a
capacidade de atendimento da frota fixa.
•
Elevação no nível de serviço – a empresa distribuidora de bebidas, visando elevar
a qualidade no atendimento dos pontos de venda, realizou o mapeamento de determinados
pontos de venda que apresentam como característica básica o volume comprado pelos mesmos
e com que freqüência compram os produtos comercializados pela empresa distribuidora de
bebidas. Conseqüentemente todos esses pontos de venda devem ser atendidos por frota fixa e
as rotas que realizam o atendimento dos mesmos deverão apresentar uma jornada líquida
inferior as outras. Isso se deve a necessidade do pleno atendimento desses clientes sem
maiores problemas. Mediante a isso essas rotas deverão apresentar uma média de
quilometragem baixa e, por conseguinte as alternativas (1) e (2) obtêm prevalência em relação
às demais.
•
Pontos de venda críticos em atendimento – Da mesma forma que ocorreu o
mapeamento dos pontos de venda que devem ter uma prioridade na entrega de seus produtos,
também houve uma identificação dos pontos de venda que dificultam de alguma forma
(problemas no pagamento, antipatia com a equipe de entrega, horário específico de entrega,
dentre outros fatores) a realização das entregas. Nesse caso as rotas que realizam o
atendimento dos pontos de venda críticos devem apresentar um formato de rota mais
111
concentrado, para que todos os pontos de venda sejam atendidos com eficiência e
conseqüentemente as alternativas (1) e (2) obtêm prevalência em relação às demais.
•
Nova equipe de entrega – Com a contratação de um nova equipe de entrega que
realizará o atendimento de determinada área, normalmente essa equipe de entrega não conhece
a rota e conseqüentemente para um atendimento eficiente de todos os pontos de venda da área
faz-e necessário a formação de rotas mais concentradas, como as que são estruturadas nas
alternativas (1) e (2).
6 CONCLUSÕES E RECOMENDAÇÕES
O trabalho teve como objetivo precípuo a adequação das alternativas de roteamento em
relação a determinados cenários simulados que tiveram como característica básica o
posicionamento dos pontos de venda em três situações específicas: pontos concentrados
próximos um dos outros, pontos concentrados e afastados um dos outros e pontos ao redor da
central de distribuição. Além disso, foram realizadas variações no volume vendido e no itens
dos parâmetros de roteirização que restringem as formas de resolução das alternativas de
roteamento.
Com as análises obtidas dos cenários simulados de roteirização pode-se constatar uma
prevalência das alternativas de roteamento (4) e (5) que apresentam um nível de interação
entre as rotas consideravelmente superior as demais alternativas. No entanto, essa
característica de forte interação pode se tornar pouco profícua em situações nas quais o
volume vendido é superior a 50% da capacidade dos veículos que realizam o atendimento das
áreas presentes nos cenários simulados, ou seja, constatou-se nas análises que nessas situações
a elevação da média de quilometragem e do tempo em rota não é contrabalanceada por uma
redução de custo. Sendo que essa redução seria proveniente da junção de duas rotas,
reduzindo com isso a utilização de 1 veículo. Diante dessas situações em que o volume
vendido é distribuído uniformemente entre as áreas de atendimento e que cada volume de um
determinado território seja superior a 50% da capacidade do veículo as demais alternativas
(1), (2) e (3) colocam-se como possibilidades para a resolução deste cenário simulado de
roteirização.
Paralelamente as questões colocadas anteriormente deve-se considerar, para a
alternativa (1), as análises realizadas no tópico 5.4. Neste tópico foram apresentadas algumas
possibilidades de utilização da alternativa (1) para a resolução dos cenários simulados de
113
roteirização. Isso se deve ao desempenho alcançado por essa alternativa de roteamento nos
resultados obtidos nas análises comparativas das alternativas de roteamento, ou seja, esta
alternativa alcançou um desempenho inferior em virtude de sua característica básica de
resolução estar vinculada a necessidade de formação de pontos concentrados, em que as rotas
de territórios diferentes não interagem umas com as outras.
Outro aspecto importante refere-se o impacto na utilização da média ou do maior valor
para itens que compõem os parâmetros de roteirização em relação aos resultados obtidos pelas
alternativas de roteamento. Com base nas análises desenvolvidas no capítulo V constata-se
que a utilização de valores dos itens dos parâmetros de roteirização provenientes do maior
valor registrado, provoca no resultado final das alternativas de roteamento uma prevalência
maior ainda das alternativas (4) e (5) do que quando são usadas as médias. Isso se deve ao
nível de restrição imposto pelos valores obtidos através da média, ou seja, esses valores
obviamente serão inferiores em relação aqueles obtidos pelo maior valor. A conclusão dessa
elevação no nível da restrição está centrada na dificuldade que as alternativas de roteamento
com maior possibilidade de interação entre as rotas tem em lidar com situações em que ocorre
uma elevação no valor das restrições impostas aos cenários simulados de roteirização.
Complementando os aspectos descritos anteriormente pode-se colocar como sugestão
para estudos futuros a possibilidade de alternativas de roteamento mais modernas, como por
exemplo, a metaheurística tabu ou a utilização de algum algoritmo genético. Além disso,
pode-se procurar aprofundar os estudos com relação a interação existente entre os parâmetros
de roteirização e em que níveis de restrição as alternativas de roteamento (1), (2), (3), (4), e
(5) se comportam melhor.
7 REFERÊNCIAS
ALTIKEMER, K; GAVISH, B. Parallel savings based heuristics for the Delivery problem.
Operational Research, n. 39. 1991. p. 456-469.
ASSAD, A. A. (1988). Modeling and implementation issues in vehicle routing. In: GOLDEN,
L. B.; ASSAD, A. A. (eds). Vehicle Routing: Methods and Studies. North Holland,
Amsterdam, 1988. p. 7-46.
ASSAD, A. A.; GOLDEN, L. B. (1984). A decision-theoretic framework for comparing
heuristics. European Journal of Operational Research, v.18, p. 167-171. In: BALLOU, R. H.
Logística empresarial. São Paulo: Atlas. 1993.
ASSAD, A. A. et al. Experimentation in optimization. European Journal of Operational
Research, v.27, 1986. p. 1-16.
BALAS, E.; CHRISTOFIDES, N. A restricted Lagrangean approach to the traveling
salesman problem. Mathematical Programming, n.21, 1981. p. 19-46.
BALLOU, R. H. Logística Empresarial: transporte, administração de materiais e distribuição
física. Tradução Hugo T. Y. São Paulo: Atlas, 1993.
BODIN, L.; BERMAN, L. Routing and scheduling of school buses by computer.
Transportation Science, n.13, 1979. p. 113-129.
BODIN, L. D. et al. Routing and scheduling of vehicle and crews: The state of the art.
Computers and Operational Research, v.9, 1983. p. 63-212.
BODIN, L.; KURSH, S. A computer-assisted system for the routing and scheduling of street
sweepers. Operational Research, v.26, n.4, 1978. p. 525-537.
BODIN, L.; KURSH, S. A detailed description of a street sweeper routing and scheduling
system. Computers & Operations Research, n.14B, 1979. p. 115-120.
115
CHRISTOFIDES, N. Uses of a vehicle routing and scheduling system in strategic distribution
planning. Scandinavian Journal of Mat Admin, v.7, n.2, 1981. p. 39-55.
CHRISTOFIDES, N. Vehicle Routing. In: LAWLER, E. L. et al. The Traveling Salesman
Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons. 1985.
CHRISTOFIDES, N.; EILON, S. An algorithm for the vehicle Dispatching problem.
Operational Research, n. 20, 1969. p. 309-318.
CHRISTOFIDES, N.; MINGOZZI, A.; TOTH, P. The vehicle routing problem. Urbino
Working Paper, July, 1978.
CHRISTOFIDES, N. et al. Combinatorial optimization. John Wiley, Chichester. 1979.
CLARKE, G.; WRIGHT, J. Scheduling of vehicles from a central depot to a number of
Delivery points. Operational Research, n.12, 1964. p. 568-581.
CUNHA, C. B. Uma contribuição para o problema de roteirização de veículos com restrições
operacionais. São Paulo. Tese (Doutorado). Escola Politécnica Universidade São Paulo,
Departamento de Engenharia de Transportes, Universidade de São Paulo, 1997.
DESROCHERS, M.; VERHOOG, T. W. A Matching Based Savings Algorithm for the vehicle
routing problem. Cahier du GERAD G-89-04. Écoledes Hautes Études Commerciales de
Montreal, 1989.
EILON, S.; EATSON-GANDY, C.; CHRISTOFIDES, N. Distribution Management:
Mathematical Modeling and Practical Analysis. Hafner, New York, 1971.
FISHER, M. L.; JAIKUMAR, R. A generalized assignment heuristic for vehicle routing.
Networks, v. 11, 1981. pp. 109-124.
GASKELL, T. J. Bases for vehicle fleet scheduling. Operational Research, n.18, 1967. p. 281295.
GILLET, B.; MILLER, L. A heuristic algorithm for the vehicle dispatch problem. Operational
Research, n.22, 1974. p. 340-349.
GOLDBARG, M. C.; LUNA, H. P. L. Otimização Combinatória e Programação Linear:
modelos e algoritmos. Rio de Janeiro: Campus, 2000. 649 p. ISBN 85-352-0541-1.
GOLDEN, B. et al. The fleet size and mix vehicle routing problem. Management Science &
Statistics Working Paper, (Report n.82-020). 1982.
116
LAPORTE, G. The vehicle routing problem: an overview of exact and approximate
algorithms. European Journal of Operational Research, v. 59, n.3, 1992. p. 345-358.
LIN, S. Computer solutions of the traveling salesman problem. Bell System Computer
Journal, n.44, 1965. p. 2245-2269.
LIN, S.; KERNIGHAN, B. W. An effective heuristic algorithm for the traveling salesman
problem. Operational Research, n.27, 1973. p. 503-511.
OSMAN, I. H. Meta strategy simulated annealing and tabu search algorithms for the vehicle
routing problem. Annals of Operations Research, 41, 1993. p. 421-451.
PUREZA, V. M.; FRANÇA, P. M. Vehicle routing problems via tabu search metaheuristic.
Montreal. Centre de recherche su les transports (Publication CRT-747). 1991.
SEMET, F.; TAILLARD, E. Solving real life vehicle routing problems efficiently using taboo
search. Annals of Operational Research, n. 41, 1993. p. 469-488.
SOLOMON, M. M. Algorithms for the vehicle routing and scheduling problems with time
windows constraints. Operations Research, v. 35, n. 2, 1987. p. 254-265.
SOLOMON, M. M.; DESROSIERS, J. Time window constrained routing and scheduling
problems. Transportation Science, v. 22, n. 1, 1988. p. 1-13.
TAILLARD, E. Parallel iterative search methods for vehicle routing problems. Networks, v.
23, 1993. p. 661-673.
ANEXOS
118
TERMINOLOGIAS ESPECÍFICAS DA OPERAÇÃO DA EMPRESA
DISTRIBUIDORA DE BEBIDAS
Antes de se iniciar a descrição do macro fluxo de operações e seus principais fluxos
internos devem-se definir algumas terminologias específicas que visam permitir uma melhor
compreensão com relação aos fluxos que serão expostos em etapas subseqüentes a esta. As
terminologias específicas são as seguintes:
•
Sistema de gestão empresarial da empresa distribuidora de bebidas: refere-se ao sistema
que congrega todas as informações concernentes a cadastramento de produtos, controle de
estoques, movimentação diária (administração de pedidos, notas fiscais, prestação de
contas, relatórios diversos, fechamento e monitoramento de um determinado processo),
financeiro e movimentação mensal (indicadores de desempenho e margem de contribuição
PDV).
•
Equipe de entrega: formada pelo motorista e dois ajudantes.
•
Prestação de contas física e financeira – PCF e PCFin: referem-se respectivamente a
comparação entre a quantidade transportada pelo caminhão no momento em que este saiu
da central de distribuição em relação ao momento de retorno deste a central de distribuição
e a comparação do valor financeiro da carga transportada em relação ao dinheiro que a
equipe de entrega trouxe.
•
Rádio freqüência – RF: equipamento que tem como objetivo coletar informações de
quilometragem rodada pelo caminhão, horário de chegada e saída da central de
distribuição e coletar informações referentes ao carregamento do caminhão.
•
Coletor: ferramenta utilizada para coletar informações e transferi-las para o sistema de
gestão empresarial.
•
Monitoramento do processo de distribuição – MPD: registro no sistema de gestão
empresarial de todas as informações referentes à quantidade de produtos carregadas pelo
caminhão, quilometragem inicial e final do caminhão, tempo inicial e final do caminhão,
horário de prestação de contas física e financeira.
•
Análise do painel de produtividade operacional - PPO: monitoramento da produtividade
interna da equipe, ou seja, monitorar o como e o tempo em que os caminhões estão sendo
carregados, a duração da prestação de contas física e financeira e como está sendo
programado o processo de abastecimento da central de distribuição.
119
•
Pallet e chapatex: O pallet refere-se a um material feito de madeira que tem como objetivo
servir de base para os produtos dentro caminhão, já o chapatex é um compensado de
madeira que serve para proteger os produtos que podem sofrer avarias com maior
facilidade.
•
Baia: refere-se ao espaço presente no caminhão para o carregamento dos produtos.
Contudo este termo apresenta outra definição ao relacionarmos com o carregamento do
caminhão, referindo-se assim ao espaço que o veículo ocupará no armazém no momento
em que está sendo carregado.
•
Dúzias: unidade utilizada pelo software de roteirização.
•
Caixas: unidade de conversão de todos os produtos para caixas de inteira (vasilhame
contendo 24 garrafas de 600ml). Para converter de dúzias para caixas basta multiplicar
por 2.
•
Ordem de Carga Paletizada-OCP: representa um sistema que determina como o caminhão
será carregado, ou seja, quais produtos ocuparão cada baia do caminhão.
•
Blitz do carregamento: refere-se à inspeção da quantidade transportada que ocorre antes
do caminhão sair da central de distribuição.
•
Amarração: recobrir a carga com uma lona plástica visando protegê-la de possíveis
tombamentos.
•
Refugo: refere-se à verificação de avarias de todo material (garrafas de vidro) que irá
retornar para a companhia.
•
Ponto de venda - PDV: referem-se aos clientes a serem atendidos pela empresa
distribuidora de bebidas, estes se constituem como sendo os estabelecimentos comerciais
que vendem os produtos fabricados pela empresa.
•
Nota fiscal – NF: refere-se ao comprovante do valor financeiro do produto a ser entregue
ao cliente.
•
Vasilhame: material feito à base de plástico onde entram as garrafas de bebida.
•
Padrão Técnico de Logística – PTL: estabelecer uma sistemática de auditoria na saída das
linhas de produção, na armazenagem de produtos, no carregamento e amarração, através
da definição de características de qualidade/processo, valores assegurados, freqüências de
medição, métodos e itens de controle.
•
Tempo interno: representa o tempo em que o motorista e os ajudantes gastam para realizar
a prestação de contas física e financeira.
120
•
Jornada Líquida: representa o tempo total de jornada de trabalho da equipe de entrega, ou
seja, congrega o somatório do tempo em rota com o tempo interno.
•
Perfis dos veículos: a base de classificação dos perfis dos veículos é o número de baias
que estes apresentam. Nesse caso têm-se os seguintes perfis e suas respectivas
capacidades: 10 baias alto (840 dúzias), 10 baias rebaixado (784 dúzias), 8 baias alto (672
dúzias), 8 baias rebaixado (616 dúzias), 6 baias alto fechado (420 dúzias), 6 baias
rebaixado (360 dúzias), 12 baias aberto (1512 dúzias – somente chopp e 840 dúzias para
outros produtos), carreta (2016 dúzias) e 8 baias aberto (560 dúzias). Além disso, deve-se
destacar que afirmar que um veículo é aberto ou fechado está relacionado à carroceria do
veículo que pode ser aberta, ou seja, os produtos ficam expostos ou fechada onde os
produtos são ficam dentro de um quadrado de ferro, onde ficam os produtos da empresa
em cada divisão (baia).
•
Custos: os custos para a realização das entregas dos produtos (os custos podem ser
subdivididos nos custos relacionados a veículos e mão-de-obra).
•
Volume transportado relacionado com as viagens realizadas: representa a quantidade de
volume transportado / quantidade de total de viagens realizadas, ou seja, denominado
como dúzias/viagem.
•
Utilização: avalia dimensionamento da frota de veículos, representa a relação entre frota
utilizada/frota total. Este parâmetro é apresentado de forma percentual
•
Tempo previsto: representa o tempo previsto pelo software de roteirização para a
realização das entregas.
•
Número de entregas: número de entregas realizadas / número de viagens realizadas.
•
Capacidade total: representa o somatório de todas as capacidades dos veículos utilizados
na roteirização.
•
Ocupação: representa a relação entre o volume total transportado pelos veículos / a
capacidade total dos veículos.
•
Caixas por viagem: calculada por intermédio da divisão entre a quantidade de caixas
carregadas por um determinado veículo em relação ao número de viagens realizadas
pelo mesmo.
•
Caixa veículo/dia: calculada pela divisão entre a quantidade de caixas carregadas e o
número de veículos necessários para carregá-las.
•
CDD: Central de Distribuição Direta.
121
Pontos concentrados próximos um dos outros
Pontos concentrados e afastados um dos outros
122
Pontos concentrados ao redor do CDD
Os 14 problemas teste de Christofides, Mingozzi e Toth (1979)
Esses problemas teste foram explorados por inúmeros pesquisadores, que os utilizaram
para avaliar as formas de resolução empregadas por uma diversidade de heurísticas. Dentre
elas pode-se mencionar: Clarke e Wright (1964), o de Mole e Jameson (1976) e sobre o
algoritmo de varredura de Gillett e Miller (1974). Posteriormente esses problemas teste foram
aplicados nas novas heurísticas propostas por Fisher e Jaikumar (1981), Desrochers Verhoog
(1989), Altinkemer e Gavish (1991), Pureza e França (1991), Taillard (1992), Osman (1993),
Gendreau, Hertz e Laporte (1994) e Kelly e Xu (1999).
Os problemas contêm entre 50 e 199 clientes mais o depósito. Dentre esses 14
problemas, 7 são problemas básicos de roteirização de veículos, já os 7 problemas restantes
usam as mesmas localizações dos 7 primeiros, mas apresentam restrições de comprimento
máximo das rotas. Além disso, é considerado um tempo de serviço constante, cobrado por
visitar cada cliente. Com isso os problemas de 1 a 5, 11 e 12 possuem apenas restrição de
capacidade. Em contrapartida os problemas de 6 a 10 são os mesmos de 1 a 5, porém,
possuem restrição de comprimento máximo das rotas e tempo de serviço; os problemas 13 e
123
14 são iguais aos problemas 11 e 12, mas nestes últimos há restrição de comprimento de rota e
é considerado o tempo de serviço aos clientes. Essas informações encontram-se resumidas na
tabela abaixo.
Características dos problemas teste de Christofides (1979)
Número do Problema Tamanho (n)
VRPNC1
50
VRPNC2
75
VRPNC3
100
VRPNC4
150
VRPNC5
199
VRPNC6
50
VRPNC7
75
VRPNC8
100
VRPNC9
150
VRPNC10
199
VRPNC11
120
VRPNC12
100
VRPNC13
120
VRPNC14
100
Capacidade do veículo
160
140
200
200
200
160
140
200
200
200
200
200
200
200
Comprimento máximo da rota
Irrestrito
Irrestrito
Irrestrito
Irrestrito
Irrestrito
200
160
130
200
200
Irrestrito
Irrestrito
720
1040
Tempo de Serviço
0
0
0
0
0
10
10
10
10
10
0
0
50
90
Razão da capacidade
0.97
0.97
0.91
0.93
0.98
0.80
0.88
0.81
0.80
0.88
0.98
0.90
0.62
0.82
Demanda Total
777
1364
1458
2235
3186
777
1364
1458
2235
3186
1375
1810
1375
1810
Número de veículos
5
10
8
12
17
6
11
9
14
18
7
10
11
11
Para os problemas de 1 a 10 os clientes encontram-se distribuídos uniformemente,
enquanto os problemas de 1 a 14 estes aparecem em agrupamentos. As coordenadas dos
clientes foram geradas randomicamente, extraídas de uma distribuição uniforme entre U
[1,100], enquanto as coordenadas dos depósitos são escolhidas de U [45,55]. As demandas
foram geradas em um intervalo U [1,41], enquanto a capacidade dos veículos é fixa,
obedecendo a uma determinada razão, que refere-se a razão entre a demanda total requerida e
a capacidade total disponível, variando com isso entre U [0.82; 0.97].
Os clientes e os depósitos são considerados pontos em um plano e as distâncias entre
eles são dadas pela distância euclidiana entre dois pontos.
Tipos de cenários simulados de roteirização
Alto volume - Pontos concentrados próximos um dos outros
Médio volume - Pontos concentrados próximos um dos outros
Baixo volume - Pontos concentrados próximos um dos outros
Alto volume - Pontos concentrados e afastados um dos outros
Médio volume - Pontos concentrados e afastados um dos outros
Baixo volume - Pontos concentrados e afastados um dos outros
Alto volume - Pontos ao redor da central de distribuição
Médio volume - Pontos ao redor da central de distribuição
Baixo volume - Pontos ao redor da central de distribuição
Tamanho do cenário (número de clientes)
Demanda total
118
3296
90
1843
70
1777
125
3342
100
2757
60
1287
80
2275
70
1677
50
1104
124
Parâmetros de roteirização utilizados no presente trabalho
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Alto volume - Pontos concentrados próximos um dos outros
8
59
36
9:40
2:40
2:22
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Alto volume - Pontos concentrados próximos um dos outros
8
108
53
9:40
3:59
3:31
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Médio volume - Pontos concentrados próximos um dos outros
7
59
39
9:40
3:21
2:23
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Médio volume - Pontos concentrados próximos um dos outros
7
88
53
9:40
5:30
4:02
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Baixo volume - Pontos concentrados próximos um dos outros
6
60
33
9:40
2:40
2:31
125
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Baixo volume - Pontos concentrados próximos um dos outros
6
108
50
9:40
4:01
3:31
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Alto volume - Pontos concentrados e afastados um dos outros
9
67
28
9:40
2:18
2:16
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Alto volume - Pontos concentrados e afastados um dos outros
9
99
42
9:40
4:23
3:36
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Médio volume - Pontos concentrados e afastados um dos outros
9
71
35
9:40
3:29
2:24
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Médio volume - Pontos concentrados e afastados um dos outros
9
127
51
9:40
6:36
4:09
126
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Baixo volume - Pontos concentrados e afastados um dos outros
9
70
34
9:40
2:45
2:14
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Baixo volume - Pontos concentrados e afastados um dos outros
9
136
48
9:40
4:34
3:36
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Alto volume - Pontos ao redor da central de distribuição
8
21
26
9:40
2:20
1:46
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Alto volume - Pontos ao redor da central de distribuição
8
47
44
9:40
4:17
3:03
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Médio volume - Pontos ao redor da central de distribuição
7
26
31
9:40
2:38
2:20
127
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Médio volume - Pontos ao redor da central de distribuição
7
81
52
9:40
5:11
3:43
(Média)
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Baixo volume - Pontos ao redor da central de distribuição
6
22
32
9:40
2:53
1:59
Maior
Nº Rotas Máx
Dist. Máx
Nº de entregas
Tempo em Rota
Tempo de espera
Tempo de deslocamento
Baixo volume - Pontos ao redor da central de distribuição
6
70
47
9:40
4:25
3:40