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.
Veja na figura à esquerda um exemplo com alguns poucos pontos e todas as combinações possíveis de 
trajetos. 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).
13 respostas em “Série Pesquisa Operacional – Problema do Caixeiro Viajante”
Parabéns pelo site. Descobri a pouco quando pesquisava sobre o assunto. Pretendo fazer um mestrado aqui em Fortaleza na UFC cujo grupo é Geslog (Mestrado em logística e Pesquisa Operacional). Talvez você conheça. Se possível, poderia me dar uma dica: é que não possuo trabalhos publicados, nem apresentados, nem frequentei os laboratórios deste grupo durante a graduação. Sendo assim sei que tenho menos chances do que outros candidatos que já possuem esta aproximação com os professores e pesquisas do grupo. Tem alguma sugestão para mim? Grato.
Muito interessante este problema. Se olharmos para o lado matemático, podemos criar algoritmo que resolve o problema rapidamente (assim como é feito pelos softwares da área).
Entre várias soluções, se imaginarmos coordenadas no plano cartesiano para cada ponto de entrega:
– Contabiliza-se 13 pontos de entrega.
– Como não há retorno ao mesmo ponto de entrega, então percebe-se que há 13 fatorial possibilidades de entrega, claro que a grande maioria podemos deduzir heuristicamente que são inviáveis.
Mas por um simples modelo matemático, o problema é resolvido rapidamente, calculando a distância entre cada possibilidade e mostrando assim o resultado final.
Mas como se trata de transporte, devemos inserir variáveis como trânsito e tempo de entrega em cada ponto. Logo se for feito uma coleta de dados, baseado numa situação real, provavelmente pontos próximos não é necessariamente o melhor, sendo que o desenho formado pode haver mudanças translacionais tornando-o menos óbvio.
Abraços.
[…] Problema do Caixeiro Viajante (Traveling Salesman Problem), que pela definição padrão busca uma rota para visitar todas as cidades de uma região, sem […]
Só otimizador, possuiu vários algoritmos como simplex, dual, barrier e també é possível utilizar heurísticas…eu não sei quantas variáveis ele suporta mas já trabalhei com modelos de 350 mil e rodou muito rápido.
Interessante,
Eu só usei o CPLEX e o GUROBI. Vou dar uma olhada nesse aí a próxima vez que tiver um problema pra resolver, só pra comparar.
Ok é importante observar que o SNO ( Strategic Network Optimization ) foi adiquirido pela Oracle ou seja pode buscá-lo diretamente no site da oracle.com
Roteirizador que é o que você procura acredito que tenha OTM da oracle, mas se realmente quer saber como funciona o SNO eu fiz um pequeno vídeo explicando o básico.
http://www.youtube.com/watch?v=VlJltGHA9vo
Interessante como os grandes players estão ligados nas ferramentas de otimização. Há pouco tempo o CPLEX foi adquirido pela IBM.
Fica a dica do seu vídeo pro pessoal interessado nessa área! Gostei.
Já testei 2 softwares de programação linear e achei muito bons Microsoft Excel e JDEdwards SNO sendo que o primeiro possui uma restrição de apenas 150 variáveis.
Marcelo,
O problema do Excel é que o otimizador dele (o Solver) é MUITO restrito, muito fraco, e em MUITAS vezes uma solução que não é ótima.
Só uso ele em problemas muito pequenos e simples… mais de 20 variáveis e restrições eu nunca confio na solução dele.
Não conheço esse JDEwards. Ele é só otimizador é só otimizador ou tem um algoritmo de roteirização embutido?
Muito interressante a materia
ficarei ansioso pelo proximo post.
se puder me indicar algo mais,como softaware de roteirizaçao fico grato
Rodrigo, que bom que você está gostando da série Pesquisa Operacional.
Eu tenho muito conhecimento técnico da área, então se você quiser saber um pouco mais sobre os algoritmos, heurísticas e métodos de otimização eu posso lhe ajudar.
Nunca trabalhei com isso na prática, então não saberia dizer quais softwares são bons e eficientes.
Quem sabe alguns dos outros leitores possam dar suas sugestões? Quais softs vocês têm usado?
Abraços
Boa noite estou com duvida! gostaria que vc me desse um exemplo pratico de pesquisa operacional.