Grundlagen Statistik & Algorithmen, Teil 1 Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Ob beim Design von künstlichen Neuronalen Netzwerken fürs Deep Learning, in der Logistik oder beim Layout von Leiterplatten – überall stößt man auf das mathematisch lösbare Problem des Handlungsreisenden: Wie lässt sich eine Tour mit mehreren Stationen auf dem kürzesten Weg und mit dem geringsten Aufwand bewältigen?

Anbieter zum Thema

Bissantz & Company GmbH

Fujitsu Technology Solutions GmbH

Fivetran Germany GmbH

Eines der beliebtesten Rechenmodelle in der Statistik der kombinatorischen Optimierung ist das Problem des Handlungsreisenden: Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden (Traveling Sales Person, TSP) möglichst kurz und die erste Station gleich der letzten Station ist. Der Vertreter muss mehrere Faktoren einbeziehen, um die kombinatorische Optimierung seiner Route zu erreichen. Die Reihenfolge ist wichtig.

Praktische Anwendungen dieses Problems gibt es beispielsweise in der Tourenplanung, in der Logistik oder im Design von Mikrochips. Noch häufiger tritt es allerdings als Unterproblem auf, wie zum Beispiel bei der Verteilung von Waren, bei der Planung von Touren eines Kunden- oder Pannendienstes oder bei der Genom-Sequenzierung. In der analytischen Disziplin „Operations Research“ werden etwa in der Logistik Ladekapazitäten und -verteilungen berechnet, um zugleich auch den Benzinbedarf für die nötige Strecke zu kalkulieren.

Das Problem taucht auch in unerwarteten Einsatzbereichen auf. Mit einer TSP-basierten Lösung ließe sich die optimale Strahlendosis für die Behandlung von Krebstumoren bei individuellen Patienten errechnen. Auch die Optimierung von Molekülen in der Chemie sowie die Optimierung von Wertpapier-Portfolios im Finanzbereich sind naheliegende Aufgabengebiete einer TSP-Lösung. Dennoch erfordert eine solche Lösung meist große Datenmengen und hohe Rechenkapazität.

Schon seit 1930 beißen sich diverse Mathematiker und Statistiker an der Lösung des TSP-Problems die Zähne aus. Viele Forscher haben Optimierungsverfahren entwickelt und für andere Disziplinen als Handlungsreisen genutzt. Da es keinen Allzweck-Algorithmus für das Problem gibt (wohl aber vereinzelte), stehen heute sowohl exakte als auch heuristische Methoden zur Verfügung. Sie erlauben es, sowohl tausende von Städten als auch mehrere Handlungsreisende zu berücksichtigen, ja, sogar Preisgelder und Zeitfenster in die optimale Strecke zu integrieren.

Modellierung als Graph

Bevor überhaupt eine Berechnung stattfinden kann, muss ein Modell erstellt werden, das das Problem wiedergibt. Schließlich kann man nichts berechnen, dass nicht in mathematischer Form vorliegt. Das Problem des Handlungsreisenden lässt sich mithilfe eines Graphen modellieren, das heißt: durch Knoten und Kanten, die die Knoten verbinden.

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Die Knoten repräsentieren die Städte, während jede Kante eine Verbindung zwischen diesen Städten beschreibt, die sich je nach Zusammenhang beispielsweise als geografische Länge einer Verbindung, als Reisezeit oder als Kosten einer Reise zwischen zwei Städten interpretieren lässt. Eine Tour ist ein Kreis in diesem Graphen, der jeden Knoten genau einmal enthält. Ziel ist es, eine möglichst kurze Tour zu finden.

Es gilt die Annahme, dass es immer eine Verbindung zwischen den Städten, also eine Kante, gibt. Die Strecken können gerichtet sein, dann spricht man von einem asymmetrischen TSP. Wenn alle Kanten bzw. Strecken in beide Richtungen gleich lang wären, würde sich in diesem symmetrischen TSP die Anzahl der möglichen Touren halbieren.

Eine weitere Modellierungsmöglichkeit ist die Formulierung als ganzzahliges lineares Programm, in dem die Entscheidungen durch Variablen und die Bedingungen durch lineare Ungleichungen beschrieben werden. Hierfür gibt es ebenfalls mehrere mögliche Varianten.

Lösungsansätze

Die bekannten Lösungsverfahren unterteilen sich in zwei Gruppen, die miteinander kombiniert werden können. Exakte Lösungsverfahren finden – beliebig lange Laufzeit vorausgesetzt – grundsätzlich eine beweisbare Optimallösung. Heuristische Verfahren finden oft in kurzer Zeit gute Lösungen, die aber im allgemeinen Fall beliebig schlecht sein können. Für das metrische TSP gibt es polynomialeHeuristiken, deren Lösungen grundsätzlich höchstens um den Faktor 1,5 bzw. 2 länger sind als eine kürzeste Rundreise.

Exakter Ansatz

Das Problem des Handlungsreisenden kann exakt gelöst werden, indem man die Weglängen aller möglichen Rundreisen berechnet und dann eine mit der kleinsten Weglänge auswählt. Das ist aber schon bei einer kleinen Zahl von Städten nicht mehr praktisch durchführbar. Bei der einfachsten Variante, dem symmetrischen TSP mit Städten, gibt es verschiedene Rundreisen, das sind bei 15 Städten über 43 Milliarden und bei 18 Städten bereits über 177 Billionen. Entsprechend steigt die dafür nötige Rechenzeit exponentiell an.

Mit Methoden der ganzzahligen linearen Optimierung (s. o.), insbesondere Branch-and-Cut, lassen sich dagegen Instanzen in praktisch relevanten Größenordnungen beweisbar optimal lösen oder zumindest die Güte einer gefundenen Tour im Vergleich zu einer Optimallösung abschätzen.

Heuristische Annäherungen

Um schnell zu brauchbaren Lösungen zu kommen, sind meist durch Heuristiken motivierte Näherungsverfahren notwendig, die aber in der Regel keine Qualitätsabschätzung für die gefundenen Lösungen liefern. Je nachdem, ob eine Heuristik eine neue Tour konstruiert oder ob sie versucht, eine bestehende Rundreise zu verbessern, wird sie als Eröffnungs- (auch Konstruktions-) oder Verbesserungsverfahren bezeichnet. Darüber hinaus gibt es Dualheuristiken, die Mindestlängen für eine Tour berechnen.

Metaheuristiken können mehrere dieser Einzelheuristiken unterschiedlich kombinieren. Metaheuristiken kombinieren lokale und globale Suchverfahren in einer abstrakten Strategie für die heuristische Optimierung eines Problems. Der Wikipedia-Artikel stellt jede Heuristik in ihrer Komplexität und Anwendbarkeit dar. Hier werden beispielsweise die heute so viel zitierten künstlichen neuronalen Netze, die für Deep Learning von größter Bedeutung geworden sind, als eine Anwendung von Metaheuristiken zitiert.

Minima

Beim TSP lassen sich auf einfache Weise untere Schranken herausfinden. Sie geben die minimale Länge einer Tour und somit die minimalen Kosten einer entsprechenden Lösung an. Was würde passieren, wenn eine Kante bzw. Knotenverbindung gestrichen würde, etwa in einem Grenzkonflikt oder durch den Brexit? Es entstünde ein „minimal aufspannender Baum“, also ein Teilgraph, der alle Knoten, aber keine Kreise enthält (also ein aufspannender Baum mit minimaler Summe der Kantenlängen) und der sich leicht bestimmen ließe.

Der Christofides-Algorithmus verfolgt als heuristischer Näherungsalgorithmus einen ähnlichen Ansatz, indem er den minimal aufspannenden Baum mit der Lösung eines anderen Problems kombiniert: Perfect Matching mit der geringsten Gewichtung. Der Algorithmus liefert eine Tour, die höchstens um den Faktor 1,5 länger ist als das Optimum.

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

Das Programm „Concorde“ wurde in den 1990er-Jahren entwickelt und viele Lösungen genutzt. 1991 veröffentlichte Gerhard Reinelt die TSPLIB als Sammlung von Benchmark-Instanzen wechselnden Schwierigkeitsgrades. Damit werden Lösungen vergleichbar.

Maxima

TSP-Problemlösungen werden in Instanzen realisiert. Die größte Instanz eines (TSP-symmetrischen) Rundreiseproblems, die bisher nachweisbar optimal gelöst wurde, ist ein Planungsproblem für das Layout integrierter Schaltkreise mit 85.900 Knoten (anno 2006). Die bis dahin größte optimal gelöste Instanz bestand aus 24.978 schwedischen Städten, gelöst im Jahre 2004. 2005 wurden Touren für ein TSP auf über 526 Millionen Sternen gefunden, deren Länge nachweislich höchstens 0,798 Prozent vom Optimum abweicht. Diese Meilensteine werden fortwährend übertroffen, denn der Bedarf nach besseren Lösungen wächst, je komplexer die TSP-relevanten Probleme werden, etwa in der globalen Logistik.

Mit der Berücksichtigung weiterer Faktoren erhöht sich der Aufwand für die Berechnung. Würde man bestimmte Zeitfenster für die Gesamtstrecke oder Teiltouren vorgeben, müsste das Vorgehen anders gewichtet werden. Das gleiche Prinzip gilt bei der Berücksichtigung einer Mehrzahl von Reisenden, die eine Mehrzahl von Vehikeln benutzen, die aber alle vom gleich Startpunkt ausgehen und dorthin zurückkehren. Das wäre beispielsweise bei einem Logistikdienstleister der Fall.

Mit UPS durch Dick und Dünn

Anno 2013 führte der US-amerikanische Paketdienst UPS ein solches Navigationssystem namens ORION (On-Road Integrated Optimization and Navigation) ein. Dieses berücksichtigt garantierte Lieferfristen für einzelne Pakete, angemeldete Abholungen und spezielle Kundenklassen mit bevorzugter Bedienung sowie Daten aus dem Verkehrsfluss in Echtzeit.

Der WIRED-Artikel „The Astronomical Math Behind UPS' New Tool to Deliver Packages Faster“ erläutert nicht nur die mathematischen Dimensionen, sondern auch die wirtschaftlichen. Es lässt erfahrenen Mitarbeitern die Möglichkeit, von der vorgeschlagenen Route abzuweichen. Der Faktor Mensch wird also nicht gegenüber der Software ignoriert.

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 6

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

Grundlagen Statistik & Algorithmen, Teil 7

So deckt der Local Outlier Factor Anomalien auf

(ID:45303046)