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.

Este problema foi proposto formalmente em 1930, e desde então tem sido alvo de intensas pesquisas. Hoje ele é o assunto que mais obteve publicações em jornais técnicos no mundo, sendo assim o problema mais pesquisado do mundo, dadas as inúmeras implicações que ele tem, além de fazer a rota de viagens com custo mínimo. O atual recorde mundial de solução de um problema deste tipo data de 2006 e conseguiu obter a solução para o caso com 85.900 cidades (pontos).

O Problema do Caixeiro Viajante pode apresentar caminhos simétricos (a mesma distância na ida e na volta entre duas cidades) ou caminhos assimétricos (distâncias diferentes). A versão assimétrica apresenta maior grau de realidade, pois no trânsito das cidades muitas vezes não podemos utilizar o mesmo caminho na ida e na volta, tendo, portanto, distâncias diferentes. Ao contrário do que possa parecer, a versão simétrica é mais difícil de resolver, pois os caminhos de distâncias idênticas criam ciclos que precisam ser evitados.

série Pesquisa Operacional do Logística DescomplicadaVeja na figura à esquerda um exemplo com alguns poucos pontos e todas as combinações possíveis de série pesquisa operacional - caixeiro viajantetrajetos. Perceba que mesmo um problema simples assim é muito difícil de solucionar usando nosso raciocínio. À direita veja a solução ótima do Problema do Caixeiro Viajante.

Assim, dada essa dificuldade, existem muitas heurísticas pare resolver este problema (para uma definição de heurística consulte o primeiro artigo da série pesquisa operacional). Para citar alguns exemplos:

– algoritmo do vizinho mais próximo: produz boas soluções na maioria dos casos. Consiste em visitar o vizinho mais próximo ainda não visitado. Possui uma implementação bastante simples e é muito rápido.

– algoritmos genéticos: a partir de um conjunto com algumas soluções, mesmo que não sejam boas, e combina partes destas soluções, gerando soluções diferentes, assim como os genes criam novas gerações. As melhores combinações são guardadas e o processo repete-se várias vezes.

Para empresas que devem abastecer muitos clientes ou que têm muitas filiais a escolha dos caminhos passa a ter alguma relevância nos custos. Este problema serve como base para o próximo que veremos na Série Pesquisa Operacional, que tratará de formas eficientes de se despachar veículos para atender os clientes. Confira na próxima semana.

Na próxima 4ª feira, dia 3 de março, o artigo sobre o Problema de Roteamento de Veículos (PUBLICADO);

Na 4ª feira seguinte, dia 10 de março, a matéria sobre o Problema de Estoques e Roteamento (PUBLICADO).

Fique ligado e não perca os exemplos que serão citados! Assine nosso newsleter (no começo da página à esquerda).

Gostou dessa matéria? Doe qualquer valor e ajude a manter o Logística Descomplicada gratuito:

Leandro C. Coelho, Ph.D., é Professor de Logística e Gestão da Cadeia de Suprimentos na Université Laval, Québec, Canadá. Conheça mais no menu Sobre (acima).