Wissenschaft & Ideen · Erfindungen & Technik

Die kürzeste Rundreise ist kein Reiseproblem mehr

Beim Problem des Handlungsreisenden geht es darum, eine Rundreise durch mehrere Orte so zu planen, dass jeder Ort außer dem Start genau einmal besucht wird und die Gesamtstrecke möglichst kurz bleibt. Was nach einer einfachen Denksportaufgabe klingt, entpuppt sich als eines der berühmtesten Probleme der Mathematik und Informatik, weil die Zahl möglicher Routen mit jeder zusätzlichen Stadt explosionsartig wächst – schon bei 18 Städten gibt es mehr als 177 Billionen mögliche Touren. Erstmals 1930 von Karl Menger als mathematisches Problem formuliert, bekam es bald seinen heutigen Namen und wurde ab den 1950er Jahren, etwa durch die Arbeit von George Dantzig und Kollegen bei der RAND Corporation, zu einem zentralen Testfeld für neue Optimierungsmethoden. In der Praxis taucht es überall dort auf, wo Reihenfolgen optimiert werden müssen, von der Tourenplanung über das Bohren von Leiterplatten bis zur Genom-Sequenzierung, wobei „Städte“ und „Entfernungen“ dann für ganz andere Dinge stehen können.

Mathematisch lässt sich das Problem als Graph mit Städten als Knoten und Wegen als Kanten beschreiben, wobei man zwischen symmetrischen und asymmetrischen Varianten sowie dem metrischen Fall unterscheidet, bei dem sich Umwege nie lohnen. Weil bewiesen ist, dass das Problem NP-schwer ist, gibt es vermutlich keinen Algorithmus, der für beliebig große Instanzen in vernünftiger Zeit garantiert die optimale Lösung findet – ein Umstand, der seit Richard Karps Beweis von 1972 als gesichert gilt, sofern die ungelöste P-NP-Frage wie erwartet ausfällt. Trotzdem gelang es Forschern mit immer ausgefeilteren Methoden wie Schnittebenenverfahren und Branch-and-Cut, exakte Lösungen für erstaunlich große Fälle zu berechnen, etwa 2006 für ein Layoutproblem mit fast 86.000 Städten. Wo exakte Lösungen zu aufwendig sind, kommen Heuristiken zum Einsatz, die zwar keine Optimalität garantieren, aber oft schnell brauchbare Touren liefern, etwa durch schrittweises Anfügen des nächsten Nachbarn oder durch nachträgliches Austauschen einzelner Streckenabschnitte wie bei der bekannten Lin-Kernighan-Heuristik.

Neben der klassischen Version gibt es zahlreiche Varianten, die zusätzliche Bedingungen aus der Praxis abbilden: Beim Problem mit mehreren Handlungsreisenden teilen sich verschiedene Fahrer die Städte auf, was in Kombination mit Ladekapazitäten zum praxisnahen Vehicle Routing Problem führt, wie es etwa bei Paketzustellern eingesetzt wird. Andere Varianten fassen Städte zu Clustern zusammen, ändern das Optimierungsziel wie beim Sammeln von Preisgeldern, oder fügen Zeitfenster hinzu, wie sie ein Kundendienst oder Pannenhelfer einhalten muss. So verwendet etwa der Paketdienst UPS ein System, das Lieferfristen, Echtzeitverkehr und sogar die Vermeidung von Linksabbiegern berücksichtigt. All diese Erweiterungen bleiben im Kern ebenso schwer lösbar wie das ursprüngliche Problem, was zeigt, warum es bis heute als Spielwiese für neue Optimierungsideen dient.

Trotz der theoretischen Härte des Problems wurden Fälle mit mehreren tausend Städten nachweislich optimal gelöst – nicht nur näherungsweise.

Den ganzen Artikel „Problem des Handlungsreisenden“ auf Wikipedia lesen

Der Artikel stammt aus der Wikipedia und steht unter CC BY-SA 4.0. Die Einleitung oben ist unsere eigene.