Resumen Técnico: Aceptación de Ofertas Sensible a la Latencia bajo Viabilidad Operativa

Definición del Problema

El artículo aborda el problema de aceptación de ofertas de carga de camiones en línea, un desafío de toma de decisiones estocásticas de bucle cerrado donde los transportistas o agentes deben aceptar o rechazar ofertas de carga en tiempo real (en cuestión de segundos). La decisión está condicionada por tres factores:

1. Latencia: Las decisiones deben tomarse instantáneamente.
2. Viabilidad Operativa: Una carga solo puede aceptarse si un camión puede llegar al punto de recogida, cumplir con las ventanas de cita, adherirse a las regulaciones de Horas de Servicio (HOS) y permanecer viable hasta la entrega, considerando retrasos estocásticos en el patio.
3. Oportunidad Económica: Aceptar una carga con un margen positivo inmediato puede ser subóptimo si consume un camión escaso necesario para una futura ventana de alta prima o si deja a la flota varada en un mercado de bajo valor.

El artículo identifica una brecha en la literatura existente: mientras que existen referencias estáticas de rutas (p. ej., Solomon, CVRPLIB), estas carecen de la dinámica de bucle cerrado y de una calibración pública. Por el contrario, los estudios de flotas dinámicas suelen depender de datos privados. Los autores introducen FreightBidBench v0.3, un referente público, reproducible y sin dependencias, calibrado contra el Marco de Análisis de Carga (FAF) de EE. UU. y los datos de tarifas de camiones de la USDA para abordar esto.

Metodología

1. Formulación del Referente (v0.3)

El problema se formaliza como un Proceso de Decisión de Markov (MDP) de horizonte finito con eventos de tiempo continuo.

• Estado: Incluye el estado de la flota (ubicación, próximo tiempo disponible, presupuestos restantes de conducción/servicio de HOS) y la oferta de carga actual (origen, destino, precio, ventanas de tiempo, retrasos estocásticos en el patio).
• Acción: Decisión binaria (Aceptar/Rechazar).
• Capa de Viabilidad: Un mapa determinista asigna cargas a camiones basándose en la alcanzabilidad, las ventanas de cita y las restricciones de HOS. Si ningún camión puede servir la carga dentro de las restricciones, la asignación es inviable.
• Estructura de Recompensa: El lanzamiento de la v0.3 introduce tres componentes de recompensa específicos para aislar distintas clases de políticas:
  • L1 (Penalización por Fallo de Servicio): Se aplica una penalización ($-\rho$) si una política acepta una carga inviable. Esto crea un arrepentimiento lineal para las políticas ciegas a la viabilidad.
  • L2 (Valor Terminal de la Flota): Una recompensa terminal basada en la ubicación de los camiones al final del horizonte, ponderada por el tonelaje de salida y el desequilibrio neto. Esto penaliza las políticas ávidas que dejan a los camiones varados en mercados de bajo valor.
  • L3 (Ventana de Prima de Precio Temporal): Se aplica una prima de precio multiplicativa durante horas diarias específicas. Esto crea un problema de temporización donde aceptar cargas fuera de las horas pico puede impedir la captura de primas en horas pico.

2. Techos de Perspectiva (Límites Superiores)

Para evaluar el rendimiento de la política sin depender únicamente de un profesor de despliegue (rollout teacher), el artículo propone tres techos complementarios:

• DP de Prefijo Pequeño Exacto: Un programa dinámico exacto para prefijos de carga pequeños (hasta $L=16$) utilizando búsqueda con memoización. Sirve como una referencia confiable para instancias pequeñas.
• Relajación Estilo LP: Un límite superior de horizonte completo que relaja la integralidad, la secuenciación y las restricciones de ubicación, permitiendo horas-camión fraccionarias e ignorando la continuidad espacial.
• Relajación de Información de Lagrangian-por-Camión: Un límite más ajustado que dualiza únicamente la restricción de asignación entre camiones, manteniendo las estructuras de HOS, ubicación y secuenciación por camión. Esto se justifica como una relajación de información (Brown et al., 2010) y es significativamente más ajustado que la relajación LP.

3. Clases de Política

El artículo evalúa una jerarquía de políticas:

• Líneas Base: Rechazar todo, Aceptar todo lo viable, Margen miope, y Precio de oferta (bid price).
• Sustituto (Surrogate): Un sustituto lineal sin dependencias (regresión de Ridge) entrenado con etiquetas de profesor de despliegue, que presenta atributos de carga, estado de la flota, sondas de viabilidad y características temporales.
• Profesor de Despliegue (Rollout Teacher): Una expansión de Monte Carlo de horizonte finito con números aleatorios comunes para estimar el valor esperado de las ramas de aceptar/rechazar.
• Cascada de Sustituto-Despliegue: Una política paramétrica que utiliza el sustituto para la mayoría de las decisiones pero escala al profesor de despliegue (más costoso) bajo dos disparadores:
  1. Banda de Límite ($\beta$): Cuando el puntaje con signo del sustituto está cerca de cero (incertidumbre).
  2. Umbral de Escasez ($\kappa$): Cuando el mercado de origen tiene pocos camiones disponibles inmediatamente (decisiones de capacidad de alto riesgo).

Resultados Clave

1. Calibración y Ablación de Capas

Los experimentos confirman que las tres capas de recompensa separan con éxito las clases de política:

• L1: Una penalización de \rho = \10$ causa que las políticas ciegas a la viabilidad (margen miope, precio de oferta) rindan aproximadamente entre \3.1k$y$\$3.7k$ menos que las líneas base ávidas conscientes de la viabilidad.
• L2: Un peso de valor terminal de $\omega = 0.25$ reduce la retención de la política "Aceptar todo lo viable" a aproximadamente el 90% del beneficio del profesor de despliegue, demostrando que la viabilidad miope es insuficiente.
• L3: Una amplitud de prima de precio de 0.5 amplía la brecha entre la mejor política simple y el profesor de despliegue a aproximadamente 11–14 puntos porcentuales, creando espacio para métodos con visión de futuro.

2. Rendimiento de la Política

En escenarios "ajustados" (tight) y "escasos" (scarce) (evaluación de 10 semillas):

• Líneas Base Simples: Retienen el 86.5%–91.0% del beneficio del despliegue.
• Sustituto Lineal: Retiene el 89.3%–94.2% del beneficio del despliegue, superando a las líneas base simples pero dejando un valor significativo sin aprovechar.
• Cascada: Una cascada con una sola banda de escalada (\beta = \500$) y un umbral de escasez ($\kappa = 2$) recupera el 98.0%–98.2% del beneficio del despliegue.
  • En escenarios "ajustados", la cascada es estadísticamente indistinguible del profesor de despliegue (el intervalo de confianza del 95% incluye el cero).
  • Latencia: La cascada opera al 40%–56% de la latencia media de decisión del profesor de despliegue (p. ej., ~12.95ms frente a 32.11ms en escenarios ajustados).

3. Diagnósticos de Perspectiva (Hindsight)

• El límite de Lagrangian-por-camión es un 20.7% más ajustado (escenario ajustado) y un 39.3% más ajustado (escenario escaso) que la relajación de estilo LP.
• La retención del despliegue frente al límite de Lagrangian es del 67.6% (ajustado) y 65.7% (escaso), lo que sugiere que la brecha restante se debe a la coordinación entre camiones en lugar de errores de puntuación de un solo camión.

Significado y Reivindicaciones

El artículo reivindica las siguientes contribuciones e ideas:

1. Referente Reproducible: FreightBidBench v0.3 proporciona el primer referente público, versionado y sin dependencias para la aceptación de ofertas de carga de camiones en línea que modela explícitamente la viabilidad operativa y los compromisos económicos.
2. Separación Estructural: Los tres componentes de recompensa (L1, L2, L3) aíslan matemática y empíricamente distintos modos de fallo (ceguera de viabilidad, miopía de posicionamiento y ceguera de tiempo), asegurando que los métodos futuros sean probados contra desafíos estructurales significativos.
3. Espacio de Mejora Metodológica: Al ajustar el límite superior mediante la relajación de Lagrangian, el artículo demuestra que el "espacio" para la mejora es menor de lo que sugieren las relajaciones LP. La brecha restante reside en la coordinación entre camiones (mirada conjunta de decisiones) en lugar de la puntuación de una sola oferta.
4. Eficiencia de la Cascada: La cascada de sustituto-despliegue se presenta como el marco óptimo para la práctica. Aprovecha sustitutos económicos para decisiones rutinarias mientras delega las decisiones de alto riesgo o incertidumbre (impulsadas por la escasez o la ambigüedad de la puntuación) a profesores costosos, logiendo un beneficio casi óptimo con una latencia significativamente reducida.
5. Viabilidad Operativa como Recompensa: El artículo argumenta que la viabilidad debe integrarse en la función de recompensa (mediante penalizaciones) en lugar de tratarse como un diagnóstico secundario, ya que ignorarla incurre en un arrepentimiento lineal.

Los autores declaran explícitamente que el referente es el artefacto principal; los resultados de los métodos sirven como evidencia de que el problema refinado admite una frontera no trivial de latencia-beneficio. El lanzamiento incluye contratos de escenarios versionados, conjuntos de políticas y techos exactos más relajados para servir como un banco de pruebas reproducible para trabajos futuros.