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

Résumé Technique : Proxys d'Apprentissage pour la Programmation Stochastique Contextuelle Séquentielle

Formulation du Problème

L'article traite du défi des programmes stochastiques contextuels séquentiels dans les systèmes de décision en temps réel, en se concentrant spécifiquement sur l'exécution des commandes omnicanales dans l'e-commerce à grande échelle. Dans ce contexte, un décideur doit affecter les commandes entrantes aux centres de distribution (DC) et aux services de transport sous une incertitude concernant les délais de livraison et la demande future.

La difficulté centrale réside dans la contrainte de latence : si des décisions de haute qualité peuvent être générées hors ligne via une Approximation par Moyenne Échantillonnée Contextuelle (C-SAA) résolue par des solveurs d'optimisation commerciaux, ces solveurs nécessitent généralement des secondes ou des minutes par instance. Cela est insuffisant pour les périodes opérationnelles de pointe (ex. : ventes de fêtes) où des réponses en sous-seconde sont requises pour gérer des centaines de commandes par minute. Par conséquent, les systèmes opérationnels se rabattent souvent sur des heuristiques plus simples qui ignorent l'incertitude modélisée, entraînant des coûts et des niveaux de service sous-optimaux.

Le problème est formalisé comme un programme stochastique contextuel à deux étapes :

1. Première étape : Affectation immédiate des produits d'une commande aux DC et aux transporteurs en fonction du contexte actuel (attributs de la commande, niveaux d'inventaire des DC, coûts des transporteurs) et d'échantillons de scénarios d'incertitude future.
2. Deuxième étape : Recours agrégé pour les commandes futures ($t+1 \dots T$), représentant le coût attendu futur de l'expédition et des ruptures de stock compte tenu de l'inventaire consommé par la décision de la première étape.

L'objectif est de minimiser les coûts totaux attendus, incluant l'expédition, les pénalités de délai asymétriques (retard vs avance), les remises sur la consolidation et les pénalités de rupture de stock, tout en respectant les contraintes d'inventaire.

Méthodologie

Les auteurs proposent un proxy d'optimisation basé sur l'apprentissage qui remplace l'appel au solveur par époque par une simple passe avant d'un réseau de neurones, suivie d'un décodeur garantissant la faisabilité.

1. Architecture : Réseau Neuronal Hiérarchique avec Intégration de Scénarios
Contra�à les proxys d'optimisation précédents qui reposent sur des prévisions ponctuelles, ce modèle est sensible aux scénarios. Il prend en entrée :

• Caractéristiques contextuelles : Détails de la commande, états d'inventaire des DC et matrices de coûts des transporteurs.
• Ensembles de scénarios : Réalisations échantillonnées de la demande future et des écarts de délais de livraison, générées par des prévoyants ajustés (RNN à quantiles multi-horizons pour la demande, MLP multi-quantiles pour les délais de livraison).

Le réseau utilise un encodeur de type DeepSets pour traiter les ensembles de scénarios non ordonnés, moyennant les plongements (embeddings) pour approximer la structure d'espérance de l'objectif C-SAA. L'architecture est hiérarchique :

• Tête DC : Prédit un logit pour chaque centre de distribution.
• Tête Transporteur : Prédit un logit pour chaque service de transport conditionnel au DC sélectionné.
  Cette factorisation ($p(j) \cdot p(k|j)$) réduit la complexité de l'apprentissage de l'espace complet d'affectation conjointe.

2. Stratégie d'Entraînement : Fonction de Perte Composite
Le proxy est entraîné hors ligne sur des étiquettes générées par le solveur C-SAA. L'objectif d'entraînement combine trois termes :

• Imitation d'Étiquette (Perte de Sélection) : Perte d'entropie croisée par rapport aux choix principaux de DC et de transporteur dérivés de la solution C-SAA.
• Pénalité de Violation de Contrainte : Un terme auto-supervisé utilisant un Gumbel-Softmax "Straight-Through" pour pénaliser les affectations dépassant l'inventaire disponible, garantissant que le modèle apprend à respecter les contraintes strictes.
• Alignement de Coût : Un régulariseur auto-supervisé qui attire la masse de probabilité vers les paires (DC, transporteur) à faible coût basées sur les coûts immédiats observés dans les scénarios échantillonnés.

3. Inférence : Décodage Pondéré par l'Inventaire
Au moment de l'exécution, le réseau de neurones produit des logits qui sont convertis en probabilités. Un décodeur dédié impose ensuite la faisabilité :

• Il repondère les probabilités prédites par la couverture fractionnelle de l'inventaire ($min\{Inv/q, 1\}$) de chaque DC.
• Il effectue un balayage glouton des DC et transporteurs éligibles, affectant la demande jusqu'à ce que la commande soit remplie ou que l'inventaire soit épuisé.
• Ce processus garantit que la décision finale est strictement faisable (respectant les plafonds d'inventaire et la satisfaction de la demande) en un temps $O(|J| \log |J| + |J||K|)$.

Contributions Clés

Le papier présente quatre contributions principales :

1. Proxy Conditionné par Scénarios : Une architecture novatrice qui se conditionne explicitement sur des ensembles de scénarios échantillonnés plutôt que sur des prévisions ponctuelles, capturant à la fois les coûts stochastiques immédiats et l'impact séquentiel de la consommation des ressources.
2. Modèle d'Exécution Séquentielle : Une formulation stochastique contextuelle à deux étapes qui lie explicitement les affectations immédiates de commandes au coût d'opportunité de la consommation d'inventaire pour les commandes futures.
3. Garanties Théoriques : Les auteurs prouvent que le décodeur pondéré par l'inventaire produit une décision faisable avec une complexité de temps log-linéaire. Ils établissent également que le coût attendu du proxy est une borne supérieure de l'objectif optimal à deux étapes et que ses performances hors échantillon admettent des estimateurs non biaisés et cohérents.
4. Validation Empirique : Une étude computationnelle complète utilisant un simulateur calibré avec les données transactionnelles de JD.com et des données de transporteurs propriétaires.

Résultats

Dans le simulateur calibré, le proxy proposé démontre des améliorations significatives par rapport aux bases de référence basées sur des solveurs et aux politiques heuristiques établies :

• Latence : La latence de décision est réduite d'environ 2 800× par rapport à la référence C-SAA à échantillon fini en ligne, permettant des réponses en sous-seconde.
• Efficacité des Coûts : Le proxy améliore les coûts d'exécution réalisés de 3,3 % par rapport à la base de référence C-SAA (qui est déjà de haute qualité mais lente) et réduit les coûts totaux réalisés d'au moins 10,7 % par rapport aux politiques d'exécution établies.
• Niveau de Service : Le proxy réduit environ de moitié le taux de livraison tardive des bases de référence classiques les plus performantes, améliorant directement la métrique de livraison à temps qui régit la satisfaction client.

Signification

L'article soutient que pour les opérations à haut volume et à latence critique comme l'exécution de commandes e-commerce, le compromis entre la qualité de l'optimisation et la vitesse de calcul est un goulot d'étranglement critique. En développant un proxy qui apprend à partir d'étiquettes générées par un solveur tout en modélisant explicitement l'incertitude via des scénarios, les auteurs démontrent qu'il est possible d'atteindre une qualité de décision quasi optimale avec des vitesses d'inférence en temps réel. Cette approche comble le fossé entre les avantages théoriques de l'optimisation stochastique contextuelle et les contraintes pratiques des systèmes de prise de décision à l'échelle industrielle en temps réel. Le travail suggère que de tels proxys peuvent constituer une alternative viable aux heuristiques dans des contextes où les solveurs traditionnels sont trop lents pour être déployés en ligne.