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

Resumo Técnico: Proxies de Aprendizado para Programas Estocásticos Contextuais Sequenciais

Formulação do Problema

O artigo aborda o desafio dos programas estocásticos contextuais sequenciais em sistemas de decisão em tempo real, focando especificamente no atendimento de pedidos omnichannel em larga escala no comércio eletrônico. Neste cenário, um tomador de decisão deve atribuir pedidos que chegam a centros de distribuição (CDs) e serviços de transportadoras sob incerteza em relação aos tempos de entrega e à demanda futura.

A dificuldade central reside na restrição de latência: embora decisões de alta qualidade possam ser geradas offline usando Aproximação de Média Amostral Contextual (C-SAA) resolvida por solvers de otimização comerciais, esses solvers tipicamente exigem segundos ou minutos por instância. Isso é insuficiente para períodos operacionais de pico (ex: vendas de feriados), onde são necessárias respostas de sub-segundo para lidar com centenas de pedidos por minuto. Consequentemente, sistemas operacionais frequentemente recorrem a heurísticas mais simples que ignoram a incerteza modelada, levando a custos e níveis de serviço subótimos.

O problema é formalizado como um programa estocástico contextual de dois estágios:

1. Primeiro Estágio: Atribuição imediata dos produtos de um pedido aos CDs e transportadoras com base no contexto atual (atributos do pedido, níveis de inventário, custos de transportadora) e em cenários amostrados de incerteza futura.
2. Segundo Estágio: Recurso agregado para pedidos futuros ($t+1 \dots T$), representando o custo esperado de envio e de falta de estoque (stockout) dado o consumo de inventário pela decisão do primeiro estágio.

O objetivo é minimizar os custos totais esperados, incluindo envio, penalidades assimétricas de tempo de entrega (atraso vs. antecipação), descontos de consolidação e penalidades por falta de estoque, respeitando as restrições de inventário.

Metodologia

Os autores propõem um proxy de otimização baseado em aprendizado que substitui a chamada do solver por época por uma única passagem direta (forward pass) de uma rede neural, seguida por um decodificador de imposição de viabilidade.

1. Arquitetura: Rede Neural Hierárquica com Incorporação de Cenários
Diferente de proxies de otimização anteriores que dependem de previsões pontuais, este modelo é consciente de cenários (scenario-aware). Ele recebe como entrada:

• Características Contextuais: Detalhes do pedido, estados de inventário dos CDs e matrizes de custos de transportadoras.
• Conjuntos de Cenários: Realizações amostradas de demandas futuras e desvios nos tempos de entrega, geradas por previsores ajustados (RNN de Quantil de Horizonte Múltiplo para demanda, MLP de Quantil Múltiplo para tempos de entrega).

A rede utiliza um codificador do tipo DeepSets para processar conjuntos de cenários não ordenados, calculando a média das incorporações (embeddings) para aproximar a estrutura de expectativa da função objetivo C-SAA. A arquitetura é hierárquica:

• Cabeça de CD (DC Head): Prediz um logit para cada centro de distribuição.
• Cabeça de Transportadora (Carrier Head): Prediz um logit para cada serviço de transportadora condicional ao CD selecionado.
  Essa fatoração ($p(j) \cdot p(k|j)$) reduz a complexidade de aprender o espaço completo de atribuição conjunta.

2. Estratégia de Treinamento: Função de Perda Composta
O proxy é treinado offline em rótulos (labels) gerados pelo solver C-SAA. O objetivo de treinamento combina três termos:

• Imitação de Rótulo (Perda de Seleção): Perda de entropia cruzada contra as principais escolhas de CD e transportadora derivadas da solução C-SAAs.
• Penalidade de Violação de Restrição: Um termo autossupervisionado usando Straight-Through Gumbel-Softmax para penalizar atribuições que excedam o inventário disponível, garantindo que o modelo aprenda a respeitar restrições rígidas (hard constraints).
• Alinhamento de Custo: Um regularizador autossupervisionado que atrai a massa de probabilidade para pares (CD, transportadora) de baixo custo com base nos custos imediatos observados nos cenários amostrados.

3. Inferência: Decodificação Ponderada pelo Inventário
Em tempo de execução, a rede neural produz logits que são convertidos em probabilidades. Um decodificador dedicado então impõe a viabilidade:

• Ele repondera as probabilidades previstas pela cobertura fracionária de inventário ($min\{Inv/q, 1\}$) de cada CD.
• Realiza uma varredura gananciosa (greedy scan) de CDs e transportadoras elegíveis, atribuindo a demanda até que o pedido seja atendido ou o inventário se esgote.
• Este processo garante que a decisão final seja estritamente viável (respeitando limites de inventário e satisfação da demanda) em tempo $O(|J| \log |J| + |J||K|)$.

Principais Contribuições

O artigo apresenta quatro contribuições primárias:

1. Proxy Condicionado a Cenários: Uma arquitetura inovadora que condiciona explicitamente em conjuntos de cenários amostrados em vez de previsões pontuais, capturando tanto os custos estocásticos imediatos quanto o impacto sequencial do consumo de recursos.
2. Modelo de Atendimento Sequencial: Uma formulação estocástica contextual de dois estágios que vincula explicitamente as atribuições imediatas de pedidos ao custo de oportunidade do consumo de inventário para pedidos futuros.
3. Garantias Teóricas: Os autores provam que o decodificador ponderado pelo inventário produz uma decisão viável com complexidade de tempo logarítmica-linear. Eles estabelecem ainda que o custo esperado do proxy limita superiormente o objetivo ótimo de dois estágios e que seu desempenho fora da amostra admite estimadores não viesados e consistentes.
4. Validação Empírica: Um estudo computacional abrangente utilizando um simulador calibrado com registros transacionais da JD.com e dados proprietários de transportadoras.

Resultados

No simulador calibrado, o proxy proposto demonstra melhorias significativas em relação tanto aos baselines baseados em solver quanto às políticas heurísticas estabelecidas:

• Latência: A latência de decisão foi reduzida em aproximadamente 2.800× em comparação com a referência C-SAA de amostra finita online, permitindo respostas de sub-segundo.
• Eficiência de Custo: O proxy melhora os custos de atendimento realizados em 3,3% em relação ao baseline C-SAA (que já é de alta qualidade, porém lento) e reduz os custos totais realizados em pelo menos 10,7% comparado às políticas de atendimento estabelecidas.
• Nível de Serviço: O proxy reduz aproximadamente pela metade a taxa de atraso na entrega dos baselines clássicos mais fortes, melhorando diretamente a métrica de entrega no prazo que impulsiona a satisfação do cliente.

Significância

O artigo argumenta que, para operações de alto volume e latência crítica, como o atendimento de e-commerce, o compromisso entre qualidade de otimização e velocidade computacional é um gargalo crítico. Ao desenvolver um proxy que aprende com rótulos gerados por solvers enquanto modela explicitamente a incerteza através de cenários, os autores demonstram que é possível alcançar qualidade de decisão próxima da ótima com velocidades de inferência em tempo real. Esta abordagem preenche a lacuna entre os benefícios teóricos da otimização estocástica contextual e as restrições práticas de sistemas de tomada de decisão em tempo real de escala industrial. O trabalho sugere que tais proxies podem ser uma alternativa viável às heurísticas em configurações onde os solvers tradicionais são lentos demais para serem implantados online.