O problema do caixeiro-viajante (TSP) é um problema algorítmico incumbido de encontrar a rota mais curta entre um conjunto de pontos e locais que devem ser visitados. Na declaração do problema, os pontos são as cidades que um vendedor pode visitar. O objetivo do vendedor é manter tanto os custos de viagem quanto a distância percorrida o mais baixo possível.
Focalizado na otimização, o TSP é freqüentemente usado na ciência da computação para encontrar a rota mais eficiente para os dados viajarem entre vários nós. As aplicações incluem a identificação de métodos de otimização de rede ou hardware. Foi primeiramente descrito pelo matemático irlandês W.R. Hamilton e pelo matemático britânico Thomas Kirkman nos anos 1800 através da criação de um jogo que era resolúvel ao encontrar um ciclo Hamilton, que é um caminho não sobreposto entre todos os nós.
TSP tem sido estudado por décadas e várias soluções têm sido teorizadas. A solução mais simples é tentar todas as possibilidades, mas este é também o método mais demorado e caro. Muitas soluções utilizam heurística, que fornece resultados de probabilidade. No entanto, os resultados são aproximados e nem sempre ótimos. Outras soluções incluem branch and bound, algoritmos de Monte Carlo e Las Vegas.
Rather do que focar em encontrar a rota mais eficaz, TSP muitas vezes está preocupado em encontrar a solução mais barata. Nos TSPs, a grande quantidade de variáveis cria um desafio ao encontrar a rota mais curta, o que torna as soluções aproximadas, rápidas e baratas ainda mais atraentes.