O Caixeiro Viajante

1. INTRODUÇÃO

Nos dias de hoje a competitividade entre empresas está cada vez maior, para conseguir se destacar é preciso sempre inovar ter um diferencial, para evitar que a empresa fique obsoleta e com estratégias que não funcionam.

A logística é algo que vem se destacando nesse processo de inovação das empresas, já que com ela é possível reduzir custos e acelerar o processo, o que deixa o cliente bem mais satisfeito e além disso aumenta a eficiência da operação, a junção de tudo isso faz com que o lucro da empresa aumente.

Os problemas de otimização combinatória apresentam uma função objetivo de maximização ou de minimização que tende a ser otimizada por meio de um conjunto de restrições e são representadas através de grafos. Existem diversos problemas em grafos, como por exemplo, problema do caixeiro viajante, problema do caminho mínimo, problema do fluxo máximo, entre diversos outros.

Um problema muito simples e que vem sendo muito utilizado é o do caixeiro viajante, ele é fácil de compreender e de se descrever, mas consegue resolver problemas com alto grau de dificuldade.

Neste artigo serão relatados casos que envolvem a área logística na entrega de produtos, onde o foco será mostrar a solução dos mesmos através do problema do caixeiro viajante.

1. PROBLEMA DO CAIXEIRO VIAJANTE (PCV)

O Problema do Caixeiro Viajante tem sido muito utilizado no experimento de diversos métodos de otimização por ser, principalmente, um problema de fácil descrição e compreensão, mas de grande dificuldade de solução, uma vez que é NP-Árduo (KARP, 1975).

Esse problema é representado através de um grafo e cada vértice é considerado como uma cidade e cada aresta é considerada uma rota. O caixeiro viajante deve sair da sua cidade, visitar cada uma das outras cidades e retornar à cidade de origem, de forma a percorrer a menor distância possível.

O PCV pode ser considerado simétrico ou assimétrico. O simétrico ocorre quando para todos os nós ( i, j ), os custos Cij e Cij forem iguais. Se ocorrer o contrário o problema é assimétrico.

[pic 1]                         [pic 2]

               [pic 3][pic 4]

A dificuldade na resolução do PCV aumenta à medida que o número de nós (pontos) aumenta. Para um problema com "n" nós e uma ligação entre cada par de nós, é possível calcular o número de rotas possíveis por (n – 1)! /2, pois existem (n – 1) possibilidades para o primeiro nó, (n – 2) para o segundo, etc. A divisão por 2 surge devido a cada rota possuir uma rota reversa equivalente com a mesma distância. Assim, uma situação envolvendo 10 nós tem aproximadamente 181.000 soluções, envolvendo 20 nós tem 6,08x1016 soluções, assim por diante (HILLIER, 2010).

Uma forma de se resolver tal problema seria simplesmente enumerar todas as soluções possíveis e determinar aquela de menor custo. Nesse caso, seriam determinadas todas as rotas possíveis e, com o auxílio do computador, poderia ser realizado o cálculo do comprimento de cada rota e verificada qual seria a menor rota obtida. Ao serem consideradas todas as rotas existentes, é possível afirmar que se está reduzindo um problema de otimização a um problema de enumeração (TAUFER e PEREIRA, 2011).

1.  O PROBLEMA DO CAIXEIRO VIAJANTE APLICADO AO GRUPO CRÍTICO DO SISTEMA DE ENTREGAS DE UM RESTAURANTE

1.   O PROBLEMA

O problema do caixeiro viajante ocorreu em um restaurante que realiza entrega de quentinhas em uma cidade localizada na zona da mata mineira. Para conhecimento dos dados fizeram a análise durante um mês, salvando os dias de feriados. Afim de obter informações como data, endereço dos pedidos com enfoque nos bairros.

Atualmente, a roteirização adotada pelo restaurante fica sob responsabilidade de um funcionário que, devido ao seu vasto conhecimento da cidade, tem a capacidade de discernir e determinar em qual rota deverá ser incluído cada pedido adicional. Tais rotas são determinadas levando em consideração os extremos, e os pedidos adicionais cujos endereços estão no trajeto e horário de ida ou retorno do entregador, são incluídos na rota. Não há uma delimitação de áreas que ficam sob responsabilidade de determinado entregador, ou a setorização da cidade para fins de entrega.

 A empresa não detém nenhuma ferramenta informacional para inclusão e gerenciamento dos pedidos. Todo pedido é recebido por uma colaboradora responsável pelo contato telefônico com os clientes, esses pedidos são registrados em blocos padronizados da empresa, compostos por duas vias, a primeira é destacada e distribuída aos colaboradores da cozinha, para montagem da marmitex e inserção na rota, a segunda via é guardada para posterior análise dos rendimentos da empresa.

Para o levantamento de dados utilizado no estudo de caso, foi utilizada a segunda via dos pedidos. As informações coletadas foram as ruas e bairros para entrega dos pedidos, o horário, a quantidade de marmitex por pedido e o valor total do pedido. Através destes dados, realizou-se uma análise a fim de verificar quais são os bairros responsáveis pelo maior fluxo de entregas, quais os horários e dias de pico, e principalmente desenvolver e propor a setorização da cidade com base nos perfis de consumo dos bairros.

Para a tabulação e análise dos dados, utilizou-se o MS Excel em sua versão 2013, ferramenta computacional que permitiu a análise eficiente dos dados e a confecção do gráfico e tabelas presentes neste artigo, assim como o suplemento Solver, utilizado para testes de hipóteses. De acordo com a Microsoft (2017), este suplemento trabalha sobre um grupo determinado de células denominadas “variáveis”, ajustando-as para obter-se o melhor resultado na célula objetivo e atender às restrições inseridas. Essa ferramenta pode ser utilizada para se minimizar ou maximizar um resultado, conforme a fórmula inserida na célula objetivo.

1. ANÁLISE DOS DADOS DO RESTAURANTE

Foram tabulados 1.588 pedidos, somando 2.254 marmitex fornecidas. Através da tabulação destes dados, resultados gráficos foram obtidos. No Gráfico 1 é possível verificar a quantidade de marmitex pedidos por bairro no período analisado, e verifica-se significativo destaque para o centro da cidade, região com grande número de comércios.

[pic 5]GRÁFICO 1: Número de Marmitex entregues por bairro no período. Fonte: Os Autores

 Optou-se pela utilização da ferramenta solver, suplemento do MS Excel, devido a facilidade de inserção do modelo matemático. Inicialmente, os bairros da cidade foram agrupados, e construída uma matriz de distâncias entre cada ponto. Essa matriz serviu para definição da menor rota. A opção de agrupamento foi escolhida para "delimitar" as regiões de maior fluxo comercial, e a proposição foi - Grupo 1: Centro (CNT), Bandeirantes (BDR), Popular (PPL), Vila Domingos Lopes (VDL), Haidê (HDE); Grupo 2: São Diniz, Pampulha, Sol Nascente; Grupo 3: Vila Reis, Bela Vista, Santa Cristina; Grupo 4: Granjaria, Leonardo, Guanabara, Vila Minalda, Dico Leite; Grupo 5: Vila Tereza, Beira Rio, Paraíso, Distrito Industrial, Taquara Preta, São Cristóvão, São Marcos. Após agrupados, optou-se por aplicar a metodologia do caixeiro viajante entre os bairros que compõe o Grupo 1, visto que esse é o grupo crítico, apresentando o maior número de unidades fornecidas e no horário de pico.