ANÁLISIS DE ALGORITMOS
2023 – 1
TUTORIAL: SPATIAL NETWORK ANALYSIS
Aplicaciones con grafos
Docente: Silvana Vallejo Córdoba
Objetivo del tutorial:
Este tutorial se centra en reconocer qué son las redes espaciales y en aprender a construir
un grafo dirigido que permita encontrar los caminos más cortos a lo largo de la red de calles
basándose en los tiempos de viaje. También, aprender a calcular los tiempos de viaje desde
un único origen a todos los nodos del grafo.
A continuación, aprenderemos a realizar análisis de redes espaciales en la práctica:
Flujo de trabajo típico para el enrutamiento:
Si se quiere realizar un análisis de redes (en cualquier lenguaje de programación) hay unos
cuantos pasos básicos que normalmente hay que seguir antes de empezar a enrutar. Estos
pasos son:
1. Recuperar los datos de la red espacial (como por ejemplo sacar la red de Open Street
Map (OSM) en formato Protocolbuffer (PBF)).
2. Modificar la red añadiendo/calculando los pesos de las aristas (como los tiempos de
viaje basados en el límite de velocidad, tipo de ruta y la longitud del segmento de
carretera, entre otras).
3. Construir un grafo dirigido para la herramienta de enrutamiento que esté utilizando
(para NetworkX, igraph, OpenTripPlanner, Pandana entre otras librerías posibles).
4. Realice un análisis de la red (como el análisis de la ruta más corta) con la herramienta
de enrutamiento de su elección.
Desarrollo:
1. Recuperar los datos:
Como primer paso, es necesario obtener datos para el enrutamiento. La librería Pyrosm
hace que sea realmente fácil recuperar redes enrutables de OpenStreetMap (OSM) con
diferentes modos de transporte (a pie, en bicicleta y en carro).
Cómo los archivos PBF son pesados (con muchos registros) se recomienda utilizar una
herramienta de compilación en línea como el Colaboratorio de Google.
1
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
!pip install pyrosm
from [Link] import sources
# Print available source categories
[Link]()
# Prints a list of countries in South America that can be downloaded
print(sources.south_america.available)
# Prints a list of all cities that can be downloaded
print([Link])
Instale la librería y después de indagar sobre las regiones y ciudades precargadas, escoja
una para trabajar.
from pyrosm import OSM, get_data
import geopandas as gpd
import pandas as pd
import networkx as nx
# We will use test data for Bogota that comes with pyrosm
osm = OSM(get_data("Bogota"))
# Parse roads that can be driven by car
roads = osm.get_network(network_type="driving")
[Link](figsize=(40,40))
Reconociendo el data set fuente: ¿Qué variables tenemos disponible en un archivo PBF?
¿Qué información codifican: oneway, maxspeed, highway?
print([Link](2))
print(roads["oneway"].unique())
print(roads["maxspeed"].unique())
print(roads["highway"].unique())
Para poder crear un grafo necesitamos tener nodos y aristas. Contamos con un
GeoDataFrame de aristas, pero ¿dónde están los nodos? Con pyrosm se puede recuperar
fácilmente los nodos especificando nodes=True, al analizar las calles:
# Parse nodes and edges
nodes, edges = osm.get_network(network_type="driving", nodes=True)
# Plot the data
ax = [Link](figsize=(10,10), color="gray", lw=1.0)
ax = [Link](ax=ax, color="red", markersize=2)
# Zoom in to take a closer look
ax.set_xlim([-74.15, -74.10])
ax.set_ylim([4.6, 4.65])
Reconociendo los nuevos nodos: ¿Qué información contienen los nodos?
2
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
[Link]()
Como podemos ver, el GeoDataFrame de los nodos contiene información sobre las
coordenadas de cada nodo, así como un id único para cada nodo. Estos valores de
identificación se utilizan para determinar la conectividad en nuestra red. Por lo tanto,
pyrosm también ha añadido dos columnas al GeoDataFrame de aristas que especifican los
identificadores de origen y destino de cada arista. La columna u contiene información sobre
el ID de origen y la columna v sobre el ID de destino:
# Check last four columns
[Link][:5,-4:]
Podemos ver que las geometrías se almacenan ahora como LineString en lugar de
MultiLineString. Llegados a este punto, podemos solucionar el problema relacionado con el
hecho de tener algunas vías peatonales en nuestra red. Podemos hacerlo eliminando todas
las aristas de nuestro GeoDataFrame que tengan el valor de carretera en 'carril bici', 'carril
peatonal', 'peatón', 'camino', 'cruce':
edges = [Link][~edges["highway"].isin(['cycleway', 'footway', 'pede
strian', 'trail', 'crossing'])].copy()
# Plot the data
ax = [Link](figsize=(10,10), color="gray", lw=1.0)
ax = [Link](ax=ax, color="red", markersize=2)
# Zoom in to take a closer look
ax.set_xlim([-74.15, -74.10])
ax.set_ylim([4.6, 4.65])
Explique ¿qué hace el anterior fragmento de código?
2. Modificar los datos:
En esta fase, tenemos los componentes necesarios para construir un grafo enrutable (nodos
y aristas) basado en la distancia. Sin embargo, en la vida real, la distancia de la red no es la
mejor métrica de costes que se puede utilizar, porque el camino más corto (basado en la
distancia) no es necesariamente siempre la ruta óptima en términos de tiempo de viaje. El
tiempo es normalmente la medida que la gente valora más (además de ser más fácil de
comprender), por lo que en esta fase queremos añadir un nuevo atributo de peso a nuestro
GeoDataFrame de aristas, que convierta la información de la distancia en metros en tiempo
de viaje en segundos, basándose en la siguiente fórmula:
<distancia en metros / (<límite de velocidad - kmph> / 3.6)
Antes de poder realizar este cálculo, debemos asegurarnos de que todas las filas de la
columna maxspeed tienen información sobre el límite de velocidad. Comprobemos los
3
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
recuentos de valores de la columna y también incluyamos información sobre los valores
NaN con el parámetro dropna:
# Count values
edges["maxspeed"].value_counts(dropna=False)
En algunos casos es necesario limpiar la forma en que la columna maxspeed almacena la
información, reemplazando datos string con datos numéricos que faciliten el cálculo del
tiempo de viaje.
# Cleaning data frame from String values 5 mph
edges["maxspeed"].replace({"5 mph":5}, inplace=True)
edges["maxspeed"] = edges["maxspeed"].astype(float)
.astype(pd.Int64Dtype())
edges["maxspeed"].unique()
Como podemos ver, ahora los valores de maxspeed se almacenan en formato entero dentro
de un IntegerArray, y los valores None se convirtieron en objetos [Link] que se asignan
con <NA>. Ahora podemos crear una función que devuelva un valor numérico para las
diferentes clases de carreteras en base a los criterios del siguiente método:
def road_class_to_kmph(road_class):
"""
Returns a speed limit value based on road class
"""
if road_class == "motorway":
return 100
elif road_class == "motorway_link":
return 80
elif road_class in ["trunk", "trunk_link"]:
return 60
elif road_class == "service":
return 30
elif road_class == "living_street":
return 20
else:
return 50
Está claro que los límites de velocidad varían de un País y de una ciudad a otra, por lo tanto,
el método debe ajustarse según sea el caso. Ahora podemos aplicar esta función a todas las
filas que no tienen información sobre el límite de velocidad que para la data de Bogotá se
trata del primer grupo más numeroso de nuestros datos.
# Separate rows with / without speed limit information
4
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
mask = edges["maxspeed"].isnull()
edges_without_maxspeed = [Link][mask].copy()
edges_with_maxspeed = [Link][~mask].copy()
# Apply the function and update the maxspeed
edges_without_maxspeed["maxspeed"] = edges_without_maxspeed["highway"]
.apply(road_class_to_kmph)
edges_without_maxspeed.head(5).loc[:, ["maxspeed", "highway"]]
Explique ¿qué hace el anterior fragmento de código?
El valor de la velocidad máxima se ha actualizado según el criterio establecido en el método
road_class_to_kmph, y por ejemplo, a la clase de carretera de servicio se le ha dado el límite
de velocidad de 30 kmph. Ahora podemos recrear el GeoDataFrame edges combinando los
dos subconjuntos anteriores:
edges = edges_with_maxspeed.append(edges_without_maxspeed)
edges["maxspeed"].unique()
Como ahora todos nuestros edges tienen información sobre el límite de velocidad. También
podemos visualizarlos de la siguiente manera:
# Convert the value into regular integer Series (the plotting requires
having Series instead of IntegerArray)
edges["maxspeed"] = edges["maxspeed"].astype(int)
ax = [Link](column="maxspeed", figsize=(40,40), legend=True)
Para observar mejor haga un zoom a una sección elegida cualquiera.
Por último, podemos calcular el tiempo de viaje en segundos utilizando la fórmula que
vimos antes y añadirlo como un nuevo atributo de coste para nuestra red:
edges["travel_time_seconds"] = edges["length"]/(edges["maxspeed"]/3.6)
[Link][0:10, -4:]
Ahora nuestro GeoDataFrame tiene toda la información que necesitamos para crear un
gráfo que se puede utilizar para realizar el análisis del camino más corto basado en la
longitud o el tiempo de viaje. Obsérvese que aquí asumimos que los vehículos pueden
conducir a la misma velocidad que es el límite de velocidad. Teniendo en cuenta la dinámica
urbana y la congestión del tráfico, esta suposición podría no cumplirse, pero por
simplicidad, lo asumimos en este tutorial.
3. Construir un grafo dirigido con pyrosm:
5
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
Usando datos de OpenStreetMap, no hay necesidad de construir grafos manualmente
porque la biblioteca pyrosm (así como OSMnx) contiene funciones que hacen todo este
trabajo. Veamos cómo podemos crear un grafo NetworkX usando pyrosm con un solo
comando:
G = osm.to_graph(nodes, edges, graph_type="networkx")
G
¿Qué tipo de grafo es, explique?
Por defecto, pyrosm limpia todas las aristas no conectadas del grafo y sólo mantiene las
aristas que pueden ser alcanzadas desde cualquier parte del grafo. Además, pyrosm
modifica automáticamente la información de los atributos del grafo de forma que sean
compatibles con OSMnx que proporciona muchas funcionalidades útiles para trabajar con
los grafos. Como, por ejemplo, trazar un mapa interactivo basado en el grafo:
import osmnx as ox
ox.plot_graph_folium(G)
Nota: Recuerde instalar la librería antes de usarla la primera vez: !pip install osmnx
4. Enrutamiento con NetworkX
Ahora tenemos todo lo que necesitamos para empezar a enrutar con NetworkX (basado en
la distancia o el tiempo de viaje).
Lógica básica del enrutamiento: la mayoría de los algoritmos de enrutamiento (si no todos)
funcionan más o menos de manera similar. Los pasos básicos para encontrar una ruta
óptima de A a B son:
• Encontrar el nodo más cercano para la ubicación de origen * (+ obtener información
sobre su ID de nodo y la distancia entre el origen y el nodo)
• Encontrar el nodo más cercano para la ubicación de destino * (+ obtener
información sobre su ID de nodo y la distancia entre el origen y el nodo)
• Utilizar un algoritmo de enrutamiento para encontrar el camino más corto entre A
yB
Esta misma lógica debe aplicarse siempre que se busque una ruta óptima entre un origen y
un destino, o cuando se calculen consultas de enrutamiento de uno a varios (produciendo,
por ejemplo, matrices de tiempo de viaje).
Encontrar la ruta óptima entre dos lugares:
Para encontrar el camino más corto entre dos localizaciones utilizando el algoritmo de
Dijkstra, en primer lugar, vamos a encontrar los nodos más cercanos para dos ubicaciones
que se encuentran en la zona. OSMnx proporciona una función útil para geo codificar una
6
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
dirección [Link](). Podemos usarla para recuperar las coordenadas x e y de nuestro
origen y destino.
# Typically we need to use lat/lon coordinates when searching for the
closest node
# Origin
orig_address = ""
orig_y, orig_x = [Link](orig_address) # notice the coordinate ord
er (y, x)!
# Destination
dest_address = ""
dest_y, dest_x = [Link](dest_address)
print("Origin coords:", orig_x, orig_y)
print("Destination coords:", dest_x, dest_y)
Investigar cómo funciona geocode y utilizar un origen y destino de preferencia en Bogotá.
Encontrar los nodos más cercanos:
A continuación, tenemos que encontrar los nodos más cercanos del grafo para nuestras dos
localizaciones. Para calcular el punto más cercano utilizamos la función
[Link].nearest_nodes() y especificamos return_dist=True para obtener la distancia en
metros.
# Find the closest nodes for origin and destination
orig_node_id, dist_to_orig = [Link].nearest_nodes(G, X=orig_x, Y=
orig_y, return_dist=True)
dest_node_id, dist_to_dest = [Link].nearest_nodes(G, X=dest_x, Y=
dest_y, return_dist=True)
print("Origin node-
id:", orig_node_id, "and distance:", dist_to_orig, "meters.")
print("Destination node-
id:", dest_node_id, "and distance:", dist_to_dest, "meters.")
Encontrar la ruta más rápida por distancia / tiempo:
Ahora podemos hacer el enrutamiento y encontrar el camino más corto entre las
ubicaciones de origen y destino utilizando la función dijkstra_path() de NetworkX. Para
obtener sólo el coste acumulado del viaje, podemos utilizar directamente la función
dijkstra_path_length() que devuelve el tiempo de viaje sin el camino real.
Con el parámetro peso podemos especificar el atributo que queremos utilizar como coste
entre los posibles atributos de peso disponibles: 'length' y 'travel_time_seconds'.
7
SLVC
ANÁLISIS DE ALGORITMOS
2023 – 1
# Calculate the paths
metric_path = nx.dijkstra_path(G, source=orig_node_id, target=dest_nod
e_id, weight='length')
time_path = nx.dijkstra_path(G, source=orig_node_id, target=dest_node_
id, weight='travel_time_seconds')
# Also get the actual travel times (summarize)
travel_length = nx.dijkstra_path_length(G, source=orig_node_id, target
=dest_node_id, weight='length')
travel_time = nx.dijkstra_path_length(G, source=orig_node_id, target=d
est_node_id, weight='travel_time_seconds')
Para fines de visualización, podemos utilizar una función de nuevo de OSMnx llamado
ox.plot_graph_route() (para grafico estática) o ox.plot_route_folium() (para el gráfico
interactivo).
# Shortest path based on distance
fig, ax = ox.plot_graph_route(G, metric_path)
# Add the travel distance as title
ax.set_xlabel("Shortest path distance {t: .1f} meters.".format(t=trave
l_length))
fig, ax = ox.plot_graph_route(G, time_path)
# Add the travel time as title
ax.set_xlabel("Travel time {t: .1f} minutes.".format(t=travel_time/60)
)
ox.plot_route_folium(G, time_path,
popup_attribute='travel_time_seconds')
Para terminar con el ejercicio haga la prueba con al menos tres rutas.
8
SLVC
