A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

Technische Samenvatting: Een Computermethode voor het Oplossen van het Stochastisch Gezamenlijk Aanvulprobleem in Hoge Dimensies

Probleemformulering
Het artikel behandelt het Stochastisch Gezamenlijk Aanvulprobleem (SJRP), een klassieke uitdaging in voorraadbeheer die betrekking heeft op de coördinatie van voorraadsystemen met meerdere artikelen, waarbij een vaste aanvulkosten worden gemaakt voor gezamenlijk bestelde artikelen. In de beschouwde discrete-tijdformulering controleert een magazijnmanager periodiek de voorraadniveaus en beslist of bestellingen moeten worden geplaatst voor subsets van $d$ artikelen. Het systeem staat bloot aan willekeurige vraag, lineaire voorraadkosten en achterstandstraffen. Het doel is om de totale verwachte afgepaste kosten over een oneindige horizon te minimaliseren.

De kernmoeilijkheid ligt in de "vloek van de dimensionaliteit". Bij niet-nul vaste aanvulkosten worden beslissingen op artikelniveau onderling afhankelijk, waardoor de toestands- en beslissingsruimten van het bijbehorende Markov Beslissingsproces (MDP) exponentieel groeien met het aantal artikelen ($d$). Bijgevolg worden standaard dynamische programmeringstechnieken computationeel onuitvoerbaar voor situaties met hoge dimensionaliteit (bijvoorbeeld $d \ge 50$), en heeft de bestaande literatuur grotendeels vertrouwd op heuristische beleidsregels met beperkte theoretische garanties op optimaliteit.

Methodologie
Om deze computationele barrières te overwinnen, stellen de auteurs een nieuwe, op simulatie gebaseerde computermethode voor die discrete-tijd voorraadbeheer overbrugt met continu-tijd impulscontroletheorie en deep learning.

1. Benadering in Continu Tijd: Het discrete-tijd SJRP wordt benaderd door een continu-tijd impulscontroleprobleem. In deze formulering wordt het cumulatieve vraagproces gemodelleerd als een Gaussisch proces (Brownse beweging met drift), en kan de manager op elk moment ingrijpen om de voorraadtoestand instantaan naar een hoger niveau te laten springen tegen een vaste kost. Deze benadering maakt een probabilistische representatie van de waardenfunctie mogelijk die beter geschikt is voor oplossingstechnieken in hoge dimensies.

2. Probabilistische Representatie via Beperkte BSDE's: In tegenstelling tot standaard deep Backward Stochastic Differential Equation (BSDE)-methoden die steunen op bijna-zekere gelijkheden, wordt de waardenfunctie van dit impulscontroleprobleem gekarakteriseerd als de minimale oplossing van een beperkte BSDE. Dit leidt tot een stochastische identiteit die een bijna-zekere ongelijkheid omvat in plaats van een gelijkheid. Specifiek is de waardenfunctie $V(x)$ het supremum van waarden $v$ die voldoen aan een stochastische doelvoorwaarde die betrekking heeft op het referentieproces, de lopende kosten en de sprongkosten.

3. Deep Neural Network Oplosser: De auteurs ontwikkelen een computationeel algoritme om deze beperkte BSDE op te lossen met behulp van diepe neurale netwerken.

   • Verliesfunctie: Er wordt een nieuwe verliesfunctie geconstrueerd om de ongelijkheidsbeperking te hanteren. Deze bevat een strafterm voor schendingen van de stochastische ongelijkheid, gewogen door een instelbare strafparameter $\beta$.
   • Referentieproces: Een zorgvuldig ontworpen referentiebeleid (een gerandomiseerd order-up-to-beleid aangedreven door een Poisson-proces) wordt gebruikt om steekproefpaden te genereren. Dit proces is zo ontworpen dat het exploratie en exploitatie in evenwicht brengt, zodat de neurale netwerken worden getraind op relevante gebieden van de toestandsruimte.
   • Trainingsstrategie: Om stabiliteit te waarborgen, passen de auteurs een gezamenlijk schema toe voor de strafparameter $\beta$ en de leersnelheid. De straf wordt geleidelijk verhoogd terwijl de leersnelheid wordt verlaagd, waardoor het netwerk eerst de algemene structuur leert en vervolgens de ongelijkheidsbeperkingen strikt afdwingt.

4. Beleidsextractie: Zodra de waardenfunctie $V$ en zijn gradiënt $\nabla V$ zijn benaderd door neurale netwerken, wordt een implementeerbaar beleid afgeleid. Het beleid controleert een "geen-actie"-voorwaarde die is afgeleid uit de Hamilton-Jacobi-Bellman (HJB)-vergelijking. Als de voorwaarde wordt geschonden, wordt een bestelling geplaatst. De order-up-to-vector wordt bepaald door de som van de benaderde waardenfunctie en de bestelkosten te minimaliseren, een stap die efficiënt vooraf kan worden berekend.

Belangrijkste Bijdragen

• Schaalbaarheid in Hoge Dimensies: De methode lost het SJRP succesvol op voor dimensies tot ten minste 50 (50 SKU's), een regime waar traditionele MDP-gebaseerde optimale oplossingen onuitvoerbaar zijn.
• Nieuw Verliesontwerp: Het artikel introduceert een specifieke verliesfunctie en trainingschema die zijn toegespitst op het beperkte BSDE-kader dat vereist is voor impulscontrole, waarmee de uitdaging van bijna-zekere ongelijkheden wordt aangepakt die standaard deep BSDE-methoden niet hanteren.
• Engineering van het Referentieproces: Het ontwerp van het referentieproces met toestandsafhankelijke sprongen wordt geïdentificeerd als een kritieke innovatie om efficiënt trainen en dekking van de relevante toestandsruimte te waarborgen.
• Implementatie: De auteurs bieden een volledige pijplijn aan, van probleembenadering tot beleidsextractie, inclusief gedetailleerde strategieën voor het afstellen van hyperparameters en computationele resultaten.

Resultaten
Het voorgestelde Neuraal Netwerk (NN)-beleid werd geëvalueerd op 43 testproblemen over dimensies 2, 12 en 50, met variërende vraagvariabiliteit (laag, gemiddeld, hoog) en kostenstructuren.

• Lage Dimensies ($d=2$): Het NN-beleid werd vergeleken met het ware optimale beleid dat is afgeleid via standaard MDP-oplossingstechnieken. De resultaten tonen aan dat het NN-beleid presteert binnen 1% van de optimale kosten en de geometrie van de optimale beslissingsgrenzen nauwkeurig volgt.
• Hoge Dimensies ($d=12$ en $d=50$): Omdat optimale oplossingen onuitvoerbaar zijn, werd het NN-beleid getoetst tegen state-of-the-art heuristieken: periodieke review $(R, S)$, $(Q, S)$, hybride $(R, Q, S)$, can-order en onafhankelijke $(s, S)$ beleidsregels.
  • In 12 dimensies kwam het NN-beleid overeen met of overtrof het beste benchmark in alle gevallen. In situaties met gemiddelde en hoge variabiliteit overtrof het vaak het beste heuristische beleid met aanzienlijke marges (bijvoorbeeld tot 28% verbetering ten opzichte van $(R, S)$ in specifieke gevallen met hoge variabiliteit).
  • In 50 dimensies versloeg het NN-beleid consistent het beste beschikbare heuristische beleid in alle testcases, met prestatiekloven die oplopen tot 5,59%.
• Computationele Efficiëntie: De trainingstijd schaalt bescheiden met de dimensie (bijvoorbeeld ~4 uur voor 50 dimensies op een enkele GPU), waardoor de exponentiële groei die kenmerkend is voor roostergebaseerde methoden wordt vermeden.

Betekenis en Claims
Het artikel beweert dat zijn methode een computationeel haalbare aanpak biedt voor het verkrijgen van bijna-optimale beleidsregels voor stochastische gezamenlijke aanvulproblemen in hoge dimensies, een langdurige uitdaging in operations management. Door gebruik te maken van deep learning om het onderliggende impulscontroleprobleem in hoge dimensies op te lossen, tonen de auteurs aan dat het mogelijk is om de prestaties van de beste bestaande heuristieken te evenaren of te overtreffen zonder te vertrouwen op restrictieve structurele aannames. De auteurs merken op dat hoewel de methode momenteel wordt toegepast op het SJRP met lineaire kosten en onbeperkte bestelvectoren, het kader generaliseerbaar is naar andere impulscontroleproblemen, waaronder die in financiële engineering (bijvoorbeeld cashflowbeheer) en toeleveringsketens met levertijden of verloren verkoop, hoewel deze uitbreidingen worden overgelaten aan toekomstig werk. Het artikel benadrukt dat het voorgestelde beleid niet louter een heuristiek is, maar een datagedreven benadering van de optimale controle die is afgeleid uit een rigoureuze probabilistische formulering.