Mapeando los atascos Análisis del tráfico utilizando teoría de grafos

Análisis del tráfico utilizando teoría de grafos

Aprende cómo encontrar puntos críticos potenciales en la infraestructura de tu ciudad usando la teoría de grafos

La teoría de grafos tiene muchas aplicaciones en problemas de la vida real, como las redes sociales, la biología molecular o los datos geoespaciales. Hoy, presentaré la última, analizando el diseño de las calles de la ciudad para predecir calles críticas, intersecciones y cómo los cambios en la infraestructura pueden afectarla. Pero primero, empecemos con lo básico.

Grafos y sus medidas de centralidad

Los grafos son conjuntos de vértices y sus aristas:

Donde las aristas representan las conexiones entre los nodos. Si las aristas no tienen direcciones, llamamos al grafo no dirigido. Un ejemplo de grafo no dirigido en la vida real puede ser una molécula química, donde los vértices son átomos y los enlaces se representan como aristas.

Sin embargo, a veces necesitamos información sobre si la arista va de u a v, de v a u o en ambas direcciones. Por ejemplo, si Mark le gusta Alice, no necesariamente significa que sea mutuo ( ☹ ). En esas situaciones, podemos definir la arista como una tupla ordenada en lugar de una no ordenada.

• Explicar decisiones médicas en entornos clínicos utilizando Amazon SageMaker Clarify
• Robot humanoide puede pilotar un avión mejor que un humano
• ChatGPT tiende hacia el liberalismo

Usando la estructura del grafo, podemos definir una medida de centralidad. Es una métrica utilizada para responder la pregunta:

¿Qué tan importante es este vértice/arista en un grafo?”

Y hay muchas formas de responderla.

Diferentes formas de evaluar la importancia de los componentes de un grafo

Dependiendo de la tarea, podemos comenzar desde un punto diferente evaluando la centralidad. Una de las métricas más comunes son: Grado, Cercanía e Intermediación. Las discutiremos utilizando el grafo del Club de Karate de Zachary [más información]. Presenta vínculos entre diferentes miembros del club de karate. Puedes encontrar el código utilizado para generar las imágenes a continuación aquí.

Centralidad del grado

La más básica de las centralidades. Se define solo para los vértices y es igual al grado del vértice (que es el número de los vértices vecinos). Como ejemplo, podemos pensar en el grafo de las relaciones humanas y, en el caso de las amistades entre personas, esta métrica respondería a la pregunta:

¿Qué tan popular es esta persona?

Caminos en el grafo

Para las siguientes dos centralidades, necesitamos introducir algunos conceptos en nuestro conocimiento de la teoría de grafos. Todos ellos son muy intuitivos, comenzando por los pesos de las aristas. Podemos agregar pesos a nuestras aristas para marcar la diferencia entre ellas. Por ejemplo, esto puede ser la longitud de la carretera en caso de un grafo de tráfico.

En los grafos podemos definir caminos, que son listas de vértices que debemos recorrer para llegar de A a B. Los vértices consecutivos en el camino son vecinos, el primer vértice es A y el último es B. La distancia del camino es la suma de los pesos de las aristas a lo largo del mismo. El camino más corto entre A y B es el camino con la distancia más pequeña.

Centralidad de cercanía

Teniendo todos estos nuevos conocimientos, podemos volver a nuestras métricas. La siguiente es la centralidad de cercanía, que nos dice qué tan cerca está un nodo del resto del grafo. Se define para un vértice específico como el inverso de la media de los caminos más cortos a todos los demás vértices en el grafo. De esta manera, un camino promedio más corto se traduce en una centralidad de cercanía más alta.

Centralidad de intermediación

La centralidad de intermediación nos brinda información sobre qué nodos de un grafo son cruciales para el tráfico que lo atraviesa. Imagina una ciudad con una extensa red de carreteras, donde cada intersección es un nodo. Algunas de estas intersecciones sirven como conectores clave en los desplazamientos diarios, mientras que otras pueden ser callejones sin salida con poco o ningún impacto en el flujo de tráfico. Las primeras poseen puntuaciones altas de centralidad de intermediación, calculadas como la proporción de los caminos más cortos que atraviesan la intersección.

Plan de la ciudad como un grafo

Ahora, como tenemos herramientas para describir y analizar grafos, podemos comenzar a extraer el plan de la ciudad en forma de grafo. Para hacer eso, podemos utilizar Open Street Maps (OSM) para importarlo en Python como un grafo NX utilizando la biblioteca osmnx. Comenzaremos con un ejemplo más pequeño para discutir qué proceso adicional debemos aplicar para mejorar el tiempo y la eficiencia de nuestro trabajo.

Grzegórzki es uno de los dieciocho distritos de la ciudad de Cracovia, con dos rotondas complejas: Mogilskie y Grzegórzeckie, y muchas intersecciones. Por lo tanto, podremos ver la mayoría de los posibles problemas con la ingeniería de datos.

Fronteras administrativas de Grzegórzki. [©Google]

Comencemos importando datos del repositorio de OSM a un grafo de Python y representemos los resultados:

Hay algo mal en este grafo, ¿puedes identificar qué es?

Obtenemos múltiples aristas para secciones individuales de carreteras, lo que resulta en un grafo con casi 3,000 “intersecciones”. Esto no proporciona una representación adecuada (no podemos dar la vuelta en U en medio de una carretera y cada nodo ralentiza los cálculos). Para solucionar esta situación, realizaremos una simplificación de la topología del grafo eliminando todos los nodos en la carretera entre dos intersecciones. En OSMnx, tenemos una función llamada ox.simplify_graph() para eso.

Hay otro detalle: como se puede ver, tenemos dos aristas para la mayoría de las carreteras, una para cada dirección. Debido a esto, tenemos múltiples nodos para cada intersección, lo cual es un comportamiento no deseado. Imagina que estamos en una intersección, giramos a la izquierda y no hay un carril separado para girar a la izquierda (o ya está lleno). Mientras no podamos hacer el giro, los otros autos están bloqueados. En nuestro grafo actual, esto no es cierto. El giro a la izquierda está compuesto por 2 nodos separados, uno para girar a la izquierda y el otro para cruzar el carril opuesto. Esto indicaría que son dos operaciones independientes, cuando no lo son.

Es por eso que vamos a consolidar las intersecciones, es decir, vamos a combinar múltiples nodos cercanos entre sí en uno solo. Elegiremos un radio de consolidación lo suficientemente grande como para combinar varias partes de las intersecciones en una sola, pero por otro lado, mantendremos las rotondas como estructuras de múltiples nodos, ya que solo pueden bloquearse parcialmente. Para hacer esto, utilizaremos la función ox.consolidate_intersections() de osmnx.

Después de estas operaciones, estamos casi listos para el análisis. El último detalle son los límites del municipio de Cracovia: como mucha gente viaja desde las ciudades vecinas y el análisis del grafo solo incluye datos dentro del grafo, necesitamos incluir esas áreas. Presentaré en el próximo capítulo las implicaciones de no hacerlo. Y aquí está nuestro grafo:

Puedes encontrar el código fuente utilizado para generar este mapa, así como todos los gráficos utilizados en el próximo capítulo, en este cuaderno de Jupyter.

Centralidad de intermediación del diseño de carreteras

Para este estudio de caso, nos enfocaremos solo en la medida de centralidad de intermediación para estimar el tráfico en las carreteras. En el futuro, esto podría extenderse a otras técnicas de teoría de grafos, incluido el uso de GNN (Redes Neuronales de Grafos).

Comenzaremos calculando la medida de centralidad de intermediación para todos los nodos y aristas en una representación del diseño de carreteras. Para eso, utilizaremos la biblioteca NetworkX.

Debido a un alto número de caminos en un grafo, es difícil ver qué componentes tienen la mayor probabilidad de ser críticos para el tráfico. Echemos un vistazo a una distribución de medidas de centralidad para el grafo.

Podemos usar esas distribuciones para filtrar cruces y calles menos importantes. Seleccionaremos el 2% superior de cada una, donde los valores umbral son:

• 0.047 para los nodos,
• 0.021 para las aristas.

Podemos ver que los segmentos de carretera más importantes por intermediación son:

• La autopista A4 y la S7 que forman el cinturón de circunvalación de Cracovia (nota que Cracovia no tiene la parte norte del cinturón de circunvalación),
• La parte occidental de la segunda carretera de circunvalación y su conexión con la A4,
• La parte norte de la tercera carretera de circunvalación (sustituyendo la parte norte faltante del cinturón de circunvalación),
• La calle Nowohucka que conecta la segunda carretera de circunvalación con la parte noreste de la ciudad,
• La carretera Wielicka que va desde el centro de la ciudad hasta la parte sureste de la autopista.

Comparemos esta información con un mapa de tráfico real de Cracovia de Google Maps:

Podemos ver que nuestras conclusiones se correlacionan con los resultados del radar de tráfico. El mecanismo detrás de esto es bastante simple: los componentes con alta centralidad de intermediación son aquellos que se utilizan para la mayoría de las rutas más cortas en el grafo. Si los conductores seleccionan las mejores rutas para sus trayectos, entonces las calles y cruces con el mayor volumen de tráfico serán aquellos con la mayor centralidad de intermediación.

Volviendo a la última parte de la ingeniería del grafo, ampliemos los límites del grafo. Veamos qué sucedería si solo tomáramos en cuenta los límites de la ciudad en nuestro análisis:

La autopista A4, que es uno de los componentes más importantes debido a su naturaleza de cinturón de circunvalación, ¡tiene una de las medidas de centralidad más bajas en todo el grafo! Esto ocurre porque la A4 se encuentra en las afueras de la ciudad y la mayoría de su tráfico proviene del exterior, por lo que no podemos incluir este factor en la centralidad de intermediación.

Cómo utilizar la centralidad de intermediación para analizar los efectos de un cambio en el diseño del tráfico

Veamos un escenario diferente para el análisis del grafo. Supongamos que queremos predecir cómo afecta el tráfico el cierre de una carretera (por ejemplo, debido a un accidente). Podemos utilizar las medidas de centralidad para comparar las diferencias entre dos grafos y, así, examinar los cambios en la centralidad.

En este estudio, simularemos un accidente automovilístico en el segmento de la autopista A4-7, lo cual es algo común. El accidente causará el cierre completo del segmento.

Comenzaremos creando una nueva red de carreteras eliminando el segmento A4-7 del grafo y recalculando las medidas de centralidad.

Echemos un vistazo a una distribución de centralidad:

Podemos ver que sigue siendo muy similar al original. Para inspeccionar los cambios en las medidas de centralidad, calcularemos el grafo residual, donde las medidas de centralidad son la diferencia entre el diseño vial original y después del accidente. Los valores positivos indicarán una mayor centralidad después del accidente. Los nodos e intersecciones que faltan en uno de los grafos (como A4–7) no se incluirán en el grafo residual. A continuación se muestra la distribución de las medidas residuales:

Nuevamente, filtraremos el 2% superior de calles y nodos afectados. Los valores umbrales esta vez son:

• 0.018 para los nodos,
• 0.017 para las aristas.

Podemos ver aumentos en las carreteras que conectan las partes separadas de la circunvalación con el centro de la ciudad, donde se encuentra la segunda carretera de circunvalación. El cambio más alto se puede ver en la segunda carretera de circunvalación, que contiene uno de los dos puentes izquierdos sobre el río Vístula en el lado oeste de la ciudad.

Lo que el análisis de centralidad de grafos no puede hacer en una red vial

Hay algunas cosas que no podemos tener en cuenta durante el análisis de grafos. Las dos más importantes, que pudimos ver en este análisis, son:

• El análisis de centralidad de grafos asume una distribución uniforme del tráfico entre los nodos.

Lo cual es falso en la mayoría de los casos, ya que los pueblos y ciudades tienen diferentes densidades de población. Sin embargo, existen otros efectos que pueden reducir esto, por ejemplo, una mayor cantidad de personas que viven en pueblos vecinos elegirán un automóvil como opción de transporte en comparación con las personas que viven en el centro de la ciudad.

• El análisis de grafos tiene en cuenta solo las cosas que están presentes dentro del grafo.

Esto es más difícil de ver en los ejemplos proporcionados, especialmente para alguien fuera de Cracovia. Echemos un vistazo a Zakopianka. Es una importante arteria de tráfico entre el centro de la ciudad y la mayoría de los municipios al sur de Cracovia, y también es parte de la DK7 (carretera nacional n. ° 7) que se extiende por todo el país.

Si comparamos el tráfico típico en DK7 en Cracovia con nuestras medidas de centralidad, son completamente diferentes. La centralidad de intermediación promedio es de alrededor de 0.01, que es un valor dos veces menor que el umbral del 2% superior. Mientras que en realidad, es una de las secciones más bloqueadas.

En conclusión

La teoría de grafos y su análisis tienen aplicaciones en múltiples escenarios, como el análisis de tráfico presentado en este estudio. Utilizando operaciones básicas y métricas en grafos, podemos obtener información valiosa en un tiempo mucho más corto en comparación con la construcción de un modelo de simulación completo.

Todo este análisis se puede realizar utilizando varias docenas de líneas de código Python, y no se limita a un diseño de carretera en particular. También podemos realizar fácilmente la transición a otras herramientas de análisis de la Teoría de Grafos.

Como todas las cosas, este método también tiene sus inconvenientes. Los principales son las suposiciones sobre la distribución uniforme del tráfico y el alcance limitado a la estructura del grafo.

Puedes encontrar el repositorio de Github que contiene el código utilizado en este estudio aquí.

We will continue to update Zepes; if you have any questions or suggestions, please contact us!