Last Modified: 2023-Jun-29

INTRO Roadmap

Índice

1. Objetivo
2. Fases:
   1. Datos sobre las carreteras/vías
   2. Representación en grafo
   3. Caracterizar la congestión/tráfico
      1. Analizando estos datos aparecen ciertos problemas
      2. Soluciones
      3. Juntando los datos de Uber en el grafo
   4. Estaciones Base de telefonía móvil

---

Objetivo

Desarrollar un entorno en Python, basado en la libería NetworkX, con el fin de estudiar algoritmos de planificación de rutas en un escenario de conducción remota con entornos reales.

Por ejemplo, herramienta para visualización de la evolución del camino óptimo Algoritmo jerárquico para la planificación de rutas. Con dos niveles: rutas a nivel de estación base y rutas en el área de cobertura de la estación base Algo así Simulación de eventos de congestión un poco lo que has esetado haciendo hasta ahora

Fases:

Datos sobre las carreteras/vías

Con datos aportados por OpenStreetMap, a través de la API, Overpass, se definen las carreteras como sets de vías y nodos.

Por ejemplo, en esta zona del centro de Madrid.

Se hace un request sobre estos datos en un rectángulo (bbox) o una zona y distancia(around)

Filtrando por tags, copiando algunos tags de Project-OSRM y añadiendo otros, presentes en el área de madrid

Se reciben otros tags como si la vía es de un sentido, la velocidad máxima, etc

Representación en grafo

Para tratar estos datos en forma de grafo, cargamos los datos en un objeto Graph, como un grafo indirecto. Esta libería Networkx facilita la resolución de shortest path por Dijkstra y A*

import networkx as nx
Graph=nx.Graph()
ways_nodes=queryOSM(lat,long)
Graph.add_edges_from(ways_nodes)
...
ShortestPath=nx.dijkstra_path(Graph,node_start,node_end) # Array de nodos
...
pintar(Graph)
pintar(ShortestPath)

Caracterizar la congestión/tráfico

Necesitamos datos de la congestión de las carreteras, UberMovement expone los datos de las rutas por las que atraviesan los coches de Uber, archivos csv, columnas de interés:

Field	Description
year	-
month	-
day	-
hour	-
osm_way_id	UID identifica una vía en OSM
osm_start_node_id	Útil si la vía es muy larga la velocidad se establece para un tramo de esta
osm_end_node_id	Útil si la vía es muy larga la velocidad se establece para un tramo de esta
speed_kph_mean	-
speed_kph_stddev	-

Estos datos de los csv los subo a una DB SQL, concretamente los 3 primeros meses de 2020. No hay fechas más recientes.

Analizando estos datos aparecen ciertos problemas

1. A pesar de ser 10 millones de entradas, n° muestras diario reducido:

   sql> select avg(t.samples) AvgSamplesPerDay
   from (select u.`month`, u.`day`, u.`hour` , count(*) samples 
     from ubermv u
     group by u.`month`, u.`day`, u.`hour`) t ;
   ---
   AvgSamplesPerDay|
   ----------------+
       4736.3684|
   

2. La resolución temporal es de una hora, limitando simulación en tiempo real, i.e. por minutos.

Soluciones

1. Se crea otra base de datos con días de las semana y horas como índice de las velocidades y vías.

   select * from semaneado s 
   where s.osm_way_id = 3996189 and s.`hour` = 9
   ---
   osm_way_id|weekday  |hour|speed_kph_mean|speed_kph_stddev|
   ----------+---------+----+--------------+----------------+
   3996189|Monday   |   9|    77.8963356|      11.7483333|
   3996189|Thursday |   9|    99.3883336|      14.2429997|
   3996189|Wednesday|   9|    71.7419993|          20.217|
   3996189|Friday   |   9|    96.9126689|      14.3606669|
   3996189|Saturday |   9|   109.4249985|      10.6391998|
   3996189|Sunday   |   9|   102.5900002|       8.6319997|
   

2. Interpolar muestras en horas, días, meses – SOLUCION NO EXPLORADA

Juntando los datos de Uber en el grafo

En Networkx los vertices o edges se añaden como 3-tuplas (u,v,data), data es un diccionario con información arbitraria, a la cual queremos acceder posteriormente, por ejemplo, durante la búsqueda de la ruta más corta o cuando se representa pinta el grafo. En data['speed'] se guarda la velocidad “actual”:

import networkx as nx
Graph=nx.Graph()
ways_nodes=queryOSM(lat,long)
Graph.add_edges_from(ways_nodes)
ubermv.updatespeed(Graph,hora=9,dia=Friday)
...
ShortestPath=nx.dijkstra_path(Graph,node_start,node_end) # Array de nodos
...
pintar(Graph)
pintar(ShortestPath)

1. Representación por anchura de la vía y color, en función de la velocidad máxima y la “actual”

2. Representación de las velocidades de las vías por las que pasa la ruta más corta

3. Cambios del shortest path en función del tiempo

   Estaciones Base de telefonía móvil

   Cells

---

Table of contents

• Roadmap
• Roadmap_2-Voronoi_Cells
• Conclusions