Abstract Predicting available parking spaces is one of the key issues in intelligent parking guidance systems. Current neural network-based prediction techniques achieve an average absolute error of around 10 for short prediction periods, but the accuracy drops sharply with increasing prediction step size or period. To address this issue, this paper proposes a parking space prediction method that preserves data variation characteristics over medium- to long-term prediction periods. This method uses fuzzy information granularization to obtain feature datasets, trains a long short-term memory neural network to predict future feature datasets, and reconstructs the continuous change curve of available parking spaces for the entire interval based on data interpolation. Simulation results show that this method achieves higher prediction accuracy than traditional methods for available parking spaces at the same prediction step size; and while maintaining similar prediction accuracy, it has higher computational efficiency than traditional methods.
Keywords: parking guidance system; fuzzy information granulation; long short-term memory neural network; cubic spline interpolation
Chinese Library Classification Number: TG156 Document Identification Code: A
1. Introduction
In recent years, with the rapid development of the economy, the number of cars used by citizens has also increased rapidly, which has made the problem of parking difficulties in big cities more and more serious, and has also exacerbated urban traffic congestion. Research reports show that 30% of traffic congestion is caused by cars looking for parking spaces[1]. While looking for parking spaces, unnecessary exhaust emissions are also increased. Therefore, cities across the country are actively carrying out the construction of city-level parking guidance systems. Parking guidance systems help vehicles park quickly and alleviate parking difficulties by providing them with information such as parking lot location and the number of available parking spaces[2-4]. In parking guidance systems, available parking space prediction is a very important part. Vehicles need to know the number of available parking spaces in the surrounding parking lots when they arrive at their destination at a certain distance. Available parking space prediction technology can avoid the situation where vehicles arrive at the entrance of the parking lot only to find that it is full and cannot park, and at the same time guide vehicles to park in parking lots with more spacious parking spaces. Obviously, available parking space prediction is a typical time series prediction problem. Currently, the Autoregressive Integrated Moving Average Model (ARIMA) and wavelet neural networks can be used to achieve accurate short-term prediction. However, it's important to note that the high accuracy of this type of method relies on a fundamental condition: a sufficiently small number of prediction steps, typically 1 to 3. Increasing the number of prediction steps leads to a significant decrease in accuracy. Due to the complexity of urban traffic environments, it's often necessary to understand the available parking spaces in the surrounding area when a vehicle starts moving, and to predict the availability upon arrival. This process usually takes more than 30 minutes. If current prediction techniques are used directly, the time period of the prediction step is typically lengthened, such as to 10 minutes per step. While this allows for 3 prediction steps within 30 minutes, since only 30 minutes yields a prediction value, this effectively results in only 3 prediction values. Clearly, this significantly loses the more detailed characteristics of parking space changes within this time interval, negatively impacting the accuracy of the parking guidance system.
Currently, the common methods for real-time prediction of available parking spaces are mainly divided into two categories: one is the traditional time prediction model represented by ARIMA[5], and the other is the neural network prediction method[6,7]. Among them, the traditional time series prediction model mainly decomposes the time series data. For non-stationary series, it is also necessary to convert the non-stationary time series into a stationary time series through differentiating and other means to achieve prediction[8,9]. This prediction is easily affected by the model parameters, and its effectiveness will gradually decrease. The neural network method mainly achieves prediction by iteratively training on massive data and then fitting the data features. In related studies, Sun et al.[10] and Yong et al.[11] studied multi-layer feedforward training by error backpropagation algorithm.
Neural network models are used to predict parking space occupancy rates. Although they achieve parking space prediction, they have poor robustness and require a lot of time to calculate. Later, researchers [12-14] used wavelet neural networks to fit the characteristics of nonlinear complex systems well. Although they can make short-term predictions of available parking spaces, the prediction speed and stability have been greatly improved. However, they are only single-point predictions. Zheng et al. [15] used regression trees, neural networks and support vector machines to build a combined model to predict the continuous change of parking space status. However, with the increase of real-time data, the time cost of switching the dynamic combined model is also very expensive. None of the methods mentioned above can solve the problem of predicting the fluctuation range of available parking spaces well. Among them, most methods focus on point prediction. Although a few methods consider the changes and trends within the range, the computation time cost is also very high. In response to this problem, this paper proposes a prediction method - Fuzzy Long Short-Term Memory Network Prediction On Parking Spaces (FLOPS), which can maintain the data change characteristics within a long prediction time period and is suitable for high-precision prediction under conditions of a large time span (>30min). The method consists of three main steps: (1) extracting massive amounts of key information from historical parking data based on the Fuzzy Information Granulation (FIG) method [16] and constructing a feature set for a preset prediction period; (2) constructing a Long Short-Term Memory Network (LSTM) for the feature set and predicting the feature set for the next 1 to 3 prediction steps; (3) interpolating and reconstructing the prediction results of the obtained feature set based on 3rd-order spline interpolation, thereby obtaining the continuous change results of parking spaces within the prediction time period.
2. Research Methods
The continuous change status prediction of available parking spaces includes the prediction of changes in the number of available parking spaces and the prediction of peak parking times. This paper is mainly divided into three parts: (1) data transformation based on fuzzy information granularization to obtain the feature dataset corresponding to the time series data; (2) interval prediction model based on LSTM neural network to predict the change characteristics of the number of available parking spaces; (3) reconstruction algorithm based on cubic spline interpolation to obtain the continuous change status of available parking spaces.
2.1 Data Transformation Based on Fuzzy Information Granulation
Available parking spaces are a constantly changing data set over time. Faced with such a massive nonlinear time series dataset, this paper extracts key information through compression to obtain the corresponding feature data set. In this paper, a fuzzy information granulation (FIG) method is used to reconstruct and granulate the time series of available parking spaces. Fuzzy information granulation is an effective method for extracting key information from massive datasets. The fuzzy information granulation of the time series mainly consists of two processes:
(1) Divide the time series into several smaller subsequences, which will serve as the operation window;
(2) Blur each generated window to create fuzzy sets, i.e., fuzzy information particles. The processed data samples can retain the characteristics of the original sample data and obtain a series of smaller sample intervals, which facilitates subsequent data calculation.
The time series data X of the parking lot is shown in formula (1).
Where xi represents the available parking spaces at time ti. The time series data is divided into multiple subsequences by determining an equal-interval time granularity T (e.g., 2 minutes) according to actual needs. Each subsequence is treated as a granular window, and the minimum and maximum values of available parking spaces in each granular window, as well as the available parking spaces corresponding to the initial and final time points within each granular window, are obtained. Here, lowk and upk represent the minimum and maximum values of available parking spaces within the k-th granular window, respectively, and startk and endk represent the initial and final available parking space values within the k-th granular window, i.e., ...
k=1,2......,n. Therefore, four feature data are used to reasonably represent the data within the original window, simplifying the original time series, i.e., granularizing the time series data with fuzzy information. After obtaining the low and up values, the peak times t_low and t_up corresponding to the low and up values can be obtained by combining the time attributes within each window, resulting in Y_1 , Y_2 , ..., Y_n . The time is converted to a timestamp T_stamp because the converted timestamp value is very large and difficult to fit the data features; therefore, a time offset t' is defined.
Where t is the timestamp at 00:00 on the predicted day; Tst is the current timestamp; T is the determined time granularity; and k is the k-th granular window. Thus, the peak time within each granular window is transformed into a value within the range (0, 60T). Finally, the fuzzy information of each sub-sequence window is combined to obtain matrices X and Y'. Where:
2.2 Prediction Model Based on Long Short-Term Memory Neural Network
Data transformation yields a feature matrix with fuzzy information, used to predict changes in the number of available parking spaces. This paper considers a prediction model with memory patterns, which can correlate data from previous times for better results. Long Short-Term Memory (LSTM) neural networks are a special type of recurrent neural network and a common method for time series analysis. They overcome the gradient explosion and decay problems encountered by traditional recurrent neural networks during backpropagation. By adding memory units in the hidden layers, they correlate short and long time periods of the time series, controlling the deletion and storage of relevant information, thus forming a memory network. The memory unit structure in this paper is shown in Figure 1, mainly composed of input gates, output gates, forget gates, and storage units. The gates are a method for selectively passing information; they contain a sigmoid function to determine which parts of the storage unit's state need to be output, and then pass through a tanh function to obtain the desired output data.
In this paper, the LSTM prediction model contains multiple LSTM memory units. Min-Max Normalization is selected for data normalization; Adam is chosen as the optimizer; and mean squared error is chosen as the loss function. Feature matrices X and Y' are used as model inputs, where the prediction of available berth quantity changes is achieved by matrix X, and the prediction of peak time is achieved by matrix Y'. The change in available berth quantity P<sub> k+1 </sub> = (start<sub>k +1 </sub>, low<sub>k+1</sub>, up<sub>k+ 1</sub> , end<sub> k+1 </sub> ) and the corresponding peak times t' <sub>lowk </sub> and t'<sub> upk</sub> are calculated iteratively using the LSTM hidden layers. The algorithm flow is as follows:
2.3 Spline Interpolation Reconstruction
The LSTM neural network model predicts start k+1 , low k+1 , up k+1 , end k+1 , and t' upk+1 and t' lowk+1 (where start k+1 and end k+1 are the number of available parking spaces corresponding to the starting and ending points within the k+1th granular window). After obtaining the corresponding predicted feature data, the changing characteristics of the number of available parking spaces are obtained. These feature data are discrete in numerical distribution. Interpolation uses this discrete data to determine the parameters of a known function or find an approximate function, ensuring a high degree of fit between the approximate function and the known data. Finally, the simulated value at the "breakpoint" is obtained to reconstruct the curve. Therefore, to reconstruct the continuous change in the number of available parking spaces within the prediction interval from these feature data, this paper uses cubic spline interpolation for the corresponding data processing. This is because, compared to higher-order splines, it requires less computation and storage and is more stable, achieving a reasonable trade-off between flexibility and computational speed. The specific interpolation reconstruction process is as follows:
(1) Sort the time in the (k+1)th particle window in ascending order, divide it into intervals, and determine the available parking space value at the corresponding time.
Here, x<sub> j</sub> and y<sub> j</sub> represent the number of available parking spaces at a given time and point in time; m<sub> j </sub> is a constant value. The constructed interpolation function is used to reconstruct the interval. Then, the curve for that interval is interpolated to obtain the predicted time series data corresponding to the predicted feature data of that interval. Next, the same method is used for the other two intervals to obtain the predicted time series data corresponding to their predicted feature data. Finally, the predicted time series data from each interval are merged to obtain the complete predicted time series data, thus revealing the trend of fluctuations in available parking spaces.
3. Parking space prediction experiment and results analysis
3.1 Data Transformation
This paper selects parking data from the above-ground parking lot of Baolin Jewelry Center in Luohu District, Shenzhen, Guangdong Province as experimental data. The statistical period is from July 3 to July 5, 2016. The original available parking space data is shown in Figure 2. The data sampling frequency is to record the data of unoccupied parking spaces once per minute, so there are 1440 data points per day.
Based on FIG theory, this paper sets the time granularity T to 30 minutes, meaning that every 30 points are selected as a granular window, resulting in 48 granular windows per day. A fuzzy set is established within each granular window, and the fuzzy granulation results are shown in Figure 3. In the figure, each bar consists of four feature data values: start, low, up, and end. Hollow bars indicate that the number of available parking spaces increases during this time period, while solid bars indicate that the number of available parking spaces decreases. Within each granular window, the number of available parking spaces fluctuates between the maximum value (up) and the minimum value (low), while the data volume decreases from 1440 per day to 192 (48 × 4). Thus, fuzzy feature data of available parking spaces is obtained, which can be used to predict the changes in the number of available parking spaces.
3.2 Prediction Results Based on Long Short-Term Memory Neural Network
Predicting changes in the number of available parking spaces is based on an LSTM neural network model. Many parameters of the neural network need to be set, and adjusting the hyperparameters and configuring the model structure to aggregate the optimal parameters is crucial. This paper implements the prediction of future changes in the number of parking spaces and peak time prediction in two stages. The network used for predicting changes in the number of parking spaces has 4 neurons in both the input and output layers, and 10 neurons in the hidden LSTM layer. The network used for peak time prediction has 2 neurons in the output layer, while the other layers remain unchanged. First, the LSTM neural network is trained using parking feature data from July 3rd to July 5th, 2016 (i.e., the X and Y' matrices after FIG transformation). The network is trained 100 times, terminating training after exceeding this limit. Then, the trained network model is saved and used to predict changes in available parking spaces. This paper uses data from July 6th, 2016 for testing, taking the feature data from the first three time points—the changes in the number of parking spaces and the peak time—as input to iteratively predict the feature data for the next time point. The experimental results are shown in Figure 4. In Figure 4, the curves reflect the comparison between the actual number of parking spaces and the predicted value. The average absolute error of the overall prediction for start, up, low, and end is 2.26.
3.3 Comparative Analysis of Experimental Results
The prediction yields feature data of available parking spaces for the next moment, but this only includes the available parking spaces and their occurrence times for four points. To allow users to clearly understand the continuous changes in available parking spaces in the target parking lot within the next 10 minutes, this paper uses a cubic spline interpolation algorithm to reconstruct the continuous change curve of available parking spaces. As shown in Figure 5, each 10-minute interval is a prediction interval, with three intervals from 17:00 to 17:30. Interpolation in each interval yields the continuous change of available parking spaces within the prediction time period. In Figure 5, the curve "original" represents the actual available parking space situation. A comparison of Figure 5 shows that when the time step is 10 minutes, the LSTM neural network prediction can only obtain one point, and the change trend of the interval can only directly connect the points. However, the interval change trend prediction model FLOPS proposed in this paper not only knows the available parking space information for each point within the interval, but also has better accuracy than LSTM. Furthermore, it can also identify when parking peaks occur within the interval, allowing users to grasp more parking information.
Next, the root mean square error (RMSE) of the two methods is compared, and the results are shown in Figure 6. Combining the feature data reconstruction comparison chart (Figure 5) and the error analysis chart (Figure 6), it is easy to see that both FLOPS and LSTM are relatively accurate in predicting the endpoints of the interval. However, when the time step is the same, the LSTM network's prediction effect on the values within the interval is significantly insufficient, with large fluctuations in the RMSE. The average RMSE of the LSTM network alone is 6.57, while the average RMSE of FLOPS is 2.86. Similarly, the LSTM network requires more prediction steps to achieve interval trend prediction, as shown in Figure 7. Figure 7 shows that when the prediction period is 10 minutes, the prediction accuracy of the FLOPS method is similar to that of LSTM. However, FLOPS only needs one step to predict the interval trend, with a computation time of 0.054 seconds; while LSTM requires 10 steps to complete the interval prediction and takes 1 minute to give a predicted value, with a computation time of 0.56 seconds. The specific computational cost is shown in Figure 8. Therefore, given similar prediction accuracy, the proposed FLOPS has a better computational performance advantage.
4. Comparative analysis with similar studies at home and abroad
At present, the research on parking space prediction mainly focuses on traditional time series prediction methods and neural network models. In the study of Yu et al. [9], the root mean square error of the ARIMA model for predicting available parking spaces was 4.47, while the root mean square error of the FLOPS method proposed in this paper was 2.86; Sharma et al. [13] used wavelet neural network to predict available parking spaces, and the root mean square error of the system was 3.08; and the wavelet neural network model took 13.3s to complete a day's prediction calculation, while the FLOPS method of this paper took 8.9s. Therefore, the method of applying LSTM network to the prediction of available parking spaces proposed in this paper not only improves the accuracy of prediction, but also improves the calculation speed, and has great practical application value. The shortcoming of this paper is that the parking data is not further divided according to different car usage times. For example, the car usage of citizens on weekdays and non-weekdays is very different. The prediction model can be subdivided for the two, which should further improve the prediction of the model.
Accuracy.
5. Summary
This paper proposes a prediction method that can preserve the data change characteristics over a long prediction time period, suitable for high-precision prediction under conditions of large time spans (>30 minutes). This method uses the idea of fuzzy information granularization to obtain a feature dataset, uses an LSTM network to predict the feature dataset, and then combines cubic spline interpolation to reconstruct the continuous change state of parking spaces throughout the entire prediction interval. Simulation results show that this method has higher accuracy than traditional prediction methods in predicting available parking spaces at the same prediction time step; and it has higher computational efficiency while maintaining similar prediction accuracy. In future work, we will consider more dimensional factors, such as the impact of sudden changes in weather and large-scale events on parking, to further improve prediction accuracy.
