Was ist das TSP, und warum es das Herz von OptiRoad ist

Wenn Sie 15, 30 oder 100 Kunden pro Tag beliefern, haben Sie bereits, ohne es zu wissen, TSP betrieben: das Traveling Salesman Problem, oder Problem des Handlungsreisenden. Es ist eines der meistuntersuchten Probleme der Informatik, und genau das löst OptiRoad jedes Mal, wenn Sie auf "Optimieren" klicken. Dieser Leitfaden erklärt in klaren Worten, worum es geht, warum es schwerer ist als es aussieht, und wie es in der Praxis gelöst wird.

Das Problem, in einem Satz

Sie haben einen Startpunkt (Ihr Lager, Ihr Zuhause) und eine Liste von Adressen, die Sie an einem Tag besuchen sollen. Welche Reihenfolge minimiert die zurückgelegte Gesamtstrecke? Das ist das TSP.

Trivial zu formulieren, brutal schwer zu lösen, sobald man ein Dutzend Adressen überschreitet. Und genau hier stößt die menschliche Intuition schnell an ihre Grenzen: Das Auge erkennt eine gute Tour mit 5 Stopps mühelos, eine gute Tour mit 40 Stopps deutlich schlechter. Was zunächst nach einem kleinen Detail klingt (in welcher Reihenfolge fahre ich?) entscheidet in Wirklichkeit über einen guten Teil Ihrer täglichen Fahrzeit und Ihrer Kosten.

Ein konkretes Beispiel

Stellen Sie sich 5 Lieferungen in Berlin vor:

• A: Mitte
• B: Kreuzberg
• C: Charlottenburg
• D: Prenzlauer Berg
• E: Steglitz

Wenn Sie vom Lager starten und in alphabetischer Reihenfolge A → B → C → D → E fahren, fahren Sie vermutlich kreuz und quer durch die Stadt. Konkret führt Sie diese alphabetische Route von Ost-Berlin in den Westen und wieder zurück: rechnen Sie mit rund 13 km. Mit intelligenter Umorganisation derselben 5 Adressen (zum Beispiel, indem Sie räumlich nahe Stopps gruppieren) sinkt die optimierte Reihenfolge auf etwa 9 km, also rund 30 % weniger für exakt dieselben Lieferungen. Die Adressen bleiben gleich, die Anzahl der Stopps bleibt gleich: Nur die Reihenfolge ändert sich, und allein das spart Strecke. Auf 200 Arbeitstage pro Jahr summieren sich diese Einsparungen pro Tour zu Tausenden Kilometern: Stunden Fahrzeit und ein nennenswertes Kraftstoffbudget.

Warum das TSP schwer ist

Bei 5 Adressen gibt es 5! = 120 mögliche Reihenfolgen. Ein Mensch kann sie von Hand testen. Bei 10 Adressen sind es 3,6 Millionen. Bei 20 sind es 2,4 Trillionen. Keine Maschine der Welt kann jede Kombination einer 30-Stopp-Tour in vernünftiger Zeit durchprobieren.

Das TSP ist ein sogenanntes NP-schweres Problem: Es ist kein Algorithmus bekannt, der die perfekte Lösung in einer Zeit garantiert, die vernünftig mit der Anzahl der Stopps skaliert. Jede zusätzliche Adresse vervielfacht den Lösungsraum, statt ihn nur zu vergrößern.

Merken: Bei 10 Adressen oder weniger kann man noch alle Kombinationen testen und das absolute Optimum garantieren. Darüber hinaus verwendet man Heuristiken, also Strategien, die eine sehr gute Lösung liefern, ohne mathematische Perfektion zu garantieren.

Ein wenig Geschichte

Das TSP ist nichts Neues. Mathematiker untersuchen es seit den 1930er-Jahren: Der österreichische Mathematiker Karl Menger erörterte es in Wien in seinem wissenschaftlichen Kreis, und das Problem verbreitete sich rasch an den amerikanischen Universitäten. Der Wendepunkt kam in den 1950er-Jahren bei der RAND Corporation, wo George Dantzig, Delbert Ray Fulkerson und Selmer Johnson 1954 die exakte Lösung einer berühmten Instanz veröffentlichten: eine optimale Tour, die 49 Städte der Vereinigten Staaten verband (eine je Bundesstaat, plus Washington). Das war eine bemerkenswerte Leistung für die damalige Zeit, erreicht mit Methoden der linearen Programmierung und viel Handrechnung. Noch heute bleibt das TSP ein Referenz-Benchmark in der Operations Research und der Logistik: Neue Algorithmen werden oft an diesen historischen Instanzen gemessen.

Die Ansätze in der Praxis

1. Brute Force (≤ 10 Stopps)

Alle möglichen Permutationen werden getestet, die beste behalten. Garantiert das absolute Optimum, wird aber jenseits von 10 Stopps unpraktikabel.

2. Nearest Neighbor (einfache Heuristik)

Bei jedem Schritt geht man zum nächstgelegenen verbleibenden Stopp. Schnell, aber oft weit vom Optimum: man kann fern vom Rest der Stopps stranden.

3. 2-opt (lokale Verbesserung)

Man startet von einer Initiallösung (oft via Nearest Neighbor), dann versucht man Kreuzungen "aufzulösen", indem Tour-Segmente umgekehrt werden. Iterativ, liefert typischerweise Ergebnisse innerhalb von 5 % des theoretischen Optimums.

4. Fortgeschrittene Algorithmen

Lin-Kernighan, simuliertes Abkühlen, genetische Algorithmen, Constraint Programming: Viele Ansätze existieren in der Operations Research. Sie können das letzte Quäntchen Genauigkeit herausholen, sind aber komplexer umzusetzen und zu warten. Für Geschäftsanwendungen wie Auslieferung bietet Nearest Neighbor + 2-opt den besten Kompromiss aus Einfachheit, Qualität und Geschwindigkeit: leicht verständlich, sehr schnell und auf realen Touren nahe am Optimum.

Perfektes Optimum oder sofort sehr gut?

Das ist die eigentliche Frage, wenn man ein Liefertool entwirft. Ein Solver kann die mathematisch perfekte Lösung anstreben, aber die kann auf einer großen Tour Stunden Rechenzeit erfordern. Im Arbeitsalltag wartet jedoch niemand Stunden, um loszufahren. Eine Lösung innerhalb weniger Prozent des Optimums, in Sekunden berechnet, schlägt deutlich eine perfekte Lösung, die zu spät kommt.

Warum? Weil die letzten Prozent eingesparter Strecke fast nie das Warten wert sind: Zwischen einer Tour mit 9,0 km und einer mit 8,8 km ist der Unterschied über Ihren Tag hinweg vernachlässigbar, während die Rechenzeit explodieren kann. Genau deshalb sind Heuristiken wie Nearest Neighbor + 2-opt die richtige technische Entscheidung: Sie liefern den Großteil des Gewinns, sofort und zuverlässig. Theoretische Perfektion ist Sache der Forscher; die tägliche Wirtschaftlichkeit ist Sache der Fahrer.

Die Varianten, die für die Lieferung zählen

Das "reine" TSP geht davon aus, dass man am Ende zum Startpunkt zurückkehrt. In der Praxis sind Ihre Bedingungen reicher:

• Open-Loop TSP: keine Rückkehr zum Lager (Sie enden beim letzten Kunden).
• VRPTW (Vehicle Routing Problem with Time Windows): jede Adresse hat ein Öffnungs-Zeitfenster (z. B. 9 bis 12 Uhr). Das nutzen Sie für Liefer-Zeitfenster.
• Multi-Fahrzeug-VRP: mehrere Fahrer, also wie verteilen Sie Stopps auf Fahrzeuge, um die Gesamtzeit zu minimieren?
• Kapazitiertes VRP: jedes Fahrzeug hat eine maximale Nutzlast.

OptiRoad verwaltet diese Varianten: VRPTW für Zeitfenster (Pro- und Business-Plan) und Multi-Fahrzeug-VRP mit Clarke-Wright-Savings-Algorithmus (Business-Plan, bis zu 10 Fahrzeuge). So bleibt derselbe Kern (eine möglichst kurze, sinnvolle Reihenfolge zu finden) auch dann nützlich, wenn Ihre Realität komplexer wird als das Lehrbuch-TSP.

Wie OptiRoad Ihr TSP löst

Bei jedem Klick auf Optimieren im Dashboard wendet OptiRoad folgende Strategie an:

1. Geocodiert Ihre Adressen (verwandelt sie in GPS-Koordinaten), falls nötig.
2. Erstellt die Distanzmatrix zwischen allen Punkten via OpenRouteService (oder Google Routes als Fallback).
3. Bei ≤ 10 Stopps: Brute Force, jede Permutation getestet, absolutes Optimum garantiert.
4. Sonst: Nearest Neighbor für die initiale Route, dann 2-opt zur Verfeinerung durch sukzessive Iterationen.
5. Wenn VRPTW aktiviert: der Solver respektiert Zeitfenster via einem Earliest Deadline First-Ansatz und meldet jede vorhersehbare Verspätung.
6. Bei Multi-Fahrzeug: Clarke-Wright Savings zum Verteilen der Stopps, dann lokales TSP auf jeder Tour.

Alles in wenigen Sekunden (3 Sekunden für 15 Stopps, bis zu 20 Sekunden für 150 Stopps mit adaptivem Timeout).

In der Praxis: was es für Sie ändert

Auf einer typischen 30-Lieferungs-Stadttour:

• Ohne Optimierung: etwa 120 km, etwa 5 h Fahrt
• Mit OptiRoad: etwa 85 bis 90 km, etwa 3,5 bis 4 h Fahrt
• Typischer Gewinn: 25 bis 30 % Strecke, 20 bis 30 % Zeit

Auf 200 Arbeitstage pro Jahr sind das Tausende Kilometer und Hunderte Stunden gespart. Hinzu kommen weniger Verschleiß am Fahrzeug, weniger Stress am Steuer und mehr eingehaltene Lieferzeitfenster. Und das alles, weil man ein Problem löst, das seit 1930 "das TSP" heißt.

Häufige Fragen

Wie viele Adressen kann OptiRoad optimieren?

Bis zu 150 Stopps pro Tour. Bis zu 10 Stopps testet Brute Force jede Kombination und garantiert das absolute Optimum. Darüber hinaus wechselt OptiRoad zu Heuristiken (Nearest Neighbor, dann 2-opt), die auch bei großen Touren hervorragend bleiben.

Ist die Tour immer die kürzestmögliche?

Ja, und bis 10 Stopps ist das mathematisch garantiert. Darüber hinaus liegt das Ergebnis dank 2-opt typischerweise innerhalb von etwa 5 % des theoretischen Optimums: ein im Alltag nicht spürbarer Abstand, bei nahezu sofortiger Berechnung. Für eine Liefertour ist das genau der richtige Kompromiss zwischen Qualität und Wartezeit.

Brauche ich einen Startpunkt?

Ja. Es braucht einen Startpunkt: ein Lager oder eine Heimatadresse. Der Endpunkt ist dagegen optional: Geben Sie keinen an, nimmt OptiRoad an, dass Sie zu Ihrem Startpunkt zurückkehren (eine Rundtour).

Wie lange dauert die Berechnung?

Wenige Sekunden. OptiRoad verwendet einen adaptiven Timeout: etwa 3 Sekunden für kleine Touren, bis zu 20 Sekunden für 150 Stopps. Wird das Limit erreicht, liefert das Tool trotzdem die beste gefundene Tour. In der Praxis haben Sie Ihre fertige Reihenfolge also, bevor Sie überhaupt den Motor gestartet haben.

Weiterführend

Wenn Sie den Algorithmus an Ihren eigenen Adressen erleben möchten, beinhaltet der OptiRoad Free-Plan 5 Touren pro Monat bis zu 10 Stopps, genau die Zone, in der Brute Force das absolute Optimum garantiert. Der beste Weg, konkret zu messen, was Sie sparen.

Wollen Sie tiefer in die Varianten eintauchen (Zeitfenster, Multi-Fahrzeug)? Lesen Sie weiter andere Blog-Artikel oder schauen Sie sich die API-Dokumentation an.