Multi-Fahrzeug-VRP: Clarke-Wright Savings erklärt

Sie haben über das TSP (Stopps sortieren) und über das VRPTW (Zeitfenster respektieren) gelesen. Ein sehr häufiger Praxisfall bleibt: Sie haben mehrere Fahrzeuge. 2 Fahrer am Morgen, 5 Pflegekräfte im Feld, 3 Catering-Anbieter, die gleichzeitig losfahren. Wie verteilt man Kunden auf sie, um die Gesamtzeit zu minimieren?

Das ist das VRP (Vehicle Routing Problem) und die in der Praxis meistgenutzte Methode stammt aus 1964: der Clarke-Wright-Algorithmus, auch Savings algorithm genannt. Genau das nutzt OptiRoad im Business-Plan für 2 bis 10 Fahrzeuge.

Das Problem in einem Satz

Sie haben 1 Lager und N Kunden zu beliefern. Sie haben M Fahrzeuge verfügbar. Wie verteilen Sie die N Kunden auf die M Fahrzeuge, um die Gesamtzeit zu minimieren?

Klingt einfach. Ist es nicht.

Warum es schwer ist

Bei 20 Kunden und 3 Fahrzeugen übersteigt die Anzahl möglicher Partitionen 3,5 Millionen. Und für jede Partition muss noch ein TSP (oder VRPTW bei Zeitfenstern) auf jedem Fahrzeug gelöst werden. Brute Force ist jenseits von 10 bis 15 Kunden unmöglich.

Das VRP ist, wie das TSP, NP-schwer: kein Algorithmus garantiert die optimale Lösung in vernünftiger Zeit. Also nutzen wir Heuristiken. Diejenige, die seit 60 Jahren in der Praxis dominiert, ist Clarke-Wright Savings.

Die geniale Idee von Clarke-Wright (1964)

George Clarke und John Wright veröffentlichten ihr Paper "Scheduling of vehicles from a central depot to a number of delivery points" 1964. Die Idee ist von verblüffender Eleganz.

Schritt 1: die naive Lösung

Man startet mit einer entarteten Lösung: jeder Kunde hat sein eigenes Fahrzeug. 20 Kunden = 20 Mini-Touren Lager → Kunde → Lager. Verschwenderisch, aber unser Ausgangspunkt.

Gesamtkosten: für jeden Kunden i fährt das Fahrzeug d(Lager, i) + d(i, Lager) = 2 × d(Lager, i).

Schritt 2: das Konzept des "Saving"

Stellen wir uns vor, wir verschmelzen die Touren zweier Kunden i und j zu einer einzigen. Statt:

Lager → i → Lager   +   Lager → j → Lager

Machen wir:

Lager → i → j → Lager

Die Ersparnis (das Saving) ist:

s(i,j) = d(Lager, i) + d(j, Lager) - d(i, j)

Je näher i und j zueinander und je weiter vom Lager entfernt sind, desto größer das Saving. Intuitiv: es lohnt sich, sie zusammenzufassen.

Schritt 3: die gierige Verschmelzung

1. Berechne s(i,j) für alle Paare von Kunden
2. Sortiere diese Savings absteigend
3. Für jedes Paar (i,j) der Reihe nach:
   • Wenn i und j auf unterschiedlichen Touren sind
   • Und sie an den Enden ihrer jeweiligen Touren sitzen
   • Und noch Fahrzeuge verfügbar sind (≤ M)
   • Verschmelze die beiden Touren
4. Weiter, bis keine nützlichen Paare mehr übrig sind

Am Ende erhalten Sie M Touren (oder weniger), die alle Kunden abdecken, mit einer Gesamtdistanz deutlich besser als die naive Lösung, typischerweise innerhalb von 5 bis 10 % des theoretischen Optimums.

Savings, Sweep oder Metaheuristik?

Clarke-Wright ist nicht die einzige Algorithmenfamilie für das VRP. Drei große Ansätze existieren nebeneinander.

Der Sweep-Algorithmus (Gillett und Miller, 1974) gruppiert die Kunden nach ihrem Winkel um das Lager, wie ein Uhrzeiger, der die Ebene abfährt. Er ist extrem einfach zu programmieren, aber die Tourenqualität bleibt geringer: man folgt der Geometrie, nicht den realen Kosten.

Metaheuristiken (Tabu-Suche, genetische Algorithmen) durchsuchen den Lösungsraum gründlicher und erreichen leicht bessere Ergebnisse. Der Preis dafür: sie sind langsamer und schwieriger einzustellen. Man muss viele Parameter kalibrieren, was sie aufwendig im Produktivbetrieb macht.

Clarke-Wright Savings liegt am idealen Punkt: Ergebnisse nahe am Optimum, schnelle Ausführung, eine grundsolide Robustheit und eine einfache Erweiterbarkeit mit Kapazitäten oder Zeitfenstern. Genau deshalb dominiert er die Flottenoptimierung unter realen Bedingungen seit 60 Jahren.

Ein konkretes Beispiel

Stellen wir uns 6 Kunden vor, die von einem Lager in Berlin-Mitte beliefert werden müssen, mit 2 verfügbaren Fahrzeugen:

Naive Lösung (1 Fahrzeug pro Kunde, 6 Fahrzeuge):

• Gesamtkosten: 2 × (4 + 5 + 8 + 6 + 9 + 7) = 78 km

Mit Clarke-Wright Savings und 2 Fahrzeugen:

1. Berechnung der Savings für die 15 möglichen Paare
2. Absteigend sortiert
3. Sukzessive Verschmelzungen unter Einhaltung der 2-Fahrzeug-Grenze
4. Mögliches Ergebnis: Fahrzeug 1 = Lager → A → B → D → Lager (~22 km), Fahrzeug 2 = Lager → C → F → E → Lager (~28 km)

• Gesamtkosten: ~50 km (-36 % gegenüber naiv)

In realen Fällen sind Einsparungen von 30 bis 40 % gegenüber einer manuellen "Augenmaß"-Partition üblich.

Varianten und Erweiterungen

Der ursprüngliche Algorithmus ist für das Basis-VRP. In der Praxis bereichern wir ihn:

• Kapazitäten: jedes Fahrzeug hat eine maximale Last. Bei jeder Verschmelzung wird geprüft, dass die Kapazität nicht überschritten wird.
• Multi-Lager: mehrere Lager. Heuristik: jedem Kunden das nächste Lager zuweisen, dann Clarke-Wright auf jedem Sub-Problem.
• Zeitfenster: Kombination mit VRPTW. Zwei Touren nur verschmelzen, wenn die resultierende Reihenfolge alle Fenster einhält.
• Obergrenze der Fahrzeugzahl: wenn man genau M Fahrzeuge will, hört man früher mit dem Verschmelzen auf.
• Asymmetrie: Distanz A→B kann von B→A abweichen (Einbahnstraßen usw.). Die Saving-Berechnung bleibt gültig.

Wie OptiRoad Multi-Fahrzeug-VRP umsetzt

Im Business-Plan können Sie bis zu 10 Fahrzeuge parallel optimieren. Folgendes tut OptiRoad, wenn Sie den Multi-Fahrzeug-Modus aktivieren:

1. Konfiguration: Sie geben die Fahrzeugzahl an, ihr Lager (geteilt oder pro Fahrzeug), und optional ihren Ankunftspunkt.
2. Clarke-Wright Savings: Berechnung der Savings über alle Paare, absteigende Sortierung, gierige Verschmelzungen unter Einhaltung der Fahrzeuggrenze.
3. Multi-Lager: wenn jedes Fahrzeug ein anderes Lager hat (sharedDepot: false), Vorzuweisung der Stopps nach Nähe vor der Ausführung von Clarke-Wright auf jedem Cluster.
4. Lokales TSP pro Fahrzeug: sobald die Partition gefunden ist, wird jede Tour einzeln mit Nearest Neighbor + 2-opt neu optimiert, um die interne Distanz zu minimieren.
5. Wenn VRPTW aktiv: EDF (Earliest Deadline First) auf jeder Tour unter Einhaltung der Zeitfenster jedes Kunden.
6. Unterscheidbare Farben: jedes Fahrzeug erhält eine Farbe auf der Karte (#3B82F6, #EF4444, #10B981 usw.) zur einfachen Tour-Visualisierung.

Adaptive Timeouts: 15 Sekunden für 2 bis 4 Fahrzeuge, 30 Sekunden für 5 bis 10 Fahrzeuge. Wenn überschritten, gibt OptiRoad das beste gefundene Ergebnis mit einem partial: true-Flag zurück.

Drag and Drop für manuelle Anpassung

Wenn die automatische Verteilung nicht passt (ein Kunde muss aus Beziehungsgründen unbedingt zu einem bestimmten Fahrer), können Sie einen Stopp per Drag and Drop in der App von einem Fahrzeug zum anderen ziehen. OptiRoad berechnet dann die TSP-Reihenfolge für jedes betroffene Fahrzeug unter Einhaltung der neuen Partition neu. Endpunkt: POST /api/optimize/reorder (nur Business-Plan).

Die Touren ausbalancieren

In seiner reinen Form verfolgt Clarke-Wright nur ein Ziel: die Gesamtdistanz zu minimieren. Folglich kann er unausgewogene Touren erzeugen, ein Fahrer mit 25 Stopps beladen, während ein anderer nur 8 hat. Auf dem Papier ist die Distanz optimal, im realen Alltag ist das für die Planung untragbar.

In der Praxis begrenzt man daher die Zahl der Stopps oder die Kapazität pro Fahrzeug, um eine gleichmäßigere Verteilung zu erzwingen. Anschließend balanciert man von Hand nach, wenn das Feld es verlangt. OptiRoad lässt Sie die Fahrzeugzahl festlegen und Stopps per Drag and Drop von einem zum anderen verschieben: jede betroffene Tour wird sofort neu berechnet, sodass Sie eine optimierte Reihenfolge behalten und gleichzeitig die Last jedes Fahrers im Griff haben.

Wann Multi-Fahrzeug nutzen

• 2 bis 3 Fahrzeuge: nützlich, sobald Ihr Tag 30 Stopps überschreitet oder Sie in unterschiedlichen geografischen Zonen liefern.
• 5 bis 10 Fahrzeuge: für strukturierte Flotten (häusliche Pflege, Catering mit Team, skalierende E-Commerce).
• Mehr als 10 Fahrzeuge: kontaktieren Sie uns, wir können einen dedizierten Solver für sehr große Flotten aktivieren.

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

An einem typischen Tag mit 60 Lieferungen, die auf 3 Fahrer verteilt werden:

• Ohne Optimierung (grobe manuelle Aufteilung): ~280 km, 12 kumulierte Stunden
• Mit OptiRoads Clarke-Wright Savings: ~190 km, 8 kumulierte Stunden
• Gewinn: -32 % Strecke, -33 % kumulierte Zeit

Über die Kilometer hinaus ist der eigentliche Gewinn organisatorisch: jeder Fahrer startet mit seiner sauberen Routenliste, seiner Farbe auf der Karte, präzisen ETAs. Schluss mit "wer übernimmt wen?" am Morgen.

Weiterführend

Multi-Fahrzeug-VRP ist exklusiv im Business-Plan verfügbar (49 €/Monat). Der Pro-Plan bleibt mono-Fahrzeug (mit oder ohne Zeitfenster).

Diese 3-teilige Serie (TSP → VRPTW → Multi-Fahrzeug-VRP) deckt die konzeptionellen Grundlagen von OptiRoad ab. Künftige Artikel werden sich mit praktischen Themen befassen: tatsächliche Einsparungen, API-Integration in Ihren E-Commerce-Shop, usw.

Häufige Fragen

Wie viele Fahrzeuge verarbeitet OptiRoad? Von 2 bis 10 Fahrzeuge im Business-Plan. Darüber hinaus kontaktieren Sie uns: wir können einen dedizierten Solver für sehr große Flotten aktivieren.

Kann jedes Fahrzeug ein anderes Lager haben? Ja, der Multi-Lager-Modus ist genau dafür gemacht. Die Stopps werden dem nächstgelegenen Lager vorab zugewiesen, bevor Clarke-Wright auf jedem Cluster läuft, was konsistente Touren pro Zone garantiert.

Kann ich einen Kunden an ein bestimmtes Fahrzeug binden? Ja, per Drag and Drop. Sie verschieben den Stopp auf das gewünschte Fahrzeug und OptiRoad berechnet sofort die TSP-Reihenfolge der betroffenen Fahrzeuge neu, um jede Tour optimiert zu halten.

Welcher Plan ist erforderlich? Nur der Business-Plan. Der Pro-Plan bleibt mono-Fahrzeug, mit oder ohne Zeitfenster.