Wie lässt sich eine Rundreise organisieren?
Wie lässt sich eine Rundreise durch verschiedene Städte auf dem kürzesten Weg organisieren? Darüber zerbrechen sich nicht nur Paketdienste, Handlungsreisende und Touristen den Kopf, sondern seit vielen Jahrzehnten auch Mathematiker. Eine endgültige Lösung des Problems für eine große Zahl von Orten ist noch nicht gelungen, aber Forscher der Universitäten Bonn und Grenoble haben einen Algorithmus gefunden, der mit Abstand die beste Näherung liefert. Sie berichten in der Fachzeitschrift „Combinatorica“ über ihre Ergebnisse, deren Druckausgabe nun vorliegt.
Wie lässt sich die Reihenfolge für den Besuch mehrerer Orte so wählen, dass die gesamte Route möglichst kurz ist? „Dieses Rundreiseproblem klingt trivial, ist aber eine harte Nuss“, sagt Prof. Dr. Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn. Seit mehr als 60 Jahren zerbrechen sich Mathematiker darüber den Kopf – ohne es bislang gelöst zu haben. „Dieses populäre Problem hat seit Jahrzehnten eine zentrale Bedeutung für die mathematische Optimierung: Viele ursprünglich dafür entwickelte Methoden kamen später auch bei ganz anderen Problemen zum Einsatz“, erläutert sein Kollege Prof. Dr. András Sebö von der Universität Grenoble. „Es müssen beim Rundreiseproblem auch nicht unbedingt Städte sein, die durchlaufen werden sollen – sehr oft sucht man beispielsweise auch eine optimale Reihenfolge von Arbeitsschritten.“
Komplexität überfordert sogar Supercomputer
Mit wenigen Orten lässt sich die Aufgabe noch relativ einfach lösen, indem man die Weglängen aller möglichen Rundreisen berechnet und dann die kürzeste auswählt. Mit der Zahl der zu besuchenden Orte nimmt aber die Komplexität des Problems und damit die Rechenzeit rasch zu und überfordert dann auch die schnellsten Supercomputer. Mit 15 Städten gibt es bereits mehr als 43 Milliarden verschiedene Rundreisen, aus denen die kürzeste auszuwählen ist. Mit 18 Städten steigt die Zahl der Möglichkeiten auf über 177 Billionen an – und so weiter.
„Viele Mathematiker vermuten, dass das Rundreiseproblem für eine große Anzahl von Städten überhaupt nicht lösbar ist“, berichten die beiden Wissenschaftler. Das ist aber noch nicht bewiesen. Bislang ist es den Mathematikern jedoch gelungen, sich mit verschiedenen Verfahren der optimalen Route anzunähern. Es handelt sich dabei um Kompromisslösungen mit dem Vorteil einer überschaubaren Rechenzeit, aber Abstrichen hinsichtlich der kürzesten Weglänge. Wenn zum Beispiel vorgegeben ist, dass die Gesamtstrecke insgesamt doppelt so lang sein darf wie die optimale Route, dann lässt sich das relativ einfach umsetzen: Zu jedem Punkt ist dann ein Hin- und Rückweg erlaubt.
Neuer Rekord liegt beim 1,4-fachen der optimalen Strecke
Lange Zeit hielt Nicos Christofides den Rekord: 1976 veröffentlichte er einen Algorithmus, der eine Rundreise ergab, die maximal um die Hälfte länger als die optimale Tour ist. 35 Jahre später gelang es Mathematikern aus Nordamerika erstmals, diese Annäherung im wichtigsten Spezialfall zu unterbieten, wenn auch nur um eine Winzigkeit. Nun stellen die Professoren Jens Vygen von der Universität Bonn und András Sebö von der Universität Grenoble (Frankreich) einen neuen Rekord auf: Gemeinsam beschreiben sie einen völlig neuen Algorithmus, der die bisherige Bestmarke deutlich auf das 1,4-fache der optimalen Rundreisestrecke verkürzt.
Dabei brüteten die beiden Wissenschaftler während eines Forschungsaufenthaltes von Prof. Vygen in Grenoble gar nicht über dem Rundreiseproblem. „Wie so häufig war Zufall im Spiel“, erzählt der Mathematiker der Universität Bonn. Zusammen mit seinem Kollegen aus Frankreich ging er der Frage nach, wie sich zum Beispiel Strom- oder Telekommunikationsnetzwerke so optimieren lassen, dass es bei einem Kabelriss nicht zu einem Ausfall kommt. „Aber wie viele Mathematiker haben wir das Rundreiseproblem ständig im Hinterkopf“, berichtet Prof. Vygen. Deshalb lag es nahe, den Ansatz für das Netzwerkproblem auch auf die ähnliche Rundreisefrage anzuwenden.
Prof. Sebö und Prof. Vygen entdeckten eine neue Struktur: die sogenannte „Schöne-Ohren-Zerlegung“. Wie bei einer Zwiebel gingen die Wissenschaftler bei der Verbindung der Orte von außen nach innen vor. „Das funktioniert nur, wenn man die richtige Zwiebelstruktur erfasst hat – und die sieht man der Landkarte mit den Straßen und Orten zunächst nicht an“, sagt Prof. Vygen. Der Algorithmus aus Bonn und Grenoble mit den bislang besten Ergebnissen für das Rundreiseproblem lässt sich nicht nur in der Logistikbranche nutzen: Zum Beispiel bei Himmelsdurchmusterungen der Astronomen ist ebenfalls die kürzeste Route von Stern zu Stern gefragt.
Publikation: Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Fachjournal Combinatorica 34 (5) (2014), 597-629, online-Version vorab (DOI: 10.1007/s00493-011-2960-3)
