Bonner Forscher entwickeln Algorithmus für Rundreisen

Asiaten und US-Amerikaner sind Meister darin, Rundreisen besonders effektiv zu gestalten. Bonner Mathematiker haben dazu nun einen Formel entwickelt.
Asiaten und US-Amerikaner sind Meister darin, Rundreisen besonders effektiv zu gestalten. Bonner Mathematiker haben dazu nun einen Formel entwickelt.
Foto: Archiv: Marco Kneise, Thüringer Allgemeine
Was wir bereits wissen
Europa in vier Tagen erleben, inklusive Besuch in Rom, Paris, Berlin, London und noch drei weiteren Hauptstädten: Für Asiaten und US-Touristen sind solche Touren üblich. Bonner Wissenschaftler haben jetzt erstmals eine Formel entwickelt, die Touristen besonders effektive Rundreisen ermöglichen soll.

Bonn.. Collatz-Problem, Hadwiger-Nelson-Problem oder die Goldbachsche Vermutung: Frei nach Wikipedia gibt es in der Mathematik noch viele ungelöste Problemstellungen. Bonner Wissenschaftler haben jetzt zusammen mit Forschern in Frankreich ein Problem beackert, das Touristen betrifft: das "Rundreiseproblem".

Möglichst viel sehen in möglichst kurzer Zeit: Was Touristen vor eine große Herausforderung stellt, beschäftigt auch Mathematiker seit Jahrzehnten. Forscher der Universitäten Bonn und Grenoble haben nun einen Algorithmus gefunden, der die Route einer Rundreise möglichst kurz macht. Das teilte die Universität Bonn am Dienstag mit. "Dieses Rundreiseproblem klingt trivial, ist aber eine harte Nuss", sagte Jens Vygen, Professor am Forschungsinstitut für Diskrete Mathematik der Universität Bonn. Die Ergebnisse der Forscher sind in der aktuellen Ausgabe der Fachzeitschrift "Combinatorica" erschienen.

Je mehr Orte, desto komplizierter wird die Rechnung

Je mehr Städte besucht werden sollen, desto komplizierter wird die Rechnung: So gebe es bei 15 Städten bereits 43 Milliarden mögliche Strecken, aus denen die kürzeste ausgewählt werden müsse. Mit 18 Städten steigt die Zahl der Möglichkeiten auf über 177 Billionen an – und so weiter. Die beiden Mathematiker haben nun ein Verfahren entwickelt, um sich der optimalen Route anzunähern - ohne unendlich lange rechnen zu müssen. Allerdings bedeute diese Vereinfachung bei der Rechnung einen Kompromiss bei der Reisedauer. Immerhin: Der Algorithmus ergibt eine Reiseroute, die maximal 1,4-mal so lang ist wie die optimale Strecke.

Das Rundreiseproblem ist Vygen zufolge seit Jahrzehnten bedeutend für die mathematische Optimierung. Es gehe dabei nicht nur um Städte, die besucht werden. Die Erkenntnisse ließen sich auch für die Logistikbranche nutzen und dafür, die optimale Reihenfolge von Arbeitsschritten herauszufinden. (dpa/WE)