Learning Optimization Proxies for Sequential Contextual Stochastic Programs: An Order Fulfillment Application

Technische Samenvatting: Leer-geoptimaliseerde Proxies voor Sequentiële Contextuele Stochastische Programma's

Probleemformulering

Het artikel behandelt de uitdaging van sequentiële contextuele stochastische programma's in real-time beslissingssystemen, met een specifieke focus op omnichannel orderafhandeling in grootschalige e-commerce. In deze setting moet een beslisser arriverende orders toewijzen aan distributiecentra (DC's) en vervoerders onder onzekerheid met betrekking tot levertijden en toekomstige vraag.

De kern van de moeilijkheid ligt bij de latentiebeperking: hoewel hoogwaardige beslissingen offline gegenereerd kunnen worden met behulp van Contextual Sample Average Approximation (C-SAA) opgelost door commerciële optimalisatiesoftware, vereisen deze solvers doorgaans seconden tot minuten per instantie. Dit is onvoldoende voor piekperioden (bijv. tijdens feestdagen) waarbij sub-seconde responsen vereist zijn om honderden orders per minuut te verwerken. Gevolgelijk vallen operationele systemen vaak terug op eenvoudigere heuristieken die het gemodelleerde onzekerheidsaspect negeren, wat leidt tot suboptimale kosten en serviceniveaus.

Het probleem wordt geformaliseerd als een twee-fasen contextueel stochastisch programma:

1. Eerste fase: Onmiddellijke toewijzing van de producten van een order aan DC's en vervoerders op basis van de huidige context (ordereigenschappen, voorraadniveaus, vervoerskosten) en gesamplede scenario's van toekomstige onzekerheid.
2. Tweede fase: Geaggregeerde recourse voor toekomstige orders ($t+1 \dots T$), die de verwachte toekomstige verzend- en voorraadtekortkosten vertegenwoordigt, gegeven de door de eerste-fase beslissing geconsumeerde voorraad.

Het doel is om de totale verwachte kosten te minimaliseren, inclusief verzendkosten, asymmetrische leveringstijd-boetes (te laat versus te vroeg), consolidatiekortingen en voorraadtekort-boetes, terwijl de voorraadbeperkingen worden gerespecteerd.

Methodologie

De auteurs stellen een leer-gebaseerde optimalisatie-proxy voor die de per-epoch solver-oproep vervangt door een enkele forward pass van een neuraal netwerk, gevolgd door een haalbaarheids-afdwingende decoder.

1. Architectuur: Scenario-geëmbedde Hiërarchische Neurale Netwerk
In tegen tegenstelling tot eerdere optimalisatie-proxies die vertrouwen op puntvoorspellingen, is dit model scenario-bewust. Het neemt als input:

• Contextuele Kenmerken: Orderdetails, DC-voorraadstatussen en vervoerskostenmatrices.
• Scenario Sets: Gesamplede realisaties van toekomstige vraag en afwijkingen in levertijden, gegenereerd door passende voorspellers (Multi-Horizon Quantile RNN voor vraag, Multi-Quantile MLP voor levertijden).

Het netwerk maakt gebruik van een DeepSets-stijl encoder om ongeordende scenario-sets te verwerken, waarbij embeddings worden gemiddeld om de verwachtingsstructuur van de C-SAA objectief te benaderen. De architectuur is hiërarchisch:

• DC Head: Voorspelt een logit voor elk distributiecentrum.
• Carrier Head: Voorspelt een logit voor elke vervoerdersdienst, geconditioneerd op de gekozen DC.
  Deze factorisatie ($p(j) \cdot p(k|j)$) vermindert de complexiteit van het leren van de volledige gezamenlijke toewijvingsruimte.

2. Trainingsstrategie: Composiet Verliesfunctie
De proxy wordt offline getraind op labels gegenereerd door de C-SAA solver. De trainingsdoelstelling combineert drie termen:

• Label Imitatie (Selectieverlies): Cross-entropy verlies tegen de primaire DC- en vervoerkeuzes afgeleid van de C-SAA oplossing.
• Schending van Beperkingen Straf (Constraint Violation Penalty): Een zelf-gesuperviseerde term met behulp van Straight-Through Gumbel-Softmax om toewijzingen te bestraffen die de beschikbare voorraad overschrijden, waardoor het model leert de harde beperkingen te respecteren.
• Kostenuitlijning (Cost Alignment): Een zelf-gesuperviseerde regularisator die de waarschijnlijkheidsmassa naar laag-kostende (DC, vervoer) paren trekt op basis van de direct geobserveerde kosten in de gesamplede scenario's.

3. Inferentie: Voorraad-gewogen Decoding
Tijdens de runtime genereert het neurale netwerk logits die worden omgezet in waarschijnlijkheden. Een speciale decoder dwingt vervolgens de haalbaarheid af:

• Het herweegt de voorspelde waarschijnlijkheden door de fractionele voorraaddekking ($min\{Inv/q, 1\}$) van elke DC.
• Het voert een greedy scan uit van in aanmerking komende DC's en vervoerders, waarbij de vraag wordt toegewezen totdat de order is vervuld of de voorraad is uitgeput.
• Dit proces zorgt ervoor dat de uiteindelijke beslissing strikt haalbaar is (respectieert voorraadlimieten en vraagtevredenheid) in $O(|J| \log |J| + |J||K|)$ tijd.

Belangrijkste Bijdragen

Het artikel levert vier primaire bijdragen:

1. Scenario-geconditioneerde Proxy: Een nieuwe architectuur die expliciet conditioneert op gesamplede scenario-sets in plaats van puntvoorspellingen, waardoor zowel directe stochastische kosten als de sequentiële impact van resourceconsumptie worden gevangen.
2. Sequentieel Fulfillment Model: Een twee-fasen contextuele stochastische formulering die de onmiddellijke order-toewijzingen expliciet koppelt aan de opportuniteitskosten van voorraadconsumptie voor toekomstige orders.
3. Theoretische Garanties: De auteurs bewijzen dat de voorraad-gewogen decoder een haalbare beslissing oplevert met een logaritmisch-lineaire runtime complexiteit. Ze stellen verder vast dat de verwachte kosten van de proxy de optimale twee-fasen doelstelling boven-grenzen en dat de out-of-sample prestaties onbevooroordeelde, consistente schatters toelaten.
4. Empirische Validatie: Een uitgebreide computationele studie met behulp van een simulator die is gekalibreerd met transactiegegevens van JD.com en propriëtaire vervoerdersgegevens.

Resultaten

In de gekalibreerde simulator vertoont de voorgestelde proxy significante verbeteringen ten opzichte van zowel solver-gebaseerde baselines als gevestigde heuristische policies:

• Latentie: De beslissingslatentie is met ongeveer 2.800× verminderd vergeleken met de online finite-sample C-SAA referentie, wat sub-seconde responsen mogelijk maakt.
• Kostenefficiëntie: De proxy verbetert de gerealiseerde afhandelingskosten met 3,3% ten opzichte van de C-SAA baseline (die al van hoge kwaliteit is maar traag) en vermindert de totale gerealiseerde kosten met ten minste 10,7% vergeleken met gevestigde fulfillment policies.
• Serviceniveau: De proxy halveert ruwweg het percentage te late leveringen van de sterkste klassieke baselines, wat de on-time delivery metriek die de klanttevredenheid drijft, direct verbetert.

Betekenis

Het artikel betoogt dat voor volumes die hoog zijn en latentie-kritisch zijn, zoals e-commerce afhandeling, de afweging tussen optimalisatiekwaliteit en computationele snelheid een kritieke bottleneck vormt. Door een proxy te ontwikkelen die leert van door solvers gegenereerde labels terwijl het onzekerheid expliciet modelleert via scenario's, laten de auteurs zien dat het mogelijk is om bijna optimale beslissingskwaliteit te bereiken met real-time inferentie-snelheden. Deze aanpak overbrugt de kloof tussen de theoretische voordelen van contextuele stochastische optimalisatie en de praktische beperkingen van industriële, real-time beslissingssystemen op grote schaal. Het werk suggereert dat dergelijke proxies een levensvatbaar alternatief kunnen zijn voor heuristieken in omgevingen waar traditionele solvers te traag zijn voor online inzet.