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:

El conjunto E es un subconjunto de tuplas no ordenadas (x, y) donde x e y son vértices del grafo y x no es igual a y. [Imagen del autor]

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.

La molécula de serotonina es un ejemplo de un grafo no dirigido simple. [fuente]

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.

Los corchetes representan una tupla no ordenada en las fórmulas, mientras que los paréntesis representan una tupla ordenada. [Imagen del autor]
Las interacciones humanas se pueden describir utilizando grafos dirigidos. [Imagen del autor]

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?

Centralidad del grado de los nodos para el grafo del Club de Karate. Las medidas de centralidad están normalizadas por el grado máximo del grafo (que es el número de los nodos menos uno). [Imagen del autor]

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.

El camino más corto entre A y F es [A, C, E, D, F] con una distancia de 20. [fuente]

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 cercanía de los nodos para el grafo del Club de Karate. [Imagen del autor]

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.

Centralidad de intermediación de los nodos para el grafo del Club de Karate. [Imagen del autor]

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:

Importación de datos de OSM en bruto. Los puntos blancos son nodos, que deberían representar las intersecciones de las carreteras. [Imagen del autor]

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.

Diseño de carretera después de las simplificaciones de topología. Ahora cada nodo representa un cruce de carreteras. [Imagen del autor]

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.

Diseño de carretera después de la consolidación de intersecciones. [Imagen del autor]
Comparación de la intersección. Antes y después. [Imagen del autor]

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:

Los colores indican la velocidad máxima. Cuanto más brillante el color, mayor es el valor. Podemos ver la autopista A4 coloreada en amarillo. La mayoría de las carreteras, coloreadas en azul, tienen una velocidad de 50 km/h. [Imagen del autor]

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.

Centralidad de intermediación de Cracovia para cada segmento de carretera. [Imagen del autor]

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.

Distribución de medidas de centralidad para calles y cruces en el diseño de carreteras de Cracovia. [Imagen del autor]

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.
Medidas de centralidad del grafo después de aplicar el umbral. [Imagen del autor]

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:

Tráfico típico en Cracovia durante el trayecto del lunes [©2023 Google, fuente]

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:

Centralidad de intermediación de las carreteras de Cracovia sin incluir las ciudades vecinas en el grafo. [Imagen del autor]

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.

Nuevas medidas de centralidad de diseño. La sección A4 roja representa la parte faltante. [Imagen del autor]

Echemos un vistazo a una distribución de centralidad:

Distribución de medidas de centralidad para calles e intersecciones en el diseño vial de Cracovia después de eliminar el segmento de la autopista A4–7. [Imagen del autor]

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:

Distribución del cambio de centralidad después de eliminar el segmento de la autopista A4–7. [Imagen del autor]

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.
Calles e intersecciones con el mayor aumento en la centralidad de intermediación después de eliminar el segmento de la autopista A4–7. [Imagen del autor]

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.

Carretera DK7: las partes verdes representan autopistas. [Fuente]

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.

Comparación entre la congestión promedio de Zakopianka y la centralidad de la cercanía. [©2023 Google, fuente]

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!

Share:

Was this article helpful?

93 out of 132 found this helpful

Discover more

Inteligencia Artificial

La instancia de Amazon EC2 DL2q para inferencia de IA rentable y de alto rendimiento ahora está disponible en general

Este es un post invitado de A.K Roy de Qualcomm AI. Las instancias DL2q de Amazon Elastic Compute Cloud (Amazon EC2),...

Inteligencia Artificial

Este chip centrado en la Inteligencia Artificial redefine la eficiencia duplicando el ahorro de energía al unificar el procesamiento y la memoria.

En un mundo donde la demanda de inteligencia local basada en datos está en aumento, el desafío de permitir que los di...

Inteligencia Artificial

La FAA aprueba el sistema de aeronaves no tripuladas más grande de los Estados Unidos.

La Administración Federal de Aviación de los Estados Unidos aprobó la operación comercial de los rociadores agrícolas...

Inteligencia Artificial

Microsoft lanza TypeChat una biblioteca de IA que facilita la creación de interfaces de lenguaje natural utilizando tipos.

La biblioteca TypeChat de Microsoft es un intento de facilitar la creación de interfaces de lenguaje natural basadas ...