Resumen Técnico: AlphaTransit

Formulación del Problema

El artículo aborda el Problema de Diseño de Red de Rutas de Tránsito (TRNDP), un desafío de optimización combinatoria donde un planificador debe diseñar un conjunto de rutas de autobús superpuestas en una red vial compartida para atender flujos de pasajeros de muchos a muchos bajo restricciones operativas (por ejemplo, tamaño de la flota, costos). A diferencia de los problemas de enrutamiento clásicos (por ejemplo, el Viajante de Comercio), el TRNDP implica interacciones complejas donde cambiar una ruta puede reasignar pasajeros en toda la red, alterando el valor de segmentos distantes.

Los desafíos clave identificados incluyen:

• Retroalimentación Retardada y No Local: La calidad de una extensión de ruta solo es visible después de que la red completa se ensambla y simula. Las decisiones locales que parecen beneficiosas pueden crear cuellos de botella en las transferencias, superposiciones redundantes o reducir el rendimiento global.
• Recompensas Escasas: La señal de recompensa se retrasa hasta el final del episodio, lo que dificulta la asignación de créditos para el aprendizaje por refuerzo (RL) estándar.
• Paisaje Engañoso: El paisaje de optimización es engañoso; una extensión localmente atractiva puede degradar el rendimiento general del sistema.
• Escala: El espacio de búsqueda es astronómicamente grande (estimado en $\approx 10^{82}$ conjuntos de rutas candidatas para el punto de referencia de Bloomington), lo que hace inviable la búsqueda exhaustiva.

Metodología: AlphaTransit

Los autores proponen AlphaTransit, un marco de planificación basado en búsqueda que acopla la Búsqueda de Árbol Monte Carlo (MCTS) con una red neuronal de política-valor. La filosofía central es utilizar priores aprendidos para guiar la búsqueda, extrayendo así señales de entrenamiento más fuertes de entornos de recompensa escasa que el aprendizaje de políticas por sí solo.

1. Planteamiento del Problema

La construcción de rutas se modela como un Proceso de Decisión de Markov (MDP) de horizonte finito:

• Estado ($s_t$): Codifica el grafo vial, las rutas completadas, la ruta parcial actual y el nodo frontera. Las características incluyen atributos espaciales, agregados de demanda Origen-Destino (OD) y pertenencia a rutas.
• Acción ($a_t$): Seleccionar el siguiente nodo para agregar a la ruta actual. Las acciones se restringen a vecinos válidos de un salto no visitados aún en la ruta actual (impuestos mediante enmascaramiento de acciones inválidas).
• Recompensa Terminal: Evaluada solo después de que se construyen $K$ rutas. La función de recompensa equilibra las métricas de pasajeros (cobertura, tiempo de espera, tiempo de viaje) y las métricas del operador (tamaño de la flota, superposición de rutas, utilización de autobuses) utilizando un simulador de tráfico mesoscópico (UXsim).

2. Arquitectura Neuronal

AlphaTransit utiliza una columna vertebral compartida de Red de Atención en Grafos (GATv2):

• Entrada: Características de nodos (geometría, demanda, estado) y características de aristas (longitud, velocidad de flujo libre).
• Columna Vertebral: Una pila de bloques GATv2 con agregación de Conocimiento Saltador para capturar campos receptivos de múltiples saltos.
• Cabezas:
  • Actor (Política): Produce priores de acción $P_\theta(a|s)$ para la selección de MCTS.
  • Crítico (Valor): Estima la calidad de diseño aguas abajo $V_\theta(s)$ para evaluar nodos hoja sin simulaciones de rodaje.

3. Aprendizaje por Refuerzo Guiado por Búsqueda

A diferencia del RL de extremo a extremo que actúa de manera codiciosa o mediante muestreo sin visión de futuro, AlphaTransit realiza MCTS en cada paso de decisión:

• Selección: Utiliza la regla PUCT para equilibrar la explotación de acciones de alto valor y la exploración, guiada por los priores de política neuronal.
• Expansión y Evaluación: Los nodos hoja son evaluados por la cabeza de valor neuronal $V_\theta$, evitando simulaciones de rodaje costosas dentro del árbol de búsqueda.
• Retropropagación: Las estadísticas (conteos de visitas, valores) se actualizan hacia arriba en el árbol.
• Entrenamiento: La red se entrena para imitar la política derivada de MCTS (destilando conteos de visitas) y para predecir la recompensa terminal normalizada. Esto crea un bucle donde la búsqueda mejora la política, y la política mejorada guía la búsqueda futura.

Contribuciones Clave

1. Marco AlphaTransit: Introducción de un marco de RL guiado por búsqueda específicamente para el diseño de redes de autobuses a escala urbana, demostrando que la visión de futuro aprendida es efectiva para el TRNDP definido por simuladores.
2. Punto de Referencia TRNDP de Bloomington: Un nuevo conjunto de datos de referencia realista que presenta:
   • Una red vial topológicamente precisa (143 nodos, 243 aristas) derivada de Bloomington, Indiana.
   • Matrices de demanda OD derivadas del censo.
   • Rutas de autobús existentes diseñadas por humanos para comparación con el mundo real.
3. Evaluación Exhaustiva: Una comparación rigurosa que aísla los roles de la guía aprendida y la búsqueda. Los autores comparan AlphaTransit contra:
   • RL de Extremo a Extremo: Sin búsqueda en tiempo de decisión.
   • MCTS Puro: Sin priores aprendidos ni estimaciones de valor (utilizando priores uniformes y simulaciones de rodaje completas).
   • Líneas Base: Algoritmos Genéticos, Optimización de Colonia de Abejas, Evolución Neuronal y rutas del mundo real.

Resultados Experimentales

Los experimentos se realizaron en el punto de referencia de Bloomington bajo dos regímenes de demanda: Demanda Mixta ($\alpha=0.3$, 30% de participación de tránsito) y Demanda Total de Tránsito ($\alpha=1.0$).

Métricas de Rendimiento

• Tasa de Servicio: AlphaTransit logró las tasas de servicio más altas en ambos regímenes:
  • Demanda Mixta: 54.64% (vs. 49.72% para RL de Extremo a Extremo; 53.30% para MCTS Puro).
  • Demanda Total: 82.08% (vs. 73.70% para RL de Extremo a Extremo; 73.79% para MCTS Puro).
• Eficiencia: Bajo demanda total, AlphaTransit también logró el menor tiempo de espera, la mayor eficiencia de ruta y la mayor utilización de autobuses.
• Comparación:
  • En relación con el RL de Extremo a Extremo, AlphaTransit mejoró las tasas de servicio en un 9.9% (mixta) y un 11.4% (total).
  • En relación con el MCTS Puro, las mejoras fueron del 2.5% (mixta) y un 11.2% (total).

Eficiencia y Escalabilidad

• Costo de Búsqueda: La función de valor aprendida hace que MCTS sea práctico. A una profundidad de búsqueda de 500 simulaciones, AlphaTransit requirió 6.56 segundos por decisión, mientras que MCTS Puro (basado en simulaciones de rodaje) requirió 695.48 segundos.
• Escalado: El rendimiento alcanzó su punto máximo a una profundidad de búsqueda de $N_{iter}=400$; aumentar a 500 produjo rendimientos decrecientes. Las redes de políticas más grandes no arrojaron ganancias significativas, lo que sugiere que la profundidad de búsqueda calibrada y la diversidad de datos son más críticas que el tamaño del modelo.
• Generalización: Cuando las políticas entrenadas en Bloomington se aplicaron a la red más grande de Laval sin ajuste fino, AlphaTransit mantuvo una ventaja clara en la tasa de servicio (90.72% vs. 55.03% para RL de Extremo a Extremo bajo demanda total), demostrando transferibilidad.

Significado y Afirmaciones

El artículo afirma que acoplar priores aprendidos con visión de futuro explícita (MCTS) es más efectivo que usar cualquiera de los enfoques por separado para el diseño de redes de tránsito. La idea clave es que, aunque las extensiones de rutas locales son difíciles de evaluar debido a la retroalimentación retardada, la combinación de una red neuronal (que proporciona estimaciones de valor rápidas y priores de acción) y MCTS (que proporciona visión de futuro) permite que el sistema navegue eficazmente por el paisaje de optimización engañoso.

Los autores posicionan a AlphaTransit como una herramienta de apoyo a la decisión para las agencias de tránsito. Reconocen limitaciones, incluida la dependencia de la topología de una sola ciudad para el entrenamiento, la suposición de que las rutas comienzan desde un solo centro de tránsito y la abstracción de las restricciones de equidad y robustez en la función de recompensa. Sin embargo, los resultados sugieren que la visión de futuro aprendida es un mecanismo viable para coordinar la construcción secuencial de rutas bajo una evaluación retardada a nivel de red.