Photo by Liren on Unsplash

Teoría de grafos

Un sistema de transporte puede representarse formalmente como un grafo:
G=(V,E)
Donde:
V= Conjunto de nodos (intersecciones, estaciones, puntos de decisión)
E= Conjunto de aristas o enlaces (calles, tramos, vías)
Un sistema de transporte es un sistema dinámico de entidades que se desplazan sobro una estructura física, la que nosotros podemos representar con un grafo.
Si eliminamos todo lo superficial, vehículos, semáforos, señalización, quedaría algo así:
Puntos donde algo ocurre (decisiones, giros, abordajes)
Conexiones entre puntos
Flujos que atraviesan esas conexiones.
Esto podríamos llamarlo, sistema topológico de nodos y enlaces.
Un enlace conecta con dos nodos, y tiene ciertas propiedades:
Longitud ($L$)
Velocidad permitida ($v$)
Capacidad ($C$)
Tiempo de recorrido $t= \frac{L}{V}$
En microsimulación, esta estructura es la base computacional sobre la cual luego simulamos comportamientos individuales, como el car-following.
Ahora imagina una intersección con cuatro accesos. cada esquina es un nodo, y cada ramo entre intersecciones es una arista dirigida. No importa que le agregues, como señalamientos o semáforos, al final, seguirá siendo un grafo pero con ciertos atributos.

Relación entre teoría de grafos y simulación de tránsito

La microsimulación se ejecuta sobre una estructura de grafo dirigido ponderado con atributos dinámicos.
Un modelo microscópico simula vehículos individuales.
Pero esos vehículos necesitan:
saber dónde están (nodo actual)
saber a dónde pueden ir (aristas disponibles)
saber cuánto cuesta avanzar (peso del enlace)
En teoría de grafos eso se llama grafo dirigido.
En simulación, esos pesos pueden cambiar con el tiempo.
Por ejemplo:
t_{ij}(t)=f(q{ij}(t))
Aquí espero puedas notar que el tiempo de recorrido depende del flujo, y justo aquí es donde empieza a conectarse con dinámica no linea.
La estructura puede ser estática, pero el comportamiento es dinámico.
Cuando Vissim calcula rutas dinámicas, usa algoritmos tipo Dijkstra o variantes basadas en costos generalizados.
Bases generales del software de simulación
Un software de microsimulación combina:
1.
Representación de red (grafo)
2.
Modelos de comportamiento individual
3.
Generador de demanda
Un simulador microscópico funciona en pasos de tiempo discretos:
t=0,\Delta t, 2 \Delta t, ...
En cada paso:
Actualiza posición de cada vehículo
Evalúa interacción con vehículo líder
Aplica reglas de cambio de carril
Registra datos
Es esencialmente un sistema multiagente sobre un grafo.
El realismo depende de:
calibración
calidad de datos
correcta estructuración de red
En Vissim:
Los links = aristas
Los conectores = transiciones entre aristas
Los vehículos = agentes
Los detectores = nodos con sensores
Ejercicio:
Si un vehículo se mueve con un modelo simple:
x(t+\Delta t)=x(t+v(t) \Delta t
y
v(t+ \Delta t)=v(t)+a \Delta t
con:
$v(0)=0$
$a=2m/s²$
$\Delta t=1 s$
Determine posición y velocidad después de 5 segundos.
Modelo en tiempo discreto (con $Δt=1 s\Delta t=1\ \text{s}Δt=1 s$):
x(t+Δt)=x(t)+v(t)Δt,v(t+Δt)=v(t)+aΔtx
Datos:
v(0)=0,a=2 m/s2,Δt=1 s,x(0)=0
Como $\Delta t=1$, las ecuaciones se simplifican así:
v(t+1)=v(t)+2
x(t+1)=x(t)+v(t)
Inicio $t=0$:
x(0)=0, v(0)=0
Con $t=1$:
v(1)=v(0)+2=0+2=2
x(1)=x(0)+v(0)=0+0=0
Con $t=2$:
v(2)=v(1)+2=2+2=4
x(2)=x(1)+v(1)=0+2=2
Con $t=3$:
v(3)=v(2)+2=4+2=6
x(3)=x(2)+v(2)=2+4=6
Con $t=4$:
v(4)=v(3)+2=6+2=8
x(4)=x(3)+v(3)=6+6=12
Con $t=5$:
v(5)=v(4)+2=8+2=10
x(5)=x(4)+v(4)=12+8=20
Si lo piensas un poco, notarás que el método asume que arrancaste con $v(0)=0$ constante. Pero si cambiamos $a$ por una función más realista, como el car-following que depende de un líder, de ahí se forma una microsimulación básica.