A two-stage stochastic optimization model for synchronized two-echelon routing problems

Resumen Técnico: Un Modelo de Optimización Estocástica de Dos Etapas para Problemas de Rutas Sincronizadas de Dos Eslabones

Definición del Problema
Este estudio aborda la complejidad de la incertidumbre dentro de la logística urbana, centrándose específicamente en los sistemas Integrados de Transporte Terrestre y Acuático (IWLT, por sus siglas en inglés). El problema central es el Problema de Rutas de Vehículos de Múltiples Viajes con Sincronización de Satélites de Dos Eslabones (2E-MVRP-SS). En este sistema, los Vehículos de Carga Eléctricos Ligeros (LEFVs) operan en el primer eslabón (calles) para recolectar mercancías de los clientes y transferirlas a embarcaciones (segundo eslabón) en nodos satélite. El sistema opera sin opciones de almacenamiento en los satélites, lo que requiere una estricta sincronización espaciotemporal entre los LEFVs y las embarcaciones.

El desafío principal abordado es la propagación de retrasos causados por tiempos de espera de transbordo inciertos en los satélites. Estas incertidumbres, derivadas de factores regionales como la congestión del tráfico o variaciones operativas, pueden interrumpir las operaciones sincronizadas, provocando retrasos en la atención al cliente, mayores costos operativos y reducción de la fiabilidad. El estudio se dirige específicamente a escenarios de logística inversa (por ejemplo, recolección de residuos, devoluciones) donde la puntualidad del servicio es crítica para minimizar los costos de inventario y las molestias al cliente.

Metodología
Los autores proponen un marco de optimización estocástica de dos etapas con un problema de recurrencia de enteros mixtos para gestionar estas incertidumbres.

1. Formulación de Dos Etapas:

   • Primera Etapa (Problema Maestro): Las decisiones se toman con respecto a las rutas de los LEFVs y la asignación de tareas de transferencia a los satélites antes de la realización de los retrasos. Esta etapa prioriza los tiempos de servicio fiables para las recolecciones. El modelo asume que los LEFVs visitan el satélite más cercano como una aproximación inicial.
   • Segunda Etapa (Recurrencia/Subproblema): Una vez que se materializan escenarios específicos de retraso, se toman acciones correctivas. Esto implica reasignar las operaciones de transbordo a diferentes satélites y re-optimizar las rutas de las embarcaciones para mitigar el impacto de los retrasos. Los programas de los LEFVs para el servicio al cliente permanecen fijos para cumplir con los tiempos prometidos, pero la logística de nivel de agua se re-optimiza.

2. Enfoque Algorítmico:

   • Para manejar la no convexidad de la función de costo de la segunda etapa y la naturaleza de enteros mixtos del problema, los autores emplean un método L-shaped adaptado con cortes de Benders combinatorios.
   • El algoritmo itera entre un problema maestro relajado y subproblemas para cada escenario.
   • Los cortes de factibilidad aseguran que las decisiones de la primera etapa permitan soluciones factibles en la segunda etapa.
   • Los cortes de optimalidad aproximan el costo esperado de la segunda etapa.
   • Se utiliza un enfoque de muestreo basado en escenarios para representar las incertidumbres regionales. Los retrasos en los satélites se modelan como variables con distribución normal, discretizadas en un conjunto finito de escenarios ($N$) para asegurar la tractabilidad computacional manteniendo la estabilidad.

3. Configuración Experimental:

   • El modelo fue probado en pequeñas instancias de red (10 nodos de recolección, 4 satélites) derivadas de instancias modificadas de Solomon VRPTW.
   • Se compararon dos diseños de sistema: 2E-Flexible (las embarcaciones actúan como depósitos móviles, sincronizadas con los LEFVs) y 2E-Stationary (ubicaciones de embarcaciones fijas).
   • El desempeño se evaluó contra una línea base determinista (sin retrasos) y un enfoque estocástico de dos etapas.

Contribuciones Clave

• Modelado Novedoso de Sincronización: Este es el primer estudio que aborda los impactos de los retrasos en los satélites sobre la sincronización de vehículos en un sistema de dos eslabones con capacidad de almacenamiento nula, un escenario que requiere una alta coordinación espaciotemporal.
• Marco de Recurrencia Estocástica: El artículo propone un modelo de programación estocástica de dos etapas con recurrencia de enteros mixtos específicamente para 2E-MVRP-SS. Utiliza cortes de Benders combinatorios dentro de un método de enumeración para manejar la no convexidad de la segunda etapa.
• Análisis Comparativo de Flexibilidad: El estudio proporciona una comparación cuantitativa entre sistemas de transporte flexibles (embarcaciones móviles) y sistemas estacionarios bajo incertidumbre, demostrando el valor de la flexibilidad para mitigar la propagación de retrasos.

Resultos

• Reducción de Costos: El modelo de programación estocástica propuesto redujo los costos totales esperados en un 37% en todas las instancias en comparación con un enfoque determinista que asume la ausencia de retrasos.
• Estabilidad de Escenarios: El enfoque de generación de escenarios demostró estabilidad; la varianza de los escenarios dentro de la muestra disminuyó a medida que aumentaba el número de escenarios, estabilizándose alrededor de los 30 escenarios.
• Impacto de la Topología de la Red:
  • Para redes de demanda Agrupada (C), el sistema integrado mantuvo la eficiencia con un aumento de costo mínimo (cercano al 0%) bajo incertidumbre.
  • Para redes Aleatorias (R), el enfoque estocástico logró los ahorros más significativos en comparación con las estrategias deterministas, reduciendo los costos esperados hasta en un 43% en instancias específicas al localizar mejor las ubicaciones de recolección sensibles a los retrasos.
• Desempeño del Sistema (Flexible vs. Estacionario):
  • El sistema 2E-Flexible superó significativamente al sistema 2E-Stationary en términos de fiabilidad y cuota modal.
  • Bajo incertidumbre, el sistema estacionario experimentó un aumento agudo en los tiempos de viaje en calle y en la tardanza (por ejemplo, la tardanza aumentó a 26 unidades de tiempo en instancias RC), mientras que el sistema flexible mantuvo la tardanza baja (9 unidades de tiempo) y mantuvo una cuota modal más equilibrada entre el transporte terrestre y el acuático.
  • El sistema flexible mitigó eficazmente el riesgo de aumento en los costos de viaje en calle, demostrando que reubicar las unidades de almacenamiento (o en este caso, puntos de transbordo) no puede igualar el desempeño de los servicios de navegación flexibles en términos de congestión y fiabilidad.

Significancia y Reivindicaciones
El artículo sostiene que incorporar la incertidumbre en la planificación fuera de línea es esencial para la fiabilidad y la rentabilidad de la logística urbana multimodal, particularmente en contextos donde la competencia por el espacio urbano limita las opciones de almacenamiento. El estudio demuestra que los sistemas flexibles, donde las embarcaciones actúan como depósitos móviles sincronizados con los LEFVs, ofrecen una resiliencia superior contra los retrasos de transbordo en comparación con los sistemas de ubicación fija.

Los autores concluyen que, si bien el modelo propuesto es computacionalmente intensivo, las ganancias observadas en pequeñas instancias sugieren que la optimización estocástica puede mejorar significativamente la fiabilidad del servicio y reducir la cuota modal "verde" (uso de la carretera) en la logística urbana. Señalan que el trabajo futuro podría utilizar el marco de enumeración y precios propuesto para desarrollar heurísticas para problemas de gran escala, pero el estudio actual se centra en validar el marco teórico y los beneficios de la flexibilidad en redes pequeñas y resolubles.