O Problema do Caixeiro Viajante é simples de descrever mas bastante difícil de resolver. De facto, não é conhecido nenhum algoritmo polinomial para o resolver, pelo que as soluções são tipicamente obtidas usando algoritmos de aproximação. Neste seminário iremos não só estudar a qualidade das soluções obtidas com os algoritmos 2-opt e 3-opt mas também como obter estimativas para o custo optimal.