Was ist Routenoptimierungssoftware?
Das Problem hinter der Software
Routenoptimierungssoftware löst ein konkretes mathematisches Problem: das Vehicle Routing Problem (VRP), erstmals 1959 von George Dantzig und John Ramser formalisiert. Die Frage ist einfach — welche Routen sind für eine Fahrzeugflotte optimal, um alle Kunden zu bedienen?
Die Antwort ist alles andere als einfach. Das VRP ist als NP-schwer klassifiziert — kein bekannter Algorithmus kann in angemessener Zeit eine optimale Lösung für alle Fälle garantieren.
Die kombinatorische Explosion
Bei nur 15 Stopps gibt es über 1,3 Billionen mögliche Reihenfolgen. Bei 20 Stopps sind es 2,4 Trillionen — mehr als die geschätzte Anzahl Sandkörner auf der Erde. Bei 25 Stopps: 1,55 x 10^25 Permutationen.
Kein menschlicher Planer kann diese Optionen bewerten. Ein Algorithmus bewertet Millionen pro Sekunde.
Wie die Software funktioniert
Moderne Routenoptimierung nutzt einen mehrstufigen Ansatz:
- Geokodierung — Adressen in Koordinaten umwandeln
- Distanzmatrix — reale Fahrzeiten zwischen allen Punkten berechnen (auf Basis des Straßennetzes, nicht Luftlinie)
- Constraint-Modellierung — Geschäftsregeln wie Zeitfenster, Fahrzeugkapazität, Pausen und Qualifikationen kodieren
- Optimierung — Solver-Algorithmen für nahezu optimale Routen ausführen
- Ausgabe — Routenreihenfolgen, ETAs und Navigation generieren
Die Algorithmen
Kommerzielle Software kombiniert typischerweise mehrere Ansätze:
- Konstruktionsheuristiken wie der Clarke-Wright Savings Algorithmus (1964) erstellen schnell eine Ausgangslösung
- Metaheuristiken wie Adaptive Large Neighborhood Search, Tabu Search und Simulated Annealing verbessern diese Lösung iterativ
- Constraint Programming handhabt das komplexe Zusammenspiel von Zeitfenstern, Kapazitäten und Qualifikationen
Moderne Solver erreichen Lösungen innerhalb von 0,5–1% des mathematischen Optimums für Instanzen mit hunderten Stopps.
Was sie berücksichtigt
Routenoptimierung geht weit über den „kürzesten Weg" hinaus:
- Zeitfenster — Kunden nur zu bestimmten Zeiten erreichbar
- Fahrzeugkapazität — Gewichts-, Volumen- oder Stücklimits
- Qualifikationsabgleich — der richtige Techniker für den richtigen Auftrag
- Lenkzeiten — gesetzliche Arbeitszeiten und Pflichtpausen
- Verkehr — Echtzeit- und prognostizierte Staumuster
- Ausgewogene Auslastung — faire Verteilung auf alle Fahrer
Die Zahlen
Das ORION-System von UPS spart etwa 100 Millionen Meilen pro Jahr — rund 10 Millionen Gallonen Treibstoff und 100.000 Tonnen CO2. UPS hat öffentlich erklärt, dass eine Meile weniger pro Fahrer pro Tag dem Unternehmen 50 Millionen Dollar jährlich spart.
Branchenweit reduziert Routenoptimierung die Fahrstrecke typischerweise um 20–40% gegenüber manueller Planung, mit Kraftstoffeinsparungen von 10–30%.
Wer sie nutzt
Jedes Unternehmen mit Fahrzeugen, die mehrere Standorte anfahren: Lieferdienste, Außendienst (Heizung, Schädlingsbekämpfung, Reinigung), Abfallentsorgung, Gesundheitswesen, Einzelhandel und Bauzulieferung. Das mathematische Problem ist identisch — nur die Randbedingungen unterscheiden sich.