Highway traffic flow prediction model with multi-component spatial-temporal graph convolution networks

doi:10.21203/rs.3.rs-1439012/v1

Download PDF

Article

Highway traffic flow prediction model with multi-component spatial-temporal graph convolution networks

https://doi.org/10.21203/rs.3.rs-1439012/v1

This work is licensed under a CC BY 4.0 License

You are reading this latest preprint version

Highway traffic flow forecasting is highly nonlinear and complex, so it is technically and operationally difficult to predict traffic flow accurately. In order to accurately predict the traffic flow of highway and alleviate its traffic congestion, a multi-component spatial-temporal convolution network model (MCSGCN) based on deep learning is proposed. The characteristics of short-term, daily cycle and weekly cycle of traffic data is modeled through three components and each component effectively captures the spatial-temporal correlation of traffic data by using spatial dimensional graph convolution and time dimensional convolution at the same time. Then input the sample data into the integrated model to train and extract the characteristics of traffic flow data. Finally, the model is tested on Highway England in England and PEMS-BAY, a public data set of Highway traffic in California. It is known through the experimental results that the integrated deep learning model is better than the single model in predicting the traffic flow of highway. The accuracy of traffic flow prediction on weekdays is higher than that on holidays. The prediction effect of MCSGCN is better than the existing model of traffic flow prediction.

Traffic

Prediction model

Multi-component spatial-temporal GCN

PEMS-BAY

With the acceleration of highway construction and the increase of traffic mileage in various countries, the occurrence of highway congestion and traffic accidents not only brings inconvenience to people's travel, but also affects the development of regional economy. Although many app software such as Google map, ck map and A map have provided real-time traffic condition and prediction function, they fail to provide traffic flow prediction function after 12 hours or even longer. Forecasting the highway traffic flow one day, many days or one week in advance can not only assist the managers to deploy the traffic flow plan and make reasonable dredging decisions in advance, effectively alleviate the occurrence of highway congestion and traffic accidents, but also provide important reference for people's travel.

In the past decades, researchers in the field of traffic management have conducted continuous exploratory research on traffic flow prediction in different cities, and achieved fruitful research results. The research methods include historical mean (Schakelw et al. 2012), autoregressive integral moving average method (Dolgov et al. 2016) and time series method (LEE et al. 2017). Historical mean and autoregressive integral moving average method require that the data meet some assumptions, and the processing capacity of complex nonlinear traffic data is insufficient. Time series prediction model is limited to the prediction problem with relatively stable and linear data, which is difficult to meet the actual needs. Although the machine learning methods such as k-nearest neighbor and support vector machine can model complex data, their prediction effect mainly depends on feature engineering and expert experience. The idea of using K-nearest neighbor method is to predict by identifying similar traffic conditions (Van et al. 2012), while the idea of support vector machine method is to map low-dimensional nonlinear traffic data to high-dimensional space through kernel function for linear classification (Jeong et al. 2013). This kind of method can not consider the temporal and spatial correlation of traffic data at the same time. As deep learning has made a series of research achievements in the fields of speech recognition and image processing, some scholars have proposed to apply deep learning to spatial-temporal data prediction. For example, Zhang et al. (2018) designed ST-ResNET based on residual convolution unit to predict urban passenger flow. This method uses standard 2-dimensional and 3-dimensional network data as input, although the spatial-temporal characteristics of flow data can be extracted, it can not be used for traffic flow prediction of high-speed network with graph structure. Different from the traditional convolution neural network, graph convolution can directly realize the convolution operation on the data of graph structure. At present, the mainstream graph convolution methods include spatial method and spectral method, in which, the spatial method directly applies the convolution kernel to the nodes and their neighborhoods on the graph. The core of this method is how to select the neighborhoods of nodes. Niepert et al. (2016) heuristic linear selection neighborhood for the central node, mapped the central node into a vector for convolution to heuristic linear selection neighborhood. Li et al. (2018) introduced graph convolution in human action recognition task, and proposed a variety of partition strategies to divide the neighborhood of nodes into different subsets. By controlling the number of subsets, different nodes can share the convolution kernel weight. In recent years, with the explosive growth of traffic spatial-temporal big data, the problems of high dimension, dynamics and nonlinear correlation faced by data modeling have become increasingly prominent (Ning et al. 2021), and more and more scholars have proposed traffic flow prediction models based on deep learning. For example, Lv et al. (2015) proposed a traffic flow prediction method based on deep learning, which uses a stacked automatic encoder model to learn the deep-seated features and spatial-temporal correlation in traffic flow data. However, the above model does not consider multi-inherent characteristics such as periodicity and trend of traffic data in time dimension. Huang et al. (2014) applied the deep learning method in traffic flow research, incorporated multi-task learning into the deep learning architecture, and verified its prediction performance better than the traditional model through experiments. Sutskever et al. (2014) proposed a general end-to-end sequence learning method, which proposed that a simple and direct model can also realize effective machine translation. Venugopalan et al. (2015) proposed a sequence to sequence model to generate video subtitles, comparing with the traditional model, this model has better performance in the task of image subtitle generation. Kuznetsov et al. (2018) deeply analyzed the time series prediction framework based on sequence to sequence deep learning, and compared its experimental performance with the classical time series method. Tao et al. (2021) proposed a diffusion convolutional recurrent neural network (DCRNN) based on encoder and decoder, and the deep learning framework of traffic flow prediction can learn the deep spatial-temporal dependence characteristics.

Considering that graph convolution can directly extract the features of graph structure data and automatically mine the spatial patterns of traffic data, meanwhile convolution along the time axis can fully mine the temporal patterns of traffic data, the feature description and spatial-temporal correlation of graph structure spatial-temporal data are analyzed in this paper. A Highway traffic flow prediction model based on deep learning–Multi-component Spatial-temporal Graph Convolution Networks (MCSGCN) model is proposed. The model describes the temporal and spatial characteristics of highway traffic data through three components: short-term, daily cycle and weekly cycle. Finally, the output of components is fused to obtain the desired prediction results, and the method can effectively capture the temporal and spatial characteristics of the data and solve the problem of highway traffic flow prediction when processed traffic network graph structure data.

The overall architecture of the multi-component spatial-temporal graph convolution network (MCSGCN) model proposed in this paper consists of three parts: spatial convolution GCN, temporal Convolution and fully connected FC. Firstly, the model preprocesses the traffic flow data of each expressway and constructs 2-dimensional characteristic matrices of spatial-temporal and meteorological factors. Next, the constructed 2-dimensional feature matrix are used to extract the spatial characteristics of traffic flow through GCN, and then a layer of Convolution is used to extract the time characteristics of traffic flow. Finally, the final prediction results are obtained through full-connection layer FC.

2.1 Problem Definition

Road network structure can be regarded as a topology structure with two-way roads as nodes. The figure can be defined as $G(V,\varepsilon )$, where V represents the node set of N bidirectional road sections in the city and $V=\{ {v_1},{v_{\text{2}}}, \ldots ,{v_N}\}$.${v_N}$ indicates the two-way road section numbered N.$\varepsilon$represents the set of edges and join N nodes in the diagram. The connection relation between nodes is represented by adjacency matrix $A \in {{\mathbb{R}}^{N \times N}}$.Where A[i,j] represents the connection relation between section v_i and v_j, i and j represent the row and column number of the matrix, and also represent the number of the road. If v_i and v_j are adjacent, then A[i,j] is 1, otherwise 0, and thus the adjacency matrix A is symmetric. The traffic flow data is regarded as the signal sequence of the time graph on the graph, such as the traffic flow data v_i of road i at time t, where v_i,t represents the signal value of node v_i at time t, The traffic flow data is regarded as the time graph signal sequence on the graph. For example, the traffic flow data v_i,t of road i at time t represents the signal value of node v_i at time t, and the traffic flow data ${X_t} \in {{\mathbb{R}}^{N \times 1}}$ of urban road network at time t is regarded as the graph signal. Assuming that the number of nodes and adjacency relationship remain unchanged, the traffic flow data of the city can be expressed as graph signal sequence (as shown in Fig. 1), ${t_n}$ represents the observation time, ${X_{{t_n}}}$ represents the traffic flow data of the city at ${t_n}$ time.

2.2 Model Construction

In order to solve the problem of missing data of highway traffic flow and meteorological data, linear interpolation is adopted as the missing filling method in this paper. Because linear interpolation can keep the gradual trend of data and is suitable for data sets with small continuous missing length.

In order to ensure the reliability of the predicted results, it is necessary to normalize the data to eliminate the dimensionality between different attributes. In this paper, min-max method (e.g. Eq. 1) is adopted to perform linear transformation on the original data, and then the data are mapped uniformly to the interval [0,1].

$$v_{i}^{'}=\frac{{{v_i} - {v_{\hbox{min} }}}}{{{v_{\hbox{max} }} - {v_{\hbox{min} }}}}$$

InEq. (1), v_i represents the i^th original data, $v_{i}^{'}$ represents the new data after normalization, v_min represents the minimum value, v_max represents the maximum value. Considering the possible influence of meteorological conditions, festival activities and other external factors on traffic flow prediction results, Pearson correlation analysis should be conducted between attributes in the data to select relevant features according to the size of correlation coefficient.

The change of current highway traffic flow is closely related to the historical traffic flow, upstream and downstream traffic flow and meteorological change of this section. Therefore, a 2-dimensional characteristic matrix containing spatial-temporal attributes and meteorological factors are constructed, as shown in Eq. 2:

$$\left[ \begin{gathered} {v_{{s_1},t - \Delta t}} {v_{s{\text{2}},t - \Delta t}} ... {v_{{s_m},t - \Delta t}} {w_{{q_1},t - \Delta t}} ... {w_{{q_n},t - \Delta t}} \hfill \\ {v_{{s_1},t - (\Delta t - 1)}} {v_{s{\text{2}},t - (\Delta t - 1)}} ... {v_{{s_m},t - (\Delta t - 1)}} {w_{{q_1},t - (\Delta t - 1)}} ... {w_{{q_n},t - (\Delta t - 1)}} \hfill \\ ... ... ... ... ... ... ... \hfill \\ {v_{{s_1},t - 1}} {v_{s{\text{2}},t - 1}} ... {v_{{s_m},t - 1}} {w_{{q_1},t - 1}} ... {w_{{q_n},t - 1}} \hfill \\ \end{gathered} \right]$$

In formula 2,{${v_{{s_1},t}} {v_{s{\text{2}},t}} ... {v_{{s_m},t}}$} represents the traffic flow data at time t. In which, ${v_{{s_m},t}}$represents the traffic flow data of the m^th target station s_m at time t;{${w_{{q_1},t}} {w_{{q_2},t}} ... {w_{{q_n},t}}$} represents the meteorological data of at time t;${w_{{q_n},t}}$represents the data volume of the n^th meteorological attribute q_n at time t;$\Delta t$represents the window size;${v_{{s_m},t - \Delta t}}$represents the traffic flow data of the station s_m in$\Delta t$time statistical units at the current time; ${w_{{q_1},t - \Delta t}}$ represents the time data of $\Delta t$time statistical units at the current time about weather attribute q₁.

2.3 DQN algorithm in combined action space

Considering that the action space output by DQN (Andres et al. 2017) (Deep Q-learning Networks) is discrete, and an output layer node is used to evaluate each possible action combination. The network complexity will increase exponentially with the increase of the action dimension. The algorithm cannot be realized due to a sharp increase of the output layer scale of DQN, when the volume of dynamic guidance information is large in a complex weather environment. On the basis of DQN, this paper proposes "priority experience replay" method, which uses TD (calculate temporal difference, TD) error to distinguish the priority of samples in the experience pool.

On the network structure, DQN processes image input by using a multi-layer convolutional neural network, and then connects to a multi-layer fully connected neural network. Each neuron in the output layer corresponds to a possible combination of discrete actions. For the mutually independent components in the work, the total action space is the Cartesian product of every independent action space. When the action space has n mutually independent dimensions and each dimension has m discrete actions, DQN network needs mⁿ output layer nodes to correspond to the value of Q (s, a) in different actions of the output state s. Therefore, as the number of independent actions increases, the complexity of the DQN network structure grows at an exponential rate, meanwhile, too many output layers also lead to low sample utilization and difficulty in updating network parameters. Considering these problems, this paper proposes the combined space DQN based on Combinatorial Space (CS-DQN). For mutually independent action dimensions, each dimension corresponds to a group of nodes in the output layer of the Q function network, and each group contains all discrete actions in this dimension. This change can be viewed as setting a respective value function Q_d (s, a^(d);$\theta$)for each action dimension d, and they share the same network parameters. At this time, the number of nodes in the network output layer is the sum of the number of discrete actions in each dimension, and its growth rate decreases from exponential growth to linear growth with the growth rate of the number of independent actions.

In CS-DQN, action a_t=(a_t⁽¹⁾, a_t⁽²⁾,…,a_t^(D)) is D-dimensional combined action vector. For each dimension, the agent chooses actions by greedy strategy.

$$a_{t}^{{(d)}}=\arg \mathop {\hbox{max} }\limits_{a} {Q_d}({s_t},a;\theta )$$

For a sample ${e_t}=({s_t},{a_t},{r_t},{s_{t+1}})$, define the TD error in each dimension.

$$\delta _{t}^{{(d)}}={r_t}+\gamma \mathop {\hbox{max} }\limits_{a} {Q_d}({s_{t+1}},a;{\theta ^ - }) - {Q_d}({s_t},a_{t}^{{(d)}};\theta )$$

Combining with using the current Q network to select t + 1, TD error can be further defined as follow:

$$\delta _{t}^{{(d)}}={r_t}+\gamma {Q_d}({s_{t+1}},\arg \mathop {\hbox{max} }\limits_{a} {Q_d}({s_{t+1}},a;\theta );{\theta ^ - }) - {Q_d}({s_t},a_{t}^{{(d)}};\theta )$$

The a set of samples B={e₁,e₂,…,e_t} are sampled from the experience pool and the loss function of the neural network is defined as the arithmetic mean of the square error loss.

$$L(\theta )={E_B}(\frac{1}{D}\sum\limits_{d} {{{(\delta _{t}^{{(d)}})}^2}} )$$

The neural network is trained by error back propagation algorithm according to the loss function defined in Eq. 6. For each sample, each dimension of the action has an output layer node selected and participates in the calculation of TD error and the back propagation of network error, then a total of D output layer nodes can be updated. Compared with DQN, each sample can only update one output layer node, CS-DQN method improves the utilization efficiency of the samples.

In order to obtain sufficient time dimension information and reduce the cost of processing irrelevant historical information, this paper proposes the overall framework of the multi-component spatial-temporal graph convolution (MCSGCN) network. Which is used to describe the recent characteristics, daily cycle characteristics and weekly cycle characteristics of the predicted target (GCN: spatial dimensional graph convolution; Conv: temporal dimensional convolution; FC: fully connected). For example, to predict the traffic volume of a certain highway section at 10:00, the traffic data within 1 hour before 10:00 (9:00–10:00), the traffic data corresponding to 1 day ago and 1 week ago at 10:00 will provide useful information for the prediction problem.

Suppose that the sampling frequency is q times a day, that is, q data points are included in the time series every day. It is supposed that the current moment is t₀, the length of the time window to be predicted is T_p, and three time series fragments of length T_h, T_d, T_w are intercepted along the time axis as the input of the three components of the model's recent, daily cycles and weekly cycles, as shown in Fig. 2 (suppose the prediction period length T_p is 1 hour, T_h, T_d and T_w are all 2 times of T_p), where T_h, T_d and T_w are all integer multiples of T_p, and the three time series fragments are as follows:

(1) Recent clips

${\chi _h}=({X_{{t_0} - {T_h}+1}},{X_{{t_0} - {T_h}+2}},...,{X_{{t_0}}}) \in {{\mathbb{R}}^{F \times N \times {T_h}}}$ , that is, a historical time series segment directly adjacent to the forecast period, as shown in the green part in Fig. 2.

(2) Daily cycle fragment

$${\chi _d}=({X_{{t_0} - ({T_d}/{T_p}) \times q+1}},...,{X_{{t_0} - ({T_d}/{T_p}) \times q+{T_p}}},{X_{{t_0} - ({T_d}/{T_p} - 1) \times q+1}},...,{X_{{t_0} - ({T_d}/{T_p} - 1) \times q+{T_p}}},...,{X_{{t_0} - q+1}},...,{X_{{t_0} - q+{T_p}}}) \in {{\mathbb{R}}^{F \times N \times {T_d}}}$$

It is composed of sequence fragments that are the same as the prediction target period several days before the prediction period, as shown in the red part in Fig. 2. Due to the influence of morning and evening peak cycles, people's daily routines and other factors, traffic data has a strong similarity at the same time of the day. The purpose of the daily cycle component is to model the cycle pattern of traffic data in days.

(3) Weekly cycles fragment

${\chi _w}=({X_{{t_0} - 7 \times ({T_w}/{T_p}) \times q+1}},...,{X_{{t_0} - 7 \times ({T_w}/{T_p}) \times q+{T_p}}},{X_{{t_0} - 7 \times ({T_w}/{T_p} - 1) \times q+1}},...,{X_{{t_0} - 7 \times ({T_w}/{T_p} - 1) \times q+{T_p}}},...,{X_{{t_0} - 7 \times q+1}},...,{X_{{t_0} - 7 \times q+{T_p}}}) \in {{\mathbb{R}}^{F \times N \times {T_w}}}$

It is composed of sequence fragments with the same attributes and the same period as the prediction target week in the weeks before the prediction period, as shown in the blue part in Fig. 2. There are obvious weekly cycle patterns in traffic flow data. For example, the traffic pattern on Monday is similar to the traffic pattern on Monday in history, but may be different from the traffic pattern on weekends. The purpose of the weekly cycle component is to model the changing law of the traffic data with a weekly cycle.

The three components share the same network structure and consist of a spatial-temporal convolution module (Fig. 3) and a fully connected layer. Among them, the spatial-temporal convolution module includes two parts: the graph convolution in the spatial dimension and the standard 2-dimensional convolution in the time dimension. The model finally fuses the output results of the three components based on the parameter matrix to obtain the final prediction result. This structure can effectively capture the time and space characteristics of traffic data and its spatial-temporal correlation.

3.1 Spatial dimensional graph convolution

The model adopts the spectrogram method (Briand et al. 2017) to extend the convolution operation to graph structured data, treats the data as signals on the graph, and then processes the graph signals directly on the graph to capture meaningful patterns and features in the space. The spectrogram method mainly analyzes the graph structure by transforming the graph into an algebraic form. In this paper, the connection relation and mutual influence between nodes in the graph structure are used. In spectrogram theory, a graph is represented by its corresponding Laplace matrix, and the properties of the graph structure are obtained by analyzing the Laplace matrix and its characteristics. The Laplace matrix of the graph is defined as L = D-A, and its normalized form can be expressed as $L={I_N} - {D^{ - \frac{1}{2}}}A{D^{ - \frac{1}{2}}} \in {{\mathbb{R}}^{N \times N}}$, where A is the adjacency matrix, IN is the identity matrix, and degree matrix $D \in {{\mathbb{R}}^{N \times N}}$ is the diagonal matrix composed of node degrees, ${D_{ii}}=\sum\nolimits_{j} {{A_{ij}}}$. The Eigenvalue decomposition of the Laplacian matrix is $L=U\Lambda {U^T}$, where $\Lambda =diag([{\lambda _o},...,{\lambda _{N - 1}}]) \in {{\mathbb{R}}^{N \times N}}$ is the diagonal matrix of the eigenvalues of L, and U is the Fourier basis. Taking the traffic data at time t as an example, the graph signal is $x={x^f} \in {{\mathbb{R}}^N}$, the Fourier transform of the graph signal can be expressed as $\widehat{x}={U}^{T}x$. According to the properties of the Laplace matrix, U is an orthogonal matrix, and therefore the inverse Fourier transform $x=U\widehat{x}.$ Graph convolution is a convolution operation achieved by using linear operators defined in the Fourier domain diagonalized to equivalently replace classical convolution operators, and the convolution kernel ${g_\theta }$ is used to carry out the convolution operation on graph G.

$${g_{\theta \times G}}x={g_\theta }(L)x={g_\theta }(U\Lambda {U^T})x=U{g_\theta }(\Lambda ){U^T}x$$

Since the convolution operation of the graph signal followed by the Fourier transform is equal to the product of the Fourier transform of these signals, the above equation can be understood as taking the Fourier transform of ${g_\theta }$ and x to the spectral domain respectively. Then multiply the results of the transformation of the two, and take the inverse Fourier transform to get the result of the convolution operation. Graph convolution is the transformation of a graph into a spectral domain to achieve convolution on a graph. However, when the scale of the graph is large, it is expensive to directly decompose the Eigenvalue of the Laplace matrix, so this paper adopts Chebyshev polynomial approximate expansion to solve this problem:

$${g_{\theta \times G}}x={g_\theta }(L)x \approx \sum\limits_{{k=0}}^{{K - 1}} {{\theta _k}{T_k}(\tilde {L})x}$$

${\theta _k} \in {{\mathbb{R}}^K}$ is the Chebyshev polynomial coefficient.$\tilde {L}=\frac{2}{{{\lambda _{\hbox{max} }}}}L - {I_N}$,${\lambda _{\hbox{max} }}$ represents the maximum eigenvalue of the Laplace matrix. Recursive definition of Chebyshev polynomials:${T_k}(x)=2x{T_{k - 1}}(x) - {T_{k - 2}}(x)$, in which,${T_0}(x)=1,{T_1}(x)=x$. Using Chebyshev polynomial to expand the solution approximately is equivalent to use convolution kernel to extract the neighbor information of order 0 ~ K-1 around the center of each node in the graph.

Graph convolution module uses linear correction unit (ReLU) as activation function, that is$\operatorname{Re} LU({g_{\theta \times G}}x)$.

Taking K = 2 as an example, the neighbor information of order 0 ~ 1 is extracted for each node, and the eigenvalues of the Laplacian matrix are scaled to make${\lambda _{\hbox{max} }}=2$. The above graph convolution operation is expressed as:

$${g_{\theta \times G}}x \approx {\theta _0}{T_0}(\tilde {L})x+{\theta _1}{T_1}(\tilde {L})x={\theta _0}x+{\theta _1}(L - {I_N})x={\theta _0}x+{\theta _1}( - {D^{ - \frac{1}{2}}}A{D^{ - \frac{1}{2}}})x$$

In order to reduce the number of parameters, let${\theta _0}= - {\theta _1}=\theta \in {\mathbb{R}}$, then${g_{\theta \times G}}x \approx ({I_N}+{D^{ - \frac{1}{2}}}A{D^{ - \frac{1}{2}}})x\theta$, all nodes on the graph share convolution kernel weight $\theta$.At the same time, to avoid numerical instability, gradient explosion or gradient disappearance, let $\tilde {A}=A+{I_N},{\tilde {D}_{ii}}=\sum\nolimits_{j} {{{\tilde {A}}_{ij}}}$, then get ${g_{\theta \times G}}x={\tilde {D}^{ - \frac{1}{2}}}\tilde {A}{\tilde {D}^{ - \frac{1}{2}}}x\theta$ .Expanding to multidimensional data, the input data for layer r convolution is

$$\chi _{h}^{{(r - 1)}}=({X^{1,(r - 1)}},{X^{2,(r - 1)}},...,{X^{{C_{r - 1}},(r - 1)}}) \in {{\mathbb{R}}^{{C_{r - 1}} \times N \times {T_{r - 1}}}}$$

where$r \in \{ 1,...,l\}$(l is the number of space-time convolution layers); C_r−1 is the number of channels for input data of layer r network, when r = 1, C₀ = F; T_r−1 is the time dimension length of the input data. When r = 1, the recent component T₀ = T_h (T₀ = T_d for daily periodic component, T₀ = T_w for weekly periodic component). Performing graph convolution for $\chi _{h}^{{(r - 1)}}$, it can be expressed as ${g_{\Theta \times G}}\chi _{h}^{{(r - 1)}}={\tilde {D}^{ - \frac{1}{2}}}\tilde {A}{\tilde {D}^{ - \frac{1}{2}}}\chi _{h}^{{(r - 1)}}\Theta$, in which, $\Theta =({\Theta _1},{\Theta _2},...,{\Theta _{{C_r}}}) \in {{\mathbb{R}}^{1 \times {C_{r - 1}} \times {C_r}}}$ is the convolution kernel parameter.

3.2 Time dimensional graph convolution

After modeling the spatial features of the input data by spatial convolution operation, the temporal features are captured by standard 2-dimensional convolution. Using linear modified unit activation function to extract recent features as an example, getting $\chi _{h}^{{(r)}}=ReLU(\psi \times (ReLU({g_{\Theta \times G}}\chi _{h}^{{(r - 1)}}))) \in {{\mathbb{R}}^{{C_r} \times N \times {T_r}}}$($\psi$is the parameter of the time-dimension convolution kernel), the specific convolution process is shown in Fig. 2.

After a layer of time dimension convolution, the information of the node is updated by the information of its adjacent time slices, and the information of the node and its adjacent time slices already contains the information of its adjacent nodes at the same time after the graph convolution operation. Therefore, after a layer of spatial-temporal convolution operation, the temporal and spatial dimension characteristics and spatial-temporal correlation of data will be captured. In this paper, multi-layer spatial-temporal convolution is used to extract the further information of spatial-temporal dimension, and then the results of spatial-temporal convolution are consistent with the predicted target dimension through full connection operation. The full connection module also uses linear correction unit as activation function.

3.3 Multi component fusion

For the fusion output of short-term, daily cycle and weekly cycle components, taking the flow prediction at 8:30 a.m. on Monday as an example, the law on morning and evening peak cycle of some highway sections is obvious, and the daily cycle and weekly cycle components have a great impact on the prediction results; some highway sections have no obvious traffic cycle law, and its daily cycle and weekly cycle components are of little help to the prediction target. Therefore, different nodes are affected differently by different components, and the degree of influence is also different when fusing the output results of different components. After learning the historical data, the final prediction result after fusion is shown as follows:

$$\hat {Y}={W_h} \odot {\hat {Y}_h}+{W_d} \odot {\hat {Y}_d}+{W_w} \odot {\hat {Y}_w}$$

In which,$\odot$ is the Hadamard product multiplied by the corresponding elements of the matrix; w_h, w_d, w_w are learning parameters, which reflect the influence of three time dimension characteristics of short-time, daily cycle and weekly cycle on the prediction target.

In order to test the performance of the proposed model, experiments are carried out based on two real urban traffic data sets, and the traffic flow prediction performance and effectiveness of the model are verified by comparing with the classical shallow learning model and benchmark deep learning model.

4.1 Selection of data set

The first data set comes from the Highway England Dataset (Lin et al. 2018), which publishes traffic flow data information about two types of major highway networks in England, including all trunk highway networks and localized highway networks. This data set collects the average traffic time, traffic speed and traffic flow information every 15mi and the time range of the data set is Jan 1, 2013 to Feb 28, 2014. The second data set comes from PEMS-BAY (Liu et al. 2017) of California Highway in United States. The data set collects the characteristic information of three dimensions with time stamp every 5min, such as traffic flow, average speed and average lane occupancy. It contains 4135 detectors of 29 highways. The time range is Jul 1,2018 to Aug 31, 2018. The first 52 days are used as the training set, and the last 10 days are used as the testing set.

4.2 Comparison model and parameter setting

Mean square error (RMSE) and mean absolute error (MAE) are used as evaluation indexes in this paper. The proposed MCSGCN is compared with VAR (vector autoregressive model) (Ning et al. 2021), ARIMA (autoregressive integral moving average method) (Langkvist et al. 2014), SVR (Tao et al. 2020) (support vector regression method, two kernel functions are used in this paper, namely LINEAR and RBF), RNN (recurrent neural networks) (Sun et al. 2014), LSTM (Feng et al. 2019) (long-term and short-term memory network),GRU (Liu et al. 2019) (gated cyclic unit network), ConvLSTM (Lin et al. 2018) (convolutional LSTM), STGCN (spatial-temporal graph convolution model) (Tao et al. 2018) and GCGRU (gated cyclic unit network and graph convolution network combination method) (Wang et al. 2014).

$$RMSE=\sqrt {\frac{1}{n}\sum\limits_{{i=1}}^{n} {{{({x_i} - {{\hat {x}}_i})}^2}} }$$

$$MAE=\frac{1}{n}\sum\limits_{{i - 1}}^{n} {|{x_i} - {{\hat {x}}_i}|}$$

The MCSGCN is designed based on Pytorch framework, and the graph convolution uses 32 convolution kernels of the same size. Time-dimensional convolution also uses 32 convolution kernels of the same size. The dimension of convolution kernels is 1 along the space axis and 3 along the time axis. The length of time dimension is adjusted by controlling step size. The number of training iterations is 100, the batch size is 96, the neuron discarding rate of each layer is 0.3, and the learning rate parameter is 0.01, the default number of neural network layers of the benchmark deep learning model is 1, and the number of neurons in each hidden layer is 100. The input data length of the three components will affect the experimental results. After experimental verification, the best combination of different periods is set as T_h=3, T_d=1, T_w=1. Considering that the mean square error can reflect the difference between the estimator and the estimator, this paper takes it as the loss function.

4.4 Experimental comparison and analysis

Firstly, the experimental analysis and evaluation of the Highway England traffic flow data set is conducted (the results are shown in Table 2). In the table, the traffic flow prediction errors RMSE and MAE of MCSGCN model and benchmark model under multiple specific time steps t + 1, t + 3, t + 6 and t + 12 are given. It can be seen from Table 2 that MCSGCN model is superior to other benchmark comparison models in multi-step traffic flow prediction performance. Compared with the benchmark shallow learning model and deep learning model, the MCSGCN model can maintain the lowest RMSE and MAE prediction errors whenever the prediction time step size is 3(t + 3) or 12 (t + 12).The experimental results also show that the prediction performance of the benchmark deep learning model is apparently better than that of the traditional shallow learning method.

The experimental results show that the choice of prediction time step has a great influence on the prediction performance of the model. As shown in Table 2, the prediction performance of the model under the condition of long time step is better than that under the condition of short time step, because each time step prediction in the model needs to consider the prediction result of the previous time step. With the increase of the prediction time step, the prediction errors of the previous time step model will gradually accumulate, resulting in more and more prediction errors of the whole model. But it can be seen from the experimental results that comparing with the benchmark depth model and shallow model, the MCSGCN model can keep the lowest prediction error under different prediction time step conditions.

Table 1

Comparison of the Prediction Error of Different Models
Model Type	Models	RMSE				MAE
Model Type	Models	t + 1	t + 3	t + 6	t + 12	t + 1	t + 3	t + 6	t + 12
Shallow Learning Models	VAR	16.47	16.56	20.92	30.95	11.58	12.12	13.96	18.86
	ARIMA	14.40	19.06	28.31	36.65	10.24	13.63	19.87	25.31
	SVR-LINEAR	15.38	33.50	49.91	97.75	12.70	28.15	37.17	78.19
	SVR-RBF	18.42	22.54	28.64	38.62	14.22	17.68	22.49	28.25
Baseline Deep Learning Models	RNN	11.36	14.67	20.09	30.32	8.29	10.86	14.63	20.85
	GRU	10.79	14.23	20.47	33.59	7.80	10.26	14.18	20.69
	LSTM	10.81	13.56	19.83	30.95	7.96	9.65	13.45	18.92
	ConvLSTM	10.95	14.51	19.03	29.95	8.07	10.59	13.01	19.76
Deep Learning Models	STGCN	10.94	14.48	19.02	28.90	8.06	10.51	12.94	19.06
	GCGRU	10.67	13.84	18.70	27.76	8.04	10.35	11.97	17.45
	MCSGCN	10.52	13.47	18.01	27.29	8.03	10.05	11.49	16.92

In order to further compare the prediction performance of MCSGCN and other benchmark modles under different time steps, this paper analyzes and shows the traffic flow predicion performance of different models in one working day (96 time steps, each time step interval is 15min), with different prediction time steps. It also shows the comparison in one week (672 time steps, each time step interval is 15min). Figure 4 and Fig. 5 show the prediction in one working day and one week respectively, and compare the traffic flow values and predition traffic flow curves oberserved bySVR-RBF, RNN and MCSGCN. Where the X coordinate represents the obervation time step and Y coordinate represents the traffic flow value of this time step. It can seen from the comparison of the two curves that the prediction performance of MCSGCN is better than the shallow model represented by SVR-RBF and the deep learning model representd by RNN,whether in a working day or in a week. Whether on weekdays or weekends, as shown in Fig. 5, the prediction performance of MCSGCN can remain optimal, especially in the time range of peak and trough of traffic flow. Figure 4 and Fig. 5 both show that the prediction performance of RNN is better than that of SVR-RBF. With the increase of prediction time step, the predicion performance of shallow learning model will decrease significantly, while MCSGCN and benchmark deep learning model can maintain stable performance. The analysis of the above experimental results show that the multi-step prediction performance of MCSGCN on Highway England data set under different time step prediction conditions is better than the benchmark shallow learning model and deep learning model.

In this paper, the researchers continue to compare the multi-step prediction performance of different models on PEMS-BAY data set. Table 2 described prediction results of MCSGCN in the next 1h on data sets PEMSD4 and PEMSD8, and compared them with seven benchmark methods.

Table 2

Performance comparison of different approaches on the PeMSD4 and PeMSD8 dataset
Model	PeMSD4		PeMSD8
Model	RMSE	MAE	RMSE	MAE
VAR	54.14	36.76	43.03	29.52
ARIMA	68.13	32.11	44.30	24.04
SVR-LINEAR	108.61	73.36	90.72	59.08
SVR-RBF	70.05	33.89	45.95	31.05
RNN	45.60	28.98	36.74	22.91
GRU	45.82	29.45	39.96	23.18
LSTM	45.11	28.65	35.95	22.20
ConvLSTM	45.23	28.03	34.67	21.62
STGCN	38.29	25.15	27.87	18.88
GCGRU	37.25	25.00	30.24	20.69
MCSGCN	35.64	22.73	26.47	17.47

It can be seen from the data in Table 2 that the MCSGCN model proposed in this paper, including the spatial-temporal graph convolution mechanism, achieves the best performance in both the RMSE and MAE evaluation indicators. Due to the limitation of modeling ability, the forecast results of several other time series methods are not very satisfactory. In the data set PeMSD4, the optimal values of the two indicators proposed of the model in this paper are 35.64 and 22.73 respectively, and the value of the better GCGRU model is reduced by 4.3% and 9.1% respectively. In the data set PeMSD8, the optimal values of the two indicators of the proposed model are 26.47 and 17.47 respectively, and the values of the better STGCN model are reduced by 5% and 7.5% respectively. It can be seen from Table 2 that the difficulty of prediction increases with the increase of the prediction duration, and the overall error is on the rise. Regardless of the data set PeMSD4 or PeMSD8, the MCSGCN model has obtained good prediction results in the short-term prediction. The results show that the strategy of combining multi-component and spatial-temporal graph convolution can fully mine the spatiotemporal pattern of the data, and with the increase of the prediction time, the prediction error of the proposed model in this paper grows more slowly than other models. The reason is that the MCSGCN explicitly models a variety of periodic characteristics in the time dimension, which shows more obvious advantages in medium and long-term forecasts.

In order to further analyze and compare the prediction performance of the MCSGCN and the benchmark method on the PEMS-BAY data set, as shown in Fig. 6. The horizontal axis represents the observed time step, and the vertical axis represents the traffic sequence value. It is described the traffic flow prediction error of the SVR-RBF, RNN, and MCSGCN models under the conditions of single-step prediction t + 1 and multi-step prediction t + 6 in Fig. 6. It can be seen from the figure that the MCSGCN can maintain the optimal prediction performance under different time step predictions, and the predicted value curve can be well matched with the true value curve. The prediction performance of the MCSGCN is better than the shallow model represented by SVR-RBF and the benchmark deep learning model represented by RNN, no matter in the peak or trough period. As the prediction time step increases, the prediction performance of the SVR-RBF model and RNN model declines sharply, but the decline in the prediction performance of the MCSGCN is slower than that of the SVR and RNN, which can better maintain better traffic flow forecast accuracy. Different deep learning models have relatively small performance differences under the condition of single-step prediction, while under the condition of long-step prediction, the performance advantage of the MCSGCN model is more obvious.

According to the analysis of experimental results on two real traffic flow data sets, the MCSGCN proposed in this paper, whose predicted value can keep a good match with the real value and has better prediction performance comparing with the benchmark model and the current updated model, no matter under the condition of single-step prediction or long-term multi-step prediction. Moreover, the prediction error of this model is lower than that of the benchmark model under various time step prediction. It is verified that the MCSGCN could effectively learn the deep nonlinear correlation characteristics and spatial-temporal dependence characteristics of multivariable traffic flow related spatial-temporal series data.

Accurate prediction of highway traffic flow can not only provide decision-making aid for expressway managers, but also provide reference for the selection of routes for the public to travel, so as to alleviate expressway traffic congestion. Aiming at the two key challenges of traffic flow prediction, this paper proposes an integrated deep learning multi-component spatial-temporal graph convolution network MCSGCN. This model not only considers the spatial-temporal correlation characteristics of traffic flow data, but also combines graph convolution and standard convolution to construct spatial-temporal convolution blocks to capture the spatial-temporal characteristics of traffic data. Experimental results on two real traffic flow data sets show that the integrated deep learning MCSGCN is better than other existing traffic data prediction models, and the model can explore and learn the implicit spatial-temporal dependence characteristics and nonlinear correlation characteristics of multi-variable traffic sequence data.

The proposed model is also suitable for processing other spatial-temporal traffic data based on graph structure representation. In the next step, more traffic accident or extreme weather event data will be considered, and the model will be further studied and improved to realize the effective prediction of long-term multi-step urban traffic flow under extreme weather in the future, so as to further improve the more complex traffic flow prediction.

ACKNOWLEDGMENT

This work is partially supported by Research Project on Economic and Social Development of Liaoning Province (2022lsljdybkt-014), Science and technology innovation fund program of Dalian (2021JJ13SN81) and major theoretical and practical problems in social science circles of Shaanxi Province (20yj-39).

Declaration of Interest statement

☒ The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Andres M., Nair R.. A predictive-control framework to address bus bunching. Transportation Research Part B, 2017, 104: 123-148.
Briand, E. Come, M. Trepanier and L. Analyzing year-to-year changes in public transport passenger behavior using smart card data. Transportation Research Part C, 2017, 79: 274-289.
Brunal J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs. In: Proc. Of the ICLR, 2014.
Dolgov D. Google self-driving car project monthly report. Mountain View: Google, 2016.
Feng Ning, Guo Shengnan, Song Chao, et al. Multi-component spatial-temporal graph convolution networks for traffic flow forecasting. Journal of Software, 2019, 30(3): 759-769.
Huang Wenhao, Song Guojie, Hong Haikun, et al. Deep architecture for traffic flow prediction: deep belief networks with multitask learning. IEEE Transactions on Intelligent Transportation System, 2014, 15(5): 2191-2201.
Jeong YS, Byon YJ, Castro-Neto MM, et al. Supervised weighting-online learning algorithm for short-term traffic flow prediction. IEEE Trans on Intelligent Transportation Systems, 2013, 14(4): 1700-1707.
Kuznetsov V, Mariet Z. Foundations of sequence to sequence modeling for time series. arXiv preprint arXiv:1805. 03714, 2018.
LEE N, CHOI W, VERNAZA P, et al. Desire: Distant future prediction in dynamic scenes with interacting agents. IEEE. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. New York: IEEE, 2017: 336-345.
Li C, Cui Z, Zheng W, et al. Spatio-temporal graph convolution for skeleton based action recognition. In: Proc. Of the AAAI, 2018.
Langkvist.M, Karlsson L, and Loutfi A. A review of unsupervised feature learning and deep learning fro time-series modeling. Pattern Recognition Letters, 2014, 42: 11-24.
Lin L., He Z., Petta, S., Predicting station-level hourly demand in a large-scale bike-sharing network:Ａgraph convolutional neural network approach. Transportation Research Part C, 2018, 97: 258-276.
Liu L.J., Chen R C. A novel passenger flow prediction model using deep learning methods. Transportation Research Part C: Emerging Technologies, 2017, 84: 74-91.
Liu Jiexi, Chen Songcan. Non-stationary multivariate time series prediction with MIX gated unit. Journal of Computer Research and Development, 2019, 56(8): 1642-1651.
Lv Yisheng, Duan Yanjie, Kang Wenwen, et al. Traffic flow prediction with big data: a deep learning approach. IEEE Transaction on Intelligent Transportation System, 2015, 16(2): 865-873.
Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs. In: Proc. Of the ICML, 2016: 2014-2023.
Ning T, An L, Duan XD, “Optimization of cold chain distribution path of fresh agriculture products under caorbon tax mechanism: A case study in China”.Journal of Intelligent and Fuzzy System, vol.40, no.6, pp.10549-10558, 2021.
Ning T, An L, Duan XD, “Optimization of cold chain distribution path of fresh agriculture products under caorbon tax mechanism: A case study in China”.Journal of Intelligent and Fuzzy System, vol.40, no.6, pp.10549-10558, 2021.
Schakelw J, Knoop V L, VAN A B. Integrated lane change model with relaxation and synchronization. Transportation Research Record, 2012, 2316(1): 47-57.
Su Weixing, Zhu Yunlong, Liu Fang, et al. Outliers and change-points detection algorithm for time seriese. Journal of Computer Research and Development, 2014, 51(4): 781-788.
Sutskever I, Vinyals O, Le Q V. Sequence to sequence learning with neural networks. Proc of the 2014 Advances in Neural Information Processing Systems, Montreal, Piscataway, NJ: IEEE, 2014: 3104-3112.
Tao N, Shasha Shi, Peng Z, et al. “Distribution management decision model for VRPDP under changes of customer distribution demand”. Journal of Ambient Intelligent and Humanized Computing, vol.2, no.2, pp.2053-2063, 2021.
Tao Ning, Zi Wang, Peng Zhang, et al. Integrated optimization of disruption management and scheduling for reducing carbon flow in manufacturing. Journal of Cleaner Production, 2020, 263(1): 83-91.
T Ning, XP Wang, Xiangpei Hu, et al. Disruption Management Optimal Scheduling for Logistics Distribution Based on Prospect Theory. Control and Decision. 2018, 33(11), 2064-2068.
Van Lint H, Van Hinsbergen C. Short-term traffic and travel time prediction models. Transportation Research E-circular, 2012,22(1): 22-41.
Venugopalan S, Rohrbach M, Donahue J, et al. Sequence to sequence to text. Proc of the Int Conf on Computer Vision. Piscataway, NJ: IEEE, 2015: 4534-4542.
Wang Jingyuan, Li Chao, Xiong Zhang, et al. Survey of data-centric smart city. Journal of Computer Research and Development, 2014, 51(2): 239-259.
Zhang J, Zheng Y, Qi D, et al. Predicting citywide crowd flows using deep spatio-temporal residual networks. Artificial Intelligence, 2018, 259: 147-166.

No competing interests reported.

Download PDF

Editorial decision: Major revision
05 May, 2022
Reviews received at journal
24 Mar, 2022
Reviewers agreed at journal
14 Mar, 2022
Reviewers invited by journal
14 Mar, 2022
Editor assigned by journal
14 Mar, 2022
Editor invited by journal
11 Mar, 2022
Submission checks completed at journal
11 Mar, 2022
First submitted to journal
10 Mar, 2022

You are reading this latest preprint version

Highway traffic flow prediction model with multi-component spatial-temporal graph convolution networks

Status:

Version 1

Abstract

Figures

1. Introduction

2. Prediction Model Of Integrated Deep Learning

2.1 Problem Definition

2.2 Model Construction

2.3 DQN algorithm in combined action space

3. Multi Component Spatial-temporal Convolution Network

3.1 Spatial dimensional graph convolution

3.2 Time dimensional graph convolution

3.3 Multi component fusion

4. Experimental Example

4.1 Selection of data set

4.2 Comparison model and parameter setting

4.4 Experimental comparison and analysis

5. Conclusion

Declarations

References

Additional Declarations

Status:

Version 1