A two-stage stochastic optimization model for synchronized two-echelon routing problems

Technisches Resümee: Ein zweistufiges stochastisches Optimierungsmodell für synchronisierte Zwei-Echelon-Routing-Probleme

Problemdefinition
Diese Studie befasst sich mit der Komplexität der Unsicherheit in der Stadtlogistik, wobei der Schwerpunkt auf integrierten land- und wasserbasierten Transportsystemen (IWLT) liegt. Das Kernproblem ist das Zwei-Echelon Multi-Trip Vehicle Routing Problem mit Satellitensynchronisation (2E-MVRP-SS). In diesem System operieren leichte elektrische Lieferfahrzeuge (LEFVs) auf der ersten Ebene (Straßen), um Waren von Kunden zu sammeln und sie an Satellitenknoten an Schiffe (zweite Ebene) zu übergeben. Das System arbeitet ohne Lagerkapazitäten an den Satelliten, was eine strikte spatiotemporale Synchronisation zwischen den LEFVs und den Schiffen erfordert.

Die primäre Herausforderung ist die Ausbreitung von Verzögerungen, die durch unsichere Umschlagslaufzeiten an den Satelliten verursacht werden. Diese Unsicherheiten, die aus regionalen Faktoren wie Verkehrsüberlastungen oder betrieblichen Variationen resultieren, können die synchronisierten Abläufe stören, was zu Verspätungen bei den Kunden, erhöhten Betriebskosten und reduzierter Zuverlässigkeit führt. Die Studie konzentriert sich speziell auf Reverse-Logistik-Szenarien (z. B. Abfallentsorgung, Retouren), bei denen ein zeitgerechter Service entscheidend ist, um Lagerkosten und Kundenunannehmlichkeiten zu minimieren.

Methodik
Die Autoren schlagen einen zweistufigen stochastischen Optimierungsrahmen mit einem gemischt-ganzzahligen Rekursproblem vor, um diese Unsicherheiten zu bewältigen.

1. Zweistufige Formulierung:

   • Erste Stufe (Master-Problem): Entscheidungen bezüglich der LEFV-Routen und der Zuweisung von Transferaufgaben an Satelliten werden getroffen, bevor die Verzögerungen realisiert werden. Diese Stufe priorisiert zuverlässige Servicezeiten für die Abholungen. Das Modell nimmt an, dass LEFVs zur ersten Annäherung den nächstgelegenen Satelliten besuchen.
   • Zweite Stufe (Rekurs/Subproblem): Sobald spezifische Verzögerungsszenarien realisiert werden, werden Korrekturmaßnahmen ergriffen. Dies beinhaltet die Neuverteilung der Umschlagsprozesse auf andere Satelliten und die Neuplanung der Routen der Schiffe, um die Auswirkungen der Verzögerungen abzumildern. Die LEFV-Zeitpläne für den Kundenservice bleiben fest vorgegeben, um die versprochenen Zeiten einzuhalten, aber die Wasserlogistik wird neu optimiert.

2. Algorithmischer Ansatz:

   • Um die Nichtkonvexität der Kostenfunktion der zweiten Stufe und die gemischt-ganzzahlige Natur des Problems zu handhaben, verwenden die Autoren eine L-Shaped-Methode, die mit kombinatorischen Benders-Cuts angepasst wurde.
   • Der Algorithmus iteriert zwischen einem relaxierten Master-Problem und Subproblemen für jedes Szenario.
   • Feasibility Cuts (Zulässigkeits-Schnitte) stellen sicher, dass Entscheidungen der ersten Stufe zulässige Lösungen der zweiten Stufe ermöglichen.
   • Optimality Cuts (Optimalitäts-Schnitte) approximieren die erwarteten Kosten der zweiten Stufe.
   • Ein szenarienbasiertes Sampling-Verfahren wird verwendet, um regionale Unsicherheiten darzustellen. Verzögerungen an den Satelliten werden als normalverteilte Variablen modelliert, die in einen endlichen Satz von Szenarien ($N$) diskretisiert werden, um die Rechenpraktikabilität zu gewährleisten und gleichzeitig die Stabilität zu wahren.

3. Experimenteller Aufbau:

   • Das Modell wurde an kleinen Netzwerkinstanzen (10 Abholdaten, 4 Satelliten) getestet, die aus modifizierten Solomon-VRPTW-Instanzen abgeleitet wurden.
   • Es wurden zwei Systemdesigns verglichen: 2E-Flexible (Schiffe fungieren als mobile Depots, synchronisiert mit den LEFVs) und 2E-Stationary (feste Schiffspositionen).
   • Die Leistung wurde gegen eine deterministische (keine Verzögerung) Baseline und einen zweistufigen stochastischen Ansatz evaluiert.

Wesentliche Beiträge

• Neuartige Modellierung der Synchronisation: Dies ist die erste Studie, die die Auswirkungen von Satellitenverzögerungen auf die Fahrzeugsynchronisation in einem Zwei-Echelon-System mit fehlender Lagerkapazität adressiert – ein Szenario, das eine hohe spatiotemporale Koordination erfordert.
• Stochastischer Rekurs-Rahmen: Die Arbeit schlägt ein zweistufiges stochastisches Programmierungsmodell mit gemischt-ganzzahligem Rekurs speziell für 2E-MVRP-SS vor. Sie nutzt kombinatorische Benders-Cuts innerhalb einer Enumerationsmethode, um die Nichtkonvexität der zweiten Stufe zu handhaben.
• Vergleichende Analyse der Flexibilität: Die Studie liefert einen quantitativen Vergleich zwischen flexiblen Transportsystemen (mobile Schiffe) und stationären Systemen unter Unsicherheit und zeigt den Wert der Flexibilität bei der Abmilderung der Verzögerungsausbreitung auf.

Ergebnisse

• Kostensenkung: Das vorgeschlagene stochastische Programmierungsmodell reduzierte die erwarteten Gesamtkosten um 37 % über alle Instanzen hinweg im Vergleich zu einem deterministischen Ansatz, der keine Verzögerungen annimmt.
• Szenario-Stabilität: Der Ansatz zur Szenariengenerierung zeigte Stabilität; die Varianz der Szenarien innerhalb der Stichprobe sank mit zunehmender Anzahl der Szenarien und stabilisierte sich bei etwa 30 Szenarien.
• Einfluss der Netzwerktopologie:
  • Für geclusterte (C) Nachernetzwerke behielt das integrierte System die Effizienz mit minimalem Kostenanstieg (nahe 0 %) unter Unsicherheit bei.
  • Für zufällige (R) Netzwerke erzielte der stochastische Ansatz die signifikantesten Einsparungen gegenüber deterministischen Strategien und senkte die erwarteten Kosten in spezifischen Instanzen um bis zu 43 %, indem verzögerungsempfindliche Abholorte besser lokalisiert wurden.
• Systemleistung (Flexibel vs. Stationär):
  • Das 2E-Flexible System übertraf das 2E-Stationary System hinsichtlich Zuverlässigkeit und Modalanteil deutlich.
  • Unter Unsicherheit verzeichnete das stationäre System einen starken Anstieg der Fahrzeiten auf der Straße und der Verspätungen (z. B. stieg die Verspätung in RC-Instanzen auf 26 Zeiteinheiten), während das flexible System die Verspätungen niedrig hielt (9 Zeiteinheiten) und einen ausgewogeneren Modalanteil zwischen Straßen- und Wassertransport beibehielt.
  • Das flexible System milderte das Risiko steigender Straßenfahrtkosten effektiv ab und demonstrierte, dass die bloße Umgestaltung von Lagerorten (bzw. hier: Umschlagpunkten) die Leistung flexibler Segeldienste in Bezug auf Stau und Zuverlässigkeit nicht erreichen kann.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass die Einbeziehung von Unsicherheit in die Offline-Planung essenziell für die Zuverlässigkeit und Kosteneffizienz der multimodalen Stadtlogistik ist, insbesondere in Kontexten, in denen der Wettbewerb um den urbanen Raum die Lageroptionen einschränkt. Die Studie zeigt, dass flexible Systeme, bei denen Schiffe als mobile Depots synchronisiert mit LEFVs agieren, eine überlegene Resilienz gegenüber Umschlagverzögerungen bieten als Systeme mit festen Standorten.

Die Autoren kommen zu dem Schluss, dass, obwohl das vorgeschlagene Modell rechenintensiv ist, die beobachteten Gewinne in kleinen Instanzen darauf hindeuten, dass stochastische Optimierung die Servicezuverlässigkeit erheblich verbessern und den „grünen“ Modalanteil (Straßennutzung) in der Stadtlogistik senken kann. Sie merken an, dass zukünftige Arbeiten das vorgeschlagene Enumerations- und Pricing-Framework nutzen könnten, um Heuristiken für groß angelegte Probleme zu entwickeln, sich die aktuelle Studie jedoch auf die Validierung des theoretischen Rahmens und der Vorteile der Flexibilität auf kleinen, lösbaren Netzwerken konzentriert.