VRPTW erklärt: Routenoptimierung mit Zeitfenstern

Wenn Sie den Artikel über das TSP gelesen haben, wissen Sie bereits, wie man Lieferungen sortiert, um die Distanz zu minimieren. Aber in der Praxis warten Ihre Kunden nicht zu jeder Zeit. Eine Hochzeit um 14 Uhr, ein Geschäftsessen pünktlich um 12 Uhr, eine Arztpraxis zwischen 12:30 und 14 Uhr geschlossen. Genau dafür ist das VRPTW, das Vehicle Routing Problem with Time Windows, gedacht. Es übernimmt, wo das TSP an seine Grenzen stößt.

Vom TSP zum VRPTW: die natürliche Weiterentwicklung

Das TSP minimiert die Distanz, Punkt. Es nimmt an, dass jede Adresse jederzeit erreichbar ist. Eine nützliche Vereinfachung, um das Problem zu verstehen, aber nicht Ihre tägliche Realität.

Das VRPTW fügt zwei wesentliche Zutaten hinzu:

1. Mehrere mögliche Fahrzeuge (das V in VRP): Sie können 1, 2, 5 Fahrer parallel haben
2. Zeitfenster pro Kunde (das TW in Time Windows): jede Adresse hat ein [Öffnung, Schließung]-Intervall

Plötzlich wird aus einem rein geometrischen Problem ein zeitliches Problem. Die optimale Reihenfolge ist nicht mehr nur „die kürzeste“, sondern „die kürzeste, die jedes Zeitfenster respektiert“.

Ein konkretes Beispiel

Stellen wir uns einen typischen Catering-Tag vor: 6 Lieferungen, Abfahrt vom Lager um 10:00 Uhr.

Das TSP würde Ihnen vielleicht sagen: „Fahren Sie A, B, C, D, E, F in dieser Reihenfolge, das ist am kürzesten“. Aber wenn Sie um 12:05 Uhr bei A ankommen, obwohl Sie zwischen 11:45 und 12:00 Uhr da sein sollten, sind Sie zu spät. Der Kunde ist unzufrieden. Sie verlieren den Auftrag.

Das VRPTW findet eine Reihenfolge, die:

1. Jede Adresse innerhalb ihres Zeitfensters besucht
2. Die Gesamtdistanz und die Gesamtzeit unter allen machbaren Reihenfolgen minimiert
3. Sie im Voraus warnt, wenn manche Fenster nicht erreichbar sind (in dem Fall braucht es ein zusätzliches Fahrzeug oder einen früheren Start)

Das EDF-Ergebnis in diesem Beispiel

OptiRoad sortiert die Stopps nach aufsteigender Schließzeit und simuliert dann den Tag ab der Abfahrt um 10:00 Uhr. Die resultierende Reihenfolge lautet: B (Kreuzberg), dann E (Steglitz), A (Mitte), C (Charlottenburg), D (Prenzlauer Berg) und schließlich F (Friedrichshain). Hier ist der detaillierte Plan, den Sie auf dem Bildschirm erhalten:

Bei B kommen Sie sehr früh an (10:18): das Fahrzeug wartet bis zur Öffnung um 11:00 Uhr und liefert dann. Jedes Zeitfenster wird vom ersten bis zum letzten Stopp eingehalten. Eine reine TSP-Reihenfolge nach „kürzester Distanz“ würde dieses Ergebnis nie garantieren: sie könnte Sie zum falschen Zeitpunkt zu A oder F schicken und mehrere Fenster sprengen.

Warum es schwerer ist als das TSP

Das TSP ist bereits NP-schwer (siehe TSP-Artikel). Das VRPTW noch mehr, denn man muss den zeitlichen Ablauf der Tour simulieren, um jede Kandidatenlösung zu validieren:

• An jedem Stopp wird die voraussichtliche Ankunftszeit berechnet
• Wenn Sie vor der Öffnung ankommen, warten Sie (verlorene Zeit)
• Wenn Sie nach der Schließung ankommen, ist die Lösung ungültig (verworfen)
• Die Servicezeit kommt zur Abfahrtszeit zum nächsten Stopp hinzu

Der Solver kann nicht einfach die rohe Distanz optimieren. Er muss den detaillierten Tagesplan für jede getestete Reihenfolge aufbauen.

Hartes oder weiches Zeitfenster?

In der Theorie gibt es zwei Familien von Zeitfenstern. Ein hartes Fenster muss eingehalten werden: eine Lösung, die es verfehlt, wird schlicht verworfen, wie ein Arzttermin oder eine Zeremonie, die sich einfach nicht verschieben. Ein weiches Fenster toleriert eine Verspätung, aber um den Preis einer Strafe, die der Solver zu minimieren versucht.

OptiRoad behandelt Zeitfenster als hart, um zu beurteilen, ob eine Tour machbar ist. Der Unterschied: statt ein Fenster still zu brechen, um ein paar Kilometer zu sparen, markiert OptiRoad den Stopp als verspätet, noch bevor Sie losfahren. Sie entscheiden: den Kunden warnen, ein Fahrzeug hinzufügen oder die Startzeit verschieben. Hinweis: das auf ein Fenster gesetzte strict-Flag ist eine semantische Angabe, die im Plan angezeigt wird (eine fortgeschrittenere Behandlung folgt später).

Die Ansätze zur Lösung des VRPTW

1. Earliest Deadline First (EDF)

Bei jedem Schritt wählt man den Kunden, dessen Fenster am frühesten schließt, unter den noch erreichbaren. Einfach, schnell, liefert in der Praxis ausgezeichnete Ergebnisse. Das ist der Ansatz, den OptiRoad nutzt.

2. Insertion Heuristics

Man startet von einer leeren Tour und fügt Kunden einzeln ein, an der Position, die die Gesamtkosten unter Beachtung der Fenster minimiert. Gute Qualität, längere Berechnung.

3. Metaheuristiken (Simulated Annealing, Tabu, genetisch)

Für sehr große Instanzen (hunderte Stopps, komplexes Multi-Fahrzeug). Liefern nahezu optimale Lösungen, brauchen aber Rechenzeit.

4. Constraint Programming

Sehr leistungsfähiger akademischer Ansatz, aber aufwändig zu implementieren, für Spezialfälle.

Die Servicezeit verändert alles

Man vergisst es leicht, aber die an jedem Stopp verbrachte Zeit (die Servicezeit) verschiebt jede spätere Ankunft nach hinten. Fünf Minuten für die Übergabe eines Pakets, multipliziert mit fünfzehn Lieferungen, sind mehr als eine Stunde, die sich über den ganzen Tag verschiebt. Diese Zeit zu ignorieren, ergibt einen Plan, der auf dem Papier machbar aussieht, in der Realität aber zu spät läuft.

Deshalb löst OptiRoad die Servicezeit Stopp für Stopp auf, nach einer klaren Priorität: der manuell am Stopp gesetzte Wert gewinnt, sonst der des passenden Kontakts in Ihrem Adressbuch (über Koordinaten abgeglichen), sonst der Standardwert Ihres Kontos (5 Minuten). So enthält jede angezeigte Ankunftszeit bereits die tatsächlich vor Ort verbrachte Zeit, und der Plan spiegelt Ihren Alltag wider.

Wie OptiRoad das VRPTW umsetzt

Wenn Sie „Zeitfenster“ im Dashboard aktivieren (Pro- oder Business-Plan), tut OptiRoad Folgendes:

1. Sortiert die Kunden nach aufsteigender Schließzeit (mit Sonderpriorität für mit priority: high markierte Stopps)
2. Baut die Tour per EDF-Insertion auf: bei jedem Schritt wird der nächste Kunde gewählt, der das aktuelle Fenster respektiert und den Umweg minimiert
3. Plan-Simulation: ausgehend von der Abfahrtszeit wird für jeden Stopp berechnet:
   • voraussichtliche Ankunftszeit (unter Berücksichtigung der Distanz)
   • Service-Beginnzeit (= max(Ankunft, Öffnung))
   • Abfahrtszeit (= Beginn + Servicezeit)
4. Verspätungserkennung: wenn die voraussichtliche Ankunft die Schließung überschreitet, wird der Stopp late: true in der Antwort markiert, Sie sind vor der Abfahrt gewarnt
5. Kein 2-opt bei aktivem VRPTW: die EDF-Reihenfolge hat Vorrang vor Distanzoptimierung, um die zeitlichen Bedingungen nicht zu brechen

Das Ergebnis in der App: eine klare Übersichtstabelle mit voraussichtlicher Ankunftszeit pro Kunde, Verspätungen in Rot, und der tatsächlichen Tagesgesamtdauer (inkl. Wartezeiten).

Wann VRPTW vs. einfaches TSP

• TSP: klassische Liefertour ohne starke Zeitbedingungen (E-Commerce, Post usw.). Sie kommen, wann Sie kommen.
• VRPTW: sobald mindestens einige Kunden ein vorgegebenes Zeitfenster haben. Catering, Floristen (Zeremonien), häusliche Pflege (medizinische Slots), terminierte Technikereinsätze.

OptiRoad wechselt automatisch zu VRPTW, sobald Sie mindestens ein Zeitfenster in Ihrer Tour setzen.

Und das Multi-Fahrzeug?

VRPTW kann mit Multi-Fahrzeug kombiniert werden: mehrere Fahrer parallel, jeder mit seiner eigenen optimierten Tour. OptiRoad verwaltet diesen Fall im Business-Plan mit dem Clarke-Wright-Savings-Algorithmus zur Stoppverteilung, dann EDF und Simulation pro Fahrzeug. Das wird Thema eines zukünftigen Artikels.

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

Auf einer typischen Tour mit Zeitfenstern (Catering-Lieferungen, zum Beispiel):

• Ohne VRPTW: 30 bis 50 % der Lieferungen drohen außerhalb des Fensters zu sein, Sie rufen Kunden zur Verschiebung an, Sie sind gestresst.
• Mit VRPTW: 100 % der Lieferungen innerhalb der Fenster oder Vorab-Alarm. Der Tag verläuft wie geplant.

Und wenn Sie im Voraus wissen, dass eine Lieferung verspätet sein wird, können Sie handeln: Kunden anrufen, ein Fahrzeug hinzufügen, früher starten. Allein vorab Bescheid zu wissen ist oft mehr wert als die Kilometerersparnis.

Weiterführend

VRPTW ist im Pro- und Business-Plan verfügbar. Der Free-Plan enthält das einfache TSP (ohne Zeitfenster), genug zur Qualitätsvalidierung auf kleinen Touren. Um Zeitfenster zu aktivieren, wechseln Sie zu Pro und aktivieren den Toggle „Zeitfenster“ im OptimizePanel.

Wollen Sie tiefer ins Multi-Fahrzeug (VRP mit Clarke-Wright Savings)? Das ist der nächste Artikel.

Häufige Fragen

Was passiert, wenn ein Fenster nicht eingehalten werden kann?

Der betroffene Stopp wird vor der Abfahrt als verspätet markiert, niemals erst unterwegs entdeckt. Sie behalten die Kontrolle: den Kunden warnen, ein Fahrzeug hinzufügen, um die Last zu verteilen, oder die Startzeit verschieben, damit das Fenster wieder erreichbar wird.

Kann ich Stopps mit und ohne Fenster mischen?

Ja. Stopps ohne Fenster sind an keine bestimmte Uhrzeit gebunden: OptiRoad platziert sie frei um die eingeschränkten Stopps herum, dort, wo sie am besten passen, ohne die vorgegebenen Fenster zu stören. Sie müssen also nicht für jede Lieferung ein Fenster setzen.

Verarbeitet das VRPTW mehrere Fahrzeuge?

Ja, im Business-Plan. OptiRoad verteilt die Stopps zuerst mit dem Clarke-Wright-Savings-Algorithmus auf die Fahrzeuge und wendet dann EDF und Plan-Simulation auf jede Tour einzeln an. Jeder Fahrer erhält so seine eigene optimierte, fensterkonforme Route.

Welcher Plan enthält Zeitfenster?

Zeitfenster sind im Pro- und Business-Plan verfügbar. Der Free-Plan beschränkt sich auf das einfache TSP, ohne Zeitbedingung: perfekt, um die Qualität der Optimierung auf kleinen Touren zu testen, aber nicht für Branchen mit vorgegebenen Slots geeignet.