caixeiro viajante

Logística também se aprende com a natureza

Por Paulo Sérgio Gonçalves *

formigueiro e formigasO homem com todo o seu potencial criativo desenvolveu máquinas maravilhosas. Voam, computam, fazem diagnósticos, controlam a produção, centralizam o processo decisório, flexibilizam as operações complexas, etc. Grande parte desse arsenal tecnológico foi desenvolvido a partir das pesquisas realizadas na natureza, muito especialmente, no reino animal.

A frustração do homem em não poder voar – mitologicamente reproduzida na fábula de Ícaro – tornou-se uma realidade adaptada da capacidade e flexibilidade que os pássaros possuem em vôos de longas distâncias e mesmo em grandes altitudes como é o caso do da águia. Sua visão é tão apurada que consegue ver um peixe a várias centenas de metros de altitude e mesmo perceber a presença de um coelho a uma distância de 1,6 km. Os exemplos são inúmeros: estudo do comportamento dos tubarões para descobrir o processo de altíssima tecnologia que possui em detectar a longa distância a presença de um peixe se debatendo. Sua incrível aerodinâmica permitiu projetar novas aeronaves de alta performance.

Na logística não é diferente!

Série Pesquisa Operacional – Problema do Caixeiro Viajante

Na semana passada vimos uma introdução e a definição do que é a pesquisa operacional. Hoje conheceremos um pouco mais sobre o Problema do Caixeiro Viajante (Traveling Salesman Problem).

Na definição padrão do problema, imagine que você tem uma lista de cidades para visitar, e que você conhece a distância entre cada par de cidades. Você precisa visitar todas as cidades, sem passar pela mesma cidade duas vezes, viajando o menor tempo possível.

Este problema é muito importante para a logística, pois ajuda a definir as melhores rotas possíveis, mas do ponto de vista teórico é muito mais amplo que isto.

Em empresas de transportes e entregas, o termo milk run é usado para descrever o trajeto que passa por todas as estações para coletas de produtos, para depois entregá-los num ponto específico. O milk run, ou corrida do leite, seria passar por várias fazendas coletando leite e depois entregar o grande volume coletado numa empresa de laticínio. Este assunto foi tratado recentemente no blog Universo da Logística.

Este mesmo problema do caixeiro viajante é usado para otimizar a fabricação de microchips, obtendo os caminhos mais curtos para os circuitos integrados, a otimização de padrões de corte em chapas e placas, economizando material quando obtém o melhor aproveitamento possível, além de economizar o uso e troca das facas ou lasers que fazem o corte, e em uma versão levemente modificada ele ajuda a fazer o sequenciamento do DNA. Um problema típico com algumas centenas de pontos (cidades) pode levar muitas horas para ser resolvido, pois as combinações possíveis crescem muito rapidamente.

Série Pesquisa Operacional – uma visão geral (ATUALIZADO)

equações pesquisa operacional - Logística DescomplicadaA Pesquisa Operacional (PO) é a área que analisa formas de modelar os sistemas do mundo real em termos matemáticos, para identificar mais claramente as relações entre diferentes elementos com o objetivo de melhorar ou otimizar seu desempenho. Ela faz uso de modelos matemáticos, estatísticos e de algoritmos para identificar pontos de melhoria e ajudar na tomada de decisões empresariais.

Esta área está intimamente ligada à logística, pois muitos sistemas produtivos, industriais e gerenciais podem fazer uso das técnicas de Pesquisa Operacional para alcançar um desempenho superior. De fato, muitos softwares utilizados por empresas têm complexos algoritmos por trás, para determinar a melhor quantidade de produtos para se manter em estoques, os melhores volumes de produção (e seu agendamento), fazer roteamento de veículos, dentre outros.

A Pesquisa Operacional normalmente busca encontrar o valor máximo (de lucro, performance, aproveitamento) ou mínimo (de risco, de custo). É importante ressaltar que do ponto de vista da PO, quando se fala em máximo ou mínimo está implícito que não existe nenhuma outra solução melhor, ou seja, a solução encontrada é provada matematicamente como sendo a melhor de todas as soluções possíveis. Esta solução é chamada de ótima e o sistema é dito otimizado.