PROBLEMA DO CAIXEIRO VIAJANTE (PCV) APLICADO A OTIMIZAÇÃO DE ROTEIROS DE VEÍCULOS DE TRANSPORTE RODOVIÁRIO DE UMA DISTRIBUIDORA DE ÓLEO LUBRIFICANTE A GRANEL EM FORTALEZA E REGIÃO METROPOLITANA

 

 

Raynner Braga Araripe

Graduando do Curso de Engenharia de Produção do Centro Universitário 7 de Setembro (UNI7).

raynner.ba@gmail.com

 

Natália Varela da Rocha Kloeckner

Professora adjunta do curso de Engenharia de Produção do Centro Universitário 7 de Setembro (UNI7). Mestre em Logística e Pesquisa Operacional pela Universidade Federal do Ceará (UFC). Graduada em Economia pela UFC. Professora de cursos de graduação e pós-graduação da UNI7 e Faculdade Ari de Sá.

natalia.kloeckner@fa7.edu.br

 

 

RESUMO

É notório a importância que as organizações passaram a dar aos serviços logísticos, considerando estes como parte da estratégia empresarial, a fim de prospectar novos clientes e renovar a satisfação dos atuais. O presente estudo tem como objetivo geral aplicar o problema do caixeiro viajante, um dos problemas clássicos de roteirização de veículos, para otimização de rotas no transporte rodoviário de uma distribuidora de óleo lubrificante a granel em Fortaleza e região metropolitana. Além disso, o estudo visou demonstrar os conceitos do transporte rodoviário no Brasil e no mundo, bem como as variáveis internas e externas que podem influenciar, de forma geral, os problemas de roteirização. Acrescentando também o auxílio que os sistemas de informação trouxeram aos serviços logísticos. Este trabalho é do tipo exploratório-descritivo, de natureza quantitativa, com amostra estocástica, visto que os dados selecionados para realização desse estudo foram escolhidos aleatóriamente do banco de dados da empresa, se fazendo presente também a análise documental de dados, método experimental com análise de variáveis e utilização de modelos matemáticos, para a solução do problema. Como resultados do problema proposto, através do software LINDO®, foram logrados a redução no percurso de entrega em comparação com a rota realizada.

 

PALAVRAS-CHAVE: Caixeiro viajante. Óleo lubrificante. Serviços logísticos. Transporte rodoviário. Rotas.

 

ABSTRACT

It is notorious the importance that organizations started to give to logistics services, considering these as part of the business strategy, in order to prospect new customers and renew the satisfaction of the current ones. The present study has as general objective to apply the problem of the traveling salesman, one of the classic vehicle routing problems, to optimize routes in the road transport of a bulk lubricating oil distributor in Fortaleza and metropolitan region. In addition, the study aimed to demonstrate the concepts of road transport in Brazil and in the world, as well as the internal and external variables that can influence, in a general way, the routing problems. It also adds the help that information systems have brought to logistics services. This work is an exploratory-descriptive type, with a quantitative nature, with a stochastic sample, since the data selected for this study were chosen randomly from the company's database, being also present documentary data analysis, experimental method with analysis of variables and use of mathematical models, to solve the problem. As a result of the proposed problem, through LINDO® software, the reduction in the delivery path was achieved in comparison to the route performed.

 

KEYWORDS: Traveling salesman. Lubricant. Logistic services. Road transport. Routes.


1 INTRODUÇÃO

 

Haja vista o atual cenário econômico, é imprescindível que novas alternativas sejam buscadas na operacionalização dos processos empresariais. O foco dos esforços estão voltados para os serviços logísticos, nos quais é necessário que sejam realizados precisamente os processos de armazenagem, movimentação e o tempo de fornecimento do produto ao cliente. Sendo assim, é relevante que a logística de transporte seja elaborada adequadamente. Nesse aspecto, os distribuidores têm papel fundamental, visto que um adequado funcionamento destes processos podem garantir a satisfação do cliente (NOVAES, 2007).

Para Ballou (2011), o nível de serviço logístico relaciona-se com a qualidade com que são gerenciados os fluxos de bens e serviços. Dessa forma, o resultado das atividades logísticas das empresas reflete-se no desempenho dos seus fornecedores perante seus clientes.

Devido às mudanças no mercado, cada vez mais aceleradas, a busca por preço e qualidade permanece em cada nova transferência de mercadoria, ou seja, a melhor alternativa para a logística de transporte deve ser flexível, sem a existência de modelo padrão, sendo validada a cada operação realizada. A situação de mercado vivenciada no passado levou à escolha de um determinado modelo de distribuição, este podendo ser alterado com as situações que ocorrerão (KEEDI, 2015).

Na definição da estratégia de distribuição a ser seguida para os serviços logísticos, é necessário que sejam levados em consideração vários fatores, principalmente os referentes às informações relativas ao custo, à demanda e à localização de entrega (RESENDE; MENDONÇA; CERQUEIRA, 2006).

No Brasil, é possível identificar a importância que vem sendo dada ao serviço logístico nos últimos anos. Segundo o resultado divulgado pelo Banco Mundial no relatório bienal de logística, em 2012 o país ocupava a 45ª posição de 160 países. Apesar de sofrer uma queda considerável nos anos seguintes para 65ª posição, houve uma retomada em 2016 em que figurou na 55ª posição (BANCO MUNDIAL, 2016).

Dentro dos serviços logísticos, em escala mundial, o transporte é considerado primordial, pois é o que mais detêm os custos e, devido a isso, é necessário a busca por aumento na eficiência da utilização da frota (BALLOU, 2006).

No que tange à logística de transporte e de acordo com o Plano de Transporte e Logística divulgado pela Confederação Nacional do Transporte (CNT), no Brasil, a matriz de transporte de cargas e passageiros é predominantemente rodoviária, esta correnpondendo aproximadamente a 61,1% de transporte de carga (CNT, 2014).

 Com relação ao transporte de passageiros, em 2011, o fluxo brasileiro de transporte rodoviário correspondia a 131,5 milhões, em comparação com o transporte aéreo no mesmo período que correspondia a 99,9 milhões de passageiros (CNT, 2014).

A distribuição dos produtos é uma atividade essencial para o ramo de distribuidoras, que visam, eminentemente, a disponibilizar os produtos certos nos lugares requeridos, no momento e nível de serviço desejados, incorrendo no menor custo possível (NOVAES, 2007).

No âmbito urbano, ainda há dificuldades quanto à distribuição de carga, a qual depara-se com várias restrições, como o difícil acesso a algumas ruas e indisponibilidade para o tráfego. Com isso, quando esta é realizada eficientemente, contribui de forma relevante na busca por melhorias no serviço logístico (PAULA, 2009).

Dada a complexidade de circulação urbana, o estudo de roteirização de veículos configura-se como um método satisfatório para identificar se a rota seguida é a mais viável economicamente e eficientemente. Para tal, este método apoia-se na elaboração de modelos matemáticos a partir da consideração de distintas instâncias de aplicações, buscando a geração de resultados ótimos para apoio a tomada de decisão. Com isso, a roteirização de veículos passa a ser essencial para o aumento da eficiência dos serviços logísticos (NOVAES, 2007).

De acordo com o estudo realizado por Resende; Mendonça e Cerqueira (2006), em que foi investigada a utilização de uma ampla gama de sistemas de gerenciamento de operações que servem de ferramentas de apoio à decisão referente aos serviços logísticos, apenas 6,6% das empresas, de 102 pesquisadas, tinham como atividade a roteirização através de um sistema para controle das operações de distribuição de produtos.

Aperfeiçoar os serviços aos clientes é também descobrir os melhores roteiros a serem seguidos para os veículos. Dessa forma, minimizar o tempo de percurso e a distância passam a ser temas importantes na tomada de decisões para obtenção da vantagem competitiva empresarial (BALLOU, 2006).

Entre os métodos de roteirização mais utilizados, está o Problema do Caixeiro Viajante (PCV), que consiste em traçar uma rota que retorne o menor percurso, partindo de um ponto, visitando todos os outros somente uma vez e retornando ao ponto de origem (BALLOU, 2006).  Trata-se de um problema de fácil compreensão e descrição, contudo, de grande dificuldade de solução, uma vez que pertence à categoria dos NP-difícil, ou seja, a sua dificuldade em solução aumenta exponencialmente quanto maior for o tamanho do problema (KARP, 1975).

O planejamento de suprimentos e de distribuição de produtos surge a partir da demanda, e esta, por sua vez, é definida através do relacionamento que a empresa tem com o cliente. Consequentemente, é estabelecida a roteirização de veículos e, desse modo, pode-se então minimizar os custos e aumentar o valor agregado oferecido ao cliente através do prazo de entrega (RESENDE; MENDONÇA; CERQUEIRA, 2006).

É de suma importância que empresas que têm por finalidade a distribuição de produtos realizem esta atividade de maneira eficaz. Com o modelo de rota a ser percorrido, é possível então reduzir as perdas inerentes ao processo, com relação a distância percorrida. Com isso, agilizando a entrega e assim podendo estar a frente diante deste mercado competitivo, que vem crescendo devido à consciência ambiental da população.

Este trabalho baseia-se em um estudo de caso, onde a empresa analisada, de distribuição do produto óleo lubrificante a granel, não possui uma rota definida, sendo a entrega atualmente realizada de modo empírico, ou seja, de acordo com o conhecimento do próprio motorista e dos funcionários da logística. Desta forma, toma-se como hipótese que, tal posicionamento pode estar designando o caminhão a rodar mais do que o necessário e, consequentemente, aumentando a distância e tardando a entrega do produto ao cliente.

Mediante ao exposto e visto que a roteirização de veículos pode trazer benefícios aos serviços logísticos da distribuidora de óleo lubrificante a granel, fez-se necessária a realização de um estudo sobre a roteirização de veículos, para que fosse aplicado o modelo matemático que atendesse as necessidades do problema vivenciado, direcionado aos clientes de Fortaleza e região metropolitana da empresa em análise. Por sigilo, requerido pela empresa, esta será denominada neste estudo por Empresa XYZ. Logo, dada a instância de aplicação, elegeu-se o Problema do Caixeiro Viajante (PCV).

Com base nesse contexto, o presente estudo tem por problema de pesquisa responder de que maneira pode-se obter uma melhoria na roteirização de veículos de transporte rodoviário de uma distribuidora de óleo lubrificante a granel?

O objetivo geral é aplicar o problema do caixeiro viajante para otimização de rotas no transporte rodoviário de uma distribuidora de óleo lubrificante a granel em Fortaleza e região metropolitana. Os objetivos específicos teóricos deste estudo são: descrever a logística de distribuição de carga; descrever a modelagem matemática do problema do caixeiro viajante; descrever sobre métodos de solução do PCV, bem como os métodos de melhorias de roteiro que podem ser obtidas na rota pós otimizada, e; descrever a utilização do software LINDO® como ferramenta viável para modelagem e geração de solução para o PCV.

Já os objetivos específicos empíricos deste estudo concentram-se em descrever a estratégia de distribuição utilizada em uma distribuidora de óleo lubrificante a granel localizada em Fortaleza e com atuação na capital e região metropolitana. Propondo, para isso, a aplicação do modelo matemático do problema de otimização do caixeiro viajante em seu processo de distribuição, por meio do software LINDO® de forma a analisar a eficiência quanto a nova geração de rotas para atendimento dos seus clientes a partir de um único veículo.

Trata-se de um estudo de caso que, baseado nas informações obtidas dentro da empresa em questão, se utiliza da pesquisa do tipo exploratório-descritiva, com meios de investigação bibliográfica e de campo. Contudo, sua natureza é de pesquisa quantitativa, com amostra estocástica intencional.

A estrutura deste estudo é composta por cinco seções. A primeira seção refere-se à introdução do trabalho, na qual foi descrita a importância que os serviços logísticos vêm tomando nas organizações, tendo como parte disso a roteirização de veículos. Na segunda seção, é exposta a revisão de literatura, que contempla três subseções: na primeira, é descrito um breve histórico sobre a evolução do transporte rodoviário de cargas no mundo e no Brasil, bem como as variáveis relacionadas aos serviços logísticos no transporte rodoviário; na segunda, é apresentado o problema do caixeiro viajante, explanando sobre o modelo matemático, métodos heurísticos e melhorias de roteiros, e; a terceira subseção visa demonstrar a importância dos sistemas de informação na logística e explanar sobre o software LINDO®. Já a terceira seção aborda a aplicação do método utilizado neste estudo. A quarta seção demonstra os resultados alcançados neste trabalho e, por fim, a quinta seção traz as considerações finais sobre o estudo. 

 

2 REVISÃO DE LITERATURA

 

Nesta seção foram indicados os conteúdos teóricos que deram embasamento ao estudo em questão, são eles: logística de distribuição de carga rodoviária; problema do caixeiro viajante e; aplicação do modelo matemático no software LINDO®.

 

2.1 LOGÍSTICA DE DISTRIBUIÇÃO DE CARGA RODOVIÁRIA

 

Nesta subseção, são apresentados os conceitos gerais do transporte rodoviário no mundo e no Brasil, abrangendo o histórico de evolução até os dias atuais, bem como as tendências para o futuro, previstas por autores e especialistas deste segmento.

 

2.1.1 Transporte Rodoviário no Mundo

 

O modal rodoviário surgiu no final do século XIX, juntamente com a criação da indústria automobilística, sendo que, desde os primórdios, o homem visa aperfeiçoar o sistema de transporte, adaptando-o de acordo com as necessidades da época em que vivia, tendo como os primeiros registros o transporte realizado por tração animal ou até mesmo braçal. Com o surgimento dos veículos automotivos, os pontos próximos ou distantes foram interligados, permitindo uma maior agilidade nas trocas comerciais e assim propiciando um grande avanço na economia (KEEDI, 2015).

O transporte rodoviário foi um dos primeiros a serem utilizados pelo homem, este tem grande participação na evolução da logística internacional, ainda mais quando é interligado com outros modais e consegue realizar exatamente aquilo que lhe é devido, a entrega em distâncias não tão grandes e a movimentação constante (BALLOU, 2011).

Nos países mais desenvolvidos, como os da União Européia e os Estados Unidos da América, a distribuição de produtos das fábricas e dos depósitos podem ser realizadas por diversos modais de transporte. Tais combinações são bastante variadas pelos fabricantes (NOVAES, 2007).

Apesar desta diversidade em modais de transporte maior em alguns países do que no Brasil, ainda assim o transporte rodoviário representa um papel predominante nos serviços logísticos, no entanto, considerado de alto custo, os investimentos estão sendo voltados para que o valor operacional deste modal reduza (SOUSA, 2014).

 

2.1.2 Transporte rodoviário no Brasil

 

O modal rodoviário tem grande participação nos modos do transporte nacional de cargas. Atingindo praticamente todo o território brasileiro, teve seu crescimento expressivo a partir da década de 50, com a chegada da indústria automobilística, que proporcionou a pavimentação das estradas para facilitar e agilizar a movimentação de cargas e pessoas (ALVARENGA; NOVAES, 2000).

Segundo Keedi (2015), este modal é considerado de grande relevância por ser o único que pode atender a demanda de ponta a ponta. Representa mais da metade (não contabilizando o transporte de minério de ferro)  do total de cargas transportadas no Brasil. Tal modal tem por tendência atual diminuir a sua representação devido à divisão de cargas com os demais modais, visto que o transporte rodoviário detêm um valor de implantação e manutenção alto, o que custa no bolso da população, pois é pago através dos impostos.

O setor de transporte rodoviário também passa por dificuldades. As principais vertentes referenciadas por Bowersox et al. (2014) são quanto ao crescente custo de reposição de equipamentos e combustível, bem como o aumento de despesas com a manutenção e crescente preocupação com a segurança nas estradas. Adicionam-se ainda as dificuldades do setor, a baixa oferta de motoristas, a regulamentação atual para os caminhoneiros quanto ao horário de trabalho e os baixos salários dos trabalhadores dos terminais.

Apesar do investimento atual do governo de disseminar os transportes de cargas no Brasil através da modernização de outros modais, o modal rodoviário ainda estará nesta posição por um tempo significativo, visto que toda a estrutura das empresas foram formadas em visão deste segmento, como por exemplo, os terminais de carga, equipamentos, estrutura de comunicação e administrativa (DIAS, 2010).

“Com base apenas no tamanho do setor de transportes rodoviários e nos serviços prestados, fica bastante claro que o transporte em estradas continuará a funcionar como eixo principal das operações logísticas” (BOWERSOX et al., 2014, p. 207).

 

2.1.3 Variáveis Relacionadas ao Serviço Logístico no Transporte Rodoviário

 

Neste subitem são apresentados as variáveis internas e externas que influenciam no serviço do transporte logístico rodoviário e são utilizadas, de forma geral, nos problemas de roteirização.

 

2.1.3.1 Variáveis internas

 

Com relação às variáveis internas, é preciso considerar diversos fatores, um deles é a capacidade do veículo de coleta e distribuição. Sendo necessário dimensionar, pois, dependendo da capacidade que será necessária para carregar ou descarregar, possivelmente ocorrerá superlotação do veículo, devendo-se, então, buscar uma nova alternativa para atendimento (VALENTE et al., 2016).

 

Apesar de a roteirização ser uma importante ferramenta para a redução dos custos e aumento da eficiência operacional, ela depende de alguns fatores essenciais, entre eles uma base de dados atualizada e sistemas modernos, normalmente baseados em Sistema de Informações Geográficas (GIS), que são itens caros e nem sempre se adaptam facilmente à cultura das empresas. O maior risco dos sistemas roteirizadores advém das informações que parametrizarão o sistema e que alimentarão o mesmo. Desta forma, destaca-se a necessidade de envolvimento das pessoas a fim de gerar constantes atualizações no cadastro das informações para alcançar resultados positivos (ROSA, 2007, p. 43).

 

O tempo de entrega em cada cliente também deve ser contabilizado, como também o horário de trabalho a ser obedecido pelo motorista, pois caso isso não aconteça, corre-se o risco de formular um modelo em que ele atenda todos os clientes, porém não obedeça aos horários estipulados (SOUSA, 2014).

 

Um aspecto inerente ao planejamento operacional é o grau de complexidade dos problemas tratados em função da grande quantidade de variáveis de decisão e restrições a serem analisadas. Assim, a obtenção de soluções a partir de métodos exclusivamente manuais pode se tornar bastante difícil e demorada, contrapondo-se a necessidade de boas soluções geradas em um curto espaço de tempo (ARAÚJO, 2010, p. 21).

 

2.1.3.2 Variáveis externas

 

Muitas variáveis externas estão relacionadas para contribuir com o serviço logístico do transporte rodoviário. Destas, é possível citar uma constante no Brasil e que prejudica bastante o trabalho do motorista, trata-se da infraestrutura das rodovias. As estradas são precárias, fazendo que o tempo de viagem do ponto de partida ao ponto de destino aumente. Por causa disso, o motorista deve redobrar sua atenção. Esta situação vivenciada nas estradas brasileiras também aumentam os custos operacionais do veículo (GHERESHI; TÓFILO; LIMA, 2012).

No caso de entregas dentro da região urbana, é preciso verificar a lei que rege a situação para entrega de cargas, pois barra-se em várias restrições que devem ser levadas em consideração na elaboração do modelo matemático, visando não formular uma rota seguindo por caminhos que não podem ser seguidos (SOUSA, 2014).

A segurança no tráfego também é encarada como uma variável de grande importância e, devido a isso, as entregas, até mesmo daqueles produtos que poderiam alterar seu horário de entrega para fora do horário comercial, são realizados durante o dia, aumentando cada vez mais o congestionamento dentro das grandes cidades (ROSA, 2007).

Em geral, as variáveis externas passam pelos âmbitos naturais, sociais, econômicos, entre outros, onde todos estes devem ser descritos de maneira matemática para que se adequem ao modelo, para fins de solução e validação, sendo coerentes com o que realmente acontece (ARENALES, 2007).

 

2.2 O PROBLEMA DO CAIXEIRO VIAJANTE

 

Esta subseção concentra-se na abordagem sobre o problema de otimização do caixeiro viajante, sendo apresentados sua definição, a caracterização do problema, a formulação do modelo matemático, as aplicações associadas ao problema, bem como os métodos utilizados para solução e melhoria dos roteiros gerados.

 

2.2.1 Características do Problema do Caixeiro Viajante (PCV)

 

O essencial para a qualidade dos serviços logísticos é disponibilizar ao cliente os produtos em tempo e local desejado, este então é o desafio das empresas que buscam o aperfeiçoamento em suas distribuições. Na atividade de definição de rota de veículo é preciso priorizar o melhor caminho para atender o maior número possível de clientes a um menor custo (LISBOA, 2007).

Nesse âmbito, emerge o problema do caixeiro viajante (PCV), um dos problemas clássicos de roteirização de veículos. Também conhecido por Travelling Salesman Problem (TSP), o PCV tem por objetivo basicamente fazer com que todos os clientes sejam visitados apenas uma vez e que a distância total percorrida entre eles seja minimizada, ou seja, o roteiro gerado seja o menor possível (LISBOA, 2007).

Segundo Cunha et al. (2002), a origem do PCV é atribuída a Willian Rowan Hamilton, que, por meio do seu jogo chamado de Around the World, estimulou a construção de um roteiro, por meio dos vértices de um dodecaedro. Tal jogo tinha como regras que o início e término do roteiro deveriam ser no mesmo ponto (vértice) e que a visita deveria ocorrer a todos os pontos do poliedro, contudo, sem que houvesse repetições dos pontos já visitados.

Segundo Belfiore e Fávero (2013), o problema do caixeiro viajante é considerado como um problema de programação binária, por suas variáveis de decisão assumir o valor igual a “1” (um) se o roteiro sugerido é seguido ou, caso contrário, “0” (zero),  quando o roteiro pretendido não é localizado.

Associado também à teoria dos grafos, conforme é apresentado na Figura 1, o PCV consiste em analisar todas as rotas, chamadas de circuitos hamiltonianos, para os n vértices considerados. Neste sentido, um circuito hamiltoniano é caracterizado pela rota que o caixeiro deve fazer, de forma que visite todos os vértices do grafo G = (N,E), onde N é o conjunto de nós (clientes) e E o conjunto de arestas (ruas), sendo associada a cada aresta um custo que liga os vértices (clientes) i ao j, Cij. Desta forma, a solução consiste em visitar todos os clientes somente uma única vez, retornando ao final para o ponto de origem. A rota ou percurso escolhido será o que retornar a menor distância total percorrida (SILVA, 2013).

 

Figura 1 – Grafo do problema hamiltoniano

Fonte: Goldbarg e Luna (2005 apud Belfiore e Fávero, 2013, p. 394).

 

O PCV é possível de ser modelado como um problema de programação em redes. Para isso, deve ser formado como uma estrutura de rede que possua diversos nós, todos devendo estar conectados a pelo menos um ou mais arcos (BELFIORE; FÁVERO, 2013). Na figura 2 é possível visualizar rede de caminhos e a visita de todos os pontos.

 

 

 

Figura 2 – Rede de caminhos entre os clientes

Fonte: Belfiore e Fávero, 2013, p. 474 (adaptado pelo autor).

 

O problema do caixeiro viajante é um dos mais tradicionais de roteamento de veículos, com vários estudos e trabalhos relacionados na literatura. Nesse contexto, um fator impactante para sua alta adesão em trabalhos acadêmicos é condicionada à fácil compreensão e descrição do problema (SILVA, 2013).

Contudo, o problema apresenta alta complexidade computacional, ou seja, aumenta muito o consumo de recursos, como o tempo e memória do computador, utilizados para retornar uma solução aceitável. Deste modo, os trabalhos de PCV evidenciam que os esforços programáveis crescem exponencialmente com o tamanho do problema considerado, categoria esta de problemas computacionais intitulados como NP-difícil (SILVA, 2013).

Este modelo pode ser aplicado em diversos problemas práticos conforme Goldbarg e Luna (2000 apud COLARES et al., 2005) citam, tais como:

a)    programação de operações de máquinas e manufatura;

b)    programação de transporte entre células de manufatura;

c)    otimização de movimento de ferramentas de corte;

d)    otimização de perfurações de furos em placas de circuitos impressos;    

e)    nos problemas de roteamento de veículos;

f)      nos de problemas de sequenciamento;

g)    nos problemas de programação e distribuição de tarefas em plantas;

h)    trabalhos administrativos; entre outros.

2.2.2 Formulação do modelo matemático

 

A definição do modelo matemático a ser estudado e implementado para a resolução do problema em questão é de grande importância para o alcance da otimização. A partir dessa definição, é possível aprofundar os estudos neste problema, realizando a demonstração de todas as respostas possíveis até enfim encontrar a ótima (TAHA, 2008).

O modelo matemático tradicional pode apresentar dois níveis de resolução. No primeiro momento, é a fase de programação/elaboração do roteiro de distribuição, onde ainda não é possível identificar com precisão os locais em que serão realizados os atendimentos, tanto de coleta como de distribuição. Visto isso, são adotadas, para fins de cálculo, estimativas aproximadas percebidas pelo felling de quem conhece o serviço e o modelo que será implementado, sendo possível então uma análise ampla das alternativas a serem seguidas (VALENTE et al., 2016).

No segundo momento, já é considerado como fase de operação, onde é possível ter a informação dos locais de atendimento. Podendo ser também, a partir daí, distinguidos por pontos fixos ou aleatórios. São exemplos de pontos fixos: distribuição de jornais e entrega de mercadorias nos varejistas. São exemplos de pontos aleatórios: serviço de entrega de compras nos clientes e entrega de óleo lubrificante a granel de acordo com a demanda (VALENTE et al., 2016).

De acordo com Lachtermacher (2002), através de modelos matemáticos, é possível otimizar os processos operacionais de transportes rodoviários, logo a busca por melhores roteiros que caracterizem a realidade e limitações quanto à operação da empresa estão sendo cada vez mais demandados, principalmente por organizações que possuem suas atividades diretamente ligadas à distribuição, à coleta, ao despacho, a entregas etc. Sendo assim, a busca pela realização deste serviço de maneira eficaz agrega valor ao cliente, tornando-a competitiva no mercado.

A notação matemática usada por Dantzig, Fulkerson e Johnson (DFJ), conforme descrito por Belfiore e Fávero (2013, p. 394), para descrever o modelo PCV é apresentada a seguir:

Conjuntos:

N: conjunto dos clientes a serem visitados.

Parâmetros do modelo:

Cij: distância do cliente i para o cliente j, i = 1, ..., n e j = 1, ..., n.

 

Variáveis de decisão:

Xij: variável binária; assume o valor 1 se o caixeiro viajante for diretamente do cliente i para o cliente j, ij, sendo 0 caso contrário.

 

Formulação matemática:

                                              

n

 

n

 
            Função Objetivo:

j=1

 

i=1

 
Minimizar z = ∑ ∑ Cij Xij        (1)

 

            Sujeito as restrições:

n

 
           

i=1

 
                       Xij = 1                 j N                        (2)

 

           

n

 

j=1

 
                       Xij = 1                 i N                        (3)

 

i, jS

 
Xij ≤ |S| - 1         S N                      (4)      

 

Xij {0,1}                   i, j N                      (5)      

 

Sendo assim, a função objetivo (1) a ser minimizada representa a distância total da rota. O conjunto de restrições do tipo (2) garante que o caixeiro saia de um cliente somente uma vez. Já o conjunto de restrições do tipo (3) impõe que o caixeiro visite um cliente, ou seja, entre somente uma vez. O conjunto de restrições do tipo (4) evita que a ciclagem menor que n seja solução viável para o problema, ou seja, visa vetar a criação de sub-rotas dentro da rota principal, sendo |S| o número de clientes de S e a expressão |S| - 1 a quantidade de nós à considerar para evitar sub-rotas. Por fim, o conjunto de restrições do tipo (5) garante que as variáveis de decisão sejam binárias.

 

2.2.3 Métodos de solução

 

O problema do caixeiro viajante é de difícil solução, pois nele é possível obter um grande número de soluções possíveis, principalmente quando é utilizado em grandes e diversas distâncias, considerado sua complexidade polinomial – NP – Difícil (BELFIORE; FÁVERO, 2013).

Problemas desta magnitude geralmente são abordados através de Heurísticas, que de acordo com Hillier e Lieberman (2013) são os métodos que possibilitam encontrar a solução possível de aplicação na resolução do problema proposto, não sendo possível garantir de que esta solução encontrada trata-se da ótima.

Conforme Reeves (1995 apud COLARES et al., 2005) as heurísticas passaram a ser formuladas a partir do momento que estudiosos se depararam com problemas complexos, até mesmo para que sejam rodados computacionalmente. Sendo assim, foi designado que a opção seria averiguar todas as soluções possíveis do problema em questão e assim ter a total firmeza para designar entre a melhor delas.

Neste subitem são abordados os métodos de solução para o problema do caixeiro viajante, no qual, no primeiro tópico, será explanado sobre a heurística do vizinho mais próximo; no segundo tópico, é o método pela heurística da inserção mais barata e; no terceiro tópico, será abordada a heurística de Clark e Wright.

 

2.2.3.1 Heurística do vizinho mais próximo

 

O método heurístico denominado como do vizinho mais próximo, é definido a partir da escolha do ponto de partida. Sendo assim, saindo do ponto de partida, a rota a ser realizada irá com destino ao ponto mais próximo. Este procedimento é seguido nessa sequência para os demais pontos da rota, considerando aqueles que ainda não foram visitados (BELFIORE; FÁVERO, 2013).

 

2.2.3.2 Heurística da inserção mais barata

 

A Heurística de Inserção mais Barata foi proposta por Karg e Thompson (1964). Este método busca partir de uma definição inicial com apenas três cidades, ou três pontos de parada. Apesar de haver mais pontos, estes ficam para uma tratativa posterior. A escolha para a seleção do primeiro roteiro é entre os pontos de entrega que possuem a menor distância entre eles. Sendo assim, esta atividade é repetida por vezes, analisando a inclusão de ponto a ponto até que todos tenham sido inseridos no roteiro (SILVA, 2013).

 

2.2.3.3 Heurística de Clark e Wright

 

O método heurístico de Clark e Wright também é conhecido como o método das economias que, de acordo com Ballou (2006), tem como premissa diminuir o percurso entre os clientes, bem como o quantitativo de veículos para atender a necessidade, ou seja, realizar um menor percurso com o menor número de veículos e atendendo a todos da mesma forma.

A utilização do método Clark e Wright vem crescendo na resolução de problemas isolados, como também vem sendo incorporado nos softwares de roteirização de veículos, isto é, devido à forma eficiente com que o seu roteiro é calculado, levando em consideração todas as restrições referenciadas (NOVAES, 2007).

Abaixo é possível visualizar a equação de cálculo do ganho de acordo com Novaes (2007):

gi,j = dD,i + dD,j – di,j

 

Onde: gi,j: Ganho da equação;

            dD,i: Distância do CD para o ponto i;

            dD,j: Distância do CD para o ponto j;

            di,j: Distância do ponto i para o j.

 Ainda de acordo com Novaes (2007), o método de Clark e Wright é constituído das seguintes etapas:

a)    1º etapa: combinam-se todas as paradas da rota dois a dois e, a partir daí calcula-se o ganho de cada combinação;

b)    2º etapa: ordenam-se todas as combinações de forma decrescente de acordo com os valores dos ganhos;

c)    3º etapa: é dado o início com a combinação de dois pontos que forneceram o maior ganho, posteriormente vai realizando com os demais, seguindo a ordem de ganhos;

d)    4º etapa: considerando um par de ponto (i, j), removido da sequência, é necessário verificar se já fazem parte de um roteiro iniciado;

e)    5º etapa: cada vez que houver alteração no roteiro, seja com acréscimo de algum ponto ou fusão de dois, é preciso verificar se as restrições continuam a satisfazer o modelo;

f)      6º etapa: o processo é finalizado após a inclusão de todas as paradas no roteiro.

 

2.2.4 Melhorias de Roteiro

 

Os métodos de melhoria de rotas buscam a todo momento otimizar o percurso a ser realizado dentro de um roteiro traçado no primeiro momento pelo problema do caixeiro viajante. Os métodos mais aplicados nessa perspectiva são os de arcos, desenvolvidos por Lin e Kernighan (1973),  o 2-opt (2 arcos) e 3-opt (3 arcos) (NOVAES, 2007). É necessário ressaltar que, para que seja encontrada uma nova solução ótima, é imprescindível que a solução inicial seja realizada de maneira correta (CAMPOS, 2008).

Ainda de acordo com Novaes (2007) o método 2-opt é composto pelas seguintes etapas:

a)  1º etapa: dar início com o roteiro gerado pelo problema do caixeiro viajante;

b)  2º etapa: remover dois arcos deste roteiro e reconectando-os novamente e, assim, consequentemente, alterando as ligações. É necessário verificar se o novo resultado foi melhor que o anterior, ou seja, uma menor distância, sendo então possível substituir o roteiro inicial pelo novo. A partir disso é repetido esta mesma etapa com outros dois arcos, realizando isto sucessivamente;

c)   3º etapa: término do processo, que acontece quando já tiver realizado todas as tentativas de ligações possíveis e não foi localizado mais nenhum ponto de melhoria.

 

O método 3-opt consiste do mesmo conceito do método 2-opt, com a diferença que, dessa vez, é trabalhado com 3 arcos, ou seja, somados três pontos por vez. Considerando esse aumento nos arcos, logo é possível então a realização de sete alterações diferentes. Sendo assim, esse método oferece resultados mais exatos (NOVAES, 2007).

 

2.3 SISTEMAS DE INFORMAÇÃO E O SOFTWARE  LINDO®

 

Os sistemas de informação vêm modificando a rotina das empresas nos mais diversos setores de atividade. Com a logística não é diferente, é possível constatar que um bom sistema de informação atualmente é indispensável para uma boa performance da organização (BRANCO; GIGIOLI, 2013).

Conforme Rezende e Abreu (2008) ressaltam, os sistemas de informação são implementados e aperfeiçoados para que possam auxiliar nas tomadas de decisões das empresas, lembrando que estes devem estar interligados com o objetivo principal da empresa. Caso contrário, estes sistemas não somarão para a melhor performance empresarial. 

A busca por melhorias nos processos logísticos, bem como na automatização das atividades devido aos avanços com que é necessário dar o retorno ao cliente, ou seja, na tratativa das informações, vem impulsionando o ramo de tecnologia voltado para esta área. É possível identificar no mercado os mais diversos sistemas voltados para a logística, sendo necessário então uma correta avaliação de acordo com o que a empresa busca atender e de retorno esperado (BRANCO; GIGIOLI, 2013).

Com o avanço da tecnologia, a informação vem sendo distribuída em vários outros meios. O cliente busca e indaça notícias a todo e qualquer momento, sendo possível assim monitorar a sua solicitação. Isso vem alterando o modo como as empresas devem distribuir a informação, visto que elas devem estar disponíveis ao maior interessado, o cliente (NOVAES, 2007).

Na solução de modelos matemáticos de alta complexidade o Linear, Interactive, and Discrete Optimizer (LINDO), é uma ferramente bastante utilizada para a resolução de problemas de programação linear, inteira e quadrática (JÚNIOR; SOUZA, 2004).

De acordo com Júnior e Souza (2004), para que o LINDO possa concluir um resultado e demonstrar a melhor rota a partir de um modelo matemático, ele deverá conter: função objetivo (fo), a qual deverá iniciar com os comandos MAX para maximizar e MIN para minimizar, isto dependendo do que está sendo buscado no problema, sendo informado na mesma linha de comando da função objetivo; logo abaixo a declaração SUBJECT TO (sujeito a) podendo ser substituído por “st” ou “s.t.”, onde depois serão declaradas as restrições do problema; incluir as restrições do problema para finalizar e assim ser possível que o programa “rode”, é necessário declarar o comando END. Ainda conforme os autores, as variáveis devem ser declaradas com no máximo oito letras.

 

3 MÉTODO

 

Segundo Marconi e Lakatos (2010), o método é o conjunto de procedimentos sistematizados e racionais que, de modo econômico e seguro, permitem o alcance do objetivo pretendido, mitigando erros e apoiando as decisões do pesquisador.

Para obtenção dos objetivos propostos neste estudo, as subseções a seguir concentram-se na descrição dos procedimentos metodológicos adotados.

 

3.1 CARACTERIZAÇÃO E ESTRATÉGIA DA PESQUISA

 

Segundo Marconi e Lakatos (2010), a pesquisa constitui-se de uma estratégia reflexiva do pensamento, que demanda, a partir de análises e investigações empíricas e teóricas, a aplicação de processos científicos.

Partindo disso, no que se refere aos objetivos, a presente pesquisa é do tipo exploratório-descritiva. Onde, por meio da descrição das características da população ou fenômeno, a pesquisa exploratória permite um estudo diversificado, que evidencia as relações entre as variáveis consideradas por meio do levantamento bibliográfico, bem como entrevista com pessoas que vivenciam o objeto do estudo em questão (PRODONOV; FREITAS, 2013).

Quanto à natureza, esta pesquisa é classificada como quantitativa com amostra estocástica, visto que os dados diários, como quantidade de demanda e localização de clientes (distância), considerados no trabalho, foram selecionados aleatóriamente do banco de dados da empresa em estudo. Dessa forma, faz-se presente também a análise documental de dados, método experimental com análise de variáveis e utilização de modelos matemáticos para a solução do problema.

Há uma grande semelhança entre a pesquisa documental e a bibliográfica, porém é possível distinguí-las partindo-se da identificação de onde se é colhidas as informações, a fonte. A pesquisa documental utiliza-se de materiais sem tratamento analítico; já na bibliográfica utiliza-se do cenário oposto ao mencionado (GIL, 2002).

Quanto ao método experimental, de acordo com Gil (2002), consiste nas etapas de a partir da determinação de um objeto de estudo: selecionar as variáveis que seriam capazes de influenciá-lo e definir o modo de controle dos efeitos e suas observações.

Para a realização deste estudo, foi necessário analisar a rota atual de entrega de óleo lubrificante a granel em Fortaleza e região metropolitana. Foi de extrema importância o entendimento e realização deste procedimento técnico para que o trabalho fosse realizado de maneira correta, podendo traçar a rota ótima para a atividade de entrega.

 

3.2 ESTUDO DE CASO – EMPRESA XYZ

 

O presente trabalho realizou um estudo de caso baseado nas informações obtidas dentro de uma empresa distribuidora de óleo lubrificante a granel localizada na cidade de Fortaleza e com área de atendimento na capital e região metropolitana. Objetivando o sigilo em relação as observações feitas, a empresa passa a ser denominada como XYZ, vide Apêndice A (p. 34).

  Segundo Gil (2002), o estudo de caso pode ser definido como um método de pesquisa que consiste no estudo em profundidade e exaustão de poucos objetos de forma a detalhar o seu conhecimento.

Nesse sentido, o estudo de caso envolve os pesquisadores na coleta de informações, a fim de instruí-los de argumentos referente ao assunto da pesquisa envolvida para que possa ter propriedade nas análises dos resultados (PRODONOV; FREITAS, 2013).

Mediante ao exposto, o presente artigo utiliza-se da estratégia do estudo de caso para investigar e analisar a roteirização de veículos de transporte rodoviário da empresa XYZ em Fortaleza e região metropolitana.

Já quanto à amostra, este estudo a expõe como não probabilística, pois a coleta de dados foi selecionada intencionalmente. Conforme Prodonov e Freitas (2013), este tipo de amostra consiste em selecionar uma parte do que se é necessário, ou seja, onde o estudo é realizado e validado para aquele ambiente.

 

3.3 INSTRUMENTO E TÉCNICA DE COLETA DE DADOS

 

De acordo com Marconi e Lakatos (2010, p. 149), a coleta de dados é a “etapa da pesquisa em que se inicia a aplicação dos instrumentos elaborados e das técnicas selecionadas, a fim de se efetuar a coleta dos dados previstos”.

Com relação ao tipo de instrumento, o presente estudo foi realizado a partir de entrevista não estruturada despadronizada focalizada com os colaboradores do setor de logística, pois, de acordo com Marconi e Lakatos (2010, p. 180) “o entrevistador tem liberdade para desenvolver cada situação em qualquer direção que considere adequada. É uma forma de poder explorar mais amplamente uma questão”. Devido a isso, os responsáveis pela a informação tiveram a liberdade para expor o seu pensamento sobre o objeto de estudo, a partir de pontos considerados importantes conforme Apêndice B (p. 35).

Além desta pesquisa não estruturada, foi possível também levantar as informações através do sistema informatizado utilizado e dos dados já existentes, ou seja, foi utilizada a pesquisa documental nos arquivos da empresa.

Para Prodonov e Freitas (2013, p. 106) “o pré-teste refere-se ao teste do questionário (entrevista) em uma pequena amostra de entrevistados, com o objetivo de identificar e eliminar problemas potenciais”.

No estudo em questão, como foi idealizado uma entrevista, os pré-testes ocorreram de forma constante, no período em que a pesquisa deu-se início em julho de 2017, de acordo com a necessidade identificada através das respostas obtidas.

Conforme Marconi e Lakatos (2010, p. 186) “o pré-teste pode ser aplicado mais de uma vez, tendo em vista o seu aprimoramento e aumento de sua validez. Deve ser aplicado em populações com características semelhantes”.

Após a realização do primeiro momento em que foram efetuadas as entrevistas dos pré-testes, foi possível então ter um maior esclarecimento sobre o assunto estudado, bem como a validação do modelo matemático proposto por meio dos dados obtidos.

A coleta de informações, neste âmbito, ocorreu por meio do sistema informatizado utilizado na empresa, como também dos dados que a empresa já possuía com relação a roteirização de transporte rodoviário de óleo lubrificante a granel em Fortaleza e região metropolitana. Partindo desse conhecimento, foi possível analisar e identificar o que era necessário para encontrar a solução ótima para este problema.

 

3.4 MÉTODO DE COLETA E PROCESSAMENTO DOS DADOS

 

A coleta de dados constitui-se a primeira etapa da pesquisa para a aplicação dos instrumentos e técnicas selecionadas para o estudo (MARCONI; LAKATOS, 2010).

A entrevista não estruturada foi realizada pessoalmente pelo pesquisador no período de agosto e setembro de 2017 na empresa em estudo. Cabe ressaltar, que foi considerado um período grande de entrevista, observação e coleta de dados visando identificar todas as variáveis possíveis do problema, para que assim fossem levadas em consideração. 

Durante a coleta de informações através do motorista, analistas e gerente do setor de logística, também foi possível colher os dados documentais existentes em referência ao objeto de estudo, com relação à definição da rota utilizada atualmente, endereço dos clientes e quantitativo da carga a ser transportada.

Após a análise documental e aplicação da entrevista não estruturada, foi capaz de identificar as informações necessárias e importantes a serem consideradas dentro do modelo matemático, para que logo depois fosse possível realizar a tabulação destes dados.

Segundo Pronodov e Freitas (2013, p. 114), para a tabulação, “os dados coletados são dispostos em tabelas e gráficos [...], classificados pela divisão de subgrupos e reunidos de modo que as hipóteses possam ser comprovadas ou refutadas”.

Assim, prosseguiu-se para a tabulação dos dados no Microsoft Office Excel® de forma a facilitar a visualização e tratabilidade destes no software LINDO®.

Com a tabulação bem formalizada dos dados, foi possível realizar as tratativas e análises necessárias para os dados coletados e assim também “rodar” o modelo matemático proposto. Para Marconi e Lakatos (2010, p. 214) “é aqui que são transcritos os resultados, agora sob forma de evidências para a confirmação ou refutação das hipóteses”.

Com relação a este trabalho, a análise e interpretação dos dados foram extraídas única e exclusivamente de dados e informações pertinentes a empresa estudada.

Foi utilizada a técnica de análise de conteúdo, que de acordo com Marconi e Lakatos (2010, p. 206) “permite a descrição sistemática, objetiva e quantitativa do conteúdo da comunicação”. Para este estudo, as informações coletadas foram as que já existiam na empresa, onde estas foram incluídas no modelo matemático para que fosse possível, através do problema do caixeiro viajante, encontrar o resultado ótimo para a entrega de uma distribuidora de óleo lubrificante a granel em Fortaleza e região metropolitana.

 

4 RESULTADOS DA PESQUISA

 

A coleta dos dados realizada junto à Empresa XYZ, com os colaboradores do setor de logística, abordou o funcionamento para a entrega de óleo lubrificante a granel em Fortaleza e região metropolitana.

Nesta seção, foram demonstrados os dados referente ao objeto deste estudo, resultando em rotas no modelo adotado para aplicação (PCV). Ressalta-se que tais dados foram levantados e aplicados conforme proposta. Além disso, é apresentado também o seu processo de distribuição, de forma a evidenciar o cenário e instância do problema em estudo.

 

4.1 OBJETO DE ESTUDO – EMPRESA XYZ

 

Este estudo foi realizado em uma empresa de médio-grande porte que está presente no Ceará há mais de 35 anos. Denominada, neste estudo, por Empresa XYZ, tal organização tem por característica a sua solidez e experiência no mercado de óleo lubrificante, atuando no norte e nordeste do país. Possui no seu quadro de colaboradores profissionais engenheiros e especialistas em lubrificação, a fim de atender aos seus clientes nos mais elevados níveis de qualidade.

É oferecido ao mercado o óleo lubrificante em dois tipos de produtos, que são: embalados (caixas, tambor, baldes) e o granel. A entrega dos embalados é realizada por transportadoras terceirizadas, com isso, o objeto deste estudo é a roteirização da rota a granel, referente as entregas do centro de distribuição localizado na cidade de Fortaleza-CE, com o trajeto de atuação na capital e região metropolitana.

 

4.1.1 Características da distribuição e instância do problema

 

O óleo lubrificante a granel é distribuído através de “frota” própria, por um caminhão do tipo toco, com capacidade de 8000 litros de óleo, sendo 5000 litros para óleo do tipo MX e 3000 litros para óleo do tipo FLEX. A capacidade do caminhão não é levada em consideração neste modelo, pois a oferta do veículo é sempre maior do que a demanda.

A empresa XYZ não possui sistema de roteirização. A rota que ocorre no dia (D) geralmente é dos pedidos lançados em sistema no dia anterior (D - 1). Assim, em seguida, o processo concentra-se na emissão das notas fiscais e sua entrega para conhecimento do motorista, para que possa realizar o carregamento do caminhão, que geralmente acontece no final do expediente (D - 1) ou no início da manhã (D).

Ressalta-se que não ocorrem alterações com os clientes já estabelecidos à serem distribuidos na rota (D). Porém, por vezes, a partir de solicitação da Gerência Comercial, há a necessidade de inclusão de pedidos no mesmo dia ou até mesmo a alteração dos clientes a serem visitados. Esta solicitação classificada como “extra” impacta na rota já estabelecida, pois é incluído esta demanda na rota atual e poderá postergar a entrega de algum cliente que já estava programado naquela rota para o dia seguinte (D + 1). As etapas de geração do pedido e processamento são apresentados resumidamente no Apêndice C (p. 36).

A instância do problema da empresa XYZ é compatível com o PCV, uma vez que trata-se de rotear n clientes a partir da sede da empresa, passando por cada um desses clientes somente uma única vez no dia e retornando, ao final da jornada, a origem da rota (sede). Vale ressaltar ainda, que, de acordo com o histórico da empresa, não foi evidenciado casos onde o único veículo não satisfaz toda a demanda de clientes, programada para um dia no dado espaço de tempo para a jornada de trabalho. Visto que, mesmo com os pedidos “extras” que podem ocorrer, a entrega é alinhada com os clientes.

Para realização deste estudo, foi coletado na empresa XYZ os dados referentes as entregas realizadas em dois dias aleatórios, de forma a ser possível evidenciar e comparar os resultados obtidos no modelo PCV com o de dois cenários distintos reais. Tais dados foram: a demanda de clientes e a rota seguida em ambas diárias.

Como critério para análise desse estudo, além dos dados de rotas praticados obtidos na empresa XYZ, foram pesquisadas as melhores rotas entre os clientes em quilômetros (km) no Google Maps®.

As tabelas 1 e 2, são referentes à matriz de distância entre a sede da empresa e os clientes, nos dias escolhidos aleatoriamente. Dado a grande participação das rodovias nos trechos coletados (distâncias), tomando a característica de possuírem a orientação em dois sentidos, popularmente chamado de “mão dupla”, considerou-se esta aplicação do PCV como de característica simétrica, ou seja, com a distância da sede para o cliente sendo a mesma que a do cliente para a sede.

Tal característica do PCV simétrico, impactará na quantidade de restrições que evitam sub-rotas do modelo, pois uma vez que, por exemplo, a distância do Cliente 1 para o Cliente 2 não difere na distância do Cliente 2 para o Cliente 1, não será necessário abordar as duas restrições, evidenciando no modelo apenas uma das duas.

 

Tabela 1 – Matriz de distância entre a sede da empresa e clientes em KM na amostra 1

PARA

0

1

2

3

4

5

6

DE

0

0

11

20,8

3,3

19

13,6

17,8

1

11

0

9,8

9,9

21

4,4

6,9

2

20,8

9,8

0

30,5

11,2

20,5

17,2

3

3,3

9,9

30,5

0

31

12,6

16,8

4

19

21

11,2

31

0

20,2

16,9

5

13,6

4,4

20,5

12,6

20,2

0

5,9

6

17,8

6,9

17,2

16,8

16,9

5,9

0

Fonte: Elaborado pelo autor.

 

Tabela 2 – Matriz de distância entre a sede da empresa e clientes em KM na amostra 2

PARA

0

1

2

3

4

5

DE

0

0

7,2

19,9

8,7

8,9

14,4

1

7,2

0

18,2

6,9

5,1

13

2

19,9

18,2

0

12,1

10,9

3,8

3

8,7

6,9

12,1

0

5,9

11,7

4

8,9

5,1

10,9

5,9

0

6,3

5

14,4

13

3,8

11,7

6,3

0

Fonte: Elaborado pelo autor.

 

4.2 CENÁRIOS E ETAPAS DE APLICAÇÃO

 

Para melhor caracterização do impacto do modelo PCV na empresa analisada, tal trabalho realizou a análise em duas etapas para cada cenário selecionado: i. obtenção da rota ótima gerada pelo PCV na instância conjuntamente com a distância total inferida e possíveis melhorias; ii. comparação em km da rota ótima obtida quanto a rota realizada previamente pela empresa estudada.

            Devido à facilidade de inserção dos dados amostrados no modelo matemático, optou-se por utilizar o software LINDO® para obtenção das rotas ótimas em cada instância considerada. A rota seguida pela empresa nos dias amostrados apresenta-se logo a seguir na Tabela 3.

 

Tabela 3 – Rota realizada pela empresa XYZ, nas amostras coletadas

Amostra 1

 

Amostra 2

DE

PARA

DISTÂNCIA (KM)

DE

PARA

DISTÂNCIA (KM)

0

3

3,3

0

3

8,7

3

5

12,6

3

1

6,9

5

1

4,4

1

4

5,1

1

6

6,9

4

5

6,3

6

2

17,2

5

2

3,8

2

4

11,2

2

0

19,9

4

0

19

-

-

-

TOTAL

74,6

 

TOTAL

50,7

Fonte: Elaborado pelo autor.

 

Quanto a rota realizada pela empresa XYZ, de forma empírica, para a amostra 1, é iniciada na SEDE (0), seguindo o percurso para os clientes 3, 5, 1, 6, 2, 4, respectivamente, quando retorna a SEDE (0). Já para a amostra 2, com rota também iniciada em (0), o percurso realizado foi para os clientes 3, 1, 4, 5, 2, respectivamente, retornando por fim a SEDE (0).

 

4.2.1 Etapa 1: rota ótima com aplicação do PCV utilizando o software LINDO®

 

O modelo matemático do PCV aplicado às amostras contempla a roteirização de onze clientes no total, sendo seis clientes para a amostra 1 e cinco clientes para a amostra 2, devendo o veículo capacitado de até 8000 litros sair para a entrega a partir da SEDE e após visitar todos os clientes diários retornar para ela.

As formulações do modelo matemático para cada amostra com a definição das suas respectivas função objetivo e restrições, foram desenvolvidas no LINDO®. Tais modelagens realizadas encontram-se nos Apêndice D (p. 37 a 42) e  Apêndice E (p. 43 a 46).

A solução pelo software LINDO®, resultou na atribuição pelo sistema da melhor rota gerada para a distribuição referente ao estudo em questão. Dessa forma, a solução pelo LINDO® envolve um relatório constando a menor distância ótima obtida (função objetivo ótimo), a partir da determinação das variáveis de decisão binárias que devem ser seguidas (rota obtida).

Realizado o processo de obtenção da solução pelo software LINDO® para todas as amostras, é possível visualizar o resultado quanto aos caminhos e distâncias totais a serem percorridas na rota, em quilômetros (km), na Tabela 4.

 

Tabela 4 – Rota gerada pelo LINDO® para cada dia amostrado, em quilômetros (KM)

Amostra 1

 

Amostra 2

DE

PARA

DISTÂNCIA (KM)

DE

PARA

DISTÂNCIA (KM)

0

3

3,3

0

3

8,7

3

5

12,6

3

2

12,1

5

6

5,9

2

5

3,8

6

1

6,9

5

4

6,3

1

2

9,8

4

1

5,1

2

4

11,2

1

0

7,2

4

0

19

-

-

-

TOTAL

68,7

 

TOTAL

43,2

Fonte: Elaborado pelo autor.

 

Para a amostra 1, utilizando o software LINDO®, a rota gerada também inicia-se pela SEDE (0) e seguindo, na ordem, para os clientes 3, 5, 6, 1, 2, 4, quando por fim, retorna ao ponto de origem. O total desse percurso é de 68,7 km. Já na amostra 2, a rota ótima obtida é a iniciando na SEDE (0), e seguindo para os clientes 3, 2, 5, 4, 1, respectivamente, retornando ao final ao ponto de origem.

Quanto a aplicação do método de melhoria 2-opt, escolhido para esta instância dada a quantidade de clientes, não foram obtidas melhorias diante das já geradas no modelo otimizado pelo LINDO®, conforme pode-se obervar nas figuras nos Apêndice F (p. 47) e Apêndice G (p. 48).

 

4.2.2 Etapa 2: comparação da rota ótima obtida com a realizada pela empresa XYZ

 

Após a definição do modelo matemático e a solução com a aplicação do software LINDO®, foi possível realizar a comparação de cada amostra coletada na empresa com a gerada neste estudo.

Com o uso do problema de otimização do caixeiro viajante é possível demonstrar matematicamente o menor caminho a ser percorrido, eliminando a possibilidade de decisões por uma rota à ser gerada empiricamente, pelo sentimento de que o caminho escolhido é o melhor a ser realizado.

É possível verificar também melhorias quanto ao controle e segurança da rota a ser realizada, visto que o caminhão possui rastreador e pode-se acompanhar caso este venha a sair da rota programada do dia.

No que tange à distância percorrida entre os pontos a serem visitados, é possível verificar na tabela 5, que em todas as amostras a rota gerada através da formulação matemática no software LINDO® foi menor do que a rota realizada.

 

Tabela 5 – Consolidado das informações das amostras

Amostra 1

Amostra 2

Rota realizada (KM)

74,6

50,7

Rota no LINDO®

68,7

43,2

Total Litros entregue (demanda)

2054

1550

% decréscimo em distância

7,9%

14,7%

Fonte: Elaborado pelo autor.

 

Na rota referente a amostra 1 houve um decréscimo de distância de 7,9%, na amostra 2 o decréscimo foi de 14,7%, demonstrando e comprovando que a redução referente ao caminho percorrido aconteceu, após a aplicação do PCV.

Logo, o PCV demonstrou-se eficiente na geração de rotas, retornando distâncias menores a serem percorridas quando comparadas as já praticadas pela empresa.

 

5 CONSIDERAÇÕES FINAIS

 

O presente estudo de caso demonstrou como metodologia a aplicabilidade do PCV e como a correta rota de atendimento aos clientes pode impactar de maneira positiva na melhoria do serviço de entrega, dado a agilidade pela menor distância da rota ótima.

Os objetivos específicos, descrever a logística de distribuição de carga, descrever a modelagem matemática do PCV foram evidenciados no referencial teórico, onde também, foi explanado sobre o transporte rodoviário mundial e brasileiro, bem como as variáveis internas e externas que podem influenciar, de forma geral, os problemas de roteirização.

Além dos objetivos mencionados acima, adiciona-se a caracterização do PCV, a formulação do modelo matemático, métodos de solução e melhorias do roteiro, objeto de aplicação desse estudo. Foi explanado também, sobre a importância dos sistemas de informação nos serviços logísticos, com aplicação do software LINDO® para resolução do problema proposto.

O objetivo relacionado a descrever a estratégia de distribuição utilizada pela empresa XYZ foi evidenciado já no item 4.1.1, características da distribuição e instância do problema.

O objetivo referente à aplicabilidade do PCV e o processo realizado para elaboração do modelo matemático, a fim de encontrar a solução ótima para o problema, foi demonstrado nos resultados. Diante disso, os dados extraídos da empresa estudada foram incluídos conforme visto nos itens 4.1.1 e 4.2, onde nesse momento foram demonstrados a distância no percurso da sede da empresa para cada cliente no dia das amostras.

O objetivo geral, de analisar a roteirização de veículos de transporte rodoviário de uma distribuidora de óleo lubrificante a granel em Fortaleza e região metropolitana, utilizando o método de otimização do problema do caixeiro viajante foi atingido, visto que, atualmente, na empresa estudada, não há roteirização desse veículo para a entrega do produto, logo, com a aplicação do PCV em duas amostras distintas de dois dias aleatórios em rotas que já haviam acontecido, demonstrou-se que poderia ter percorrido por um menor caminho, servindo, assim, como sugestão de melhoria para e redução do percurso e consequentemente no tempo de entrega.

O presente estudo buscou responder ao problema de pesquisa: de que maneira pode-se obter uma melhoria na roteirização de veículos de transporte rodoviário de uma distribuidora de óleo lubrificante a granel? Esta pergunta teve sua resposta, visto que foi demonstrado no estudo a redução com relação ao percurso realizado.

O uso do software LINDO® veio a acrescentar no entendimento acadêmico e agilizar na solução do problema, visto que o problema proposto é de difícil resolução e, quanto maior os pontos de paradas, maior a dificuldade.

As dificuldades e limitações encontradas na realização deste estudo foram a falta de informação documental referente à rota realizada nos dias das amostras e o acesso com relação aos custos da frota. Fica então como sugestão para trabalhos futuros, um aprofundamento com relação à perspectiva de custos relacionados a roteirização.

A realização deste estudo de caso foi de grande importância quando relacionado aos conhecimentos adquiridos no decorrer do curso de Engenharia de Produção, ficando claro também, a importância da disciplina de Pesquisa Operacional, visto que, no âmbito empresarial ainda se fala e se realiza pouco a respeito destes temas. Sendo assim, esse conhecimento vem a ser um diferencial ao profissional Engenheiro de Produção.

 

REFERÊNCIAS

 

ALVARENGA, Antonio Carlos; NOVAES, Antônio Galvão. Logística aplicada: suprimento e distribuição física. 3. ed. São Paulo: Blucher, 2000.

 

 

ARAÚJO, Rafael. Uma abordagem de resolução integrada para os problemas de roteirização e carregamento de veículos. 2010. 173f. Tese (Doutorado em Engenharia de Produção) - Universidade Federal do Rio Grande do Sul, Porto Alegre, 2010. Disponível em: <http://www.lume.ufrgs.br/bitstream/handle/10183/2587

1/000754011.pdf?sequence=1>. Acesso em: 07 maio 2017.

 

 

ARENALES, Marcos et al. Pesquisa operacional: para cursos de engenharia. 6. reimpressão. Rio de Janeiro: Elsevier, 2007.

 

 

BALLOU, Ronald. Gerenciamento da cadeia de suprimentos/logística empresarial. 5. ed. Porto Alegre: Bookman, 2006.

BALLOU, Ronald. Logística empresarial: transportes, administração de materiais e distribuição física. Tradução Hugo T. Y. Yoshizaki. 1. ed., 25. reimpressão. São Paulo: Atlas, 2011.

 

 

BANCO MUNDIAL. Relatório anual de 2016 do banco mundial. Washington, DC: Banco Mundial. Disponível em: <https://lpi.worldbank.org/international/global>. Acesso em: 19 mar. 2017.

 

 

BOWERSOX, Donald et al. Gestão logística da cadeia de suprimentos. Tradução: Luiz Claudio de Queiroz Faria. 4. ed. Porto Alegre: AMGH, 2014.

 

 

BRANCO, Fábio; GIGIOLI, Olívia. Roteirização de transporte de carga Estudo de caso: distribuidora de tintas e seu método de entregas. Rev. FAE. Curitiba, v. 17, n. 2, p. 56 - 81, jul./dez. 2014. Disponível em: <https://revistafae.fae.edu/revistafae/

article/download/18/18>. Acesso em: 20 set. 2017.

 

 

BELFIORE, Patrícia; FÁVERO, Luiz Paulo. Pesquisa operacional: para cursos de engenharia. Rio de Janeiro: Elsevier, 2013.

 

 

CAMPOS, Danilo. Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea. 2008. 136f. Tese (Doutorado em Engenharia) – Escola Politécnica da Universidade de São Paulo, São Paulo, 2008. Disponível em: <http://alvarestech.com/temp/vrptw/revisao_Tese_3D_FSMVR

PTW.pdf>. Acesso em: 17 set. 2017.

 

 

CNT. Confederação Nacional do Transporte. Plano CNT de Transporte e Logística. Disponível em: <http://www.cnt.org.br/Paginas/plano-cnt-transporte-logistica>. Acesso em: 07 set. 2017.

 

 

CUNHA, C. B.; BONASSER, U; ABAHÃO, F. T. M. Experimentos computacionais com heurísticas de melhorias para o problema do caixeiro viajante. In: XVI CONGRESSO DA ANPET – ASSOCIAÇÃO NACIONAL DE PESQUISA E ENSINO EM TRANSPORTE. Anais Eletrônicos... Natal, outubro de 2002. Disponível em: <https://www.researchgate.net/publication/228434832_Experimentos_computacionais_com_heuristicas_de_melhorias_para_o_problema_do_caixeiro_viajante>. Acesso em: 17 set. 2017.

 

 

COLARES, Flávio et al. Uma heuristica aplicada ao problema do caixeiro viajante. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL. Gramado: 2005. Anais Eletrônicos... Fortaleza: UFC, 2005. Disponível em: <http://www.repositorio.ufc.br/bitstream/riufc/13121/1/2005_eve_jclsilva.pdf>. Acesso em: 07 maio 2017.

 

 

DIAS, Marco Aurélio. Administração de materiais: uma abordagem logística. 5. ed. São Paulo: Atlas, 2010.

 

 

GHERESHI, Jonathan Soares; TÓFILO, Eduardo; LIMA, Ana Beatriz. Logística de transporte: a importância dos custos logísticos AJM TRANSPORTE LINS SP. Universitari@ - Revista científica do Unisalesiano, Lins – SP, ano 3., n. 6, jan/jul de 2012. Disponível em: <http://www.unisalesiano.edu.br/biblioteca/monografias/548/54

810.pdf>. Acesso em: 07 maio 2017.

 

 

GIL, Antonio Carlos. Como elaborar projetos de pesquisa. 4. ed. São Paulo: Atlas, 2002.

 

 

HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução a pesquisa operacional. 9. ed. São Paulo: Amgh, 2013.

 

 

JÚNIOR, Aloísio; SOUZA, Marcone. Softwares de Otimização: manual de referência. Disponível em: <http://www.decom.ufop.br/prof/marcone/Disciplinas/Otimi

zacaoCombinatoria/ManualdeSoftwaresdeOtimizacao.pdf>. Acesso em: 05 out. 2017.

 

 

KARP, R. M. On the Computational Complexity of Combinatorial Problems, Networks 5, 45-68, 1975.

 

 

KEEDI, Samir. Logística de transporte internacional: veículo prático de competitividade. 5. ed. São Paulo: Aduaneiras, 2015. 

 

 

LACHTERMACHER, Gerson. Pesquisa operacional na tomada de decisões. Rio de Janeiro: Campus, 2002.

 

 

LISBOA, Fabrício da Silveira. GRASP para o problema de roteamento de veículos com multi-comportamentos e restrição de janela de tempo. 2007. 97f. Dissertação (Mestrado em Engenharia de Produção) – Centro de Ciências e Tecnologia da Universidade Estadual do Norte Fluminense, Campos dos Goytacazes – RJ, 2007. Disponível em: <http://livros01.livrosgratis.com.br/cp034109.

.pdf>. Acesso em: 09 abr. 2017.

 

 

MARCONI, Marina; LAKATOS, Eva Maria. Fundamentos de metodologia científica. 7. ed. São Paulo: Atlas, 2010.

 

 

NOVAES, Antonio Galvao. Logística e gerenciamento da cadeia de distribuição: estratégia, operação e avaliação. Rio de Janeiro: Elsevier, 2007.

 

 

PAULA, Miguel Ângelo Almeida Faria. Estudo de roteirização de veículos empregando o TransCAD: contribuição para a distribuição urbana de cargas. 2009. 104f. Dissertação (Mestrado em Engenharia Civil) – Faculdade de Engenharia Civil da Universidade Federal de Uberlândia, Uberlândia - MG, 2009. Disponível em: <http://www.ppgec.feciv.ufu.br/node/269>. Acesso em: 19 mar. 2017.

 

 

PRODANOV, Cleber; FREITAS, Ernani. Metodologia do trabalho científico: métodos e técnicas da pesquisa e do trabalho acadêmico. 2. ed. Novo Hamburgo: Feevale, 2013.

 

 

RESENDE, Paulo T. V.; MENDONÇA, Guilherme Dayrell; CERQUEIRA, Marina Rodrigues. Relatório de pesquisa: análise estratégica dos canais de distribuição no Brasil. Fundação Dom Cabral. Minas Gerais, ano 6, nº 06, dezembro de 2006. Disponível em: <http://acervo.ci.fdc.org.br/AcervoDigital/Relat% C3%B3rios%20de%

%20Pesquisa/Relat%C3%B3rios%20de%20Pesquisa%202006/0606.pdf>. Acesso em: 19 mar. 2017.

 

 

REZENDE, Denis Alcides; ABREU, Aline França. Tecnologia da Informação Aplicada a Sistemas de Informação Empresariais: o papel estratégico da informação e dos sistemas de informação nas empresas. 5. ed. São Paulo: Atlas, 2008.

 

 

ROSA, Adriano. Gestão do transporte na logística de distribuição física: uma análise da mionimização do custo operacional. 2007. 90p. Dissertação (Mestrado em Gestão de Desenvolvimento Regional) – Departamento de Economia, Contabilidade e Administração da Universidade de Taubaté, Taubaté – SP, 2007. Disponível em:

<http://www.ppga.com.br/mestrado/2007/rosa-adriano_carlos.pdf>. Acesso em: 07

maio 2017.

 

 

SILVA, Bruno. Otimização de rotas utilizando abordagens heurísticas em um ambiente georreferenciado. 2013. 105f. Dissertação (Mestrado em Ciência da Computação) – Universidade Estadual do Ceará, Fortaleza, 2013. Disponível em: <http://www.uece.br/macc/index.php/arquivos/doc_download/202-otimizacao-de-rotas-utilizando-abordagens-heuristicas-em-um-ambiente-georreferenciado>. Acesso em: 11 set. 2017.

 

 

SOUSA, Tatiana S. A. G. Distribuição de GPL a granel: caso da GALP energia. 2014. 56f. Trabalho Final de Mestrado (Mestrado em Decisão Econômica e Empresarial) – Lisboa School of Economics & Management, Lisboa – PT, 2007. Disponível em: <https://www.iseg.ulisboa.pt/aquila/getFile.do?fileId=550463&method

=getFile>. Acesso em: 09 abr. 2017.

 

 

TAHA, H. A. Pesquisa Operacional. 8ª ed. São Paulo: Pearson Prentice Hall, 2008.

 

 

VALENTE, Amir et al. Gerenciamento de transportes e frotas. 3. ed. São Paulo: Cengage Learning, 2016.


APÊNDICES

 

Apêndice A – Carta de Autorização de Participação da Empresa XYZ no Estudo de Caso

 

Autorização de Participação da Empresa no Estudo de Caso

 

Fortaleza, 03 de novembro de 2017.

 

Eu, RAYNNER BRAGA ARARIPE, aluno do Curso de Graduação em Engenharia de Produção do Centro Universitário 7 de Setembro (UNI7), sob orientação da Profa. Natália Varela da Rocha Kloeckner, solicito permissão para obter voluntariamente de sua empresa informações que serão utilizadas, após tratamento, na forma de estudo de caso a ser inserido na pesquisa em andamento sobre "Problema do Caixeiro Viajante (PCV) aplicado a otimização de roteiros de veículos de transporde rodoviário de uma distribuidora de óleo lubrificante a granel em Fortaleza e região metropolitana”.

As informações declaradas nesta pesquisa serão mantidas em sigilo, como também o anonimato da empresa e do respondente.

No aguardo do aceite, agradecemos a atenção dispensada.

 

 

Raynner Braga Araripe

Aluno-Pesquisador

 

 

 

Profa. Natália Varela da Rocha Kloeckner

Orientador(a) da Pesquisa

 

 

 

L S F S

Gerente de RH

Empresa XYZ

 


Apêndice B – Instrumento de Pesquisa – Entrevista não estruturada despadronizada focalizada

 

 


PESQUISA SOBRE O PROBLEMA DO CAIXEIRO VIAJANTE (PCV) APLICADO A OTIMIZAÇÃO DE ROTEIROS DE VEÍCULOS DE TRANSPORTE RODOVIÁRIO DE UMA DISTRIBUIDORA DE ÓLEO LUBRIFICANTE A GRANEL EM FORTALEZA E REGIÃO METROPOLITANA

 

ARTIGO CIENTÍFICO

Curso de Graduação em Engenharia da Produção

Data:

I – Característica do entrevistado

1 – Nome

2 – Qual o cargo que exerce na empresa?

3 – Há quanto tempo trabalha na empresa?

ll – Tópicos abordados com os entrevistados para a coleta de informações.

4 – Como se sabe os clientes a serem visitados?

5 – De que maneira é formada a rota atual?

6 – Quais os clientes foram visitados?

7 – Qual a rota realizada para esses clientes?

8 – Qual veículo é utilizado para a entrega?

9 – Existe alguma forma de acompanhar o andamento das entregas?

10 – Qual a importância desta entrega nos serviços logísticos?


Apêndice CEtapas de geração do pedido

 

1.   Acionar o consultor comercial solicitando o produto.

 

1.   Receber pedido do cliente;

2.   Imputar em sistema;

3.   Confirmar a validação do cliente junto ao Contas a Receber;

4.   Verificar se o pedido foi encaminhado para faturamento.

 

1.   Faturar o pedido;

2.   Providenciar o carregamento do caminhão;

3.   Incluir na rota;

4.   Entregar pedido no cliente.

 
 

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Apêndice DModelagem da amostra 1 no LINDO®

 

 

 

 

 

 

 

 

 

 

Apêndice DContinuação da modelagem da amostra 1 no LINDO®

 

 

 

 

 

 

 

 

 

Apêndice DContinuação da modelagem da amostra 1 no LINDO®

 

 

 

 

 

 

 

Apêndice DContinuação da modelagem da amostra 1 no LINDO®

 

 

 

 

Apêndice DContinuação da modelagem da amostra 1 no LINDO®

 

 

 

Apêndice DContinuação da modelagem da amostra 1 no LINDO®

 

 

 

 

 

Apêndice EModelagem da amostra 2 no LINDO®

 

 

 

 

 

 

 

 

 

Apêndice EContinuação da modelagem da amostra 2 no LINDO®

 

 

 

 

 

 

 

 

 

 

 

Apêndice EContinuação da modelagem da amostra 2 no LINDO®

 

 

Apêndice EContinuação da modelagem da amostra 2 no LINDO®

 

 

 

 

 

 

 

Apêndice FMelhor rota obtida amostra 1

 

Fonte: Google Maps®, 2017 (adaptado pelo autor).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Apêndice GMelhor rota obtida amostra 2

 

Fonte: Google Maps®, 2017 (adaptado pelo autor).