UM ESTUDO SOBRE O PROBLEMA
DO CAIXEIRO VIAJANTE
Aluna:
Natalle Cristina Moretti Cammarosano Kopczynski
Orientadora: Profa. Lílian Kátia de Oliveira
2010
INTRODUÇÃO
Ultimamente, problemas de roteamento, que são comuns em
sistemas logísticos, vêm sendo amplamente estudados nas
empresas para aumentar a eficiência da prestação de seus
serviços.
Para tal, são aplicados alguns métodos, dos quais pode-se
obter soluções factíveis.
O problema de roteamento estudado foi o Problema do
Caixeiro Viajante.
OBJETIVOS
•
•
•
•
•
Estudo dos principais conceitos de Teoria de Grafos;
Estudo dos modelos matemáticos utilizados na
resolução do Problema do Caixeiro Viajante;
Pesquisa sobre os principais métodos de solução da
literatura;
Implementação dos métodos exatos, heurísticos e
probabilísticos para sua resolução (linguagem de
modelagem GAMS);
Comparação das soluções obtidas a partir dos métodos
executados.
JUSTIFICATIVAS
O Problema do Caixeiro Viajante, devido à sua potencialidade de
aplicações, bem como pela dificuldade de resolução, tem sido bastante
estudado na literatura em diferentes campos do saber, como a
otimização, matemática, engenharia, inteligência artificial.
Algumas aplicações são: programação de operações de máquinas em
manufatura; programação de transporte entre células de manufatura;
otimização do movimento de ferramentas de corte; maioria dos
problemas de roteamento de veículos; solução de problemas de
sequenciamento de DNA; solução de problemas de programação e
distribuição de tarefas em plantas; trabalhos administrativos, entre
outros.
Portanto, procedimentos de solução para o Problema do Caixeiro
Viajante que determinam boas soluções em um tempo computacional
razoável são importantes.
PROBLEMA DO CAIXEIRO
VIAJANTE
Objetivo: cobrir todos os nós de uma rede, a fim de alcançar um
objetivo pré determinado (menor distância ou menor custo), passando
somente 1 vez em cada nó.
Decorre de uma situação hipotética de um caixeiro, que deve sair de
uma cidade, passar por várias outras e voltar ao seu ponto de origem.
Considera-se que as distâncias e custos entre uma cidade e outra são
conhecidos.
Sua complexidade de solução aumenta de acordo com a extensão do
problema.
As aplicações práticas são: entrega de produtos em depósitos,
reposição de materiais em postos de trabalho, roteiro de condução
escolar, entre outros.
MODELOS
Grafo Completo não Orientado
Seja G(N, A) um grafo completo não orientado com n nós e δ (v) o conjunto dos arcos
incidentes no nó v N . Seja cij o custo do arco (i,j) e considere:
O Problema do Caixeiro Viajante não orientado pode ser modelado como:
onde S é qualquer subconjunto de N, a partir de 3 elementos, que descreve os possíveis ciclos.
MODELOS
Grafo Completo Orientado
Seja G(N, A) um grafo completo orientado com n nós. Seja cij o custo do arco (i,j) e considere:
O Problema do Caixeiro Viajante orientado pode ser modelado como:
MÉTODOS
Algoritmo 1 – Problema da Mínima Árvore Geradora (MST):
Consiste em encontrar uma árvore de comprimento mínimo, entre todas
as possíveis árvores geradoras do grafo G(N,U).

Passo 1: Escolha arbitrariamente o nó i. Encontre o nó mais próximo de
i, digamos j, e conecte-o a i.

Passo 2: Se todos os nós estiverem conectados, pare. Neste caso a
MST foi encontrada. Caso contrário, vá para o passo 3.

Passo 3: Encontre o nó, entre os nós ainda não conectados, que esteja
mais próximo dos nós já conectados, e conecte-o aos nós já
conectados. Volte para o passo 2.
MÉTODOS
Algoritmo 2 – TSP1
Considere um grafo com n nós, completo e satisfazendo a desigualdade
triangular.
 Passo 1: Encontre a mínima árvore geradora ligando os n nós. Chamea de T.
 Passo 2: Seja m o número de nós de T de grau ímpar (m sempre é par).
Encontre o minimum length pairwise matching desses m nós e
identifique os m/2 caminhos mínimos do casamento ótimo. Chame-o de
M.
 Passo 3: Crie o grafo H com a união de T e M. Note que H não contém
nós de grau ímpar. Encontre um circuito de Euler em H. Este circuito é
uma solução aproximada para o TSP1.
 Passo 4: Caso haja nós visitados mais de uma vez no circuito de Euler,
melhore o roteiro levando em conta a desigualdade triangular, de
maneira a obter um ciclo Hamiltoniano para o grafo H. Este ciclo
também é uma solução aproximada para o TSP1.
MÉTODOS
TSP Probabilístico
Considere n pontos que são aleatoriamente e independentemente
distribuídos sobre uma área A, com a localização de cada ponto
uniformemente distribuído em A.
Pode ser mostrado que:
Observação: Na prática, a expressão fornece boas aproximações se os n
pontos estiverem razoavelmente bem espalhados sobre a região A
(mesmo nos casos onde os n pontos não são tão independentemente
localizados, ou quando a distribuição de probabilidade não é exatamente
uniforme).
PRÓXIMOS PASSOS

Implementação de Algoritmos Básicos: para tal, será
usada a linguagem de modelagem GAMS;

Resultados;

Relatório final.
REFERÊNCIAS
BIBLIOGRÁFICAS
•
CUNHA, C. B.; BONASSER, U. O.; ABRAHÃ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 Transportes. Natal, 2002.
•
FERNANDES, F.; MORABITO, R. Linguagens de modelagem GAMS e
LINGO: Aplicação a um problema de balanceamento de linha de montagem.
Cadernos de Engenharia de Produção n.20, UFSCar. São Carlos, 1993.
•
GOLDBARG, M. C.; LUNA, H. P. L. Otimização combinatória e
programação linear: modelos e algoritmos. 2ª edição revisada. Rio de
Janeiro: Elsevier, 2005.
•
PRESTES, A. N. Uma Análise Experimental de Abordagens Heurísticas
Aplicadas ao Problema do Caixeiro Viajante. 2006. Dissertação
(Mestrado em Sistemas e Computação) - Pós- Graduação em Sistemas e
Computação, Universidade Federal do Rio Grande do Norte, Natal, 2006.