Fahrzeugeinsatz- und Tourenoptimierung

Disponenten bei Kurierdiensten, Großhändlern, Entsorgern und ambulanten Pflegediensten erstellen Tagestouren noch immer von Hand oder nach festen Routinen. Routenplanungs-Solver kombiniert mit ML-geschätzten Fahr- und Servicezeiten ordnen Stopps den Fahrzeugen zu und bringen sie in eine Reihenfolge, unter Beachtung von Zeitfenstern, Kapazität und Lenkzeitregeln, und planen im Tagesverlauf neu. Typisches Ergebnis: weniger Kilometer und Fahrzeuge bei gleichem Servicegrad, dazu geringere Emissionen und verlässlichere Ankunftszeiten.

Problem & Nutzen

• Heute: Disponenten arbeiten mit Tabellen, Kartenwerkzeugen oder der Erfahrung erfahrener Fahrer. Die Pläne sind starr, ignorieren reale Servicezeiten und brechen zusammen, wenn ein Eilauftrag, ein Stau oder eine Panne dazwischenkommt.
• Warum es schwierig ist: Das Tourenplanungsproblem (Vehicle Routing Problem, VRP) und seine Varianten (Zeitfenster, Abhol- und Lieferstopps, gemischte Flotte, mehrere Depots) sind NP-schwer; bei 100–10.000 Stopps kommt es auf gute Heuristiken an.
• KI-Nutzen: (1) Metaheuristik-, MIP- und CP-Solver finden in Sekunden bis Minuten Pläne von hoher Qualität; (2) ML ersetzt geschätzte Eingaben (Fahrzeit nach Uhrzeit, Servicezeit je Kunde, Risiko für nicht angetroffene Empfänger); (3) gelernte oder hybride Solver beschleunigen große Instanzen; (4) LLM-Assistenten lassen Disponenten Regeln in normaler Sprache formulieren (siehe OPT-018).
• Belege für den Nutzen: Routenoptimierung gehört zu den am besten dokumentierten Erfolgen des Operations Research (z. B. UPS ORION, beschrieben in den Arbeiten zum INFORMS Franz Edelman Award) [6]. Die Einsparungen hängen stark von der Qualität der Ausgangslage ab; behandeln Sie prozentuale Herstellerversprechen als Hypothesen für den Piloten und messen Sie sie an Ihren eigenen historischen Tagen.

Varianten

• Paketzustellung auf der letzten Meile sowie Essens-/Lebensmittellieferung: viele Stopps, enge Zeitfenster, vom Kunden gewählte Zeitfenster.
• Distribution / Großhandel / Außendienst: weniger, größere Stopps, Kapazitäts- und Beladungsrestriktionen (OPT-012).
• Müllabfuhr, Winterdienst, kommunale Touren: Kantenroutenplanung, oft im öffentlichen Sektor.
• Service- und Pflegetouren (ambulante Pflege, Techniker): Qualifikationen und Termine, siehe OPT-019.
• Abholung & Lieferung / FTL-LTL: gepaarte Stopps, Reihenfolgebeziehungen; Lkw unterliegen den EU-Lenkzeitregeln.
• Elektroflotten: Reichweite und Ladestopps, siehe OPT-021.
• Rufbus / bedarfsgesteuerter Verkehr: siehe OPT-028.
• Schulbus und öffentliche Ausschreibung: Varianten mit festem Fahrplan, siehe OPT-013.
• Privatnutzung: Besorgungs- und Wegeketten in Karten-Apps (kleine Mehrfachstopp-Planer); vernachlässigbarer Umfang.

So funktioniert es

1. Aufträge + Flotte + Depots
2. Geokodierung & Adressbereinigung
3. Fahrzeitmatrix (Straßennetz, Verkehrsprofile; ML-korrigiert)
4. Restriktionsmodell (Zeitfenster, Kapazität, Qualifikationen, Pausen, Lenkzeitrecht, Kostenfunktion)
5. Solver (Konstruktionsheuristik
6. lokale Suche / HGS / LNS; oder MIP/CP für kleine Fälle)
7. Prüfung durch die Disposition (Was-wäre-wenn, manuelle Sperren, Übersteuerung)
8. Übergabe an Fahrer-App / Telematik
9. Live-Verfolgung
10. Neuoptimierung bei Ereignissen (neuer Auftrag, Verspätung, Panne)
11. Rückfluss der Ist-Werte in das ML

• Der Kern ist klassische Optimierung: hybride genetische Suche (HGS), adaptive Suche in großen Nachbarschaften, Constraint Programming und GPU-parallele Heuristiken. ML ersetzt in den meisten Produkten den Solver nicht; es liefert bessere Eingaben und manchmal Startlösungen.
• ML-Komponenten: Regression von Fahr- und Servicezeiten aus Telematikdaten (Gradient Boosting), Modelle für die voraussichtliche Ankunftszeit (PRED-018), Nachfrageprognosen für die Vorplanung sowie neuronale/RL-Konstruktionsheuristiken als Beschleuniger auf Forschungsniveau.
• Mensch-in-der-Schleife (Human-in-the-Loop): Disponenten genehmigen Pläne, binden Kunden fest an Fahrer und bearbeiten Ausnahmen; Fahrer können Stopps ablehnen oder umsortieren, mit protokollierten Begründungen, die zu Trainingsdaten werden.

Datenaufbereitung

Die Routenplanung braucht saubere Stamm- und Auftragsdaten: Kundenadressen, Zeitfenster, Servicezeiten, Fahrzeug- und Fahrerdaten. Diese liegen typischerweise im ERP oder TMS, in Excel-Tabellen der Disposition und in Telematikportalen; manches Wissen steckt nur in den Köpfen der Fahrer (Zufahrtsbeschränkungen, Rampenhöhen, Schlüsselübergabe).

Typische Lücken sind ungeprüfte oder doppelte Adressen, fehlende Geokoordinaten, geschätzte Servicezeiten, veraltete Fahrzeugkapazitäten und auf Papier geführte Fahrerregeln.

Schritte der Aufbereitung: - Aufträge, Flotten- und Kundendaten exportieren (siehe PREP-005) und Dubletten zusammenführen. - Adressen mit einem Geocoder oder einem OSM-basierten Werkzeug geokodieren und prüfen; Fehlschläge manuell korrigieren. - Reale Service- und Fahrzeiten aus 3-6 Monaten GPS-/Telematikhistorie ableiten statt aus Schätzungen. - Ortswissen als strukturierte Stopp-Attribute (Zeitfenster, Zugangshinweise) über Interviews mit Disposition und Fahrern erfassen (PREP-016). - Festlegen, wer für die Qualität der Stammdaten verantwortlich ist (PREP-004).

Grober Anteil am Aufwand: etwa 30-40 Prozent des Projekts. Die Anforderungen an die Datenmenge sind moderat, aber die Qualität von Adressen und Zeiten entscheidet über die Planqualität. Führen Sie zuerst die Prüfung der Datenreife aus GUIDE-003 durch.

Umsetzungswege

Welcher Weg für wen

• KMU: Weg A. Es gibt ausgereifte, in der EU hostbare Tourenplanungs-SaaS zu Preisen je Fahrzeug, und das Routing-Problem ist Standard.
• Großunternehmen: Weg B. Die Routenplanung ist ein zentraler Kostenhebel; ein Solver in der eigenen Cloud mit TMS-/ERP-Anbindung vermeidet Gebühren pro Stopp und Abhängigkeit vom Anbieter.
• Entwickler: Weg C. OR-Tools oder PyVRP laufen auf HW1 und geben volle Kontrolle über Restriktionen und Kosten.
• Öffentlicher Sektor: Weg C. Open-Source-Solver auf souveräner Infrastruktur erleichtern die Beschaffung und halten Bürgeradressen (Müll, ambulante Pflege) im eigenen Haus.

Weg A — Kaufen (Standardsoftware) (empfohlen für die meisten KMU und den gehobenen Mittelstand)

• SaaS für Routenplanung & Disposition: Routific, Circuit, OptimoRoute, Onfleet, Locus, Track-POD, Descartes, Trimble, Omnitracs, Bringg; ERP-/TMS-Module von SAP TM und Oracle.
• EU-Anbieter: PTV Group (PTV Route Optimiser, PTV Developer, DE), Quintiq/Dassault (Planung, NL/FR), TourSolver / Mapotempo (FR), Timefold (BE) als Solver-Plattform; ORTEC (NL).
• Weg A wählen, wenn: bis zu einigen hundert Fahrzeugen, Standardrestriktionen, keine ungewöhnlichen Regeln. Prüfen: Telematik-Anbindung, Datenhaltung in der EU, Fahrer-App, Unterstützung des Lenkzeitrechts, API-Zugang.

Weg B — Auf Cloud-KI-Diensten aufbauen

• APIs zur Routenoptimierung: Google Maps Platform Route Optimization API, Microsoft/Azure Maps Routing, HERE Tour Planning API (HERE hat seinen Sitz in der EU), PTV Developer APIs, TomTom Routing- und Matrix-APIs, Mapbox Optimization API (kleine VRPs).
• Solver-Dienste in der Cloud: Gurobi, FICO Xpress oder Hexaly (FR) gehostet; NVIDIA cuOpt als Dienst.
• Orchestrierung: n8n/Airflow-Job, der Aufträge einspeist, Matrix abruft, den Solver aufruft und das Ergebnis an die Fahrer-App sendet; eine LLM-Schicht kann Wünsche der Disposition in Restriktionsänderungen übersetzen (OPT-018).
• Weg B wählen, wenn: Sie eigene Regeln brauchen oder die Lösung in ein eigenes Produkt einbetten wollen.

Weg C — Selbst betreiben (Open Source)

• Solver: Google OR-Tools (Routing-Bibliothek, CP-SAT), PyVRP (HGS-basiert, starke Benchmark- Ergebnisse), VROOM (schnelle C++-Engine), Timefold Solver (Java/Kotlin/Python), jsprit, LKH-3, NVIDIA cuOpt (als Open Source veröffentlichter GPU-Solver), HiGHS für MIP-Anteile.
• Routing-/Matrix-Engine: OSRM, Valhalla oder GraphHopper auf OpenStreetMap-Daten (Geofabrik-Extrakte).
• Hardware: HW1 (CPU-Server) genügt für die meisten Flotten; GPU (HW2) nur für Instanzen in cuOpt-Größe.
• Betriebsaufwand: Aktualisierung der Kartendaten, Verkehrsprofile, Überwachung der Rechenzeiten; 1 Ingenieur in Teilzeit.

Weg D — Eigenes Training

Lohnt sich für sehr große, wiederkehrende Probleme (nationale Paketnetze) oder besondere Restriktionen. Fahr- und Servicezeitmodelle mit 6–12 Monaten Telematikdaten trainieren; Forschung zu neuronaler kombinatorischer Optimierung und RL-basierter Konstruktion (z. B. Attention-Modelle für das Routing, gelernte HGS-Komponenten) kann die Rechenzeit senken, muss aber auf Ihren Daten gut abgestimmte klassische Solver schlagen, um den Aufwand zu rechtfertigen.

Stand der Technik (2026)

• Benchmarks: Die DIMACS Vehicle Routing Challenge und die Instanzen von Solomon/Gehring-Homberger/X zeigen, dass Solver vom Typ HGS und LNS (PyVRP, HGS-CVRP, FILO) weiterhin schwer zu schlagen sind; gelernte Solver helfen vor allem bei Geschwindigkeit und Startlösungen [3].
• GPU-Optimierung: NVIDIA hat cuOpt als Open Source veröffentlicht; es parallelisiert VRP-Heuristiken für große Instanzen [2].
• Dynamisches und stochastisches Routing: Neuoptimierung binnen Sekunden bei neuen Ereignissen ist in kommerziellen Werkzeugen Standard; vorausschauende Modelle für Stoppzeiten machen Pläne realistischer.
• LLM-Assistenten: Was-wäre-wenn-Analysen und Formulierung von Restriktionen in natürlicher Sprache auf Basis von Solvern; LLMs sollen in Solver-Modelle übersetzen, nicht selbst Routen „lösen“ (schwach bei kombinatorischer Optimalität).
• Grenzen und Fehlerbilder: schlechte Geokoordinaten, falsche Servicezeiten, ignoriertes stilles Fahrerwissen (Zufahrtsbeschränkungen, Parken), Planinstabilität (kleine Änderungen kippen alle Routen) und Überoptimierung, die keinen Puffer für Verspätungen lässt.

Gemeinsame Bausteine & Kombinationen

• Gleicher Stack (optimization-solver + time-series): OPT-019 Technikereinsatzplanung, OPT-028 Ridepooling, OPT-003 Personaleinsatzplanung, OPT-005 Bestandsauffüllung (liefert Liefermengen).
• Vorgelagert: PRED-018 Prognose der Ankunftszeit, OPT-005 Bestand, DOC-006 Transportdokumente.
• Nachgelagert/verwandt: OPT-021 Ladebeschränkungen für Elektrofahrzeuge, OPT-012 Ladungsplanung, VIS-028 Überwachung im Fahrerhaus (getrennt zu betrachten, hochsensibel, siehe Risiken), ROBO-020 Lieferroboter.
• Fahrzeitmatrizen und Kartendaten lassen sich in allen Routing-Anwendungsfällen wiederverwenden.

Aufwand, Kosten & Kennzahlen

• Weg A: Tage bis Wochen; üblich sind monatliche Preise je Fahrzeug oder je Stopp.
• Weg B: 1–3 Monate inkl. Anbindung an Auftragsverwaltung und Fahrer-App.
• Weg C: 2–4 Monate; geringe Hardwarekosten, Hauptkosten sind Entwicklung und Betrieb der Kartendaten.
• Kennzahlen: Gesamt-km und Fahrstunden, eingesetzte Fahrzeuge, Stopps pro Routenstunde, Quote pünktlicher bzw. im Zeitfenster erfolgter Zustellungen, Zustellquote beim ersten Versuch, Abweichung zwischen Plan und Ist, CO2 je Paket, Planungszeit der Disposition pro Tag, Akzeptanzquote der Pläne bei den Fahrern.

Menschen & Veränderung

Beziehen Sie die Geschäftsleitung (Budget, Kennzahlen) und die Leitung der Disposition von Anfang an ein; Disponenten sind die wichtigsten Anwender und sollten die Regeln mitdefinieren. Holen Sie die IT für die Anbindung von TMS/ERP und Telematik, die Datenverantwortlichen für Adress- und Kundenstammdaten sowie früh den Betriebsrat dazu.

Betriebsrat: abhängig vom Einzelfall. Tourenplanung allein ist keine Überwachung, aber Fahrer-GPS, voraussichtliche Ankunftszeiten und Pünktlichkeitsquoten machen das System objektiv geeignet, Verhalten oder Leistung zu überwachen, daher greift in der Regel die Mitbestimmung nach §87 Abs. 1 Nr. 6 BetrVG; §90 Abs. 1 Nr. 3 verlangt rechtzeitige Information über KI-geplante Arbeitsabläufe. Öffentlicher Dienst: Personalrat. Vereinbaren Sie die Zwecke (kein individuelles Leistungsranking) in einer Betriebsvereinbarung (GUIDE-004).

Datenschutz: Standortdaten der Fahrer und Adressen von Privatkunden sind personenbezogene Daten; beziehen Sie die/den Datenschutzbeauftragte(n) ein, schließen Sie mit dem Anbieter einen AVV und prüfen Sie, ob eine DSFA nötig ist (GUIDE-005).

KI-Kompetenz: Schulen Sie Disponenten und Fahrer kurz darin, was der Solver optimiert und wo er irrt; das unterstützt die KI-Kompetenz, die Art. 4 der KI-Verordnung (AI Act) verlangt (GUIDE-006).

Kommunikation und Pilot: Beginnen Sie mit einem Depot oder einer Tourengruppe, vergleichen Sie Pläne mit den realen Touren und gehen Sie auf typische Sorgen ein (Fahrer fürchten stärkere Kontrolle, Disponenten fürchten, ersetzt zu werden). Disponenten behalten das letzte Wort und können jede Tour übersteuern; siehe GUIDE-008.

Risiken, Regulierung & Compliance

• KI-Verordnung (AI Act): in der Regel minimales Risiko. Achten Sie auf die Grenze zu Anhang III Nr. 4 (Beschäftigung): Verteilt das System Aufgaben auf Grundlage von individuellem Verhalten oder persönlichen Merkmalen und überwacht oder bewertet es Beschäftigte (z. B. Fahrerbewertung, die die Aufgabenverteilung steuert), kann es ein Hochrisiko-System sein [4]. Halten Sie Routenplanung und Leistungsbewertung getrennt. Für die Routenplanung selbst entsteht kein Problem nach Art. 5; die KI-Kompetenz (Art. 4) gilt.
• DSGVO: Kundenadressen, Lieferzeitfenster und GPS-Spuren der Fahrer sind personenbezogene Daten; Mitbestimmung des Betriebsrats in Deutschland (BetrVG §87) bei der Fahrerortung; Zweckbindung, Speicherfristen für GPS-Daten, DSFA bei kontinuierlicher Ortung [5].
• Branchenregeln: Die EU-Lenk- und Ruhezeitvorschriften (Verordnung (EG) 561/2006 und Änderungen) müssen als harte Restriktionen im Modell stehen; Zufahrtsbeschränkungen in Städten und Umweltzonen; Arbeitszeitregeln.
• Risiken und Gegenmaßnahmen: unsichere oder unrealistische Pläne (Puffer einplanen, Feedback-Schleife mit Fahrern), unfaire Arbeitsbelastung (Fairness-Restriktionen), Abhängigkeit vom Anbieter (offene Datenformate, Export der Restriktionen), Einhaltung der Lizenz der Kartendaten (OSM ODbL, Namensnennung).

Erste Schritte

1. 30–60 Tage reale Aufträge, Stoppzeiten und GPS-Spuren exportieren; Ausgangswerte für km, Stunden und Pünktlichkeitsquote berechnen.
2. Harte Restriktionen (Zeitfenster, Fahrzeugtypen, Lenkzeitrecht) und weiche (bevorzugter Fahrer) auflisten.
3. 5–10 historische Tage mit zwei Werkzeugen aus Weg A oder mit OR-Tools/PyVRP neu planen und mit den tatsächlichen Touren vergleichen.
4. Pilot in einem Depot, in dem die Disposition übersteuern kann; Übersteuerungen und Rückmeldungen der Fahrer protokollieren.
5. Geschätzte Service-/Fahrzeiten durch ML-Schätzungen aus der Telematik ersetzen, dann Live-Neuoptimierung ergänzen.

Quellen

1. Google OR-Tools — Vehicle Routing — https://developers.google.com/optimization/routing
2. NVIDIA cuOpt — https://github.com/NVIDIA/cuopt
3. PyVRP — https://github.com/PyVRP/PyVRP
4. Regulation (EU) 2024/1689 (AI Act), Annex III — https://eur-lex.europa.eu/eli/reg/2024/1689/oj
5. EDPB — Guidelines 01/2020 on connected vehicles and mobility applications — https://www.edpb.europa.eu/our-work-tools/our-documents/guidelines/guidelines-012020-processing-personal-data-context_en
6. INFORMS — UPS ORION, Franz Edelman Award — https://www.informs.org/Impact/O.R.-Analytics-Success-Stories/UPS-On-Road-Integrated-Optimization-and-Navigation-ORION-Project
7. VROOM project — https://github.com/VROOM-Project/vroom
8. Timefold Solver — https://github.com/TimefoldAI/timefold-solver
9. Regulation (EC) 561/2006 on driving times and rest periods — https://eur-lex.europa.eu/eli/reg/2006/561/oj