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

Technische Samenvatting: Een tweestaps stochastisch optimalisatiemodel voor gesynchroniseerde twee-etage routeproblemen

Probleemdefinitie
Deze studie behandelt de complexiteit van onzekerheid binnen stedelijke logistiek, met een specifieke focus op geïntegreerde water- en landgebaseerde transportsystemen (IWLT). Het kernprobleem is het twee-etage multi-trip voertuigrouteprobleem met satellietsynchronisatie (2E-MVRP-SS). In dit systeem opereren lichte elektrische vrachtvoertuigen (LEFV's) in het eerste etage (straten) om goederen te verzamelen bij klanten en deze over te dragen aan schepen (tweede etage) bij satellietknooppunten. Het systeem werkt zonder opslagmogelijkheden bij de satellieten, wat strikte spatiotemporele synchronisatie tussen de LEFV's en de schepen vereist.

De primaire uitdaging die wordt aangepakt, is de propagatie van vertragingen veroorzaakt door onzekere overslag wachttijden bij de satellieten. Deze onzekerheden, voortkomend uit regionale factoren zoals verkeerscongestie of operationele variaties, kunnen gesynchroniseerde operaties verstoren, wat leidt tot klantvertragingen, verhoogde operationele kosten en verminderde betrouwbaarheid. De studie richt zich specifiek op reverse logistics scenario's (bijv. afvalinzameling, retourzendingen) waar tijdige service cruciaal is om voorraadkosten en ongemak voor de klant te minimaliseren.

Methodologie
De auteurs stellen een tweestaps stochastisch optimalisatieraamwerk voor met een mixed-integer recourse probleem om deze onzekerheden te beheren.

1. Tweestaps Formulering:

   • Eerste fase (Master Problem): Beslissingen worden genomen met betrekking tot de LEFV-routes en de toewijzing van transfertaken aan satellieten voordat de vertragingen zich manifesteren. Deze fase geeft prioriteit aan betrouwbare servicetijden voor pick-ups. Het model gaat ervan uit dat LEFV's de dichtstbijzijnde satelliet bezoeken als een initiële benadering.
   • Tweede fase (Recourse/Subprobleem): Zodra specifieke vertragingsscenario's gerealiseerd zijn, worden corrigerende maatregelen genomen. Dit omvat het herverdelen van overslagoperaties naar andere satellieten en het herrouteren van schepen om de impact van vertragingen te mitigeren. De LEFV-schema's voor klantenservice blijven vast om beloofde tijden na te komen, maar de logistiek op het water wordt opnieuw geoptimaliseerd.

2. Algoritmische Aanpak:

   • Om de niet-convexiteit van de tweede-fase kostenfunctie en het mixed-integer karakter van het probleem aan te pakken, gebruiken de auteurs een L-shaped methode aangepast met combinatorische Benders cuts.
   • Het algoritme roteert tussen een ontspannen masterprobleem en subproblemen voor elk scenario.
   • Feasibility cuts (haalbaarheidsrestricties) zorgen ervoor dat beslissingen in de eerste fase leiden tot haalbare oplossingen in de tweede fase.
   • Optimality cuts (optimaliteitsrestricties) benaderen de verwachte kosten van de tweede fase.
   • Een scenario-gebaseerde bemonsteringsmethode wordt gebruikt om regionale onzekerheden te representeren. Vertragingen bij satellieten worden gemodelleerd als normaal verdeelde variabelen, gediscretiseerd in een eindige set scenario's ($N$) om computationele hanteerbaarheid te garanderen terwijl stabiliteit behouden blijft.

3. Experimentele Opzet:

   • Het model werd getest op kleine netwerkinstantiën (10 pickup-nodes, 4 satellieten) afgeleid van gemodificeerde Solomon VRPTW-instanties.
   • Twee systeemontwerpen werden vergeleken: 2E-Flexible (schepen fungeren als mobiele depots, gesynchroniseerd met LEFV's) en 2E-Stationary (vaste scheepslocaties).
   • Prestaties werden geëvalueerd tegen een deterministische (geen vertraging) baseline en een tweestaps stochastische aanpak.

Belangrijkste Bijdragen

• Nieuwe Modellering van Synchronisatie: Dit is de eerste studie die de impact van satellietvertragingen op voertuigsynchronisatie adresseert in een twee-etage systeem met geen opslagcapaciteit, een scenario dat een hoge spatiotemporele coördinatie vereist.
• Stochastisch Recourse Raamwerk: Het artikel stelt een tweestaps stochastisch programmeermodel voor met mixed-integer recourse specifiek voor 2E-MVRP-SS. Het maakt gebruik van combinatorische Benders cuts binnen een enumeratiemethode om de niet-convexiteit van de tweede fase te behandelen.
• Vergelijkende Analyse van Flexibiliteit: De studie biedt een kwantitatieve vergelijking tussen flexibele transportsystemen (mobiele schepen) en stationaire systemen onder onzekerheid, waarbij de waarde van flexibiliteit bij het mitigeren van vertragingspropagatie wordt aangetoond.

Resultaten

• Kostenreductie: Het voorgestelde stochastische programmeermodel verminderde de verwachte totale kosten met 37% over alle instanties vergeleken met een deterministische aanpak die uitgaat van geen vertragingen.
• Scenario Stabiliteit: De scenario-generatie aanpak toonde stabiliteit; de variantie van scenario's binnen de steekproef nam af naarmaling van het aantal scenario's, waarbij het stabiliseerde rond de 30 scenario's.
• Impact van Netwerktopologie:
  • Voor Geclusterde (C) vraagnetwerken behield het geïntegreerde systeem de efficiëntie met een minimale kostenstijging (bijna 0%) onder onzekerheid.
  • Voor Random (R) netwerken behaalde de stochastische aanpak de meest significante besparingen vergeleken met deterministische strategieën, waarbij de verwachte kosten in specifieke instanties met wel 43% werden verminderd door vertragingsgevoelige pickup-locaties beter te positioneren.
• Systeemprestaties (Flexibel vs. Stationair):
  • Het 2E-Flexible systeem presteerde aanzienlijk beter dan het 2E-Stationary systeem wat betreft betrouwbaarheid en modal share (modaliteitsverdeling).
  • Onder onzekerheid ervoer het stationaire systeem een scherpe toename in reistijden op straat en lateness (bijv. lateness steeg naar 26 tijdseenheden in RC-instanties), terwijl het flexibele systeem de lateness laag hield (9 tijdseenheden) en een meer gebalanceerde modal share tussen weg- en watertransport behield.
  • Het flexibele systeem mitigeerde het risico op verhoogde reiskosten op straat effectief, wat aantoont dat het verplaatsen van opslagunits (of in dit geval overslagpunten) de prestaties van flexibele vaarbedrijven qua congestie en betrouwbaarheid niet kan evenaren.

Betekenis en Claims
Het artikel claimt dat het integreren van onzekerheid in offline planning essentieel is voor de betrouwbaarheid en kosteneffectiviteit van multimodale stedelijke logistiek, met name in contexten waar concurrentie om stedelijke ruimte de opslagopties beperkt. De studie demonstreert dat flexibele systemen, waarbij schepen fungeren als mobiele depots gesynchroniseerd met LEFV's, superieure veerkracht bieden tegen overslagvertragingen vergeleken met systemen met vaste locaties.

De auteurs concluderen dat hoewel het voorgestelde model computationeel intensief is, de geobserveerde winsten in kleine instanties suggereren dat stochastische optimalisatie de servicebetrouwbaarheid aanzienlijk kan verbeteren en het "groene" modal share (weggebruik) in stedelijke logistiek kan verminderen. Zij merken op dat toekomstig werk de voorgestelde enumeratie- en pricingframework kan gebruiken om heuristieken voor grootschalige problemen te ontwikkelen, maar de huidige studie richt zich op het valideren van het theoretische raamwerk en de voordelen van flexibiliteit op kleine, oplosbare netwerken.