Einführung in die Welt der Tourenoptimierung (1/3)

In vielen Unternehmen fallen täglich verschiedene Transportprozesse an. Klassische Beispiele sind die Optimierung von Warenein- und ausgängen, die Einsatzplanung von Servicetechnikern oder die optimale Reihenfolge der Auslieferung bei Lieferdiensten. Zur Tourenoptimierung im Logistikbereich existieren eine ganze Reihe an fertigen Lösungen von verschiedenen SaaS-Anbietern (Software as a Service). Diese bringen verschiedene Vorteile mit sich: SaaS-Produkte können in der Regel schnell integriert und genutzt werden, sind meist flexibel skalierbar, erfordern weniger internes IT-Know-how im Vergleich zu Individuallösungen und sind mit keinen oder geringen initialen Investitionskosten verbunden. Nachteile liegen in der hohen Abhängigkeit vom Anbieter und der Unsicherheit, ob die One-Size-fits-All-Lösung eines SaaS-Anbieters alle Besonderheiten der eigenen Transportprozesse abbildet. 

Aus der Fahrradstadt Münster kommend, setzen einige Logistikanbieter immer mehr auf das Fahrrad als Transportmittel für die letzte Meile. Beim Einsatz von Tourenplanungs-SaaS-Produkten für die Planung von Fahrrädern als Transportmittel kommt es häufiger zu Problemen, insbesondere bei den angegebenen Zeiten – gefahrene Geschwindigkeiten auf dem Rad sind stark abhängig von den individuellen Fahrer*innen, aber auch von der gewählten Strecke mit ihren äußeren Gegebenheiten. Diese wichtigen Nebenbedingungen können die meisten SaaS Lösungen nicht abbilden. 

In einem Proof of Concept für einen unserer Kunden habe ich gezeigt, wie wir Tourenoptimierungsprobleme beim Einsatz des Fahrrads für die letzte Meile mit individuellen Nebenbedingungen lösen können. In einer dreiteiligen Blogreihe möchte ich einen kleinen Einblick in die Welt der Tourenoptimierung geben und auf praktische Umsetzungsmöglichkeiten eingehen. Im ersten Blogartikel diskutiere ich die theoretischen Grundlagen der Tourenoptimierung und gehe hier auf das bekannte Traveling Salesman Problem (TSP), gängige Nebenbedingungen und verschiedene Lösungsverfahren ein. Im zweiten Teil wird es praktisch: Hier stelle ich einen kleinen Showcase in einem Python Jupyter Notebook vor und zeige beispielhaft, wie wir kleine Tourenoptimierungsprobleme Schritt für Schritt lösen und visualisieren können.
Im dritten Teil werden die Ideen und Konzepte aus dem zweiten Teil weiter vertieft und um realistischere Nebenbedingungen und Anforderungen erweitert.

Das Traveling Salesman Problem in der Tourenoptimierung

Wie versprochen starte ich mit etwas Theorie. Ein bekanntes und gut erforschtes Problem, das den meisten Tourenoptimierungsproblemen zu Grunde liegt, ist das so genannte Rundreisendenproblem (Englisch: Traveling Salesman Problem, TSP). Das Traveling Salesman Problem erfreut sich hoher Beliebtheit bei Uni-Dozenten und wird in vielen Vorlesungen angesprochen, da es einen leichten Einstieg in das Feld der Tourenoptimierung gibt. Außerdem kann man daran anschaulich zeigen, warum verschiedene naive Verfahren weniger gut zum effizienten Berechnen einer Lösung geeignet sind. Welche Lösungsansätze praxisrelevant sind, wird leider häufiger außen vor gelassen. 

Die Grundidee des TSP ist einfach. Ein Handelsreisender möchte n verschiedene Kunden besuchen. Dazu startet er von einem Startpunkt, besucht in einer bestimmten Reihenfolge nacheinander alle n Kunden und kehrt dann wieder zu seinem Ausgangspunkt zurück. Gesucht ist nun die Tour, deren Gesamtstrecke am kürzesten ist.

Klingt einfach? Ist es auch! Zumindest für eine kleine Anzahl von Kunden. Ist die Anzahl der Kunden gering oder sind diese günstig angeordnet, lässt sich eine optimale Lösung visuell schnell finden.

Schwieriger wird es bei einer größeren Anzahl an Zielpunkten, die zusätzlich ungünstig angeordnet sind. Unten dargestellt ist eine Tour, die 20 deutsche Städte verbindet. Ist die Tour optimal oder findet ihr vielleicht noch eine bessere Variante? Und wie kann ich überhaupt wissen, ob es noch eine effizientere Lösung gibt?

Exakte Lösungsverfahren und warum wir sie nicht nutzen

Eine sichere Art und Weise, um die optimale Lösung zu finden oder zu überprüfen, ob eine Lösung optimal ist, ist die Brute-Force-Methode. Im TSP-Kontext bedeutet das, alle Permutationen der Zielpunkte zu bilden und für jede Permutation die Routenlänge zu berechnen. Einfacher ausgedrückt: alle möglichen Touren bilden und dann vergleichen, welche Tour am kürzesten ist. Dies ist für eine kleine Anzahl von Zielpunkten problemlos möglich. Allerdings wächst die Anzahl möglicher Touren extrem stark mit der Zahl an Zielpunkten, wie in der unten abgebildeten Tabelle zu sehen ist. Da “extrem stark” mathematisch etwas unpräzise ist, spricht man hier von faktoriellem Wachstum.

Faktorielles Wachstum ist auf der unten abgebildeten Skala zum Vergleich des Wachstums von Ordungsklassen ganz rechts und damit, salopp gesagt, nicht gerade das, was man gerne sehen würde. Es existieren zwar bessere exakte Lösungsverfahren, die aber immer noch exponentiell langsam sind. In der Komplexitätstheorie gehört das TSP zur Klasse der NP-schweren Probleme. Das bedeutet aus praktischer Sicht, dass sich das Problem nicht effizient optimal lösen lässt. Deswegen kommen in der Praxis in der Regel Heuristiken statt exakten Lösungsverfahren zum Einsatz. Heuristiken sind darauf ausgelegt, schnell eine gute Lösung zu finden, die aber nicht zwingend die optimale Lösung sein muss. Übertragen auf das TSP bedeutet das effizient eine kurze Tour zu finden, die aber nicht zwingend die kürzeste sein muss.

Aber wie berechnet man überhaupt die Länge einer Tour? Eine wichtige Voraussetzung zur Lösung des TSP ist, dass für jede Route zwischen zwei Punkten A und B die Distanz gegeben ist. Je nachdem worauf man optimieren möchte muss dies nicht die Wegstrecke sein, sondern kann z.B. auch die durchschnittliche Fahrtdauer sein. Dadurch lässt sich eine Distanzmatrix aufstellen, die ein wichtiger Grundbaustein für die Lösung des TSP ist. Mathematisch lässt sich das Problem dann als Graph darstellen. Jeder Punkt wird durch einen Knoten dargestellt und jede Route zwischen zwei Punkten als Kante zwischen den jeweiligen Knoten.

Da die Begriffe Touren- und Routenoptimierung immer mal wieder durcheinander geworfen werden, hier noch einmal die Unterscheidung: Bei Routenoptimierung geht es darum die optimale Route von einem Punkt A zu einem Punkt B zu finden. Tourenoptimierung baut darauf auf, es wird also davon ausgegangen, dass das Problem bereits gelöst ist. Hier fassen wir stattdessen verschiedene Zielpunkte zu einer Tour zusammen, wobei der Fokus auf eine Festlegung der Reihenfolge der Zielpunkte liegt.

Heuristische Lösungsverfahren für die Tourenoptimierung

Es gibt eine ganze Reihe an heuristischen Verfahren. Im folgenden stelle ich euch einen einfachen und, durch die häufige Verwendung in Einführungen zur Tourenoptimierung, recht bekannten Ansatz vor, den Greedy Approach. Danach gehe ich auf die spannenderen und praxisrelevanten Ansätze k-opt Swap und Ant Colony Optimization ein.

Greedy Approach

Die Grundidee des Greedy Approaches ist simpel: Wähle als nächsten Punkt immer den Zielpunkt, der dem vorherigem am nächsten liegt. Als greedy wird dieser Ansatz bezeichnet, da wir anfangs gierig nach möglichst kurzen Verbindungen suchen, was gegen Ende dazu führen kann, dass noch sehr ungünstige Strecken zurückgelegt werden müssen. Ihr erinnert euch an das Deutschland-Beispiel? Diese Lösung habe ich mit dem Greedy-Ansatz erstellt. Rechts seht ihr eine bessere Lösung, falls ihr sie oben nicht schon selbst gefunden habt. Die Gesamtdistanz ist mehr als 200 Kilometer kürzer.

k-opt swap

Das k-opt-swap-Verfahren ist eine so genannte Postoptimierungsheuristik. “Heuristik”, weil das Ziel ist, eine sehr gute, aber nicht zwingend optimale Lösung zu finden und “Postoptimierung” weil k-opt-swap auf einer ersten initialen Lösung basiert und sie verbessern soll. So kann beispielsweise mit Hilfe des greedy Verfahrens eine Ausgangslösung erstellt werden, die dann mit k-opt-swap weiter verbessert wird. Die Idee des Ansatzes ist es, k Verbindungen aus der bestehenden Lösungen herauszunehmen und durch k neue Verbindungen auszutauschen, wodurch wieder eine gültige Tour entstehen muss. Führt dieser Tausch zu einer Verbesserung, verringert sich also die Gesamtstrecke, so wird diese Änderung übernommen. Unten seht ihr ein Beispiel bei dem zwei Fahrten durch zwei kürzere ersetzt werden. Da ist also ein Beispiel für die 2-opt-swap-Variante. Die bessere Lösung in der Grafik oben wurde mit Hilfe dieses Ansatzes erzeugt. Zunächst habe ich mit dem Greedy-Verfahren eine Ausgangslösung erzeugt, die ich dann mit 2-opt-swap verbessert habe.

Ant Colony Optimization

Die Ant-Annealing-Colony-Optimization-Methode ist, wie der Name schon sagt, von Ameisenkolonien inspiriert und basiert auf der Pheromon-basierten Kommunikation von Ameisen. Diese hinterlassen Duftstoffe (Pheromone), um mit ihren Kolonie-Mitgliedern zu kommunizieren, z. B. bei der Suche nach neuen Nahrungsquellen. Die Idee lässt sich mit einem probabilistischen Algorithmus auf das Traveling Salesman Problem übertragen. Im Gegensatz zu den zuvor eingeführten deterministischen Verfahren, bei denen Wahrscheinlichkeiten und Zufall keine Rolle spielen, setzen probabilistische Verfahren auf eben diese. Der Algorithmus funktioniert folgendermaßen:

1. Eine virtuelle Ameise startet vom Ausgangspunkt und hat für ihre erste Strecke n Zielpunkte zur Auswahl. 
2. Der nächste Punkt wird durch das Ziehen einer Zufallszahl ausgewählt. Da zu Beginn noch keine Pheromonspuren verteilt wurden, haben alle Punkte die gleiche Wahrscheinlichkeit, gewählt zu werden.  
3. Es werden so lange Punkte ausgewählt, bis jeder Zielpunkt einmal besucht wurde.
4. Anschließend wird für die gewählten Strecken eine Pheromonspur verteilt. Je kürzer die Gesamtstrecke, desto stärker fällt diese aus.
5. Eine weitere Ameise startet. Stärkere Pheromonspuren führen dazu, dass es an einer Abzweigung wahrscheinlicher wird, dass eine Ameise der Spur folgt. 
6. Am Ende jeder Runde verdunstet auch ein Anteil der Pheromonspuren.

So legen die virtuellen Ameisen mit steigender Zahl an Durchläufen nach und nach immer kürzere Streckenkombinationen zurück, wodurch sich eine immer bessere Lösung für das Touring-Problem ergibt.

Im Gegensatz zu anderen Algorithmen hat dieser Ansatz den großen Vorteil, dass nachträgliche Änderungen, z.B. ein zusätzlicher Kunde der noch angefahren werden muss, eingebaut werden können, ohne dass wieder komplett von vorne gestartet werden muss. Wer etwas mehr Zeit hat, dem kann ich diesen super Science Slam zum gleichen Thema von Adrian Lison empfehlen: https://www.youtube.com/watch?v=xJZNRZIQZSw .

Zusammengefasst gilt: Zur Lösung des Traveling Salesman Problem gibt es eine Reihe verschiedener Verfahren. Da exakte Lösungsverfahren mindestens exponentielle Laufzeit haben und so schlecht mit wachsender Anzahl von Zielpunkten skalieren, verwenden wir in der Praxis in der Regel Heuristiken , mit denen sich gute, aber nicht zwingend die beste, Lösungen berechnen lassen. Im nächsten Blogartikel der Reihe werde ich euch zeigen, wie ihr in einem Python Jupyter Notebook kleinere gängige Tourenoptimierungs-Probleme lösen und visualisieren könnt.