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

Resumen Técnico: Proxies de Aprendizaje para la Optimización de Programas Estocásticos Contextuales Secuenciales

Formulación del Problema

El artículo aborda el desafío de los programas estocásticos contextuales secuenciales en sistemas de decisión en tiempo real, centrándose específicamente en el cumplimiento de pedidos omnicanal en el comercio electrónico a gran escala. En este entorno, un tomador de decisiones debe asignar los pedidos entrantes a centros de distribución (DC) y servicios de transporte bajo incertidumbre respecto a los tiempos de entrega y la demanda futura.

La dificultad central radica en la restricción de latencia: si bien se pueden generar decisiones de alta calidad de forma offline utilizando la Aproximación de Promedio de Muestras Contextual (C-SAA) resuelta mediante solvers de optimización comerciales, estos solvers suelen requerir segundos o minutos por instancia. Esto es insuficiente para periodos operativos de máxima actividad (por ejemplo, ventas de temporada festiva) donde se requieren respuestas de sub-segundo para manejar cientos de pedidos por minuto. En consecuencia, los sistemas operativos suelen recurrir a heurísticas más simples que ignoran la incertidumbre modelada, lo que conduce a costos y niveles de servicio subóptimos.

El problema se formaliza como un programa estocástico contextual de dos etapas:

1. Primera Etapa: Asignación inmediata de los productos de un pedido a los DC y transportistas basándose en el contexto actual (atributos del pedido, niveles de inventario de los DC y matrices de costos de transporte) y escenarios muestreados de la incertidumbre futura.
2. Segunda Etapa: Recurso agregado para pedidos futuros ($t+1 \dots T$), que representa el costo esperado de envío y de falta de existencias (stockout) dado el consumo de inventario por la decisión de la primera etapa.

El objetivo es minimizar los costos totales esperados, incluyendo el envío, las penalizaciones asimétricas por tiempo de entrega (retraso vs. anticipación), descuentos por consolidación y penalizaciones por falta de existencias, respetando las restricciones de inventario.

Metodología

Los autores proponen un proxy de optimización basado en aprendizaje que reemplaza la llamada al solver por época con una única pasada hacia adelante (forward pass) de una red neuronal, seguida de un decodificador que garantiza la factibilidad.

1. Arquitectura: Red Neuronal Jerárquica con Inserción de Escenarios (Scenario-Embedded)
A diferencia de los proxies de optimización previos que dependen de pronósticos puntuales, este modelo es consciente de los escenarios. Toma como entrada:

• Características Contextuales: Detalles del pedido, estados de inventario de los DC y matrices de costos de transporte.
• Conjuntos de Escenarios: Realizaciones muestreadas de la demanda futura y desviaciones en los tiempos de entrega, generadas por pronosticadores ajustados (RNN de cuantiles de horizonte múltiple para la demanda, MLP de cuantiles múltiples para los tiempos de entrega).

La red emplea un codificador de estilo DeepSets para procesar conjuntos de escenarios no ordenados, promediando las inserciones (embeddings) para aproximar la estructura de expectativa del objetivo C-SAA. La arquitectura es jerárquica:

• Cabeza de DC: Predice un logit para cada centro de distribución.
• Cabeza de Transportista: Predice un logit para cada servicio de transporte condicionado al DC seleccionado.
  Esta factorización ($p(j) \cdot p(k|j)$) reduce la complejidad de aprender el espacio completo de asignación conjunta.

2. Estrategia de Entrenamiento: Función de Pérdida Compuesta
El proxy se entrena offline sobre etiquetas generadas por el solver C-SAA. El objetivo de entrenamiento combina tres términos:

• Imitación de Etiquetas (Pérdida de Selección): Pérdida de entropía cruzada contra las elecciones principales de DC y transportista derivadas de la solución C-SAA.
• Penalización por Violación de Restricciones: Un término autosupervisado utilizando Gumbel-Softmax de paso directo (Straight-Through) para penalizar asignaciones que exceden el inventario disponible, asegurando que el modelo aprenda a respetar las restricciones estrictas.
• Alineación de Costos: Un regularizador autosupervisado que atrae la masa de probabilidad hacia pares (DC, transportista) de bajo costo basados en los costos inmediatos observados en los escenarios muestreados.

3. Inferencia: Decodificación Ponderada por Inventario
En tiempo de ejecución, la red neuronal produce logits que se convierten en probabilidades. Un decodificador dedicado garantiza entonces la factibilidad:

• Repondera las probabilidades predichas mediante la cobertura de inventario fraccional ($\min\{Inv/q, 1\}$) de cada DC.
• Realiza un escaneo codicioso (greedy scan) de los DC y transportistas elegibles, asignando la demanda hasta que el pedido se cumple o el inventario se agota.
• Este proceso asegura que la decisión final sea estrictamente factible (respetando los topes de inventario y la satisfacción de la demanda) en un tiempo de $O(|J| \log |J| + |J||K|)$.

Contribuciones Clave

El artículo realiza cuatro contribuciones principales:

1. Proxy Condicionado por Escenarios: Una arquitectura novedosa que se condiciona explícitamente en conjuntos de escenarios muestreados en lugar de pronósticos puntuales, capturando tanto los costos estocásticos inmediatos como el impacto secuencial del consumo de recursos.
2. Modelo de Cumplimiento Secuencial: Una formulación estocástica contextual de dos etapas que vincula explícitamente las asignaciones inmediatas de pedidos con el costo de oportunidad del consumo de inventario para pedidos futuros.
3. Garantías Teóricas: Los autores demuestran que el decodificador ponderado por inventario produce una decisión factible con una complejidad de tiempo logarítmica-lineal. Además, establecen que el costo esperado del proxy constituye un límite superior del objetivo de dos etapas óptimo y que su rendimiento fuera de la muestra admite estimadores insesgados y consistentes.
4. Validación Empírica: Un estudio computacional exhaustivo utilizando un simulador calibrado con registros transaccionales de JD.com y datos de transportistas propios.

Resultados

En el simulador calibrado, el proxy propuesto demuestra mejoras significativas tanto sobre las líneas base basadas en solvers como sobre las políticas heurísticas establecidas:

• Latencia: La latencia de decisión se reduce aproximadamente 2,800 veces en comparación con la referencia C-SAA de muestra finita online, permitiendo respuestas de sub-segundo.
• Eficiencia de Costos: El proxy mejora los costos de cumplimiento realizados en un 3.3% respecto a la línea base C-SAA (que ya es de alta calidad pero lenta) y reduce los costos totales realizados en al menos un 10.7% en comparación con las políticas de cumplimiento establecidas.
• Nivel de Servicio: El proxy prácticamente reduce a la mitad la tasa de entrega tardía de las líneas base clásicas más fuertes, mejorando directamente la métrica de entrega a tiempo que impulsa la satisfacción del cliente.

Significado

El artículo argumenta que, para operaciones de alto volumen y latencia crítica como el cumplimiento de pedidos en el comercio electrónico, la relación entre la calidad de la optimización y la velocidad computacional es un cuello de botella crítico. Al desarrollar un proxy que aprende de las etiquetas generadas por el solver mientras modela explícitamente la incertidumbre a través de escenarios, los autores demuestran que es posible lograr una calidad de decisión casi óptima con velocidades de inferencia en tiempo real. Este enfoque cierra la brecha entre los beneficios teóricos de la optimización estocástica contextual y las restricciones prácticas de los sistemas de toma de decisiones en tiempo real a escala industrial. El trabajo sugiere que tales proxies pueden ser una alternativa viable a las heurísticas en entornos donde los solvers tradicionales son demasiado lentos para ser desplegados online.