Resumo Técnico: Aceitação de Lances com Sensibilidade à Latência sob Viabilidade Operacional

Definição do Problema

O artigo aborda o problema de aceitação de lances de carga de caminhão online, um desafio de tomada de decisão estocástica de ciclo fechado onde transportadores ou corretores devem aceitar ou rejeitar ofertas de carga em tempo real (dentos de segundos). A decisão é restringida por três fatores:

1. Latência: As decisões devem ser tomadas instantaneamente.
2. Viabilidade Operacional: Uma carga só pode ser aceita se um caminhão puder chegar à coleta, satisfazer as janelas de agendamento, aderir às regulamentações de Horas de Serviço (HOS) e permanecer viável até a entrega, considerando atrasos estocásticos no pátio.
3. Oportunidade Econômica: Aceitar uma carga com margem positiva imediata pode ser subótimo se ela consumir um caminhão escasso necessário para uma futura janela de alto prêmio ou deixar a frota retida em um mercado de baixo valor.

O artigo identifica uma lacuna na literatura existente: enquanto existem benchmarks de roteamento estático (ex: Solomon, CVRPLIB), eles carecem de dinâmicas de ciclo fechado e calibração pública. Por outro lado, estudos de frota dinâmica geralmente dependem de dados privados. Os autores introduzem o FreightBidBench v0.3, um benchmark público, reproduzível e livre de dependências, calibrado contra o U.S. Freight Analysis Framework (FAF) e dados de taxas de caminhão da USDA para resolver isso.

Metodologia

1. Formulação do Benchmark (v0.3)

O problema é formalizado como um Processo de Decisão de Markov (MDP) de horizonte finito com eventos de carimbo de tempo contínuos.

• Estado: Inclui o estado da frota (localização, próximo tempo disponível, orçamentos restantes de direção/serviço de HOS) e a oferta de carga atual (origem, destino, preço, janelas de tempo, atrasos estocásticos no pátio).
• Ação: Decisão binária (Aceitar/Rejeitar).
• Camada de Viabilidade: Um mapa determinístico atribui cargas a caminhões com base em alcançabilidade, janelas de agendamento e restrições de HOS. Se nenhum caminhão puder atender à carga dentro das restrições, a atribuição é inviável.
• Estrutura de Recompensa: O lançamento v0.3 introduz três componentes de recompensa específicos para isolar distintas classes de políticas:
  • L1 (Penalidade de Falha de Serviço): Uma penalidade ($-\rho$) é aplicada se uma política aceitar uma carga inviável. Isso cria um arrependimento linear para políticas cegas à viabilidade.
  • L2 (Valor Terminal da Frota): Uma recompensa terminal baseada na localização dos caminhões ao final do horizonte, ponderada pelo tonelagem de saída e desequilíbrio líquido. Isso penaliza políticas gananciosas que retêm a frota em mercados de baixo valor.
  • L3 (Janela de Prêmio de Preço Temporal): Um prêmio de preço multiplicativo é aplicado durante horas diárias específicas. Isso cria um problema de tempo onde aceitar cargas fora do pico pode impedir a captura de prêmios de horário de pico.

2. Tetos de Histórico (Hindsight Ceilings) (Limites Superiores)

Para avaliar o desempenho da política sem depender apenas de um professor de rollout, o artigo propõe três tetos complementares:

• DP de Pequeno Prefixo Exato: Um programa dinâmico exato para pequenos prefixos de carga (até $L=16$) usando busca com memoização. Serve como uma referência confiável para instâncias pequenas.
• Relaxação Estilo LP: Um limite superior de horizonte completo que relaxa integridade, sequenciamento e restrições de localização, permitindo horas de caminhão fracionárias e ignorando a continuidade espacial.
• Relaxação de Informação de Lagrange por Caminhão: Um limite mais apertado que dualiza apenas a restrição de atribuição entre caminhões, mantendo as estruturas de HOS, localização e sequenciamento por caminhão. Isso é justificado como uma relaxação de informação (Brown et al., 2010) e é significativamente mais apertado que a relaxação LP.

3. Classes de Política

O artigo avalia uma hierarquia de políticas:

• Baselines: Rejeitar tudo, Aceitar tudo o que é viável, Margem míope, e Preço de lance (Bid price).
• Surrogate (Substituto): Um substitente linear livre de dependências (regressão ridge) treinado em rótulos de professor de rollout, apresentando atributos de carga, estado da frota, sondagens de viabilidade e características temporais.
• Rollout Teacher (Professor de Rollout): Uma expansão de Monte Carlo de olhar à frente finito usando números aleatórios comuns para estimar o valor esperado dos ramos de aceitar/rejeitar.
• Cascata de Substitutos-Rollout (Surrogate-Rollout Cascade): Uma política paramétrica que usa o substituto para a maioria das decisões, mas escala para o caro professor de rollout sob dois gatilhos:
  1. Banda de Fronteira ($\beta$): Quando o escore assinado do substituto está próximo de zero (incerteza).
  2. Limiar de Escassez ($\kappa$): Quando o mercado de origem possui poucos caminhões imediatamente disponíveis (decisões de capacidade de alto risco).

Principais Resultados

1. Calibração e Ablação de Camadas

Experimentos confirmam que as três camadas de recompensa separam com sucesso as classes de política:

• L1: Uma penalidade de \rho = \10$ faz com que políticas cegas à viabilidade (margem míope, preço de lance) tenham um desempenho inferior às baselines gananciosas conscientes da viabilidade em aproximadamente \3,1k$–$\$3,7k$.
• L2: Um peso de valor terminal de $\omega = 0,25$ reduz a retenção da política "Aceitar tudo o que é viável" para cerca de 90% do lucro do professor de rollout, demonstrando que a viabilidade míope é insuficiente.
• L3: Uma amplitude de prêmio de preço de 0,5 amplia a lacuna entre a melhor política simples e o professor de rollout para cerca de 11–14 pontos percentuais, criando espaço para métodos focados no futuro.

2. Desempenho da Política

Em cenários "apertados" (tight) e "escassos" (scarce) (avaliação de 10 sementes):

• Baselines Simples: Retêm 86,5%–91,0% do lucro do rollout.
• Substituto Linear: Retém 89,3%–94,2% do lucro do rollout, superando as baselines simples, mas deixando valor considerável na mesa.
• Cascata: Uma cascata com uma única banda de escalonamento (\beta = \500$) e limiar de escassez ($\kappa = 2$) recupera 98,0%–98,2% do lucro do rollout.
  • Em cenários "apertados", a cascata é estatisticamente indistinguível do professor de rollout (o IC de 95% abrange o zero).
  • Latência: A cascata opera a 40%–56% da latência média de decisão do professor de rollout (ex: ~12,95ms vs 32,11ms em cenários apertados).

3. Diagnósticos de Histórico (Hindsight)

• O limite de Lagrange por caminhão é 20,7% mais apertado (cenário apertado) e 39,3% mais apertado (cenário escasso) do que a relaxação estilo LP.
• A retenção do rollout contra o limite de Lagrange é de 67,6% (apertado) e 65,7% (escasso), sugerindo que a lacuna restante deve-se à coordenação entre caminhões, e não a erros de pontuação de caminhão individual.

Significância e Alegações

O artigo reivindica as seguintes contribuições e percepções:

1. Benchmark Reproduzível: O FreightBidBench v0.3 fornece o primeiro benchmark público, versionado e livre de dependências para aceitação de lances de carga de caminhão online que modela explicitamente a viabilidade operacional e os compromissos econômicos.
2. Separação Estrutural: Os três componentes de recompensa (L1, L2, L3) isolam matematicamente e empiricamente distintos modos de falha (cegueira de viabilidade, miopia de posicionamento e cegueira de tempo), garantindo que métodos futuros sejam testados contra desafios estruturais significativos.
3. Espaço de Melhoria Metodológica: Ao tornar o limite superior mais apertado via relaxação de Lagrange, o artigo demonstra que o "espaço de melhoria" é menor do que as relaxações LP sugerem. A lacuna restante reside na coordenação entre caminhões (decisão conjunta de olhar à frente) em vez de erros de pontuação de um único pedido.
4. Eficiência da Cascata: A cascata de substituto-rollout é apresentada como a moldura ideal para a prática. Ela utiliza substitutos baratos para decisões rotineiras enquanto delega decisões de alto risco e incerteza (impulsionadas por escassez ou ambiguidade de escore) ao professor caro, alcançando lucro próximo do ótimo com latência significativamente reduzida.
5. Viabilidade Operacional como Recompensa: O artigo argumenta que a viabilidade deve ser incorporada na função de recompensa (via penalidades) em vez de ser tratada como um diagnóstico lateral, pois ignorá-la acarreta arrependimento linear.

Os autores afirmam explicitamente que o benchmark é o artefato principal; os resultados dos métodos servem como evidência de que o problema refinado admite uma fronteira não trivial de latência-lucro. O lançamento inclui contratos de cenários versionados, conjuntos de políticas e tetos exatos mais relaxados para servir como um ambiente de teste reproduzível para trabalhos futuros.