Rekord bei mathematischer Rundreise

Städte-Tour mit hoher Mathematik: Ein neuer Algorithmus liefert mit Abstand die beste Näherung an das mathematische Handlungsreisenden-Problem. Bereits seit über 60 Jahren suchen Mathematiker nach einer Lösung, wie sich eine Reiseroute optimieren lässt – die Aufgabe überfordert selbst Supercomputer. Die Bestmarke für eine Annäherung haben deutsche und französische Wissenschaftler nun auf das 1,4-fache der kürzesten Wegstrecke herabgesetzt.

Wie plant man eine Rundreise durch mehrere Städte so, dass die gesamte Reiseroute möglichst kurz ist? „Dieses Rundreiseproblem klingt trivial, ist aber eine harte Nuss“, sagt Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn. Bei wenigen Städten auf der Route ist die Lösung einfach: Man berechnet die Wegstrecken aller möglichen Verbindungen und wählt die kürzeste aus.

Steigt aber die Zahl der Zielorte, so wächst auch die Komplexität des sogenannten Handlungsreisenden-Problems rasant an. Bei 15 Städten gibt es bereits mehr als 43 Milliarden verschiedene Rundreisen, mit 18 Städten steigt die Zahl der Möglichkeiten auf über 177 Billionen. Die dafür nötige Rechenzeit überfordert selbst die modernsten Supercomputer.

Zentrale Bedeutung für mathematische Optimierung

Dabei ist das Problem nicht nur für Touristen, Handlungsreisende oder Paketdienste interessant: „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“, erklärt András Sebő von der Universität Grenoble. Bei astronomischen Himmelsdurchmusterungen ist beispielsweise die kürzeste Strecke von Stern zu Stern gefragt. „Dieses populäre Problem hat seit Jahrzehnten eine zentrale Bedeutung für die mathematische Optimierung.“

Jens Vygen vom Forschungsinstitut für Diskrete Mathematik der Universität Bonn hilft Handlungsreisenden, den kürzesten Weg zu finden. © Barbara Frommann/Uni Bonn

Mathematiker suchen schon seit mehr als 60 Jahren nach einer einfacheren und vor allem allgemeinen Lösung – bisher ohne Erfolg. Es existieren jedoch einige Algorithmen, die sich der optimalen Route annähern. Dabei müssen die Wissenschaftler allerdings Zugeständnisse machen: Eine etwas längere Wegstrecke wird in Kauf genommen, wenn sich die Rechenzeit dadurch deutlich verkürzen lässt. Die Mindestlänge der Strecke lässt sich gut berechnen, allein für die nötige Reihenfolge der Städte ist ein hoher Rechenaufwand nötig. Der bisherige Rekordhalter lieferte Reiserouten, die um knapp die Hälfte der Strecke länger waren als der theoretische kürzest-mögliche Reiseweg.

Zwiebel-Algorithmus mit schönen Ohren

Sebő und Vygen haben diesen Rekord nun deutlich unterboten: Ihr neuer Algorithmus liefert das 1,4-fache der optimalen Rundreisestrecke. Möglich ist die neue Bestmarke durch ein mathematisches Verfahren namens „Schöne-Ohren-Zerlegung“. Dabei gehen die Mathematiker von außen nach innen vor, während sie die Orte miteinander verbinden. Vygen vergleicht die Zerlegung mit den Schichten einer Zwiebel: „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.“

Kurioserweise brüteten die Wissenschaftler zunächst gar nicht über dem Rundreiseproblem: „Wie so häufig war Zufall im Spiel“, sagt Vygen. Eigentlich wollten die Mathematiker Strom- und Telekommunikationsnetzwerke so optimieren, dass bei einem Kabelriss nicht das komplette System ausfällt. „Aber wie viele Mathematiker haben wir das Rundreiseproblem ständig im Hinterkopf“, so Vygen. Deshalb lag es nahe, den Ansatz für das Netzwerkproblem auch auf die ähnliche Rundreisefrage anzuwenden. (Combinatorica, 2014; doi: 10.1007/s00493-011-2960-3)

(Rheinische Friedrich-Wilhelms-Universität Bonn, 04.11.2014 – AKR)