Das
Problem des Handlungsreisenden (auch
Botenproblem,
Rundreiseproblem,
engl. Traveling Salesman Problem oder
Traveling Salesperson Problem (TSP)) ist ein
kombinatorisches Optimierungsproblem des
Operations Research und der
theoretischen Informatik. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des
Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist.
Seit seiner ersten Erwähnung als mathematisches Problem im Jahre 1930 haben sich viele Forscher damit befasst und neue
Optimierungsverfahren daran entwickelt und erprobt, die momentan auch für andere Optimierungsprobleme eingesetzt werden. Heute steht eine Vielzahl von
heuristischen und
exakten Methoden zur Verfügung, mit denen auch schwierige Fälle mit mehreren tausend Städten optimal gelöst wurden.
Das Problem des Handlungsreisenden tritt schon in seiner Reinform in vielen praktischen Anwendungen auf, beispielsweise in der
Tourenplanung, in der
Logistik oder im Design von
Mikrochips. Noch häufiger tritt es allerdings als Unterproblem auf, wie zum Beispiel bei der Verteilung von Waren, bei der Planung von Touren eines
Kunden- oder
Pannendienstes oder bei der
Genom-Sequenzierung. Dabei sind die Begriffe „Stadt“ und „Entfernung“ nicht wörtlich zu nehmen, vielmehr repräsentieren die Städte beispielsweise zu besuchende Kunden, Bohrlöcher oder DNA-Teilstränge, während Entfernung für Reisezeit, Kosten oder den Grad der Übereinstimmung zweier DNA-Stränge steht. In vielen praktischen Anwendungen müssen zudem Zusatzbedingungen wie Zeitfenster oder eingeschränkte Ressourcen beachtet werden, was die Lösung des Problems erheblich erschwert.
Das Problem des Handlungsreisenden ist ein
NP-schweres Problem. Unter der bislang
unbewiesenen Annahme, dass die
Komplexitätsklassen P und
NP verschieden sind, gilt demnach, dass kein
Algorithmus existiert, der eine kürzeste Rundreise in
polynomieller Worst-case-Laufzeit bestimmt.
