Back to Home
Best Independent Mathematical Research Project Award

Traffic Flow Modelling & Reinforcement Learning via the LWR Conservation Law and Godunov Schemes

Deniz Coban · Python, NumPy, FastAPI, PDEs
Overview Awarded the school prize for Best Independent Mathematical Research Project, this study models urban road networks as a 1D compressible fluid governed by the nonlinear Lighthill–Whitham–Richards (LWR) conservation law $\partial_t \rho + \partial_x q(\rho) = 0$. We discretise the PDE with a conservative Godunov demand–supply finite-volume scheme, proving its equivalence to the exact Riemann flux and capturing shockwaves and rarefaction waves across signalised grids of 1 to 36 junctions ($1\times 1$ to $6\times 6$). We then engineer a shared-table Q-learning signal controller over a compressed 96-state space using network-wide flux rewards and sensor-informed priors to accelerate cold-start convergence. Across 6 held-out demand seeds per load against sensor-actuated and fixed-time baselines, the controller raises junction flux by up to 2.9% and reduces total time spent (TTS) by 7–19% at medium load on grids of $2\times 2$ and larger.

1. Macroscopic Conservation Law & Greenshields Closure

Let $\rho(x,t) \in [0, \rho_{\max}]$ denote spatial vehicle density (veh/m) and $q(x,t)$ denote macroscopic flow rate (veh/s) along a road link $x \in [0, L]$. Conservation of vehicles over any control volume $[x_1, x_2]$ requires $\frac{d}{dt}\int_{x_1}^{x_2} \rho(x,t)\,dx = q(x_1,t) - q(x_2,t)$, yielding the scalar hyperbolic PDE:

$$\frac{\partial \rho}{\partial t} + \frac{\partial q(\rho)}{\partial x} = 0, \qquad q(\rho) = \rho v(\rho) = v_f \rho \left(1 - \frac{\rho}{\rho_{\max}}\right)$$

where $v_f > 0$ is the free-flow speed and $\rho_{\max} > 0$ is the jam density. Because $q''(\rho) = -2v_f / \rho_{\max} < 0$, the flux function $q(\rho)$ is strictly concave and attains its unique capacity maximum $q_{\max} = \frac{1}{4} v_f \rho_{\max}$ at the critical density $\rho_c = \frac{1}{2}\rho_{\max}$.

2. Method of Characteristics, Shockwaves & Rarefaction Fans

For smooth solutions, the chain rule gives the quasi-linear advection equation $\partial_t \rho + c(\rho)\partial_x \rho = 0$ with kinematic wave speed:

$$c(\rho) = q'(\rho) = v_f \left(1 - \frac{2\rho}{\rho_{\max}}\right)$$
Theorem 1 (Rankine–Hugoniot Jump Condition & Entropy Waves) Across a discontinuity $x = \xi(t)$ separating upstream density $\rho_L$ and downstream density $\rho_R$, integral mass conservation enforces the Rankine–Hugoniot shock speed: $$s = \frac{d\xi}{dt} = \frac{q(\rho_R) - q(\rho_L)}{\rho_R - \rho_L} = v_f \left(1 - \frac{\rho_L + \rho_R}{\rho_{\max}}\right)$$ By the Lax entropy condition $c(\rho_L) > s > c(\rho_R)$, a discontinuous shockwave forms if and only if $\rho_L < \rho_R$ (vehicles decelerating into the back of a queue). Conversely, when a signal turns green and a dense queue discharges into an empty link ($\rho_L > \rho_R$), characteristics fan outward in a continuous self-similar rarefaction wave $\rho(x,t) = \frac{\rho_{\max}}{2}\left(1 - \frac{x}{v_f t}\right)$ for $c(\rho_L) \le x/t \le c(\rho_R)$.

3. Conservative Godunov Demand–Supply Scheme

Partitioning each road link into $N$ finite-volume cells $C_i = [x_{i-1/2}, x_{i+1/2}]$ of width $\Delta x = L/N$, cell averages $\rho_i^n$ evolve via the exact conservation update:

$$\rho_i^{n+1} = \rho_i^n + \frac{\Delta t}{\Delta x}\left(F_{i-1/2}^n - F_{i+1/2}^n\right)$$

Splitting $q(\rho)$ at the critical density $\rho_c$ defines upstream kinematic Demand $D(\rho)$ and downstream Supply $S(\rho)$:

$$D(\rho) = \begin{cases} q(\rho) & 0 \le \rho \le \rho_c \\ q_{\max} & \rho_c < \rho \le \rho_{\max} \end{cases}, \qquad S(\rho) = \begin{cases} q_{\max} & 0 \le \rho \le \rho_c \\ q(\rho) & \rho_c < \rho \le \rho_{\max} \end{cases}$$
Proposition 2 (Equivalence to the Exact Riemann Flux) For any interface Riemann problem $(\rho_L, \rho_R)$ with strictly concave flux $q(\rho)$, the exact Godunov flux is algebraically equivalent to the minimum of upstream demand and downstream supply: $$F_{\text{God}}(\rho_L, \rho_R) = \min\big(D(\rho_L),\, S(\rho_R)\big)$$ Under the CFL condition $\Delta t \le \Delta x / v_f$, the scheme preserves $\rho_i^n \in [0, \rho_{\max}]$.
Python Implementation — Vectorised Godunov Demand–Supply Solver [Show / Hide Code] 
import numpy as np

def demand(rho: np.ndarray, vf: float, rho_max: float) -> np.ndarray:
    rho_c = 0.5 * rho_max
    q_max = 0.25 * vf * rho_max
    q = vf * rho * (1.0 - rho / rho_max)
    return np.where(rho <= rho_c, q, q_max)

def supply(rho: np.ndarray, vf: float, rho_max: float) -> np.ndarray:
    rho_c = 0.5 * rho_max
    q_max = 0.25 * vf * rho_max
    q = vf * rho * (1.0 - rho / rho_max)
    return np.where(rho <= rho_c, q_max, q)

def godunov_step(rho: np.ndarray, dx: float, dt: float, vf: float, rho_max: float,
                 q_in: float, s_out: float) -> np.ndarray:
    d = demand(rho, vf, rho_max)
    s = supply(rho, vf, rho_max)
    flux = np.empty(len(rho) + 1)
    flux[0] = min(q_in, s[0])
    flux[1:-1] = np.minimum(d[:-1], s[1:])
    flux[-1] = min(d[-1], s_out)
    return rho + (dt / dx) * (flux[:-1] - flux[1:])

4. Shared-Table Q-Learning, Sensor Priors & Multi-Agent Scaling

Across signalised grids of 1 to 36 junctions ($1\times 1$ to $6\times 6$), independent tabular controllers would suffer exponential joint state-space growth ($96^{36}$). Instead, all junctions share a single Q-table $Q(s, a)$ over a compressed 96-state phase-relative representation:

$$s_t = \big(\text{bin}(\bar{\rho}_{\text{green}}) \in \{0..3\},\; \text{bin}(\bar{\rho}_{\text{red}}) \in \{0..3\},\; \text{bin}(\tau_{\text{elapsed}}) \in \{0..2\},\; \mathbb{I}_{\text{spillback}} \in \{0,1\}\big), \qquad |\mathcal{S}| = 96$$

The controller is trained on network-wide flux rewards and initialised with sensor-informed priors to accelerate cold-start convergence. Benchmarked against both sensor-actuated and fixed-time control over 6 held-out demand seeds per load:

Grid Size Junctions Medium Load TTS vs Actuated Heavy Load TTS vs Actuated Peak Junction Flux Gain
1×11−7.5%+9.5%+0.8%
2×24−10.3%−15.8%+1.7%
3×39−15.4%−10.2%+2.2%
4×416−19.4%−17.0%+2.9%
6×636−16.4%−17.0%+2.6%

Scaling & Multi-Agent Constraints: The efficiency gain of the RL system over baseline methods scales positively with network size and complexity—cutting total time spent by 7–19% at medium load on grids of $2\times 2$ and up, and raising junction flux by up to 2.9%—while identifying partial observability and multi-agent credit assignment as constraints on multi-agent scaling.