Resumen Técnico: Avance en la Simulación de Compartición de Viajes Dinámica – Un Despachador Altamente Escalable

1. Declaración del Problema

La compartición dinámica de viajes busca mejorar la eficiencia de los recursos en el transporte mediante la coincidencia de viajeros con itinerarios similares en vehículos compartidos, ofreciendo un punto medio entre la flexibilidad de los automóviles privados y la eficiencia del transporte público. Aunque se considera un componente central de los futuros sistemas de transporte autónomo, la investigación existente a menudo se ve limitada por la escalabilidad del despachador—el algoritmo responsable de asignar viajeros a vehículos en tiempo real.

Las limitaciones actuales incluyen:

• Escalabilidad: La mayoría de los despachadores no pueden manejar millones de solicitudes por hora ni flotas de decenas de miles de vehículos, lo que restringe los estudios a áreas urbanas pequeñas o tamaños de flota reducidos.
• Suposiciones Estáticas: Muchos modelos asumen tiempos de viaje estáticos o conocimiento previo de todas las solicitudes futuras, fallando en capturar la verdadera naturaleza dinámica del problema.
• Alcance del Servicio: Muchos estudios ignoran el contexto de transporte más amplio (por ejemplo, la elección de modo entre caminar, conducir y transporte público) y carecen de características como puntos de encuentro optimizados, asumiendo a menudo un servicio rígido de puerta a puerta.
• Rendimiento Periférico: La calidad del servicio y la eficiencia a menudo se degradan significativamente en áreas de baja densidad o periféricas.

2. Metodología

Los autores introducen Mt-KaRRi (Compartición Rápida de Viajes de Karlsruhe Multihilo), un despachador novedoso diseñado para procesar millones de viajeros por hora. La metodología integra varias técnicas algorítmicas avanzadas y componentes de simulación:

2.1 Algoritmo Central de Despacho

El sistema se basa en el despachador KaRRi, que utiliza algoritmos de estado del arte para rutas más cortas para calcular inserciones sobre la marcha.

• Optimización de Rutas Más Cortas: El sistema emplea Jerarquías de Contracción (CH) y Jerarquías de Contracción de Cubetas (BCH) para calcular eficientemente rutas más cortas de uno a muchos y de muchos a muchos.
• Poda Elíptica: Para manejar la carga computacional de las solicitudes dinámicas, el algoritmo utiliza "poda elíptica" para restringir el espacio de búsqueda de desvíos basándose en las restricciones existentes de los viajeros, reduciendo significativamente el uso de memoria y el tiempo de consulta.
• Puntos de Encuentro: A diferencia de los modelos tradicionales de puerta a puerta, Mt-KaRRi incorpora puntos de encuentro. Los viajeros pueden caminar distancias cortas hasta los lugares de recogida/descarga. Esto se modela utilizando una red peatonal separada ($G_{psg}$) y permite desvíos de vehículos más pequeños, particularmente en áreas con límites de velocidad bajos o cuadrículas de calles complejas.
• Función de Costo: El despachador minimiza una función de costo lineal que combina el tiempo de operación del vehículo, el tiempo del viaje del viajero y el tiempo de caminata, sujeto a restricciones de capacidad, intervalos de servicio, tiempos de espera máximos y desvíos máximos en el tiempo del viaje.

2.2 Marco de Simulación

• Modelo de Elección de Modo: La simulación va más allá de la asignación simple integrando un modelo de elección discreta (modelo logit). Los viajeros eligen entre compartición de viajes, automóviles privados, caminar y transporte público basándose en puntuaciones de utilidad derivadas del tiempo de viaje, tiempo de espera y tiempos de acceso/egreso. Esto permite que el sistema modele una demanda realista donde los viajeros pueden rechazar ofertas de compartición de viajes si la calidad del servicio se degrada.
• Paralelización (Mt-KaRRi): Para lograr escalabilidad, los autores paralelizan el despachador. Las solicitudes se agrupan en lotes (intervalos de tiempo fijos, por ejemplo, 5 segundos). Dentro de un lote, múltiples hilos de trabajo calculan las mejores inserciones para las solicitudes en paralelo.
• Resolución de Conflictos: Dado que los hilos paralelos pueden proponer inserciones para el mismo vehículo, se utiliza un mecanismo de resolución de conflictos iterativa. Las solicitudes conflictivas se resuelven secuencialmente dentro del lote, actualizando el estado de la ruta y volviendo a calcular las inserciones para las solicitudes pospuestas hasta que se resuelvan todos los conflictos.

2.3 Configuración Experimental

Los autores generaron instancias de problemas realistas utilizando datos de demanda de Karlsruhe y Stuttgart (Alemania) y Los Ángeles (EE. UU.), derivados de simulaciones basadas en agentes (mobiTopp y MATSim).

• Escala: Los experimentos variaron desde miles hasta más de 25 millones de viajes de viajeros y flotas de hasta 500,000 vehículos.
• Geografía: El estudio distinguió entre áreas urbanas y rurales (periféricas) utilizando la tipología RegioStaR-2 para analizar las diferencias de rendimiento.

3. Contribuciones Clave

1. Despachador Escalable: Presentación del primer despachador de compartición dinámica de viajes capaz de manejar millones de solicitudes por hora y decenas de miles de vehículos, representando instancias de problemas un orden de magnitud más grandes que el trabajo anterior.
2. Estrategia de Paralelización: Desarrollo de Mt-KaRRi, una variante multihilo que logra aceleraciones significativas (hasta ~37x en 96 núcleos para instancias grandes) mientras mantiene la calidad de la solución mediante el procesamiento por lotes y la resolución de conflictos.
3. Integración de la Elección de Modo: Combinación del despachador con un modelo realista de elección de modo, permitiendo la evaluación de la compartición de viajes como parte de un sistema de transporte multimodal en lugar de un silo aislado.
4. Modelado de Puntos de Encuentro: Implementación de un modelo detallado de puntos de encuentro que tiene en cuenta las velocidades y distancias de caminata específicas del viajero, demostrando su impacto en la eficiencia del sistema.
5. Análisis Empírico a Gran Escala: Realización de simulaciones extensas para analizar los efectos del tamaño de la flota, la densidad de la base de clientes, los puntos de encuentro y los contextos urbanos versus rurales en la calidad del viaje y el uso de recursos.

4. Resultados Experimentales

Los autores realizaron experimentos extensos para evaluar el rendimiento y la calidad de la solución:

• Escalabilidad: Mt-KaRRi demostró una fuerte escalabilidad débil. Para la instancia más grande (Los Ángeles, 100% de la población, 25 millones de viajes), el sistema logró una aceleración de 36.89x sobre la versión secuencial utilizando 96 hilos, con un tiempo de respuesta promedio de **1.84 ms por solicitud**.
• Impacto de la Base de Clientes:
  • Las bases de clientes más grandes aumentaron el número total de viajeros y el potencial de compartición (mayor ocupación y compañeros de viaje).
  • Sin embargo, si el tamaño de la flota era fijo y pequeño en relación con la demanda, la calidad del viaje (tiempos de espera, desvíos) se deterioró significativamente.
  • La efectividad del sistema (tiempo de vehículo ahorrado en comparación con los automóviles privados) mejoró con bases de clientes más grandes, alcanzando hasta 1.57x de eficiencia para flotas grandes.
• Puntos de Encuentro: El uso de puntos de encuentro mejoró significativamente el rendimiento del sistema:
  • Redujo los tiempos de espera promedio en 4+ minutos en escenarios de alta demanda.
  • Redujo los tiempos totales de viaje en 8–11%.
  • Aumentó el número promedio de compañeros de viaje y la efectividad del sistema.
• Tamaño de la Flota y Capacidad:
  • El aumento del tamaño de la flota mejoró la calidad del viaje (menores desvíos y tiempos de espera), pero eventualmente produjo rendimientos decrecientes en la cuota modal.
  • Las flotas más pequeñas requirieron niveles de compartición más altos (mayor ocupación) para mantenerse efectivas, mientras que las flotas más grandes operaban más como taxis individuales con tasas de compartición más bajas.
• Urbano vs. Periferia:
  • La compartición de viajes fue más atractiva en corredores urbano-rurales y rural-urbanos, donde redujo la cuota modal del automóvil privado de ~66% a <45%.
  • Aunque los viajes periféricos tuvieron desvíos ligeramente más largos debido a las mayores distancias, la distribución de los tiempos de espera y los desvíos permaneció relativamente justa entre las categorías urbanas y rurales.

5. Significado y Afirmaciones

El artículo posiciona a Mt-KaRRi como una herramienta fundamental para futuras investigaciones sobre compartición de viajes a gran escala. Su significado principal radica en permitir una escala sin precedentes en estudios de simulación, permitiendo a los investigadores:

• Analizar el comportamiento de los sistemas de compartición de viajes con decenas de miles de vehículos y millones de viajeros, lo cual era computacionalmente inviable anteriormente.
• Estudiar la interacción entre la compartición de viajes y otros modos de transporte (caminar, transporte público, automóviles privados) en un entorno dinámico y realista.
• Investigar los desafíos específicos de las áreas periféricas y los beneficios de los puntos de encuentro para reducir el estrés operativo en las flotas.

Los autores concluyen que, aunque las bases de clientes más grandes mejoran la efectividad del sistema, pueden degradar la calidad del viaje si la capacidad de la flota es insuficiente. Sugieren que el uso de puntos de encuentro es una palanca crítica para mantener la calidad del servicio bajo alta demanda. El artículo no afirma resolver todos los desafíos de la compartición de viajes, sino que proporciona un motor escalable para explorarlos, señalando que el trabajo futuro podría involucrar un acoplamiento más estrecho con simulaciones de tráfico, actualizaciones dinámicas de los tiempos de viaje y enrutamiento multimodal más sofisticado.