modeloPCV Caixeiro Viajante

PROBLEMA DO CAIXEIRO VIAJANTE

Palhoça
2013

sumário
1 introdução 3
2 O PROBLEMA DO CAIXEIRO VIAJANTE 3
2.1 O PROBLEMA DO CAIXEIRO VIAJANTE COM DESIGUALDADE DE TRIÂNGULOS 4
2.2 O PROBLEMA GERAL DO CAIXEIRO VIAJANTE 6
3 CONCLUSÃO 7
REFERÊNCIAS 8

1 introdução
O problema do caixeiro viajante é um dos mais conhecidos e estudados na área de otimização matemática combinatória, estando dessa forma diretamente ligada ao ciclo hamiltoniano. O problema tenta determinar a menor rota para percorrer uma série de cidades, retornando a cidade de origem. Visitando cada cidade exatamente uma única vez, com o objetivo de encontrar a maneira mais barata de visitar todas as cidades e voltar ao seu ponto de origem.

Este problema tem inúmeras aplicações práticas, como minimização de rotas de veículos, confecção de sistemas digitais, sequenciamento de atividades e outros. (PACHECO, 2010).
Embora possa ser explicado de forma simples o Problema do Caixeiro Viajante (PCV) pertence à classe dos problemas NP-Completo inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.
Devido à sua complexidade computacional, o PCV tem sido amplamente abordado no desenvolvimento de algoritmos aproximativos e meta-heurísticas. (GUEDES, 2005, p. 16).

Segundo os teoremas até então apresentados, é improvável existir um algoritmo rápido para a resolução do problema do caixeiro viajante.

2 O PROBLEMA DO CAIXEIRO VIAJANTE
Antigamente muitos vendedores, chamados de caixeiros viajantes, ganhavam a vida oferecendo seus produtos em diferentes cidades. Imagine que um caixeiro viajante escolhesse algumas cidades e precisasse encontrar o caminho mais curto para suas andanças. Esse é um problema matemático, conhecido como o problema do caixeiro viajante (PCV).

O problema do caixeiro viajante (do inglês travelling