Overview

GPS positions

\(\downarrow\)

Travel times

\(\downarrow\)

Network state

\(\downarrow\)

Arrival time distributions

\(\downarrow\)

ETAs

Part One
GPS positions\(\downarrow\)travel times

Real-time vehicle locations

• Auckland Transport provides API for real-time data
• Vehicle locations: GPS coordinates of buses/trains
• Trip updates: arrival/departure times at bus stops
• Over 1000 buses operating at peak
• Target: ETAs updated every 30 seconds

Vehicle state

• Unknown vehicle state \(\boldsymbol{x}_k = [x_k, \dot x_k]^\top\), at time \(t_k\)
  • \(x_k\): distance travelled along route, meters
  • \(\dot x_k\): speed, meters per second
• Observable state \(\boldsymbol{y}_k = h(\boldsymbol{x}_k) + \boldsymbol{\epsilon}_k\)

Particle filter

• Approximate vehicle state using sample of \(N\) particles
  \[ p(\boldsymbol{x}_{k-1} | \boldsymbol{y}_{1:k-1}) \approx \sum_{i=1}^N \boldsymbol{w}_{k-1}^{(i)} \delta_{\boldsymbol{x}_{k-1}^{(i)}}(\boldsymbol{x}_{k-1}) \]
  • \(\boldsymbol{x}_{k-1}^{(i)}\): state (distance, velocity) of particle \(i\)
  • \(\boldsymbol{w}_{k-1}^{(i)}\): weight of particle \(i\)
  • \(\delta_{x^{(i)}}(x)\): Dirac measure

Particle filter ii

• Vehicle transition function, \(f\)
  • Acceleration/deceleration
  • Bus stop behaviour
  • Traffic lights, etc.
    \[ \boldsymbol{x}_k^{(i)} = f(\boldsymbol{x}_{k-1}^{(i)}, \sigma_x^2, ...) \]
• Predicts new state before observing latest position
  \[ p(\boldsymbol{x}_{k} | \boldsymbol{x}_{k-1}) \approx \sum_{i=1}^N \boldsymbol{w}_{k-1}^{(i)} \delta_{\boldsymbol{x}_k^{(i)}}(\boldsymbol{x}_{k}) \]

Particle filter iii

• Update using likelihood function
• Distance (squared) between particle and observation
• Measurement error \(\epsilon^2\) = GPS error (meters)
  \[ d\left(\boldsymbol{y}_k, h(\boldsymbol{x}_k^{(i)})\right)^2 \sim Exp\left(\frac{1}{2\epsilon^2}\right) \]

Particle filter iv

• Update vehicle state by reweighting particles

\[ \boldsymbol{w}_k^{(i)} = \frac{\boldsymbol{w}_{k-1}^{(i)} p(\boldsymbol{y}_k | \boldsymbol{x}_k^{(i)})}{\sum_{j=1}^N \boldsymbol{w}_{k-1}^{(j)} p(\boldsymbol{y}_k | \boldsymbol{x}_k^{(j)})} \]

\[ p(\boldsymbol{x}_k | \boldsymbol{y}_{1:k}) \approx \sum_{i=1}^N \boldsymbol{w}_{k}^{(i)} \delta_{\boldsymbol{x}_k^{(i)}}(\boldsymbol{x}_{k}) \]

Estimating travel times

• Estimated once vehicle has completed each segment
  • \(T_j^{(i)}\): travel time particle \(i\), segment \(j\)
  • Computed in transition function
• Posterior estimate of travel time
  \[ p(T_j | \boldsymbol{y}_{1:k}) \approx \sum_{i=1}^N \boldsymbol{w}_{k}^{(i)} \delta_{T_j^{(i)}}(T_{j}) \]

Part Two
Travel times\(\downarrow\)Network state

Transit road network

• road network consists of all \(M\) road segments
• estimate of traffic flows (as travel times)
• combines data from different routes

Network state

• travel time (seconds) of buses along roads at time \(t_c\)
  \[ \Theta_c = [ \theta_{1c}, \theta_{2c}, \cdots, \theta_{Mc} ]^\top \]
• summarize by mean and variance
  \[ \hat\Theta_{c|c} = \mathrm{E}(\Theta_c | T_{1:c}) \] \[ \Sigma_{c|c} = \mathrm{Var}(\Theta_c | T_{1:c}) \]

Information filter

• alternate form of Kalman filter
• replace mean and variance by
  • information matrix \[ \mathbf{P}_{c-1|c-1} = \Sigma_{c-1|c-1}^{-1} \]
  • information vector \[ \boldsymbol{p}_{c-1|c-1} = \Sigma_{c-1|c-1}^{-1}\hat\Theta_{c-1|c-1} \]
• easy handling of multiple observations
  • buses tend to clump together

Information filter ii

• predict next state
  • travel times constant over short (30 sec) intervals
  • system noise \(\rho^2\) (s/s)
    \[ \begin{split} \hat\Theta_{c|c-1} &= \hat\Theta_{c-1|c-1} \\ \Sigma_{c|c-1} &= \Sigma_{c-1|c-1} + \mathbf{I} \rho^2 \end{split} \]
• update road segments independently
  • avoid inverting large matrices
  • not observing correlations

Information filter iii

• \(L_c^j\) buses completing segment \(j\) at time \(t_c\)
• observation and measurement error for each
  \[ \begin{split} z_c^{j\ell} &= \mathrm{E}(T_j^\ell | \boldsymbol{y}_{1:k}^\ell) \\ R_c^{j\ell} &= \max\{\mathrm{Var}(T_j^\ell | \boldsymbol{y}_{1:k}^\ell), R_\text{min}\} \end{split} \]
• transform to information space
  \[ \begin{split} {I}_c^{j\ell} &= ({R}_c^{j\ell})^{-1} \\ {i}_c^{j\ell} &= ({R}_c^{j\ell})^{-1} {z}_c^{j\ell} \end{split} \]

Information filter iv

• update state by adding information
  \[ \begin{split} (\mathbf{P}_{c|c})_{jj} &= (\mathbf{P}_{c|c-1})_{jj} + \sum_\ell {I}_{c}^{j\ell} \\ (\boldsymbol{p}_{c|c})_j &= (\boldsymbol{p}_{c|c-1})_j + \sum_\ell {i}_{c}^{j\ell} \end{split} \]
• back transform for state parameters

Network state prediction

• use historical data to forecast (e.g., 10 mins ahead)
• include correlations between adjacent segments

Part Three
Network state\(\downarrow\)Arrival time distrutions

Predicting arrival time

• when will the bus arrive at stop \(m\) given
  • latest estimate of position/speed
  • current network state (traffic conditions)
• uncertainty from
  • position/speed estimate
  • traffic conditions now and in the near future
  • dwell time at stops (can be zero)
  • traffic lights, random traffic fluctuations, …

Reprise the particle filter

• for each particle, run transition function \(f'\)
  • sample travel times from \(\Theta_c\)
  • continue to end of route
  • \(A_m^{(i)}\): particle arrival time at stop \(m\)

\[ p(A_m | \boldsymbol{x}_k, \Theta_c) \approx \sum_{i=1}^N \boldsymbol{w}_{k}^{(i)} \delta_{A_{m}^{(i)}}(A_m) \]

Maybe not …

• requires simulating \(N \times M_\text{remaining}\) arrival times
• for upwards of 1000 buses at peak times
• every 30 seconds …

(Work in progress)

• use particle filter to estimate next \(M'\) stops
• predict remaining travel time using normal theory
• allow uncertainty to converge to prior (historical data)

Part Four
Arrival time distrutions\(\downarrow\)ETAs

Arrival time distribution

• we have a distribution
  \[ p(A_j | \boldsymbol{x}_k, \Theta_c) \]
• need to summarize it for the general public

Point estimates

• expected
• easy to communicate
• infrastrature exists (real-time boards, etc)

Point estimates ii

• assumes ETA is exact (it’s not)
• underestimate = frustration, hard to plan journey
• overestimate = shorter wait OR miss bus entirely

• mean? median? some quantile?
• minimise \(p(A_j \notin [\hat A_j, \hat A_j+1)), A_j \in 0, 1, 2, \ldots\)
• … stronger penalty on overestimation?

Point estimates iii

• desirable that \(A_j\) decreases with time
• Kalman filter on arrival times? at least for > 10 mins

Prediction intervals

• unfamiliar to the general public
• allows uncertainty to be expressed
  • at least \(\ell_j\) mins away, could be up to \(u_j\) mins
• what values?
  • quantiles of predictive distribution?
  • min \(p(A_j \notin [\ell_j, u_j])\) constrained by \((u_j - \ell_j)^2\)

end.