O Problema do Vendedor Viajante (freqüentemente chamado de TSP) é um problema algorítmico clássico no campo da ciência da computação e da pesquisa operacional. Ele está focado na otimização. Neste contexto, uma melhor solução muitas vezes significa uma solução mais barata, mais curta ou mais rápida. O TSP é um problema matemático. Ele é mais facilmente expresso como um gráfico descrevendo a localização de um conjunto de nós.
O problema do vendedor ambulante foi definido no século XIX pelo matemático irlandês W. R. Hamilton e pelo matemático britânico Thomas Kirkman. O Jogo Icosiano de Hamilton era um quebra-cabeça recreativo baseado em encontrar um ciclo Hamiltoniano. A forma geral do TSP parece ter sido estudada pela primeira vez por matemáticos durante a década de 1930 em Viena e em Harvard, notadamente por Karl Menger. Menger define o problema, considera o óbvio algoritmo de força bruta e observa a não-optimidade do vizinho mais próximo heurístico:
Denominamos por problema de mensageiro (já que na prática esta questão deve ser resolvida por cada carteiro, de qualquer forma também por muitos viajantes) a tarefa de encontrar, para finitely muitos pontos cujas distâncias em pares são conhecidas, a rota mais curta que liga os pontos. É claro que este problema pode ser resolvido por muitas tentativas finitas. Não são conhecidas regras que empurrariam o número de tentativas abaixo do número de permutações dos pontos em questão. A regra de que primeiro se deve ir do ponto de partida para o ponto mais próximo, depois para o ponto mais próximo a este, etc., em geral não produz o trajeto mais curto.
Hassler Whitney da Universidade de Princeton introduziu o problema do nome vendedor ambulante logo em seguida.
