Das Traveling Salesman Problem (oft TSP genannt) ist ein klassisches algorithmisches Problem aus dem Bereich der Informatik und des Operations Research. Es ist auf Optimierung ausgerichtet. Bessere Lösung bedeutet in diesem Zusammenhang oft eine Lösung, die billiger, kürzer oder schneller ist. TSP ist ein mathematisches Problem. Es lässt sich am einfachsten in Form eines Graphen ausdrücken, der die Positionen einer Menge von Knoten beschreibt.
Das Problem der Handlungsreisenden wurde in den 1800er Jahren von dem irischen Mathematiker W. R. Hamilton und dem britischen Mathematiker Thomas Kirkman definiert. Hamiltons Icosian Game war ein Erholungsrätsel, das auf der Suche nach einem Hamilton-Zyklus basierte. Die allgemeine Form des TSP scheint erstmals in den 1930er Jahren von Mathematikern in Wien und in Harvard untersucht worden zu sein, insbesondere von Karl Menger. Menger definiert das Problem, betrachtet den offensichtlichen Brute-Force-Algorithmus und beobachtet die Nichtoptimalität der Heuristik des nächsten Nachbarn:
Wir bezeichnen als Botenproblem (da diese Frage in der Praxis von jedem Postboten, jedenfalls auch von vielen Reisenden, gelöst werden sollte) die Aufgabe, für finitely viele Punkte, deren paarweise Entfernungen bekannt sind, den kürzesten Weg zu finden, der die Punkte verbindet. Natürlich ist dieses Problem durch endlich viele Versuche lösbar. Regeln, die die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte drücken würden, sind nicht bekannt. Die Regel, dass man zuerst vom Startpunkt zum nächstgelegenen Punkt gehen soll, dann zum nächstgelegenen Punkt usw., ergibt im Allgemeinen nicht den kürzesten Weg.
Hassler Whitney an der Universität Princeton führte bald darauf das Problem des Namens Reiseverkäufer ein.
