Dynamic Multi-Depot Vehicle Routing with Online Requests: Event-Driven Transformer--DRL and Rolling-Horizon Benchmarking

Technische Samenvatting: Dynamisch Multi-Depot Voertuigrouteprobleem met Online Verzoeken

Probleemdefinitie
Dit artikel behandelt het Dynamische Multi-Depot Voertuigrouteprobleem (D-MDVRP), gekenmerkt door progressief onthulde verzoeken en evoluerende voertuigtoestanden. In tegenstelling tot statische VRP's, waarbij alle verzoeken voorafgaand aan de dispatch bekend zijn, betreft de D-MDVRP een sequentieel beslissingsproces waarbij nieuwe serviceverzoeken binnenkomen tijdens de uitvoering van routes. De dispatcher moet bepalen welk voertuig van welk depot elk verzoek bedient, terwijl beperkingen zoals voertuigcapaciteit, servicievraag, route-duur en veranderende voertuiglocaties worden beheerd. Het probleem wordt geformuleerd als een sequentieel beslissingsproces dat een balans vereist tussen operationele efficiëntie (minimaliseren van afstand en wachttijd) en stabiliteit (minimaliseren van verstoringen in bestaande plannen).

Methodologie
De auteurs stellen een geïntegreerd, event-gestuurd leer- en benchmarking-framework voor dat deterministische haalbaarheidsafhandeling combineert met deep reinforcement learning (DRL) en traditionele optimalisatie.

• State en Action Representatie: Het systeem modelleert verzoeken en voertuigen met behulp van genormaliseerde feature-vectoren. Verzoeken bevatten locatie, vraag, prioriteit, aankomsttijd en status (niet onthuld, in afwachting, toegewezen, onderweg, bedienend, voltooid). Voertuigen worden gerepresenteerd door locatie, resterende capaciteit, status en thuisdepot. De staat omvat globale kenmerken zoals simulatietijd en het aantal herplanningsmomenten.
• Event-Driven Simulatie: Het systeem vordert via discrete gebeurtenissen (aankomst van verzoeken, aankomst van voertuigen, start/voltooiing van service). Bij elk herplanningsmoment wordt de route opgedeeld in een fixed prefix (voltooide, actieve en op korte termijn vastgelegde beslissingen) en een flexible suffix. Alleen de flexibele suffix is onderhevig aan herverdeling of herordening.
• Feasibility Masking: Een deterministisch maskeringmechanisme voorkomt ongeldige acties (bijv. het toewijzen van een voltooid verzoek of het schenden van de capaciteit). Ongeldige voertuig-verzoekparen krijgen een negatieve oneindige logit vóór de softmax of greedy selectie, wat 100% haalbaarheid garandeert tijdens training en testen.
• Policy Architecturen:
  • MLP Policy: Een Multi-Layer Perceptron scoort voertuig-verzoekparen met behulp van verzoek-, voertuig-, globale en paar-specifieke kenmerken (bijv. incrementele afstand, voorspelde wachttijd).
  • Transformer Policy: Maakt gebruik van attention-mechanismen om afhankelijkheden tussen gecodeerde elementen te modelleren. Het gebruikt aparte tokens voor verzoeken, voertuigen en depots, met geleerde positionele embeddings en een globale contextvector.
• Trainingsregime: Policies worden getraind via Behavior Cloning (BC) met behulp van expert-demonstraties (afgeleid van heuristieken zoals wacht-bewuste insertie of een hybride expert), gevolgd door Proximal Policy Optimization (PPO) fine-tuning. De beloningsfunctie stemt overeen met het evaluatiedoel en bevat straffen voor afstand, wachttijd en routewijzigingen.
• Benchmarking: De geleerde policies worden vergeleken met:
  1. Dynamische Insertie Heuristieken: Inclusief 'nearest feasible', 'cheapest append' en 'waiting-aware insertion'.
  2. Rolling-Horizon Optimalisatie: Een tijdgelimiteerde (1 seconde) heroptimalisatie van flexibele verzoeken met behulp van OR-Tools/SCIP.

Belangrijkste Bijdragen

1. Geïntegreerd Framework: Het artikel presenteert een uniform framework dat een event-gestuurd D-MDVRP-omgeving, deterministische haalbaarheidsmaskering en fixed-prefix/flexible-suffix routeverplichtingen combineert.
2. Stabiliteitsbewuste Metrieken: Het introduceert aparte maten voor voertuigherverdeling en predecessor change (hersequencing), wat een genuanceerde analyse van routeverstoring mogelijk maakt in plaats van alle wijzigingen als één enkele metriek te behandelen.
3. Common-Protocol Benchmarking: De studie evalueert geleerde policies, heuristieken en rolling-horizon optimalisatie onder identieke haalbaarheidsregels, commitment-horizons en scenario-seeds, wat een eerlijke vergelijking biedt van componenten die vaak in isolatie worden bestudeerd.
4. Transferabiliteitsanalyse: Het werk onderzoekt het vermogen van geleerde policies om te schalen naar grotere probleeminstanties (tot 80 verzoeken) zonder hertraining.

Experimentele Resultaten
Experimenten werden uitgevoerd op synthetische Euclidische instanties met variërende aantallen depots, voertuigen en verzoeken (30, 50 en 80 verzoeken in totaal).

• Prestaties vs. Heuristieken: In een benchmark van 20 scenario's presteerde de "Nearest Feasible" heuristiek consistent beter dan alle geleerde policies (MLP en Transformer, met of zonder PPO) en de rolling-horizon baseline. "Nearest Feasible" behaalde de laagste gemiddelde doelstelling (346.1), de laagste afstand, de laagste wachttijd, de hoogste stabiliteit (minste routewijzigingen) en de snelste runtime (0.156 ms/actie).
• Impact van PPO: Over vijf onafhankelijke trainingsruns had PPO fine-tuning een verwaarloosbaar gemiddeld effect op de MLP policy (0.13% verbetering), maar verbeterde de Transformer policy met ongeveer 2,5%, hoewel met een hogere variabiliteit tussen de seeds.
• Schaalbaarheid: De geleerde policies werden succesvol overgedragen naar grotere instanties (tot 80 verzoeken) zonder hertraining, waarbij ze milliseconde-besluitvormingstijden behielden. Echter, hun doelwaarden en runtime namen toe met de probleemgrootte, en ze waren nog steeds niet superieur aan de sterkste heuristiek.
• Rolling-Horizon Trade-off: De rolling-horizon optimalisatie behaalde de laagste wachttijden en makespan, maar bracht aanzienlijk hogere computationele kosten en grotere routeverstoring met zich mee vergeleken met heuristieken en geleerde policies.
• Ablatieonderzoek: Het verwijderen van near-term commitments of herverdelingsstraffen verhoogde de algehele doelstelling, waarbij het verwijderen van de herverdelingsstraf statistisch significant was (p = 0.007).

Betekenis en Claims
Het artikel claimt bescheiden dat de primaire bijdrage de integratie en rigoureuze vergelijking van deze componenten is, in plaats van de uitvinding van een superieur route-algoritme. De resultaten laten zien dat, hoewel geleerde policies haalbare, milliseconde-snelle beslissingen en transferabiliteit over instantiegroottes bieden, ze niet beter presteerden dan de sterkste heuristiek ("Nearest Feasible") op het gebied van route-efficiëntie, service-responsiviteit, stabiliteit of online computationele tijd.

De auteurs benadrukken het belang van sterke heuristische baselines bij het evalueren van learning-gebaseerde benaderingen voor dynamische routing. De studie onderstreept dat het integreren van haalbaarheidsafhandeling, route-commitments en stabiliteitsmaten waardevol is voor het creëren van robuuste dynamische routing-policies, maar dat huidige learning-gebaseerde methoden in deze specifieke setting de klassieke heuristieken qua algehele prestaties nog niet hebben overtroffen. Het werk benadrukt dat geen enkele methode optimaal is over alle criteria (efficiëntie, responsiviteit, stabiliteit en snelheid), wat suggereert dat de keuze van de methode afhangt van de specifieke operationele prioriteiten van de toepassing.