# Online Traffic Accident Spatial-Temporal Post-Impact Prediction Model on Highways Based on Spiking Neural Networks

Authors: Duowei Li; Jianping Wu; Depin Peng
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

Traffic accident management as an approach to improve public security and reduce economic losses has received public attention for a long time, among which traffic accidents post-impact prediction (TAPIP) is one of the most important procedures. However, existing systems and methodologies for TAPIP are insufficient for addressing the problem. The drawbacks include ignoring the recovery process after clearance and failing to make comprehensive prediction in both time and space domain. To this end, we build a 3-stage TAPIP model on highways, using the technology of spiking neural networks (SNNs) and convolutional neural networks (CNNs). By dividing the accident lifetime into two phases, i.e., clean-up phase and recovery phase, the model extracts characteristics in each phase and achieves prediction of spatial-temporal post-impact variables (e.g., clean-up time, recovery time, and accumulative queue length). The framework takes advantage of SNNs to efficiently capture accident spatial-temporal features and CNNs to precisely represent the traffic environment. Integrated with an adaptation and updating mechanism, the whole system works autonomously in an online manner that continues to self-improve during usage. By testing with a new dataset CASTA pertaining to California statewide traffic accidents on highways collected in four years, we prove that the proposed model achieves higher prediction accuracy than other methods (e.g., KNN, shockwave theory, and ANNs). This work is the introduction of SNNs in the traffic accident prediction domain and also a complete description of post-impact in the whole accident lifetime.


---

## Body

## 1. Introduction

People’s living standards have increased all over the world, leading to an increase in the ownership of private vehicles [1]. While private vehicles have improved people’s traveling experience, they have also contributed to several traffic problems, where traffic safety is one of the main concerns. According to statistical data released by World Health Organization in 2004, road traffic accidents are among the main causes of deaths and injuries all over the world, leading to 1.2 million deaths and 50 million injuries each year [2]. In 2019, the number of traffic accidents in China was 248,000, and the direct property loss was as high as 1.35 billion yuan (China Statistical Yearbook).Besides the costs of fatalities and injuries, indirect effects brought by traffic accidents such as congestion and energy consumption also have tremendous impacts on socioeconomic development. Typically, accident congestion can spread rapidly and even cause a chain breakdown in the entire system, especially in closed roads like highways. In severe cases, the delays of clearance for an accident may increase the occurrence probability of a secondary accident [3]. In 1988, the total extra travel time and fuel consumption caused by traffic congestion, both regular and occasional, in 50 major cities in the United States was estimated at 35 billion U.S. dollars [4].Traffic accident management (TAM) is of great importance to government and transportation agencies, which can not only improve public security but also reduce economic losses. There are usually two main tasks in TAM: analysis and prediction. By analyzing the features of historical accident records, accident prediction can be realized to foresee the time and place of the accident in advance. Furthermore, traffic accidents post-impact prediction (TAPIP) is also an essential part in TAM but have not caught enough attention. When an accident occurs, if the spatial and temporal impact scope can be quickly determined, then the transportation agency can induce vehicles to avoid unnecessary congestion, and travelers can also plan their routes in advance.The lifetime of a traffic accident is usually divided into five phases, namely, detection, verification, response, clearance, and recovery [5]. Most TAPIP-related research studies till now concentrate only on the first four phases, which means the duration from accident occurrence to the reopening of all blocked traffic lanes. The existing research studies use traffic wave theory, regression model, and other methods to analyze the influence of various factors on accident indicators, but have not established a complete relationship between the influencing factors and the spatial-temporal impact of the accidents. Furthermore, the clearance is never the end of an accident, and the process that the traffic gradually recovers to normal conditions cannot be ignored. For the convenience of expression, this work proposes a two-phase accident lifetime. As shown in Figure 1, the four phases before clearance are grouped into clean-up phase, while the recovery phase remains unchanged. The reason for this division is that in the clean-up phase, at least one lane will be blocked, while after that, the whole lanes will be reopened.Figure 1
Two-phase traffic accident lifetime.As the third-generation neuron model, spiking neural networks (SNNs) [6] are closer to biological principle compared with other artificial neural networks (ANNs). Due to the advantage of being sensitive to spatial-temporal characteristics of information [7], SNNs already improve the traditional neural models on accuracy in many application areas. However, SNNs till now are rarely used in traffic domain and have even never been applied to accident prediction related research.This study proposes a traffic accident spatial-temporal post-impact prediction model on highways, using the technology of SNNs and CNNs. In the 3-stage model, the duration of clean-up phase (clean-up time) is first estimated, and then, several post-impact variables such as recovery time and accumulative queue length are predicted. Additional online stage is used to make adaptation and update the model. In this regard, the main contributions of this work can be summarized as follows:(1)
The development of a framework to predict post-impact in the complete accident lifetime, which contains the recovery process.(2)
The prediction of highway accident post-impact in both spatial and temporal domain, and the outputs are specific and effective variables that can help both transportation agencies and travelers.(3)
The first use of SNNs in the traffic accident prediction domain and the implementation of encoding the traffic spatial-temporal features into time spikes.(4)
The processing of a new highway spatial-temporal traffic accident dataset CASTA and the use of it in testing the performance of the proposed model.(5)
The proposal of an online adaptation and updating method to revise the error and modify the model, for self-improvement during usage.The rest of this study is organized as follows. Section2 describes literature review on SNNs and TAPIP. Section 3 defines the general framework of the 3-stage prediction model, including the specific input, output, and structure of SNNs and CNNs. The processing of the new dataset is introduced in Section 4, and Section 5 presents the experiment results. Finally, Section 6 provides concluding statements on our work.


## 2. Literature Review

### 2.1. Spiking Neural Networks in Traffic Domain

With the rapid development of artificial intelligence and computer technology, deep learning has been widely applied in traffic domain, including traffic state prediction [8, 9], traffic signal control [1, 10], and driving model development [11].The works mentioned above are all based on artificial neural networks (ANNs), where the neurons use differentiable, nonlinear activation functions. Although ANNs have achieved great performance in wide areas including classification, pattern recognition, and prediction, they are fundamentally different in structure, neural computations, and learning rule compared to the brain [7]. The way of information propagation between units is one of the most obvious differences. While ANNs rely on 32 bit or 64 bit continuous messages sent between units [12], the neurons in biological brain broadcast trains of action potentials, also known as spike trains to downstream neurons. As the third-generation neuron model, spiking neural networks (SNNs) are close to biological principle by utilizing spikes. When dealing with complex or large datasets, while ANNs face the concern of huge computational consumption, SNNs achieve energy efficiency since output spike trains can be made sparse in time [13]. Besides that, SNNs improve the traditional neural models on accuracy due to the advantage of being sensitive to the spatial-temporal characteristics of information [7]. Although still in the early stages of development, SNNs have become the focus of many application areas and made progress in visual processing [12], speech recognition [14], and medical diagnosis [15].However, SNNs till now are rarely used in traffic domain, despite their specialized capability in representing spatial-temporal data. Laña et al. [16] presents an approach for spatial-temporal road traffic forecasting that relies on the adoption of the NeuCube architecture based on SNNs. Taking advantages of the NeuCube platform, this work focuses on the spatially-aware traffic variable forecasts and on the exploration of the spatial-temporal relationships among different sensor locations within a traffic network. In another work of Laña et al. [17], an evolving spiking neural networks (eSNNs) based adaptive long-term traffic state estimation model is proposed. By using similarity-based clustering of daily traffic volume data and monitoring them in real time, the model encodes traffic data into spikes over the time domain effectively and achieves high accuracy in online prediction when new data samples arrive.


### 2.2. Post-Impact Prediction of Traffic Accident

At present, the main research methods in predicting the impact of highway accidents are the traffic wave theory [18, 19], vehicle arriving-departure model [20, 21], regression model [22, 23], decision tree model [5], and ANNs [23, 24]. Yu et al. [18] analyzed the accumulation and dissipation process of the accident location on two-lane highway, using the shockwave theory as a foundation, and finally estimated the spatial-temporal impact of the accident. However, such methods based on theoretical analysis considered only limited influencing factors (flow and density of upstream) and only showed general laws that lead to poor applicability. Zhu et al. [23] established two kinds of forecasting models of spatial-temporal impact for traffic accidents based on nonlinear regression and BP neural networks, where the influence of factors were analyzed such as upstream flowrate, ratio of cargos, and accident handling time. The results showed that the BP neural network achieves higher accuracy. Lin and Li [24] embedded three machine learning algorithms in a hierarchical scheme to perform sequential prediction. The result outperformed others by achieving a MAPE range of 5.5–53.8%. However, it just considered the time duration of an accident rather than spatial impact. In contrast, Lee et al. [25] only focused on estimation of vehicle accident queue length using the ANN model with relatively abundant influencing factors.The methods above theoretically described and inferred the characteristics of incidental accidents and analyzed the influence of various factors on accident indicators. But they have not established a complete relationship model between the influencing factors and the spatial-temporal impact of the accidents. Furthermore, related works all used one model to output all prediction variables regardless of the characteristics in different phases of accidents. However, the five phases are closely related and can have great influence on each other. Thus, in order to fully capture the spatial-temporal features in the whole process, the prediction should be made separately according to the order of phase.Since the prediction of accident impact highly relies on feature extraction of spatial and temporal data, SNNs are considered to be a more suitable method due to its characteristics compared with the models mentioned above. However, no such SNNs-related models have been proposed till now.


## 2.1. Spiking Neural Networks in Traffic Domain

With the rapid development of artificial intelligence and computer technology, deep learning has been widely applied in traffic domain, including traffic state prediction [8, 9], traffic signal control [1, 10], and driving model development [11].The works mentioned above are all based on artificial neural networks (ANNs), where the neurons use differentiable, nonlinear activation functions. Although ANNs have achieved great performance in wide areas including classification, pattern recognition, and prediction, they are fundamentally different in structure, neural computations, and learning rule compared to the brain [7]. The way of information propagation between units is one of the most obvious differences. While ANNs rely on 32 bit or 64 bit continuous messages sent between units [12], the neurons in biological brain broadcast trains of action potentials, also known as spike trains to downstream neurons. As the third-generation neuron model, spiking neural networks (SNNs) are close to biological principle by utilizing spikes. When dealing with complex or large datasets, while ANNs face the concern of huge computational consumption, SNNs achieve energy efficiency since output spike trains can be made sparse in time [13]. Besides that, SNNs improve the traditional neural models on accuracy due to the advantage of being sensitive to the spatial-temporal characteristics of information [7]. Although still in the early stages of development, SNNs have become the focus of many application areas and made progress in visual processing [12], speech recognition [14], and medical diagnosis [15].However, SNNs till now are rarely used in traffic domain, despite their specialized capability in representing spatial-temporal data. Laña et al. [16] presents an approach for spatial-temporal road traffic forecasting that relies on the adoption of the NeuCube architecture based on SNNs. Taking advantages of the NeuCube platform, this work focuses on the spatially-aware traffic variable forecasts and on the exploration of the spatial-temporal relationships among different sensor locations within a traffic network. In another work of Laña et al. [17], an evolving spiking neural networks (eSNNs) based adaptive long-term traffic state estimation model is proposed. By using similarity-based clustering of daily traffic volume data and monitoring them in real time, the model encodes traffic data into spikes over the time domain effectively and achieves high accuracy in online prediction when new data samples arrive.


## 2.2. Post-Impact Prediction of Traffic Accident

At present, the main research methods in predicting the impact of highway accidents are the traffic wave theory [18, 19], vehicle arriving-departure model [20, 21], regression model [22, 23], decision tree model [5], and ANNs [23, 24]. Yu et al. [18] analyzed the accumulation and dissipation process of the accident location on two-lane highway, using the shockwave theory as a foundation, and finally estimated the spatial-temporal impact of the accident. However, such methods based on theoretical analysis considered only limited influencing factors (flow and density of upstream) and only showed general laws that lead to poor applicability. Zhu et al. [23] established two kinds of forecasting models of spatial-temporal impact for traffic accidents based on nonlinear regression and BP neural networks, where the influence of factors were analyzed such as upstream flowrate, ratio of cargos, and accident handling time. The results showed that the BP neural network achieves higher accuracy. Lin and Li [24] embedded three machine learning algorithms in a hierarchical scheme to perform sequential prediction. The result outperformed others by achieving a MAPE range of 5.5–53.8%. However, it just considered the time duration of an accident rather than spatial impact. In contrast, Lee et al. [25] only focused on estimation of vehicle accident queue length using the ANN model with relatively abundant influencing factors.The methods above theoretically described and inferred the characteristics of incidental accidents and analyzed the influence of various factors on accident indicators. But they have not established a complete relationship model between the influencing factors and the spatial-temporal impact of the accidents. Furthermore, related works all used one model to output all prediction variables regardless of the characteristics in different phases of accidents. However, the five phases are closely related and can have great influence on each other. Thus, in order to fully capture the spatial-temporal features in the whole process, the prediction should be made separately according to the order of phase.Since the prediction of accident impact highly relies on feature extraction of spatial and temporal data, SNNs are considered to be a more suitable method due to its characteristics compared with the models mentioned above. However, no such SNNs-related models have been proposed till now.


## 3. Methodology

This work proposes a spatial-temporal post-impact prediction model of traffic accidents. The 3-stage process is shown in Figures2 and 3, where Figure 2 corresponds to the training process using historic accident records (training set) and Figure 3 corresponds to the predicting process using new accident records (test set). Stage 1 is the prediction of accident clean-up time; it uses clusters to define length hierarchy of clean-up time and then extract accident features to train the SNNs classifier. Stage 2 concerns with a prediction model of spatial-temporal impact based on CNNs and backpropagation neural networks (BPNNs), feeds with flow and speed data, and outputs the recovery time and accumulative queue length. When a new accident record comes to the model after being processed with the above two stages, another online updating stage will be promoted to correct error and revise model. The notations used frequently in the 3-stage model are given in Table 1.Figure 2
3-stage model for accident post-impact prediction–training process.Figure 3
3-stage model for accident post-impact prediction–predicting process.Table 1
Notations.
NotationMeaningUnitsCAThe actual cluster that the clean-up time of an accident belongs to—CPThe predicted cluster that the clean-up time of an accident belongs to—TclAThe actual clean-up timeMinuteTclPThe predicted clean-up timeMinuteLclAThe actual accumulative queue length in the clean-up phaseMileLclPThe predicted accumulative queue length in the clean-up phaseMileLmaxAThe actual maximum accumulative queue lengthMileLmaxPThe predicted maximum accumulative queue lengthMileLaveAThe actual average accumulative queue lengthMileLavePThe predicted average accumulative queue lengthMileTfrAThe actual full-recovery timeMinuteTfrPThe predicted full-recovery timeMinuteThrAThe actual half-recovery timeMinuteThrPThe predicted half-recovery timeMinute


### 3.1. Stage 1: Accident Clean-Up Time Prediction

According to the two-phase accident lifetime defined in Section1, phases are not completely independent and can influence each other. Therefore, in order to figure out the spatial-temporal impact in the whole process, we need to predict the duration of clean-up phase first.Mean-shift clustering is first performed on the clean-up time, which groups the clean-up time into several intervals. Thus, the accidents with similar cleaning difficulty are labeled as a cluster. Furthermore, the accident records with attributes and corresponding class labels are input to train an SNNs classifier. Whenever a new accident record comes in, the accident attributes are extracted and then classified using the trained classifier. The predicting clean-up time is represented by the centroid value of its corresponding cluster.


#### 3.1.1. Clustering Using Mean-Shift

According to the statistics in Section4, the clean-up time of the accidents distributes unevenly throughout the interval. It exists the case where some of the interval lack records. Thus, to improve the prediction accuracy and remove exceptional, clustering the clean-up time into groups and using the centroid value to present the predicted value is better than a direct prediction model.The mean-shift algorithm [26] is chosen to cluster the clean-up time for two main reasons: it does not require a predefined number of clusters; and such density-based algorithms are less affected by the mean value compared with the K-means algorithm. The key operation of the algorithm is to calculate the drift vector of the centroid through the data density change in the region of data, so as to move the centroid in the next iteration until it reaches the maximum density. Algorithm 1 shows the procedure of clustering the traffic records according to the clean-up time. The bandwidth is set as 10.Algorithm 1: Mean-shift clustering of clean-up time.
(1)
Input(2)
Tc≔ dataset of clean-up time over which the procedure is performed(3)
Initialization(4)
r≔ the radius of a region(5)
d≔ the minimum distance between clusters(6)
Fi,Cj≔ probability that point i belongs to Cluster Cj(7)
Repeat(8)
Randomly select an unvisited point from the dataset as the starting centre pointoc(9)
Repeat(10)
Find all the points that appear in the circle⊙oc,r and group into cluster Coc(11)
For pointiin Coc, Fi,Coc←Fi,Coc+1(12)
Calculate the shift vector ofoc as Mc=1/K∑xi∈Cxi−oc(13)
Updateoc towards the shift vector as oc←oc+Mc(14)
UntilMc reaches minimum threshold(15)
If∃Coi,distanceCoc,Coi<d, then merge Coc and Coi(16)
Else, labelCoc as a new cluster(17)
Until all points are visited(18)
For pointi in Tc, i belongs to cluster C with maximum probability Fi,C=maxCjFi,Cj(19)
Output(20)
Coc≔ all clusters(21)
CTc≔ clusters that each point in Tc belongs to


#### 3.1.2. Accident Characterization

When a new accident record comes to the model, in order to predict the clean-up time, the cluster that the records belongs to needs to be figured out. Thus, a number of attributes that represent the characteristics of accidents are used to train a classifier, which outputs the corresponding cluster.In a previous work, three kinds of attributes are usually extracted to demonstrate the accident: accident information (e.g. accident type [24, 25, 27–29], blocked area size [5, 25], number of vehicles involved [5, 25, 28], and casualties [5, 25, 29]), spatial-temporal attributes (e.g. lane location [25, 27, 29], road type [24, 25], and time [5, 24, 25, 27–29]), and weather information (e.g. humidity [24, 25, 28], wind [24, 25], and visibility [24, 25]). In this model, considering the dataset used, 6 attributes are selected as the input in this stage:(i)
Block lanes: a number between 1 and 6 represents the number of lanes blocked by the accident. The value is determined according to TMC event code [30].(ii)
Block distance: a value represents the length of road blocked by the accident in miles.(iii)
Day or night: a binary digit, where 0 represents daytime while 1 represents night.(iv)
Workday or not: a binary digit, where 0 represents workday while 1 represents holiday or weekend.(v)
Peak hour or not: a number between 0 and 2, where 0 represents morning peak (8 a.m.–10 a.m.), 1 represents evening peak (4 p.m.–6 p.m.), and 2 represents the normal period [31].(vi)
Weather condition: a number between 0 and 4, which represents sunny/rain/snow/thunderstorm/fog, respectively, when accident happens.More detailed information of data processing can be found in Section4.


#### 3.1.3. Classification Using SNNs

A classifier is trained to match the accident attributes to the cluster it belongs to. Due to the characteristics of being sensitive to the spatial-temporal features, SNNs are applied in building the classifier. It is the first time of applying SNNs in traffic accident prediction domain.After being first proposed in 1997 by Maass [6], SNNs have attracted researchers to explore different research directions. The main technique directions of SNNs can be concluded in four main categories: encoding and decoding of spiritual information, neuron models and network simulation strategy, similarity measurement of spiking sequence, and synaptic weight learning rules [32].The classification problem in this work concerns with the supervised learning in SNNs, which refers to finding a suitable synaptic weight matrix for a series of given input spike trains and target spike trains, so that the output of the neurons is as close as the corresponding target spike trains, that is, the error evaluation function of the two reaches minimum [33].(1) Leaky Integrate-and-Fire Neural Model. Neural computing relies on the construction of the spiking neuron model. In order to do numerical analysis, an efficient mathematical neural model should be built based on the geometry and electrical properties of neuron. Leaky Integrate-and-Fire neural (LIF) model [34], as the single compartment model with fixed threshold which has been widely used in neural computing, can directly describe the relationship between membrane potential V and input electric current I. When V is between the resting potential Vrest and the threshold Vthre, it is given by the following equation:(1)τmdVdt=−V−Vrest+RmI,where τm is a time constant, and I is the sum of current released by presynaptic neurons. Once V crosses Vthre from below, a spike is generated and V is reset to Vrest. The LIF model, with the advantages of using simple structure to realize accurate simulation of SNNs by event-driven simulation strategy, is chosen as the basic neuron model in our work.(2) Gaussian Tuning Curve Coding. In the biological neural system, spikes are transmitted between neurons with different combinations. The corresponding rules and mechanisms of conversion between the stimulation signal and the spike trains are called neural coding [35]. When neuron feels external stimuli, encoding module encodes the stimulation signal to specific spike trains and responses; in turn, decoding module can estimate the stimulation signal from spike trains.Researchers put forward various coding methods, which can be divided into two main categories: frequency-based coding [36] and time-based coding [37]. Evidence confirms that time-based coding is the more effective, since the time structure of the spike trains carries stimulus signals on a millisecond or even smaller scale, not just the average firing frequency [38]. With the introduction of more complex systems, single-neuron coding cannot effectively present the huge amount of information. Population coding [39] is thus proposed to solve complex information coding problem, where each neuron has a unique spike response distribution for a given stimulus, and the responses of the neuron population are combined to represent the overall information.The population coding method used in this model is Gaussian tuning curve coding [40], as shown in Figure 4. A neuron covers a certain range of analog quantity in the form of Gaussian function, while the height of the corresponding Gaussian function to a certain value of the analog quantity determines the time for the neuron to emit spike. In this work, a population containing six neurons is used to encode the six accident attributes mentioned above. Figure 4 shows an example of how “block distance” of 0.18 miles is encoded into spike trains 0.79,0.04,0.52,0.96,1.00,1.00ms.Figure 4
Accident attribute coding with Gaussian tuning curve. (a) The corresponding Gaussian curve of six neurons. (b) Firing time of six neurons.
(a)(b)(3) Multi-ReSuMe Training Algorithm. The supervised learning algorithm in SNNs can be divided into three categories based on the learning rules of synaptic weight: gradient-descent based method, synaptic plasticity-based method, and convolution-based method [41]. Gradient-descent based methods such as SpikeProp [40] learn from the error back propagation algorithm of traditional ANNs, where the state variables of the neuron model must have analytical expressions and lack biological realism. From a biological perspective, a training algorithm should update synaptic weights based on the temporal correlation of presynaptic and postsynaptic spikes, in keeping with the spike timing-dependent plasticity (STDP) theory [42]. In this work, a synaptic plasticity-based method called the multilayer remote supervised method (Multi-ReSuMe) [43] is used to train the classifier. Multi-ReSuMe extends the single-layer impulse neural network ReSuMe algorithm [41] to the multilayer network and overcomes some limitations as it can be applied to neurons firing multiple spikes, and it can in principle be applied to any linear neuron model.The main contribution of Multi-ReSuMe is the combination of the STDP and anti-STDP mechanism in one process, where synaptic weight update between hidden layerH and output layer O satisfies the following equation:(2)ddtwoht=1nhSht∫0∞apreSodt−Soatds+1nhSodt−Soata+∫0∞apostsSht−sds.For any excitatory synaptic connection from hidden neuronh to output neuron o, a synaptic strength woh is potentiated whenever a target spike Sodt is observed and depressed whenever the trained neuron fires Soat. Here, s denotes a delay between the presynaptic and postsynaptic firing times, where s=tof−thf. The role of the noncorrelative factor a in equation (2) is to adjust the average strength of the synaptic inputs so as to impose on a neuron a desired level of activity. The kernels apre and apost are STDP-related terms that define the shape of a learning window Ws [44],(3)Ws=apre−s=−A−⋅expsτ−,s≤0,aposts=+A+⋅exp−sτ+,s>0,where parameters A+,A−>0 are the amplitudes and τ+,τ−>0 are the time constants of the learning process. apre−s gives the weight change if the presynaptic spike (the spike of the hidden neuron occurs) comes after the postsynaptic spike (the spike of the output and target neurons), while aposts gives the weight change if the presynaptic spike comes before the postsynaptic spike [43].Similarly, synaptic weight update between input layerI and hidden layer H satisfies the following equation:(4)ddtwhit=1ninhSit∑o∈O∫0∞apreSodt−Soatwoh+1ninh∑o∈OSodt−Soata+∫0∞apostsSit−sdswoh.As Figure5 shows, the network has 36 input neurons corresponding to six accident attributes, and an output neuron representing the cluster that the input sample belongs to. The hidden layer contains 80 neurons which are fully connected with other layers. The output neuron’s spike train contains a single spike, where the timing differs from each other, as given in Table 2. The process of building and training a Multi-ReSuMe-based classifier is given in Algorithm 2. The parameters are initialized as follows: A+=1.2, A−=0.5, τ+=τ−=0.5, and a=0.05 [45].Figure 5
A Multi-ReSuMe-based SNNs classifier.Table 2
The target spike-time of output neuron corresponding to each cluster.
Cluster no.Output spike-time (ms)00112233⋮⋮nnAlgorithm 2: Multi-ReSuMe-based classifier.
(1)
Definition(2)
A≔ Historic accident dataset(3)
Ai≔ accident data in A where Ai=a1,a2,a3,a4,a5,a6,c(4)
etarget≔ the minimum value of network error to reach when learning is considered converged(5)
W≔ synaptic weight between all neurons(6)
M≔ maximum number of iterations(7)
Initialization(8)
W← Initial synaptic weight with random value θ∼U0.2,0.8(9)
For iteration = 1, M do(10)
ForAi∈A do(11)
EncodeAi=a1,a2,a3,a4,a5,a6,c to a series of spike trains Ai=Si1,Si2,Si3,Si4,Si5,Si6,Sod(12)
Set membrane potential of all neurons to the resting potential (set to 0)(13)
Pass input spike trains to the network and find actual output spikeSoa(14)
Calculate network erroreAi=1/2Sod−Soa2(15)
Compute weight modificationsΔW for all layers according to equation (2) and equation (4)(16)
Update synaptic weightW←W+ΔW(17)
End for(18)
Calculate summed network errore=∑eAi(19)
Whilee≥etarget


### 3.2. Stage 2: Accident Spatial-Temporal Post-Impact Prediction

After the clean-up phase of an accident, the traffic flow will begin to recover from congestion to normal condition. Recovery phase is an important process which is often neglected by the travelers and traffic management department, since people always regard clearance as the end of an accident, while the evacuation process afterwards plays a vital role in reasonable path planning. Thus, in this phase, several important values in the recovery phase will be predicted.First, the predicted clean-up time, matrixes of traffic volume, and speed at the occurrence of the accident are used to estimate the queue length at the end of the clean-up phase (or the beginning of recovery phase). A CNNs-based predictor is used in order to better capture the spatial features of the congested road. Second, the analysis of the recovery phase is based on a backpropagation neural networks (BPNNs), where the estimated queue length together with the historical average traffic condition are used as input. The final output of this stage can include full-recovery time, half-recovery time, maximum accumulative queue length, and average accumulative queue length. Whenever a new accident record comes in, stage 2 will start when it receives the output clean-up time of stage 1.


#### 3.2.1. Queue Length Estimation at the End of Clean-Up Phase Using CNNs

During the clean-up phase, one or several lanes of the highway will be affected which leads to the reduction of capacity. According to the specific number of block lanes and block distance, there will be varying degrees of vehicle accumulation. If the block area is relatively small or the traffic volume is low, the traffic flow itself will absorb disturbance and cause little congestion. However, if high traffic volume meets the large block area, the accumulated queue will be very long, and it will be necessary for the travelers to change the travel plan.Convolutional neural network (CNN) is a class of deep, feed-forward artificial neural network, which has been successfully employed to analyze visual imagery. Since the variables that influence the queue length in our model include traffic flow, speed, and the geometry of the block area, they can all be better presented by pictures. Thus, CNNs are the best choice since they behave well in extracting spatial features from images so as to fully understand the spatial characteristics around the block area. A CNN consists of an input and an output layer, multiple convolutional layers, and optional hidden layers such as pooling layers, fully connected layers, and normalization layers. Figure6 shows the demonstration of how these layers can be combined to build a CNN according to the requirement [1]. Convolutional layers apply a convolution operation to the input and pass the result to the next layer, so as to achieve feature extraction [46].Figure 6
Architecture of CNNs.(1) Traffic Environment Preprocessing. The definitions and representations of the traffic environment are very important, as the accuracy of prediction is dependent on the effectiveness of the information received about the environment. To take advantage of the CNNs, the environment is processed as three pictures in the model: a picture of geometry showing the block area, a picture of the vehicle speed, and a picture of the traffic flow. A representation of this process is shown in Figure 7, where an accident blocks two lanes with 0.23 miles on a four-lane highway. Noticing that the red arrow shows the location of sensors (spread unevenly), and the grey dotted lines in Figure 7(a) represents how the picture is divided into grids that is long in 0.1 miles and wide in lane width. Figure 7(b) shows the trafficability of each grid, where the block area is set to 0, and other normal area is set to 1. The corresponding average flow (vehicles/hour) and average speeds (miles/hour) are shown in Figures 7(c) and 7(d). The data in each grid are always accessed from the nearest sensor and later normalized. The total length is set as 5 miles, which means 4×50 grids. These settings ensure that the environment is accurately and sufficiently represented and also not too complex for the CNNs to understand.Figure 7
Example of processing traffic environment pictures. (a) Four-lane highway map. (b) Geometry picture. (c) Traffic flow (vehicles/hour). (d) Average speed (miles/hour).
(a)(b)(c)(d)(2) Network Structure. For highways with different number of lanes in the dataset, we separately trained three CNNs, namely, the 4-lane model, 5-lane model, and 6-lane model. Each CNN receives three traffic environment pictures mentioned in 3.2.1.1 together with the predicted clean-up time as input, and after processing through six layers (three convolutional layers and three fully connected layers), it outputs a number representing the predicted queue length LclP. The structure of the 5-lane CNN model, including the processing method in each layer and the picture size before and after each layer, is shown in Figure 8. The network structure of the 4-lane model and 6-lane model is not presented here. Learning rate is set as 0.005, and the training ends when mean square error reaches 0.001.Figure 8
Structure of the CNNs in the 5-lane model.


#### 3.2.2. Prediction of Spatial-Temporal Impact in Recovery Phase Using BPNNs

At the beginning of the recovery phase, the block area will be removed and the traffic will gradually return to normal condition. Thus, the environment in this phase can be described as a simple congestion propagation model in the straight closed road. Shock wave theory [47], proposed in 1955, regards traffic flow as a continuous fluid with a linear flow-density relationship and has been applied widely in the congestion propagation analysis. However, it only concerns constant flow and density and neglects stochastic effects. This work fully considers the uneven distribution of traffic in the upstream and downstream and uses a BPNNs-based predictor to capture the nonlinear relationship between model input and output that estimate spatial-temporal impact variables such as full-recovery time, half-recovery time, maximum accumulative queue length, and average accumulative queue length.Similar to Section3.2.1, we also train three BPNNs models corresponding to 4-lane case, 5-lane case, and 6-lane case. Each BPNN receives inputs including the speed and flow of each lane at the beginning of recovery phase together with the predicted queue length, and after processing through a hidden layer, it outputs a number representing the spatial-temporal impact variable. Note that a separate BPNN is trained for each variable. It is worth mentioning that in the predicting process shown in Figure 3, the instant traffic data are represented by the historical average value to improve accuracy. For example, if the predicted recovery phase of an accident starts at 2021/6/20, 8 : 00 (Sunday), the speed and flow data will be accessed through calculating the average value at the four most recent “Sunday 8:00.” . Figure 9 shows the structure of the 4-lane BPNN model, which has 17 input neurons and 9 hidden neurons. The 5-lane model has 21 input neurons and 11 hidden neurons, while the 6-lane model has 25 and 13. Learning rate is set as 0.005, and the training ends when mean square error reaches 0.001.Figure 9
Structure of the BPNNs in the 4-lane model.The process of acquiring actual recovery time and accumulative queue length is detailed in Section4.


### 3.3. Stage 3: Online Updating

After stage 1 and stage 2, the whole lifetime of an accident has already been predicted. It is expected that most accidents will be classified accurately, and the predicted spatial-temporal variables will match the actual one within a fault tolerance. However, some of the predictions can have long time span using the information at the first beginning. Long-term prediction has always been a difficulty and errors must exist. The most influencing part would be the clustering and classification accuracy, since the error will continue to propagate and cause more serious errors in the following stages. That is the reason for proposing stage 3: detecting the error during the development of the accident and making timely adaptation and revision. Furthermore, the revised values can also help to modify and update the models in stage 1, namely, mean-shift-based clustering and SNNs-based classification.


#### 3.3.1. Error Detection and Adaptation

The first step in the online updating stage is to detect if the predicted clean-up time is excessively deviating from the true value. As Figure10 shows, the detection process is carried out every 5 minutes starting from the occurrence of an accident. The cause of errors can be divided into two situations:(i)
TclA>TclP: the accident has not been totally cleaned in the predicted clean-up time; then, the stage 2 is repeated every 5 minutes until the accident is cleaned.(ii)
TclA<TclP: the accident is cleaned earlier than predicted; then, the current time is set as the actual clean-up time and is used to repredict in stage 2.Figure 10
Error detection and adaptation process.This process makes up for the shortcomings of long-term prediction and helps the model to predict more accurately.


#### 3.3.2. Clustering and Classification Updating

Another benefit of online stage is the modification of the clustering and prediction model when new knowledge is found along with the incoming accidents. As Figure11 shows, the process starts with finding the actual closest cluster CA for TclA. Then, it can be divided into the following two situations:(i)
CA=CP: the accident is classified into the proper cluster and the error is caused by the difference from the centroid value. In this case, only a clustering updating is carried out to add a new instance and recompute new centroid of CA;(ii)
CA≠CP: the accident is not classified into the proper cluster and the error is caused by the misclassification of the SNNs classifier. Then, another classification updating is needed where the accident attributes and its actual cluster CA is added to the SNNs training set and later used to retrain the SNNs model.Figure 11
Clustering and classification updating process.This process helps to describe accidents that are not available in the training dataset and further improve the overall accuracy of the model.


## 3.1. Stage 1: Accident Clean-Up Time Prediction

According to the two-phase accident lifetime defined in Section1, phases are not completely independent and can influence each other. Therefore, in order to figure out the spatial-temporal impact in the whole process, we need to predict the duration of clean-up phase first.Mean-shift clustering is first performed on the clean-up time, which groups the clean-up time into several intervals. Thus, the accidents with similar cleaning difficulty are labeled as a cluster. Furthermore, the accident records with attributes and corresponding class labels are input to train an SNNs classifier. Whenever a new accident record comes in, the accident attributes are extracted and then classified using the trained classifier. The predicting clean-up time is represented by the centroid value of its corresponding cluster.


### 3.1.1. Clustering Using Mean-Shift

According to the statistics in Section4, the clean-up time of the accidents distributes unevenly throughout the interval. It exists the case where some of the interval lack records. Thus, to improve the prediction accuracy and remove exceptional, clustering the clean-up time into groups and using the centroid value to present the predicted value is better than a direct prediction model.The mean-shift algorithm [26] is chosen to cluster the clean-up time for two main reasons: it does not require a predefined number of clusters; and such density-based algorithms are less affected by the mean value compared with the K-means algorithm. The key operation of the algorithm is to calculate the drift vector of the centroid through the data density change in the region of data, so as to move the centroid in the next iteration until it reaches the maximum density. Algorithm 1 shows the procedure of clustering the traffic records according to the clean-up time. The bandwidth is set as 10.Algorithm 1: Mean-shift clustering of clean-up time.
(1)
Input(2)
Tc≔ dataset of clean-up time over which the procedure is performed(3)
Initialization(4)
r≔ the radius of a region(5)
d≔ the minimum distance between clusters(6)
Fi,Cj≔ probability that point i belongs to Cluster Cj(7)
Repeat(8)
Randomly select an unvisited point from the dataset as the starting centre pointoc(9)
Repeat(10)
Find all the points that appear in the circle⊙oc,r and group into cluster Coc(11)
For pointiin Coc, Fi,Coc←Fi,Coc+1(12)
Calculate the shift vector ofoc as Mc=1/K∑xi∈Cxi−oc(13)
Updateoc towards the shift vector as oc←oc+Mc(14)
UntilMc reaches minimum threshold(15)
If∃Coi,distanceCoc,Coi<d, then merge Coc and Coi(16)
Else, labelCoc as a new cluster(17)
Until all points are visited(18)
For pointi in Tc, i belongs to cluster C with maximum probability Fi,C=maxCjFi,Cj(19)
Output(20)
Coc≔ all clusters(21)
CTc≔ clusters that each point in Tc belongs to


### 3.1.2. Accident Characterization

When a new accident record comes to the model, in order to predict the clean-up time, the cluster that the records belongs to needs to be figured out. Thus, a number of attributes that represent the characteristics of accidents are used to train a classifier, which outputs the corresponding cluster.In a previous work, three kinds of attributes are usually extracted to demonstrate the accident: accident information (e.g. accident type [24, 25, 27–29], blocked area size [5, 25], number of vehicles involved [5, 25, 28], and casualties [5, 25, 29]), spatial-temporal attributes (e.g. lane location [25, 27, 29], road type [24, 25], and time [5, 24, 25, 27–29]), and weather information (e.g. humidity [24, 25, 28], wind [24, 25], and visibility [24, 25]). In this model, considering the dataset used, 6 attributes are selected as the input in this stage:(i)
Block lanes: a number between 1 and 6 represents the number of lanes blocked by the accident. The value is determined according to TMC event code [30].(ii)
Block distance: a value represents the length of road blocked by the accident in miles.(iii)
Day or night: a binary digit, where 0 represents daytime while 1 represents night.(iv)
Workday or not: a binary digit, where 0 represents workday while 1 represents holiday or weekend.(v)
Peak hour or not: a number between 0 and 2, where 0 represents morning peak (8 a.m.–10 a.m.), 1 represents evening peak (4 p.m.–6 p.m.), and 2 represents the normal period [31].(vi)
Weather condition: a number between 0 and 4, which represents sunny/rain/snow/thunderstorm/fog, respectively, when accident happens.More detailed information of data processing can be found in Section4.


### 3.1.3. Classification Using SNNs

A classifier is trained to match the accident attributes to the cluster it belongs to. Due to the characteristics of being sensitive to the spatial-temporal features, SNNs are applied in building the classifier. It is the first time of applying SNNs in traffic accident prediction domain.After being first proposed in 1997 by Maass [6], SNNs have attracted researchers to explore different research directions. The main technique directions of SNNs can be concluded in four main categories: encoding and decoding of spiritual information, neuron models and network simulation strategy, similarity measurement of spiking sequence, and synaptic weight learning rules [32].The classification problem in this work concerns with the supervised learning in SNNs, which refers to finding a suitable synaptic weight matrix for a series of given input spike trains and target spike trains, so that the output of the neurons is as close as the corresponding target spike trains, that is, the error evaluation function of the two reaches minimum [33].(1) Leaky Integrate-and-Fire Neural Model. Neural computing relies on the construction of the spiking neuron model. In order to do numerical analysis, an efficient mathematical neural model should be built based on the geometry and electrical properties of neuron. Leaky Integrate-and-Fire neural (LIF) model [34], as the single compartment model with fixed threshold which has been widely used in neural computing, can directly describe the relationship between membrane potential V and input electric current I. When V is between the resting potential Vrest and the threshold Vthre, it is given by the following equation:(1)τmdVdt=−V−Vrest+RmI,where τm is a time constant, and I is the sum of current released by presynaptic neurons. Once V crosses Vthre from below, a spike is generated and V is reset to Vrest. The LIF model, with the advantages of using simple structure to realize accurate simulation of SNNs by event-driven simulation strategy, is chosen as the basic neuron model in our work.(2) Gaussian Tuning Curve Coding. In the biological neural system, spikes are transmitted between neurons with different combinations. The corresponding rules and mechanisms of conversion between the stimulation signal and the spike trains are called neural coding [35]. When neuron feels external stimuli, encoding module encodes the stimulation signal to specific spike trains and responses; in turn, decoding module can estimate the stimulation signal from spike trains.Researchers put forward various coding methods, which can be divided into two main categories: frequency-based coding [36] and time-based coding [37]. Evidence confirms that time-based coding is the more effective, since the time structure of the spike trains carries stimulus signals on a millisecond or even smaller scale, not just the average firing frequency [38]. With the introduction of more complex systems, single-neuron coding cannot effectively present the huge amount of information. Population coding [39] is thus proposed to solve complex information coding problem, where each neuron has a unique spike response distribution for a given stimulus, and the responses of the neuron population are combined to represent the overall information.The population coding method used in this model is Gaussian tuning curve coding [40], as shown in Figure 4. A neuron covers a certain range of analog quantity in the form of Gaussian function, while the height of the corresponding Gaussian function to a certain value of the analog quantity determines the time for the neuron to emit spike. In this work, a population containing six neurons is used to encode the six accident attributes mentioned above. Figure 4 shows an example of how “block distance” of 0.18 miles is encoded into spike trains 0.79,0.04,0.52,0.96,1.00,1.00ms.Figure 4
Accident attribute coding with Gaussian tuning curve. (a) The corresponding Gaussian curve of six neurons. (b) Firing time of six neurons.
(a)(b)(3) Multi-ReSuMe Training Algorithm. The supervised learning algorithm in SNNs can be divided into three categories based on the learning rules of synaptic weight: gradient-descent based method, synaptic plasticity-based method, and convolution-based method [41]. Gradient-descent based methods such as SpikeProp [40] learn from the error back propagation algorithm of traditional ANNs, where the state variables of the neuron model must have analytical expressions and lack biological realism. From a biological perspective, a training algorithm should update synaptic weights based on the temporal correlation of presynaptic and postsynaptic spikes, in keeping with the spike timing-dependent plasticity (STDP) theory [42]. In this work, a synaptic plasticity-based method called the multilayer remote supervised method (Multi-ReSuMe) [43] is used to train the classifier. Multi-ReSuMe extends the single-layer impulse neural network ReSuMe algorithm [41] to the multilayer network and overcomes some limitations as it can be applied to neurons firing multiple spikes, and it can in principle be applied to any linear neuron model.The main contribution of Multi-ReSuMe is the combination of the STDP and anti-STDP mechanism in one process, where synaptic weight update between hidden layerH and output layer O satisfies the following equation:(2)ddtwoht=1nhSht∫0∞apreSodt−Soatds+1nhSodt−Soata+∫0∞apostsSht−sds.For any excitatory synaptic connection from hidden neuronh to output neuron o, a synaptic strength woh is potentiated whenever a target spike Sodt is observed and depressed whenever the trained neuron fires Soat. Here, s denotes a delay between the presynaptic and postsynaptic firing times, where s=tof−thf. The role of the noncorrelative factor a in equation (2) is to adjust the average strength of the synaptic inputs so as to impose on a neuron a desired level of activity. The kernels apre and apost are STDP-related terms that define the shape of a learning window Ws [44],(3)Ws=apre−s=−A−⋅expsτ−,s≤0,aposts=+A+⋅exp−sτ+,s>0,where parameters A+,A−>0 are the amplitudes and τ+,τ−>0 are the time constants of the learning process. apre−s gives the weight change if the presynaptic spike (the spike of the hidden neuron occurs) comes after the postsynaptic spike (the spike of the output and target neurons), while aposts gives the weight change if the presynaptic spike comes before the postsynaptic spike [43].Similarly, synaptic weight update between input layerI and hidden layer H satisfies the following equation:(4)ddtwhit=1ninhSit∑o∈O∫0∞apreSodt−Soatwoh+1ninh∑o∈OSodt−Soata+∫0∞apostsSit−sdswoh.As Figure5 shows, the network has 36 input neurons corresponding to six accident attributes, and an output neuron representing the cluster that the input sample belongs to. The hidden layer contains 80 neurons which are fully connected with other layers. The output neuron’s spike train contains a single spike, where the timing differs from each other, as given in Table 2. The process of building and training a Multi-ReSuMe-based classifier is given in Algorithm 2. The parameters are initialized as follows: A+=1.2, A−=0.5, τ+=τ−=0.5, and a=0.05 [45].Figure 5
A Multi-ReSuMe-based SNNs classifier.Table 2
The target spike-time of output neuron corresponding to each cluster.
Cluster no.Output spike-time (ms)00112233⋮⋮nnAlgorithm 2: Multi-ReSuMe-based classifier.
(1)
Definition(2)
A≔ Historic accident dataset(3)
Ai≔ accident data in A where Ai=a1,a2,a3,a4,a5,a6,c(4)
etarget≔ the minimum value of network error to reach when learning is considered converged(5)
W≔ synaptic weight between all neurons(6)
M≔ maximum number of iterations(7)
Initialization(8)
W← Initial synaptic weight with random value θ∼U0.2,0.8(9)
For iteration = 1, M do(10)
ForAi∈A do(11)
EncodeAi=a1,a2,a3,a4,a5,a6,c to a series of spike trains Ai=Si1,Si2,Si3,Si4,Si5,Si6,Sod(12)
Set membrane potential of all neurons to the resting potential (set to 0)(13)
Pass input spike trains to the network and find actual output spikeSoa(14)
Calculate network erroreAi=1/2Sod−Soa2(15)
Compute weight modificationsΔW for all layers according to equation (2) and equation (4)(16)
Update synaptic weightW←W+ΔW(17)
End for(18)
Calculate summed network errore=∑eAi(19)
Whilee≥etarget


## 3.1.1. Clustering Using Mean-Shift

According to the statistics in Section4, the clean-up time of the accidents distributes unevenly throughout the interval. It exists the case where some of the interval lack records. Thus, to improve the prediction accuracy and remove exceptional, clustering the clean-up time into groups and using the centroid value to present the predicted value is better than a direct prediction model.The mean-shift algorithm [26] is chosen to cluster the clean-up time for two main reasons: it does not require a predefined number of clusters; and such density-based algorithms are less affected by the mean value compared with the K-means algorithm. The key operation of the algorithm is to calculate the drift vector of the centroid through the data density change in the region of data, so as to move the centroid in the next iteration until it reaches the maximum density. Algorithm 1 shows the procedure of clustering the traffic records according to the clean-up time. The bandwidth is set as 10.Algorithm 1: Mean-shift clustering of clean-up time.
(1)
Input(2)
Tc≔ dataset of clean-up time over which the procedure is performed(3)
Initialization(4)
r≔ the radius of a region(5)
d≔ the minimum distance between clusters(6)
Fi,Cj≔ probability that point i belongs to Cluster Cj(7)
Repeat(8)
Randomly select an unvisited point from the dataset as the starting centre pointoc(9)
Repeat(10)
Find all the points that appear in the circle⊙oc,r and group into cluster Coc(11)
For pointiin Coc, Fi,Coc←Fi,Coc+1(12)
Calculate the shift vector ofoc as Mc=1/K∑xi∈Cxi−oc(13)
Updateoc towards the shift vector as oc←oc+Mc(14)
UntilMc reaches minimum threshold(15)
If∃Coi,distanceCoc,Coi<d, then merge Coc and Coi(16)
Else, labelCoc as a new cluster(17)
Until all points are visited(18)
For pointi in Tc, i belongs to cluster C with maximum probability Fi,C=maxCjFi,Cj(19)
Output(20)
Coc≔ all clusters(21)
CTc≔ clusters that each point in Tc belongs to


## 3.1.2. Accident Characterization

When a new accident record comes to the model, in order to predict the clean-up time, the cluster that the records belongs to needs to be figured out. Thus, a number of attributes that represent the characteristics of accidents are used to train a classifier, which outputs the corresponding cluster.In a previous work, three kinds of attributes are usually extracted to demonstrate the accident: accident information (e.g. accident type [24, 25, 27–29], blocked area size [5, 25], number of vehicles involved [5, 25, 28], and casualties [5, 25, 29]), spatial-temporal attributes (e.g. lane location [25, 27, 29], road type [24, 25], and time [5, 24, 25, 27–29]), and weather information (e.g. humidity [24, 25, 28], wind [24, 25], and visibility [24, 25]). In this model, considering the dataset used, 6 attributes are selected as the input in this stage:(i)
Block lanes: a number between 1 and 6 represents the number of lanes blocked by the accident. The value is determined according to TMC event code [30].(ii)
Block distance: a value represents the length of road blocked by the accident in miles.(iii)
Day or night: a binary digit, where 0 represents daytime while 1 represents night.(iv)
Workday or not: a binary digit, where 0 represents workday while 1 represents holiday or weekend.(v)
Peak hour or not: a number between 0 and 2, where 0 represents morning peak (8 a.m.–10 a.m.), 1 represents evening peak (4 p.m.–6 p.m.), and 2 represents the normal period [31].(vi)
Weather condition: a number between 0 and 4, which represents sunny/rain/snow/thunderstorm/fog, respectively, when accident happens.More detailed information of data processing can be found in Section4.


## 3.1.3. Classification Using SNNs

A classifier is trained to match the accident attributes to the cluster it belongs to. Due to the characteristics of being sensitive to the spatial-temporal features, SNNs are applied in building the classifier. It is the first time of applying SNNs in traffic accident prediction domain.After being first proposed in 1997 by Maass [6], SNNs have attracted researchers to explore different research directions. The main technique directions of SNNs can be concluded in four main categories: encoding and decoding of spiritual information, neuron models and network simulation strategy, similarity measurement of spiking sequence, and synaptic weight learning rules [32].The classification problem in this work concerns with the supervised learning in SNNs, which refers to finding a suitable synaptic weight matrix for a series of given input spike trains and target spike trains, so that the output of the neurons is as close as the corresponding target spike trains, that is, the error evaluation function of the two reaches minimum [33].(1) Leaky Integrate-and-Fire Neural Model. Neural computing relies on the construction of the spiking neuron model. In order to do numerical analysis, an efficient mathematical neural model should be built based on the geometry and electrical properties of neuron. Leaky Integrate-and-Fire neural (LIF) model [34], as the single compartment model with fixed threshold which has been widely used in neural computing, can directly describe the relationship between membrane potential V and input electric current I. When V is between the resting potential Vrest and the threshold Vthre, it is given by the following equation:(1)τmdVdt=−V−Vrest+RmI,where τm is a time constant, and I is the sum of current released by presynaptic neurons. Once V crosses Vthre from below, a spike is generated and V is reset to Vrest. The LIF model, with the advantages of using simple structure to realize accurate simulation of SNNs by event-driven simulation strategy, is chosen as the basic neuron model in our work.(2) Gaussian Tuning Curve Coding. In the biological neural system, spikes are transmitted between neurons with different combinations. The corresponding rules and mechanisms of conversion between the stimulation signal and the spike trains are called neural coding [35]. When neuron feels external stimuli, encoding module encodes the stimulation signal to specific spike trains and responses; in turn, decoding module can estimate the stimulation signal from spike trains.Researchers put forward various coding methods, which can be divided into two main categories: frequency-based coding [36] and time-based coding [37]. Evidence confirms that time-based coding is the more effective, since the time structure of the spike trains carries stimulus signals on a millisecond or even smaller scale, not just the average firing frequency [38]. With the introduction of more complex systems, single-neuron coding cannot effectively present the huge amount of information. Population coding [39] is thus proposed to solve complex information coding problem, where each neuron has a unique spike response distribution for a given stimulus, and the responses of the neuron population are combined to represent the overall information.The population coding method used in this model is Gaussian tuning curve coding [40], as shown in Figure 4. A neuron covers a certain range of analog quantity in the form of Gaussian function, while the height of the corresponding Gaussian function to a certain value of the analog quantity determines the time for the neuron to emit spike. In this work, a population containing six neurons is used to encode the six accident attributes mentioned above. Figure 4 shows an example of how “block distance” of 0.18 miles is encoded into spike trains 0.79,0.04,0.52,0.96,1.00,1.00ms.Figure 4
Accident attribute coding with Gaussian tuning curve. (a) The corresponding Gaussian curve of six neurons. (b) Firing time of six neurons.
(a)(b)(3) Multi-ReSuMe Training Algorithm. The supervised learning algorithm in SNNs can be divided into three categories based on the learning rules of synaptic weight: gradient-descent based method, synaptic plasticity-based method, and convolution-based method [41]. Gradient-descent based methods such as SpikeProp [40] learn from the error back propagation algorithm of traditional ANNs, where the state variables of the neuron model must have analytical expressions and lack biological realism. From a biological perspective, a training algorithm should update synaptic weights based on the temporal correlation of presynaptic and postsynaptic spikes, in keeping with the spike timing-dependent plasticity (STDP) theory [42]. In this work, a synaptic plasticity-based method called the multilayer remote supervised method (Multi-ReSuMe) [43] is used to train the classifier. Multi-ReSuMe extends the single-layer impulse neural network ReSuMe algorithm [41] to the multilayer network and overcomes some limitations as it can be applied to neurons firing multiple spikes, and it can in principle be applied to any linear neuron model.The main contribution of Multi-ReSuMe is the combination of the STDP and anti-STDP mechanism in one process, where synaptic weight update between hidden layerH and output layer O satisfies the following equation:(2)ddtwoht=1nhSht∫0∞apreSodt−Soatds+1nhSodt−Soata+∫0∞apostsSht−sds.For any excitatory synaptic connection from hidden neuronh to output neuron o, a synaptic strength woh is potentiated whenever a target spike Sodt is observed and depressed whenever the trained neuron fires Soat. Here, s denotes a delay between the presynaptic and postsynaptic firing times, where s=tof−thf. The role of the noncorrelative factor a in equation (2) is to adjust the average strength of the synaptic inputs so as to impose on a neuron a desired level of activity. The kernels apre and apost are STDP-related terms that define the shape of a learning window Ws [44],(3)Ws=apre−s=−A−⋅expsτ−,s≤0,aposts=+A+⋅exp−sτ+,s>0,where parameters A+,A−>0 are the amplitudes and τ+,τ−>0 are the time constants of the learning process. apre−s gives the weight change if the presynaptic spike (the spike of the hidden neuron occurs) comes after the postsynaptic spike (the spike of the output and target neurons), while aposts gives the weight change if the presynaptic spike comes before the postsynaptic spike [43].Similarly, synaptic weight update between input layerI and hidden layer H satisfies the following equation:(4)ddtwhit=1ninhSit∑o∈O∫0∞apreSodt−Soatwoh+1ninh∑o∈OSodt−Soata+∫0∞apostsSit−sdswoh.As Figure5 shows, the network has 36 input neurons corresponding to six accident attributes, and an output neuron representing the cluster that the input sample belongs to. The hidden layer contains 80 neurons which are fully connected with other layers. The output neuron’s spike train contains a single spike, where the timing differs from each other, as given in Table 2. The process of building and training a Multi-ReSuMe-based classifier is given in Algorithm 2. The parameters are initialized as follows: A+=1.2, A−=0.5, τ+=τ−=0.5, and a=0.05 [45].Figure 5
A Multi-ReSuMe-based SNNs classifier.Table 2
The target spike-time of output neuron corresponding to each cluster.
Cluster no.Output spike-time (ms)00112233⋮⋮nnAlgorithm 2: Multi-ReSuMe-based classifier.
(1)
Definition(2)
A≔ Historic accident dataset(3)
Ai≔ accident data in A where Ai=a1,a2,a3,a4,a5,a6,c(4)
etarget≔ the minimum value of network error to reach when learning is considered converged(5)
W≔ synaptic weight between all neurons(6)
M≔ maximum number of iterations(7)
Initialization(8)
W← Initial synaptic weight with random value θ∼U0.2,0.8(9)
For iteration = 1, M do(10)
ForAi∈A do(11)
EncodeAi=a1,a2,a3,a4,a5,a6,c to a series of spike trains Ai=Si1,Si2,Si3,Si4,Si5,Si6,Sod(12)
Set membrane potential of all neurons to the resting potential (set to 0)(13)
Pass input spike trains to the network and find actual output spikeSoa(14)
Calculate network erroreAi=1/2Sod−Soa2(15)
Compute weight modificationsΔW for all layers according to equation (2) and equation (4)(16)
Update synaptic weightW←W+ΔW(17)
End for(18)
Calculate summed network errore=∑eAi(19)
Whilee≥etarget


## 3.2. Stage 2: Accident Spatial-Temporal Post-Impact Prediction

After the clean-up phase of an accident, the traffic flow will begin to recover from congestion to normal condition. Recovery phase is an important process which is often neglected by the travelers and traffic management department, since people always regard clearance as the end of an accident, while the evacuation process afterwards plays a vital role in reasonable path planning. Thus, in this phase, several important values in the recovery phase will be predicted.First, the predicted clean-up time, matrixes of traffic volume, and speed at the occurrence of the accident are used to estimate the queue length at the end of the clean-up phase (or the beginning of recovery phase). A CNNs-based predictor is used in order to better capture the spatial features of the congested road. Second, the analysis of the recovery phase is based on a backpropagation neural networks (BPNNs), where the estimated queue length together with the historical average traffic condition are used as input. The final output of this stage can include full-recovery time, half-recovery time, maximum accumulative queue length, and average accumulative queue length. Whenever a new accident record comes in, stage 2 will start when it receives the output clean-up time of stage 1.


### 3.2.1. Queue Length Estimation at the End of Clean-Up Phase Using CNNs

During the clean-up phase, one or several lanes of the highway will be affected which leads to the reduction of capacity. According to the specific number of block lanes and block distance, there will be varying degrees of vehicle accumulation. If the block area is relatively small or the traffic volume is low, the traffic flow itself will absorb disturbance and cause little congestion. However, if high traffic volume meets the large block area, the accumulated queue will be very long, and it will be necessary for the travelers to change the travel plan.Convolutional neural network (CNN) is a class of deep, feed-forward artificial neural network, which has been successfully employed to analyze visual imagery. Since the variables that influence the queue length in our model include traffic flow, speed, and the geometry of the block area, they can all be better presented by pictures. Thus, CNNs are the best choice since they behave well in extracting spatial features from images so as to fully understand the spatial characteristics around the block area. A CNN consists of an input and an output layer, multiple convolutional layers, and optional hidden layers such as pooling layers, fully connected layers, and normalization layers. Figure6 shows the demonstration of how these layers can be combined to build a CNN according to the requirement [1]. Convolutional layers apply a convolution operation to the input and pass the result to the next layer, so as to achieve feature extraction [46].Figure 6
Architecture of CNNs.(1) Traffic Environment Preprocessing. The definitions and representations of the traffic environment are very important, as the accuracy of prediction is dependent on the effectiveness of the information received about the environment. To take advantage of the CNNs, the environment is processed as three pictures in the model: a picture of geometry showing the block area, a picture of the vehicle speed, and a picture of the traffic flow. A representation of this process is shown in Figure 7, where an accident blocks two lanes with 0.23 miles on a four-lane highway. Noticing that the red arrow shows the location of sensors (spread unevenly), and the grey dotted lines in Figure 7(a) represents how the picture is divided into grids that is long in 0.1 miles and wide in lane width. Figure 7(b) shows the trafficability of each grid, where the block area is set to 0, and other normal area is set to 1. The corresponding average flow (vehicles/hour) and average speeds (miles/hour) are shown in Figures 7(c) and 7(d). The data in each grid are always accessed from the nearest sensor and later normalized. The total length is set as 5 miles, which means 4×50 grids. These settings ensure that the environment is accurately and sufficiently represented and also not too complex for the CNNs to understand.Figure 7
Example of processing traffic environment pictures. (a) Four-lane highway map. (b) Geometry picture. (c) Traffic flow (vehicles/hour). (d) Average speed (miles/hour).
(a)(b)(c)(d)(2) Network Structure. For highways with different number of lanes in the dataset, we separately trained three CNNs, namely, the 4-lane model, 5-lane model, and 6-lane model. Each CNN receives three traffic environment pictures mentioned in 3.2.1.1 together with the predicted clean-up time as input, and after processing through six layers (three convolutional layers and three fully connected layers), it outputs a number representing the predicted queue length LclP. The structure of the 5-lane CNN model, including the processing method in each layer and the picture size before and after each layer, is shown in Figure 8. The network structure of the 4-lane model and 6-lane model is not presented here. Learning rate is set as 0.005, and the training ends when mean square error reaches 0.001.Figure 8
Structure of the CNNs in the 5-lane model.


### 3.2.2. Prediction of Spatial-Temporal Impact in Recovery Phase Using BPNNs

At the beginning of the recovery phase, the block area will be removed and the traffic will gradually return to normal condition. Thus, the environment in this phase can be described as a simple congestion propagation model in the straight closed road. Shock wave theory [47], proposed in 1955, regards traffic flow as a continuous fluid with a linear flow-density relationship and has been applied widely in the congestion propagation analysis. However, it only concerns constant flow and density and neglects stochastic effects. This work fully considers the uneven distribution of traffic in the upstream and downstream and uses a BPNNs-based predictor to capture the nonlinear relationship between model input and output that estimate spatial-temporal impact variables such as full-recovery time, half-recovery time, maximum accumulative queue length, and average accumulative queue length.Similar to Section3.2.1, we also train three BPNNs models corresponding to 4-lane case, 5-lane case, and 6-lane case. Each BPNN receives inputs including the speed and flow of each lane at the beginning of recovery phase together with the predicted queue length, and after processing through a hidden layer, it outputs a number representing the spatial-temporal impact variable. Note that a separate BPNN is trained for each variable. It is worth mentioning that in the predicting process shown in Figure 3, the instant traffic data are represented by the historical average value to improve accuracy. For example, if the predicted recovery phase of an accident starts at 2021/6/20, 8 : 00 (Sunday), the speed and flow data will be accessed through calculating the average value at the four most recent “Sunday 8:00.” . Figure 9 shows the structure of the 4-lane BPNN model, which has 17 input neurons and 9 hidden neurons. The 5-lane model has 21 input neurons and 11 hidden neurons, while the 6-lane model has 25 and 13. Learning rate is set as 0.005, and the training ends when mean square error reaches 0.001.Figure 9
Structure of the BPNNs in the 4-lane model.The process of acquiring actual recovery time and accumulative queue length is detailed in Section4.


## 3.2.1. Queue Length Estimation at the End of Clean-Up Phase Using CNNs

During the clean-up phase, one or several lanes of the highway will be affected which leads to the reduction of capacity. According to the specific number of block lanes and block distance, there will be varying degrees of vehicle accumulation. If the block area is relatively small or the traffic volume is low, the traffic flow itself will absorb disturbance and cause little congestion. However, if high traffic volume meets the large block area, the accumulated queue will be very long, and it will be necessary for the travelers to change the travel plan.Convolutional neural network (CNN) is a class of deep, feed-forward artificial neural network, which has been successfully employed to analyze visual imagery. Since the variables that influence the queue length in our model include traffic flow, speed, and the geometry of the block area, they can all be better presented by pictures. Thus, CNNs are the best choice since they behave well in extracting spatial features from images so as to fully understand the spatial characteristics around the block area. A CNN consists of an input and an output layer, multiple convolutional layers, and optional hidden layers such as pooling layers, fully connected layers, and normalization layers. Figure6 shows the demonstration of how these layers can be combined to build a CNN according to the requirement [1]. Convolutional layers apply a convolution operation to the input and pass the result to the next layer, so as to achieve feature extraction [46].Figure 6
Architecture of CNNs.(1) Traffic Environment Preprocessing. The definitions and representations of the traffic environment are very important, as the accuracy of prediction is dependent on the effectiveness of the information received about the environment. To take advantage of the CNNs, the environment is processed as three pictures in the model: a picture of geometry showing the block area, a picture of the vehicle speed, and a picture of the traffic flow. A representation of this process is shown in Figure 7, where an accident blocks two lanes with 0.23 miles on a four-lane highway. Noticing that the red arrow shows the location of sensors (spread unevenly), and the grey dotted lines in Figure 7(a) represents how the picture is divided into grids that is long in 0.1 miles and wide in lane width. Figure 7(b) shows the trafficability of each grid, where the block area is set to 0, and other normal area is set to 1. The corresponding average flow (vehicles/hour) and average speeds (miles/hour) are shown in Figures 7(c) and 7(d). The data in each grid are always accessed from the nearest sensor and later normalized. The total length is set as 5 miles, which means 4×50 grids. These settings ensure that the environment is accurately and sufficiently represented and also not too complex for the CNNs to understand.Figure 7
Example of processing traffic environment pictures. (a) Four-lane highway map. (b) Geometry picture. (c) Traffic flow (vehicles/hour). (d) Average speed (miles/hour).
(a)(b)(c)(d)(2) Network Structure. For highways with different number of lanes in the dataset, we separately trained three CNNs, namely, the 4-lane model, 5-lane model, and 6-lane model. Each CNN receives three traffic environment pictures mentioned in 3.2.1.1 together with the predicted clean-up time as input, and after processing through six layers (three convolutional layers and three fully connected layers), it outputs a number representing the predicted queue length LclP. The structure of the 5-lane CNN model, including the processing method in each layer and the picture size before and after each layer, is shown in Figure 8. The network structure of the 4-lane model and 6-lane model is not presented here. Learning rate is set as 0.005, and the training ends when mean square error reaches 0.001.Figure 8
Structure of the CNNs in the 5-lane model.


## 3.2.2. Prediction of Spatial-Temporal Impact in Recovery Phase Using BPNNs

At the beginning of the recovery phase, the block area will be removed and the traffic will gradually return to normal condition. Thus, the environment in this phase can be described as a simple congestion propagation model in the straight closed road. Shock wave theory [47], proposed in 1955, regards traffic flow as a continuous fluid with a linear flow-density relationship and has been applied widely in the congestion propagation analysis. However, it only concerns constant flow and density and neglects stochastic effects. This work fully considers the uneven distribution of traffic in the upstream and downstream and uses a BPNNs-based predictor to capture the nonlinear relationship between model input and output that estimate spatial-temporal impact variables such as full-recovery time, half-recovery time, maximum accumulative queue length, and average accumulative queue length.Similar to Section3.2.1, we also train three BPNNs models corresponding to 4-lane case, 5-lane case, and 6-lane case. Each BPNN receives inputs including the speed and flow of each lane at the beginning of recovery phase together with the predicted queue length, and after processing through a hidden layer, it outputs a number representing the spatial-temporal impact variable. Note that a separate BPNN is trained for each variable. It is worth mentioning that in the predicting process shown in Figure 3, the instant traffic data are represented by the historical average value to improve accuracy. For example, if the predicted recovery phase of an accident starts at 2021/6/20, 8 : 00 (Sunday), the speed and flow data will be accessed through calculating the average value at the four most recent “Sunday 8:00.” . Figure 9 shows the structure of the 4-lane BPNN model, which has 17 input neurons and 9 hidden neurons. The 5-lane model has 21 input neurons and 11 hidden neurons, while the 6-lane model has 25 and 13. Learning rate is set as 0.005, and the training ends when mean square error reaches 0.001.Figure 9
Structure of the BPNNs in the 4-lane model.The process of acquiring actual recovery time and accumulative queue length is detailed in Section4.


## 3.3. Stage 3: Online Updating

After stage 1 and stage 2, the whole lifetime of an accident has already been predicted. It is expected that most accidents will be classified accurately, and the predicted spatial-temporal variables will match the actual one within a fault tolerance. However, some of the predictions can have long time span using the information at the first beginning. Long-term prediction has always been a difficulty and errors must exist. The most influencing part would be the clustering and classification accuracy, since the error will continue to propagate and cause more serious errors in the following stages. That is the reason for proposing stage 3: detecting the error during the development of the accident and making timely adaptation and revision. Furthermore, the revised values can also help to modify and update the models in stage 1, namely, mean-shift-based clustering and SNNs-based classification.


### 3.3.1. Error Detection and Adaptation

The first step in the online updating stage is to detect if the predicted clean-up time is excessively deviating from the true value. As Figure10 shows, the detection process is carried out every 5 minutes starting from the occurrence of an accident. The cause of errors can be divided into two situations:(i)
TclA>TclP: the accident has not been totally cleaned in the predicted clean-up time; then, the stage 2 is repeated every 5 minutes until the accident is cleaned.(ii)
TclA<TclP: the accident is cleaned earlier than predicted; then, the current time is set as the actual clean-up time and is used to repredict in stage 2.Figure 10
Error detection and adaptation process.This process makes up for the shortcomings of long-term prediction and helps the model to predict more accurately.


### 3.3.2. Clustering and Classification Updating

Another benefit of online stage is the modification of the clustering and prediction model when new knowledge is found along with the incoming accidents. As Figure11 shows, the process starts with finding the actual closest cluster CA for TclA. Then, it can be divided into the following two situations:(i)
CA=CP: the accident is classified into the proper cluster and the error is caused by the difference from the centroid value. In this case, only a clustering updating is carried out to add a new instance and recompute new centroid of CA;(ii)
CA≠CP: the accident is not classified into the proper cluster and the error is caused by the misclassification of the SNNs classifier. Then, another classification updating is needed where the accident attributes and its actual cluster CA is added to the SNNs training set and later used to retrain the SNNs model.Figure 11
Clustering and classification updating process.This process helps to describe accidents that are not available in the training dataset and further improve the overall accuracy of the model.


## 3.3.1. Error Detection and Adaptation

The first step in the online updating stage is to detect if the predicted clean-up time is excessively deviating from the true value. As Figure10 shows, the detection process is carried out every 5 minutes starting from the occurrence of an accident. The cause of errors can be divided into two situations:(i)
TclA>TclP: the accident has not been totally cleaned in the predicted clean-up time; then, the stage 2 is repeated every 5 minutes until the accident is cleaned.(ii)
TclA<TclP: the accident is cleaned earlier than predicted; then, the current time is set as the actual clean-up time and is used to repredict in stage 2.Figure 10
Error detection and adaptation process.This process makes up for the shortcomings of long-term prediction and helps the model to predict more accurately.


## 3.3.2. Clustering and Classification Updating

Another benefit of online stage is the modification of the clustering and prediction model when new knowledge is found along with the incoming accidents. As Figure11 shows, the process starts with finding the actual closest cluster CA for TclA. Then, it can be divided into the following two situations:(i)
CA=CP: the accident is classified into the proper cluster and the error is caused by the difference from the centroid value. In this case, only a clustering updating is carried out to add a new instance and recompute new centroid of CA;(ii)
CA≠CP: the accident is not classified into the proper cluster and the error is caused by the misclassification of the SNNs classifier. Then, another classification updating is needed where the accident attributes and its actual cluster CA is added to the SNNs training set and later used to retrain the SNNs model.Figure 11
Clustering and classification updating process.This process helps to describe accidents that are not available in the training dataset and further improve the overall accuracy of the model.


## 4. Dataset

This section describes the process of constructing a California statewide spatial-temporal traffic accident dataset (CASTA), using two datasets named US accident [48] and California Department of Transportation (Caltrans) Performance Measurement System (PeMS) [49].US accident is a countrywide traffic accident dataset, which covers 49 states of the United States. The data are continuously being collected from February 2016, containing about 3.5 million accident records currently.PeMS provides access to real-time and historical performance data in many useful formats and presentation styles, including a consolidated database of traffic data collected by Caltrans placed on state highways throughout California, as well as other Caltrans and partner agency datasets.To figure out the spatial-temporal impact of each accident, we use the process shown in Figure12 to match and merge the two datasets—US accident and PeMS. It includes three important steps: data filter, integration, and extraction.Figure 12
Process of creating spatial-temporal accident dataset CASTA.


### 4.1. Data Filter

12,000 traffic accident records in California between February 2016 and February 2020 are filtered from the US accident datasets. The locations of the samples are all state motorways in California, and their distributions are given in Table3. For better representing the spatial characteristics of accidents, the statistical distribution of clean-up time (sum of detection, verification, response, and clearance time) of the selected records is shown in Figure 13, from 16 min to 8 h 40 min. It can be figured out that the clean-up time is not distributed evenly in the range, where more than 96% of the records fall in 25,120, and 25,30 is the interval with the highest amount. However, the records with clean-up time less than 25 min or higher than 240 min are not representative and not enough to train the model. Thus, we only include 11940 pieces of records with clean-up time fallen in 25,240 minutes in the experiment.Table 3
Locations of traffic accident records.
CountyMotorwayI-5I-805I-8I-15I-405I-605I-10I-880I-80I-280I-680TotalSan Diego69448439125800000001827Orange5230004102500000958Riverside000284001780000462Los Angeles7080001320690174100004459San Bernardino0002590086300001122Santa Clara00000003070317216840Alameda000000081824203791439Solano00000000605057662San Francisco00000000137940231Total192548439180117307152782112598441165212000Figure 13
Distribution of accident clean-up time.


### 4.2. Data Integration

The data integration process is about matching the traffic flow and speed data with traffic accident records. First, we extract the latitude and longitude coordinates and time of each accident record, denoted aslat,lng,t. Second, we find the nearest sensor to that coordination in PeMS and extract the flow and speed data after te. Third, concatenate the PeMS and US accident to form the new raw dataset. Note that disabled detectors have already been filtered out.


### 4.3. Data Extraction

By comparing with the upstream flow/speed afterte, figure out the accident full-recovery time TfrA, half-recovery time ThrA, maximum accumulative queue length LmaxA, and average accumulative queue length LaveA according to Algorithm 3. The final dataset CASTA consists of 20 attributes that fall in 6 main types as given in Table 4.Table 4
Attributes in CASTA.
Attribute categoryAttributesValue and descriptionAccident attributeIdUnique identifier of the accident recordTMC event code202 serious accidents203 multivehicle accidents245 two-lane blocked246 three-lane blocked……Block lanesThe number of lanes affected by the accidentBlock distanceThe length of the road extent blocked by the accidentSpatial attributeLatitudeLatitude in GPS coordinate of the accident pointLongitudeLongitude in GPS coordinate of the accident pointCountyCounty in address fieldMotorway IDMotorway name in address fieldSensor IDUnique identifier of the nearest sensor to the accident pointTemporal attributeDay or night0 day1 nightWorkday or not0 workday1 holiday or weekendPeak hour or not0 morning peak hour1 evening peak hour2 normal periodWeather attribute0 sunny1 rain2 snow3 thunderstorm4 fogTraffic flow characteristic attributeFlow data seriesA matrix of flowrate of upstream sensors after accident happensSpeed data seriesA matrix of speed of upstream sensors after accident happensImpact attributeAccident clean-up timeSum of detection, verification, response, and clearance timeFull-recovery timeTime duration from clearance to the moment when no vehicle is accumulatedHalf-recovery timeTime duration from clearance to the moment when queue length is half of maximum accumulative queue lengthMaximum accumulative queue length—Average accumulative queue length—Algorithm 3: Data extraction from dataset.
(1)
Input(2)
se≔ the nearest sensor in PeMS to the location of traffic accident e(3)
S≔ upstream sensors set of se denoted by S=s1,s2,…sn(4)
te≔ the closest time point in PeMS to the start time of traffic accident e(5)
T≔ time point set in PeMS after te denoted by T=t1,t2,…tn, where ti−ti−1=5min(6)
Vi≔ speed of sensor si in T denoted by Vi=vsi,t1,vsi,t2,…,vsi,tn(7)
Tc≔ sum of detection, verification, response, and clearance time of traffic accident e(8)
Initialization(9)
Fdissipate←false means if the traffic flow is in dissipating process(10)
vthreshold←10mile/h means the vehicle is low-speed driving or waiting(11)
Forti in T do(12)
Forsj in S do(13)
Ifvsj,ti>vthreshold(14)
Then IfLmaxA<distancese,sj(15)
Then updateLmaxA=distancese,sj(16)
Else(17)
Fdissipate=true(18)
Ifdistancese,sj<LmaxA/2(19)
ThenThrA=ti−te(20)
End if(21)
End if(22)
UpdateLaveA←j−1∗LaveA+distancese,sj/j(23)
Break(24)
End for(25)
Ifj=1andFdissipate=true(26)
Then updateTtotal=ti−te(27)
Break(28)
End for(29)
TfrA=Ttotal−Tc(30)
Output(31)
TfrA≔ full-recovery time of traffic accident e(32)
ThrA≔ half-recovery time of traffic accident e(33)
LmaxA≔ maximum accumulative queue length(34)
LaveA≔ average accumulative queue length


## 4.1. Data Filter

12,000 traffic accident records in California between February 2016 and February 2020 are filtered from the US accident datasets. The locations of the samples are all state motorways in California, and their distributions are given in Table3. For better representing the spatial characteristics of accidents, the statistical distribution of clean-up time (sum of detection, verification, response, and clearance time) of the selected records is shown in Figure 13, from 16 min to 8 h 40 min. It can be figured out that the clean-up time is not distributed evenly in the range, where more than 96% of the records fall in 25,120, and 25,30 is the interval with the highest amount. However, the records with clean-up time less than 25 min or higher than 240 min are not representative and not enough to train the model. Thus, we only include 11940 pieces of records with clean-up time fallen in 25,240 minutes in the experiment.Table 3
Locations of traffic accident records.
CountyMotorwayI-5I-805I-8I-15I-405I-605I-10I-880I-80I-280I-680TotalSan Diego69448439125800000001827Orange5230004102500000958Riverside000284001780000462Los Angeles7080001320690174100004459San Bernardino0002590086300001122Santa Clara00000003070317216840Alameda000000081824203791439Solano00000000605057662San Francisco00000000137940231Total192548439180117307152782112598441165212000Figure 13
Distribution of accident clean-up time.


## 4.2. Data Integration

The data integration process is about matching the traffic flow and speed data with traffic accident records. First, we extract the latitude and longitude coordinates and time of each accident record, denoted aslat,lng,t. Second, we find the nearest sensor to that coordination in PeMS and extract the flow and speed data after te. Third, concatenate the PeMS and US accident to form the new raw dataset. Note that disabled detectors have already been filtered out.


## 4.3. Data Extraction

By comparing with the upstream flow/speed afterte, figure out the accident full-recovery time TfrA, half-recovery time ThrA, maximum accumulative queue length LmaxA, and average accumulative queue length LaveA according to Algorithm 3. The final dataset CASTA consists of 20 attributes that fall in 6 main types as given in Table 4.Table 4
Attributes in CASTA.
Attribute categoryAttributesValue and descriptionAccident attributeIdUnique identifier of the accident recordTMC event code202 serious accidents203 multivehicle accidents245 two-lane blocked246 three-lane blocked……Block lanesThe number of lanes affected by the accidentBlock distanceThe length of the road extent blocked by the accidentSpatial attributeLatitudeLatitude in GPS coordinate of the accident pointLongitudeLongitude in GPS coordinate of the accident pointCountyCounty in address fieldMotorway IDMotorway name in address fieldSensor IDUnique identifier of the nearest sensor to the accident pointTemporal attributeDay or night0 day1 nightWorkday or not0 workday1 holiday or weekendPeak hour or not0 morning peak hour1 evening peak hour2 normal periodWeather attribute0 sunny1 rain2 snow3 thunderstorm4 fogTraffic flow characteristic attributeFlow data seriesA matrix of flowrate of upstream sensors after accident happensSpeed data seriesA matrix of speed of upstream sensors after accident happensImpact attributeAccident clean-up timeSum of detection, verification, response, and clearance timeFull-recovery timeTime duration from clearance to the moment when no vehicle is accumulatedHalf-recovery timeTime duration from clearance to the moment when queue length is half of maximum accumulative queue lengthMaximum accumulative queue length—Average accumulative queue length—Algorithm 3: Data extraction from dataset.
(1)
Input(2)
se≔ the nearest sensor in PeMS to the location of traffic accident e(3)
S≔ upstream sensors set of se denoted by S=s1,s2,…sn(4)
te≔ the closest time point in PeMS to the start time of traffic accident e(5)
T≔ time point set in PeMS after te denoted by T=t1,t2,…tn, where ti−ti−1=5min(6)
Vi≔ speed of sensor si in T denoted by Vi=vsi,t1,vsi,t2,…,vsi,tn(7)
Tc≔ sum of detection, verification, response, and clearance time of traffic accident e(8)
Initialization(9)
Fdissipate←false means if the traffic flow is in dissipating process(10)
vthreshold←10mile/h means the vehicle is low-speed driving or waiting(11)
Forti in T do(12)
Forsj in S do(13)
Ifvsj,ti>vthreshold(14)
Then IfLmaxA<distancese,sj(15)
Then updateLmaxA=distancese,sj(16)
Else(17)
Fdissipate=true(18)
Ifdistancese,sj<LmaxA/2(19)
ThenThrA=ti−te(20)
End if(21)
End if(22)
UpdateLaveA←j−1∗LaveA+distancese,sj/j(23)
Break(24)
End for(25)
Ifj=1andFdissipate=true(26)
Then updateTtotal=ti−te(27)
Break(28)
End for(29)
TfrA=Ttotal−Tc(30)
Output(31)
TfrA≔ full-recovery time of traffic accident e(32)
ThrA≔ half-recovery time of traffic accident e(33)
LmaxA≔ maximum accumulative queue length(34)
LaveA≔ average accumulative queue length


## 5. Experiments and Results

Methods proposed in Section3 have been tested with the CASTA dataset, and the results are discussed in this section. Among the 11940 pieces of records, 9940 of them are randomly chosen as the training set, while the rest 2000 are used as the test set. Since no similar previous work that predicts the whole accident process has been proposed yet, the comparison is carried out in each stage, respectively. First, the outcomes of the first two stages without the online adaptation are presented. Second, the online stage is added to test how the outcomes have been improved. Experiments have been implemented on the server with four CPU (Intel Xeon (R) CPU E5-2650 v2 @ 2.60 GHz), 32 GB RAM.


### 5.1. Offline Prediction Analysis

#### 5.1.1. Clean-Up Time Analysis

The efficiency of the initial clean-up time prediction is essential to the following stages, since the error will be further propagated and lead to larger mistakes. According to the cluster results, the clean-up time has been divided into 13 groups, where group 13 is a noise cluster. Table5 presents the interval of each group and its corresponding centroid value.Table 5
Clustering results.
Cluster no.Clean-up time intervalCentroid value125,3028.73230,3430.89334,4036.65440,4843.02548,5349.22653,5856.87758,6260.11862,7668.35976,9184.251091,10898.3711108,116113.0312116,125118.0813 (noise cluster)125,240130.90When comparing the performance of classifiers, the classification accuracy which means the proportion that predicted class is equal to the real class is usually calculated. However, in this case, since the specific value of clean-up time is more important than the class, the classification accuracy is replaced by the MAPE and RMSE in the following equations, respectively, by comparing the predicted clean-up timeTclP and actual clean-up time TclA.(5)MAPE=∑i=1nTclA−TclPTclA×100n,(6)RMSE=1n∑i=1nTclA−TclP2.In order to verify the suitability of our proposed model (mean-shift clustering and SNNs classifier), several methods have been selected as comparison benchmarks: nonlinear regression [50], KNN [51], ANNs, and mean-shift clustering and ANNs classifier. Noticing that the first three benchmarks directly build the relationship between accident attributes and clean-up time without the clustering process, while the fourth replaces the SNNs classifier by ANNs. The experiment results are given in Table 6. Our proposed method outperforms all other benchmarks in accuracy and training time. Mean-shift clustering and ANNs classifier ranks first in the comparing methods, but still needs more running time and higher MAPE and RMSE. The other three benchmarks achieves unsatisfied prediction accuracy due to the lacks of combination of clustering and classification. The results prove that clustering the records into classes and using the centroid value to present the predicted value is better than direct prediction model when the data are dispersive distributed, as well as the suitability of applying SNNs in capturing spatial and temporal features.Table 6
Prediction performance comparison of clean-up time.
MethodMAPE (%)RMSETraining time (h)Nonlinear regression29.3330.97—KNN30.0228.05—ANNs28.5823.645.50Mean-shift clustering and ANNs classifier14.3011.194.88Mean-shift clustering and SNNs classifier (ours)12.078.133.20For better analysis of the model performance, the accuracy in each interval is calculated, respectively, as given in Table7. It can be figured out that MAPE and RMSE are relatively low in intervals with abundant records, e.g., 25,30 and 40,50. In contrast, the prediction difficulty of intervals that clustered as noise (e.g., 120,240) is relatively high and the accuracy is not satisfied due to insufficient training. Fortunately, the probability of such severe accidents is low enough and will not cause frequent impact on traffic. Furthermore, with the increase of historic accident data, those outliers can be removed from the noise cluster and the accuracy can be further improved.Table 7
MAPE and RMSE in clean-up time intervals.
Clean-up time interval (min)MAPE (%)RMSE25,303.622.6430,409.064.3240,505.303.0850,6010.876.3760,1209.0118.26120,24043.9050.20


#### 5.1.2. Clean-Up Phase Queue Length Analysis

In this section, the performance of CNNs based queue length prediction is analyzed, using the output of the previous stage. Comparison benchmarks include the shockwave theory [18], nonlinear regression, and ANNs. Shockwave theory assumes that the traffic flow and speed is constant at the accident site and upstream. It takes traffic flow as a continuous fluid with a flow (q)-density (k) relationship and uses equation (7) to calculate the shockwave when the state of a traffic stream changes from qi,ki to qj,kj [18]. The length of block area is neglected in the shockwave theory.(7)Wij=qj−qikj−ki.Due to inability of capturing picture input, other two benchmarks set up relationships between constant flow, speed, block length, and queue length.In Table8, MAPE and RMSE of the proposed model and other benchmarks are listed based on number of lanes. 4-lane cases, 5-lane cases, and 6-lane cases account for 19%, 27%, and 54%, respectively. The proposed CNNs based model still outperforms other benchmarks in MAPE and RMSE in all three cases. Shockwave theory is unable to make efficient prediction due to unrealistic assumption, while nonlinear regression and ANNs make similar performance but are still not satisfied due to constant traffic information. Considered together with the distribution of queue length shown in Figure 14, the 4-lane model and 5-lane model have simple environment that leads to high prediction accuracy. With the increase of lanes, the traffic itself can absorb the disturbance better; thus, the accumulated queue length becomes shorter. That explains the high MAPE but low RMSE in 6-lane case.Table 8
Prediction performance comparison of queue length.
Method4-lane (19%)5-lane (27%)6-lane (54%)AverageMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEShockwave theory30.030.1728.980.1536.790.1533.400.15Nonlinear regression22.300.1321.070.1327.090.1224.550.12ANNs22.090.1223.500.1026.850.0825.040.09CNNs (ours)16.810.0715.060.0620.770.0518.480.06Figure 14
Distribution of clean-up phase queue length.The MAPE of 6-lane cases grouped according to the length of the queue is also calculated and shown in Figure15. It can be concluded that the MAPE of queue length in 0.4,2.2 miles is below 20%, while the model performs relatively poor when the queue length is below 2 miles and above 2.2 miles. The cause of error in low queue length is the quality of the PeMS dataset, where the distance between sensors is not small enough to give accurate queue length. For example, if the actual queue length of an accident is 0.06 miles while the distance between the closet sensors is 0.1 miles, then the queue length will be regarded as 0. That kind of errors will greatly affect the model performance, especially in low queue length cases. Meanwhile, when the accumulative queue length is greater than 2.2 miles, the model needs larger input to capture the environment, and thus, 5-mile is not enough to make accurate prediction.Figure 15
MAPE and RMSE in queue length intervals of 6-lane cases. The cross-point represents the average value in that interval.Though the proposed model has already achieved better performance than other methods, the accuracy would still improve if trained by a more complete dataset. The merging process of US accident and PeMS can expand the error in some situation. For example, the coordination bias errors in US accident will result in an offset when matching the closet sensor in PeMS.


#### 5.1.3. Recovery Phase Spatial-Temporal Impact Analysis

In the last stage of the offline prediction, the model will give out the final predicted spatial-temporal impact during the recovery process. Comparison benchmarks include shockwave theory, nonlinear regression, and BPNNs (base). The proposed model will use the output data of the CNNs model in the previous stage, while shockwave theory and nonlinear regression will still be based on the result using the same method, which means the performance analysis already includes the error of previous stages. Comparing to our proposed model that uses historical average flow/speed as input, the BPNN (base) only uses the value at the beginning of the recovery phase. According to the results given in Table9, the error of the shockwave theory and nonlinear regression continues to expand. The MAPE of maximum accumulative queue length even reaches 40.47%, which losses its reference value. The BPNN (base) stably ranks the second under all assessment criteria, just behind our proposed method. Due to the comprehensive representation of traffic environment and the use of historical average value, the proposed model achieves satisfying performance, where the MAPE of four impact variables are all below 20%.Table 9
Prediction performance comparison of spatial-temporal impact.
Method4-lane (19%)5-lane (27%)6-lane (54%)AverageMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEFull-recovery time (minute)Shockwave theory30.8833.9630.0532.7727.2829.8828.7131.44Nonlinear regression29.0731.5427.9631.0826.0326.0327.1328.44BPNNs (base)24.5526.0525.3725.7324.0722.3624.5123.97BPNNs (ours)19.3018.0320.0517.9917.9315.0218.7616.39Half-recovery time (min)Shockwave theory36.5222.5832.9520.3033.8420.1734.1120.66Nonlinear regression27.3318.0727.7417.9426.3217.7226.9017.85BPNNs (base)21.8016.3322.9315.0221.0113.2221.6814.30BPNNs (ours)18.7111.2617.9710.3818.029.9618.1410.32Maximum accumulative queue length (mile)Shockwave theory38.740.5238.550.5042.030.4740.470.49Nonlinear regression29.750.3728.030.3332.550.3430.800.34BPNNs (base)21.740.3123.090.3124.110.2723.380.29BPNNs (ours)18.240.2418.010.2121.390.1919.880.20Average accumulative queue length (mile)Shockwave theory35.520.4336.040.3640.540.3538.370.37Nonlinear regression26.220.2622.340.1925.620.2524.850.23BPNNs (base)18.410.2020.030.1622.570.1921.090.18BPNNs (ours)16.280.1917.260.1220.090.1318.600.14Although there is no existing work considering the whole accident process that can be used as comparing benchmark, the above separate comparison in each offline stage still illustrates the effectiveness of our proposed method. The offline part can be regarded as the combination of three different models developed for the characteristics in each stage, and the advantages are further expanded after the combination.


### 5.2. Online Prediction Analysis

Although the accuracy of offline prediction is already much higher than other comparing benchmarks, it is still not satisfying enough for providing precise information and guidance for governments and travelers. Especially for accidents with long time span, as shown in Figure16, the error can be as large as 40%. To compensate for the difficulty in long-term prediction, the online prediction phase is carried out and analyzed to see how much improvement it can bring.Figure 16
MAPE in spatial-temporal impact in accident duration intervals of 6-lane cases. The cross-point represents the average value in that interval.Taking the 6-lane cases as examples, 10 accidents in each clean-up time interval given in Table10 are chosen as the test set (60 accidents in total) in this stage. According to statistical results given in Table 10, the actual clean-up time of 29 accidents is larger than the predicted ones, while 28 is smaller, and the rest 3 are equal. Apply error detection and adaptation mechanism to these test cases, and an averaged result per interval is given in Table 11. Reduction of MAPE is visible from any interval and impact variable when the final adaptation is done.Table 10
Clean-up time differences distribution in intervals.
Clean-up time interval25,6060,9090,120120,150150,180180,240TotalTclA>TclP54652729TclA=TclP2010003TclA<TclP36358328Table 11
Average MAPE in clean-up time intervals before and after adaptation.
Clean-up time interval25,60 (%)60,90 (%)90,120 (%)120,150 (%)150,180 (%)180,240 (%)Average (%)TfrOffline18.4013.3615.6214.3921.0744.8021.27Online16.3310.5210.0712.3517.0924.3715.12ThrOffline20.9516.0712.4514.8920.0538.5820.50Online17.8615.0110.9911.3717.2920.5515.51LmaxOffline19.3720.2820.8022.3622.5527.6422.17Online17.7017.2516.8318.7717.0518.4217.67LaveOffline18.1419.4716.1423.7621.6530.4821.61Online15.1717.9314.8219.9018.9521.0717.97To further find out how the improvement is made in each test case, the detailed MAPE difference in full-recovery time of 60 cases is shown in Figure17, where values above 0 represent cases with less error, while negative values represent cases with more error. It can be concluded that most of the cases except for one accident (in red) experienced lower MAPE, and the differences range from −0.28% to 32.98%. Along with the increase of accident clean-up time, the improvement becomes more evident. That is reasonable since cases with longer clean-up time always experience more times of adaptation.Figure 17
MAPE difference distribution of full-recovery time.In Figure18, 6 accidents are randomly picked to show how MAPE of full-recovery time changes along with the increase in adaptation times, where the adaptation interval is 5 minutes. The overall trend for all cases is gradually decreasing, where the least of them has experienced one adaptation, while the most has experienced 8 times of adaptation. Even after a few times of adaptation, the model can achieve a much better accuracy, which conveys the effectiveness of this mechanism.Figure 18
MAPE of full-recovery time along with the increase in adaptation times.In the second step of online stage, the clustering and prediction model will be modified and updated to improve the future prediction. To reduce workload, this process should be carried out until a batch of data has been gathered. Due to the dataset size limit, there is no enough cases to support to show the obvious change in model parameters and improvements after retraining. Thus, the result analysis of this step is not represented in this work, but can be supplemented when applied to more datasets in the future.All of the results and discussion above point to the same conclusion: the introduction of online stage can greatly improve the model performance.


## 5.1. Offline Prediction Analysis

### 5.1.1. Clean-Up Time Analysis

The efficiency of the initial clean-up time prediction is essential to the following stages, since the error will be further propagated and lead to larger mistakes. According to the cluster results, the clean-up time has been divided into 13 groups, where group 13 is a noise cluster. Table5 presents the interval of each group and its corresponding centroid value.Table 5
Clustering results.
Cluster no.Clean-up time intervalCentroid value125,3028.73230,3430.89334,4036.65440,4843.02548,5349.22653,5856.87758,6260.11862,7668.35976,9184.251091,10898.3711108,116113.0312116,125118.0813 (noise cluster)125,240130.90When comparing the performance of classifiers, the classification accuracy which means the proportion that predicted class is equal to the real class is usually calculated. However, in this case, since the specific value of clean-up time is more important than the class, the classification accuracy is replaced by the MAPE and RMSE in the following equations, respectively, by comparing the predicted clean-up timeTclP and actual clean-up time TclA.(5)MAPE=∑i=1nTclA−TclPTclA×100n,(6)RMSE=1n∑i=1nTclA−TclP2.In order to verify the suitability of our proposed model (mean-shift clustering and SNNs classifier), several methods have been selected as comparison benchmarks: nonlinear regression [50], KNN [51], ANNs, and mean-shift clustering and ANNs classifier. Noticing that the first three benchmarks directly build the relationship between accident attributes and clean-up time without the clustering process, while the fourth replaces the SNNs classifier by ANNs. The experiment results are given in Table 6. Our proposed method outperforms all other benchmarks in accuracy and training time. Mean-shift clustering and ANNs classifier ranks first in the comparing methods, but still needs more running time and higher MAPE and RMSE. The other three benchmarks achieves unsatisfied prediction accuracy due to the lacks of combination of clustering and classification. The results prove that clustering the records into classes and using the centroid value to present the predicted value is better than direct prediction model when the data are dispersive distributed, as well as the suitability of applying SNNs in capturing spatial and temporal features.Table 6
Prediction performance comparison of clean-up time.
MethodMAPE (%)RMSETraining time (h)Nonlinear regression29.3330.97—KNN30.0228.05—ANNs28.5823.645.50Mean-shift clustering and ANNs classifier14.3011.194.88Mean-shift clustering and SNNs classifier (ours)12.078.133.20For better analysis of the model performance, the accuracy in each interval is calculated, respectively, as given in Table7. It can be figured out that MAPE and RMSE are relatively low in intervals with abundant records, e.g., 25,30 and 40,50. In contrast, the prediction difficulty of intervals that clustered as noise (e.g., 120,240) is relatively high and the accuracy is not satisfied due to insufficient training. Fortunately, the probability of such severe accidents is low enough and will not cause frequent impact on traffic. Furthermore, with the increase of historic accident data, those outliers can be removed from the noise cluster and the accuracy can be further improved.Table 7
MAPE and RMSE in clean-up time intervals.
Clean-up time interval (min)MAPE (%)RMSE25,303.622.6430,409.064.3240,505.303.0850,6010.876.3760,1209.0118.26120,24043.9050.20


### 5.1.2. Clean-Up Phase Queue Length Analysis

In this section, the performance of CNNs based queue length prediction is analyzed, using the output of the previous stage. Comparison benchmarks include the shockwave theory [18], nonlinear regression, and ANNs. Shockwave theory assumes that the traffic flow and speed is constant at the accident site and upstream. It takes traffic flow as a continuous fluid with a flow (q)-density (k) relationship and uses equation (7) to calculate the shockwave when the state of a traffic stream changes from qi,ki to qj,kj [18]. The length of block area is neglected in the shockwave theory.(7)Wij=qj−qikj−ki.Due to inability of capturing picture input, other two benchmarks set up relationships between constant flow, speed, block length, and queue length.In Table8, MAPE and RMSE of the proposed model and other benchmarks are listed based on number of lanes. 4-lane cases, 5-lane cases, and 6-lane cases account for 19%, 27%, and 54%, respectively. The proposed CNNs based model still outperforms other benchmarks in MAPE and RMSE in all three cases. Shockwave theory is unable to make efficient prediction due to unrealistic assumption, while nonlinear regression and ANNs make similar performance but are still not satisfied due to constant traffic information. Considered together with the distribution of queue length shown in Figure 14, the 4-lane model and 5-lane model have simple environment that leads to high prediction accuracy. With the increase of lanes, the traffic itself can absorb the disturbance better; thus, the accumulated queue length becomes shorter. That explains the high MAPE but low RMSE in 6-lane case.Table 8
Prediction performance comparison of queue length.
Method4-lane (19%)5-lane (27%)6-lane (54%)AverageMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEShockwave theory30.030.1728.980.1536.790.1533.400.15Nonlinear regression22.300.1321.070.1327.090.1224.550.12ANNs22.090.1223.500.1026.850.0825.040.09CNNs (ours)16.810.0715.060.0620.770.0518.480.06Figure 14
Distribution of clean-up phase queue length.The MAPE of 6-lane cases grouped according to the length of the queue is also calculated and shown in Figure15. It can be concluded that the MAPE of queue length in 0.4,2.2 miles is below 20%, while the model performs relatively poor when the queue length is below 2 miles and above 2.2 miles. The cause of error in low queue length is the quality of the PeMS dataset, where the distance between sensors is not small enough to give accurate queue length. For example, if the actual queue length of an accident is 0.06 miles while the distance between the closet sensors is 0.1 miles, then the queue length will be regarded as 0. That kind of errors will greatly affect the model performance, especially in low queue length cases. Meanwhile, when the accumulative queue length is greater than 2.2 miles, the model needs larger input to capture the environment, and thus, 5-mile is not enough to make accurate prediction.Figure 15
MAPE and RMSE in queue length intervals of 6-lane cases. The cross-point represents the average value in that interval.Though the proposed model has already achieved better performance than other methods, the accuracy would still improve if trained by a more complete dataset. The merging process of US accident and PeMS can expand the error in some situation. For example, the coordination bias errors in US accident will result in an offset when matching the closet sensor in PeMS.


### 5.1.3. Recovery Phase Spatial-Temporal Impact Analysis

In the last stage of the offline prediction, the model will give out the final predicted spatial-temporal impact during the recovery process. Comparison benchmarks include shockwave theory, nonlinear regression, and BPNNs (base). The proposed model will use the output data of the CNNs model in the previous stage, while shockwave theory and nonlinear regression will still be based on the result using the same method, which means the performance analysis already includes the error of previous stages. Comparing to our proposed model that uses historical average flow/speed as input, the BPNN (base) only uses the value at the beginning of the recovery phase. According to the results given in Table9, the error of the shockwave theory and nonlinear regression continues to expand. The MAPE of maximum accumulative queue length even reaches 40.47%, which losses its reference value. The BPNN (base) stably ranks the second under all assessment criteria, just behind our proposed method. Due to the comprehensive representation of traffic environment and the use of historical average value, the proposed model achieves satisfying performance, where the MAPE of four impact variables are all below 20%.Table 9
Prediction performance comparison of spatial-temporal impact.
Method4-lane (19%)5-lane (27%)6-lane (54%)AverageMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEFull-recovery time (minute)Shockwave theory30.8833.9630.0532.7727.2829.8828.7131.44Nonlinear regression29.0731.5427.9631.0826.0326.0327.1328.44BPNNs (base)24.5526.0525.3725.7324.0722.3624.5123.97BPNNs (ours)19.3018.0320.0517.9917.9315.0218.7616.39Half-recovery time (min)Shockwave theory36.5222.5832.9520.3033.8420.1734.1120.66Nonlinear regression27.3318.0727.7417.9426.3217.7226.9017.85BPNNs (base)21.8016.3322.9315.0221.0113.2221.6814.30BPNNs (ours)18.7111.2617.9710.3818.029.9618.1410.32Maximum accumulative queue length (mile)Shockwave theory38.740.5238.550.5042.030.4740.470.49Nonlinear regression29.750.3728.030.3332.550.3430.800.34BPNNs (base)21.740.3123.090.3124.110.2723.380.29BPNNs (ours)18.240.2418.010.2121.390.1919.880.20Average accumulative queue length (mile)Shockwave theory35.520.4336.040.3640.540.3538.370.37Nonlinear regression26.220.2622.340.1925.620.2524.850.23BPNNs (base)18.410.2020.030.1622.570.1921.090.18BPNNs (ours)16.280.1917.260.1220.090.1318.600.14Although there is no existing work considering the whole accident process that can be used as comparing benchmark, the above separate comparison in each offline stage still illustrates the effectiveness of our proposed method. The offline part can be regarded as the combination of three different models developed for the characteristics in each stage, and the advantages are further expanded after the combination.


## 5.1.1. Clean-Up Time Analysis

The efficiency of the initial clean-up time prediction is essential to the following stages, since the error will be further propagated and lead to larger mistakes. According to the cluster results, the clean-up time has been divided into 13 groups, where group 13 is a noise cluster. Table5 presents the interval of each group and its corresponding centroid value.Table 5
Clustering results.
Cluster no.Clean-up time intervalCentroid value125,3028.73230,3430.89334,4036.65440,4843.02548,5349.22653,5856.87758,6260.11862,7668.35976,9184.251091,10898.3711108,116113.0312116,125118.0813 (noise cluster)125,240130.90When comparing the performance of classifiers, the classification accuracy which means the proportion that predicted class is equal to the real class is usually calculated. However, in this case, since the specific value of clean-up time is more important than the class, the classification accuracy is replaced by the MAPE and RMSE in the following equations, respectively, by comparing the predicted clean-up timeTclP and actual clean-up time TclA.(5)MAPE=∑i=1nTclA−TclPTclA×100n,(6)RMSE=1n∑i=1nTclA−TclP2.In order to verify the suitability of our proposed model (mean-shift clustering and SNNs classifier), several methods have been selected as comparison benchmarks: nonlinear regression [50], KNN [51], ANNs, and mean-shift clustering and ANNs classifier. Noticing that the first three benchmarks directly build the relationship between accident attributes and clean-up time without the clustering process, while the fourth replaces the SNNs classifier by ANNs. The experiment results are given in Table 6. Our proposed method outperforms all other benchmarks in accuracy and training time. Mean-shift clustering and ANNs classifier ranks first in the comparing methods, but still needs more running time and higher MAPE and RMSE. The other three benchmarks achieves unsatisfied prediction accuracy due to the lacks of combination of clustering and classification. The results prove that clustering the records into classes and using the centroid value to present the predicted value is better than direct prediction model when the data are dispersive distributed, as well as the suitability of applying SNNs in capturing spatial and temporal features.Table 6
Prediction performance comparison of clean-up time.
MethodMAPE (%)RMSETraining time (h)Nonlinear regression29.3330.97—KNN30.0228.05—ANNs28.5823.645.50Mean-shift clustering and ANNs classifier14.3011.194.88Mean-shift clustering and SNNs classifier (ours)12.078.133.20For better analysis of the model performance, the accuracy in each interval is calculated, respectively, as given in Table7. It can be figured out that MAPE and RMSE are relatively low in intervals with abundant records, e.g., 25,30 and 40,50. In contrast, the prediction difficulty of intervals that clustered as noise (e.g., 120,240) is relatively high and the accuracy is not satisfied due to insufficient training. Fortunately, the probability of such severe accidents is low enough and will not cause frequent impact on traffic. Furthermore, with the increase of historic accident data, those outliers can be removed from the noise cluster and the accuracy can be further improved.Table 7
MAPE and RMSE in clean-up time intervals.
Clean-up time interval (min)MAPE (%)RMSE25,303.622.6430,409.064.3240,505.303.0850,6010.876.3760,1209.0118.26120,24043.9050.20


## 5.1.2. Clean-Up Phase Queue Length Analysis

In this section, the performance of CNNs based queue length prediction is analyzed, using the output of the previous stage. Comparison benchmarks include the shockwave theory [18], nonlinear regression, and ANNs. Shockwave theory assumes that the traffic flow and speed is constant at the accident site and upstream. It takes traffic flow as a continuous fluid with a flow (q)-density (k) relationship and uses equation (7) to calculate the shockwave when the state of a traffic stream changes from qi,ki to qj,kj [18]. The length of block area is neglected in the shockwave theory.(7)Wij=qj−qikj−ki.Due to inability of capturing picture input, other two benchmarks set up relationships between constant flow, speed, block length, and queue length.In Table8, MAPE and RMSE of the proposed model and other benchmarks are listed based on number of lanes. 4-lane cases, 5-lane cases, and 6-lane cases account for 19%, 27%, and 54%, respectively. The proposed CNNs based model still outperforms other benchmarks in MAPE and RMSE in all three cases. Shockwave theory is unable to make efficient prediction due to unrealistic assumption, while nonlinear regression and ANNs make similar performance but are still not satisfied due to constant traffic information. Considered together with the distribution of queue length shown in Figure 14, the 4-lane model and 5-lane model have simple environment that leads to high prediction accuracy. With the increase of lanes, the traffic itself can absorb the disturbance better; thus, the accumulated queue length becomes shorter. That explains the high MAPE but low RMSE in 6-lane case.Table 8
Prediction performance comparison of queue length.
Method4-lane (19%)5-lane (27%)6-lane (54%)AverageMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEShockwave theory30.030.1728.980.1536.790.1533.400.15Nonlinear regression22.300.1321.070.1327.090.1224.550.12ANNs22.090.1223.500.1026.850.0825.040.09CNNs (ours)16.810.0715.060.0620.770.0518.480.06Figure 14
Distribution of clean-up phase queue length.The MAPE of 6-lane cases grouped according to the length of the queue is also calculated and shown in Figure15. It can be concluded that the MAPE of queue length in 0.4,2.2 miles is below 20%, while the model performs relatively poor when the queue length is below 2 miles and above 2.2 miles. The cause of error in low queue length is the quality of the PeMS dataset, where the distance between sensors is not small enough to give accurate queue length. For example, if the actual queue length of an accident is 0.06 miles while the distance between the closet sensors is 0.1 miles, then the queue length will be regarded as 0. That kind of errors will greatly affect the model performance, especially in low queue length cases. Meanwhile, when the accumulative queue length is greater than 2.2 miles, the model needs larger input to capture the environment, and thus, 5-mile is not enough to make accurate prediction.Figure 15
MAPE and RMSE in queue length intervals of 6-lane cases. The cross-point represents the average value in that interval.Though the proposed model has already achieved better performance than other methods, the accuracy would still improve if trained by a more complete dataset. The merging process of US accident and PeMS can expand the error in some situation. For example, the coordination bias errors in US accident will result in an offset when matching the closet sensor in PeMS.


## 5.1.3. Recovery Phase Spatial-Temporal Impact Analysis

In the last stage of the offline prediction, the model will give out the final predicted spatial-temporal impact during the recovery process. Comparison benchmarks include shockwave theory, nonlinear regression, and BPNNs (base). The proposed model will use the output data of the CNNs model in the previous stage, while shockwave theory and nonlinear regression will still be based on the result using the same method, which means the performance analysis already includes the error of previous stages. Comparing to our proposed model that uses historical average flow/speed as input, the BPNN (base) only uses the value at the beginning of the recovery phase. According to the results given in Table9, the error of the shockwave theory and nonlinear regression continues to expand. The MAPE of maximum accumulative queue length even reaches 40.47%, which losses its reference value. The BPNN (base) stably ranks the second under all assessment criteria, just behind our proposed method. Due to the comprehensive representation of traffic environment and the use of historical average value, the proposed model achieves satisfying performance, where the MAPE of four impact variables are all below 20%.Table 9
Prediction performance comparison of spatial-temporal impact.
Method4-lane (19%)5-lane (27%)6-lane (54%)AverageMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEMAPE (%)RMSEFull-recovery time (minute)Shockwave theory30.8833.9630.0532.7727.2829.8828.7131.44Nonlinear regression29.0731.5427.9631.0826.0326.0327.1328.44BPNNs (base)24.5526.0525.3725.7324.0722.3624.5123.97BPNNs (ours)19.3018.0320.0517.9917.9315.0218.7616.39Half-recovery time (min)Shockwave theory36.5222.5832.9520.3033.8420.1734.1120.66Nonlinear regression27.3318.0727.7417.9426.3217.7226.9017.85BPNNs (base)21.8016.3322.9315.0221.0113.2221.6814.30BPNNs (ours)18.7111.2617.9710.3818.029.9618.1410.32Maximum accumulative queue length (mile)Shockwave theory38.740.5238.550.5042.030.4740.470.49Nonlinear regression29.750.3728.030.3332.550.3430.800.34BPNNs (base)21.740.3123.090.3124.110.2723.380.29BPNNs (ours)18.240.2418.010.2121.390.1919.880.20Average accumulative queue length (mile)Shockwave theory35.520.4336.040.3640.540.3538.370.37Nonlinear regression26.220.2622.340.1925.620.2524.850.23BPNNs (base)18.410.2020.030.1622.570.1921.090.18BPNNs (ours)16.280.1917.260.1220.090.1318.600.14Although there is no existing work considering the whole accident process that can be used as comparing benchmark, the above separate comparison in each offline stage still illustrates the effectiveness of our proposed method. The offline part can be regarded as the combination of three different models developed for the characteristics in each stage, and the advantages are further expanded after the combination.


## 5.2. Online Prediction Analysis

Although the accuracy of offline prediction is already much higher than other comparing benchmarks, it is still not satisfying enough for providing precise information and guidance for governments and travelers. Especially for accidents with long time span, as shown in Figure16, the error can be as large as 40%. To compensate for the difficulty in long-term prediction, the online prediction phase is carried out and analyzed to see how much improvement it can bring.Figure 16
MAPE in spatial-temporal impact in accident duration intervals of 6-lane cases. The cross-point represents the average value in that interval.Taking the 6-lane cases as examples, 10 accidents in each clean-up time interval given in Table10 are chosen as the test set (60 accidents in total) in this stage. According to statistical results given in Table 10, the actual clean-up time of 29 accidents is larger than the predicted ones, while 28 is smaller, and the rest 3 are equal. Apply error detection and adaptation mechanism to these test cases, and an averaged result per interval is given in Table 11. Reduction of MAPE is visible from any interval and impact variable when the final adaptation is done.Table 10
Clean-up time differences distribution in intervals.
Clean-up time interval25,6060,9090,120120,150150,180180,240TotalTclA>TclP54652729TclA=TclP2010003TclA<TclP36358328Table 11
Average MAPE in clean-up time intervals before and after adaptation.
Clean-up time interval25,60 (%)60,90 (%)90,120 (%)120,150 (%)150,180 (%)180,240 (%)Average (%)TfrOffline18.4013.3615.6214.3921.0744.8021.27Online16.3310.5210.0712.3517.0924.3715.12ThrOffline20.9516.0712.4514.8920.0538.5820.50Online17.8615.0110.9911.3717.2920.5515.51LmaxOffline19.3720.2820.8022.3622.5527.6422.17Online17.7017.2516.8318.7717.0518.4217.67LaveOffline18.1419.4716.1423.7621.6530.4821.61Online15.1717.9314.8219.9018.9521.0717.97To further find out how the improvement is made in each test case, the detailed MAPE difference in full-recovery time of 60 cases is shown in Figure17, where values above 0 represent cases with less error, while negative values represent cases with more error. It can be concluded that most of the cases except for one accident (in red) experienced lower MAPE, and the differences range from −0.28% to 32.98%. Along with the increase of accident clean-up time, the improvement becomes more evident. That is reasonable since cases with longer clean-up time always experience more times of adaptation.Figure 17
MAPE difference distribution of full-recovery time.In Figure18, 6 accidents are randomly picked to show how MAPE of full-recovery time changes along with the increase in adaptation times, where the adaptation interval is 5 minutes. The overall trend for all cases is gradually decreasing, where the least of them has experienced one adaptation, while the most has experienced 8 times of adaptation. Even after a few times of adaptation, the model can achieve a much better accuracy, which conveys the effectiveness of this mechanism.Figure 18
MAPE of full-recovery time along with the increase in adaptation times.In the second step of online stage, the clustering and prediction model will be modified and updated to improve the future prediction. To reduce workload, this process should be carried out until a batch of data has been gathered. Due to the dataset size limit, there is no enough cases to support to show the obvious change in model parameters and improvements after retraining. Thus, the result analysis of this step is not represented in this work, but can be supplemented when applied to more datasets in the future.All of the results and discussion above point to the same conclusion: the introduction of online stage can greatly improve the model performance.


## 6. Conclusions

Traffic accidents post-impact prediction (TAPIP) plays an important role in traffic management. In this study, a 3-stage TAPIP model on highway is proposed and tested by the dataset CASTA. Using the advantages of SNNs, the model builds a comprehensive relationship between the spatial-temporal features of accidents and clean-up time. The combination of clustering and classification improves the prediction accuracy. Due to the capability of CNNs to fully capture the spatial characteristics of traffic environment and the use of historical average data, the model achieves effective prediction of post-impact variables (e.g., fully-recovery time, half-recovery time, maximum accumulative queue length, and average accumulative queue length). A new dataset CASTA that describes California statewide spatial-temporal traffic accidents is constructed and used to test the model. Experiment results prove that our model performs better in accuracy and running time than several existing benchmarks, including nonlinear regression and KNN. The introduction of online adaptation and updating the mechanism further expands the advantages of the model.This work implements a framework that describes the whole process of a traffic accident and captures the spatial-temporal characteristics in each phase. When applied in real world, whenever an accident takes place, the whole process can be predicted immediately. It proves the reliability and efficiency in applying SNNs in traffic domain, especially in accident prediction research. With regards to future work, we acknowledge that this work is not perfect and that there are still many aspects that can be improved upon. First, the dataset with more detailed accident information and higher quality traffic data can be used to improve the model performance. Second, accidents with clean-up time longer than 240 or shorter than 25 minutes can be further added into the model when enough records have been gathered. Third, clustering and classification updating in online stage needs further experimental demonstration. Last, the model can be extended to city roads rather than limited to highways.



---

*Source: 9290921-2021-12-02.xml*