Enfoque innovador para el diseño de redes de transporte

Las agencias de transporte en todas partes están enfrentando recortes de presupuesto. Para seguir brindando un buen servicio mientras ahorran dinero, necesitan diseñar redes de transporte de manera eficiente. Sin embargo, planificar las rutas de transporte público es un trabajo complicado. Los mejores métodos hasta ahora utilizan algoritmos para buscar diferentes opciones haciendo pequeños cambios aleatorios en las rutas. La forma en que se diseñan estos pequeños cambios puede afectar enormemente el resultado final. En este trabajo, aplicamos aprendizaje profundo con redes neuronales gráficas para aprender a hacer estos pequeños cambios automáticamente, en lugar de hacerlo manualmente. Este nuevo método muestra mejores resultados cuando se prueba en ciudades de muestra con muchos nodos, y rinde excepcionalmente bien en la reducción de Costos operativos. También mejoró una simulación de la red de transporte real en Laval, Canadá, en un gran porcentaje y logró ahorrar en costos en comparación con el sistema existente.

#Agradecimientos

Agradecemos la ayuda de la Sociedad de Transporte de Laval por proporcionar datos de mapas y transporte, y de la Agencia Metropolitana de Transporte de Quebec por proporcionar los conjuntos de datos necesarios. Estos datos fueron cruciales para nuestros experimentos. También agradecemos a nuestra agencia de financiación por el apoyo. Además, estamos agradecidos a uno de los compañeros de cuarto del autor por compartir ideas y dar retroalimentación sobre nuestros diseños.

#Contexto y Desafíos

La pandemia de COVID-19 ha causado una caída en el número de personas que usan el transporte en ciudades de todo el mundo. Esta situación ha creado una crisis financiera para muchas agencias de transporte, haciendo que sientan la necesidad de recortar costos en los servicios de transporte. Si recortar costos lleva a una disminución en la calidad del servicio, podría hacer que menos personas quieran usar el transporte, creando un ciclo de reducción en el servicio y en los ingresos. Las agencias tienen que hacer más trabajo con menos recursos. Esto hace que el diseño de las redes de transporte sea muy importante, ya que una buena planificación puede ahorrar dinero mientras aún se brinda un servicio decente. Sin embargo, cambiar una red de transporte no es algo que se deba tomar a la ligera. Para los sistemas ferroviarios, puede requerir cambios extensos, lo cual puede ser demasiado caro. Incluso para los sistemas de autobuses, rediseñar rutas puede ser costoso y disruptivo. Así que es crucial para las agencias de transporte acertar en sus diseños de red desde el principio. Buenos algoritmos para diseñar redes de transporte pueden ser muy útiles en este sentido.

#El Problema de Diseño de Redes de Transporte

El Problema de Diseño de Redes de Transporte (NDP) trata sobre planificar un conjunto de rutas de transporte para una ciudad que cumplan objetivos específicos, como satisfacer todas las necesidades de viaje mientras se mantienen bajos los costos operativos. Este es un problema complejo y desafiante. Debido a la naturaleza de las ciudades del mundo real, que a menudo tienen muchos puntos de parada potenciales, los enfoques de optimización tradicionales no son prácticos. Por lo tanto, los métodos más exitosos para abordar el NDP hasta ahora han sido algoritmos metaheurísticos. Estos algoritmos aplican diferentes reglas simples que realizan alteraciones aleatorias a una red, guiando la búsqueda de redes mejores a lo largo de muchas iteraciones utilizando un proceso similar a la selección natural.

Se han sugerido varios enfoques diferentes para guiar esta búsqueda, y se han propuesto numerosas reglas simples, adaptadas específicamente para el diseño de redes de transporte. Aunque estos algoritmos pueden ofrecer buenos resultados en muchos casos, la mayoría de las redes de transporte del mundo real todavía se diseñan manualmente.

Estas reglas simples cambian la red de diferentes maneras: algunas pueden eliminar paradas de una ruta al azar, mientras que otras podrían agregar una parada en cualquiera de los extremos de una ruta, o intercambiar dos paradas en una ruta. La mayoría de estas reglas simples son bastante aleatorias, lo que significa que no tienen en cuenta detalles específicos sobre la ciudad o la red al decidir qué cambio hacer. Queremos determinar si un sistema de aprendizaje automático podría actuar como una regla más inteligente, aprendiendo a utilizar información sobre la ciudad y la red de transporte actual para hacer los mejores cambios.

En trabajos anteriores, entrenamos una red neuronal para crear una red de transporte desde cero, demostrando que este método mejoró la calidad de las redes cuando se combinó con dos algoritmos metaheurísticos. Esto involucró generar rutas conectando los caminos más cortos en la red vial de una ciudad, y usando la red neuronal para elegir qué camino agregar a continuación. Al hacer esto repetidamente, pudimos ensamblar una red de transporte completa.

En investigaciones continuadas, exploramos si nuestra red neuronal podría mejorar un algoritmo metaheurístico al servir como una regla simple aprendida. Para probar esto, adaptamos un algoritmo evolutivo existente al sustituir una de sus reglas estándar por una que utiliza la red neuronal para planificar una nueva ruta.

Los resultados mostraron mejoras considerables en el rendimiento para ciudades con muchos nodos (70 o más).

#Expansión de los Resultados

En este trabajo, ampliamos estos hallazgos de varias maneras. Presentamos nuevos resultados obtenidos con un modelo de red neuronal actualizado y una nueva versión del algoritmo evolutivo. También llevamos a cabo estudios para evaluar la importancia de diferentes partes de nuestro enfoque combinado de redes neuronales y evolución. Algunos de estos estudios involucran una nueva regla simple no aprendida, donde los caminos con puntos finales comunes se vinculan al azar en lugar de seguir la guía de la red neuronal. Curiosamente, al centrarse estrictamente en minimizar el tiempo de viaje de los pasajeros, esta regla no aprendida superó tanto a las reglas tradicionales como a nuestra regla de red neuronal. Sin embargo, en la mayoría de los otros casos, nuestra regla de red neuronal mostró mejores resultados.

Comparamos los resultados de nuestras reglas aprendidas y no aprendidas con otros hallazgos sobre ciudades de referencia estándar. Encontramos que la regla no aprendida logra resultados similares a los mejores métodos conocidos al centrarse puramente en minimizar el tiempo de viaje de los pasajeros, mientras que nuestra regla de red neuronal supera los mejores métodos previos por hasta un 13% al minimizar los costos operativos.

Finalmente, superamos nuestro trabajo anterior aplicando nuestras reglas a datos reales de Laval, Canadá, un caso real significativo. Nuestros hallazgos muestran que nuestra regla aprendida se puede utilizar para diseñar redes de transporte para Laval que superen el sistema de transporte actual de la ciudad en simulaciones en tres objetivos de optimización. Estos resultados indican que las reglas aprendidas pueden permitir a las agencias de transporte ofrecer un mejor servicio a menores costos.

#Contexto y Trabajo Relacionado

#Aprendizaje Profundo y Problemas de Optimización

El aprendizaje profundo implica usar métodos de aprendizaje automático que cuentan con redes neuronales artificiales profundas, aquellas con múltiples capas ocultas. Cuando se combina con el aprendizaje por refuerzo (RL), una rama del aprendizaje automático donde un sistema toma decisiones y recibe recompensas numéricas, puede maximizar la recompensa total a través de diversas acciones. Existe un notable aumento en el interés por aplicar el aprendizaje profundo, y específicamente RL profundo, a problemas de optimización combinatoria como el Problema del Viajante (TSP).

Los investigadores han propuesto diferentes modelos, como las Redes de Puntero, entrenadas mediante aprendizaje supervisado para resolver instancias del TSP. Otros estudios han ampliado estos hallazgos, empleando modelos de redes neuronales similares con algoritmos de RL para crear soluciones para el TSP y otros desafíos de optimización. Algunos estudios recientes han entrenado redes neuronales recurrentes para generar poblaciones iniciales de soluciones para un algoritmo genético, mejorando aún más el proceso de entrenamiento.

Estos métodos generalmente caen bajo los métodos de "construcción" que comienzan con una solución vacía y construyen sobre ella, mientras que los métodos de "mejora" modifican soluciones completas para buscar mejores opciones. Los Algoritmos Evolutivos pertenecen a esta categoría y pueden ser computacionalmente costosos pero a menudo producen mejores resultados. Algunos trabajos han entrenado redes neuronales para seleccionar movimientos en métodos de mejora, demostrando un rendimiento impresionante en el TSP y problemas similares. En este contexto, nuestro trabajo entrena una red neuronal para abordar el problema de diseño de redes de transporte y luego la utiliza para mejorar soluciones dentro de un método de mejora.

En la mayoría de esta investigación, los modelos de redes neuronales utilizados son redes neuronales gráficas, diseñadas para trabajar con datos estructurados en gráficos. Estos modelos han encontrado aplicaciones en diversos campos, incluyendo análisis de gráficos web grandes, diseño de circuitos y predicción de propiedades moleculares. Dado que el problema de diseño de redes de transporte se puede describir como un problema de gráfico, también empleamos modelos de redes neuronales gráficas.

#Optimización del Transporte Público

El problema de diseño de redes de transporte es NP-completo, lo que significa que encontrar soluciones óptimas es impráctico para la mayoría de los casos. Si bien las técnicas de optimización analítica han funcionado en instancias pequeñas, a menudo luchan por representar de manera realista el problema. Por lo tanto, los enfoques metaheurísticos han ganado tracción.

Las metaheurísticas más utilizadas para el NDP incluyen algoritmos genéticos, recocido simulado y optimización por colonia de hormigas. Trabajos recientes han mostrado éxito con otras metaheurísticas como hiper-heurísticas, búsqueda en haz y enjambres de partículas. Numerosas reglas de bajo nivel se utilizan en estos algoritmos metaheurísticos, pero la mayoría selecciona entre las opciones posibles de manera uniforme y al azar.

Existe una excepción donde los autores diseñaron un modelo simple para examinar cómo cada cambio podría impactar la calidad. Sin embargo, este modelo sencillo pasa por alto los viajes de pasajeros que involucran transbordos y preferencias de los usuarios. En contraste, nuestro método aprende un modelo para evaluar estos impactos mientras considera un conjunto más rico de entradas.

Si bien se han empleado redes neuronales para problemas predictivos en movilidad urbana, su aplicación al NDP sigue siendo limitada, al igual que el aprendizaje por refuerzo. Dos ejemplos recientes han utilizado RL para el diseño de rutas en una pequeña ciudad de referencia con solo un puñado de paradas de transporte. Sin embargo, estos métodos no se adaptan bien a instancias más amplias. Nuestro enfoque puede encontrar buenas soluciones para casos más grandes de NDP, superando los 600 nodos, y puede ser utilizado para instancias no vistas.

#Formulación del Problema

Definimos el problema de diseño de redes de transporte en términos de un gráfico de la ciudad con una colección de nodos y aristas. Cada nodo representa paradas potenciales de transporte, mientras que las aristas los conectan con pesos que indican los tiempos de viaje. El objetivo es ofrecer una red de transporte que satisfaga la demanda de viajes con un enfoque en minimizar costos.

La red debe conectar pares de demanda mientras mantiene un número definido de rutas y respetando limitaciones como límites de paradas y evitando ciclos. Nos enfocamos en el NDP simétrico, lo que significa que todas las demandas y rutas funcionan igualmente en ambas direcciones.

#Formulación del Proceso de Decisión de Markov

Un Proceso de Decisión de Markov (MDP) ofrece una manera de definir problemas de RL. Un agente interactúa con un entorno durante varios pasos de tiempo. En cada paso de tiempo, el entorno se encuentra en un estado particular, y el agente elige acciones que conducen a nuevos estados, recibiendo recompensas según las acciones tomadas. En nuestro enfoque MDP para el NDP, el estado consiste en rutas completadas y una ruta que se está diseñando actualmente. El agente alterna entre extender esta ruta o decidir detenerla.

#Función de Costo

Nuestra función de costo del NDP tiene varias partes. El primer componente representa el tiempo promedio que los pasajeros pasan viajando a través de la red, mientras que el segundo componente tiene en cuenta el tiempo total de conducción de las rutas. La tercera parte asegura que se respeten las limitaciones contando la fracción de pares de demanda que permanecen desconectados. De este modo, la función de costo equilibra los costos de los pasajeros y operativos mientras permite ajustes.

#Aprender a Construir una Red

Entrenamos una red neuronal gráfica para maximizar el retorno acumulativo dentro de nuestra formulación MDP. Al aplicar esta política aprendida en una ciudad, podemos generar redes de transporte, a las que llamamos "construcción aprendida". Ejecutarla varias veces nos ayuda a obtener diversas redes, permitiéndonos elegir la que tenga el costo más bajo.

La parte central de la red de políticas es una red de atención gráfica que trata la ciudad como un gráfico completamente conectado. Cada nodo y arista contiene información relevante sobre la ubicación, la demanda y las conexiones de transporte existentes. La salida consiste en incrustaciones de nodos que informan la decisión de elegir entre extensiones o detener la construcción.

Entrenar la política implica ejecutar episodios en ciudades sintéticas. Cada ciudad se genera al azar, mientras que los parámetros se mantienen constantes durante el entrenamiento, lo que permite que la red neuronal aprenda de diversas situaciones.

#Algoritmo Evolutivo

Evaluamos si nuestra política aprendida puede servir efectivamente como una regla de bajo nivel dentro de un algoritmo metaheurístico. El algoritmo evolutivo base opera sobre una población de soluciones, alternando entre fases de mutación y selección. Para la fase de mutación, aplicamos dos tipos de mutadores a subconjuntos elegidos al azar de la población. Si la red mutada rinde mejor que su predecesora, reemplaza a la red madre.

Nuestro algoritmo evolutivo neuronal modifica esto al utilizar nuestra política aprendida en lugar de uno de los mutadores estándar. Este enfoque permite cambios más avanzados, fomentando mejores soluciones mediante la combinación de heurísticas existentes y aprendidas.

#Experimentos y Resultados

Evaluamos nuestro método en varios conjuntos de datos de referencia, incluyendo ciudades de Mandl y Mumford. Cada ciudad presenta parámetros distintos, y cada experimento se ejecuta en varias iteraciones para obtener resultados robustos. El algoritmo evolutivo neuronal se compara con el enfoque evolutivo base para determinar su efectividad.

#Comparación con el Algoritmo Base

En nuestros experimentos, el algoritmo evolutivo neuronal logra resultados significativamente mejores, particularmente en ciudades más grandes. Las mejoras se vuelven más pronunciadas a medida que las ciudades crecen, con mejoras distintas tanto en costos operativos como en tiempos de viaje de los pasajeros.

#Estudios de Ablación

Para mejorar nuestra comprensión de cada componente del algoritmo, realizamos estudios de ablación para analizar el impacto de varias partes dentro de nuestro sistema. Esto incluye comparar nuestro mutador neuronal con una versión sin él, ayudándonos a evaluar su contribución al rendimiento general.

#Aplicación a Escenarios del Mundo Real

Aplicamos nuestro enfoque a datos de Laval, Canadá, para evaluar su efectividad en un entorno real. El gráfico de calles se deriva de diversas fuentes, incluyendo datos geográficos, redes de transporte existentes y matrices de demanda. Cada uno de estos componentes informa nuestro diseño mientras asegura que la nueva red conecte todos los viajes de pasajeros necesarios.

#Resultados en Laval

Nuestros experimentos muestran que la política aprendida puede desarrollar redes en Laval que superan el sistema de transporte existente, reduciendo significativamente los tiempos operativos y mejorando las experiencias de los pasajeros. Los hallazgos indican posibles ahorros de costos para la agencia de transporte mientras mejoran la calidad del servicio.

#Conclusión

Esta investigación demuestra que usar Aprendizaje por refuerzo profundo para aprender heurísticas puede mejorar drásticamente el diseño de redes de transporte sobre métodos tradicionales. El enfoque permite a las agencias de transporte lograr un mejor servicio a un costo reducido, siendo beneficioso en escenarios del mundo real. De cara al futuro, explorar algoritmos metaheurísticos variados y refinar el proceso de aprendizaje podría generar aún mayores mejoras en el diseño y rendimiento de redes.