Bei der dynamischen Tourenoptimierung sind die schwierigsten Einfügungen nicht unbedingt die teuersten.

Einige Aufträge fallen sofort als ungültig durch das Raster:

• Inkompatible Qualifikationen des Fahrers
• Überschreitung der Fahrzeugkapazität
• Verletzung von Kundenzeitfenstern
• Verstoß gegen gesetzliche Vorgaben (z. B. Lenkzeiten)

Diese harten Ausschlusskriterien lassen sich durch Algorithmen leicht herausfiltern.

Die echte Komplexität liegt in den Grauzonen: Eine neue Aufgabe wirkt geografisch oft perfekt – sie erfordert kaum Umwege, liegt nah an bestehenden Stopps und fügt sich natürlich in die Route ein. Dennoch kann sie unter Berücksichtigung aller Nebenbedingungen die Gesamtqualität der Planung massiv verschlechtern.

Genau diese trügerischen Grenzfälle in Sekundenschnelle zu erkennen und zu lösen, ist die Kernaufgabe einer modernen Echtzeit-Optimierungs-Engine auf der letzten Meile.

Wie Ammar Oulamara, Leiter der Forschungs- und Entwicklungsabteilung bei AntsRoute, erklärt:

„Eine lokal optimale Einbindung kann zu einer erheblichen Verschlechterung der gesamten Tagesplanung führen, wenn alle zeitlichen und betrieblichen Einschränkungen berücksichtigt werden.“

Genaue diese Unterscheidung zwischen lokaler Optimierung und globaler Stabilität steht heute im Mittelpunkt, wenn es um moderne und dynamische Planungsprozesse geht.

Für einen umfassenden Überblick über die Mechanismen der Tourenoptimierung in der Last-Mile-Logistik empfehlen wir Ihnen unseren vollständigen Artikel zur Routenoptimierung.

In diesem Artikel geht es um Folgendes:

• Warum dynamische Einfügungen auf den zweiten Blick enorme Komplexität offenbaren
• Wo die Grenzen der Grenzkostenrechnung bei der Bewertung von Touren liegen
• Wie engmaschige Zeitfenster komplexe Abhängigkeiten erzeugen
• Warum scheinbar machbare Touren sehr anfällig werden
• Welche konkreten Auswirkungen geschäftliche Vorgaben auf die Einplanung haben
• Wie die Engine den Plan lokal blitzschnell neu organisiert
• Warum nicht jede Einfügung den gleichen Prüfaufwand verdient

Eine dynamische Einfügung ist viel komplexer, als es auf den ersten Blick erscheint

In einer mehrtägigen Tourenplanung gibt es für eine neue Aufgabe τ (Task) selten nur einen einzigen möglichen Einfügepunkt.

Daraus ergibt sich für die Engine ein Entscheidungsraum der folgenden Form:
(Tag d) × (Route rᵢ ∈ R_d) × (Position p in rᵢ)

Mit anderen Worten prüft sie:

• welche Tage geeignet sind,
• welche Touren an diesen Tagen infrage kommen und
• welche konkreten Positionen innerhalb dieser Touren möglich sind.

Denn jeder neue Stopp wirbelt den bestehenden Plan durcheinander. Er verändert die Kosten pro Kilometer, verzögert Folgefahrpläne, erhöht die Wartezeiten, frisst die Zeitpuffer auf und gefährdet geschäftliche Vorgabe. Sogar zukünftige Umplanungsvarianten werden dadurch blockiert. Die Aufgabe mutiert schnell zu einem kombinatorischen Problem.

Für reale Systeme bedeutet dies: es reicht nicht aus, bloß eine freie Lücke im Plan zu finden. Die Gesamtqualität jeder einzelnen Einfügeoption muss exakt evaluiert werden.

Warum die Grenzkostenrechnung nicht ausreicht

Die meisten Ansätze zur Einfügung starten naturgemäß mit der Berechnung der Grenzkosten, die durch den neuen Stopp in der Tour entstehen:
Δc = c(vₚ₋₁, τ) + c(τ, vₚ) − c(vₚ₋₁, vₚ)

Diese Messgröße ist von entscheidender Bedeutung. Dabei werden die geografischen Mehrkosten bewertet, die durch das Hinzufügen einer neuen Aufgabe τ zwischen zwei aufeinanderfolgenden Punkten einer Tour verursacht werden.
Bei Touren mit zahlreichen Restriktionen stößt dieses Kriterium jedoch schnell an seine Grenzen.

Betrachten wir einen einfachen Fall, bei dem zwei Einfügungen genau die gleichen Grenzkosten verursachen:

• gleiche Zunahme der Kilometerzahl,
• gleiche zusätzliche Fahrzeit.

Während beim ersten zusätzlichen Stopp noch beträchtliche zeitliche Spielräume im weiteren Verlauf der Tour erhalten bleiben, konzentrieren sich durch die zweite Option mehrere kritische Einsätze auf einen ohnehin schon stark ausgelasteten Zeitblock zwischen 14 und 16 Uhr.

Geografisch gesehen scheinen die beiden Einfügungen gleichwertig zu sein. Zeitlich gesehen sind sie es jedoch keineswegs.
Die zweite Option macht die Tour wesentlich anfälliger. Das Problem:

• Staus,
• Verzögerungen,
• Überschreitungen der Einsatzzeiten und
• Notfälle in letzter Minute

… sind hier quasi vorprogrammiert.

Mit anderen Worten:
Die lokalen Kosten spiegeln selten die tatsächliche Stabilität der Gesamtlösung wider.

Engmaschige Zeitfenster erzeugen starke Abhängigkeiten

In einem VRPTW-Kontext (Vehicle Routing Problem with Time Windows – zu Deutsch: Tourenplanungsproblem mit Zeitfenstern) sorgt eine Kette zeitlicher Abhängigkeiten dafür, dass jeder Auftrag untrennbar mit den vorhergehenden Stopps verknüpft ist.
Die exakte Ankunftszeit an einen Auftragsort wird implizit durch mehrere Faktoren beeinflusst:

• die vorangegangenen Fahrzeiten,
• die jeweiligen Servicezeiten,
• eventuellen Wartezeiten und
• alle zuvor auf der Tour aufgelaufenen Verspätungen.

Bei jeder neuen Einfügung muss also die gesamte zeitliche Struktur neu berechnet werden.
Der sogenannte Domino-Effekt macht dynamische Einfügungen besonders fehleranfällig.
Eine Verschiebung von nur wenigen Minuten mitten in einer Tour kann bereits ausreichen, um:

• Sicherheitspuffer komplett aufzuheben,
• vorgeschriebene Pausen unzulässig zu verschieben,
• zusätzliche Wartezeiten zu generieren oder
• weitere Zeitüberschreitungen im Tagesverlauf nach sich zu ziehen.

Bei AntsRoute werden vor allem unnötige Wartezeiten von unserer Engine für die Tourenplanung ins Visier genommen:
min Σᵢ max(0, eᵢ − tᵢ)

Dabei stehen:

• eᵢ für den Beginn des Zeitfensters beim Kunden i und
• tᵢ für die erwartete Ankunftszeit (ETA).

In vereinfachten Ansätzen werden diese Wartezeiten oft unterschätzt. Das hat fatale Folgen für das gesamte System: Es sinken die Produktivität, die Tourendichte und nicht zuletzt die Flexibilität für zukünftige Umstrukturierungen.

Eine vermeintlich machbare Tournee kann sich schnell als äußerst anfällig erweisen

In vielen Systemen wird die Machbarkeit als rein binäre Bedingung behandelt: Eine Einfügung ist entweder gültig oder sie ist es nicht.

Im realen Betrieb ist die Situation jedoch viel differenzierter. Manche Einfügungen bleiben technisch machbar, führen aber zu einer extrem instabilen Tour.

Ein konkretes Beispiel: Eine Tour kann zwar alle Zeitfenster exakt einhalten, lässt dabei aber fast keinerlei zeitlichen Spielraum mehr – Sie bleibt zwar technisch machbar, ist in der Realität jedoch nicht mehr in der Lage, auch nur die geringste Verzögerung aufzufangen.

Ammar Oulamara betont:

„Das Problem besteht nicht nur darin, die sofortige Durchführbarkeit einer Einfügung zu gewährleisten. Dabei muss auch die betriebliche Robustheit der Planung bewahrt werden.“

Dieser Begriff der Robustheit spielt in dynamischen Systemen eine zentrale Rolle.
Eine Lösung, die in Bezug auf die Kilometerleistung etwas weniger optimiert ist, kann letztendlich die bessere Alternative sein, wenn sie mehr operative Flexibilität beibehält.

Geschäftliche Restriktionen verstärken diese negativen Nebeneffekte zusätzlich

Die Schwierigkeiten nehmen stark zu, wenn die Engine komplexe betriebliche Vorgaben integrieren muss:

• Spezifische Qualifikationen
• Berechtigungen und Zertifikate
• spezielle Ausrüstung
• Arbeits-und Lenkzeiten
• Fahrzeugkapazitäten
• Einschränkungen bei Abholung und Zustellung
• Einsatzregeln

Bestimmte Ressourcen werden dadurch kritisch. Eine Fehlzuweisung kann beispielsweise dazu führen, dass ein Mitarbeiter mit einer seltenen Kompetenz vorzeitig gebunden wird. Dies verhindert zukünftige, dringendere Optimierungen und blockiert wertvolle Spielräume für eine dynamische Tourenumplanung.

Bei kombinierten Abhol- und Lieferprozessen (Pickup & Delivery) muss das System zudem logische Abhängigkeiten garantieren:
t(dτ) − t(pτ) ≤ Δtₘₐₓ

Mit anderen Worten:
Die maximale Zeitspanne zwischen einer Abholung und einer Zustellung muss mit den betrieblichen Restriktionen des Systems vereinbar bleiben.
Diese zusätzlichen Abhängigkeiten erhöhen die Komplexität dynamischer Einfügungen erheblich.

Wann eine lokale Tourenanpassung durch die Engine notwendig wird

Angesichts dieser vielfältigen Wechselwirkungen reicht eine einfache Logik der direkten Einfügung nicht mehr aus.

Nach jeder potenziellen Einfügung ist oft eine Phase der lokalen Umplanung erforderlich, um ein stabiles Gleichgewicht im Zeitplan wiederherzustellen.

Unsere Engine bei AntsRoute nutzt gleich mehrere lokale Suchoperatoren:

• relocate
• Or-opt
• 2-opt
• cross-exchange

Das Ziel besteht nicht nur darin, die Einbindung zu ermöglichen, sondern auch darum:

• Domino-Effekte zu verringern,
• Zeitpuffer wiederherzustellen,
• das Gleichgewicht der Touren zu verbessern und
• die globale Stabilität des Systems zu gewährleisten.

Wie Ammar Oulamara erklärt:

„Eine Einfügung darf niemals isoliert betrachtet werden. Man muss auch das lokale Verbesserungspotenzial messen, das dadurch ermöglicht wird.“

Diese Logik ist für moderne Optimierungsalgorithmen von grundlegender Bedeutung.

Nicht jede Einfügung rechtfertigt den gleichen Prüfaufwand

Eine der größten Herausforderungen einer Echtzeit-Engine sind die anfallenden Rechenkapazitäten.
Eine umfassende Untersuchung aller mathematisch möglichen Umstellungen wäre mit den betrieblichen Anforderungen der „letzten Meile“ unvereinbar.

Aus diesem Grund nutzt unsere Engine eine strukturierte Nachbarschaftshierarchie.
Offensichtlich ungünstige Einfügungen werden durch oberflächliche Prüfungen frühzeitig eliminiert.
Vielversprechendere Einfügungen werden anschließend einer tiefergehenden Analyse unterzogen:

• Tourenübergreifender Tausch
• Mehrtägige Umstrukturierungen
• Erweiterte lokale Reoptimierung.

Diese hierarchische Struktur ermöglicht es, die Rechenleistung intelligent auf die Szenarien zu konzentrieren, die das größte Optimierungspotential bieten.

Fazit

In dynamischen Tourenplanungssystemen kann eine geografisch optimale Einfügung sehr negative Auswirkungen auf die Gesamteffizienz der Planung haben.

Eine Tour ist mehr als nur eine bloße Abfolge von Stopps. Es ist ein komplexes Gefüge aus harten Restriktionen, in dem sich Zeitpuffer, betriebliche Abhängigkeiten, Umstrukturierungsmöglichkeiten und die operative Robustheit ständig verändern.

Bei der Optimierung dynamischer Einfügungen geht es also nicht nur darum, einen Umweg in Kilometern zu minimieren.
Das Ziel ist vor allem, das Gesamtgleichgewicht des Systems nach jeder Änderung des Fahrplans aufrechtzuerhalten.