Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
CAIO MEZZETI GIORDANO
RESOLUÇÃO DE UM PROBLEMA DE LOCALIZAÇÃO E ROTEIRIZAÇÃO DE
VEÍCULOS NA INDÚSTRIA DE TRANSFORMAÇÃO DE VIDRO
São Paulo
2016
CAIO MEZZETI GIORDANO
RESOLUÇÃO DE UM PROBLEMA DE LOCALIZAÇÃO E ROTEIRIZAÇÃO DE
VEÍCULOS NA INDÚSTRIA DE TRANSFORMAÇÃO DE VIDRO
Trabalho de Formatura apresentado à Escola
Politécnica da Universidade de São Paulo para
a obtenção do Diploma de Engenheiro de
Produção
São Paulo
2016
CAIO MEZZETI GIORDANO
RESOLUÇÃO DE UM PROBLEMA DE LOCALIZAÇÃO E ROTEIRIZAÇÃO DE
VEÍCULOS NA INDÚSTRIA DE TRANSFORMAÇÃO DE VIDRO
Trabalho de Formatura apresentado à Escola
Politécnica da Universidade de São Paulo para
a obtenção do Diploma de Engenheiro de
Produção
Orientadora:
Profª. Dra. Débora Pretti Ronconi
São Paulo
2016
FICHA CATALOGRÁFICA
AGRADECIMENTOS
À minha família pelo suporte, amor e valores recebidos. Estes elementos compõe a
bússola com a qual eu procuro me guiar todos os dias.
À professora Débora Pretti Ronconi pelo seu papel dentro da minha graduação. Por ter
me introduzido à Pesquisa Operacional no curso ministrado na graduação do qual eu tive a
oportunidade e prazer de participar. Agradeço à professora também pela paciência, pelo
incentivo e pela dedicação transmitida ao longo da orientação deste trabalho de formatura, me
dando sempre o suporte necessário para avançar.
À empresa Saint-Gobain e aos meus colegas dentro da empresa, por terem acreditado
no meu potencial, me recebendo como estagiário por cerca de 8 meses e contribuindo com a
minha formação acadêmica e profissional.
Ao professor Eduardo de Senzi Zancul com quem eu tive o prazer de trabalhar,
contribuindo com minha formação acadêmica e profissional, principalmente em termos de rigor
e dedicação.
Às professoras e aos professores da Escola Politécnica da Universidade de São Paulo
pela competência técnica, rigor e seriedade que contribuíram com minha formação acadêmica
e no meu papel como futuro profissional.
À Rebeca pela companhia, por acreditar e por me motivar a sempre melhorar.
Aos meus amigos e colegas de turma pelo suporte recebido e pelos momentos
compartilhados.
RESUMO
Este trabalho buscou estudar o modelo de distribuição de uma empresa de transformação
de vidros, identificando ineficiências e buscando propor, com o auxílio de técnicas de pesquisa
operacional, uma configuração de transporte mais eficiente. Decidiu-se concentrar as análises
nas operações da empresa na Noruega, em que se tem um alto e importante custo de transporte.
Para otimização da distribuição da empresa considerou-se a otimização dos roteiros de entrega
e a possibilidade de utilização de novos centros de distribuição. Tem-se, portanto, um problema
misto de localização e de roteirização de veículos com particularidades como frota homogênea
e janelas de tempo. Desenvolve-se também a modelagem matemática do problema
caracterizado como de programação linear inteira mista (PLIM). Dado o caráter NP-hard do
problema utilizou-se uma heurística construtiva sequencial para obtenção de soluções de boa
qualidade para o problema em sua dimensão completa. O trabalho permitiu a proposição de um
novo modelo de distribuição, com a utilização de dois centros de distribuição, o que resultou
em importantes economias nos custos de distribuição da empresa. Discorre-se, ainda, sobre a
metodologia de levantamento de dados e de implementação da solução na empresa e sobre
possíveis replicações do processo de otimização descrito em outras unidades da empresa.
Palavras-chave: Pesquisa Operacional. Logística. Localização. Roteirização.
ABSTRACT
This work studied the distribution model of a glass processing company, identifying
inefficiencies and trying to propose, using operations research techniques, a more efficient
transport configuration. The study focus on the company’s Norwegian operations, where it has
a high and important shipping cost. To optimize the company’s distribution, the study
considered the optimization of delivery routes and possible use of new distribution centers. It
is therefore a mixed problem of location and vehicle routing with specific characteristics such
as a homogeneous fleet and time windows. The work also develops on the mathematical
modeling of the problem, characterized as mixed linear integer program. Given the NP-hard
character of the problem a sequential constructive heuristics was used to obtain good quality
solutions to the problem in its full dimension. The work allowed the proposition of a new
distribution model, using two distribution centers, which resulted in important savings in the
company's distribution costs. The study elaborates also on the data collection methodology and
implementation of the solution in the company and possible replication of the optimization
process described in other business units.
Keywords: Operations Research. Logistics. Location. Routing.
LISTA DE FIGURAS
Figura 1: Distribuição geográfica da empresa. ......................................................................... 18
Figura 2: Organização da empresa Saint-Gobain Glassolutions. ............................................. 21
Figura 3: Instalações produtivas e comercias de Saint-Gobain Glassolutions na Europa. ....... 22
Figura 4: Cadeia de valor simplificada do vidro segundo a organização Saint-Gobain........... 23
Figura 5: Estoque do vidro float em uma fábrica Glassolutions. ............................................. 26
Figura 6: operações dentro de uma fábrica Glassolutions ........................................................ 26
Figura 7: Palete adaptado para o transporte de produtos de vidros. ......................................... 28
Figura 8: Cavalete de uma face para estoque e transporte de vidro. ........................................ 28
Figura 9 : Cavalete de duas faces para transporte de vidro. ..................................................... 28
Figura 10 : Cavalete com rodas para transporte de vidro. ........................................................ 29
Figura 11: Cavalete com rodas para transporte de vidro de uma fábrica Glassolutions .......... 29
Figura 12: Cavalete com rodas nos trilhos da plataforma elevadora durante carregamento de
um caminhão. ........................................................................................................................... 30
Figura 13: Funcionário Saint-Gobain prende os cavaletes nos trilhos dos caminhões. .......... 30
Figura 14: Sistema de trilhos em um caminhão para fixação dos cavaletes no caminhão. ...... 31
Figura 15 : Exemplo de uma rota de entrega realizada por um caminhão Glassolutions. A
estrela azul representa a fábrica e os pontos pretos seguidos do número da parada, os clientes
visitados. ................................................................................................................................... 34
Figura 16: Clássico trade-off entre o nível de serviço oferecido e os custos logísticos. .......... 35
Figura 17: Localização dos centros de distribuição de Glassolutions na Noruega. ................. 37
Figura 18: Importação de produtos de países vizinhos. ........................................................... 38
Figura 19: Possibilidade de otimização da distribuição na Noruega com a utilização de centros
de distribuição (CD) da transportadora parceira....................................................................... 39
Figura 20: Instalações da empresa (Oslo e Fredrikstad) e centros de distribuição estudados
(amarelo). .................................................................................................................................. 40
Figura 21: Ilustração da repartição dos clientes em janelas de tempo...................................... 50
Figura 22: Veículo 2 realiza entregas sem ter iniciado pelo centro de distribuição (CD). ....... 55
Figura 23: Conservação dos fluxos de entrada e saída ............................................................. 55
Figura 24: Roteiro com a ocorrência de subtours. .................................................................... 57
Figura 25: Ilustração do funcionamento da restrição 10. ......................................................... 59
Figura 26: Etapas da metodologia para otimização de rotas .................................................... 62
Figura 27: Gráfico de sazonalidade ao longo do ano para uma fábrica Glassolutions. ............ 65
Figura 28: Etapas de implementação da solução ...................................................................... 68
Figura 29: Heurística de inserção para roteamentos baseado em Solomon (1987). ................ 76
Figura 30: Heurística sequencial construtiva para resolução do problema de localização e
roteirização. .............................................................................................................................. 77
Figura 31: mapa da Noruega com depósitos candidatos em amarelo e o depósito existente de
Fredrikstad em azul. ................................................................................................................. 81
Figura 32: Mapa da Noruega com os dois centros de distribuição utilizados na solução
proposta. ................................................................................................................................... 83
Figura 33: Número de roteiros de entrega por dia da semana para Fredrikstad e Hamar. ....... 88
Figura 34: Distribuição do total de 𝑚2 de vidros entregues ao longo da semana para os
centros de distribuição de Fredrikstad e Hamar. ...................................................................... 88
Figura 35 : Variação do custo total de distribuição da solução apresentada em relação ao custo
total do modelo atual corrigido pelo aumento do custo de transporte. .................................... 92
Figura 36: Variação do custo total de distribuição da solução apresentada em relação ao custo
total do modelo atual para os diferentes experimentos realizados. .......................................... 93
LISTA DE TABELAS
Tabela 1: Exemplos de produtos da Saint-Gobain Glassolutions ............................................ 20
Tabela 2: Algumas das características atribuídas aos produtos Glassolutions. ........................ 24
Tabela 3: Principais operações de transformação nas fábricas Glassolutions. ......................... 27
Tabela 4: Maiores centros urbanos da Noruega e suas populações (STATISTISK
SENTRALBYRA, 2015b) ........................................................................................................ 41
Tabela 5: Classificação do problema retratado neste trabalho segundo os critérios de (MIN;
JAYARAMAN; SRIVASTAVA, 1998). ................................................................................. 47
Tabela 6: Janela de entrega para as respectivas frequências de entrega (1: segunda-feira e 5:
sexta-feira) ................................................................................................................................ 50
Tabela 7: Resolução de maneira exata de problemas menores ................................................ 70
Tabela 8 : Resolução de versões reduzidas com a heurística proposta e comparação com a
resolução exata ......................................................................................................................... 78
Tabela 9: Resultados para cada cenário na resolução completa do problema utilizando método
heurístico .................................................................................................................................. 82
Tabela 10: Coeficientes de centralidade para os diferentes depósitos candidatos. .................. 82
Tabela 11 : Roteiros sugeridos para o centro de distribuição de Fredrikstad na solução proposta.
.................................................................................................................................................. 84
Tabela 12: Roteiros sugeridos para o centro de distribuição de Hamar na solução proposta. . 85
Tabela 13: Dias de execução dos roteiros sugeridos para o centro de distribuição de Fredrikstad.
.................................................................................................................................................. 85
Tabela 14: Dias de execução dos roteiros sugeridos para o centro de distribuição de Hamar.
.................................................................................................................................................. 86
Tabela 15: Solução obtida para hipótese de aumento de 10% nos custos de transporte. ......... 90
Tabela 16: Solução obtida para hipótese de aumento de 20% nos custos de transporte. ......... 90
Tabela 17: Solução obtida para hipótese de aumento de 30% nos custos de transporte. ......... 90
Tabela 18: Solução obtida para hipótese de aumento de 30% nos custos de transporte. ......... 91
Tabela 19: Solução obtida para hipótese de aumento de 50% nos custos de transporte. ......... 91
LISTA DE SIGLAS
R&D – Research and Development
VRP – Vehicle Routing Problem
VRPSD – Vehicle Routing Problem with Split Deliveries
VRPTWSD – Vehicle Routing Problem with Time Windows and Split Deliveries
CARPTWSD – Capacitated Arc Routing Problem with Time Windows and Split Deliveries
PLIM – Programação Linear Inteira Mista
LVRPTWMD - Location Vehicle Routing Problem with Time Windows and Multiple Deposits
S.a. – Sujeito a
SUMÁRIO
INTRODUÇÃO ...................................................................................................................... 13
1. DESCRIÇÃO DA EMPRESA ....................................................................................... 17
1.1. O grupo Saint Gobain .......................................................................................... 17
1.2. Materiais inovadores e Glassolutions ................................................................. 18
1.3. Cadeia de valor do vidro ...................................................................................... 22
1.3.1. Produção do vidro plano ............................................................................... 23
1.3.2. Transformações nas unidades fabris de Glassolutions ............................... 24
1.3.3. Distribuição .................................................................................................... 27
2. ESTUDO DO PROBLEMA ........................................................................................... 31
2.1. O interesse de Glassolutions na otimização de sua distribuição ...................... 33
2.2. Descrição do problema ......................................................................................... 36
3. REVISÃO BIBLIOGRÁFICA ....................................................................................... 43
3.1. Problemas de localização e roteirização de veículos.......................................... 43
3.2. Métodos de Resolução .......................................................................................... 47
4. MODELAGEM DO PROBLEMA ................................................................................ 49
4.1. Considerações sobre o problema ......................................................................... 49
4.2. Formulação Matemática ...................................................................................... 51
4.3. Detalhamento do Modelo ..................................................................................... 54
5. METODOLOGIA DE LEVANTAMENTO DE DADOS E DE IMPLEMENTAÇÃO
DA SOLUÇÃO ........................................................................................................................ 59
5.1. Levantamento de dados (rotas, clientes, frota, zonas de entrega) .................... 62
5.2. Análise da situação atual ...................................................................................... 66
5.3. Modelagem matemática do problema especificado ........................................... 67
5.4. Adaptar, implementar e controlar a solução ..................................................... 67
6. RESOLUÇÃO DO PROBLEMA .................................................................................. 69
6.1. Resolução exata de versões reduzidas ................................................................. 69
6.2. Heurística Construtiva de Localização de Centros de Distribuição e de
Roteirização..................................................................................................................72
6.2.1. Validação do método heurístico apresentado ............................................. 78
6.2.2. Implementação da heurística ....................................................................... 79
7. ANÁLISE DOS RESULTADOS ................................................................................... 81
7.1. Solução Proposta .................................................................................................. 81
7.2. Análise de Sensibilidade ...................................................................................... 89
7.2.1. Aumento do custo de transporte .................................................................. 89
7.2.2. Redução dos custos de utilização dos depósitos .......................................... 93
CONCLUSÃO ........................................................................................................................ 95
APÊNDICE A – FICHA DE LEVANTAMENTO DE INFORMAÇÕES ........................ 99
APÊNDICE B – MODELAGEM DO PROBLEMA EM CPLEX OPL ......................... 101
APÊNDICE C – CÓDIGO DA HEURÍSTICA EM VBA ................................................ 107
APÊNDICE D – EXTRATO DA MATRIZ DE CUSTO DE DESLOCAMENTO ENTRE
CLIENTES E DEPÓSITOS ................................................................................................ 127
APÊNDICE E –EXTRATO DA MATRIZ DE TEMPO DE DESLOCAMENTO ENTRE
CLIENTES E DEPÓSITOS ................................................................................................ 129
13
INTRODUÇÃO
Neste trabalho abordou-se o estudo e otimização do processo de distribuição de uma
empresa de transformação de vidros. A empresa considerada no trabalho é a subsidiária do
grupo francês Saint-Gobain, responsável pelo processamento e distribuição de vidro para o
mercado da construção na Europa, Saint-Gobain Glassolutions. A empresa adquire vidros
planos simples e transforma-os segundo especificações dos clientes para seu uso em produtos
industriais, comércio, casas e escritórios. O autor realizou estágio profissional de 8 meses na
sede da empresa, em Paris, período no qual tomou conhecimento de seu funcionamento, dos
problemas existentes e realizou a coleta de dados para o trabalho aqui apresentado.
Como parte do seu plano estratégico de redução de custos, Saint-Gobain Glassolutions
procura desenvolver, testar e implementar novos processos para otimizar seus meios de
distribuição. Procura-se uma maneira padronizada de analisar dados históricos e, com ajuda de
modelos matemáticos, propor configurações de transportes de menor custo que permitam à
empresa melhor servir seus clientes.
Dentro deste contexto, as operações do grupo na Noruega surgem como candidato ideal
para um projeto de otimização que reveja o modelo de distribuição e as rotas de entrega
existente. No caso da Noruega, os custos com mão de obra são altos e superiores aos países
vizinhos o que encarece qualquer operação no país. De fato, a operação da empresa no país
possui um dos maiores custos logísticos por 𝑚2 de produto transportado. Para reduzir os custos
da operação, hoje a produção está concentrada em outros países, como Alemanha e Polônia, e
a distribuição na Noruega é realizada a partir de um único centro de distribuição no sul do país,
em Fredrikstad. Como os encargos de trabalho no país são elevados, a empresa optou por
terceirizar o transporte de seus produtos. Com o acordo previsto com a transportadora, cabe à
fábrica carregar os caminhões da transportadora e informar a lista de clientes à serem entregue
pelo caminhão.
No modelo atual, toda a distribuição no país é concentrada na fábrica de Fredrikstad, no
extremo sul da Noruega e distante de diversos centros urbanos e de concentrações de clientes.
Procurou-se, portanto, rever as rotas de entrega no país considerando também a possibilidade
de utilização de novos depósitos em outras regiões da Noruega. Na nova configuração,
Fredrikstad não funcionaria mais como ponto de partida único para a distribuição, com outros
depósitos espalhados pelo país também recebendo das fábricas produtoras e redistribuindo-os
à clientes próximos.
14
Tem-se caracterizado, portanto, um problema misto de localização e roteirização de
veículos que trata da junção de dois problemas clássicos de alta complexidade de pesquisa
operacional. Face à complexidade do problema necessitou-se da utilização de técnicas de
pesquisa operacional que permitisse a obtenção de soluções de boa qualidade de maneira rápida
e de fácil implementação.
O trabalho está estruturado em 10 capítulos abrangendo detalhes das operações da
empresa, do problema enfrentado e dos métodos e ferramentas utilizados para resolução do
problema.
O Capítulo 2 apresenta o grupo Saint-Gobain e sua subsidiária para transformação do
vidro, Glassolutions. Descreve-se a empresa, sua organização, seus produtos e processos e seus
clientes podendo, assim, compreender as operações e os riscos envolvidos nestes processos.
No Capítulo 3 apresenta-se a definição do problema abordado neste trabalho,
delimitando-o e estabelecendo de maneira clara os objetivos da otimização. O contexto e riscos
envolvidos também são apresentados
Uma revisão da literatura sobre os tópicos de otimização de rotas e de problemas de
localização, ambos abordado neste trabalho, é apresentada no Capítulo 4. Procura-se
compreender as variações de problemas encontrados na literatura, suas classificações e
particularidades. Abrange-se, também neste capítulo, uma revisão da literatura sobre os
diferentes métodos de resolução do problema NP-hard de localização e roteirização de veículos.
No Capítulo 5 desenvolve-se a modelagem matemática do problema. Apresenta-se,
também, um detalhamento do modelo com a explicação das restrições empregadas.
O Capítulo 6 apresentará a metodologia de coleta e tratamento de dados. Fará
considerações também sobre cuidados necessários para implementação da solução uma vez que
ela tenha sido obtida.
Tópicos referentes à resolução do problema são apresentados no Capítulo 7. Apresenta-
se o limite computacional da resolução exata do problema e, em seguida, introduz-se a
heurística construtiva desenvolvida para resolução do problema. Utiliza-se das resoluções
exatas de versões reduzidas do problema para testar e comparar a heurística apresentada.
Finalmente, são feitas considerações sobre a implementação computacional da heurística.
15
No Capítulo 8 discorre-se sobre os resultados obtidos na resolução do problema
completo com o método heurístico apresentado. Compara-se a solução apresentada com a
situação atual, permitindo avaliar os ganhos obtidos com a otimização proposta.
O Capítulo 9 apresenta as conclusões do estudo, pontos de melhoria e possibilidade de
replicar o estudo em outras fábricas do grupo na Europa.
Ao final do trabalho, lista-se as referências bibliográficas e os apêndices, com os
programas computacionais e exemplo de dados utilizados para a resolução do problema
17
1. DESCRIÇÃO DA EMPRESA
Neste primeiro capítulo, apresenta-se a empresa na qual o trabalho será realizado, Saint-
Gobain Glassolutions. Na Seção 1.1 caracteriza-se o conglomerado industrial controlador de
Glassolutions, Saint-Gobain. Na seção seguinte apresenta-se a subsidiária Glassolutions e seus
produtos, derivados do vidro. Na seção 1.3 destaca-se a cadeia de valor do vidro, ilustrando os
processos produtivos da empresa e como esta está inserida no ciclo de vida total do produto.
1.1. O grupo Saint Gobain
A Saint-Gobain é um grupo francês líder mundial na produção, transformação e distribuição
de materiais. A empresa lida com, por exemplo, produção e distribuição de vidros para edifícios
(interior e exterior) e automóveis, tubos, gesso, isolamento acústico e térmico, revestimentos
de parede, materiais de alto desempenho, tais como cerâmica, cristais, grãos abrasivos e outros.
Este gigante do mundo dos materiais tem uma longa e rica história. A empresa em 2015
comemorou seus 350 anos, um dos grupos mais tradicionais do mundo. Foi criado em 1665
pelo rei da França Louis XIV para confrontar a supremacia de Veneza na fabricação de espelhos
e foi responsável pela criação da sala de espelhos do Palácio de Versalhes em 1684.
Nos anos seguintes, o grupo diversificou suas atividades para enfrentar rápidas e constantes
mudanças no desenvolvimento de novas tecnologias e materiais, mudanças de comportamento
dos consumidores e mudanças nos padrões arquitetônicos e de construção no mundo. Este
dinamismo é confirmado ainda hoje com o objetivo da empresa de ser referência no lar
sustentável.
Hoje, o grupo conta com 180 000 colaboradores espalhados por 945 escritórios e locais de
produção em todo o mundo. O grupo teve um faturamento de € 39,6 bilhões em 2015, dos quais
69% na Europa. No entanto, Saint-Gobain reconhece a importância crescente de outros países,
incluindo países emergentes, e realiza investimentos significativos nestes países. O continente
asiático e países emergentes são juntos responsáveis por 20% do seu volume de negócios e,
como mostrado na Figura 1, a empresa tem instalações de produção em 66 países e centros de
pesquisa e desenvolvimento (R&D) no Brasil, Índia e na China (SAINT-GOBAIN, 2015a).
18
Figura 1: Distribuição geográfica da empresa.
Fonte: traduzido de (SAINT-GOBAIN, 2015a).
O grupo divide suas mais de 50 atividades em três segmentos (SAINT-GOBAIN,
2015a):
• Distribuição para construções: serve mercados de novas construções, renovação e restauração
da habitação e representa 48% das vendas do grupo;
• Materiais de Construção: oferece soluções internas e externas para aumentar o conforto das
habitações e é responsável por 28% das vendas do grupo.
• Materiais inovadores: composto por duas grandes operações, a produção de vidros e de
materiais de alto desempenho sendo responsável por 24% do volume de negócios do grupo.
A subsidiária do grupo para transformação do vidro e em que se aprofundou as análises
deste trabalho, Glassolutions, encontra-se dentro do segmento de materiais inovadores. Na
seção a seguir descreve-se em maiores detalhes este segmento e a empresa específica na qual
se realizou o trabalho.
1.2. Materiais inovadores e Glassolutions
O Setor de materiais inovadores também inclui a divisão de vidros do grupo, com a
produção de vidro plano (ou float), realizada por Saint-Gobain Glass, transformação e
distribuição de vidro para o mercado de construção e renovação, executada por Saint-Gobain
Glassolutions e vidros automotivos, executada por Saint-Gobain Sekurit.
19
Glassolutions é a rede do grupo Saint-Gobain, repartida em diversos países da Europa,
responsável pela compra do vidro float, placas individuais de vidro plano, e sua transformação
segundo cada pedido do cliente para o mercado de construção e renovação (janelas, fachadas,
equipamentos urbanos, marcenaria industrial, mobiliário, elementos de banheiro, vidros
decorativos, entre outros). Esta rede é composta de 200 pontos comerciais ou de produção em
17 países europeus com o emprego de cerca de 10.000 colaboradores. Na Tabela 1 podemos
visualizar algumas aplicações dos vidros produzidos pela Glassolutions.
Dentre as operações de transformações nas fábricas da Saint-Gobain Glassolutions tem-se
corte, têmpera, impressão, acabamento, montagem, produção de vidros insulados, entre outras.
Cada operação visa adaptar o produto ao projeto do cliente, levando em consideração diversas
características críticas do vidro como sua dimensão, isolamento térmico, isolamento acústico,
resistência à quebra, estética e transmissão de luz. Sabendo que para cada característica do
vidro, existem diversos níveis de performance a partir do qual o cliente pode escolher e que o
cliente tem a opção de especificar qualquer dimensão de vidro, chega-se a um número infinito
de permutações possíveis. Isto significa que qualquer transformação é personalizada de acordo
com as necessidades do cliente e só é realizada uma vez que o pedido do cliente é efetuado. O
cliente transmite todas as especificações do seu projeto e dos vidros que ele precisa para a
empresa que, por sua vez, produz e entrega os vidros que atendam às dimensões e características
especificadas. Trata-se, portanto, de um clássico caso de make-to-order, com produção
completamente personalizada.
O cliente final de Glassolutions é o proprietário do edifício onde o vidro será instalado, seja
para utilização externas (janelas e fachadas de prédios), ou para uso interno (guarda-corpos,
escadas, elementos de banheiros, e todas as demais aplicações de vidro em imóveis). No
entanto, a empresa tem pouco contato com o cliente final. Na maioria dos casos, é um instalador
ou empreiteiro que desenvolve um projeto de vidros para o proprietário do imóvel, e transmite
os pedidos para a fábrica Glassolutions mais próxima. Uma vez que os vidros são entregues, o
instalador ou empreiteiro se encarrega da instalação do vidro no imóvel do cliente final. O
endereço de entrega pode ser a oficina comercial do instalador ou empreiteiro que realizou os
pedidos, canteiros de obras, no imóvel do cliente final, ou lojas de material de construção.
Algumas fábricas específicas também possuem equipes que executam instalações a pedido dos
clientes.
20
Tabela 1: Exemplos de produtos da Saint-Gobain Glassolutions
Guarda corpos
Box de duchas
Telhados
Portas
Fachadas
Fonte: (GLASSOLUTIONS, 2016).
21
A empresa também está organizada de acordo com os diferentes segmentos de clientes.
Cada segmento possui necessidades diferentes em termos de serviço e de tipo de produto. A
estrutura de comercialização, produção e entrega de vidros para fachadas de grandes prédios
comerciais é muito diferente da estrutura necessária para servir pequenos instaladores de
janelas. Por consequente, o grupo divide sua força comercial e suas fábricas em função destes
segmentos. Esta organização está ilustrada na Figura 2.
Figura 2: Organização da empresa Saint-Gobain Glassolutions.
Fonte: elaborado pelo autor.
O segmento regional atende os pequenos empreiteiros e instaladores de vidros para lares
e pequenos comércios. Trata-se, portanto, de uma grande variedade de clientes com pequenos
pedidos.
O segmento Windows foca em servir grandes fabricantes de janelas.
No segmento OEM – Original Equipment Manufacturer, em português fabricante de
equipamento original, e Retail, em português varejo, atende-se empresas industriais que
utilizam vidros em seus produtos, tais como fabricantes de mobiliário e de espelhos.
Finalmente, no segmento de vidros de performance, busca-se aplicações especificas e
de alta performance de vidros com produtos de alto valor agregado. Trata-se por exemplo de
vidros resistentes a altas temperaturas em fornos ou bloqueadores de radiação para salas de raio-
x em hospitais.
É importante ressaltar que apesar do grupo Saint-Gobain estar presente em cerca de 66
países, o perímetro de atividades da Glassolutions é a Europa. Esta segregação é explicada pela
história de crescimento por aquisições do grupo e pela necessidade de desenvolvimento de
22
marcas locais. Assim, o grupo atua nas diferentes regiões do mundo através de inúmeras
empresas. Na Figura 3 podemos visualizar as diferentes instalações de Glassolutions na Europa.
Figura 3: Instalações produtivas e comercias de Saint-Gobain Glassolutions na Europa.
Fonte: (SAINT-GOBAIN, 2015b).
1.3. Cadeia de valor do vidro
O vidro passa por várias transformações ao longo de sua cadeia de valor. O vidro float
produzido em fábricas de vidro é o produto base para todas as aplicações da indústria de vidro,
desde aplicações em imóveis residenciais e comerciais, até aplicações na indústria de garrafas
e automotiva. O que diferencia o vidro em cada aplicação são as operações de transformação
específicas para transmitir ao vidro as características e dimensões desejadas para cada
aplicação. Glassolutions é a entidade de Saint-Gobain responsável pelo processamento e
distribuição do vidro para o mercado da construção. A Figura 4 exemplifica de forma
simplificada a cadeia de valor do vidro
23
Figura 4: Cadeia de valor simplificada do vidro segundo a organização Saint-Gobain
Fonte das imagens: (SAINT-GOBAIN SEKURIT, 2016) e (SAINT-GOBAIN, 2015b)
1.3.1. Produção do vidro plano
O vidro float é o produto base para todas as aplicações de vidro e é produzido em grandes
fábricas de uma subsidiária específica do grupo, Saint-Gobain Glass. As fases de produção
deste tipo de vidro são as seguintes (SAINT-GOBAIN, 2015c):
1. Fusão: as matérias-primas do vidro (sílica, soda, cal, feldspato e dolomita) e vidro reciclado
(aparatas de vidro) são misturados em um forno aquecido a gás, a temperaturas de 1.550 ° C.
2. Banho de estanho: a mistura líquida é jogada sobre estanho fundido a 1.000 ° C e, uma vez
que o vidro é menos denso do que o estanho, ele "flutua" sobre ele, origem do nome “float” do
vidro nesta etapa. Rodas dentadas esticam o vidro lateralmente em função da espessura desejada
(2-19 mm).
3. Resfriamento: depois do banho de estanho, o vidro tornou -se rígido e passa através de um
túnel de arrefecimento controlado. A sua temperatura cai para 250 ° C. Em seguida, é
lentamente resfriado ao ar livre.
4. Corte: a fita de vidro fino, até aqui contínua, é cortada em placas de 6000x3210 mm e
preparada para transporte.
24
1.3.2. Transformações nas unidades fabris de Glassolutions
O vidro da Saint-Gobain Glassolutions pode ter várias características e especificações
para atender às necessidades de cada cliente. A utilização do vidro, a localização geográfica do
cliente, o nível desejado de conforto, acabamento e dimensões especificadas pelo cliente
formam uma infinidade de variações de produto que Glassolutions deve estar preparada para
produzir através de operações de transformação do vidro float. A Tabela 2 apresenta algumas
características incorporadas ao vidro através de operações dentro das fábricas da Glassolutions.
Tabela 2: Algumas das características atribuídas aos produtos Glassolutions.
Vidros insulados
Isolação acústica
Blindagem
Vidros estampados
Resistência ao calor e incêndios
25
Controle da transmissão de luz
Proteção contra radiação
Fonte: (SAINT-GOBAIN, 2015b)
Para dar ao vidro suas características e para atender as especificações do cliente, placas
de vidro float passam por várias operações de transformação dentro das fábricas Glassolutions.
Na Figura 5 pode-se ver a estocagem de placas de vidro plano (float) em uma fábrica
Glassolutions aguardando sua transformação. Já a Figura 6 apresenta a ordenação das operações
de transformação dentro de uma fábrica enquanto que na Tabela 3 vemos os tipos de
transformação mais comuns nas fábricas Glassolutions. Outros tipos de transformações são
mais específicos e centrada em fábricas específicas do grupo.
26
Figura 5: Estoque do vidro float em uma fábrica Glassolutions.
Fonte: (Saint-Gobain, 2015)
Figura 6: operações dentro de uma fábrica Glassolutions
Fonte: elaborado pelo autor
27
Tabela 3: Principais operações de transformação nas fábricas Glassolutions.
Corte
Facetamento e lapidação
Tempera
Produção de vidro
insular
Fonte: (SAINT-GOBAIN, 2015b)
1.3.3. Distribuição
A distribuição de produtos de vidro pela rede Saint-Gobain Glassolutions é
responsabilidade do local de produção (transformação) e é realizada com caminhões próprios
das fábricas ou por transportadoras externas. Nos últimos anos, com o objetivo de flexibilizar
suas operações, Glassolutions decidiu não mais ter caminhões em propriedade da empresa.
Deste modo, ao final do ciclo de vida de um caminhão em propriedade da empresa, ele é
substituído por um veículo alugado, com ou sem motorista incluso no aluguel, e com termos de
contrato variáveis segundo as necessidades de cada fábrica. No entanto, hoje muitas fábricas
ainda estão em processo de transição, havendo uma mistura de caminhões adquiridos e alugados
em suas frotas.
Nesta indústria, um período médio ou longo termo de contrato é comum pois os
caminhões que a empresa utiliza para entregas devem ser adaptados com, por exemplo, a
instalação de trilhos para movimentação e fixação dos cavaletes.
Para transportar o vidro, as fábricas utilizam equipamentos adaptados para o produto
como carrinhos, paletes adaptados, cavaletes de madeira, aço ou uma mistura dos dois
28
materiais, tipicamente com um formato triangular para melhor distribuir o peso do vidro e
facilitar a carga e descarga dos produtos. Nas figuras 7 a 10 pode-se ver os equipamentos típicos
utilizados para transporte e armazenamento dos produtos de vidro.
Figura 7: Palete adaptado para o transporte de produtos de vidros.
Fonte: (AMS CHARIOTS, 2016).
Figura 8: Cavalete de uma face para estoque e transporte de vidro.
Fonte: (AMS CHARIOTS, 2016).
Figura 9 : Cavalete de duas faces para transporte de vidro.
Fonte: (AMS CHARIOTS, 2016).
29
Figura 10 : Cavalete com rodas para transporte de vidro.
Fonte: (AMS CHARIOTS, 2016).
Estes diferentes tipos de cavaletes ou paletes são carregados em caminhões e entregues
aos clientes de Glassolutions. Dado o elevado peso destes equipamentos carregados ou vazios,
deve-se utilizar equipamentos como guindastes, pontes ou plataformas elevatórias para carregar
ou descarregar os caminhões. Nas Figuras 11 a 14, pode-se ver o uso de cavaletes em uma
fábrica da Saint-Gobain Glassolutions e o carregamento de um caminhão com a ajuda de
plataformas elevadoras.
Figura 11: Cavalete com rodas para transporte de vidro de uma fábrica Glassolutions
Fonte: elaborado pelo autor
30
Figura 12: Cavalete com rodas nos trilhos da plataforma elevadora durante carregamento de um caminhão.
Fonte: elaborado pelo autor
Figura 13: Funcionário Saint-Gobain prende os cavaletes nos trilhos dos caminhões.
Fonte: elaborado pelo autor
31
Figura 14: Sistema de trilhos em um caminhão para fixação dos cavaletes no caminhão.
Fonte: elaborado pelo autor
Uma característica da indústria do vidro na Europa é que a maioria dos clientes solicita
a guarda dos equipamentos (cavaletes) no momento da entrega. Produtos de vidro são pesados,
frágeis e, portanto, de difícil manuseio sem esses equipamentos de auxílio. Desta forma, no
padrão de serviço estabelecido pela indústria, a empresa entrega cavaletes com os vidros
encomendados pelo cliente e deve retornar ao local posteriormente (em dias ou semanas) para
recuperar os equipamentos deixados. No entanto, por causa do alto número de clientes e de
pedidos e pela variedade de endereços de entrega (muitos clientes solicitam entregas diretas nos
canteiros de construção), a empresa possui problemas da rastreabilidade de seus equipamentos.
Além disso é comum haver erros de procedimentos, como quando um entregador esquece de
realizar a leitura digital de um rack antes da entrega. Em muitos casos, os próprios clientes
perdem ou se apropriam dos cavaletes. Entretanto, estes problemas podem ter alto custo à
empresa, com o custo de um equipamento de entrega podendo custar cerca de 500 euros.
Além de problemas com as perdas dos equipamentos, o fato de a empresa ter que
retornar aos pontos de entrega apenas para recuperar equipamentos vazios, representa desafios
adicionais de distribuição e consequentemente de custos logísticos. Para os clientes regulares,
a empresa pode aproveitar de uma próxima entrega para recuperar o equipamento deixado na
última entrega. No entanto, para clientes não regulares e canteiros de construção, a empresa
deve realizar uma visita adicional apenas para recuperar seu equipamento.
33
2. ESTUDO DO PROBLEMA
Este capítulo é dedicado ao estudo do problema que se propõe resolver neste trabalho.
Inicia-se o capítulo pela contextualização da operação de distribuição da empresa evidenciando
potenciais ganhos em termos de serviço aos clientes e de custos com sua otimização.
Em seguida, delimita-se o escopo do problema a ser resolvido com a identificação de uma
oportunidade clara de otimização nas operações da empresa na Noruega. Apresenta-se detalhes
desta operação, com o mapeamento de fornecedores e focos de clientes. Compreende-se, assim,
restrições, vantagens e desvantagens da distribuição de produtos na Noruega podendo-se,
assim, estabelecer objetivos para o problema a ser resolvido.
2.1. O interesse de Glassolutions na otimização de sua distribuição
A fim de obter melhores resultados financeiros, a rede Glassolutions está buscando
maneiras de aumentar a receita e reduzir os custos, especialmente no segmento regional. Neste
segmento, o elevado custo de transporte pode ser explicado pelo nível de serviço oferecido aos
clientes, pela necessidade de proximidade ao cliente, pelas complexidades de entrega, e altos
custos de manutenção e operação de uma frota de caminhões na Europa.
Hoje os clientes exigem pouco tempo de entrega e a possibilidade de receber os produtos
diretamente em seus canteiros de obra. É importante ressaltar novamente que os produtos da
empresa consistem de vidros feitos sob medida, de acordo com as especificações do projeto de
cada cliente. Portanto, para se ter um alto nível de serviço e para atender as necessidades dos
clientes, a empresa necessita de locais de produção próximos aos clientes e deve estar apta a
lidar com curtos prazos de entrega. Há, portanto, um clássico trade-off na cadeia de
abastecimento entre o custo logístico e o nível de serviço oferecido.
As fabricas Glassolutions realizam suas entregas a partir de rotas como exemplificado
na Figura 15. As rotas são realizadas em dias fixos da semana e são estabelecidas a partir do
comportamento históricos da demanda. Assim, cada caminhão de uma fábrica possui rotas pré-
estabelecidas para cada dia da semana, com uma lista de clientes regulares que são servidos por
cada rota. Novos clientes ou clientes não regulares são servidos com a rota mais adequada que
possua capacidade livre. Em uma rota típica, o caminhão deixa a fábrica, visita diversos clientes
para entrega e recolhimento de cavaletes e retorna à fábrica ao final do dia.
34
Figura 15 : Exemplo de uma rota de entrega realizada por um caminhão Glassolutions. A estrela azul representa
a fábrica e os pontos pretos seguidos do número da parada, os clientes visitados.
Fonte: elaborado pelo autor com software Geoconcept.
Entretanto, na maioria das fábricas, as rotas dos caminhões foram criadas há muitos anos
e de maneira manual, isto é, com a utilização de mapas impressos e sem a utilização de
ferramentas de otimização. Assim, em muitos casos, a lista de clientes atendidos por uma rota
já não corresponde à realidade de hoje. Ao longo do tempo, pode haver várias alterações em
relação aos clientes. Alguns desapareceram ou viram seus negócios apresentar um acentuado
declínio, enquanto outros cresceram muito mais rápido do que o esperado. As rotas atuais
também não levam em consideração o desenvolvimento da rede Glassolutions dos últimos anos,
com a aquisição de negócios, a criação de novas linhas de produção, mudanças nos papéis e
fechamento das fábricas.
Alguns locais de produção possuem boas equipes logísticas que realizam constantes
adaptações nas rotas de entregas, mas, dado a complexidade e o grande número de variáveis
envolvidas, estas adaptações não necessariamente levam ao ótimo do sistema. Além disso,
muitas vezes as fábricas não possuem incentivos para realizar um trabalho regional de análise
ao estabelecerem suas rotas de entregas. Assim, potenciais sinergias com fábricas vizinhas são
perdidas. Pode-se considerar, por exemplo, o compartilhamento de caminhões entre fábricas ou
a revisão da alocação de clientes com mudanças nas áreas atendidas por cada fábrica.
Perante esta complexidade logística, as significativas restrições de entrega aos clientes,
o elevado número de fábricas e, portanto, o alto custo logístico, Glassolutions procura otimizar
sua distribuição e avaliar, a nível estratégico, a existência de certos recursos logísticos
(caminhões e instalações). Existe, portanto, uma necessidade de buscar ferramentas de
otimização adaptadas à empresa afim de modelar a rede de distribuição da empresa, permitindo
identificar rotas típicas de entrega otimizadas e, consequentemente, identificar os recursos
35
logísticos necessários para atender a demanda com o nível de serviço prometido pela empresa.
Busca-se também o estabelecimento de uma metodologia que permita replicar o modelo
matemático desenvolvido em qualquer fábrica do grupo, principalmente para o segmento
regional em que os clientes são pequenos e numerosos havendo alta complexidade na
identificação de rotas de entrega.
Além dos ganhos financeiros a empresa pode também fornecer um melhor serviço aos seus
clientes, principalmente através do aumento do número de pedidos entregues nos prazos
prometidos e pelo aumento da frequência de visitas à determinados clientes. O respeito aos
prazos de entrega é valorizado pelos clientes e já é medido dentro da empresa através do OTIF
(On Time In Full), indicador que mede a fração dos pedidos entregues conformes, isto é, sem
atrasos (SEHGAL; SAHAY; GOYAL, 2006).
Os objetivos da empresa ao buscar a otimização das rotas de entrega são, portanto, aumentar
o nível de serviço oferecido aos seus clientes e buscar a redução dos custos logísticos. Em geral,
acredita-se que estes dois objetivos são antagônicos. O que é verdade para alguns casos em que
a situação já está otimizada com o emprego de modelo de negócio ideal. Nestes casos, o
aumento do serviço oferecido aos clientes, provavelmente, implicará um aumento nos custos
logísticos como exemplificado na Figura 16.
Entretanto, em casos complexos e desatualizados como o tratado na empresa pode-se
conseguir melhorar o serviço oferecido aos clientes e ao mesmo tempo reduzir os custos
logísticos ao se reavaliar frequências de entrega e os meios de entrega.
Figura 16: Clássico trade-off entre o nível de serviço oferecido e os custos logísticos.
Fonte: adaptado de (FENDER; BARON, 2012).
Uma vez que a empresa busca maneiras de reduzir seus custos de operação afim de melhorar
sua posição no mercado é importante identificar dentro da vasta operação Europeia do grupo,
36
regiões que possam render bons retornos com projetos de otimização. A operação nos países
escandinavos sempre apresentou custo elevado em comparação aos outros países de operação
do grupo. Nestes casos, os custos elevados e a alta intensidade da competição elevam os riscos
financeiros de operação. Esses países tornam-se, portanto, um importante alvo para os projetos
de otimização e de redução de custos da empresa, buscando tornar sustentável a sua operação
no país.
Analisando os custos de transporte da empresa nos diferentes países, nota-se que os custos
de transporte por 𝑚2 de produto na Noruega é mais de duas vezes à média observada na Europa.
Este alto custo de transporte pode ser explicado, entre outros motivos, pelo ao alto custo da mão
de obra no país.
Segundo o instituto estatístico norueguês (STATISTISK SENTRALBYRA, 2015a), o
salário médio mensal da indústria norueguesa em 2015 foi de 43 300 coroas norueguesas, ou
4670 euros. Para exemplo de comparação, em 2016, na Polônia, o salário médio da indústria
foi de 3949,40 zloty (moeda polonesa), ou 911 euros (POLAND CENTRAL STATISTICAL
OFFICE, 2016).
Na Noruega existe apenas um ponto de distribuição o que permite à empresa se indagar
sobre possíveis melhorias com a utilização de novos pontos de distribuição e com a atualização
e otimização das rotas de entrega empregadas no país. Por estes motivos, decidiu-se delimitar
o escopo do problema às operações norueguesas da empresa.
2.2. Descrição do problema
Devido aos altos custos de operação na Noruega, o grupo concentrou suas operações em
dois pontos no sul do país: em Fredrikstad, que funciona como escritório comercial e centro de
distribuição, e Oslo, que funciona apenas como escritório comercial como indicado na Figura
17. Trata-se de dois grandes centros urbanos, próximos à grandes concentrações de clientes da
empresa e próximo à rede de infraestrutura que conecta ao restante do país e aos países vizinhos
(estradas e portos).
37
Figura 17: Localização dos centros de distribuição de Glassolutions na Noruega.
Fonte: elaborado pelo autor com auxílio do software Google Maps.
Ainda devido aos altos custos de produção e à menor demanda quando comparado aos
demais países europeus, o grupo decidiu por realizar a importação de todos os produtos
vendidos no país. Assim, resta à equipe norueguesa as atividades de venda comercial, algumas
operações de corte de vidro simples, distribuição e serviços de relacionamento com o cliente.
As fábricas de países vizinhos que produzem para a Noruega são identificadas pelo nome
da cidade em que estão localizadas e podem ser vistas na Figura 18, sendo que o maior provedor
de produtos para a Noruega seria a instalação polonesa. São elas:
Tartu na Estônia;
Barczewo na Polônia;
Berlim na Alemanha;
Aalborg na Dinamarca;
Emmaboda na Suécia;
38
Figura 18: Importação de produtos de países vizinhos.
Fonte: elaborado pelo autor com auxílio do software Google Maps.
Devido ao alto custo de mão de obra no país e aos demais custos operacionais, o grupo
optou por terceirizar as operações de transporte. Neste caso, cabe à empresa preparar os
produtos para expedição, carregar os caminhões e informar à transportadora a lista de clientes
à serem entregues. A partir de então, é função da transportadora realizar a entrega do produto
ao cliente. A transportadora cobra a empresa por km rodado de cada caminhão colocado à
disposição e por hora de trabalho do motorista.
É do interesse de Glassolutions, portanto, otimizar as rotas de entrega de seus produtos,
encontrando a combinação de clientes e roteiros que minimizem o custo de distribuição. A
empresa deve criar, a partir do comportamento histórico da demanda, dias pré-definidos para
realização de certos roteiros de entrega e, assim, distribuir os pedidos de seus clientes ao longo
da semana e nos seus respectivos roteiros e dias de entrega.
Além da simples otimização dos roteiros de entrega, a empresa também se mostra disposta
a rever seu modelo de distribuição na Noruega. A opção considerada pela empresa seria de, ao
39
invés de concentrar toda a recepção de produtos importados na fábrica de Fredrikstad e depois
redistribuí-los pelo país, utilizar certos centros de distribuição da transportadora parceira como
ponto de recepção de alguns produtos importados.
Esta possível otimização do modelo de distribuição está esquematizada na Figura 19. O fato
que tornaria esta opção mais vantajosa é o de que o custo de transporte dos diversos países
fornecedores é inferior ao custo de transporte interno da Noruega. Deste modo, pode ser mais
vantajoso usufruir por um maior tempo da transportadora estrangeira, solicitando a entrega do
produto à um centro de distribuição mais próximo aos clientes finais, que entregar em
Fredrikstad, ponto no extremo sul do país, mais próximo dos fornecedores, porém mais longe
dos clientes de outras regiões da Noruega.
Figura 19: Possibilidade de otimização da distribuição na Noruega com a utilização de centros de distribuição
(CD) da transportadora parceira.
Fonte: elaborado pelo autor
Assim, neste novo modelo de distribuição, procura-se entender quais centros de distribuição
utilizar, quantos roteiros de entrega deveriam existir e qual seria a composição destes roteiros
de entrega. Na construção do modelo deve-se, portanto, considerar todas as variáveis existentes
neste novo cenário tal como o aumento do custo de transporte ao enviar produtos à um centro
de distribuição mais distante.
40
Os potenciais pontos para servirem como centros de distribuição são pontos já existentes da
transportadora, próximo a grandes concentrações de clientes da empresa. Segundo
levantamento da empresa, os pontos compatíveis com a estratégia do grupo são:
Hamar;
Trondheim;
Bergen;
Sandnes;
Estes pontos candidatos são indicados na Figura 20 junto com as instalações atuais da empresa.
Figura 20: Instalações da empresa (Oslo e Fredrikstad) e centros de distribuição estudados (amarelo).
Fonte: elaborado pelo autor com auxílio do software Google Maps.
As localizações estudadas são regiões de grande concentração de clientes.
Consequentemente, também são grandes centros urbanos da Noruega e estão entre as zonas de
maior concentração de população da Noruega como indicado pela Tabela 4. A exceção seria
Hamar que, entretanto, possui uma localização estratégica por estar próximo à uma bifurcação
dos eixos rodoviários do país e também estar próximo aos clientes do grupo. Se estes centros
de distribuição atendessem apenas as populações desses centros urbanos, já estariam atendendo
41
por volta de 31% da população da Noruega, sem contar ainda a proximidade com outras cidades
no entorno.
Tabela 4: Maiores centros urbanos da Noruega e suas populações (STATISTISK SENTRALBYRA, 2015b)
Maiores centros
urbanos da Noruega População
Oslo 958 378
Bergen 250 420
Stavanger/Sandnes 210 874
Trondheim 175 068
Drammen 113 534
43
3. REVISÃO BIBLIOGRÁFICA
Neste capítulo procura-se apresentar uma revisão da literatura acerca dos problemas de
localização, de roteirização de veículos e do problema misto de localização e roteirização.
Procura-se compreender a visão dos principais autores, ilustrando taxonomia, definições e
constatações bem estabelecidas na indústria.
Além de apresentar os diferentes tipos de problemas de roteirização e localização, o capítulo
apresenta os principais métodos de resolução para estes problemas. Constrói-se, assim, um
panorama do estado atual da literatura científica que servirá de base, posteriormente, para a
formulação matemática do problema e sua resolução.
3.1. Problemas de localização e roteirização de veículos
Temos no caso estudado a combinação de dois problemas clássicos da literatura de pesquisa
operacional, o problema de roteirização de veículos e de localização de centros de distribuição.
Segundo Ghiani; Laporte e Musmanno (2004), os problemas de roteirização e de localização
são duas das decisões mais fundamentais em logística. Segundo os autores, no nível estratégico
a decisão principal a ser tomada é quanto à localização dos centros de distribuição. Já a nível
tático, o ponto principal a ser levantado é quanto ao dimensionamento da frota, enquanto que
no escopo operacional preocupa-se mais com a roteirização. Entretanto, os autores afirmam que
ao se planejar a localização de uma instalação produtiva ou de distribuição, é preferível integrar
também a análise dos custos das rotas de distribuição a fim de evitar ineficiências no sistema.
De acordo com Belfiore e Fávero (2006), os problemas de roteirização têm recebido atenção
nos últimos anos em função de sua aplicabilidade e importância econômica para as empresas.
No problema clássico de roteirização de veículos (VRP – Vehicle Routing Problem) o objetivo
é encontrar o conjunto de rotas que resulte no menor custo possível, podendo ser interpretado,
por exemplo, como a minimização do custo monetário efetivo, da distância total percorrida,
número de veículos utilizados, tempo de atendimento, tempo de espera entre outros. Existe
ainda uma grande variedade de problemas de roteirização dentre os quais podemos citar alguns
exemplos clássicos como:
Problema de roteirização de veículos com entregas fracionadas (Vehicle Routing
Problem with Split Deliveries – VRPSD) em que cada cliente pode ser atendido por
mais de um veículo e, assim, a demanda total do cliente pode ser maior que a
capacidade do veículo (DROR; TRUDEAU, 1990);
44
Problema de roteirização de veículos com janelas de tempo e entregas fracionadas
(Vehicle Routing Problem with Time Windows and Split Deliveries - VRPTWSD) é
derivado do VRPSD com a restrição adicional de que existe uma janela de tempo
que deve ser respeitada à cada entrega (FRIZZELL; GIFFIN, 1995);
Problema de roteirização de veículos com demanda em arcos, janelas de tempo e
entregas fracionadas (Capacitated Arc Routing Problem with Time Windows and
Split Deliveries – CARPTWSD) em que se tem uma variante do VRPSD com a
restrição adicional de que existe uma janela de tempo que deve ser respeitada à cada
entrega com demanda nos arcos ao invés de nos nós (GOLDEN; RAGHAVAN;
WASIL, 2008);
Diversas outras variações ainda podem ser construídas segundo os contextos e
necessidades encontradas na indústria como, por exemplo, variações com frotas heterogêneas
(BELFIORE; YOSHIZAKI, 2013).
O outro problema tratado neste trabalho é o de localização de centros de distribuição. Trata-
se também de um problema clássico de pesquisa operacional com ampla aplicação na indústria.
As decisões sobre o sistema de distribuição das empresas são de grande importância e passam
por uma tomada de decisão referente à localização do ponto de produção, de distribuição e dos
clientes (MELO; NICKEL; SALDANHA-DA-GAMA, 2009) (OWEN; DASKIN, 1998). Esta
importância não se limita a corporações privadas que buscam otimizar seus processos. No setor
público também é de extrema importância permitindo melhorar os serviços prestados e otimizar
os recursos dos contribuintes. Pode-se citar como exemplos de aplicação na esfera pública, a
localização de hospitais, escolas, bombeiros, polícia, entre outros, de maneira a satisfazer uma
série de critérios e otimizar os recursos investidos (KLOSE; DREXL, 2005).
De acordo com ReVelle e Eiselt (2005) existem 4 componentes que caracterizam o
problema de localização:
I. Os clientes, que presumidamente já estão localizados em seus pontos ou rotas;
II. As instalações que deverão ser localizadas;
III. O espaço em que os clientes e as instalações estão localizadas;
IV. Uma medida de distância ou tempo entre os clientes e as instalações.
Os autores ressaltam que, diferentemente dos problemas de roteirização que possuem
escopos e objetivos bem delimitados, problemas de localização são suscetíveis frequentemente
a múltiplos objetivos e com inúmeras variáveis diferentes, o que dificulta sua modelagem.
45
Para Ghiani; Laporte e Musmanno (2005), decisões referentes à localização das instalações
são necessárias quando se está desenhando um novo sistema logístico, quando existe variação
no padrão da demanda ou na distribuição espacial dos agentes envolvidos e quando existe
variação nos custos. Os autores ressaltam também que este tipo de decisão deve ocorrer à nível
estratégico, quando envolverem altos custos fixos, ou à nível tático, quando os custos fixos
envolvidos forem menores com, por exemplo, espaço e equipamentos alugados.
Segundo Daskin (1995), a combinação de problemas de localização com problemas de
roteirização é de grande complexidade pois o número de variáveis envolvidas é superior a
qualquer dos problemas separados. Segundo o autor existem 5 decisões envolvidas nesse
problema:
I. Quantas instalações devo abrir;
II. Onde localizar tais instalações;
III. Quais clientes devo atribuir à quais instalações;
IV. Quais clientes devo atribuir à quais rotas;
V. Em qual ordem os clientes devem ser atendidos dentro de uma mesma rota.
O autor ressalta a dificuldade do problema notando que somente a última etapa, a de
sequenciar os clientes, é análogo ao problema do caixeiro viajante, que é NP-hard. O problema
do caixeiro viajante é um problema clássico da pesquisa operacional em que um caixeiro deve,
a partir de uma cidade inicial ou depósito, visitar um conjunto de cidades uma única vez e
retornar ao seu ponto inicial de modo a otimizar um ou mais objetivos (ARENALES et al.,
2007). De acordo com Daskin (1995), neste problema quer-se, encontrar o ciclo hamiltoniano
que otimize a função objetivo do problema sendo, consequentemente, NP-hard.
Ainda segundo Daskin (1995) um problema pode ser classificado como de classe P se puder
ser resolvido em tempo polinomial. Um problema é de classe NP (non deterministic
polynomial), se uma solução candidata puder ser verificada como solução efetiva em tempo
polinomial. Um algoritmo é dito ser de tempo polinomial se sua ordem de grandeza, f(n), for
uma função polinomial de n. O conceito de NP-completo refere-se a problemas de decisão tais
que se existir um algoritmo de complexidade polinomial para a sua resolução, então todos os
problemas de NP poderão ser resolvidos por algoritmos de complexidade polinomial. As
versões análogas dos problemas de decisão para otimização serão classificadas como NP-hard
(NP-árduo em português). Deste modo, problemas de otimização considerados NP-hard são de
46
difícil resolução com o tempo computacional de resolução podendo aumentar
exponencialmente em função do número de variáveis do problema. Em levantamento realizado
por Lenstra e Kan (1981), concluiu-se que a grande maioria dos problemas de roteirização são
NP-hard.
Min; Jayaraman e Srivastava (1998) desenvolveram uma classificação e taxonomia para os
problemas mistos de localização e roteirização. Segundo os autores estes problemas podem ser
classificados segundo suas perspectivas:
i. Nível Hierárquico
a. Um nível (apenas distribuição a partir das instalações)
b. Dois níveis (considera distribuição e coleta a partir das instalações)
ii. Natureza da oferta/demanda
a. Determinística
b. Estocástica
iii. Número de instalações que se quer localizar
a. Uma instalação
b. Múltiplas instalações
iv. Tamanho das frotas de veículos
a. Veículo único
b. Múltiplos veículos
v. Capacidade dos veículos
a. Sem restrição de capacidade
b. Com restrição de capacidade
vi. Capacidade dos centros de distribuição
a. Sem restrição de capacidade
b. Com restrição de capacidade
vii. Camada dos centros de distribuição
a. Primária (veículos partem dos centros de distribuição para os clientes finais)
b. Secundária/intermediária (requer paradas intermediárias como depósitos antes
de prosseguir para os clientes finais)
viii. Horizonte de planejamento
a. Período único (estático)
b. Múltiplos períodos (dinâmico)
ix. Janela de tempo
47
a. Não especificada e sem prazos
b. Janela de tempo folgada e com prazos flexíveis
c. Janela de tempo restrita e com prazos rígidos
x. Função Objetivo
a. Único objetivo
b. Múltiplos objetivos
xi. Tipo de dados do modelo
a. Hipotético
b. Real
No caso do problema tratado neste trabalho poderíamos classifica-lo segundo estes
critérios, como apresentado na Tabela 5.
Tabela 5: Classificação do problema retratado neste trabalho segundo os critérios de (MIN; JAYARAMAN;
SRIVASTAVA, 1998).
Critério Classificação
i. Nível Hierárquico Etapa única
ii. Natureza da oferta/demanda Determinística
iii. Número de centros de distribuição
que se quer localizar
Múltiplos centros de distribuição
iv. Tamanho das frotas de veículos Múltiplos veículos
v. Capacidade dos veículos Com restrição de capacidade
vi. Capacidade dos centros de
distribuição
Sem restrição de capacidade
vii. Camada dos centros de
distribuição
Primária
viii. Horizonte de planejamento Período único (estático)
ix. Janela de tempo Janela de tempo restrita e com prazos
rígidos
x. Função Objetivo Único objetivo
xi. Tipo de dados do modelo Real
3.2. Métodos de Resolução
Nagy e Salhi (2007) sintetizam os métodos de resolução em 2 categorias:
Métodos Exatos;
Métodos heurísticos
Os métodos exatos garantem a solução ótima do problema. Entretanto, como a maior parte
dos problemas que envolvem roteirização pertencem à classe NP-hard, estes algoritmos
funcionam apenas para problemas de pequena ordem de grandeza ou com características
48
específicas, não correspondendo à realidade enfrentada pela indústria em geral e pelo problema
aqui descrito.
Os métodos heurísticos são métodos que, com base de experiência ou julgamento, são
prováveis de fornecerem soluções razoáveis ao problema investigado sem que se possa garantir
se tratar de um ótimo matemático. São assim métodos rápidos e robustos de se implementar,
propondo uma boa solução para um problema que pode não ser solucionável com os recursos
computacionais normalmente disponíveis ao se utilizar outros métodos (SILVER, 2004).
Zanakis; Evans e Vazacopoulos (1989) classificaram as heurísticas em 10 grupos:
Construtivas;
Melhoria;
Programação matemática;
Decomposição;
Particionamento;
Restrição do espaço de solução;
Relaxamento;
Sondagem, comparação e avaliação;
Avaliação da performance e complexidade;
Análise probabilística e inferência.
Min; Jayaraman e Srivastava (1998) afirmam também ser possível classificar os métodos
de resolução dos problemas mistos de localização e roteirização:
i. Algoritmo exato
a. Branch and bound / árvore de busca;
b. Programação dinâmica;
c. Programação inteira;
d. Programação não linear.
ii. Heurísticos
a. Location-allocation first, route-second;
b. Route-first, location-allocation-second;
c. Economias/inserção;
d. Melhoria/trocas.
49
4. MODELAGEM DO PROBLEMA
Neste capítulo desenvolve-se a formulação matemática do problema. Inicia-se com uma
breve e objetiva descrição do problema estabelecendo alguns dados de entrada para a
construção das restrições do problema. Explica-se também o funcionamento das janelas de
tempo dentro do problema.
Finalmente, apresenta-se a formulação matemática do problema que servirá como base
para sua resolução. Realiza-se também uma detalhada descrição das restrições do problema
explicando o comportamento e objetivo das restrições.
4.1. Considerações sobre o problema
A partir de um conjunto limitado de centros de distribuição estabelecidos a partir de um
conjunto K de depósitos candidatos, são atendidos N clientes por semana. No modelo
estabelecido, todos os clientes possuem frequência unitária. Deste modo, um cliente que possui
inicialmente frequência maior que 1 é repartido em múltiplos clientes com frequência igual a 1
e em janelas de tempo segregada.
Deste modo, clientes que possuam frequência múltipla de visita (2, 3, 4 ou 5 vezes por
semana) são multiplicados utilizando-se janelas de tempo [𝑎𝑖, 𝑏𝑖] que especificam os intervalos
de dias da semana nas quais podem receber visita. Assim, inibe-se que um mesmo cliente receba
todas as suas entregas semanais em um mesmo dia e possibilita-se a melhor divisão das entregas
ao longo da semana.
Por exemplo, supondo que um cliente tenha uma frequência de 2 visitas por semana e
uma demanda média por visita igual a 𝑑𝑖. Este cliente será transformado em 2 clientes com
frequência de 1 entrega por semana e demanda média por entrega de 𝑑𝑖, mas com janelas de
entrega diferentes. Um dos clientes resultantes deverá ser visitado na segunda-feira ou terça-
feira enquanto que o outro terá que ser visitado na quinta-feira ou sexta-feira. Desta maneira,
garantimos o espaçamento das entregas com respeito ao nível de serviço esperado pelo cliente.
A Tabela 6 estabelece a relação entra a frequência de entrega semanal de um cliente e
as janelas de tempo das respectivas divisões desses clientes. Já a Figura 21 representa a
repartição de um cliente em janelas de tempo.
50
Tabela 6: Janela de entrega para as respectivas frequências de entrega (1: segunda-feira e 5: sexta-feira)
Frequência Janela de entrega
1 1 - 5
2 1-2 e 4-5
3 1-2, 3, 4-5
4 1-2, 3, 4 e 5
5 1, 2, 3, 4 e 5
Figura 21: Ilustração da repartição dos clientes em janelas de tempo.
Fonte: elaborado pelo autor
De cada centro de distribuição parte um número de roteiros de entrega, sendo que cada
roteiro também passa por um número clientes, sem repetições. Para cada visita, é entregue uma
quantidade 𝑑𝑖 (demanda média por entrega do cliente i) com um tempo de atendimento 𝑠𝑖. A
frota de veículos é homogênea e com capacidade C medida em função da quantidade de 𝑚2
que podem transportar. A capacidade em termos de 𝑚2 de produto a transportar é superior à
maior demanda de um cliente. Busca-se encontrar a menor frota que atenda as demandas dos
clientes com o menor custo bem como os centros de distribuição que servirão como local de
partida destes roteiros.
51
Temos, portanto, um problema de programação linear inteira mista (PLIM) de roteirização
de veículos com janelas de tempo e com a possibilidade de existência de diversos centros de
distribuição (Location Vehicle Routing Problem with Time Windows and Multiple Deposits –
LVRPTWMD).
Como estamos tratando com prestadores externos de transporte, frota homogênea e
possibilidades ilimitadas de roteiros, neste problema um veículo será sinônimo de roteiro.
Busca-se concentrar a análise no número de roteiros necessários, quais clientes incluir em qual
roteiro e a partir de quais centros de distribuição devem partir os roteiros.
Neste problema os custos de deslocamento entre os nós (centros de distribuição e clientes)
são proporcionais ao tempo de trajeto e à distância percorrida conforme estabelecido no
contrato entre a empresa e a transportadora.
Para utilização de um centro de distribuição candidato deve-se incorrer um custo de
utilização que considera o custo de transporte dos produtos dos fornecedores ao depósito
considerado e os custos para uso do depósito como, por exemplo, aluguel ou custo fixo de
construção do depósito.
É importante ressaltar que no caso norueguês, analisado neste trabalho, utiliza-se caminhões
de grandes dimensões e com grande capacidade de transporte em termos de peso. Deste modo,
não se considera o peso transportado como uma restrição do problema, diferentemente de casos
em que se utiliza caminhões de menor capacidade de transporte de carga e em que o peso dos
produtos é um fator a ser considerado.
4.2. Formulação Matemática
São apresentados, a seguir, as principais características do modelo, destacando-se as
principais restrições, hipóteses consideradas, associações, conjuntos e variáveis.
Principais restrições:
Atender a demanda dos clientes;
Respeitar janelas de tempo;
Capacidade dos caminhões;
Os veículos partem do centro de distribuição, mas não precisam retornar (custo é
calculado até a entrega do último cliente)
Principais hipóteses:
52
A demanda é determinística e trabalha-se com uma demanda média por entrega e por
cliente a partir de dados históricos;
Horizonte de planejamento de uma semana;
Frota de veículos homogênea;
Não é permitido entregas fracionadas (quando o cliente recebe mercadorias de
diferentes caminhões em um mesmo dia);
Não são permitidos “re-carregamentos” dos caminhões. Uma vez que o caminhão deixa
o Centro de Distribuição ele não deve mais retornar;
Possibilidade de existência de 5 pontos de distribuição com localização determinadas e
sem restrições quanto à oferta de produtos.
Associações:
Para cada cliente i estão associados:
Uma demanda 𝑑𝑖;
Um tempo de atendimento 𝑠𝑖;
Uma janela de tempo [𝑎𝑖 , 𝑏𝑖];
Um roteiro pode ser formado por um único cliente ou vários clientes, as quais estão
associados:
Deslocamento do nó i = 0 (depósito) até o nó j (primeiro cliente);
Deslocamentos entre clientes (do nó i, i= 1, ..., n até o nó j, j=1, ..., n);
Conjuntos:
N: Conjunto de clientes a serem atendidos;
W: Conjunto de centros de distribuição candidatos;
𝑘𝑤: Conjunto de veículos associados ao centro de distribuição candidato w;
K: Conjunto de todos os veículos disponíveis (𝑘1 a 𝑘𝑤).
Parâmetros:
Q: número suficientemente grande tal que Q≤𝑛2;
𝑐𝑖𝑗: custo de locomoção do cliente i ao cliente j;
𝐶𝑈𝑖: custo de utilização para existência do centro de distribuição i;
𝑑𝑖: demanda média de uma entrega ao cliente i;
53
𝑠𝑖: tempo de atendimento do cliente i considerando o tempo de descarga e entrega do
produto e a realização dos procedimentos administrativos de entrega (verificação do
pedido e recolhimento de assinatura);
C: capacidade do caminhão (roteiro) v;
𝑡𝑖𝑗: tempo em horas entre o nó i e o nó j;
M: número suficientemente grande tal que 𝑀 ≥ 𝑚;
𝑐𝑖𝑗: custo de ir do cliente i ao cliente j, sendo proporcional à distância percorrida e à
duração deste trajeto segundo o contrato da empresa com a transportadora;
P: número suficiente grande.
Variáveis de decisão:
𝑥𝑖𝑗𝑣 : 1, se j é atendido após i pelo veículo v;
0, caso contrário.
𝑦𝑖𝑣 : 1, se o cliente i é atendido pelo veículo (roteiro) v;
0, caso contrário.
𝑉𝑣 : 1, se o roteiro v existe;
0, caso contrário.
𝑧𝑖 : 1, se centro de distribuição i existe;
0, caso contrário.
𝑇𝑖: tempo de início de atendimento do cliente i.
min ∑ ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗𝑣
𝑣∈𝐾𝑗∈𝑁𝑖∈𝑁
+ ∑ 𝑧𝑖𝐶𝑈𝑖
𝑖∈𝑊
(1)
S.a.
𝑄𝑉𝑣 ≥ ∑ ∑ 𝑥𝑖𝑗𝑣
𝑗𝜖𝑁𝑖𝜖𝑁
, ∀ 𝑣 𝜖 𝐾 (2)
∑ 𝑥0𝑗𝑣
𝑗𝜖𝑁
− 𝑉𝑣 = 0, ∀ 𝑣 𝜖 𝐾 (3)
∑ 𝑥𝑖𝑝𝑣
𝑖𝜖𝑁
− ∑ 𝑥𝑝𝑗𝑣
𝑗𝜖𝑁
= 0, ∀ 𝑝 𝜖 𝑁, ∀ 𝑣 𝜖 𝐾 (4)
54
𝑦𝑖𝑣 = ∑ 𝑥𝑗𝑖
𝑣
𝑗𝜖𝑁
, ∀ 𝑖 𝜖 𝑁, ∀ 𝑣 𝜖 𝐾 (5)
𝑇𝑖 + 𝑠𝑖 + 𝑡𝑖𝑗 − 𝑃 (1 − ∑ 𝑥𝑖𝑗𝑣
𝑣𝜖𝐾
) ≤ 𝑇𝑗, ∀ 𝑖 𝜖 𝑁, ∀ 𝑗 𝜖 𝑁 (6)
𝑎𝑖 ≤ 𝑇𝑖 ≤ 𝑏𝑖, ∀ 𝑖 𝜖 𝑁 (7)
∑ ∑ 𝑥𝑖𝑗𝑣
𝑖𝜖𝑁𝑣𝜖𝐾
= 1, ∀ 𝑗 𝜖 𝑁 (8)
∑ 𝑑𝑖𝑦𝑖𝑣
𝑖𝜖𝑁
≤ 𝐶, ∀ 𝑣 𝜖 𝐾 (9)
𝑀 ∗ 𝑧𝑤 ≥ ∑ 𝑉𝑣
𝑣𝜖𝑘𝑤
, ∀ 𝑤 𝜖 𝑊 (10)
𝑥𝑖𝑗𝑣 ∈ {0,1}, ∀ 𝑖, 𝑗, 𝑣 (11)
𝑦𝑖𝑣 ∈ {0,1}, ∀ 𝑖, 𝑣 (12)
𝑉𝑣 ∈ {0,1}, ∀ 𝑣 (13)
𝑧𝑖 ∈ {0,1}, ∀ 𝑖 (14)
4.3. Detalhamento do Modelo
Função Objetivo (1): min ∑ ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗𝑣
𝑣∈𝐾𝑗∈𝑁𝑖∈𝑁 + ∑ 𝑧𝑖𝐶𝑈𝑖𝑖∈𝑊
A função objetivo busca minimizar os custos de transporte das rotas e o custo de utilização
dos centros de distribuição abertos. Cada arco ij do problema representa o deslocamento de um
cliente i para o cliente j com um custo imputável à empresa. Conforme o contrato estabelecido
entre a empresa e a transportadora, o custo de transporte é calculado em função da distância
percorrida e do tempo de trajeto. Assume-se, também que a matriz de custo seja simétrica, isto
é, 𝑐𝑖𝑗 = 𝑐𝑗𝑖.
Além disso, existe um custo de utilização dos centros de distribuição representado pelo
valor adicional de frete fixo cobrado pelos fornecedores até o depósito e por uma compensação
pelo uso do local.
Restrição (2): 𝑄𝑉𝑣 ≥ ∑ ∑ 𝑥𝑖𝑗𝑣
𝑗𝜖𝑁𝑖𝜖𝑁 , ∀ 𝑣 𝜖 𝐾
Esta restrição estabelece se o roteiro 𝑉𝑣 existe ou não (1 ou 0). Segundo esta restrição, se
existir algum arco 𝑥𝑖𝑗 relacionado ao veículo v, com valor 1, então a variável 𝑉𝑣 que indica a
existência do veículo v também será 1. Caso contrário, dado que a existência de um roteiro
55
implica na utilização de um centro de distribuição e, consequentemente, em um custo, na
resolução do modelo o valor dessa variável tenderá a zero.
Restrição (3): ∑ 𝑥0𝑗𝑣
𝑗𝜖𝑁 − 𝑉𝑣 = 0, ∀ 𝑣 𝜖 𝐾
Estabelece que se um roteiro existe, ele deve partir do centro de distribuição. Como no caso
real, os veículos devem ser carregados com os produtos no centro de distribuição e em seguida
realizarem as entregas aos clientes. Evita, portanto, que ocorra a situação exemplificada na
Figura 22, em que o veículo 2 inicia o roteiro pelo cliente C4.
Figura 22: Veículo 2 realiza entregas sem ter iniciado pelo centro de distribuição (CD).
Fonte: elaborado pelo autor
Restrição (4): ∑ 𝑥𝑖𝑝𝑣
𝑖𝜖𝑁 − ∑ 𝑥𝑝𝑗𝑣
𝑗𝜖𝑁 = 0, ∀ 𝑝 𝜖 𝑁, ∀ 𝑣 𝜖 𝐾
Garante a conservação dos fluxos de entrada e saída dos nós (clientes). Se um veículo atende
um cliente, isto é, o arco de entrada possui valor positivo (𝑥𝑖𝑝𝑣 ), então o veículo deve continuar
sua viagem rumo a outro cliente, isto é, deve existir algum j para o qual 𝑥𝑝𝑗𝑣 é positivo, conforme
exemplificado pela Figura 23.
Figura 23: Conservação dos fluxos de entrada e saída
Fonte: elaborado pelo autor
56
Restrição (5): 𝑦𝑖𝑣 = ∑ 𝑥𝑗𝑖
𝑣𝑗𝜖𝑁 , ∀ 𝑣 𝜖 𝐾, ∀ 𝑖 𝜖 𝑁
Esta restrição estabelece qual roteiro servirá cada cliente. Se existe um valor positivo
do arco de entrada de um cliente 𝑥𝑗𝑖𝑣 proveniente de qualquer nó j, a variável 𝑦𝑖
𝑣 que relaciona
o veículo v ao cliente i também será positiva. Importante notar que no modelo cada cliente é
servido uma única vez, isto é, existe um único arco de entrada positivo para cada cliente.
Restrição (6): 𝑇𝑖 + 𝑠𝑖 + 𝑡𝑖𝑗 − 𝑃(1 − ∑ 𝑥𝑖𝑗𝑣
𝑣𝜖𝐾 ) ≤ 𝑇𝑗 , ∀ 𝑖 𝜖 𝑁, ∀ 𝑗 𝜖 𝑁
Impõe o horário mínimo de atendimento de um cliente que é dado pela soma do horário
de atendimento do cliente anterior, do tempo de atendimento do cliente anterior e pelo tempo
de percurso entre os dois clientes. A expressão 𝑃(1 − ∑ 𝑥𝑖𝑗𝑣
𝑣𝜖𝐾 ) permite avaliar se para
qualquer veículo v, exista alguma ligação entre o cliente i e j. Caso não haja, ∑ 𝑥𝑖𝑗𝑣
𝑣𝜖𝐾 = 0 e o
valor da variável 𝑇𝑗 segue livre. Caso exista algum 𝑥𝑖𝑗𝑣 positivo para qualquer v, então o valor
de 𝑇𝑗 deverá respeitar a restrição de tempo, sendo no mínimo superior à 𝑇𝑖 + 𝑠𝑖 + 𝑡𝑖𝑗.
Segundo Belfiore (2006), esta restrição também garante a eliminação de subtours. Na
Figura 24 pode-se observar exemplos de subtours que seriam evitados. O cliente 4, por
exemplo, possui um ciclo interno a si próprio. Já os clientes 5 e 6 constituíram um ciclo próprio
sem conexão com o restante do roteiro. Em ambos os casos temos o respeito às demais
condições do problema uma vez que o início do roteiro se dá pelo centro de distribuição
(restrição 3) e há conservação dos fluxos de entrada e saída dos nós (restrição 4). Com a
restrição de tempo imposta por esta restrição, o tempo de início de atendimento teria que ser
ligado ao cliente predecessor sendo majorado pelo tempo de atendimento no cliente predecessor
e de deslocamento entre os nós.
Neste exemplo, o nó predecessor ao nó 4 é ele próprio. A restrição 6 levaria, portanto,
a uma situação não factível:
𝑇4 + 𝑠4 + 𝑡44 ≤ 𝑇4
Com 𝑠4 > 0 e 𝑡44 = 0 teríamos, portanto, uma inconsiténcia com 𝑇4 + 𝑠4 ≤ 𝑇4 e o
modelo não permitira a existência desta configuração.
Para o exemplo do ciclo interno entre os nós 5 e 6 teríamos:
𝑇5 + 𝑠5 + 𝑡56 ≤ 𝑇6
𝑇6 + 𝑠6 + 𝑡65 ≤ 𝑇5
57
A primeira equação permite concluir que 𝑇6 ≥ 𝑇5 enquanto que a segunda equação
estabelece que 𝑇5 ≥ 𝑇6. Temos novamente uma situação não factível e que não seria permitida
pelo modelo.
Figura 24: Roteiro com a ocorrência de subtours.
Fonte: elaborado pelo autor
Restrição (7): 𝑎𝑖 ≤ 𝑇𝑖 ≤ 𝑏𝑖, ∀ 𝑖 𝜖 𝑁
Esta restrição complementa a restrição (6) na determinação das janelas de tempo. A
restrição garante que o horário de início de atendimento de um cliente i estará dentro de sua
janela de tempo pré-determinada [𝑎𝑖, 𝑏𝑖].
Restrição (8): ∑ ∑ 𝑥𝑖𝑗𝑣
𝑖𝜖𝑁𝑣𝜖𝐾 = 1 , ∀ 𝑗 𝜖 𝑁
Garante que cada cliente é visitado uma única vez, condizente com a frequência
unitária semanal estabelecida. Os clientes com frequência original maior que 1 são repartidos
em um número de clientes igual ao valor da frequência original, com a mesma demanda
média por entrega e com frequência unitária. Para impedir que haja mais de uma entrega em
um mesmo dia a um mesmo cliente, os clientes repartidos são alocados em janelas de tempo
diferentes ao longo da semana, como indicado pela Tabela 6.
Restrição (9): ∑ 𝑑𝑖𝑦𝑖𝑣
𝑖𝜖𝑁 ≤ 𝐶𝑣, ∀ 𝑣 𝜖 𝐾
Garante que a capacidade de cada veículo (roteiro) não será excedida. Cada veículo v
possui uma capacidade 𝐶𝑣 medida em termos de 𝑚2 de vidro. Em contrapartida, cada cliente
possui uma demanda média de 𝑚2 de vidro por entrega igual a 𝑑𝑖. A expressão ∑ 𝑑𝑖𝑦𝑖𝑣
𝑖𝜖𝑁 me
58
permite, portanto, identificar a quantidade média de 𝑚2 a ser transportada pelo veículo (roteiro)
v.
Restrição (10): 𝑀 ∗ 𝑧𝑤 ≥ ∑ 𝑉𝑣𝑣𝜖𝑘𝑤, ∀ 𝑤 𝜖 𝑊
Esta restrição estabelece a relação de existência entre os roteiros e os centros de
distribuição. Um roteiro de um determinado centro de distribuição só pode existir se o
respectivo centro de distribuição também existir e for utilizado. O mesmo é válido para a relação
inversa, um centro de distribuição apenas é utilizado se houver roteiros partindo do referido
depósito.
Na expressão, a constante M é um número suficientemente grande tal que M |K| de
maneira que, caso exista algum roteiro dentro do conjunto 𝑘𝑤, a variável 𝑧𝑤 será forçada a
apresentar valor positivo.
Esta restrição é importante para o modelo na medida em que ela estabelece se um
depósito é utilizado ou não e, assim, permite ao modelo considerar os respectivos custos de
utilização do depósito.
Para exemplo de ilustração, na configuração apresentada na Figura 25, a variável 𝑧1 e
𝑧2 apresentariam valor igual a 1, já que possuem roteiros ligados aos respectivos centros de
distribuição. Já as variáveis 𝑧3 e 𝑧4 teriam valor igual a 0 já que não possuem roteiros ligados
aos depósitos.
59
Figura 25: Ilustração do funcionamento da restrição 10.
Fonte: elaborado pelo autor
Restrição (11): 𝑥𝑖𝑗𝑣 ∈ {0,1}, ∀ 𝑖, 𝑗, 𝑣
Restrição (12): 𝑦𝑖𝑣 ∈ {0,1}, ∀ 𝑖, 𝑣
Restrição (13): 𝑉𝑣 ∈ {0,1}, ∀ 𝑣
Restrição (14): 𝑧𝑖 ∈ {0,1}, ∀ 𝑖
As restrições 11, 12, 13 e 14 estabelecem o caráter binário de certas variáveis de decisão.
61
5. METODOLOGIA DE LEVANTAMENTO DE DADOS E DE IMPLEMENTAÇÃO
DA SOLUÇÃO
Dado o grande porte do grupo e a pulverização dos locais de produção por toda a Europa
torna-se interessante também a padronização da metodologia implementada para otimização de
transportes visando futuros trabalhos. Este capítulo apresentará a metodologia seguida para
levantamento e análise dos dados bem como considerações sobre a implementação da solução
uma vez que uma solução tenha sido escolhida. Esta metodologia segue os princípios
estabelecidos pelo departamento de Supply Chain da empresa.
Para o estabelecimento de uma metodologia de projetos de otimização, a empresa procurou
basear-se na metodologia DMAIC do sistema seis sigmas de controle de qualidade. DMAIC é
uma metodologia de mudança e desenvolvimento de novas rotinas e é baseado em cinco etapas
(SCHROEDER et al., 2008) (MAST; LOKKERBOL, 2012):
Define: define o problema;
Measure: traduz o problema de uma maneira que ele possa ser mensurado;
Analyze: analisa o problema e identifica causas;
Improve: cria e implementa ações e ajustes afim de melhorar a performance do
sistema;
Control: controla as medidas implementadas de maneira a assegurar uma solução
mais perene.
Na metodologia utilizada, a etapa de measure, ou medição, é mais direta uma vez que
os indicadores de performance e o procedimento de medição são idênticos a todos as fábricas e
já foram estabelecidos previamente.
Tem-se, portanto, uma metodologia constituída de quatro etapas, cada uma com diversas
atividades desenvolvidas especificamente para responder as necessidades da empresa,
conforme sintetizado na Figura 26:
62
Figura 26: Etapas da metodologia para otimização de rotas
Fonte: elaborado pelo autor com base em metodologia implementada na empresa.
5.1. Levantamento de dados (rotas, clientes, frota, zonas de entrega)
A coleta e análise de informações é uma das etapas mais importantes do processo de
otimização. A qualidade e a confiabilidade dos dados impactarão diretamente o modelo e o
resultado obtido. Para ter-se certeza que o modelo construído representa bem a realidade
enfrentada pela fábrica, deve-se assegurar que a exatidão dos dados de entrada e sua
compatibilidade com o contexto atual das fábricas analisadas.
Para construção do modelo matemático necessita-se de dois grandes grupos de
informação. O primeiro com informações sobre os clientes como seus históricos de pedidos,
sua localização e suas restrições de entrega tais como horário de funcionamento e tipo de
caminhão e equipamento necessário para realizar as entregas. Em segundo lugar deve-se obter
informações sobre a frota de veículos disponíveis para entrega como o número, tipo e
capacidade dos caminhões disponíveis e as restrições horárias dos motoristas. Em maiores
detalhes, as informações necessárias são:
a) Dados dos clientes ao longo do período histórico escolhido para análise:
- Código e nome do cliente;
- Pedidos realizados;
- Fornecedor do pedido;
- Data de entrega;
- Quantidade entregue;
- Número de peças entregues;
1. Levantamento de dados (rotas, clientes, frota, zonas de entrega)
2. Análise da situação atual
3. Encontrar a configuração de transporte ótima com modelagem matemática
4. Adaptar, implementar e controlar a solução
63
- Peso do pedido;
- Endereço de faturamento;
- Endereço de entrega;
- Rota utilizada para entrega;
- Tipo de endereço de entrega (canteiro de obra, endereço comercial do
cliente ou o cliente realizou a coleta do produto).
Estas informações podem ser obtidas a partir do sistema de informações da empresa que
realiza o arquivamento de todas as informações relativas à pedidos. Além disso deve-se obter
informações qualitativas quanto às restrições de entrega aos clientes:
b) Restrições de entrega (principalmente para os grandes clientes)
- Horários possíveis de entrega;
- Tipo de caminhão que pode acessar o cliente;
- Dias possíveis de entrega.
As informações qualitativas devem ser obtidas junto às equipes comerciais das fábricas que
conhecem de fato as necessidades dos clientes. No Apêndice A, pode-se encontrar uma ficha
modelo a ser enviada aos clientes pelo departamento comercial das fábricas para facilitar a
obtenção destas informações.
Deve-se também realizar levantamentos quanto à frota e quanto a fábrica com dados obtidos
com consulta à própria fábrica:
c) Descrição da frota da fábrica
- Características e particularidades dos caminhões;
- Capacidade dos caminhões em termos de m² de produtos e em peso;
- Histórico de carga do caminhão e taxa de carregamento do caminhão;
- Restrições horária dos motoristas;
- Tipo de contrato do caminhão (locação ou propriedade da empresa) e
características do contrato.
d) Informações sobre a fábrica
- Endereço;
- Papel da fábrica na região;
- Restrições de produção;
- Contexto comercial e de produção.
Para definição das restrições de demanda dos clientes, deve-se partir de informações
históricas. O objetivo é encontrar uma frequência semanal histórica para cada cliente e uma
64
quantidade média de produtos entregues por cliente e por entrega, medida em 𝑚2 de produto.
Para realizar esta coleta e análise histórica devemos incialmente escolher um período histórico
para análise que reflita as condições existentes atualmente.
É importante lembrar que no mercado regional existe forte presença de sazonalidade e de
variabilidade. Os pedidos podem variar a cada semana e existem meses de baixa e alta atividade.
Por exemplo, o mês de agosto é o tradicional mês de férias de verão na Europa e, por esta razão,
as fábricas e seus clientes paralisam suas atividades por 3 ou 4 semanas para proporcionar férias
aos seus empregados. Os clientes também variam seus pedidos em função dos projetos que
recebem. A empresa possui também diversos tipos de clientes, alguns encomendando com
maior ou menor frequência.
Para reduzir o efeito da variabilidade e da sazonalidade, utiliza-se uma média histórica dos
dados corrigidos pelo fator de sazonalidade. O objetivo é identificar para cada cliente o número
médio histórico de encomenda em uma semana e a quantidade média de 𝑚2 de vidro e tipo de
vidro por cliente e por pedido. Deve-se, portanto, escolher um período de estudo compatível
com a realidade atual da fábrica. Dado o dinamismo do mercado, um período de 6 a 18 meses
mostra-se bem adequado para a identificação de médias dos pedidos. Analisando períodos
maiores pode-se encontrar clientes que não existam mais ou com um comportamento muito
distinto do atual. Deve-se, entretanto, atentar a mudanças no contexto industrial da fábrica ao
longo do período considerado. Por exemplo, se houve recentemente uma fusão entre duas
fábricas na região ou o fechamento de uma fábrica vizinha, deve-se escolher um período
posterior à tal acontecimento ou realizar uma triagem nos dados coletados.
Como existe sazonalidade no mercado e como quer-se identificar a capacidade mínima
necessária para servir os clientes, deve-se considerar também a demanda máxima no período
pois, invariavelmente, a empresa deve estar apta para atendê-la. Por isso, deve-se aplicar um
fator de correção (índice de sazonalidade) à média encontrada de maneira a identificar as
capacidades necessárias no período de alta demanda. O índice de sazonalidade é dado pela
divisão da demanda média do período considerado pela demanda média de toda a série
histórica. Trata-se de uma indicação de o quanto maior a demanda da semana, mês ou trimestre
foi maior que a demanda média de todos os períodos (ARNOLD; CLIVE; CHAPMAN, 2008):
Í𝑛𝑑𝑖𝑐𝑒 𝑑𝑒 𝑆𝑎𝑧𝑜𝑛𝑎𝑙𝑖𝑑𝑎𝑑𝑒 = 𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑚é𝑑𝑖𝑎 𝑑𝑜 𝑝𝑒𝑟í𝑜𝑑𝑜
𝑑𝑒𝑚𝑎𝑛𝑑𝑎 𝑚é𝑑𝑖𝑎 𝑑𝑒 𝑡𝑜𝑑𝑜𝑠 𝑜𝑠 𝑝𝑒𝑟í𝑜𝑑𝑜𝑠
65
Como pode ser visto na Figura 27, o mês de julho apresenta um aumento de cerca de 40%
da demanda em comparação com a demanda média do ano. Isto se deve à antecipação de
pedidos que alguns clientes realizam prevendo o período de férias da empresa no mês de agosto.
Os meses de setembro e outubro também são de alta atividade pois representam o início da
temporada escolar e de trabalho europeia e, portanto, de retomada de projetos e de realização
de pedidos acumulados ao longo de agosto enquanto a indústria estava de recesso.
Figura 27: Gráfico de sazonalidade ao longo do ano para uma fábrica Glassolutions.
Fonte: elaborado pelo autor.
Uma vez escolhido o período de estudo, deve-se coletar informações que permitam
analisar a situação atual e as necessidades da fábrica.
Dado que se procura encontrar rotas otimizadas e comparar cenários à nível estratégico,
isto é, à longo prazo, deve-se trabalhar com dados médios da demanda e da frequência de
entrega. Por exemplo, se um cliente recebeu entregas 55 vezes durante um período de 12 meses,
deve-se atribuir a este cliente uma taxa de entrega média de 1,14 vezes por semana, que é
aproximado para o valor inteiro de 1 vez por semana, considerando cerca de 48 semanas de
atividade completa da fábrica. Deve-se também calcular a demanda média do cliente. Portanto,
se para o mesmo cliente do exemplo, a empresa entregou 480 𝑚2 de vidro com peso total de
2400 kg nos mesmos 12 meses, trata-se de uma demanda média de 10 𝑚2 e de 50 kg por entrega
(1 entrega por semana atribuída ao cliente por 48 semanas de atividade da fábrica). Assim, sabe-
se que a fábrica deve reservar em suas rotas semanais ao menos uma parada para entregar a este
cliente em média 10 𝑚2 de produto que pesarão, em média, 50 kg. Este raciocínio deve ser
0,00
0,20
0,40
0,60
0,80
1,00
1,20
1,40
1,60
Jan. Fev. Mar. Abr. Mai. Jui. Jul. Ago. Set. Out. Nov. Dez.
66
reproduzido para todos os clientes da fábrica. Assim, pode-se estimar a capacidade do caminhão
em termos de 𝑚2 e de peso que será ocupada por pelos clientes da empresa.
Uma vez que se procura trabalhar com dados médios de um período histórico e que o
objetivo da empresa é encontrar rotas de entrega regulares e avaliar cenários logísticos
estratégicos, é necessário trabalhar com dados estáveis e com uma frequência regular de
entrega, isto é, clientes que são entregues ao menos uma vez por semana.
Entretanto, em boa parte dos casos encontra-se clientes com frequência de entrega
inferior à 1. Se, por exemplo, em um período de 6 meses (26 semanas) tem-se um cliente que
recebeu 13 entregas (média de 0,5 entregas por semana), não se pode atribuir a estre cliente
uma frequência de uma parada semanal com risco de “poluir” o modelo construído.
A solução encontrada para responder a este tipo de caso e diluir o efeito da variabilidade
das entregas no modelo é de reagrupar os clientes não regulares próximos em zonas de entrega
com uma frequência de entrega semanas igual ou superior à uma entrega por semana. Assim,
pode-se assegurar que, em média, um caminhão deverá passar nesta zona de entrega ao menos
uma vez na semana e este conjunto de clientes pode ser considerado um ponto de parada regular
do caminhão. A demanda média para esta zona de entrega será igual à soma da demanda dos
clientes que constituem a zona.
5.2. Análise da situação atual
Antes de iniciar um projeto de otimização e de estabelecer as novas rotas deve-se conhecer
a situação atual da fábrica. Deve-se estudar a localização da fábrica, seu papel na rede
Glassolutions, os recursos logísticos disponíveis, tipos de produtos fabricados e o contexto de
produção e da concorrência.
Uma vez conhecida a situação atual e o contexto da fábrica a ser analisada pode-se começar
a identificar cenários com potencial de melhora do serviço oferecido ao cliente e com potencial
de redução de custos. Estes cenários são possibilidades que direcionarão o modelo matemático
a encontrar uma melhor resposta seja otimizando a configuração atual ou encontrando uma
nova configuração de produção e transporte que resulte em um sistema mais eficiente. São
configurações de transporte em que se muda a maneira de servir cliente, seja em termos de
frequência de entrega, mudança na fábrica que atenderá o cliente ou com mudanças na maneira
de entrega.
67
Um eixo de otimização, por exemplo, seria alterar frequências de entrega de certos clientes
percebidos como mais ou menos importantes pela fábrica ou considerar a entrega de produtos
entre filiais de maneira a otimizar as entregas dentro de um contexto regional.
Esta etapa permite compreender quais as restrições necessárias ao modelo matemático de
otimização a ser empregado. Para o caso norueguês tratado neste trabalho, esta fase de estudos
permitiu considerar novos centros de distribuição a partir dos quais se poderia realizar entregas,
conforme descrito na Seção 2.2.
Cada opção a ser explorado dependerá do contexto da fábrica estudada e do objetivo que se
procura atingir. O modelo matemático deverá, portanto, ser adaptado segundo as possibilidades
de cada fábrica.
5.3. Modelagem matemática do problema especificado
Com o auxílio de modelagem matemática e de técnicas de pesquisa operacional, pode-
se obter soluções de boa qualidade para o problema apresentado. Tem-se, assim, uma
metodologia e ferramenta que permite ganhos econômicos com a redução dos custos
operacionais pela otimização da rede de distribuição. O modelo permite, também, auxiliar na
tomada de decisão estratégica, uma vez que permite estimar os impactos que certas medidas
terão nos custos da empresa.
5.4. Adaptar, implementar e controlar a solução
Uma vez obtida uma solução com o auxílio de técnicas de pesquisa operacional deve-
se iniciar os trabalhos de implementação com certos cuidados. A distribuição representa um
eixo importante na estratégia da empresa. A qualidade do serviço percebida pelo cliente é
diretamente ligada ao serviço de entrega sendo este uma importante vantagem competitiva da
empresa face à concorrência e uma das principais razões para os clientes buscarem a empresa.
Deste modo, a implementação de mudanças relativas à distribuição exige atenção e cuidados
tanto da equipe logística quanto da equipe comercial e de tecnologia do grupo e deve, sobretudo,
estar alinhada com os clientes.
Antes de realizar a implementação das novas rotas e da solução escolhida deve-se
informar certos clientes e motoristas para obter o feedback destes quanto às mudanças
propostas. Os clientes podem não gostar das mudanças aos seus hábitos, solução importante
explicar os ganhos para toda as partes com a solução a ser implementada (redução dos atrasos
e maior flexibilidade). Deve-se buscar o consentimento de certos clientes que terão seus dias
68
de entrega alterados deixando claro a mudança com um certo período de antecedência,
principalmente para os maiores e mais importantes clientes.
Deve-se, também, discutir as mudanças com os motoristas, que conhecem a verdadeira
realidade das estradas e rotas e, assim, validar as escolhas de roteiros.
O sistema de informação da fábrica deve ser preparado para lidar com a nova lista de
roteiros. Ao receberem um pedido, os vendedores cadastram o pedido no sistema de informação
que, por sua vez, informará ao vendedor o dia de entrega. O sistema também enviará à fábrica
fornecedora do produto a ordem de produção com os respectivos prazos de produção e entrega.
Com a alteração de datas de entrega e dos centros de distribuição ligados a cada cliente, deve-
se recadastrar as informações no software.
Finalmente, deve-se assegurar a compreensão e validação de todos os envolvidos na
cadeia de distribuição do produto. Com mudanças nos depósitos intermediários dos produtos
deve-se buscar validar que as fábricas produtoras serão capazes de se adaptar às mudanças e
entregar os produtos conformes e no prazo acordado. Em contrapartida, a distribuidora final
dos produtos também deve estar alinhada com a solução implementada e disposta a gerenciar o
produto no depósito intermediário e entrega-lo ao cliente final no prazo.
Este alinhamento pode requerer a assinatura de novos contratos entre as diferentes partes
envolvidas especificando o novo desenho logístico empregado. As medidas necessárias para
implementação de uma solução são sintetizadas na Figura 28.
Figura 28: Etapas de implementação da solução
Fonte: elaborado pelo autor.
Contrôle e adaptação
Revisão das rotas segundo feedback dos clientes e motoristas;
Medir a eficicênciq das novas rotas;
Clientes
Informar os clientes sobre mudanças nos dias de entrega deixando claro os ganhos para os dois lados;
Comercial
Treinar a equipe comercial para a execução da nova proposta de serviço a ser oferecida (mudança de prazos de entrega, de dias de entrega e flexibilização das entregas)
Sistemas de informação
Implementar as novas rotas de entrega nos sistemas de informação da empresa;
Preparar os sistemas para entregas entre filiais;
69
6. RESOLUÇÃO DO PROBLEMA
Como mencionado no Capítulo 4, o problema de roteirização com localização de centros de
distribuição é NP-hard. Deste modo, sua resolução de maneira exata é limitada
computacionalmente pelo número de variáveis e de restrições. Dada a dimensão real do
problema, com 284 clientes, 5 centros de distribuição candidatos e 284 roteiros possíveis
ligados a cada depósito candidato e considerando a formulação apresentada no Capítulo 4, tem-
se um problema de programação linear inteira mista de 114.936.509 variáveis e 892.049
restrições.
Todavia, buscou-se a construção de um modelo a ser resolvido pelo método exato a fim de
medir a limitação computacional de resolução de problemas do tipo e compará-la à dimensão
real do problema. Mais importante, a resolução de versões reduzidas permite validar o modelo
matemático e permite a construção de uma base de comparação para os métodos não exatos a
serem utilizados posteriormente para resolução do problema em sua dimensão completa.
Posteriormente, buscou-se a utilização de heurísticas construtivas para a resolução do
problema em suas dimensões reais, que permitam obter soluções de boa qualidade de maneira
rápida e de fácil implementação.
6.1. Resolução exata de versões reduzidas
Nesta primeira etapa utilizou-se do software IBM CPLEX OPL versão 12.6.3 com
parâmetros padrão do software para teste do modelo e resolução de versões reduzidas do
problema. A codificação dentro do programa está disponível no Apêndice B, seguindo a
formulação do modelo apresentado no Capítulo 4.
A resolução do modelo matemático de maneira exata, mesmo que para versões reduzidas
do problema, permite avaliar o comportamento do modelo e a necessidade ou não de utilizar-
se de métodos heurísticos para a resolução de problemas maiores. Inicialmente foram realizados
inúmeros experimentos com populações aleatórias de clientes e centros de distribuição e
também com populações específicas para testar o funcionamento de diversas restrições do
modelo.
Foram realizados experimentos com variações no número de variáveis (clientes, depósitos
e roteiros) que permitiram verificar o tempo computacional para resolução e, assim, constituir
uma biblioteca de problemas e resultados que servirão, posteriormente, para avaliação dos
métodos heurísticos empregados.
70
A resolução de problemas com dimensões reduzidas permitiu também realizar uma série de
experimentos de sensibilidade para averiguar o comportamento do modelo e certificar-se da
consistência das restrições do problema.
Na Tabela 7 pode-se visualizar alguns dos testes realizados que permitem inferir a limitação
computacional de resolução do problema. Os testes foram realizados utilizando-se um
computador de sistema operacional Windows 10, com processador Intel® Core™ i5-
4200U CPU 1,60-2,29 GHz e com memória RAM instalada de 8,00 Gb. A Tabela 7 apresenta
diferentes problemas testes resolvidos, com sua descrição em termos de número de clientes,
depósitos candidatos analisados e número de veículos disponíveis para roteirização. Apresenta,
também, o tempo necessário para o programa encontrar a solução ótima.
Observa-se que o tempo para resolução do problema aumenta conforme aumenta-se o
número de variáveis do problema. Para o problema 1, em que se considera apenas 5 clientes e
25 roteiros à disposição, tem-se um tempo de resolução de 11,66 segundos. Já para o problema
20, também com 25 veículos à disposição, mas com 24 clientes envolvidos, observou-se um
tempo de resolução de 38,21 segundos.
Tabela 7: Resolução de maneira exata de problemas menores
Problema Número de
clientes
Número de
depósitos
candidatos
Número total
de veículos
disponíveis
Tempo para
resolução
(segundos)
1 5 5 25 11,66
2 6 5 25 12,00
3 7 5 25 12,18
4 8 5 25 12,27
5 9 5 25 12,11
6 10 5 25 13,04
7 11 5 25 13,64
8 12 5 25 14,28
9 13 5 25 15,55
10 14 5 25 18,99
11 15 5 25 18,65
12 16 5 25 19,59
13 17 5 25 17,94
14 18 5 25 25,08
15 19 5 25 27,31
16 20 5 25 29,63
17 21 5 25 31,00
18 22 5 25 22,82
71
19 23 5 25 25,85
20 24 5 25 38,21
21 25 5 30 50,96
22 25 5 40 371,23
23 30 5 30 2305,98
24 30 5 40 6053,80
25 35 5 40
Memória
computacional
insuficiente
Vale lembrar que o modelo matemático descrito no Capítulo 4 estabelece um conjunto de
veículos para cada depósito candidato de maneira a não limitar a resolução do problema.
Idealmente deve-se considerar um número de veículos, ou roteiros, disponíveis em cada
depósito suficiente para atender todos os clientes com viagens exclusivas se necessário (roteiros
com apenas 1 cliente). Deste modo, à medida em que se aumenta o número de clientes no
modelo, deve-se crescer também o número de veículos totais, aumentando o número de
variáveis e restrições no modelo e, consequentemente, o tempo para resolução.
Para compreender o efeito deste aumento de variáveis e restrições em termos de tempo de
resolução, basta comparar o problema de número 21 com o problema de número 22, e o
problema de número 23 com o problema 24, apresentados na Tabela 7. Os pares de problemas
destacados possuem o mesmo número de depósitos candidatos e clientes, mas com diferença
em termos do número de veículos disponíveis. No problema 21, tem-se 30 veículos à
disposição, ou seja, 6 veículos por depósito candidato. Já no problema 22 tem-se 8 veículos por
depósito, totalizando 40 veículos no total. O tempo de resolução aumentou de 50,96 segundos
no problema 21, para 371,23 segundos no problema 22. Um comportamento similar também é
observado para o par de problemas 23 e 24, em que ambos lidam com 30 clientes, mas com um
número diferente de veículos disponíveis. No problema 23 necessita-se de 2305,98 segundos
para resolução, enquanto que no problema 24 são necessários 6053,80 segundos.
Este aumento no tempo de resolução é esperado uma vez que ao se aumentar o número de
veículos (roteiros) disponíveis, aumenta-se o número de variáveis e de restrições do problema.
O comportamento do tempo de resolução observado é condizente com um problema NP-
hard. Portanto, dado o número de variáveis e restrições do problema que se busca resolver, não
é possível realizar a sua resolução de maneira exata com os hardwares comuns disponíveis no
mercado.
72
Além do tempo para resolução, outro fator limitante é a memória computacional disponível.
Ao tentar-se resolver o problema de número 25, descrito na Tabela 7, que engloba 35 clientes
e 40 veículos à disposição, o software empregado acusou memória computacional insuficiente.
A dimensão deste problema é ainda muito inferior à dimensão real do problema, com 284
clientes e um número não limitante de veículos à disposição, evidenciando a necessidade de
utilização de outros métodos para sua resolução.
6.2. Heurística Construtiva de Localização de Centros de Distribuição e de
Roteirização
Dado a impossibilidade computacional de resolução do problema atual completo de maneira
exata buscou-se o desenvolvimento de uma heurística de fácil implementação e replicação e
que resultasse em soluções de boa qualidade. Assim, buscou-se sequenciar as diferentes
tomadas de decisões dentro do problema de localização e roteamento com heurística
construtivas adaptadas para cada etapa.
Nagy e Salhi (2007) apontam que métodos sequenciais não permitem feedback entre os
resultados das diferentes etapas de decisão. Entretanto, Srivastava e Benton (1990) apontam
que métodos sequenciais em que se resolve primeiro o problema de localização e alocação e
posteriormente o problema de roteirização, podem resultas em soluções de boas qualidades para
alguns casos estudados.
No problema retratado neste trabalho, como as possíveis instalações são limitadas e com
localização bem estabelecidas, temos 4 grandes decisões a serem tomadas:
1. Quais instalações utilizar;
2. Quais clientes alocar a quais instalações;
3. Quais clientes atribuir a quais rotas;
4. Em qual ordem os clientes dentro de uma mesma rota devem ser atendidos.
As tomadas de decisão 1 e 2 referem-se essencialmente à problemas de localização
enquanto que as decisões 3 e 4 são típicas de problemas de roteirização.
I. Decisões de localização e alocação:
Dentro da primeira tomada de decisão, referente a quais instalações utilizar, insere-se
também uma reflexão sobre quantas instalações utilizar. Para responder de maneira construtiva
esta questão, utilizou-se uma heurística, baseada no algoritmo de centralidade utilizado por
73
Moshref-Javadi e Lee (2016). Nesta heurística considera-se um coeficiente de centralidade do
depósito (𝑐𝑒𝑛𝑡𝑔), calculado em função das distâncias do depósito a cada cliente, como parte do
critério para abertura de depósitos.
Este algoritmo permite avaliar quais os depósitos mais bem localizados, mas não indica o
número de depósitos a serem utilizados. Além disso, o coeficiente de centralidade, sozinho, não
permite a avaliação dos custos de utilização do depósito. Alguns depósitos podem estar em
zonas de alto custo de utilização, por exemplo, centros urbanos. Assim, apesar de estarem
melhor localizados em relação aos clientes, resultariam em um custo total mais elevado que
depósitos localizados em zonas periféricas.
Para resolução deste problema é necessário, portanto, a adaptação da heurística visando o
contexto do problema apresentado. Considera-se, inicialmente, múltiplos cenários com a
abertura de diferentes números de depósitos.
Neste caso, os cenários são as combinações de possíveis números de instalações a serem
utilizadas. De maneira geral, para um problema que tenha W depósitos candidatos, analisa-se
W cenários: cenário 1 com a abertura de 1 único depósito, cenário 2 com a abertura de 2
depósitos, cenário 3 com a abertura de 3 depósitos e assim por diante até o cenário W em que
se utiliza todos os depósitos.
Para cada cenário, utiliza-se como critério para abertura de depósitos o coeficiente de
abertura de depósito (𝐶𝑜𝑒𝑓𝐴𝐷𝑔), priorizando sempre os depósitos que apresentam maior valor
para este coeficiente. Este coeficiente considera a proximidade do depósito aos clientes,
representada pelo coeficiente de centralidade (𝑐𝑒𝑛𝑡𝑔), e o custo de utilização do depósito,
medido pelo coeficiente de custo de utilização (𝐶𝑜𝑒𝑓𝐶𝑈𝑔).
O coeficiente de centralidade do depósito g é calculado por:
𝑐𝑒𝑛𝑡𝑔 = ∑1
1 + 𝐶𝑔𝑖𝑖 𝜖 𝑁
Onde 𝐶𝑔𝑖 é o custo de deslocamento do depósito g ao cliente i.
Já o coeficiente de custo de utilização de cada depósito (𝐶𝑜𝑒𝑓𝐶𝑈𝑔) é calculado de maneira
a aumentar a probabilidade de escolha de centros de distribuição que possuam menor custo de
utilização e é dado pela proporção que este custo teria nos custos de distribuição atuais da
empresa:
74
𝐶𝑜𝑒𝑓𝐶𝑈𝑔 =𝐶𝑢𝑠𝑡𝑜 𝑑𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎çã𝑜 𝑑𝑜 𝑑𝑒𝑝ó𝑠𝑡𝑖𝑜 𝑔
𝐶𝑢𝑠𝑡𝑜 𝑑𝑒 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑖çã𝑜 𝑡𝑜𝑡𝑎𝑙 𝑎𝑡𝑢𝑎𝑙 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑔
É importante ressaltar que um depósito candidato que tenha um custo de utilização superior
aos custos de distribuição atuais deveria ser imediatamente desconsiderado uma vez que, ao se
adicionar o custo de roteirização a este depósito, ter-se-ia certamente um custo de distribuição
superior ao custo atual. Deste modo, o 𝐶𝑜𝑒𝑓𝐶𝑈𝑔 apresentará valor inferior a 1 para os depósitos
que devam ser considerados como candidatos.
Para escolha dos centros de distribuição candidatos a serem utilizados em cada cenário,
utiliza-se a fórmula seguinte, que considera o coeficiente de centralidade ponderado pelo custo
de utilização de cada centro de distribuição:
𝐶𝑜𝑒𝑓𝐴𝐷𝑔 = 𝑐𝑒𝑛𝑡𝑔(1 − 𝐶𝑜𝑒𝑓𝐶𝑈𝑔)
Um depósito candidato com maior custo de utilização terá, portanto, um maior valor de
𝐶𝑜𝑒𝑓𝐶𝑈𝑔 e, deste modo, terá o seu valor de 𝐶𝑜𝑒𝑓𝐴𝐷𝑔 reduzido. Isto pode impedir, por
exemplo, que um depósito com boa localização (alto valor de 𝑐𝑒𝑛𝑡𝑔) mas com custo de
utilização elevado acabe sendo escolhido, preterindo outro de menor custo de utilização e que,
assim, poderia resultar em um custo total final inferior.
Uma vez identificado quais centros de distribuição utilizar em cada cenário, ainda é
necessário alocar os clientes para cada depósito aberto.
Moshref-Javadi e Lee (2016) utilizaram os coeficientes de centralidade para identificar
quantos veículos alocar para cada instalação aberta. Para o problema estudado neste trabalho,
não há restrições quanto ao número de veículos uma vez que o transporte é terceirizado.
Entretanto, utiliza-se critério análogo para a alocação de clientes nas instalações abertas com
os centros de distribuição de maior coeficiente de centralidade recebendo maior parcela dos
clientes. De maneira geral, o número de clientes que um depósito aberto receberá é calculado
por:
𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑐𝑙𝑖𝑒𝑛𝑡𝑒𝑠 𝑎𝑙𝑜𝑐𝑎𝑑𝑜𝑠 𝑎𝑜 𝐶𝑒𝑛𝑡𝑟𝑜 𝑑𝑒 𝐷𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑖çã𝑜 𝑖 = 𝑐𝑒𝑛𝑡𝑖
𝑐𝑒𝑛𝑡𝑔̅̅ ̅̅ ̅̅ ̅𝑁,
onde 𝑐𝑒𝑛𝑡𝑔̅̅ ̅̅ ̅̅ ̅ é a média dos coeficientes de centralidade das demais instalações abertas no
referido cenário e N é o número total de clientes.
75
Uma vez estabelecido o número de clientes alocados a cada centro de distribuição,
deve-se identificar quais clientes alocar a quais instalações. Neste caso utiliza-se de um
algoritmo de distribuição dos clientes em que se inicia pela instalação aberta de maior
centralidade, atribuindo-lhe os clientes mais próximos à instalação até que o número de
clientes atribuídos ao centro de distribuição seja atendido. Repete-se este procedimento para
os demais centros de distribuição abertos.
II. Decisões de roteirização:
Após estabelecer quais centros de distribuição utilizar em cada cenário e quais clientes serão
alocados a cada centro de distribuição, deve-se iniciar a construção dos roteiros. Dentro desta
etapa existem duas categorias de decisão a serem tomadas, quais clientes inserir em quais
roteiros e em qual ordem visitar os clientes inseridos no roteiro.
Solomon (1987) apresenta uma heurística de inserção sequencial para roteamento de
veículos com janela de tempo, obtendo soluções de boa qualidade para os problemas
testados. O autor apresenta três critérios para a inicialização de uma nova rota:
1. Cliente não atendido de maior distância ao centro de distribuição;
2. Cliente não atendido com restrição de tempo mais urgente;
3. Cliente não atendido com a menor ponderação de distância e duração do trajeto
direto ao cliente;
Neste trabalho decidiu-se utilizar o primeiro critério pela sua clareza e coerência.
Ronconi e Manguino (2016) obtiveram bons resultados utilizando este mesmo critério ao
aplicar a heurística de Solomon. Em seguida, para cada iteração, utiliza-se dois critérios para
inserção de clientes nas rotas:
𝑐1(𝑖, 𝑢, 𝑗) : indica o ponto ideal de inserção (entre os clientes i e j) e o impacto
negativo que a inserção do cliente u traz para o roteiro;
𝑐2(𝑖, 𝑢, 𝑗) : indica o benefício da inserção do cliente u no roteiro em comparação
com a construção de uma nova rota direta ao cliente u;
Diversas possibilidades de cálculo de 𝑐1 e 𝑐2 são indicadas pelo autor. Neste trabalho
considera-se 𝑐1 como o custo suplementar da inserção do cliente u na rota, entre os clientes i e
j, e 𝑐2 como o benefício, em termos de custo, da inserção do cliente u entre os clientes i e j em
comparação com o custo de se criar uma rota direta entre o depósito e o cliente u.
76
Seja (𝑖0, 𝑖1, 𝑖2, 𝑖3, … , 𝑖𝑚) a rota em construção atual, com 𝑖0 = 𝑖𝑚 = 0. A posição ideal
de inserção do cliente u e o custo suplementar desta inserção pode ser calculado por:
𝑐1(𝑖, 𝑢, 𝑗) = min[𝑐1(𝑖𝑝−1, 𝑢, 𝑖𝑝)] , 𝑝𝑎𝑟𝑎 𝑝 = 1, … , 𝑚
Onde
𝑐1(𝑖𝑝−1, 𝑢, 𝑖𝑝) = 𝑐𝑢𝑠𝑡𝑜(𝑖𝑝−1, 𝑢) + 𝑐𝑢𝑠𝑡𝑜(𝑢, 𝑖𝑝) − 𝑐𝑢𝑠𝑡𝑜 (𝑖𝑝−1, 𝑖𝑝)
O benefício da inserção do cliente u na rota é calculado por:
𝑐2(𝑖, 𝑢, 𝑗) = 𝑐𝑢𝑠𝑡𝑜(0 , 𝑢) − 𝑐1(𝑖, 𝑢, 𝑗)
O algoritmo empregado para implementação desta heurística de roteirização é
apresentado na Figura 29.
Figura 29: Heurística de inserção para roteamentos baseado em Solomon (1987).
Fonte: elaborado pelo autor
Início do algoritmo de roteirização
1. Se todos os clientes já estiverem roteados, encerra-se o procedimento. Caso
contrário, inicia-se uma nova rota com a inserção do cliente não atendido mais
distante ao centro de distribuição.
2. Avalia-se quais cliente são candidatos à inserção (capacidade do veículo). Se houver
ao menos um cliente candidato, passar para a etapa 3. Caso contrário, retornar à
etapa 1.
3. Para cada cliente candidato u, calcular 𝑐1(𝑖, 𝑢, 𝑗) referente à melhor posição de
inserção e ao custo suplementar de inserção do cliente na rota. Verificar o impacto
da inserção do cliente no roteiro em termos de tempo de entrega. Se houver
violação das janelas de tempo, excluir o cliente da lista de candidatos.
4. Calcular 𝑐2(𝑖, 𝑢, 𝑗) referente ao benefício da adição do cliente u ao roteiro. Adicionar
ao roteiro o cliente com maior valor positivo de 𝑐2(𝑖, 𝑢, 𝑗) e retornar à etapa 2. Caso
não haja clientes com valor positivo de 𝑐2(𝑖, 𝑢, 𝑗), retornar à etapa 1.
Fim
77
Uma vez terminado a roteirização para todos os centros de distribuição abertos no
cenário, inicia-se a roteirização do cenário seguinte até que todos os cenários considerados
tenham sua etapa de roteirização concluída.
Em seguida, compara-se os custos totais de distribuição de cada cenário, escolhendo o
cenário de menor custo como solução.
O algoritmo completo da heurística construtiva sequencial empregada é sintetizado na
Figura 30.
Figura 30: Heurística sequencial construtiva para resolução do problema de localização e roteirização.
Fonte: elaborado pelo autor
Início do algoritmo sequencial de resolução do problema de localização e roteirização
de veículos.
1. Calcular coeficientes de centralidade (𝑐𝑒𝑛𝑡𝑔) para cada depósito candidato.
2. Calcular coeficiente de abertura de depósito (𝐶𝑜𝑒𝑓𝐴𝐷𝑔) para cada depósito
candidato.
Para i = 1 até W
3. Abrir i centros de distribuição com maior valor de 𝐶𝑜𝑒𝑓𝐴𝐷𝑔.
4. Calcular número de clientes a serem alocados a cada centro de distribuição
(𝑁𝑔) baseado no valor de 𝑐𝑒𝑛𝑡𝑔.
5. Alocar clientes aos centros de distribuição abertos, dando prioridade aos
centros de maior 𝑐𝑒𝑛𝑡𝑔, até que o número de clientes alocados ao centro de
distribuição atinja o valor de 𝑁𝑔.
6. Algoritmo de roteirização para cada centro de distribuição aberto conforme
ilustrado na Figura 29.
7. Calcular custo total do cenário.
Atualizar o valor de i, acrescentando-lhe uma unidade, e retornar à Etapa 3
8. Escolher como solução o cenário de menor custo total.
Fim
78
6.2.1. Validação do método heurístico apresentado
Como teste de validação da heurística construtiva apresentada realizou-se uma série de
experimentos que permitissem analisar o comportamento do modelo, comparando sempre os
resultados à resolução exata dos experimentos. Nestes experimentos de sensibilidade, variou-
se alguns parâmetros como custos de utilização, custos de deslocamento, tempo de
deslocamentos, restrições de janelas de tempo entre outros, de maneira a avaliar o
comportamento do modelo.
Resolveu-se finalmente replicar as simulações testes resolvidas de maneira exata na Seção
6.1 e comparar os resultados em termos de centros de distribuição utilizados, roteiros
construídos e custo total (função objetivo a ser minimizada). Na Tabela 8 pode-se visualizar a
comparação dos resultados obtidos na resolução dos problemas de dimensão reduzidas com o
método heurístico com a resolução exata dos problemas.
Tabela 8 : Resolução de versões reduzidas com a heurística proposta e comparação com a resolução exata
Problema Número
de clientes
Número de
Depósitos
Candidatos
Diferença do valor da função
objetivo em relação à resolução
exata (%)
1 5 5 0,6
2 6 5 4,9
3 7 5 3,6
4 8 5 0,0
5 9 5 11,3
6 10 5 11,5
7 11 5 8,9
8 12 5 7,9
9 13 5 8,0
10 14 5 8,6
11 15 5 9,1
12 16 5 11,0
13 17 5 15,6
14 18 5 14,8
15 19 5 13,8
16 20 5 13,6
17 21 5 12,2
18 22 5 14,1
19 23 5 14,5
20 24 5 13,8
21 25 5 14,2
23 30 5 4,8
79
Conforme observado na Tabela 8, a diferença média dos valores obtidos em relação à
solução exata para todos os problemas foi de 9,85%, sendo que o maior desvio encontrado foi
de 15,6%. Os resultados obtidos na resolução de problemas de dimensões reduzidas indicam
que a heurística proposta é capaz de obter soluções de boa qualidade.
Ainda mais importante que a obtenção de soluções de boa qualidade para problemas de
dimensões reduzidas é a obtenção de boas soluções para o problema em sua dimensão completa,
objetivo do trabalho. Neste caso, um dos indicadores a ser considerado será a comparação da
solução obtida para o problema em suas dimensões reais com os valores atuais da empresa.
Deste modo, a obtenção de uma solução com custos inferiores aos praticados atualmente
representariam ganhos diretos para a empresa e, mesmo que não se possa garantir a obtenção
de um valor ótimo, ter-se-ia uma solução melhor que a configuração atual da empresa.
6.2.2. Implementação da heurística
Para a implementação da heurística desenvolvida utilizou-se de programação em linguagem
VBA (Visual Basic for Applications) no software Microsoft Exel. A Escolha da linguagem de
programação se deu pela facilidade de comunicação entre o programa e as bases de dados
construídas em Excel e pela ampla difusão do software no mundo corporativo.
O programa implementado segue as etapas da heurística descritas na Figura 30, com a
resolução sequencial do problema. Para cada cenário, decide-se primeiro quais depósitos
utilizar, em seguida quantos clientes e quais clientes alocar a cada depósito e, finalmente,
realiza-se a roteirização. O código do programa implementado encontra-se disponível no
Apêndice C.
Como dados de entrada para o programa temos principalmente:
Matriz de custo de deslocamento entre clientes e depósitos (dada a grande proporção
da matriz, 290x290, disponibiliza-se apenas uma parte da mesma no Apêndice D);
Matriz de tempo de deslocamento entre clientes depósitos (dada a grande proporção
da matriz, 290x290, disponibiliza-se apenas uma parte da mesma no Apêndice E);
Tabela de demanda (em 𝑚2) por cliente;
Janela de tempo de cada cliente;
Para obtenção das matrizes de custo e tempo de deslocamento entre clientes e entre clientes
e depósitos utilizou-se de um software de geolocalização, Geoconcept, disponível na empresa.
A partir da lista de endereços dos clientes e dos depósitos e da parametrização dos veículos de
80
entrega, permite-se a obtenção das matrizes de distância em e de tempo de condução entre os
pontos. O custo de deslocamento é calculado em função da distância e do tempo entre os pontos,
conforme contrato comercial estabelecido entre a empresa e a transportadora.
Como temos uma frota homogênea de entrega, a capacidade é considerada igual para todos
os roteiros e estabelecido em 150 𝑚2 por veículo. Além disso, estabeleceu-se um limite de até
30 clientes por roteiro, número suficientemente grande para não restringir o problema ao longo
de sua resolução. Conforme experiência com as atuais entregas e conforme mostram os
resultados obtidos, este número é suficientemente grande, com as entregas raramente superando
15 clientes em um mesmo roteiro.
Os resultados obtidos serão apresentados e discutidos no capítulo seguinte.
81
7. ANÁLISE DOS RESULTADOS
Neste capítulo serão apresentados os resultados obtidos na resolução do problema com
a heurística proposta no trabalho. Apresenta-se em detalhes a nova configuração proposta e
a economias obtidas com a solução.
Realiza-se, também, análises de sensibilidade a fim de identificar a variação da solução
obtida com a variação de alguns fatores de mercado como, por exemplo, aumento do custo
de deslocamento e redução do custo de utilização dos depósitos. O objetivo das análises de
sensibilidade é compreender a volatilidade da solução proposta, analisando qual a mudança
necessária na estrutura de custos na Noruega para afetar a solução sugerida.
7.1. Solução Proposta
Utilizado a heurística sequencial e construtiva descrita no Capítulo 6, pôde-se encontrar
uma solução de boa qualidade para a localização dos centros de distribuição e de roteirização
dos veículos para o problema tratado neste trabalho em sua instância completa.
Temos um total de 284 entregas semanais a serem realizadas a partir de 5 centros de
distribuição candidatos, identificados na Figura 31.
Figura 31: mapa da Noruega com depósitos candidatos em amarelo e o depósito existente de Fredrikstad em
azul.
Fonte: elaborado pelo autor com ferramenta google maps.
82
Na Tabela 9 pode-se visualizar resultados obtidos para cada cenário, sendo o cenário 1 com
a abertura de 1 depósito candidato e o cenário 5 com a abertura de todos os depósitos. Nota-se
que o cenário mais vantajoso para a empresa é aquele com a abertura de dois centros de
distribuição: Fredrikstad (centro de distribuição atualmente utilizado) e Hamar. Esta
configuração de transporte permitiria uma economia de 5,9% nos custos de distribuição da
empresa no país. No cenário 4 e 5 temos um aumento do custo de distribuição dado
principalmente pela menor concentração de clientes em torno dos depósitos de Bergen e
Trondheim, pelo alto custo de transporte a estes dois depósitos mais afastados das fábricas
fornecedoras e pelo custo de utilização das instalações.
Tabela 9: Resultados para cada cenário na resolução completa do problema utilizando método heurístico
Centros de Distribuição Utilizados Custo total em relação
à situação atual
Cenário 1 Fredrikstad -1,8%
Cenário 2 Fredrikstad, Hamar -5,9%
Cenário 3 Fredrikstad, Hamar, Sandnes -1,7%
Cenário 4 Fredrikstad, Hamar, Sandnes, Bergen 1,3%
Cenário 5 Fredrikstad, Hamar, Sandnes, Bergen e
Trondheim 4,4%
É importante notar que mesmo dentro do cenário 1, com a utilização de um único centro de
distribuição, temos ganhos de 1,8% apenas com a otimização dos roteiros existentes. Neste
cenário, a heurística empregada identificou como mais vantajoso continuar utilizando o centro
de distribuição atualmente empregado, Fredrikstad. De fato, como apresentado pela Tabela 10,
o centro de Fredrikstad é o depósito candidato com maior coeficiente de centralidade,
favorecido principalmente pela sua proximidade à aglomeração urbana de Oslo, a maior do
país. Percebe-se, portanto, que havia ineficiências na construção dos roteiros e, com um simples
remanejamento dos clientes entre roteiros, obtêm-se economias.
Tabela 10: Coeficientes de centralidade para os diferentes depósitos candidatos.
Centro de Distribuição Coeficiente de Centralidade
Fredrikstad 0,384
Hamar 0,122
Sandnes 0,070
Bergen 0,067
Trondheim 0,051
83
Entretanto com o emprego da solução proposta pelo cenário 2, obtêm-se um ganho quase
três vezes superior ao ganho de apenas se otimizar os roteiros a partir da estrutura atual, com
uma economia de 5,9% nos custos de distribuição da empresa. A configuração proposta com a
utilização dos centros de distribuição de Fredrikstad e Hamar pode ser visualizada na Figura
32.
Figura 32: Mapa da Noruega com os dois centros de distribuição utilizados na solução proposta.
Fonte: elaborado pelo autor com ferramenta google maps.
Na heurística empregada, baseia-se nos valores dos coeficientes de centralidade dos
depósitos abertos para alocar clientes a cada depósito. Deste modo, na solução apresentada,
alocou-se os 215 clientes ao depósito de Fredrikstad e os 69 restantes ao centro de distribuição
de Hamar.
Para atender estes clientes foram criados 44 roteiros a partir de Fredrikstad e 21 a partir de
Hamar. Os roteiros sugeridos pela heurística empregada são apresentados na Tabela 11, para
Fredrikstad, e na Tabela 12 para Hamar. A primeira linha da tabela indica a posição dos clientes
dentro do roteiro com a coluna “#1” indicando o primeiro cliente do roteiro, a coluna “#2” o
segundo cliente do roteiro e assim por diante. De maneira a garantir a confidencialidade dos
dados da empresa, renomeou-se cada um dos 5 centros de distribuição e 284 clientes por um
nome genérico resultado da concatenação da letra “C” e um índice de identificação de cliente.
84
Tabela 11 : Roteiros sugeridos para o centro de distribuição de Fredrikstad na solução proposta.
Roteiro\Posição #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13
Roteiro 1 C223 C142 C131 C17 C129 C126 C124 C122 C120 C95
Roteiro 2 C162 C158 C148 C10 C40 C118 C41 C123 C116 C113 C115 C101
Roteiro 3 C130 C128 C125 C121 C117 C114 C132 C149
Roteiro 4 C39 C112 C263 C119
Roteiro 5 C134 C133 C127 C277
Roteiro 6 C264 C262 C272 C154 C144
Roteiro 7 C56 C43 C278 C135 C143 C7 C228 C54 C235 C226
Roteiro 8 C240 C153 C44 C155 C265
Roteiro 9 C266
Roteiro 10 C241 C166 C161 C46 C20 C146 C157 C267
Roteiro 11 C137
Roteiro 12 C138
Roteiro 13 C279 C42 C275 C140 C139 C55 C136
Roteiro 14 C282 C289 C283 C233 C53 C179 C224 C276
Roteiro 15 C259 C248 C242 C246 C156 C268
Roteiro 16 C194 C186 C183 C22 C31 C145 C269
Roteiro 17 C260 C32 C199 C205 C201 C247 C270
Roteiro 18 C196 C210 C52 C188 C147 C271
Roteiro 19 C165 C24 C163 C45 C19 C150 C18 C141
Roteiro 20 C152 C151 C159 C181 C47
Roteiro 21 C48 C172 C174 C169 C176 C219 C177 C237 C229 C227 C206 C203 C6
Roteiro 22 C221
Roteiro 23 C222
Roteiro 24 C230 C234 C225 C170 C208 C214 C50
Roteiro 25 C216 C232 C236 C239
Roteiro 26 C238 C231 C180 C175 C173 C178 C220 C215 C209 C171
Roteiro 27 C167 C189 C164 C21 C160 C185
Roteiro 28 C207 C204
Roteiro 29 C217 C213 C211 C193 C190 C212 C49 C27 C197
Roteiro 30 C25 C23 C184 C187 C192 C195 C218 C51 C28
Roteiro 31 C255 C191
Roteiro 32 C26 C182 C29 C198 C200 C30 C202 C243 C245
Roteiro 33 C281 C168
Roteiro 34 C286 C280
Roteiro 35 C258 C261 C284 C244
Roteiro 36 C256 C285
Roteiro 37 C253 C287
Roteiro 38 C257 C288
Roteiro 39 C249
Roteiro 40 C254
Roteiro 41 C252
Roteiro 42 C250
Roteiro 43 C251
85
Tabela 12: Roteiros sugeridos para o centro de distribuição de Hamar na solução proposta.
Com o auxílio das restrições de janelas de tempo, pode-se garantir a distribuição dos
clientes e, consequentemente de demanda de produtos ao longo da semana. Evita -se, também,
que clientes recebessem visitas diversas vezes em um mesmo dia. As Tabelas 13 e 14
apresentam os dias de execução de cada roteiro para os centros de distribuição de Fredrikstad e
Hamar.
Tabela 13: Dias de execução dos roteiros sugeridos para o centro de distribuição de Fredrikstad.
Roteiro Dia da
semana
Roteiro 1 Terça-Feira
Roteiro 2 Terça-Feira
Roteiro 3 Sexta-Feira
Roteiro 4 Quarta-Feira
Roteiro 5 Terça-Feira
Roteiro 6 Terça-Feira
Roteiro 7 Quinta Feira
Roteiro 8 Segunda-Feira
Roteiro 9 Terça-Feira
Roteiro 10 Quinta Feira
Roteiro 11 Segunda-Feira
Roteiro 12 Sexta-Feira
Roteiro\Posição #1 #2 #3 #4 #5 #6 #7 #8 #9
Roteiro 1 C110 C36 C108 C34 C111 C103
Roteiro 2 C15 C37
Roteiro 3 C16 C38 C105
Roteiro 4 C81 C273 C274 C8 C88 C82
Roteiro 5 C13 C14 C106 C70 C73
Roteiro 6 C109 C35 C107 C75 C72
Roteiro 7 C91
Roteiro 8 C92
Roteiro 9 C93
Roteiro 10 C94
Roteiro 11 C65 C66 C68 C64 C60
Roteiro 12 C58 C61 C74
Roteiro 13 C79 C77 C67 C62 C59
Roteiro 14 C104 C102 C99 C100 C71 C69 C63 C33 C57
Roteiro 15 C86 C9 C12
Roteiro 16 C97 C96 C98 C76
Roteiro 17 C83 C89 C90 C80
Roteiro 18 C84 C78
Roteiro 19 C85
Roteiro 20 C87
Roteiro 21 C11
86
Roteiro 13 Terça-Feira
Roteiro 14 Segunda-Feira
Roteiro 15 Terça-Feira
Roteiro 16 Quarta-Feira
Roteiro 17 Quinta Feira
Roteiro 18 Quinta Feira
Roteiro 19 Segunda-Feira
Roteiro 20 Sexta-Feira
Roteiro 21 Segunda-Feira
Roteiro 22 Terça-Feira
Roteiro 23 Sexta-Feira
Roteiro 24 Quarta-Feira
Roteiro 25 Sexta-Feira
Roteiro 26 Quinta Feira
Roteiro 27 Segunda-Feira
Roteiro 28 Terça-Feira
Roteiro 29 Terça-Feira
Roteiro 30 Quinta Feira
Roteiro 31 Quarta-Feira
Roteiro 32 Segunda-Feira
Roteiro 33 Sexta-Feira
Roteiro 34 Segunda-Feira
Roteiro 35 Segunda-Feira
Roteiro 36 Quinta Feira
Roteiro 37 Segunda-Feira
Roteiro 38 Sexta-Feira
Roteiro 39 Quarta-Feira
Roteiro 40 Terça-Feira
Roteiro 41 Quarta-Feira
Roteiro 42 Terça-Feira
Roteiro 43 Quinta Feira
Tabela 14: Dias de execução dos roteiros sugeridos para o centro de distribuição de Hamar.
Roteiro Dia da
semana
Roteiro 1 Segunda-Feira
Roteiro 2 Quarta-Feira
Roteiro 3 Sexta-Feira
Roteiro 4 Segunda-Feira
Roteiro 5 Segunda-Feira
Roteiro 6 Sexta-Feira
Roteiro 7 Terça-Feira
Roteiro 8 Quarta-Feira
Roteiro 9 Quinta Feira
Roteiro 10 Sexta-Feira
Roteiro 11 Terça-Feira
87
Roteiro 12 Quarta-Feira
Roteiro 13 Quinta Feira
Roteiro 14 Terça-Feira
Roteiro 15 Quinta Feira
Roteiro 16 Terça-Feira
Roteiro 17 Segunda-Feira
Roteiro 18 Terça-Feira
Roteiro 19 Quarta-Feira
Roteiro 20 Sexta-Feira
Roteiro 21 Terça-Feira
Outro fator importante a se considerar na avaliação da solução é a distribuição da
demanda de transporte e de produtos ao longo da semana. Uma solução desbalanceada pode
resultar em uma demanda excessiva de produtos em determinados dias, sobrecarregando a
produção. Além disso, uma vez que se deve dimensionar uma frota pelo pico da demanda de
entrega, a concentração das entregas em determinados dias pode gerar custos adicionais com
um maior número de caminhões necessários para atender a demanda do dia. Entretanto, no caso
estudado neste trabalho, pelo fato do prestador do serviço de transporte ser externo e não cobrar
pelo número de caminhões, mas pela quantidade de produto transportado e pela distância
percorrida, não há impactos em relação ao dimensionamento de frota.
Em casos de desequilíbrios, pode ser de interesse da empresa estudar os dias de entrega
a cada cliente, procurando redistribuí-los ao longo da semana. Como o dia de entrega é algo
normalmente acordado entre o setor comercial da empresa e os clientes, seria necessário,
também, obter consentimentos dos clientes em relação à eventuais mudanças.
Na Figura 33, pode-se visualizar o número de roteiros de entrega realizados em cada dia
da semana para os centros de distribuição de Fredrikstad e Hamar. Já na Figura 34 tem-se a
proporção da demanda total da semana entregues em cada dia da semana. Nota-se que para
ambos os centros de distribuição existe uma preferência por entregas nos dois primeiros dias da
semana (Figura 33). O maior número de roteiros nos dois primeiros dias da semana resulta
também em uma maior parcela de produtos entregues nestes dois dias (Figura 34). Entretanto
ao se analisar a relação da quantidade de produtos entregues ao longo da semana, nota-se que
as disparidades são mais tênues, principalmente para o centro de distribuição de Hamar.
88
Figura 33: Número de roteiros de entrega por dia da semana para Fredrikstad e Hamar.
Fonte: elaborado pelo autor
Figura 34: Distribuição do total de 𝑚2 de vidros entregues ao longo da semana para os centros de distribuição de
Fredrikstad e Hamar.
Fonte: elaborado pelo autor
A preferência dos clientes pelos dois primeiros dias da semana para entregue é algo
esperado na distribuição de vidros. Os clientes preferem receber os produtos no início da
semana e realizar as instalações ao longo da semana.
É importante ressaltar que este desequilíbrio de demanda na solução proposta é similar
ao desequilíbrio encontrado na configuração de entregas atual da empresa e não vem
acarretando grandes problemas em relação à produção. Entretanto, em cenários futuros de maior
demanda total de produtos junto aos fornecedores e em que haja menor flexibilidade de
0
2
4
6
8
10
12
14
Segunda-Feira Terça-Feira Quarta-Feira Quinta-Feira Sexta-Feira
Fredrikstad Hamar
24
,67
%
25
,75
%
13
,99
% 18
,00
%
17
,60
%20
,8%
25
,9%
18
,2%
17
,2%
17
,8%
S E G U N D A -F E I R A
T E R Ç A - F E I R A Q U A R T A - F E I R A Q U I N T A F E I R A S E X T A - F E I R A
Fredrikstad Hamar
89
produção, pode ser interessante para a empresa realizar projetos com a equipe comercial para
buscar a redistribuição de certos clientes que permitam um maior equilíbrio na demanda ao
longo da semana.
7.2. Análise de Sensibilidade
Nos estudos de análise de sensibilidade buscou-se analisar como certos fatores externos
influenciam a solução apresentada pela heurística. Embora nas condições atuais a solução
apresentada tenha previsto a utilização de dois centros de distribuição, com a modificação de
certos parâmetros a solução de melhor resultado apresentada pela heurística pode resultar
na utilização de depósitos diferentes. Busca-se também compreender o impacto da alteração
destes parâmetros no custo total para a empresa.
Dois parâmetros que podem influenciar as soluções foram escolhidos para a análise de
sensibilidade:
Aumento no custo transporte (custo de deslocamento entre pontos);
Redução dos custos de utilização dos depósitos;
7.2.1. Aumento do custo de transporte
O custo de transporte da empresa é definido em contrato celebrado entre a empresa e a
transportadora responsável por executar o serviço. Do ponto de vista da empresa transportadora,
as maiores fontes de custos para ela são a depreciação e manutenção dos caminhões, mão de
obra dos motoristas e gastos com combustíveis. Os contratos firmados possuem duração
limitada e, para sua renovação, existe uma negociação entre Glassolutions e a transportadora,
que procura sempre repassar variações de seus custos.
Suporemos 5 experimentos de aumento do custo de transporte para compreender o impacto
que estes teriam na solução a ser adotada pela empresa e nos custos finais da empresa. Os
experimentos representarão aumento de 10%, 20%, 30%, 40% e 50% nos custos de transporte
da empresa. Os resultados obtidos para cada experimento e cenário considerado são
apresentados nas Tabelas 15 a 19. Importante relembrar que cada cenário corresponde à
abertura de um determinado número de depósitos com o cenário 1 utilizando 1 depósito e o
cenário 5 utilizando obrigatoriamente todos os depósitos candidatos.
90
Tabela 15: Solução obtida para hipótese de aumento de 10% nos custos de transporte.
Centros de Distribuição
Utilizados
Custo total em relação à distribuição
atual corrigida pelo aumento de custos
Cenário 1 Fredrikstad -1,8%
Cenário 2 Fredrikstad, Hamar -6,1%
Cenário 3 Fredrikstad, Hamar, Sandnes -1,9%
Cenário 4 Fredrikstad, Hamar, Sandnes,
Bergen 0,5%
Cenário 5 Fredrikstad, Hamar, Sandnes,
Bergen e Trondheim 2,0%
Tabela 16: Solução obtida para hipótese de aumento de 20% nos custos de transporte.
Aumento de 20%
no custo
transporte
Centros de Distribuição
Utilizados
Custo total em relação à distribuição
atual corrigida pelo aumento de custos
Cenário 1 Fredrikstad -1,8%
Cenário 2 Fredrikstad, Hamar -4,5%
Cenário 3 Fredrikstad, Hamar, Sandnes 0,2%
Cenário 4 Fredrikstad, Hamar, Sandnes,
Bergen -0,2%
Cenário 5 Fredrikstad, Hamar, Sandnes,
Bergen e Trondheim -0,2%
Tabela 17: Solução obtida para hipótese de aumento de 30% nos custos de transporte.
Aumento de 30%
no custo
transporte
Centros de Distribuição
Utilizados
Custo total em relação à distribuição
atual corrigida pelo aumento de custos
Cenário 1 Fredrikstad -2,0%
Cenário 2 Fredrikstad, Hamar -4,6%
Cenário 3 Fredrikstad, Hamar, Sandnes 0,0%
Cenário 4 Fredrikstad, Hamar, Sandnes,
Bergen -0,8%
Cenário 5 Fredrikstad, Hamar, Sandnes,
Bergen e Trondheim -1,5%
91
Tabela 18: Solução obtida para hipótese de aumento de 30% nos custos de transporte.
Aumento de 40%
no custo
transporte
Centros de Distribuição
Utilizados
Custo total em relação à distribuição
atual corrigida pelo aumento de custos
Cenário 1 Fredrikstad -2,0%
Cenário 2 Fredrikstad, Hamar -4,7%
Cenário 3 Fredrikstad, Hamar, Sandnes -0,2%
Cenário 4 Fredrikstad, Hamar, Sandnes,
Bergen -1,2%
Cenário 5 Fredrikstad, Hamar, Sandnes,
Bergen e Trondheim -3,2%
Tabela 19: Solução obtida para hipótese de aumento de 50% nos custos de transporte.
Aumento de 50% no custo
transporte
Centros de Distribuição Utilizados
Custo total em relação à distribuição atual corrigida pelo aumento de custos
Cenário 1 Fredrikstad -1,8%
Cenário 2 Fredrikstad, Hamar -4,8%
Cenário 3 Fredrikstad, Hamar, Sandnes -0,3%
Cenário 4 Fredrikstad, Hamar, Sandnes,
Bergen -1,7%
Cenário 5 Fredrikstad, Hamar, Sandnes,
Bergen e Trondheim -4,6%
Para todos os experimentos o cenário 2 com a utilização de dois centros de utilização
continuou sendo aquele que representa maiores ganhos à empresa com economias entre 4,5%
e 6,1% em relação ao modelo atual da empresa corrigido pelo aumento nos custos de transporte
considerados nos experimentos.
É importante ressaltar, entretanto, que a partir de aumentos de 20% nos custos de transportes
internos na Noruega, os cenários 4 e 5, com a abertura de 4 e 5 centros de distribuição, surgem
como alternativas lucrativas para a empresa. Nestes cenários, por utilizar-se um maior número
de depósitos e, assim, estar mais próximos aos clientes, obtêm-se um menor custo de transporte
na Noruega. Entretanto, a utilização de um maior número de depósitos com a ativação inclusive
de depósitos de altos custos de utilização, eleva os custos totais da distribuição. Com o aumento
da importância dos custos de transportes na Noruega os efeitos dos custos de utilização desses
depósitos são diminuídos, transformando-os em soluções positivas ao problema.
92
De fato, com um aumento de 10% nos custos de transporte a solução com 5 depósitos
apresenta um aumento nos custos corrigidos de distribuição de 2,0%. Já com um aumento de
20% nos custos de distribuição temos uma redução nos custos de distribuição em 0,2% com a
utilização de todos os depósitos.
Entretanto, a solução com utilização de dois centros de distribuição continua como a de
melhor resultado para todos os experimentos realizados. Na Figura 35 pode-se ver o efeito do
aumento dos custos de transporte nos ganhos totais obtidos com cada cenário para os diferentes
experimentos realizados. Uma variação do custo total positiva significa que existe aumento do
custo total de distribuição, enquanto que valores negativos representam economias.
A mudança de patamar vista nos cenários 2 e 3 ao se passar do experimento de aumento de
10% nos custos para o experimento de aumento de 20% nos custos deve-se a diferenças na
alocação de clientes causadas pela nova configuração de custos de transportes.
Figura 35 : Variação do custo total de distribuição da solução apresentada em relação ao custo total do modelo
atual corrigido pelo aumento do custo de transporte.
Fonte: elaborado pelo autor
A escolha do cenário 2, com a utilização dos centros de distribuição de Fredrikstad e
Hamar, deixa de ser melhor escolha apenas para o caso de aumento dos custos de transportes
acima de 50%. Dado que aumentos desta magnitude são pouco prováveis, conclui-se que a
solução proposta é estável e não seria impactada por eventuais aumentos no custo de transporte.
93
7.2.2. Redução dos custos de utilização dos depósitos
Os custos de utilização dos depósitos no problema estudado são representados
principalmente por um aumento dos custos de entrega dos fornecedores de produtos (fábricas
fora da Noruega) e por uma compensação à transportadora proprietária do depósito pela
utilização do espaço. Em outros contextos este custo de utilização poderia representar, por
exemplo, os custos fixos do depósito e os custos para se operar o depósito (mão de obra,
consumo de energia e etc.).
Estes custos interferem diretamente na solução escolhida uma vez que o custo total de
distribuição considerado na escolha da solução é composto pelo custo de transporte e pelo custo
de utilização dos centros de distribuição. Consideraremos novamente 5 experimentos com a
redução em 10%, 20%, 30%, 40% e 50% nos custos de utilização dos centros de distribuição.
Os resultados obtidos são apresentados na Figura 36.
Figura 36: Variação do custo total de distribuição da solução apresentada em relação ao custo total do modelo
atual para os diferentes experimentos realizados.
Fonte: elaborado pelo autor
Os cenários 4 e 5, por empregarem maior número de centros de distribuição, incluindo
depósitos mais distantes dos fornecedores e, consequentemente, com maior custo de utilização,
são os que apresentam maiores variações no custo total ao se reduzir os valores dos custos de
utilização. Com os custos atuais, o cenário 4 e 5 representariam um aumento dos custos de
distribuição em 1,3% e 4,4% respectivamente. Já com uma redução de 50% nos custos de
utilização dos centros de distribuição, estes cenários resultariam em economias de 3,1% e
-12,0%
-10,0%
-8,0%
-6,0%
-4,0%
-2,0%
0,0%
2,0%
4,0%
6,0%
0% 10% 20% 30% 40% 50%
Var
iaçã
o d
o c
ust
o t
ota
l de
dis
trib
uiç
ão
Redução no custo de utilização dos depósitosCenário 1 Cenário 2 Cenário 3 Cenário 4 Cenário 5
94
10,2% em relação à configuração atual, com o cenário 5 passando a ser a melhor solução
apresentada pela heurística.
Entretanto, dado que uma redução de 40% ou mais nos custos de utilização é pouco
provável até mesmo em horizonte de longo prazo, percebe-se que a solução proposta, com a
utilização de dois centros de distribuição, é de fato a mais vantajosa para a empresa.
95
CONCLUSÃO
Este trabalho buscou a construção de uma metodologia de otimização das operações de
distribuição de vidro levando em consideração decisões de localização de centros de
distribuição e de roteirização. Para formulação matemática do problema e resolução exata ou
aproximada do problema utilizou-se de técnicas de pesquisa operacional.
Dado o caráter NP-hard do problema, que inclui diversos níveis de decisão de alta
complexidade, foi necessário encontrar e adaptar heurísticas construtivas que permitissem a
obtenção de soluções de boa qualidade para o problema específico retratado. Utilizou-se, assim,
um algoritmo que permitisse a resolução sequencial do problema definindo quais centros de
distribuição utilizar, quantos e quais clientes alocar a cada depósito, e, finalmente, a
roteirização.
Para a primeira etapa, de resolução do problema de localização e de alocação dos
clientes, utilizou-se um algoritmo inspirado no coeficiente de centralidade utilizado por
Moshref-Javadi e Lee (2016), ponderado por um custo de utilização de cada depósito. Para
considerar também as diferentes combinações possíveis de abertura de depósitos, testou-se
múltiplos cenários com a abertura de diferentes números de depósitos. Dentro de cada cenário
buscou-se utilizar sempre os depósitos de melhor localização e menor custo de utilização. Já
para o problema de roteirização adaptou-se a heurística de inserção conforme descrito por
Solomon (1987), considerando restrições de capacidade dos veículos e de janelas de tempo.
A heurística utilizada permite a resolução do problema de maneira rápida, com poucos
parâmetros de inicialização e é de fácil replicação dentro da empresa. Além disso, a heurística
apresentou resultados de boa qualidade. Para os experimentos de dimensões
reduzidasrealizados e comparados com as respectivas resoluções exatas, encontrou-se soluções
com erro médio de 9,86%. Mais importante que os testes em problemas reduzidos, ao utilizar a
heurística proposta para resolução do problema descrito neste trabalho em suas dimensões reais,
pode-se encontrar soluções que reduzam o custo de distribuição da empresa. Ao se propor a
utilização de dois centros de distribuição, em Hamar e Fredrikstad, pôde-se reduzir os custos
de distribuição da empresa em 5,9%.
Além disso, análises de sensibilidade permitiram validar a estabilidade da solução
proposta perante cenários de mudanças nos custos de transporte e de utilização dos centros de
distribuição.
96
O trabalho também realizou um estudo e padronização das metodologias de
levantamento de dados e de implementação de solução para o contexto da empresa e do
problema estudado. Buscou-se, assim, mapear os cuidados necessários para a realização de um
trabalho de otimização na empresa estudada.
É importante ressaltar que o método heurístico utilizado neste trabalho buscou a
resolução do problema específico da empresa estudada. Deste modo, considerou-se restrições
e premissas específicas para o problema apresentado, não considerando outros fatores que
porventura possam existir em outras empresas e operações.
Os bons resultados obtidos na resolução do problema permitem à empresa considerar a
replicação da metodologia e heurística apresentados neste trabalho em outras operações da
empresa. Glassolutions possui hoje mais de 200 pontos comerciais, de produção e distribuição
em 17 países da Europa. Até a realização deste trabalho não havia esforços de otimização das
operações de distribuição com utilização de pesquisa operacional. Buscar utilizar a mesma
metodologia e heurística aqui apresentado em outras fábricas do grupo poderia, portanto,
apresentar ganhos adicionais importantes para a empresa.
Finalmente, este trabalho permitiu o alinhamento entre as técnicas científicas
apresentadas ao longo do curso de graduação de Engenharia de Produção na Escola Politécnica
da USP, a função dos engenheiros de produção e as necessidades reais das empresas. Ao utilizar
uma metodologia de identificação, reflexão e resolução de problema, com a proposição de uma
solução que represente ganhos à empresa, ressaltou-se a importância da função de engenheiros
de produção, gerando valor e vantagens competitivas para empresas.
97
REFERÊNCIAS BIBLIOGRÁFICAS
AMS CHARIOTS. Agres Verriers. 2016. Disponível em : <http://www.chariot-
verrier.com/agres-verriers/chariots.html>. Acesso em: 24 out. 2016.
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANESSE, H. Pesquisa
Operacional para cursos de engenharia. Rio de Janeiro: Elsevier, 2007.
ARNOLD, J. R. T.; CLIVE, S. N.; CHAPMAN, L. M. Introduction to Materials
Management. Upper Saddle River: Pearson, 2008
BELFIORE, P. P. Scatter Search para problemas de roteirização de veículos com frota
heterogênea, janela de tempo e entregas fracionadas. 2006. 203 p. Dissertação (Doutorado)
– Escola Politécnica, Universidade de São Paulo, São Paulo, 2006.
BELFIORE, P. P.; FAVERO, L. P. L. Problema de roteirização de veículos com entregas
fracionadas: revisão da literatura. In: XIII SIMPEP – Bauru, SP, Brasil, 06 a 08 de novembro
de 2006. Anais do XIII SIMPEP. Barueri: 2006.
BELFIORE, P. P.; YOSHIZAKI, H. T. Y. Heuristic methods for the fleet size and mix vehicle
routing problem with time windows and split deliveries. Computers and Industrial
Engineering, v. 64, n. 2, p. 589-601, 2013.
DASKIN, M. S. Network and Discrete Location: models, algorithms and applications.
Hoboken: John Wiley & Sons, 1995.
DROR, M.; TRUDEAU, P. Split delivery routing. Naval Research Logistics, v. 37, n. 3, p.
383-402, 1990.
FENDER, M.; BARON, F.; Le Supply Chain Management: en 37 fiches-outils. Paris :
Dunod, 2012.
FRIZZELL, P. W.; GIFFIN, J. W. The split delivery vehicle scheduling problem with time
windows and grid network distances. Computers and Operations Research, v. 22, n. 6, p.
655-667, 1995.
GHIANI, G.; LAPORTE, G.; MUSMANNO, R. Introduction to Logistics Systems Planning
and Control. West Sussex: John Wiley & Sons, 2004.
GLASSOLUTIONS. Produits. Disponível em: <http://glassolutions.fr/fr/produits>. Acesso
em: 24 out. 2016.
GOLDEN, B.; RAGHAVAN, S.; WASIL, E. The Vehicle Routing Problem: Latest
Advances and New Challenges. Nova York: Springer, 2008.
KLOSE, A.; DREXL, A. Facility location models for distribution system design. European
Journal of Operational Research, v. 162, n. 1, p. 4-29, 2005.
LENSTRA, J. K.; KAN, A. H. G. R. Complexity of vehicle routing and scheduling problems.
Networks, v. 11, p. 221–227, 1981.
MAST, J.; LOKKERBOL, J. An analysis of the six sigma DMAIC method from the perspective
of problem solving. International Journal of Production Economics, v. 139, n. 2, 2012.
98
MELO, M. T.; NICKEL, S.; SALDANHA-DA-GAMA, F. Facility location and supply chain
management: a review. European Journal of Operational Research, v. 196, n. 2, p. 401-412,
2009.
MIN, H.; JAYARAMAN, V.; SRIVASTAVA, R. Combined location-routing problems: A
synthesis and future research directions. European Journal of Operational Research, v. 108,
n. 1, p. 1-15, 1998.
MOSHREF-JAVADI, M.; LEE, S. The Latency Location-Routing Problem. European
Journal of Operational Research, v. 255, n. 2, p. 604-619, 2016.
NAGY, G.; SALHI, S. Location-routing: issues, models and methods. European Journal of
Operational Research, v. 177, n. 2, p. 649-672, 2007.
OWEN, S. H.; DASKIN, M. S. Strategic facility location: A review. European Journal of
Operational Research, v. 111, n. 3, p. 423-447, 1998.
POLAND CENTRAL STATISTICAL OFFICE. Employment, wages and salaries in
national economy in first quarter 2016. Warszawa: 2016.
REVELLE, C. S.; EISELT, H. A. Location analysis: A synthesis and survey. European
Journal of Operational Research, v. 165, n. 1, p. 1-19, 2005.
RONCONI, D. P.; MANGUINO, J. L. V. Heurísticas construtivas para o problema de
roteamento de veículos com custos escalonados. In: XLVIII SBPO – Vitória, ES, Brasil, 27 a
30 de setembro de 2016. Anais do XLVIII Simpósio Brasileiro de Pesquisa Operacional.
Rio de Janeiro: SOBRAPO - Sociedade Brasileira de Pesquisa Operacional, v. 1., p. 1-11, 2016.
SAINT-GOBAIN. Document de référence 2015 incluant le rapport financier annuel et le
rapport de responsabilité sociale d'entreprise. 2015a. Disponível em: <https://www.saint-
gobain.com/sites/sgcom.master/files/saint-gobain_drf_2015_vf.pdf>. Acesso em: 24 out. 2016.
SAINT-GOBAIN. Building Glass Europe: Enter the customer perspective. 2015b.
Documento interno da empresa. Não Publicado.
SAINT-GOBAIN. Mémento. 2015. Disponível em: <http://ememento.saint-gobain-
glass.com/app/webroot/img/assets/24/products/pdffiles/24_1429713683_1.pdf>. Acesso em:
24 out. 2016.
SAINT-GOBAIN SEKURIT. Photo Library. 2016. Disponível em:< http://www.saint-
gobain-sekurit.com/photolibrary#prettyPhoto>. Acesso em: 24 out. 2016.
SCHROEDER, R. G.; LINDERMAN, K.; LIEDTKE, C.; CHOO, A. S. Six Sigma: Definition
and underlying theory. Journal of Operations Management, v. 26, n. 4, p. 536-554, 2008.
SEHGAL, S.; SAHAY, B.; GOYAL, S.; Reengineering the supply chain in a paint company.
International Journal of Productivity and Performance Management, v. 55, n.8, pp.655 –
670, 2006.
SILVER, E. A. An Overview of Heuristic Solution Methods. The Journal of the Operational
Research Society, v. 55, n. 9, p. 936-956, 2004.
SOLOMON, M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time
Window Constraints. Operations Research, v. 35, n. 2, p. 254-265, 1987
99
SRIVASTAVA, R. BENTON, W. C. The location-routing problem: considerations in physical
distribution system design. Computers and Operations Research, v. 17, n. 5, p. 427-435,
1990.
STATISTISK SENTRALBYRA. Earnings of all employees. 2015a. Disponível
em:<https://www.ssb.no/en/arbeid-og-lonn/statistikker/lonnansatt/aar/2016-03-
03?fane=tabell&sort=nummer&tabell=258764>. Acesso em: 24 out. 2016.
STATISTISK SENTRALBYRA. Population and land area in urban settlements, 1 January
2015. 2015b. Disponível em: <https://www.ssb.no/en/befolkning/statistikker/beftett>. Acesso
em: 24 out. 2016.
ZANAKIS, S. H.; EVANS, J. R.; VAZACOPOULOS, A. A. Heuristic methods and
applications: A categorized survey. European Journal of Operational Research, v. 43, n. 1,
p. 88-110, 1989.
101
APÊNDICE A – FICHA DE LEVANTAMENTO DE INFORMAÇÕES
Ficha de levantamento de
informações de entrega
Informações sobre o Cliente
Nome do Cliente:
Endereço:
Contato:
(Telefone, e-mail, nome
do contato)
Informações de Entrega
Modo de descarregamento:
Tipo de cavalete requisitado:
Dias e horários de entrega:
Recebido por Glassolutions: Recebido pelo cliente:
Nome: Nome:
Data: Data:
Assinatura: Assinatura:
Ponte
Plataforma elevadora
Empilhadeira
Outro:
Palete
Cavalete
Cavalete com rodas
Outro:
Informar horário e dias da semana possíveis de entrega:
103
APÊNDICE B – MODELAGEM DO PROBLEMA EM CPLEX OPL
/*********************************************
* OPL 12.6.0.0 Model
* Author: Giordano
* Creation Date: 11/09/2016 at 10:51:55
*********************************************/
// parâmetros
int n=...; // numero de veiculos
int m=... ;// numero de clientes
int w=...;// numero de centros de distribuição
range veiculos=1..n;
range clientes=1..m;
// range clientes2 exclui os CD (cliente=1, 2, 3, 4, 5) para fazer funcionar as restrições de janela de tempo
range clientes2=6..m;
range CD = 1..w;
// define os roteiros ligados a cada centro de distribuição
range CD1 = 1..8;
range CD2 = 9..16;
range CD3 = 17..24;
range CD4 = 25..32;
range CD5 = 33..40;
float demanda[clientes]=...;
float duracao_entrega[clientes]=...;
float capacidade[veiculos]=...;
float cost[clientes][clientes]=...;
float tempo_entre_clientes[clientes][clientes]=...;
float Horario_visita_1[clientes]=...;
float Horario_visita_2[clientes]=...;
float CF[CD];
int Frequencia[clientes]=...;
//variaveis
// 1 se o cliente i é atendido apos o cliente j pela rota v
dvar int x[veiculos][clientes][clientes]in 0..1 ;
//1 se a rota v atende o cliente i
dvar int y[veiculos][clientes] in 0..1;
// se a rota V existe
dvar int V[veiculos] in 0..1;
// variavel sobre os centros de distribuicao
dvar int z[CD] in 0..1;
//Tempo de inicio de atendimento
dvar int+ T[clientes];
//Me diz quantos m2 de produto cada CD distribuiu
dvar int+ G[CD];
//FO
minimize sum(v in veiculos, i in clientes, j in clientes)x[v][i][j]*cost[i][j] + CF[1]*z[1] + CF[2]*z[2] +
CF[3]*z[3] + CF[4]*z[4] + CF[5]*z[5];
subject to{
// restrição 2: estabelece se o roteito Vv existe ou não (1 ou 0)
cons2:
forall(v in veiculos)
104
100000*V[v]>= sum(i in clientes, j in clientes)x[v][i][j];
// restrição 3: estabelece que se uma rota existe, ela deve partir do seu respectivo CD
cons3_1:
forall(v in CD1)
sum(j in clientes2)x[v][1][j] - V[v] == 0;
cons3_2:
forall(v in CD2)
sum(j in clientes2)x[v][2][j] - V[v] == 0;
cons3_3:
forall(v in CD3)
sum(j in clientes2)x[v][3][j] - V[v] == 0;
cons3_4:
forall(v in CD4)
sum(j in clientes2)x[v][4][j] - V[v] == 0;
cons3_5:
forall(v in CD5)
sum(j in clientes2)x[v][5][j] - V[v] == 0;
//Garante a conservação dos fluxos de entrada e saída dos nós
cons4:
forall(v in veiculos)
forall(p in clientes)
sum(i in clientes)x[v][i][p] - sum(j in clientes)x[v][p][j] == 0;
//determinação dos clientes que são entregues pelo roteiro v
cons5:
forall(v in veiculos, i in clientes)
y[v][i] == sum(j in clientes)x[v][j][i];
//resrição 6: Impõe o horário mínimo de atendimento de um cliente que é dado pela soma do horário de
atendimento do cliente anterior, do tempo de atendimento do cliente anterior e pelo tempo de percurso entre os
dois clientes.
//range clientes2 exclui o CD
cons6:
forall(i in clientes2, j in clientes)
T[i] + duracao_entrega[i] + tempo_entre_clientes[i][j] - (100000*(1-sum(v in veiculos)x[v][i][j])) <= T[j];
//restrição7: Garante que o horário de atendimento de um cliente i estará dentro de sua janela de tempo pré-
determinada.
cons7:
forall (i in clientes)
Horario_visita_1[i]<= T[i];
cons7_1:
forall (i in clientes)
T[i] <= Horario_visita_2[i];
//restrição8: Garante que cada cliente é visitado uma vez pelos roteiros (não pode haver repetições dentro de um
mesmo roteiro)
cons8:
forall(v in veiculos)
forall(i in clientes)
sum (j in clientes)x[v][i][j] == 1;
105
//restrição9: Garante que a capacidade de cada veículo (roteiro) não será excedida.
cons9:
forall(v in veiculos)
sum(i in clientes)demanda[i]*y[v][i] <= capacidade[v];
//restrição10: estabelece a relação de existência entre os roteiros e os centros de distribuição. Um roteiro de um
determinado centro de distribuição só pode existir se o referido centro de distribuição também existir.
cons10_1:
forall(i in CD1)
1000*z[1] >= V[i];
cons10_2:
forall(i in CD2)
1000*z[2] >= V[i];
cons10_3:
forall(i in CD3)
1000*z[3] >= V[i];
cons10_4:
forall(i in CD4)
1000*z[4] >= V[i];
cons10_5:
forall(i in CD5)
1000*z[5] >= V[i];
}
/*********************************************
* OPL 12.6.0.0 Data
* Author: Giordano
* Creation Date: 11/09/2016 at 10:51:55
*********************************************/
n=40;
// 35 clientes + 5 CD
m=40;
w=5;
SheetConnection my_sheet("Data_Noruega.xlsm");
demanda from SheetRead(my_sheet, "Demanda");
duracao_entrega from SheetRead(my_sheet, "Duracao_entrega");
capacidade from SheetRead(my_sheet, "Capacidade");
Horario_visita_1 from SheetRead(my_sheet, "Horario_visita_1");
Horario_visita_2 from SheetRead(my_sheet, "Horario_visita_2");
Frequencia from SheetRead(my_sheet, "frequencia");
cost from SheetRead(my_sheet, "Cost");
CF from SheetRead(my_sheet, "CF");
tempo_entre_clientes from SheetRead(my_sheet, "Tempo_entre_clientes");
107
APÊNDICE C – CÓDIGO DA HEURÍSTICA EM VBA
Encontra-se, a seguir, a codificação do problema em linguagem VBA -Visual Basics for
Aplications. Dado a grande extensão do código e a repetição de certas estruturas do código,
decidiu-se expor nesta seção apenas parte do código total. Tem-se, portanto, a estrutura do
código para inicialização e resolução do problema para o cenário 1, com utilização de 1 centro
de distribuição, e cenário 2, com utilização de dois centros de distribuição.
Para os cenários 3, 4 e 5 que não estão expostos aqui, utiliza-se da mesma estrutura de
código, adaptando-se apenas em relação ao número de centros de distribuição utilizados.
INÍCIO DO CÓDIGO
Sub HeuristicaOtimizacaoDeRotas()
'trava a tela
Application.ScreenUpdating = False
'número de clientes n = 284
Const n = 284
'números de CD
Const w = 5
'Capacidade caminhão
Const capacidade = 150
'Numero de clientes por roteiro
Const p = 100
'contadores lógicos
Dim i As Integer
Dim j As Integer
Dim g As Integer
Dim icounter As Integer
Dim cont As Integer
Dim condicao As Integer
‘CD aberto
Dim abrir1, abrir2, abrir3, abrir4, abrir5 As Integer
'coeficiente de centralidade
Dim cent(w) As Double
'coeficiente de utilização do depósito
Dim coefCU(w) As Double
'coeficiente de abertura de depósito
coefAD(w) As Double
'me diz se o CD ja foi aberto
Dim CDaberto(w) As Integer
'custo fixo do CD g
Dim CF(w) As Integer
108
Dim cost(n + w, n + w) As Integer
'custo de cada CD para cada cliente
Dim CostAbrir1ToClient(n) As Integer
Dim CostAbrir2ToClient(n) As Integer
Dim CostAbrir3ToClient(n) As Integer
Dim CostAbrir4ToClient(n) As Integer
Dim CostAbrir5ToClient(n) As Integer
Dim demanda(n + w) As Double
'Me indica de o cliente i já esta alocado no cenario estudado
Dim ClienteEscolhido(n + w) As Integer
'se o CD w esta aberto (1) ou fechado (0) em cada um dos 5 cenarios
Dim CD(5, w) As Integer
'numero de clientes direcionados ao CD(i) em cada um dos 5 cenarios
Dim Clientes(5, w) As Integer
'se o cliente n é atendido pelo CD w no cenario em que tenho w CDs aberto
Dim Z(w, w, n) As Integer
'media dos valores de centg
Dim mediag As Double
Dim lngPos As Long
'Variaveis relacionados à roteirização
'roteiro
Dim V(5, w, p, n + w) As Integer
Dim CapacidadeDisponivel As Integer
Dim NumVeiculo As Integer
Dim u As Integer
Dim C1antigo As Double
Dim C1novo As Double
Dim C2(n + w) As Double
Dim Posicao(n + w) As Integer
Dim SemCapacidade As Integer
Dim rotas As Integer
Dim Custosuplementar(n + w) As Double
Dim TamRoteiro As Integer
Dim PotencialEntrar(n + w) As Integer
Dim Sair As Integer
Dim CostAbrir1ToClient2(n + w)
Dim CustoTotal As Double
'horario de inicio e fim de atendimento
Dim horario_inicio_atendimento(n + w) As Double
Dim horario_fim_atendimento(n + w) As Double
Dim tempo_inicio_roteiro(p) As Double
Dim tempo_fim_roteiro(p) As Double
Dim DuracaoRoteiro(p) As Double
Dim T(n + w, n + w) As Double
Dim Lmin As Double
Const JornadaMax = 1440
Dim PFnovo As Double
Dim PF(n + w) As Double
'trava a tela
Application.ScreenUpdating = False
'Inicialização dos valores
For i = 1 To w
109
For j = 1 To 5
CD(j, i) = 0
Next j
Next i
For i = 1 To w
For j = 1 To 5
Clientes(j, i) = 0
Next j
Next i
For i = 1 To n
ClienteEscolhido(i) = 0
Next i
'leitura dos valores de custo de deslocamento entre nós
Worksheets("Cost").Activate
Range("B2").Activate
'lê a linha
For i = 1 To (n + w)
'lê a coluna
For j = 1 To (n + w)
cost(i, j) = ActiveCell
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
'vai para a primeira coluna da linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
'leitura dos valores de tempo de deslocamento entre nós
Worksheets("Tempo entre clientes").Activate
Range("B2").Activate
'lê a linha
For i = 1 To (n + w)
'lê a coluna
For j = 1 To (n + w)
T(i, j) = ActiveCell
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
'vai para a primeira coluna da linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
'leitura dos valores de demanda
Worksheets("Demanda").Activate
Range("B2").Activate
'lê a linha
For i = 1 To (n + w)
demanda(i) = ActiveCell
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'leitura dos valores de horario inicio atendimento
Worksheets("Horario_visita1").Activate
Range("B1").Activate
'lê a linha
For i = 1 To (n + w)
110
horario_inicio_atendimento(i) = ActiveCell
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'leitura dos valores de horario fim atendimento
Worksheets("Horario_visita2").Activate
Range("B1").Activate
'lê a linha
For i = 1 To (n + w)
horario_fim_atendimento(i) = ActiveCell
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'leitura dos valores de coeficiente de abertura de depósito
Worksheets("Coeficiente Utilização").Activate
Range("B1").Activate
'lê a linha
For i = 1 To (w)
coefAD(i) = ActiveCell
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
coefCU (w)
'--------------------------------- CENARIO COM 1 CD ABERTO -----------------------------------------------
------
'calcula valores de coeficiente de centralidade para os depósitos
For g = 1 To w
For i = (w + 1) To (n + w)
cent(g) = cent(g) + (1 / (1 + cost(g, i)))
Next i
Next g
'calcula valores do coeficiente de abertura de depósito
For g = 1 To w
coefAD(g) = cent(g) * (1 - coefCU(g))
Next g
'identifica qual o CD com maior cent
g = 1
Do Until g > w
If coefAD(g) = Application.WorksheetFunction.Large(coefAD, 1) Then
abrir1 = g
Exit Do
End If
g = g + 1
Loop
'Abre o CD de maior Cent
CD(1, abrir1) = 1
'alocação de clientes
Clientes(1, abrir1) = n
'array com os custos de cada CD que abri
For i = 1 To n
CostAbrir1ToClient(i) = cost(abrir1, i + w)
111
Next i
'alocação de clientes ao CD1
For i = 1 To Clientes(1, abrir1)
j = w + 1
Do Until j = n + w + 1
If cost(abrir1, j) = Application.WorksheetFunction.Large(CostAbrir1ToClient, n + 1 - i) And
ClienteEscolhido(j) = 0 Then
Z(1, abrir1, i) = j
ClienteEscolhido(j) = 1
Exit Do
End If
j = j + 1
Loop
Next i
'ROTEIRIZACAO
NumVeiculo = 1
rotas = 1
Do Until rotas = 0
'veiculo sai do CD
V(1, abrir1, NumVeiculo, 0) = abrir1
'ETAPA 1
'identificar qual o cliente mais longe do CD aberto que ainda não foi servido e inicio a contruir
minha rota passando por ele
Sair = 0
j = w + 1
Do Until Sair = 1
If cost(abrir1, j) = Application.WorksheetFunction.Large(CostAbrir1ToClient, 1) And
ClienteEscolhido(j) = 1 Then
V(1, abrir1, NumVeiculo, 1) = j
V(1, abrir1, NumVeiculo, 2) = abrir1
'marca que o cliente foi servido
ClienteEscolhido(j) = 0
'calcula o espaço livre no caminhão
CapacidadeDisponivel = capacidade - demanda(j)
'tamanho do roteiro com 1 cliente
TamRoteiro = 2
Sair = 1
CostAbrir1ToClient(j - w) = 0
'estabelece o inicio e o fim maximo do roteiro
tempo_inicio_roteiro(NumVeiculo) = horario_inicio_atendimento(j)
tempo_fim_roteiro(NumVeiculo) = horario_fim_atendimento(j)
'estabelece a duracao do roteiro e quanto tempo ha disponivel na jornada de trabalho
DuracaoRoteiro(NumVeiculo) = T(abrir1, j)
Lmin = JornadaMax - DuracaoRoteiro(NumVeiculo)
End If
j = j + 1
Loop
'Verifica se com a inserção de cliente que acabou de fazer ja atende a todos os clientes
SemCapacidade = 1
For i = w + 1 To n + w
112
If ClienteEscolhido(i) = 1 Then
SemCapacidade = 0
End If
Next i
Do Until SemCapacidade = 1
'-------ETAPA 2
'Identifica os clientes com potencial para entrar
For j = (w + 1) To (n + w)
If CapacidadeDisponivel - demanda(j) > 0 And ClienteEscolhido(j) = 1 And
horario_inicio_atendimento(j) >= tempo_inicio_roteiro(NumVeiculo) And
horario_inicio_atendimento(j) <= tempo_fim_roteiro(NumVeiculo) Then
PotencialEntrar(j) = 1
Else
PotencialEntrar(j) = 0
End If
Next j
'-------ETAPA 3
'calcula c1 e a melhor posição para inserir cada cliente candidato na rota
For u = (w + 1) To (n + w)
If PotencialEntrar(u) = 1 Then
i = 1
C1antigo = 10000000
PotencialEntrar(u) = 0
For i = 1 To TamRoteiro
C1novo = cost(V(1, abrir1, NumVeiculo, i - 1), u) + cost(u, V(1, abrir1, NumVeiculo, i)) -
cost(V(1, abrir1, NumVeiculo, i - 1), V(1, abrir1, NumVeiculo, i))
PFnovo = T(V(1, abrir1, NumVeiculo, i - 1), u) + T(u, V(1, abrir1, NumVeiculo, i)) -
T(V(1, abrir1, NumVeiculo, i - 1), V(1, abrir1, NumVeiculo, i))
If C1novo < C1antigo And PFnovo < Lmin Then
Custosuplementar(u) = C1novo
PF(u) = PFnovo
Posicao(u) = i
PotencialEntrar(u) = 1
End If
C1antigo = C1novo
Next i
End If
Next u
'-------ETAPA 4
'calcula c2 e identifica qual cliente adicionar ao roteiro
'inicialização dos valores
C2(0) = -100000000
C2(1) = -100000000
C2(2) = -100000000
C2(3) = -100000000
C2(4) = -100000000
C2(5) = -100000000
For u = 5 To n + w
C2(u) = 0
Next u
113
For u = (w + 1) To (n + w)
If ClienteEscolhido(u) = 1 And PotencialEntrar(u) = 1 Then
C2(u) = cost(abrir1, u) - Custosuplementar(u)
Else
C2(u) = -100000000
End If
Next u
'Verifica se há capacidade para adicionar um cliente e se é de interesse adicionar este cliente ou
iniciar um novo roteiro
SemCapacidade = 1
For i = w + 1 To n + w
If CapacidadeDisponivel > demanda(i) And ClienteEscolhido(i) = 1 And PotencialEntrar(i)
= 1 And C2(i) > 0 Then
SemCapacidade = 0
End If
Next i
If SemCapacidade = 1 Then
NumVeiculo = NumVeiculo + 1
End If
'Se há capacidade disponível, e existe um cliente com C2>0, insere este cliente no roteiro, se não,
sai do Loop e inicia um novo roteiro
If SemCapacidade = 0 Then
Sair = 0
u = w + 1
Do Until Sair = 1
'For u = (w + 1) To (n + w)
If C2(u) = Application.WorksheetFunction.Large(C2, 1) And ClienteEscolhido(u) = 1 Then
TamRoteiro = TamRoteiro + 1
'Insere o cliente no roteiro e na Posicao(u). Adiciona mais um espaço (slot) no roteiro para
poder adicionar o novo cliente
i = TamRoteiro
'abre espaço para o cliente u
Do Until i = Posicao(u)
V(1, abrir1, NumVeiculo, i) = V(1, abrir1, NumVeiculo, i - 1)
i = i - 1
Loop
'insere cliente u na posicao(u)
V(1, abrir1, NumVeiculo, Posicao(u)) = u
CapacidadeDisponivel = CapacidadeDisponivel - demanda(u)
DuracaoRoteiro(NumVeiculo) = DuracaoRoteiro(NumVeiculo) + PF(u)
Lmin = JornadaMax - DuracaoRoteiro(NumVeiculo)
'atualiza o tempo de fim maximo e de inicio minimo do meu roteiro
If horario_fim_atendimento(u) < tempo_fim_roteiro(NumVeiculo) Then
tempo_fim_roteiro(NumVeiculo) = horario_fim_atendimento(u)
End If
If horario_inicio_atendimento(u) > tempo_inicio_roteiro(NumVeiculo) Then
tempo_inicio_roteiro(NumVeiculo) = horario_inicio_atendimento(u)
End If
ClienteEscolhido(u) = 0
CostAbrir1ToClient(u - w) = 0
Sair = 1
End If
u = u + 1
114
Loop
End If
Loop
'Verifica se há algum cliente não alocado. Se não tiver, mantem rotas = 0 e sai do loop.
rotas = 0
For i = w + 1 To n + w
If ClienteEscolhido(i) = 1 Then
rotas = 1
End If
Next i
Loop
'----------------------------Calcula Custo Distribuição
CustoTotal = 0
For NumVeiculo = 1 To 50
For i = 1 To n
CustoTotal = CustoTotal + cost(V(1, abrir1, NumVeiculo, i - 1), V(1, abrir1, NumVeiculo, i))
Next i
Next NumVeiculo
'-------------------------------------- Resultados Cenario 1 CD ---------------------------------------------
Worksheets("Resultados 1 CD").Activate
Range("G1").Activate
ActiveCell = CustoTotal
Range("B2").Activate
For i = 1 To (w)
ActiveCell = cent(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
Range("C2").Activate
For i = 1 To (w)
ActiveCell = CD(1, i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
Range("D2").Activate
For i = 1 To (w)
ActiveCell = Clientes(1, i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
Range("B11").Activate
For i = 1 To w
For j = 1 To n
ActiveCell = Z(1, i, j)
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
115
'vai para linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
'imprime roteiros
Range("A21").Activate
ActiveCell = abrir1
Range("B22").Activate
For i = 1 To p
For j = 1 To 30
ActiveCell = V(1, abrir1, i, j)
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
'vai para linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
Range("AF22").Activate
For i = 1 To p
ActiveCell = tempo_inicio_roteiro(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
Range("AG22").Activate
For i = 1 To p
ActiveCell = tempo_fim_roteiro(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'------------------------------------- CENARIO COM 2 CD ABERETOS ----------------------------------------
-----
'inicializa cliente escolhido do cenario
For i = 1 To n + w
ClienteEscolhido(i) = 0
Next i
'inicializa os cd
For i = 1 To w
CDaberto(i) = 0
Next i
'identifica primeiro CD a abrir
g = 1
Do Until g > w
If coefAD(g) = Application.WorksheetFunction.Large(coefAD, 1) And CDaberto(g) = 0 Then
abrir1 = g
CDaberto(g) = 1
Exit Do
End If
g = g + 1
Loop
'identifica segundo CD a abrir
g = 1
Do Until g > w
If coefAD(g) = Application.WorksheetFunction.Large(coefAD, 2) And CDaberto(g) = 0 Then
abrir2 = g
116
CDaberto(g) = 1
Exit Do
End If
g = g + 1
Loop
'Abre os CDs de maior Cent
CD(2, abrir1) = 1
CD(2, abrir2) = 1
'Identifica quantos clientes vou alocar a cada CD
Clientes(2, abrir1) = (cent(abrir1) * n) / (cent(abrir1) + cent(abrir2))
Clientes(2, abrir2) = (cent(abrir2) * n) / (cent(abrir1) + cent(abrir2))
'array com os custos de cada CD que abri
For i = 1 To n
CostAbrir1ToClient(i) = cost(abrir1, i + w)
CostAbrir2ToClient(i) = cost(abrir2, i + w)
Next i
'identifica quais clientes serão entregues pelo CD(abrir1)
For i = 1 To Clientes(2, abrir1)
j = w + 1
Do Until j > (n + w)
If cost(abrir1, j) = Application.WorksheetFunction.Large(CostAbrir1ToClient, n + 1 - i) And
ClienteEscolhido(j) = 0 Then
Z(2, abrir1, i) = j
ClienteEscolhido(j) = 1
Exit Do
End If
j = j + 1
Loop
Next i
'identifica quais clientes serão entregues pelo CD(abrir2)
icounter = 1
i = 1
'Analisa todos os clientes à procura do cliente j que possui o icounter de menor custo de trajeto do
CD2
Do Until i > Clientes(2, abrir2)
j = w + 1
condicao = 0
Do Until j > n + w
If cost(abrir2, j) = Application.WorksheetFunction.Large(CostAbrir2ToClient, n + 1 - icounter)
Then
'Se encontrou este cliente e ele já estiver alocado, começa a procurar desde o inicio (j=w) o
cliente n-1 custo
If ClienteEscolhido(j) = 1 Then
'varre o restante dos custos para ver se tem valor igual, impedindo que ignore dois custos com
mesmo valor
For cont = j + 1 To n + w
If cost(abrir2, j) = cost(abrir2, cont) Then
If ClienteEscolhido(cont) = 0 Then
condicao = 1
End If
117
End If
Next cont
If condicao = 0 Then
icounter = icounter + 1
Exit Do
End If
'se o cliente não estiver alocado, aloca ele ao CD e vou para o proximo i
Else
Z(2, abrir2, i) = j
ClienteEscolhido(j) = 1
i = i + 1
icounter = icounter + 1
Exit Do
End If
End If
j = j + 1
Loop
Loop
'atualiza os array com os custos de cada CD aberto para os clientes alocados a estes CDs
For i = 1 To Clientes(2, abrir1)
CostAbrir1ToClient(i) = cost(abrir1, Z(2, abrir1, i))
Next i
For i = Clientes(2, abrir1) + 1 To n
CostAbrir1ToClient(i) = 0
Next i
For i = 1 To Clientes(2, abrir2)
CostAbrir2ToClient(i) = cost(abrir2, Z(2, abrir2, i))
Next i
For i = Clientes(2, abrir2) + 1 To n
CostAbrir2ToClient(i) = 0
Next i
'----------- ROTEIRIZACAO PRIMEIRO CD - CENARIO 2-----------
'inicializa tempos de atendimento dos roteiros
For i = 1 To p
tempo_inicio_roteiro(i) = 0
tempo_fim_roteiro(i) = 0
DuracaoRoteiro(i) = 0
Next i
'roteiro de cada cenario, para cada CD, para n clientes, n ordem de clientes dentro do roteiro
NumVeiculo = 1
rotas = 1
Do Until rotas = 0
'veiculo sai do CD
V(2, abrir1, NumVeiculo, 0) = abrir1
'ETAPA 1
118
'identificar qual o cliente mais longe do CD aberto que ainda não foi servido e inicio a contruir rota
passando por este cliente
Sair = 0
j = 1
Do Until Sair = 1
If cost(abrir1, Z(2, abrir1, j)) = Application.WorksheetFunction.Large(CostAbrir1ToClient, 1)
And ClienteEscolhido(Z(2, abrir1, j)) = 1 Then
V(2, abrir1, NumVeiculo, 1) = Z(2, abrir1, j)
V(2, abrir1, NumVeiculo, 2) = abrir1
'marca que o cliente foi servido
ClienteEscolhido(Z(2, abrir1, j)) = 0
'calcula o espaço livre no caminhão
CapacidadeDisponivel = capacidade - demanda(Z(2, abrir1, j))
'tamanho do roteiro com 1 cliente
TamRoteiro = 2
Sair = 1
CostAbrir1ToClient(j) = 0
'estabelece o inicio e o fim maximo do roteiro
tempo_inicio_roteiro(NumVeiculo) = horario_inicio_atendimento(Z(2, abrir1, j))
tempo_fim_roteiro(NumVeiculo) = horario_fim_atendimento(Z(2, abrir1, j))
'estabelece a duracao do roteiro e quanto tempo ha disponivel na jornada de trabalho
DuracaoRoteiro(NumVeiculo) = T(abrir1, Z(2, abrir1, j))
Lmin = JornadaMax - DuracaoRoteiro(NumVeiculo)
End If
j = j + 1
Loop
'Verifica se com a inserção de cliente que acaba-se de fazer ja atende a todos os clientes
SemCapacidade = 1
For i = 1 To Clientes(2, abrir1)
If ClienteEscolhido(Z(2, abrir1, i)) = 1 Then
SemCapacidade = 0
End If
Next i
Do Until SemCapacidade = 1
'-------ETAPA 2
'Identifica os clientes com potencial para entrar
For j = 1 To Clientes(2, abrir1)
If CapacidadeDisponivel - demanda(Z(2, abrir1, j)) > 0 And ClienteEscolhido(Z(2, abrir1, j)) =
1 And horario_inicio_atendimento(Z(2, abrir1, j)) >= tempo_inicio_roteiro(NumVeiculo) And
horario_inicio_atendimento(Z(2, abrir1, j)) <= tempo_fim_roteiro(NumVeiculo) Then
PotencialEntrar(Z(2, abrir1, j)) = 1
Else
PotencialEntrar(Z(2, abrir1, j)) = 0
End If
Next j
'-------ETAPA 3
'calcula c1 e a melhor posição para inserir cada cliente candidato na rota
For u = 1 To Clientes(2, abrir1)
If PotencialEntrar(Z(2, abrir1, u)) = 1 Then
i = 1
C1antigo = 10000000
PotencialEntrar(Z(2, abrir1, u)) = 0
119
For i = 1 To TamRoteiro
C1novo = cost(V(2, abrir1, NumVeiculo, i - 1), Z(2, abrir1, u)) + cost(Z(2, abrir1, u), V(2,
abrir1, NumVeiculo, i)) - cost(V(2, abrir1, NumVeiculo, i - 1), V(2, abrir1, NumVeiculo, i))
PFnovo = T(V(2, abrir1, NumVeiculo, i - 1), Z(2, abrir1, u)) + T(Z(2, abrir1, u), V(2,
abrir1, NumVeiculo, i)) - T(V(2, abrir1, NumVeiculo, i - 1), V(2, abrir1, NumVeiculo, i))
If C1novo < C1antigo And PFnovo < Lmin Then
Custosuplementar(Z(2, abrir1, u)) = C1novo
Posicao(Z(2, abrir1, u)) = i
PF(Z(2, abrir1, u)) = PFnovo
PotencialEntrar(Z(2, abrir1, u)) = 1
End If
C1antigo = C1novo
Next i
' Loop
End If
Next u
'-------ETAPA 4
'calcula c2 e identifica qual cliente adicionar ao roteiro
'inicialização dos valores
C2(0) = -10000
C2(1) = -10000
C2(2) = -10000
C2(3) = -10000
C2(4) = -10000
C2(5) = -10000
For u = 5 To n + w
C2(u) = 0
Next u
For u = 1 To Clientes(2, abrir1)
If ClienteEscolhido(Z(2, abrir1, u)) = 1 And PotencialEntrar(Z(2, abrir1, u)) = 1 Then
C2(Z(2, abrir1, u)) = cost(abrir1, Z(2, abrir1, u)) - Custosuplementar(Z(2, abrir1, u))
Else
C2(Z(2, abrir1, u)) = -10000
End If
Next u
'Verifica se ha capacidade para adicionar um cliente e se é de interesse adicionar este cliente ou
iniciar um novo roteiro
SemCapacidade = 1
For i = 1 To Clientes(2, abrir1)
If CapacidadeDisponivel > demanda(Z(2, abrir1, i)) And ClienteEscolhido(Z(2, abrir1, i)) =
1 And PotencialEntrar(Z(2, abrir1, i)) = 1 And C2(Z(2, abrir1, i)) > 0 Then
SemCapacidade = 0
End If
Next i
If SemCapacidade = 1 Then
NumVeiculo = NumVeiculo + 1
End If
If SemCapacidade = 0 Then
Sair = 0
u = 1
120
Do Until Sair = 1
If C2(Z(2, abrir1, u)) = Application.WorksheetFunction.Large(C2, 1) And
ClienteEscolhido(Z(2, abrir1, u)) = 1 Then
TamRoteiro = TamRoteiro + 1
'Insere o cliente no roteiro e na Posicao(u). Adiciono mais um espaço (slot) no roteiro para
poder adicionar o novo cliente
i = TamRoteiro
'abre espaço para o cliente u
Do Until i = Posicao(Z(2, abrir1, u))
V(2, abrir1, NumVeiculo, i) = V(2, abrir1, NumVeiculo, i - 1)
i = i - 1
Loop
'insere cliente u na posicao(u)
V(2, abrir1, NumVeiculo, Posicao(Z(2, abrir1, u))) = Z(2, abrir1, u)
CapacidadeDisponivel = CapacidadeDisponivel - demanda(Z(2, abrir1, u))
DuracaoRoteiro(NumVeiculo) = DuracaoRoteiro(NumVeiculo) + PF(Z(2, abrir1, u))
Lmin = JornadaMax - DuracaoRoteiro(NumVeiculo)
'atualiza o tempo de fim maximo e de inicio minimo do meu roteiro
If horario_fim_atendimento(Z(2, abrir1, u)) < tempo_fim_roteiro(NumVeiculo) Then
tempo_fim_roteiro(NumVeiculo) = horario_fim_atendimento(Z(2, abrir1, u))
End If
If horario_inicio_atendimento(Z(2, abrir1, u)) > tempo_inicio_roteiro(NumVeiculo) Then
tempo_inicio_roteiro(NumVeiculo) = horario_inicio_atendimento(Z(2, abrir1, u))
End If
ClienteEscolhido(Z(2, abrir1, u)) = 0
CostAbrir1ToClient(u) = 0
Sair = 1
End If
u = u + 1
Loop
End If
Loop
'Verifica se tenho algum cliente não alocado. Se não houver, mantem rotas = 0 e sai do loop.
rotas = 0
For i = 1 To Clientes(2, abrir1)
If ClienteEscolhido(Z(2, abrir1, i)) = 1 Then
rotas = 1
End If
Next i
Loop
Worksheets("Resultados 2 CD").Activate
Range("AF22").Activate
For i = 1 To p
ActiveCell = tempo_inicio_roteiro(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
Range("AG22").Activate
For i = 1 To p
ActiveCell = tempo_fim_roteiro(i)
'vai para linha seguinte
121
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'----------- ROTEIRIZACAO SEGUNDO CD - CENARIO 2-----------
'inicializa tempos de atendimento dos roteiros
For i = 1 To p
tempo_inicio_roteiro(i) = 0
tempo_fim_roteiro(i) = 0
Next i
'roteiro de cada cenario, para cada CD, para n clientes, n ordem de clientes dentro do roteiro
NumVeiculo = 1
rotas = 1
Do Until rotas = 0
'veiculo sai do CD
V(2, abrir2, NumVeiculo, 0) = abrir2
'ETAPA 1
'identificar qual o cliente mais longe do CD aberto que ainda não foi servido e inicio a contruir
minha rota passando por ele
Sair = 0
j = 1
'se não há clientes alocados, não realiza roteirização
If Clientes(2, abrir2) = 0 Then
Sair = 1
End If
Do Until Sair = 1
If cost(abrir2, Z(2, abrir2, j)) = Application.WorksheetFunction.Large(CostAbrir2ToClient, 1)
And ClienteEscolhido(Z(2, abrir2, j)) = 1 Then
V(2, abrir2, NumVeiculo, 1) = Z(2, abrir2, j)
V(2, abrir2, NumVeiculo, 2) = abrir2
'marca que o cliente foi servido
ClienteEscolhido(Z(2, abrir2, j)) = 0
'calcula o espaço livre no caminhão
CapacidadeDisponivel = capacidade - demanda(Z(2, abrir2, j))
'tamanho do roteiro com 1 cliente
TamRoteiro = 2
Sair = 1
CostAbrir2ToClient(j) = 0
'estabelece o inicio e o fim maximo do roteiro
tempo_inicio_roteiro(NumVeiculo) = horario_inicio_atendimento(Z(2, abrir2, j))
tempo_fim_roteiro(NumVeiculo) = horario_fim_atendimento(Z(2, abrir2, j))
'estabelece a duracao do roteiro e quanto tempo ha disponivel na jornada de trabalho
DuracaoRoteiro(NumVeiculo) = T(abrir2, Z(2, abrir2, j))
Lmin = JornadaMax - DuracaoRoteiro(NumVeiculo)
End If
j = j + 1
Loop
'Verifica se com a inserção de cliente que acaba de realizar já atende a todos os clientes
SemCapacidade = 1
For i = 1 To Clientes(2, abrir2)
If ClienteEscolhido(Z(2, abrir2, i)) = 1 Then
122
SemCapacidade = 0
End If
Next i
Do Until SemCapacidade = 1
'-------ETAPA 2
'Identifica os clientes com potencial para entrar
For j = 1 To Clientes(2, abrir2)
If CapacidadeDisponivel - demanda(Z(2, abrir2, j)) > 0 And ClienteEscolhido(Z(2, abrir2, j)) =
1 And horario_inicio_atendimento(Z(2, abrir2, j)) >= tempo_inicio_roteiro(NumVeiculo) And
horario_inicio_atendimento(Z(2, abrir2, j)) <= tempo_fim_roteiro(NumVeiculo) Then
PotencialEntrar(Z(2, abrir2, j)) = 1
Else
PotencialEntrar(Z(2, abrir2, j)) = 0
End If
Next j
'-------ETAPA 3
'calcula c1 e a melhor posição para inserir cada cliente candidato na rota
For u = 1 To Clientes(2, abrir2)
If PotencialEntrar(Z(2, abrir2, u)) = 1 Then
i = 1
C1antigo = 10000000
PotencialEntrar(Z(2, abrir2, u)) = 0
For i = 1 To TamRoteiro
C1novo = cost(V(2, abrir2, NumVeiculo, i - 1), Z(2, abrir2, u)) + cost(Z(2, abrir2, u), V(2,
abrir2, NumVeiculo, i)) - cost(V(2, abrir2, NumVeiculo, i - 1), V(2, abrir2, NumVeiculo, i))
PFnovo = T(V(2, abrir2, NumVeiculo, i - 1), Z(2, abrir2, u)) + T(Z(2, abrir2, u), V(2,
abrir2, NumVeiculo, i)) - T(V(2, abrir2, NumVeiculo, i - 1), V(2, abrir2, NumVeiculo, i))
If C1novo < C1antigo And PFnovo < Lmin Then
Custosuplementar(Z(2, abrir2, u)) = C1novo
Posicao(Z(2, abrir2, u)) = i
PF(Z(2, abrir2, u)) = PFnovo
PotencialEntrar(Z(2, abrir2, u)) = 1
End If
C1antigo = C1novo
Next i
End If
Next u
'-------ETAPA 4
'calcula c2 e identifica qual cliente adicionar ao roteiro
'inicialização dos valores
C2(0) = -10000
C2(1) = -10000
C2(2) = -10000
C2(3) = -10000
C2(4) = -10000
C2(5) = -10000
For u = 5 To n + w
C2(u) = 0
Next u
For u = 1 To Clientes(2, abrir2)
If ClienteEscolhido(Z(2, abrir2, u)) = 1 And PotencialEntrar(Z(2, abrir2, u)) = 1 Then
123
C2(Z(2, abrir2, u)) = cost(abrir2, Z(2, abrir2, u)) - Custosuplementar(Z(2, abrir2, u))
Else
C2(Z(2, abrir2, u)) = -10000
End If
Next u
'Verifica se o veiculo ainda tem capacidade, se não tiver, vai para o proximo veiculo
SemCapacidade = 1
For i = 1 To Clientes(2, abrir2)
If CapacidadeDisponivel > demanda(Z(2, abrir2, i)) And ClienteEscolhido(Z(2, abrir2, i)) = 1
And PotencialEntrar(Z(2, abrir2, i)) = 1 And C2(Z(2, abrir2, i)) > 0 Then
SemCapacidade = 0
End If
Next i
If SemCapacidade = 1 Then
NumVeiculo = NumVeiculo + 1
End If
'Se há capacidade, e existe um cliente com C2>0, insire este cliente no roteiro, se não, sai do Loop e
inicia um novo roteiro
If SemCapacidade = 0 Then
Sair = 0
u = 1
Do Until Sair = 1
If C2(Z(2, abrir2, u)) = Application.WorksheetFunction.Large(C2, 1) And
ClienteEscolhido(Z(2, abrir2, u)) = 1 Then
TamRoteiro = TamRoteiro + 1
'Insere o cliente no roteiro e na Posicao(u). Adiciona mais um espaço (slot) no roteiro para
poder adicionar o novo cliente
i = TamRoteiro
'abre espaço para o cliente u
Do Until i = Posicao(Z(2, abrir2, u))
V(2, abrir2, NumVeiculo, i) = V(2, abrir2, NumVeiculo, i - 1)
i = i - 1
Loop
'insere cliente u na posicao(u)
V(2, abrir2, NumVeiculo, Posicao(Z(2, abrir2, u))) = Z(2, abrir2, u)
CapacidadeDisponivel = CapacidadeDisponivel - demanda(Z(2, abrir2, u))
DuracaoRoteiro(NumVeiculo) = DuracaoRoteiro(NumVeiculo) + PF(Z(2, abrir2, u))
Lmin = JornadaMax - DuracaoRoteiro(NumVeiculo)
'atualiza o tempo de fim maximo e de inicio minimo do meu roteiro
If horario_fim_atendimento(Z(2, abrir2, u)) < tempo_fim_roteiro(NumVeiculo) Then
tempo_fim_roteiro(NumVeiculo) = horario_fim_atendimento(Z(2, abrir2, u))
End If
If horario_inicio_atendimento(Z(2, abrir2, u)) > tempo_inicio_roteiro(NumVeiculo) Then
tempo_inicio_roteiro(NumVeiculo) = horario_inicio_atendimento(Z(2, abrir2, u))
End If
ClienteEscolhido(Z(2, abrir2, u)) = 0
CostAbrir2ToClient(u) = 0
Sair = 1
End If
u = u + 1
Loop
124
End If
Loop
'Verifica se tenho algum cliente não alocado. Se não houver, mantem rotas = 0 e sai do loop.
rotas = 0
For i = 1 To Clientes(2, abrir2)
If ClienteEscolhido(Z(2, abrir2, i)) = 1 Then
rotas = 1
End If
Next i
Loop
Worksheets("Resultados 2 CD").Activate
Range("AF128").Activate
For i = 1 To p
ActiveCell = tempo_inicio_roteiro(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
Range("AG128").Activate
For i = 1 To p
ActiveCell = tempo_fim_roteiro(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'----------------------------Calcula Custo Distribuição
CustoTotal = 0
For NumVeiculo = 1 To p
For i = 1 To n
CustoTotal = CustoTotal + cost(V(2, abrir1, NumVeiculo, i - 1), V(2, abrir1, NumVeiculo, i))
Next i
Next NumVeiculo
For NumVeiculo = 1 To p
For i = 1 To n
CustoTotal = CustoTotal + cost(V(2, abrir2, NumVeiculo, i - 1), V(2, abrir2, NumVeiculo, i))
Next i
Next NumVeiculo
'-------------------------------------- Resultados Cenario 2 CD ---------------------------------------------
Worksheets("Resultados 2 CD").Activate
'imprime custo total do cenario
Range("G1").Activate
ActiveCell = CustoTotal
'imprime coeficientes de centralidade
Range("B2").Activate
For i = 1 To (w)
ActiveCell = cent(i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
125
Next i
'imprime se CD esta aberto ou fechado
Range("C2").Activate
For i = 1 To (w)
ActiveCell = CD(2, i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'imprime numero de clientes alocados a cada CD
Range("D2").Activate
For i = 1 To (w)
ActiveCell = Clientes(2, i)
'vai para linha seguinte
ActiveCell.Offset(1, 0).Range("A1").Select
Next i
'imprime clientes entregues para cada CD
Range("B11").Activate
For i = 1 To w
For j = 1 To n
ActiveCell = Z(2, i, j)
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
'vai para linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
'imprime roteiros CD1
Range("A21").Activate
ActiveCell = abrir1
Range("B22").Activate
For i = 1 To p
For j = 1 To 30
ActiveCell = V(2, abrir1, i, j)
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
'vai para linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
'imprime roteiros CD2
Range("A127").Activate
ActiveCell = abrir2
Range("B128").Activate
For i = 1 To p
For j = 1 To 30
ActiveCell = V(2, abrir2, i, j)
ActiveCell.Offset(0, 1).Range("A1").Select
Next j
'vai para linha seguinte
ActiveCell.Offset(1, 1 - j).Range("A1").Select
Next i
127
APÊNDICE D – EXTRATO DA MATRIZ DE CUSTO DE DESLOCAMENTO ENTRE
CLIENTES E DEPÓSITOS
De
/ P
ara
Be
rge
nS
an
dn
es
Tro
nd
he
imF
red
rik
sta
dH
am
ar
C1
.1C
1.2
C2
.1C
2.2
C3
C4
C4
C5
C6
.1C
6.2
C6
.3C
7C
8C
9.1
C9
.2C
10
.1C
10
.2C
10
.3
Be
rge
n0
33
56
91
82
76
88
66
74
69
16
69
16
11
09
71
10
97
42
98
90
11
90
11
36
24
41
33
41
33
41
33
63
95
67
48
68
85
68
85
72
02
72
02
72
02
Sa
nd
ne
s0
01
20
65
71
15
81
47
71
14
71
14
13
97
01
39
70
60
47
11
41
71
14
17
26
87
92
79
27
92
77
84
65
36
65
29
65
29
68
45
68
45
68
45
Tro
nd
he
im0
00
82
35
54
59
70
61
70
61
19
47
19
47
62
92
25
54
25
54
12
32
71
28
36
12
83
61
28
36
59
42
74
15
73
32
73
32
73
43
73
43
73
43
Fre
dri
ks
tad
00
00
30
08
18
94
18
94
94
44
94
44
39
82
65
42
65
42
71
28
71
21
71
21
71
21
30
04
16
62
15
74
15
74
14
25
14
25
14
25
Ha
ma
r0
00
00
18
22
18
22
73
70
73
70
26
58
40
21
40
21
83
40
88
02
88
02
88
02
10
47
21
75
20
93
20
93
21
03
21
03
21
03
C1
.10
00
00
00
81
46
81
46
25
73
52
43
52
43
69
65
69
68
69
68
69
68
11
05
83
07
20
72
05
45
54
55
45
C1
.20
00
00
00
81
46
81
46
25
73
52
43
52
43
69
65
69
68
69
68
69
68
11
05
83
07
20
72
05
45
54
55
45
C2
.10
00
00
81
34
81
34
00
74
03
33
89
33
89
13
31
21
33
62
13
36
21
33
62
70
09
84
29
83
33
83
33
81
64
81
64
81
64
C2
.20
00
00
81
34
81
34
00
74
03
33
89
33
89
13
31
21
33
62
13
36
21
33
62
70
09
84
29
83
33
83
33
81
64
81
64
81
64
C3
00
00
02
57
12
57
17
40
27
40
20
52
89
52
89
60
04
60
55
60
55
60
55
21
47
23
36
24
46
24
46
26
32
26
32
26
32
C4
00
00
05
22
35
22
33
37
83
37
85
29
00
01
11
99
11
24
91
12
49
11
24
94
24
35
51
75
42
95
42
95
26
05
26
05
26
0
C4
00
00
05
22
35
22
33
37
83
37
85
29
00
01
11
99
11
24
91
12
49
11
24
94
24
35
51
75
42
95
42
95
26
05
26
05
26
0
C5
00
00
06
96
76
96
71
33
09
13
30
96
00
11
11
95
11
19
50
10
11
01
10
17
63
16
32
26
31
06
31
06
44
66
44
66
44
6
C6
.10
00
00
69
69
69
69
13
36
31
33
63
60
56
11
25
71
12
57
10
00
00
76
25
63
24
63
03
63
03
64
40
64
40
64
40
C6
.20
00
00
69
69
69
69
13
36
31
33
63
60
56
11
25
71
12
57
10
00
00
76
25
63
24
63
03
63
03
64
40
64
40
64
40
C6
.30
00
00
69
69
69
69
13
36
31
33
63
60
56
11
25
71
12
57
10
00
00
76
25
63
24
63
03
63
03
64
40
64
40
64
40
C7
00
00
01
10
51
10
57
00
07
00
02
14
94
24
34
24
37
62
27
62
57
62
57
62
50
17
11
18
14
18
14
16
59
16
59
16
59
C8
00
00
08
36
83
68
43
68
43
62
33
65
53
45
53
46
32
36
32
66
32
66
32
61
70
30
11
61
16
31
53
15
31
5
C9
.10
00
00
72
27
22
83
48
83
48
24
46
54
45
54
45
63
01
63
03
63
03
63
03
19
07
12
50
02
26
22
62
26
C9
.20
00
00
72
27
22
83
48
83
48
24
46
54
45
54
45
63
01
63
03
63
03
63
03
19
07
12
50
02
26
22
62
26
C1
0.1
00
00
05
37
53
78
15
58
15
52
62
25
25
25
25
26
44
66
44
16
44
16
44
11
71
43
03
21
42
14
00
0
C1
0.2
00
00
05
37
53
78
15
58
15
52
62
25
25
25
25
26
44
66
44
16
44
16
44
11
71
43
03
21
42
14
00
0
C1
0.3
00
00
05
37
53
78
15
58
15
52
62
25
25
25
25
26
44
66
44
16
44
16
44
11
71
43
03
21
42
14
00
0
129
APÊNDICE E –EXTRATO DA MATRIZ DE TEMPO DE DESLOCAMENTO ENTRE
CLIENTES E DEPÓSITOS
,
De
/ P
ara
Be
rge
nS
an
dn
es
Tro
nd
he
imF
red
rik
sta
dH
am
ar
C1
.1C
1.2
C2
.1C
2.2
C3
C4
C4
C5
C6
.1C
6.2
C6
.3C
7C
8C
9.1
C9
.2C
10
.1C
10
.2C
10
.3
Be
rge
n0
234
601
502
431
439
439
680
680
274
567
567
238
241
241
241
406
423
430
430
439
439
439
Sa
nd
ne
s0
078
646
152
445
745
786
486
438
973
573
54
88
850
641
341
341
342
242
242
2T
ron
dh
eim
00
051
835
144
644
682
8240
215
215
278
979
279
279
238
545
945
445
444
344
344
3F
red
rik
sta
d0
00
018
211
911
959
759
725
040
440
446
446
346
346
318
610
398
9888
8888
Ha
ma
r0
00
00
109
109
430
430
163
237
237
523
523
523
523
5912
211
711
710
610
610
6C
1.1
00
00
00
052
452
416
433
133
145
745
745
745
773
5751
5139
3939
C1
.20
00
00
00
524
524
164
331
331
457
457
457
457
7357
5151
3939
39C
2.1
00
00
052
552
50
048
122
722
786
887
187
187
146
453
953
353
352
252
252
2C
2.2
00
00
052
552
50
048
122
722
786
887
187
187
146
453
953
353
352
252
252
2C
30
00
00
164
164
481
481
035
135
139
339
639
639
613
814
815
615
616
916
916
9C
40
00
00
331
331
226
226
352
00
739
742
742
742
276
345
340
340
329
329
329
C4
00
00
033
133
122
622
635
20
073
974
274
274
227
634
534
034
032
932
932
9C
50
00
00
457
457
868
868
393
738
738
08
88
506
413
413
413
422
422
422
C6
.10
00
00
457
457
871
871
396
742
742
80
00
505
413
412
412
421
421
421
C6
.20
00
00
457
457
871
871
396
742
742
80
00
505
413
412
412
421
421
421
C6
.30
00
00
457
457
871
871
396
742
742
80
00
505
413
412
412
421
421
421
C7
00
00
073
7346
346
313
827
627
650
550
550
550
50
116
123
123
113
113
113
C8
00
00
057
5753
953
914
834
634
641
341
341
341
311
50
99
2222
22C
9.1
00
00
051
5153
453
415
634
134
141
241
241
241
212
39
00
1717
17C
9.2
00
00
051
5153
453
415
634
134
141
241
241
241
212
39
00
1717
17C
10
.10
00
00
3838
521
521
168
328
328
422
421
421
421
110
2116
160
00
C1
0.2
00
00
038
3852
152
116
832
832
842
242
142
142
111
021
1616
00
0C
10
.30
00
00
3838
521
521
168
328
328
422
421
421
421
110
2116
160
00