Bei der Tourenoptimierung ist die Erarbeitung einer ersten Lösung selten die größte Herausforderung. Die eigentliche Schwierigkeit entsteht, wenn sich der Plan aufgrund betrieblicher Ereignisse ändern muss, wie zum Beispiel durch das Hinzufügen einer neuen Aufgabe, eine Verspätung, eine Stornierung, eine Änderung der Kundenanforderung, die Umverteilung eines Fahrzeugs oder die lokale Auslastung einer Tour.

In diesem Zusammenhang arbeitet die Engine nicht an einer neuen Anfangskonfiguration. Ihre Aufgabe ist es, eine bereits etablierte und teiloptimierte Planung unter Berücksichtigung bestehender Einschränkungen so anzupassen, dass die Gesamtqualität bestmöglich erhalten bleibt. Genau diese Fähigkeit, einen bestehenden Plan effizient weiterzuentwickeln, unterscheidet dynamische Optimierungsprobleme von klassischen theoretischen Ansätzen.

Dieser Artikel konzentriert sich bewusst auf die Reoptimierungsmechanismen dynamischer Tourenplanungs-Engines: Warm-Start, lokale Suche, Nachbarschaftsverfahren und Erkundungsheuristiken. Für einen umfassenderen Überblick über die logistischen Herausforderungen der „letzten Meile“ empfehlen wir unseren vollständigen Artikel zur Tourenoptimierung.

Im operativen Betrieb kann eine leistungsfähige Engine nicht jedes Mal von Grund auf neu anfangen, sobald eine Änderung auftritt. Die Algorithmen müssen in der Lage sein, einen dynamischen Plan lokal neu zu optimieren, ohne bestehende Touren unnötig zu destabilisieren.

Bei AntsRoute steht diese Herausforderung im Mittelpunkt der Architektur der Optimierungs-Engine.

In diesem Artikel geht es um Folgendes:

• Warum ein kompletter Neustart in Echtzeit nicht praktikabel ist
• Die Rolle des Warm-Starts bei dynamischen Touren
• Warum eine Einfügung global bewertet werden muss
• Wie die Local Search funktioniert
• Warum nicht alle Nachbarschaften den selben Erkundungsaufwand rechtfertigen
• First-Improvement vs. Best-Improvement: zwei Optimierungsstrategien
• Warum exakte Methoden schnell an ihre Grenzen stoßen

Warum ein kompletter Neustart selten eine gute Strategie ist

Theoretisch könnte es so aussehen, als wäre es der beste Ansatz, den Plan nach jeder Änderung komplett neu zu erstellen. In der Praxis erweist sich diese Strategie jedoch schnell als undurchführbar, da die Anzahl der zu untersuchenden Optionen explosionsartig ansteigt, der Rechenaufwand enorm ist und alles in allem zu Instabilitäten im operativen Betrieb führt.

Wie der Leiter der R&D-Abteilung bei AntsRoute Ammar Oulamara erklärt:

„Eine Echtzeit-Engine kann die Touren bei jedem neuen Ereignis nicht vollständig neu berechnen. Der Rechenaufwand und die dadurch verursachte Instabilität wären viel zu groß.“

Genau aus diesem Grund setzen moderne Engines auf Warm-Start-Verfahren.

Der Warm-Start: eine voroptimierte Lösung als Ausgangspunkt

Ein „Warm-Start“ besteht darin, den aktuellen Plan als Ausgangspunkt für die Optimierung zu nutzen. Anstatt nach einer völlig neuen Lösung zu suchen, versucht der Algorithmus, eine bereits konsistente Lösung lokal zu verbessern und dabei Beeinträchtigungen zu begrenzen, die das globale Gleichgewicht des Systems beeinträchtigen könnten.

Zu den wesentlichen Vorteilen dieses Ansatzes zählen insbesondere:

• die drastische Verkleinerung des Suchraums,
• die Erhaltung einer nachhaltigen operativen Tourenstabilität,
• die Echtzeit-Kompatibilität der Reaktionszeiten sowie
• die Vermeidung unnötiger Umstrukturierungen.

Ammar Oulamara fügt hinzu:

„Durch den Warm-Start konzentriert die Suchmaschine ihre Rechenleistung auf die Bereiche, die tatsächlich von einer Planänderung betroffen sind.“

Diese Herangehensweise verändert die Art und Weise, wie das Problem untersucht wird, grundlegend.

Eine Einfügung wird niemals isoliert bewertet

Wenn eine neue Aufgabe τ (engl. task) eingefügt wird, beschränkt sich die Engine nicht auf die Bewertung der unmittelbaren Grenzkosten. Diese Einfügung kann nämlich – vergleichbar mit dem Domino-Effekt – kaskadierende Folgewirkungen auf den gesamten Zeitplan haben, unter anderem auf:

• die zeitlichen Einschränkungen, die an anderen Stellen entstehen,
• die Sicherheitsmargen, die drastisch sinken,
• das verlorene Tourengleichgewicht,
• die zukünftige Fähigkeit zur Umstrukturierung oder
• die geografische Kompaktheit des Plans.

Die Suchmaschine muss daher nicht nur die Einfügung selbst untersuchen, sondern auch die lokalen Umstrukturierungen, die dadurch anschließend möglich werden. Genau diese Fähigkeit, eine bestehende Lösung zu verbessern, zeigt die grundlegende Rolle der lokalen Suchmechanismen.

Local Search: Die Umgebung einer Lösung erkunden

Bei Tourenoptimierungsproblemen ist es unmöglich, alle möglichen Lösungen erschöpfend zu untersuchen. Moderne Algorithmen arbeiten daher hauptsächlich mit der Erkundung von Nachbarschaften.
Das Prinzip ist einfach:

• von einer bestehenden Lösung ausgehen;
• bestimmte Transformationen lokal anwenden;
• und anschließend prüfen, ob die neue Lösung die Planung verbessert.

Bei AntsRoute nutzt der lokale Suchalgorithmus mehrere Operatoren zur effizienten Exploration dieser Nachbarschaften.

Relocate: Eine Aufgabe an eine bessere Position verschieben

Der Relocate-Operator ist einer der grundlegendsten Mechanismen in der lokalen Suche. Er besteht darin, eine Aufgabe aus einer Tour zu entfernen, um sie an einer anderen Position wieder einzufügen – entweder in derselben Tour oder in einer anderen Tour.
Durch diesen Vorgang werden insbesondere:

• wichtige Zeitpuffer wiederhergestellt,
• eine unausgewogene Tourauslastung ausgeglichen sowie
• drohende Kaskadeneffekte minimiert oder vollständig vermieden.

In dynamischen Systemen spielt „relocate“ oft eine zentrale Rolle bei schnellen Neuoptimierungen mit dem Vorteil, mit relativ geringem Rechenaufwand einen Zeitplan lokal deutlich zu verbessern.

Or-opt: Verschiebung von Aufgabensequenzen

In manchen Fällen reicht es nicht aus, eine einzelne Aufgabe zu verschieben, um ein gutes Gleichgewicht im Zeitplan wiederherzustellen. Die Engine verwendet dann Or-opt-Operatoren, bei denen eine Sequenz von 1, 2 oder 3 aufeinanderfolgenden Aufgaben an eine andere Position in der Tour oder im Zeitplan verschoben wird.
Dieser Ansatz ist besonders nützlich, wenn:

• mehrere Aufgaben eine enge geografische Kohärenz aufweisen oder
• die Beibehaltung der Tourkontinuität bei einer lokalen Umstrukturierung im Vordergrund steht.

So erklärt es Ammar Oulamara:

„Das Verschieben einer kohärenten Aufgabensequenz kann das Gleichgewicht im Plan manchmal viel effizienter wiederherstellen als eine Reihe von Einzelveränderungen.“

2-opt und 3-opt: Umstrukturierung der geografischen Verteilung der Touren

2-opt- und 3-opt-Operatoren verfolgen ein anderes Ziel. Dabei drehen sie die Reihenfolge bestimmte Teilsequenzen einer Tour um, um deren geografische Struktur zu verbessern.

Diese Mechanismen ermöglichen insbesondere:

• die Vermeidung von Überschneidungen,
• eine Verbesserung der geografischen Kompaktheit oder
• die Reduzierung unnötiger Umwege.

Dieser Ansatz erweist sich als besonders effektiv, wenn:

• die Touren zunehmend fragmentieren oder
• aufeinanderfolgende Einfügungen die räumliche Struktur der Route schrittweise verschlechtern.

Selbst in Systemen mit starken zeitlichen Einschränkungen bleibt die geografische Qualität der Touren ein wesentlicher Faktor für die operative Robustheit.

Cross-Exchange: Gleichzeitige Neuausrichtung mehrerer Touren

In stark ausgelasteten Systemen können bestimmte Einfügungen nicht durch einfache lokale Anpassungen aufgefangen werden. Die Engine muss dann mithilfe von Cross-Exchange-Operatoren mehrere Touren gleichzeitig neu organisieren, wobei ganze Segmente zwischen den Touren ausgetauscht werden, um ein besseres Gesamtgleichgewicht wiederherzustellen.

Diese Mechanismen erweisen sich insbesondere dann als nützlich, wenn:

• bestimmte kritische Ressourcen sich ihrer maximalen Auslastung nähern,
• mehrere Touren zeitlich instabil werden sowie
• die Möglichkeiten für lokale Anpassungen schwinden.

Die Engine agiert dann nicht mehr nur auf der Ebene einer einzelnen Tour, sondern auf der Ebene des gesamten Plans, um die sinnvollsten Ausgleichsmaßnahmen zu identifizieren.

Nicht alle Nachbarbereiche rechtfertigen den gleichen Rechenaufwand

Jeden möglichen Einfügepunkt eingehend zu untersuchen, wäre aus rechnerischer Sicht viel zu aufwendig. Die Engine setzt daher Prioritäten und konzentriert ihre Rechenleistung auf die vielversprechendsten Lösungen. Bei AntsRoute stützt sie dabei auf eine Hierarchie von Nachbarschaften; auf dieser Basis wird dann die Suchtiefe (eng. Search Depth) an die Qualität der bewerteten Einfügepunkte schrittweise und dynamisch angepasst.

Nachbarschaft ersten Grades (direkte Nachbarschaft)

Die erste Nachbarschaftsebene basiert ausschließlich auf einfachen lokalen Änderungen innerhalb derselben Tour. Ziel ist es, offensichtlich ungünstige Einfügungen schnell herauszufiltern und gleichzeitig den Rechenaufwand zu begrenzen.

Nachbarschaft zweiten Grades

In dieser Phase prüft die Engine den Austausch zwischen Touren sowie umfassendere Neugewichtungen. Diese Untersuchung ermöglicht es, die Gesamtfolgen bestimmter Einfügungen zu bewerten und Verbesserungen zu identifizieren, die auf der Ebene einer einzelnen Tour nicht sichtbar wären.

Nachbarschaft dritten Grades

In der dritten Nachbarschaftsebene werden wesentlich tiefgreifendere Umstrukturierungen überprüft und vorgenommen, die mehrtägige Umstrukturierungen oder erhebliche Änderungen am Zeitplan umfassen können. Diese rechenintensiveren Untersuchungen sind den vielversprechendsten Einfügungen oder besonders eingeschränkten Situationen vorbehalten.

Durch diese Hierarchie der Nachbarschaftsebenen kommt es zu einer intelligenten Zuweisung der Rechenleistung, die Suchtiefe wird an die erwartete Qualität der gefundenen Lösungen angepasst.

First-Improvement vs. Best-Improvement

Eine der wichtigsten Entscheidungen bei der lokalen Suche betrifft die Strategie, die zur Erkundung der Nachbarschaft einer Lösung verwendet wird. Im Allgemeinen kommen zwei Hauptansätze zum Einsatz: First-Improvement und Best-Improvement.

First-Improvement

Bei der First-Improvement-Strategie akzeptiert der Algorithmus die erste Verbesserung, auf die er bei der Erkundung stößt.
Dieser Ansatz bietet mehrere Vorteile:

• eine schnelle Konvergenz,
• einen geringen Rechenaufwand und
• eine gute Wirksamkeit in den ersten Phasen der Erkundung.

Best-Improvement

Im Gegensatz dazu besteht die Best-Improvement-Strategie darin, die gesamte Nachbarschaft zu durchsuchen, bevor die beste verfügbare Verbesserung ausgewählt wird. Sie ermöglicht in der Regel:

• das Erzielen einer höheren Lösungsqualität sowie
• eine gründlichere Untersuchung der Optimierungsmöglichkeiten.

Allerdings ist diese Strategie mit einem deutlich höheren Rechenaufwand verbunden.

Ammar Oulamara:

„Die Wahl zwischen ‚First-Improvement‘ und ‚Best-Improvement‘ hängt stark von der Dichte des Zeitplans und dem verfügbaren Rechenbudget ab.“

Bei AntsRoute wechselt die Engine dynamisch zwischen diesen beiden Strategien, je nach Qualität der beobachteten Lösungen, dem erreichten Konvergenzgrad und dem Sättigungsgrad des Zeitplans.

Warum exakte Methoden schnell an ihre Grenzen stoßen

Probleme der dynamischen Tourenplanung gehören zu einer Klasse besonders komplexer kombinatorischer Optimierungsaufgaben. Je mehr Einschränkungen hinzukommen, je dichter die Touren werden und je häufiger Echtzeitereignisse auftreten, desto stärker vergrößert sich der Suchraum. Exakte Methoden erweisen sich dann schnell als unpraktikabel für die betrieblichen Anforderungen, sowohl hinsichtlich der Rechenzeit als auch der Reaktionsfähigkeit.

Ammar Oulamara betont:

„Die Engine sucht nicht nach der theoretisch perfekten Lösung. Sie sucht innerhalb einer gewissen Rechenzeit nach der besten umsetzbaren Lösung, die sich für den operativen Einsatz eignet.“

Genau aus diesem Grund stützen sich moderne Suchmaschinen auf eine Kombination aus Heuristiken, Warm-Start-Mechanismen, lokalen Suchoperatoren und adaptiven Explorationsstrategien, um schnell robuste und betrieblich sinnvolle Lösungen zu liefern.

Fazit

In modernen Tourenoptimierungssystemen besteht die Schwierigkeit nicht nur darin, einen ersten Plan zu erstellen. Die eigentliche Herausforderung besteht darin, diesen kontinuierlich weiterzuentwickeln, ohne dabei seine Robustheit, Stabilität oder operative Qualität zu beeinträchtigen.

Der Warm-Start, lokale Suchoperatoren und Multi-Nachbarschafts-Explorationen ermöglichen es genau, diese Herausforderung zu bewältigen. In der Logistik der letzten Meile steht eine Tour niemals vollständig fest: Sie muss sich ständig an Veränderungen vor Ort anpassen können und dabei ein gutes Maß an operativer Leistung beibehalten.