Schon Konfuzius betonte, dass der Weg das Ziel sei. Aber welcher Weg? Das fragen sich Mathematikerinnen und Mathematiker seit  über 100 Jahren. 1832 tauchte in einem Handbuch der Begriff des kürzesten oder optimalen Weges erstmals auf, wurde aber noch nicht mathematisch behandelt. Als „Botenproblem“ bezeichnete 1930 der österreichische Mathematiker Karl Menger das Problem, das er so beschrieb: „„Wir bezeichnen als Botenproblem die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden.“ Wenig später wurde der Begriff Traveling Salesman Problem (TSP) durch den amerikanischen Mathematiker Hassler Whitney eingeführt.

Beim Traveling Salesman Problem geht es darum, dass ein Handlungsreisender während seiner Rundreise eine vorgegebene Anzahl von Städte besuchen soll. Er startet also in einer dieser Städte, besucht nacheinander einmalig die restlichen Städte und kehrt schließlich zu seinem Ausgangspunkt zurück. Dabei soll er möglichst den kürzesten Weg benutzen. Die Forderung kann aber beispielsweise auch gestellt werden, den kostengünstigsten Weg zu finden. Auch wenn unterschiedliche Anforderungen gestellt werden, ist man mit TSP also immer bemüht, den optimalen Weg zu finden.

Mathematische Grundlage für die Routenberechnung ist ein sogenannter Graph. Ein solcher Graph besteht zunächst aus einzelnen Knoten, bei der Rundreise sind dies die einzelnen Städte. Die Verbindung zwischen diesen Knoten nennt man Kanten, sie repräsentieren den Weg zwischen den Städten. Beispiel für Graphen sind etwa U-Bahn-Fahrpläne, Stammbäume oder auch die Struktur von Webseiten. Die Mathematik unterscheidet zwischen ungerichteten und gerichteten Graphen. Laut Gablers Wirtschaftslexikon besteht ein ungerichteter Graph aus einer Menge V von Knoten und einer Menge E von Kanten, ein gerichteter Graph dagegen aus einer Menge V von Knoten und einer Menge A von Bögen oder Pfeilen.

Für die Modellierung eines Graphen müssen die Entfernungen zwischen den einzelnen Städten bekannt sein. In unterschiedlichen Voraussetzungen können dabei zudem neben den tatsächlichen geometrischen Abständen beispielsweise auch Reisezeiten oder Kosten, z.B. für Treibstoff, in das Modell einbezogen werden. Unterschiedliche Ziele können also sein, die Rundreise so zu planen, dass der Gesamtreiseweg bzw. die Reisezeit oder auch die insgesamt anfallenden Kosten minimiert werden. Das macht das Problem nicht leichter. Die Mathematiker Martin Grötschel und Manfred Padberg beschreiben dies in ihrem – auch für Laien gut verständlichen – Beitrag „Die optimierte Odyssee“ im Magazin „Spektrum der Wissenschaft“ 1999 so: „Das berühmte Travelling Salesman Problem ist schnell formuliert, höchst praxisrelevant, scheinbar harmlos, in Wirklichkeit aber – für große Städteanzahlen – so schwer, dass die Mathematiker sich auch nach Jahrzehnten harter Arbeit die Zähne daran ausbeißen.“

Es leuchtet sofort ein, dass diese Optimierungsmethode für viele Anwendungen von großer Bedeutung ist, nicht nur für VertreterInnen (Traveling Salesman), auch für BriefträgerInnen, für Logistikunternehmen, für Fahrpläne, bei Computerprogrammen, beim Entwurf von Mikrochips, der Personalplanung, der Gestaltung von Kommunikations- oder Energienetzen, der Kapitalanlageplanung   und, und, und…

Kurz, das Traveling Salesman Problem ist ein grundlegendes Problem in allen Optimierungsfragen und daher das am intensivsten untersuchte kombinatorische Optimierungsproblem.

Neben dieser praktischen Bedeutung ist TSP für MathematikerInnen aber auch zu einem Wettbewerb geworden. Denn meist gibt es nicht den einzigen, optimalen Weg. Es kann viele Lösungswege geben und so wird für die MathematikerInnen die Frage zentral, wie nahe man an den optimalen Weg kommt. In dem oben zitierten Artikel haben Martin Grötschel und Manfred Padberg für die 16 Stationen der 20 Jahre dauernden Irrfahrt des griechischen Königs Odysseus 653837184000 Möglichkeiten gefunden. Mit 18 Städten steigt die Zahl der Möglichkeiten auf über 177 Billionen an.

Die Autoren Grötschel und Padberg tauchen selbst immer wieder in der Liste der neuen Rekorde bei der Anzahl der verbundenen Städte auf. 1977 konnte Martin Grötschel mit 120 Städten die vorher mögliche Zahl fast verdoppeln, Manfred Padberg erreichte gemeinsam mit G. Rinaldi 1987 bereits die Verbindung von 2.392 Städten. 2004 gelang es einer Gruppe amerikanischer Mathematiker 24.978 Städte zu verbinden. Heute ist man in der Lage, eine Rundtour durch 1.904.711 Städte auf der ganzen Welt zu berechnen und kann beweisen, dass diese Lösung maximal 0.076% länger ist als die optimale Tour. Aber optimal ist auch diese Rundtour noch nicht.

Daher vermuten viele Mathematiker, dass das Rundreiseproblem für eine große Anzahl von Städten überhaupt nicht lösbar ist. Aber auch das können sie nicht beweisen. Bei allen bisherigen Lösungen handelt es sich also um Kompromisse mit dem Vorteil einer überschaubaren Rechenzeit, aber Abstrichen hinsichtlich der kürzesten Weglänge. Geht man von der Voraussetzung aus, dass die Route maximal doppelt so lang sein darf als die optimale, ist die Berechnung noch relativ einfach. Im November 2014 jedoch stellten die Professoren Jens Vygen von der Universität Bonn und András Sebö von der Universität Grenoble (Frankreich) einen neuen Rekord auf. Sie beschrieben einen völlig neuen Algorithmus, der die bisherige Bestmarke deutlich auf das 1,4-fache der optimalen Rundreisestrecke verkürzt. Diesen neuen Algorithmus gaben sie den Namen „Schöne-Ohren-Zerlegung“.

Es gibt also riesige Fortschritte dank neuer mathematischer Methoden. Gleichzeitig muss man jedoch feststellen, dass es voraussichtlich immer noch ein langer Weg zum kürzesten – oder besser – optimalen Weg ist. Die vielfachen Anwendungen dieser Optimierungsmethode geben jedoch die Sicherheit, dass weiterhin mit Nachdruck geforscht wird.