Apresentação problema

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Caixeiro Viajante
O Problema do caixeiro viajante
O problema do caixeiro viajante é um problema que tenta determinar a menor rota para percorrer uma série de cidades(visitando cada uma pelo menos uma vez), retornando à cidade de origem.
A origem do nome travelling salesman problem “problema do caixeiro viajante” é desconhecida.
A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena
O Problema do Caixeiro Viajante é importante devido a pelo menos três de suas características: grande aplicação prática, grande relação com outros modelos e grande dificuldade de solução exata.
					Aplicações do PCV
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.
Otimização de perfurações de furos em placas de circuitos impressos.
Na maioria dos problemas de roteamento de veículos.
Na solução de problemas de sequenciamento de DNA
Na solução de problemas de programação e distribuição de tarefas em plantações.
A simulação ilustra um circuito hamitoniano a ser percorrido por uma ferramenta responsável pela perfuração de uma placa de circuito impresso.
O PCV pertence a classe de problemas considerados difíceis ou intratáveis. A busca de uma solução ótima pode “custar caro”, pois a medida que aumentamos o número de vérices o tempo para a resolução do problema aumenta de forma gritante.
Para problemas difíceis, são utilizadas algumas técnicas para tentar resolver o problema em tempo hábil como por exemplo a elaboração de Algoritmos de Aproximação. 
Algoritmos de aproximação são aqueles que apresentam uma solução correta com a garantia de que esta solução está dentro de uma determinada porcentagem da solução ótima. 
Métodos para a solução do PCV
As abordagens aplicadas ao PCV podem ser dividas em, pelo menos, duas grandes categorias: Métodos Exatos e Métodos Heurísticos.
Métodos Exatos
Uma forma natural e intuitiva para obter soluções ótimas para instâncias do pcv seria testar todas as possibilidades.
Uma vantagem importante dos algoritmos exatos que usam Programção Inteira está no fato de que se pode provar que soluções ótimas podem ser obtidas se o algoritmo tiver sucesso na execução.
Uma das maiores desvantagens dos métodos exatos está no fato de que, para muitos problema, o tamanho das instâncias que podem ser solucionadas é limitado pelo custo computacional.
Métodos Heurísticos
Um exemplo de abordagem heurística aplicada ao PCV é a busca Tabu que foi introduzida por Hansen (1986) e Glover(1990). A idéia geral é ter um mecanismo para auxiliar o processo de busca, evitando a realização de movimentos feitos recentemente.
O Algoritmo de Lin e Kernighan
Algoritmos de busca local se baseiam em modificação simples no percuros, realizando trocas entre as cidades deste percurso, com o objetivo de reduzir o comprimento do mesmo (minimizar a distância dos percurso pelas n cidade).