Beim TSP soll die kürzeste Entfernung zwischen n verschiedenen Orten P_i gefunden werden. Dabei sollen ausgehend vom Ort P_i alle übrigen Orte genau einmal aufgesucht werden. Die Rundreise soll wieder in P_i enden. 

Wie bereits der Name „Traveling-Salesman-Problem“ aussagt, hat man bei dieser häufig benutzten Definition die räumlichen Vorstellung einer Rundreise, was leicht dazu verführt, die Orte zu lokalisieren, d.h. zum Merkmal „Länge“ implizit ein weiteres Merkmal „Lage im Raum“ hinzuzufügen. Beim TSP ist die "Rundreise" nur ein Bild, um das Problem anschaulich zu machen. Die Definition des TSP als ein geometrisch-geographisches System, wie es u.a. von Wolfgang Oberstenfeld (http:/www.rundreiseproblem.de) beschrieben wird, greift nach Überzeugung des Autors für das allgemeine, bedingungsfreie TSP zu kurz. 

Somit ist das TSP(min) ein minimaler Hamiltonkreis in einem Graphen, völlig unabhängig davon, was zu minimieren ist. Müller-Merbach spricht hier allgemein von "Kosten". Besser als das Bild einer Rundreise ist daher die graphentheoretische Beschreibung.

Bemerkung:
Das Minimum steht stellvertretend auch für das andere Extrem Maximum, was hier aber nicht untersucht werden soll.

Das Problem des TSP
  

(15.04.2005)