Die klassische Entscheidung eines Distributors, der täglich aus einem Depot 5-30 Kunden beliefert: Wie viele Fahrzeuge fahren los, welches Fahrzeug bedient welche Kunden, in welcher Reihenfolge — Kapazität nicht überschritten, Gesamtstrecke minimal. Akademisch: Capacitated Vehicle Routing Problem (CVRP); kanonischer Vorfahr der VRP-Familie, eröffnet von Dantzig und Ramser 1959.
Kurz gesagt
Kommt Ihnen das bekannt vor?
- Wir liefern täglich aus unserem Depot an 30-100 Kunden — Händlerbelieferung, B2B-Ersatzteile, Lebensmittel-Getränke-Distribution, Single-Depot-Betrieb.
- Die Bestellung jedes Kunden ist in kg oder m³ bekannt; der Disponent gruppiert die Kunden nach Gefühl, um die 2-5 t Fahrzeugkapazität nicht zu überschreiten.
- Die Kunden haben keine oder sehr weite Zeitfenster (Annahme 08:00-18:00) — sie nehmen zu jeder Stunde an.
- Zwei benachbarte Kunden landen manchmal auf zwei verschiedenen Fahrzeugen — die Entscheidung 'welches Fahrzeug in welche Zone diese Woche' folgt dem alten Plan.
- Wie viele Fahrzeuge morgens aus dem Depot fahren, entscheidet der Disponent — manche Tage reichen 3, manchmal fahren 5 raus, keine klare Regel.
- Kraftstoff plus Fahrerlöhne machen 30-50 % der Betriebskosten aus, aber niemand weiß, wie viele Kilometer eine Routenänderung sparen würde.
- Bei einem neuen Kunden wird 'auf welches Fahrzeug passt das' aus dem Bauch entschieden, nicht berechnet.
Warum es wichtig ist
Wie wird es gelöst?
Technische Tiefe
Wie wird es gelöst?
Technische TiefeIn einem Satz: Statt für jeden Kunden eine separate Depot-Fahrt zu machen, berechne wie viele km eingespart werden, wenn zwei Kunden auf demselben LKW fahren, fusioniere die einsparungsstärksten Paare solange die Kapazität reicht — läuft in Sekunden; Lokalsuche darübergelegt erhöht die Qualität.
CVRP ist das kanonische und älteste Mitglied der VRP-Familie in der Operations-Research-Literatur (Disziplin, die Mathematik und Computer für Geschäftsentscheidungen einsetzt). Die Arbeit aus dem Jahr 1959 (“The Truck Dispatching Problem”) eröffnete das Feld. Ein Depot, mehrere Fahrzeuge, Kapazitätsrestriktion, Kundennachfrage; keine Zeitfenster. Lösung in drei Stufen:
1. Modellierung. Eingangsdaten: Depotstandort (eine Koordinate), Kundenstandorte und Bedarfsmengen (kg, m³, Pakete — gleich welche Einheit, Summe darf Kapazität nicht überschreiten), Fahrzeugflotte (homogen — alle gleiche Kapazität; heterogen — unterschiedliche Kapazitäten), Distanzmatrix Depot–Kunde und Kunde–Kunde (symmetrisch — A→B = B→A; asymmetrisch — Einbahnstraßen verändern die Werte). Nebenbedingungen: jeder Kunde wird genau einmal besucht, jede Tour beginnt und endet am Depot, Gesamtnachfrage einer Tour übersteigt nicht die Fahrzeugkapazität. Optional: maximale Tourlänge (Fahrerschicht), Maximalzahl Kunden pro Tour, Open VRP (Fahrzeug endet beim letzten Kunden, kehrt nicht zurück — Mietfahrzeug-Szenarien), Multi-Depot-VRP. Zielfunktion meist Gesamtstrecke minimal (oder Kraftstoff); sekundär kann Fahrzeuganzahl minimiert werden.
2. Solver-Entscheidung. Drei Hauptansätze:
- Klassische Heuristik — Clarke-Wright Savings (1964): Jeder Kunde startet auf eigener Tour (Depot → Kunde → Depot). Die “Ersparnis” aus dem Zusammenführen zweier Touren wird berechnet: liegen A und B auf getrennten Touren und werden verschmolzen, wie viel Strecke wird gespart? Das Paar mit der größten Ersparnis wird verschmolzen, solange die Kapazität es zulässt. Auch ohne Computer berechenbar; läuft in Sekunden für 100-200 Kunden; liefert in der Regel 5-10 % vom Optimum entfernt. Sechzig Jahre später ist es noch immer ein praktischer Ausgangspunkt für mittlere Operationen.
- Exact MIP — Branch-and-Cut-and-Price (Branch-Cut-Price — Baumsuche, verstärkt durch Spaltengenerierung): liefert Optimum für 50-200 Kunden, aber Lösungszeit Minuten bis Stunden. Für wöchentliche oder saisonale Planung geeignet — schwer für tägliche dynamische Planung. MIP = Mixed-Integer Linear Programming (Optimierung mit teils 0/1-, teils stetigen Variablen).
- Metaheuristiken — 2-opt, Or-opt, ALNS (Adaptive Large Neighborhood Search — adaptive Großnachbarschaftssuche, intelligentes Verfahren, das Teile der Lösung herausreißt und neu einfügt): Lokal-Verbesserungs-Operatoren (“zwei Kanten tauschen”) auf der Clarke-Wright-Ausgabe heben die Lösung schrittweise an. Praktisch für 200-1000 Kunden; in Minuten innerhalb von 2-5 % des Optimums.
Praxiswahl: unter 50 Kunden — Exact MIP (Optimum-Garantie); 50-200 Kunden — Clarke-Wright + 2-opt; 200+ Kunden — ALNS oder ähnliche Metaheuristik.
3. Felddeployment. Die Ausgabe ist eine geordnete Liste an Fahrer-Tablet oder Ausdruck: “Fahrzeug 1 — 08:30 Abfahrt Depot → Kunde A (1,2 t) → Kunde C (0,8 t) → Kunde F (1,5 t) → Rückkehr Depot.” Das Auftragsmanagement (ERP oder eigenständige Dispo-Software) füttert den CVRP-Solver: Auftragsliste, Bedarfe, Flottenzustand, Depotbestand. Abends oder früh morgens berechnet; bei Tagesneueinträgen Rolling-Horizon-Replanning (5-15 Minuten). Monatliche Operations-Sitzung: Ist vs Plan km, Ist vs Plan Fahrzeuge, Einsparbericht.
Alternativen
Manuell + Tabellenkalkulation + Disponent
KostenlosKeine Lizenz
Für wen geeignet: 1-3 Fahrzeuge, 15-30 Kunden/Tag, festes Gebiet
- + Keine Softwarekosten
- + Erfahrung des Disponenten im Vordergrund
- + Schnelle Anpassung per Telefon
- − Planqualität bricht ab 30-50 Kunden ein
- − Keine Garantie optimaler Kapazitätsnutzung
- − Lange Einarbeitung neuer Disponenten
- − Keine historische km/Fahrzeug-Statistik
Lokale Tourenplanungs-Software (KMU)
Enterprise500-3.000 EUR Setup + 200-800 EUR/Monat Abo
Für wen geeignet: 5-15 Fahrzeuge, 50-200 Kunden/Tag, ein Depot
- + Lokale Adress- und Kartendaten integriert
- + Deutsche Oberfläche, lokaler Support
- + Fahrer-App enthalten
- − Engine typisch ein einfaches Savings- oder Nearest-Neighbor-Verfahren; schwach unter komplexen Nebenbedingungen
- − Multi-Depot oder Flotten mit verschiedenen Kapazitäten schwach
- − Algorithmus-Transparenz begrenzt — 'warum diese Tour' lässt sich kaum beantworten
Internationale spezialisierte Tourenplanungs-Software
Enterprise100-500 EUR/Fahrzeug/Monat Abo oder 50.000-250.000 EUR/Jahr Lizenz
Für wen geeignet: 20-100 Fahrzeuge, mehrere Depots, heterogene Flotte, komplexe Nebenbedingungen
- + Ausgereift: kapazitierte Routenplanung plus Erweiterungen (Flotten mit gemischten Kapazitäten, Touren ohne Depot-Rückkehr, Multi-Depot) voll unterstützt
- + Fortgeschrittene Such-Engines für große Größenordnungen
- + Starke Szenariovergleiche
- − Hohe Lizenz + 3-6 Monate Einführung
- − Deutscher Support kann begrenzt sein
- − Breites Schulungsprogramm
Open-Source-Solver + Eigenentwicklung
Open SourceLizenz kostenlos; Eigenentwicklung 8-16 Wochen oder 30.000-100.000 EUR Beratung
Für wen geeignet: Distributor mit Tech-Team, ERP-Integration gewünscht
- + Keine Lizenzkosten
- + Kapazitierte Routenplanung in Open-Source-Solvern gut unterstützt
- + Savings-Verfahren + lokale Verbesserung als Referenzimplementierungen breit verfügbar
- − Interne Optimierungs- und Software-Expertise nötig
- − 6-12 Monate bis zur Feldreife
- − Wartungslast beim Betreiber
Empfehlung
Im Gespräch fragen
- Welche Engine — Savings-Verfahren, Solver mit Optimum-Garantie, fortgeschrittene Such-Engine oder einfaches Nearest-Neighbor? Demonstrieren Sie an 50 Kunden, welches Verfahren das Ergebnis erzeugt.
- Gleiche Kapazitäten oder auch Flotten mit gemischten Kapazitäten? Wird in einer Flotte mit gemischten Kapazitäten die Fahrzeug-Kunde-Zuordnung von der Engine entschieden?
- Werden Touren ohne Depot-Rückkehr (Mietfahrzeuge, Fahrzeug endet beim letzten Kunden) und Multi-Depot-Routing unterstützt?
- Wie wird die Distanzmatrix berechnet — Luftlinie, reale Straßendistanz oder verkehrsadjustierte Zeit? Wie wurde die regionale Genauigkeit geprüft?
- Wenn tagsüber ein neuer Auftrag eintrifft, wird der Plan neu gelöst? In wie viel Sekunden erreicht die aktualisierte Tour den Fahrer?
- Werden Tourlängenlimits (z. B. max 6 h oder 300 km) und Fahrer-Schichtgrenzen auf Engine-Ebene durchgesetzt oder nachgefiltert?
- Welcher Einsparbericht lässt sich nach 8-12 Wochen Pilot mit Echtdaten gegenüber der vorigen manuellen Planung erstellen?
- Wenn wir den Vertrag beenden, in welchem offenen Format (CSV, GeoJSON oder ähnlich) lassen sich Kundenstandorte, Auftrags- und Tour-Historie sowie die Distanzmatrix exportieren?
Technische Details
Anmerkung der Redaktion
In der täglichen Sprache heißt dieses Problem “Tourenplanung”, “Verteilplan” oder “Liefersequenz”. Akademisch lautet der Name Capacitated Vehicle Routing Problem (CVRP) — das älteste und kanonische Mitglied der VRP-Familie. Dantzig und Ramser eröffneten 1959 das Feld. Die Frage, die Sie jeden Morgen stellen — “wie viele Fahrzeuge, welches Fahrzeug zu welchen Kunden, in welcher Reihenfolge, Kapazität nicht überschritten” — ist die Frage, an der die Forschung seit über 60 Jahren arbeitet.
Diese Seite darf nicht mit VRPTW (#002) verwechselt werden: VRPTW fügt für jeden Kunden ein Zeitfenster hinzu (“der Laden ist nur 09:00-12:00 geöffnet”). CVRP hat keine Zeitfenster — der Kunde ist den ganzen Tag verfügbar. Es ist der Unterschied zwischen Veganer-Liefer-Stunden und B2B-Lieferung mit flexibler Zeit. CVRP ist einfacher (weicher); VRPTW ist realistischer, aber mathematisch schwerer. Wenn Ihre Kunden wirklich flexible Annahmezeiten haben — Händlerbelieferung, B2B-Ersatzteile, Wasser-Getränke-Distribution — dann ist das Ihre Seite. Bei engen Zeitfenstern (E-Commerce-Hauszustellung, Kühlkette) siehe #002.
Im Segment am häufigsten übersehen: die praktische Stärke des Clarke-Wright-Savings-Algorithmus. 1964 für Papier-und-Bleistift-Berechnung entwickelt, als Computer noch nicht verfügbar waren, liefert diese Heuristik noch sechzig Jahre später Ergebnisse innerhalb von 5-10 % des Optimums für mittlere Operationen, in Minuten. Wenn ein Software-Anbieter eine “proprietäre Heuristik” oder “patentierten Optimierungsmotor” bewirbt, fragen Sie nach einem Benchmark-Vergleich an 50 Kunden gegen Clarke-Wright + 2-opt. Liegt der Abstand unter 2 %, lohnt sich der Aufpreis nicht. Zweiter übersehener Punkt: Qualität der Distanzmatrix. Viele Werkzeuge nutzen Luftlinie (Euklid); reale urbane Straßendistanzen sind 1,3-1,8× höher. Falsche Distanz heißt falsche Tour — die reale Straßenmatrix muss im Pilot getestet werden.
Schritt-für-Schritt für ein KMU
Phase 1 — Erst messen, dann planen. Mindestens 4 Wochen lang Tabelle führen: pro Fahrzeug tägliche km, Kundenzahl, Kapazitätsausnutzung (Ladung / Maximum), Tourdauer Depot–Depot, Fahrerstunden. Ohne diese Basis lässt sich keine Software bewerten.
Phase 2 — Kunden-Bedarfs-Tabelle erstellen. Pro Kunde: typische Bestellmenge (kg oder m³), Adresse, Koordinaten, Beschränkungen (Fahrzeuggrößenlimit — “großer Lkw kann nicht hinein”, manuelle Entladezeit). In den meisten KMU lebt diese Information nur im Kopf des Disponenten; sie aufzuschreiben bringt 5-10 % Effizienz.
Phase 3 — Pilot. 6-10 Wochen. 1-3 Fahrzeuge. Erfolgskriterium schriftlich vor Start: “in 60 Tagen Gesamtkilometer -10 %, Kapazitätsausnutzung +5 %, tägliche Fahrzeuganzahl -1.” Bei Verfehlung endet der Pilot — Ausstiegsrecht im Vertrag sichern.
Phase 4 — Rollout. 2-4 Monate auf die volle Flotte. Fahrertraining 1-2 Wochen. Ein “Champion”-Fahrer pro Zone. Monatliche Operations-Sitzung: Ist vs Plan km, Kapazitätsausnutzung, Kosten pro Kunde.
Risiken — was schiefgehen kann
- Bedarfsprognose driftet. Liegt die tägliche Bestellung 20-50 % neben dem Plan, ist die Kapazität halb leer oder überschritten. Bestell-Cut-off und Routenberechnungs-Zeit so nah wie möglich; Rolling-Horizon-Replanning ist Pflicht.
- Fahrzeugausfall tagsüber. Bricht ein Fahrzeug auf der Strecke aus, führt intuitive Umverteilung der verbleibenden Kunden zu Kapazitätsüberlauf oder ausgelassenem Kunden. Die Software muss Tagesneuberechnung unterstützen — neuer Plan in 30 Minuten.
- Kundenwunsch zu Zeitfenstern entsteht später. Sagt ein Kunde “ich nehme nur vormittags an”, bricht das CVRP-Modell — es wird zu VRPTW. Sobald die Zahl der Zeitfenster im Kundenstamm 10-20 überschreitet, ist die Umstellung auf einen VRPTW-Solver nötig.
- Bindung an einen TMS-Anbieter. Ohne Vertragsklausel zum jährlichen Export von Kundenstandorten, Auftrags- und Tourenhistorie in Standardformaten (CSV oder GeoJSON) bedeutet ein Anbieterwechsel den Verlust des operativen Gedächtnisses des Distributors.
Technische Sicht auf die Lösung
Hauptansätze in der CVRP-Literatur:
| Ansatz | Typische Größe | Lösungszeit | Optimum garantiert? |
|---|---|---|---|
| Heuristik (Disponent + Regel) | 1-3 Fahrzeuge, 15-30 Kunden | sofort | Nein, 50-80 % optimal |
| Clarke-Wright Savings (1964) | 50-200 Kunden | Sek-Min | Nein, 5-10 % vom Optimum |
| Clarke-Wright + 2-opt / Or-opt | 50-300 Kunden | Minuten | Nein, 3-7 % vom Optimum |
| Exact MIP — Branch-and-Cut-and-Price | 50-200 Kunden | Min-Std | Ja (im begrenzten Maßstab) |
| ALNS-Metaheuristik | 200-1000 Kunden | Minuten | Nein, 2-5 % vom Optimum |
| Spaltengenerierung | 100-500 Kunden, multi-tour | Stunden | Praktisch nahe Optimum |
Formulierungswahl:
- 2-Index-Formulierung: Eine Entscheidungsvariable pro Kante (i, j). Leicht verständlich, aber schwer in großem Maßstab durch Subtour-Eliminations-Bedingungen (SEC).
- 3-Index-Formulierung: Eine Entscheidungsvariable pro (i, j, Fahrzeug k). Flexibler für heterogene Flotte oder Open VRP; Variablenzahl wächst.
Zielfunktions-Optionen:
- Gesamtstrecke minimal: am häufigsten; Kraftstoff + Wartung im Fokus.
- Gesamtzeit minimal: wenn Fahrerkosten den Kraftstoff überwiegen.
- Fahrzeuganzahl plus Gesamtstrecke (hierarchisch): zuerst Fahrzeuge, dann Strecke — für Flottenverkleinerungen.
- Kraftstoff plus Fahrerlohn kombiniert: direkte Betriebskosten als Ziel.
Erweiterungen — praktische CVRP-Verwandte:
- Heterogeneous Fleet VRP: Flotte mit unterschiedlichen Kapazitäten — kombiniert mit “großes Fahrzeug nicht in die Innenstadt”.
- Open VRP: Fahrzeug endet beim letzten Kunden, keine Rückkehr.
- Multi-Depot-VRP: mehrere Depots; jeder Kunde wird dem günstigsten zugeordnet.
- Distance-Constrained VRP: Tourlänge durch Fahrerschicht begrenzt.
- Asymmetric CVRP: A→B ≠ B→A wegen urbaner Einbahnstraßen.
VRPTW (#002), PDPTW (#046), DARP (#047) und TSP (#068) sind nahe Verwandte. CVRP ist das einfachste und älteste Familienmitglied; sein Verständnis ist der erste Schritt zu den anderen.
Akademische Quellen
Im sources-Block dieser Seite gelistet.
Quellen
- Dantzig, G. B. und Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. Gründungsarbeit der VRP-Familie — erste Definition als ‘TSP mit Kapazität’.
- Clarke, G. und Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. Klassischer Savings-Algorithmus — weiterhin praktischer Benchmark.
- Toth, P. und Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2. Auflage). SIAM-MOS. Standardwerk des VRP-Feldes.
- Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. Historischer und methodischer Überblick.
- Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P., Reis, M., Uchoa, E. und Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491-511. Moderner Exact-Algorithmus für CVRP.
- YÖK Tez Merkezi — Stichwort: ‘kapasiteli araç rotalama’ oder ‘CVRP’ — 30+ Arbeiten aus der TR-Akademia. tez.yok.gov.tr
Glossar
- Kapazitierte Tourenplanung
- Entwurf kostenminimaler Touren, die an einem einzigen Depot beginnen und enden, jeden Kunden genau einmal besuchen und deren Gesamtnachfrage pro Tour die Fahrzeugkapazität nicht überschreitet.
- Clarke-Wright Savings
- Klassische Heuristik von 1964 für das Capacitated Vehicle Routing Problem: jeder Kunde startet auf einer eigenen Tour; Paare von Touren werden iterativ nach größter 'Ersparnis' verschmolzen, bis die Kapazität weitere Verschmelzungen verhindert.
- VRP
- Die Entscheidung, welche Fahrzeuge — ausgehend von einem oder mehreren Depots — welche Kunden in welcher Reihenfolge anfahren.
- MIP
- Optimierungsmodell, bei dem ein Teil der Entscheidungsvariablen ganzzahlig sein muss (z. B. Anzahl LKW, Anzahl Schichten).
Ähnliche Probleme
Ein Fahrzeug, viele Stopps — in welcher Reihenfolge fahre ich alle an, damit die Gesamtstrecke minimal ist?
Sie betreiben einen Servicetechniker mit 8-15 Kundenbesuchen pro Tag (Klima, Aufzug, Weißware), einen Einzelfahrzeug-Lieferantenbesuch eines Vertrieblers oder eine PCB-Bohrmaschine, die 500-5.000 Bohrungen in Reihenfolge bringt. Alle stehen vor derselben Kernfrage: gegeben N Punkte, in welcher Reihenfolge fährt das einzige Fahrzeug oder der Kopf jeden Punkt an und kehrt zum Start zurück. Bei falscher Reihenfolge verbrennt das Servicefahrzeug 80-200 TRY/Tag extra an Kraftstoff und Fahrerstunden, die PCB-Linie braucht 15-30% länger pro Bauteil und der letzte Kunde verpasst sein Lieferfenster. Bei 50 Stopps liegt die handgemachte Reihenfolge 20-40% über dem wahren Minimum; mit wachsender Stoppzahl summiert sich die Lücke der Bauchgefühl-Reihenfolge.
Mehrere Werke, mehrere Kunden — Wie viel liefert jedes Werk an jeden Kunden, damit die Gesamtfracht minimal wird?
Für Lebensmittel-, Verpackungs- oder Textil-KMU, die wöchentlich aus 3-8 Werken oder Regionallagern an 20-100 Kunden liefern. Die wöchentliche Entscheidung lautet: welches Werk schickt wie viel an welchen Kunden, bei festen Werkkapazitäten, festgelegten Kundenbedarfen und je Werk-Kunde-Paar unterschiedlichen Stückkosten (Entfernung + Fahrzeugtyp + Vertrag). Ziel ist die niedrigste Gesamtfrachtrechnung über das Netz. Die Faustregel 'nächstgelegenes Werk' oder 'das machen wir schon immer so' kostet gegenüber einer systematischen Zuweisung typischerweise 10-20% zusätzlichen Diesel- und Fahrzeugaufwand.