Il Traveling Salesman Problem (spesso chiamato TSP) è un classico problema algoritmico nel campo dell'informatica e della ricerca operativa. È focalizzato sull'ottimizzazione. In questo contesto, soluzione migliore significa spesso una soluzione più economica, più breve o più veloce. TSP è un problema matematico. Si esprime più facilmente come un grafico che descrive la posizione di un insieme di nodi.
Il problema dei venditori ambulanti fu definito nel 1800 dal matematico irlandese W. R. Hamilton e dal matematico britannico Thomas Kirkman. L'Icosian Game di Hamilton era un puzzle ricreativo basato sulla ricerca di un ciclo hamiltoniano. La forma generale del TSP sembra essere stata studiata per la prima volta dai matematici negli anni Trenta a Vienna e ad Harvard, in particolare da Karl Menger. Menger definisce il problema, considera l'ovvio algoritmo della forza bruta e osserva la non ottimalità del vicino euristico:
Si indica per problema di messaggero (poiché in pratica questa questione dovrebbe essere risolta da ogni postino, comunque anche da molti viaggiatori) il compito di trovare, per molti punti di cui si conoscono le distanze a coppie, il percorso più breve per collegare i punti. Naturalmente, questo problema è risolvibile con molte prove. Non sono note regole che spingano il numero di prove al di sotto del numero di permutazioni dei punti indicati. La regola secondo cui si deve andare prima dal punto di partenza al punto più vicino, poi al punto più vicino a questo, ecc. in generale non dà il percorso più breve.
Hassler Whitney alla Princeton University ha introdotto subito dopo il problema dei venditori ambulanti.
