A Swarm Approach to Public Transit Using On-demand Routing in a Slime-Mold-Inspired Framework

Resumen Técnico: Un enfoque de enjambre para el transporte público mediante el enrutamiento bajo demanda en un marco inspirado en el moho mucilaginoso

Planteamiento del problema
Los sistemas de transporte de respuesta a la demanda (DRT, por sus siglas en inglés) ofrecen una alternativa flexible al transporte masivo tradicional de rutas fijas, particularmente en comunidades suburbanas y rurales de baja densidad donde las rutas fijas suelen no proporcionar un acceso adecuado. Sin embargo, las implementaciones actuales de DRT frecuentemente sufren de altos costos operativos, baja confiabilidad y altas tasas de falla. Los enfoques de enrutamiento actuales suelen depender de la planificación centralizada utilizando algoritmos de ruta más corta (por ejemplo, basados en Dijkstra) o metaheurísticas (por ejemplo, algoritmos genéticos u optimización de colonias de hormigas). Estos métodos tienen dificultades con la escala y la imprevisibilidad de la demanda en tiempo real, donde las rutas preplanificadas se vuelven rápidamente subóptimas. Además, los sistemas centralizados enfrentan cargas computacionales y de comunicación que resultan inviables para redes grandes bajo un alto uso. El desafío central es diseñar un mecanismo de enrutamiento distribuido y escalable que se adapte dinámicamente a la demanda de los pasajeros, minimice las distancias de caminata y optimice la utilización de los vehículos sin depender del control centralizado.

Metodología
Los autores proponen un novedoso sistema de tránsito distribuido impulsado por el algoritmo RAPID, un método de enrutamiento bioinspirado modelado tras los eficientes comportamientos de búsqueda de rutas del moho mucilaginoso Physarum polycephalum. El sistema opera sin control centralizado, utilizando la comunicación local de la red para crear y mantener gradientes de demanda a través de la red vial.

La metodología se estructura en torno a tres componentes:

1. Mecanismo de licitación (Bidding Mechanism): Cuando un pasajero solicita un viaje, los vehículos candidatos generan ofertas basadas en una función de recompensa. El valor de la oferta ($B_{i,p}$) para que el vehículo $i$ recoja al pasajero $p$ se calcula utilizando el tiempo de espera normalizado, la distancia de la ruta más corta y la carga actual de pasajeros, ponderados por parámetros ajustables ($\alpha, \beta, \gamma, \delta, \sigma, \epsilon$). El vehículo con el valor de oferta máximo es asignado al pasajero.
2. Enrutamiento inspirado en el moho mucilaginoso (RAPID): En lugar de computar rutas fijas, los vehículos navegan basándose en gradientes de demanda locales. Cada nodo en la red mantiene un valor de demanda ($d_{p,n}$) y un valor de referencia ($r_{p,n}$), donde los valores de referencia se establecen en 10 en los puntos de recogida y entrega, y 0 en los demás lugares. La demanda se propaga entre nodos vecinos basándose en parámetros de difusión, relajación e inercia ($\zeta, \eta, \mu$). La demanda acumulada en un nodo se pondera por el tiempo de espera del pasajero. Los vehículos deciden localmente su siguiente movimiento dirigiéndose hacia el nodo adyacente con el valor de demanda más alto, lo que permite que el sistema reaccione en tiempo real a las condiciones cambiantes.
3. Transferencias dinámicas: Para optimizar aún más la eficiencia, el sistema permite que los pasajeros realicen trasbordos entre vehículos si esto reduce su tiempo de viaje esperado. Una transferencia se inicia solo si la mejora acumulada en los valores de oferta para los pasajeros involucrados supera un umbral ($\theta$) y el pasajero no ha excedido un límite máximo de transferencia ($\tau$).

Marco de simulación
Los autores implementaron una simulación basada en agentes utilizando redes de calles del mundo real derivadas de OpenStreetMap para tres entornos distintos: el suburbio de Rutherford, NJ; el entorno urbano de Newark, NJ; y el entorno semi-rural de Wayne, NJ. La simulación compara el sistema basado en RAPID contra un punto de referencia de ruta fija derivado de los datos de NJ Transit.

• Agentes: Pasajeros (rastreando ubicación, destino, transferencias y marcas de tiempo) y Vehículos (rastreando posición y pasajeros asignados).
• Parámetros: Se utilizó un algoritmo genético para optimizar los parámetros de la función de licitación y los umbrales de transferencia, con una función de aptitud (fitness) que equilibra el tiempo medio de entrega y la desviación estándar de los tiempos de entrega.
• Condiciones: Las simulaciones se ejecutaron durante 100 minutos con una flota de 10 vehículos (capacidad de 30 pasajeros cada uno) en el escenario base, con pruebas adicionales variando el tamaño de la flota y la capacidad del vehículo manteniendo una capacidad total constante de 300 pasajeros.

Resultados clave
Los resultados de la simulación indican que el enfoque basado en RAPID supera significativamente al sistema de ruta fija en todos los entornos probados:

• Tasas de entrega de pasajeros: El sistema RAPID aumentó el número de pasajeros entregados en relación con el enfoque de ruta fija en un 28.2% en el suburbio de Rutherford, un 49.0% en el entorno urbano de Newark y un 101.4% en el entorno semi-rural de Wayne.
• Tiempo de caminata: El sistema redujo el tiempo medio de caminata para los pasajeros en más de un 75% en todos los escenarios (85.5% en Rutherford, 84.7% en Newark y 76.8% en Wayne).
• Configuración de la flota: El sistema demostró flexibilidad en la composición de la flota, mostrando que las configuraciones con muchos vehículos más pequeños a menudo resultaban en tiempos de entrega más rápidos en comparación con unos pocos vehículos más grandes, siempre que la capacidad total se mantuviera constante.

Significancia y reclamos
El artículo afirma que el enfoque propuesto basado en RAPID ofrece una solución escalable y descentralizada para las limitaciones de los sistemas DRT actuales. Al imitar la toma de decisiones descentralizada del moho mucilaginoso, el sistema logra una alta eficiencia y confiabilidad sin la carga computacional de la planificación centralizada. Los autores sostienen que este enfoque es particularmente adecuado para entornos rurales y suburbanos donde el transporte de ruta fija suele ser ineficaz.

El trabajo contribuye con:

1. El diseño de un novedoso algoritmo de enrutamiento de transporte público bioinspirado.
2. El desarrollo de un marco de simulación flexible que incorpora datos de redes de calles del mundo real.
3. Evidencia empírica inicial que sugiere que el enrutamiento bajo demanda impulsado por enjambres puede mejorar significativamente el rendimiento del tránsito y la accesibilidad (específicamente al reducir las distancias de caminata) en comparación con las redes tradicionales de ruta fija.

Los autores reconocen limitaciones, incluyendo la ausencia de modelado de congestión de tráfico, el uso de demanda de pasajeros generada aleatoriamente en lugar de patrones de desplazamiento del mundo real, y la falta de un análisis de costos. Señalan que el trabajo futuro se centrará en validar el sistema con simulaciones a mayor escala, incorporando la dinámica del tráfico y evaluando la rentabilidad.