Caixeiro viajante

EXPERIMENTOS COMPUTACIONAIS COM HEURÍSTICAS DE MELHORIAS
PARA O PROBLEMA DO CAIXEIRO VIAJANTE

O problema do Caixeiro Viajante é um dos problemas mais estudados em otimização combinatória. Apesar de sua definição singela, o PCV representa, até hoje, um dos desafios da Pesquisa Operacional.
Reinelt ( 1994 ) vai mais além, ao afirmar que o PCV é um dos mais proeminentes dentre um amplo conjunto de problemas de Otimização Combinatória. Segundo o autor, o estudo do PCV tem atraído pesquisadores de diferentes campos, entre os quais pesquisa operacional, matemática, física, biologia, inteligência artificial, entre outros. Isso se deve ao fato de que, apesar da simplicidade da sua formulação, no PCV é possível encontrar a maioria das questões que envolvem otimização combinatória; consequentemente, o mesmo tem sido usado como benchmark para avaliação de novos algoritmos e estratégias de solução que envolvem busca tabu, algoritmos genéricos, simulated annealing, redes naturais, entre outros.
Entre esses problemas, pode-se citar o problema de produção que corresponde ao sequenciamento de n tarefas em uma única máquina, de forma minimizar o tempo total execução das mesmas.
O PROBLEMA DO CAIXEIRO VIAJANTE ( PVC )
O PVC pode ser definido o problema de encontrar o roteiro de menor distância ou custo que passa por um conjunto de cidades, sendo cada cidade visitada exatamente uma vez.
Sua origem é creditada a William Rowan Hamilton, que inventou um jogo cujo objetivo era de traçar um roteiro através dos vértices de um dodecaedro ( vértices equivalem a cidades ) que iniciasse e terminassem no mesmo vértice ( cidade ) sem, contudo,repetir uma vizita . O ciclo Hamiltoniano constitui uma solução para o jogo de Hamilton ( Golbarg e luna - 1999 ).
O PCV é chamado simétrico quando a distância entre dois nós ( ou cidades ) quaisquer i e j independe do sentido, isto é, quando dy = dji ; caso contrário o problema é denominado assimétrico. Segundo Helsgaun ( 2000 ),