Problema călătorului de vânzări (adesea numită TSP) este o problemă algoritmică clasică în domeniul informaticii și al cercetării operaționale. Ea este axată pe optimizare. În acest context, o soluție mai bună înseamnă adesea o soluție mai ieftină, mai scurtă sau mai rapidă. TSP este o problemă matematică. Este cel mai ușor de exprimat sub forma unui grafic care descrie locațiile unui set de noduri.
Problema comis-voiajorului călător a fost definită în anii 1800 de către matematicianul irlandez W. R. Hamilton și de matematicianul britanic Thomas Kirkman. Jocul Icosian al lui Hamilton era un puzzle recreativ bazat pe găsirea unui ciclu hamiltonian. Forma generală a TSP pare să fi fost studiată pentru prima dată de matematicieni în anii 1930 la Viena și la Harvard, în special de Karl Menger. Menger definește problema, ia în considerare algoritmul evident de forță brută și observă caracterul neoptimal al euristicii celui mai apropiat vecin:
Numim problema mesagerului (deoarece în practică această problemă ar trebui rezolvată de fiecare poștaș, oricum și de mulți călători) sarcina de a găsi, pentru un număr finit de puncte ale căror distanțe pereche sunt cunoscute, cea mai scurtă rută care leagă punctele. Bineînțeles, această problemă este rezolvabilă printr-un număr finit de multe încercări. Nu se cunosc reguli care ar împinge numărul de încercări sub numărul de permutări ale punctelor date. Regula conform căreia ar trebui să se meargă mai întâi de la punctul de plecare la punctul cel mai apropiat, apoi la punctul cel mai apropiat de acesta etc., în general, nu produce cel mai scurt traseu.
Hassler Whitney, de la Universitatea Princeton, a introdus la scurt timp după aceea numele de problema vânzătorului ambulant.
