Introduction
A city can be divided into many small regions. The inflow and outflow of a region are the number of vehicles that have entered and left the region, respectively.
The traffic condition of each region is predicted based on the inflow and outflow of the region.
Important Factors of Predicting Traffic Condition
Spatial Dependencies
- Outflows of its nearby and distant regions
- Inflow of its own
Multiple Temporal Dependencies
Short, middle, long tern intervals
- Traffic congestion occurring now will affect the following hours
- Rush hour pattern repeats
External Factors
Special events
- vehicle accidents
- road maintenance
- weather conditions
Problem Definition
Citywide Region
A city is divided into an $I \times J$ grid map based on the longitude and latitude where a grid denotes a region.
Historical Traffic Status
The whole time span T is spliced as time intervals $T=1,2,\dots,t-1$.
Citywide Vehicle Flow
For a grid $(i,j)$, the inflow and outflow of the vehicles at the time interval $t$ are defined as
$$
\begin{gather}
x_t^{in,i,j}=\sum_{T_r\in P}|{\lambda>1|g_{\lambda-1}\notin(i,j)\land g_\lambda \in(i,j)}| \
x_t^{out,i,j}=\sum_{T_r\in P}|{\lambda\ge1|g_\lambda\in(i,j)\land g_{\lambda+1} \notin(i,j)}|
\end{gather}
$$
$P$: a collection of trajactories at time interval $t$
$T_r: g_1\to g_2 \to,\dots,\to g_{|T_r|}$: a trajectory in $P$
$g_\lambda$: the geospatial coordination
$g_\lambda \in (i,j)$: $g_\lambda$ lies in grid (i,j)
Citywide Vehicle Flow Prediction
Predict the inflow and outflow at the next time interval t of the whole grid map of the city
MST3D Framework
Two components in MST3D
- Multiple 3D CNNs: closeness dependency and different periodic (daily, weekly) dependencies
- External branch: weather conditions, holiday and metadata(i.e., day of the week, weekday and weekend)
Data Modeling
Modeling Spatio-temporal Correlation with 3D volumes
Given a $I\times J$ grid map of a city, at the $t$ time interval, the traffic status can be represented by a tensor $X_t \in R^{i \times j \times 2}$, where $k =2$ denotes the inflow and outflow of traffic variables.
Given $h$ time segments, the traffic status of these time segments can be denoted as a tensor $V\in R^{h\times i\times j\times 2}$
Modeling Multiple Temporal Dependencies
The closeness fragment $[X_{t-l_c}, X_{t-(l_c-1)},\dots,X_{t-1}]$, can be constructed as a 3D volume $V_c\in R^{l_c\times i \times j \times 2}$
The preodic fragment $[X_{t-l_d \times d}, X_{t-(l_c-1)\times d},\dots,X_{t-1}]$, can be constructed as a 3D volume $V_d\in R^{l_d\times i \times j \times 2}$
$d$: the period span
Multiple 3D CNNs
The 3D volumes constructed in the modeling phase are then fed into corresponding 3D CNN branches of MST3D.
The closeness, daily, weekly branches are fused as:
$$
V_{fusion}=W_c\bigotimes V_c + W_d\bigotimes V_d + W_w \bigotimes V_w
$$
$V_{fusion}$: the fused features
$\bigotimes$: Hadmard product (element-wise multiplication for tensors)
$V_c, V_d. V_w$: the feature volumes extracted by closeness, daily, weekly branches
$W_c, W_d, W_w$: learnable parameters that adjust the degrees affected by different branches
Then, the fused feature $V_{fusion}$ is flattened into a vector $V_{mc}$.
External Branch
The paper focuses on the weather condition, holiday event, and metadata.
For the weather condition at future time interval $t$, we can use the forecasting weather condition at time interval $t$ or the approximately weather condition from historical weather data at time interval $t-1$.
We utilize two fully-connected layers upon $E_t$, the first layer as an embedding layer for each subfactor, the second layer as a reshape layer to map low to high dimensions as $V_{ext}$ the same shape with $V_{mc}$
The fused output $\hat{V}$ of the multiple 3D CNNs and the external components is defined as:
$$
\hat{V}=V_{mc} + V_{ext}
$$
Finally, the fused output $\hat{V}$ is connected with a fully-connected layer using Tanh function.
MST3D Algorithm
Question
- Road intersection network
- Special events (e.g. concerts, shows, sport competitions)