Combination forecast for urban rail transit passenger flow based on fuzzy information granulation and CPSO-LS-SVM

TANG Min-an， ZHANG Kai， LIU Xing

(1. School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China；2. School of Mechanical and Electronical Engineering, Lanzhou University of Technology, Lanzhou 730050, China)

0 Introduction

The passenger flow of urban rail transit is the basis for planning rail transit network and line trend, selecting vehicle type, determining station equipment capacity in the early stage. It is also the basis of organizing traffic and arranging transportation capacity in later period. Therefore, the accurate passenger flow forecast can improve the utilization ratio of urban rail transit, and it has great practical significance for the daily operation of urban rail transit. At present, domestic and foreign scholars have carried out in-depth research on the forecasting model of urban rail passenger flow, which are mainly divided into two categories:

One is the traditional traffic forcasting method, the four stage method is mature in foreign countries, that is trip generation, trip distribution, mode division and traffic assignment. This forecasting method has merits in its macroscopic and systematic aspects, but it is necessary to carry out large-scale urban traffic investigation and obtain a large amount of data to implement[1]. Malaysia scholar Mahendran used the time series forecasting analysis method to forecast the monthly passenger flow of Malaysia Ampang line, which provides the basis for the relevant departments to plan ahead and make decisions[2]. The other is based on neural network or intelligent algorithm. Russian scholar Tatiana analyzed the possibility of using neural network to predict passenger demand, and predicted the passenger demand of Russian airport in the next two or three years by using neural network[3]; Wang Y analyzed the inbound passenger flow data of Beijing metro and used the seasonal time series (SARIMA) model to predict, the results showed that the forecasting model could accurately describe the variation trend of the inbound passenger flow of Beijing Metro[4]; Zhou J Z researched on passenger flow forecast of urban rail transit station by space weighted least squares support vector machine (LS-SVM)[5]; Yao E J considered the impact of the new line on passenger flow of existing line, and established the passenger flow forecasting model of existing station after the new line, the example showed that the model could accurately predict the passenger flow of the existing station when the topological structure of the rail transit network changed[6].

At present, the research of urban rail transit traffic forecast by domestic and foreign scholars are mainly concentrated in a certain period of time or a site traffic forecast, the change range of traffic prediction is lack of relevant research. If the fluctuation range of short-term peak passenger flow can be effectively predicted, the impact of peak passenger flow on urban rail transit operation can be evaluated in advance. It also can forecast the short-term passenger flow trend in the future according to the forecast of the fluctuation of passenger flow. Therefore, some effective measures, such as adjusting train departure interval or controlling passenger flow, can be used for dispatching and decision-making, which have certain practical application value.

In this paper, a combination forecasting method based on fuzzy information granulation (FIG) and LS-SVM is proposed to predict the fluctuation range of urban rail transit passenger flow. In this algorithm, firstly, traffic data is processed with FIG and valid data is extracted; secondly, by using the ergodicity of chaos and the fast convergence of particle swarm, the chaotic particle swarm optimization (CPSO) algorithm is used to optimize the key parameters of LS-SVM to establish a combined forecasting model of passenger flow; finally, the optimized combination model is used to predict the fluctuation range of passenger flow.

1 Fuzzy information granulation

The concept of information granulation was presented by Professor Zadeh L A[7]. Information granule is a collection of some elements, which are not distinguishable and have functional similarity. Information granulation divides a large number of complex information into several blocks according to their own characteristics, each block is an information granule. There are three main models of information granulation: model based on fuzzy set theory[7], model based on rough set theory[8]and model based on quotient space theory[9].

This paper adopts the model based on fuzzy set theory. For the prediction of urban rail transit passenger flow range, it needs to define the scale of the forecast time first, and then it is necessary to extract the effective information from this scale by information granulation. The prediction sequence is divided into two steps by FIG, which are partition window and information fuzzification. The division window is to divide the whole prediction sequence into several subsequences; fuzzy information is to make every window by fuzzy rules and generate fuzzy information granules. The combination of these two steps is the fuzzy information granulation, the core is to create a reasonable fuzzy set for all windows, so that it can replace the original window of the data information.

For a given passenger flow series, considering the single window problem, the whole passenger flow seriesXis regarded as a window to be fuzzed. The task of fuzzification is to establish a fuzzy particlePonX, that is, a fuzzy conceptGthat can describeXreasonably (Gis a fuzzy set withXas a domain). Therefore, the fuzzy particlePis obtained by

PXisG.

(1)

Ais the membership function of fuzzy conceptG. The fuzzy essence is to determine the process of functionA, and the basic form of the fuzzy concept is to be determined in order to determine the specific membership functionA. The commonly used fuzzy particles are: Gauss type, triangle type, ladder type, parabolic type, etc. Triangular fuzzy particles are adopted in this paper, and the membership function is as follows

(2)

wherexis the predictor sequence variable;a,m,bare parameters. It is worth noting thata,m,brespectively correspond to three variablesLOW,R,UPfor single window, which are obtained by window granulation. TheLOWparameter represents the minimum value of the data change in the window; theRparameter represents the average level of the data change in the window; theUPparameter represents the maximum value of the data change in the window[10].

2 LS-SVM model for traffic passenger flow forecast

Support vector machine (SVM) proposed by Vapnik is a machine learning method based on statistical learning theory[11]. SVM adopts the principle of structural risk minimization and has better generalization performance[12]. It can solve the nonlinear, finite sample and other practical problems. LS-SVM is an extension of SVM, which simplifies calculation process effectively, improves the speed of operation and reduces the solving difficulty by changing the inequality constraints in SVM as equality constraints and transforming the solution quadratic programming problem into linear equations problem[13-15].

y(x)=ωTφ(x)+b.

(3)

According to the structural risk minimization principle, the regression problem can be transformed into

(4)

The constraint in Eq.(4) is as follows

yi=ωTφ(xi)+b+ξi,i=1,2,…,n,

(5)

whereωis the weight matrix;bis the offset amount;Cis the penalty parameter;ξiis the training error.

When solving the optimization problem of Eq.(5), the constraint optimization problem is transformed into unconstrained optimization problem by introducing the Lagrange function. The Lagrange function is constructed as

L(ω,b,ξi,λi)=

(6)

whereλiis a Lagrange operator, andλi∈R.

According to the Karush-Kuhn-Tucker (KKT) condition, the following equation can be obtained by taking the partial derivative ofω,b,ξi,λiin Eq.(6) respectively and making them zero.

(7)

The following linear equations can be obtained by eliminatingω,ξiin Eq.(7),

(8)

whereE=[1,…,1]T;λ=[λ1,…,λn]T;y=[y1,…,yn]T;b,λiare obtained by solving the above linear equations by means of the least squares method. Then the linear regression function is

(9)

According to the Mercer condition, the kernel function is used to convert the problem of Eq.(9) into a linear regression problem

Qij=φ(xi)Tφ(xp)=K(xi,xp).

(10)

The selection of kernel function determines the prediction accuracy of LS-SVM model. In this paper, the radial basis function (RBF) function with strong generalization ability is chosen as the kernel function, which is defined as

(11)

whereσis the kernel function width.

The form of LS-SVM model established by Eqs.(9)-(11) is

(12)

3 Forecasting model based on CPSO to improve LS-SVM

3.1 Particle swarm algorithm

Particle swarm optimization (PSO) is a bionic optimization algorithm based on the feeding process of birds. Compared with other intelligent optimization algorithms, PSO algorithm has the following advantages: ① convergence speed is fast, the algorithm can quickly get the search results; ② the required control parameters are few, the algorithm is simple and easy to implement; ③ it has a certain degree of parallelism, PSO operation object is a particle group containing a lot of data. It has been widely used in the field of solving optimization problem[16-18].

In the PSO algorithm, the two most important indicators that represent the state of a particle are the velocity vector of the particleV(t) and the position of the particleX(t), in addition, each particle has a fitness used to measure the quality of the solution. For each particle in the particle population, the individual optimal solutionpbestis recorded, which shows the optimal solution found by the particle. For the current particle swarm, it will correspond to a global optimal solutiongbest, which shows the global optimal solution of the whole particle swarm at this time. When the particle swarm continues the next step optimization iteration, each particle will update itself by tracking the two optimal solutions ofpbestandgbest, the formula is as follows

(13)

wheretrepresents thetgeneration;wis the inertia weight, which takes the random number between [0,1];pbest,trepresents the optimal position found by the particle itself;gbest,trepresents the optimal position currently found for the entire population;c1,c2are the learning factors, which affect the particle group to follow the optimal solution of the speed;r1,r2are the random number between [0,1].

3.2 Chaotic particle swarm optimization

The PSO algorithm also has the same problem as genetic algorithm: it is easy to fall into the local optimal value; the convergence speed is slow in the later stage of evolution; it is difficult to find the global optimal solution. In order to overcome the above problems, this paper integrates chaos optimization algorithm into PSO algorithm. Chaos is a kind of random motion state obtained by determining the equation, which is a common phenomenon in nonlinear system. Its behavior is complex and random, and using the randomness, ergodicity and regularity of chaotic variables, excellent global search function can be achieved[19], which is generated by the chaotic iterative equation. This paper uses Logistic mapping function to generate chaos[20], the formula is as

zn+1=μzn(1-zn),n=0,1,…,∞,

(14)

whereμis the control of the parameters, whenμ=4,z0∈[0,1], the system is in a chaotic state. When an initial valuez0∈[0,1] is given to the chaotic variable, the pseudo-random sequence is generated by the iteration of the initial value. Each iteration is a search, through continuous iteration, the chaotic space traversal search can be obtained. Chaos algorithm can achieve a unique traversal search, which fundamentally solves the PSO algorithm in the local extreme value problem.

CPSO optimization LS-SVM steps are as follows:

Step 1: Randomly initialize the position and velocity of each particle in the population.

Step 2: Save the current individual optimal solution and global optimal solution by the fitness of each particle.

Step 3: By Eq.(13) to update the velocity and position of each particle, calculate the fitness of each particle, the optimal solution of the individual and the global optimal solution.

Step 4: Select the new individual optimal solution and new global optimal solution.

Step 5: For Step 4, the new individual optimal solution and the new global optimal solution are chaotic mapped by Eq,(14), then generate chaotic variable sequences.

Step 6: Evaluate all the particles in the population and update their velocity and position, then select the individual optimal solution and global optimal solution again.

Step 7: Verify that the end condition is met, if the end condition is not satisfied, go to Step 2. Otherwise exit the loop and output the iteration search result.

4 Forecasting model of fluctuation range of traffic passenger flow

The specific steps of the fluctuation range of passenger flow based on the FIG and LS-SVM are as follows:

Step 1: The passenger flow of urban rail transit is extracted as the sample data, determine the window size, fuzzy information granulation on the sample data according to Eq.(2).

Step 2: Normalize theLOW(minimum),R(average) andUP(maximum) of the fuzzy information granularity.

D=(xi-xmin)/(xmax-xmin),

(15)

whereDis the normalized data;xmax,xminare the maximum and minimum values in the data.

Step 3: Set the range of parametersC，σin LS-SVM, initialize the particle swarm according to the parameter range, including the population sizeS=30, the maximum number of iterationsM=300, position vector and velocity vector of the particle, maximum and minimum weight coefficientωmax=0.9,ωmin=0.1, learning factorc1=1.5,c2=1.7.

Step 4: Calculate the fitness of the particle. In order to reduce the forecast error of passenger flow, search for the optimal parameters, the fitness function is defined as

(16)

Step 5: By Eq.(13) to update the particle’s position and velocity, so as to produce a new generation of particle swarm. And comparing the history of the individual and the global optimal position to determine the history of the new individual and global optimal position.

Step 6: Comparing with the final termination conditions, if it is not satisfied, continue the next step; if the conditions are satisfied, then stop the optimization and execute Step 9 directly.

Step 7: Use chaos optimization for historical optimal position of particle swarm.

Step 8: Determine whether the updated optimal solution satisfies the termination condition, if not satisfied, return to Step 5; if satisfied, execute the next step.

Step 9: Establish the forecast model based on the optimal LS-SVM parametersC，σthat has been found, predicte theLOW(minimum),R(average) andUP(maximum) for the next window. Finally, the prediction results are reverse-normalized and get the predicted actual value.

In summary, the flow chart of the combined forecasting model of passenger flow based on FIG-LS-SVM is shown in Fig.1.

Fig.1 Flow chart of combined forecasting model for passenger flow

5 Analysis of combination forecasting model

5.1 Experimental operating environment

Running environment: Window 10 operating system；Intel Core I5-4200H processor; Matlab 2015b programming software; libsvm-3.22 toolbox.

5.2 Data sample preprocessing

In this paper, the daily morning peak passenger flows from Tiyu Xilu station in the annual weekdays in 2014 were selected as the example data, which has the largest passenger flow on the Guangzhou Metro Line 3. The data of 8:00-9:00 are taken for prediction and study. In fact, all data were collected by every 5 min as a statistical point, and recorded them every 5 min, which reflect the passenger flow of the morning peak of 250 weekdays in 2014. There are 3 000 groups of data since the sampling period of the data sample is 5 min. The previous 2 880 groups of data (240 weekdays) are selected as training samples, and the latter 120 groups of data (10 weekdays) are taken as test samples. According to the Eq.(2), the training samples are granulated by the fuzzy information for one hour (12 samples) as a window, and each component after the granulation is shown in Fig.2.

Fig.2 Visualization of fuzzy information granulation

In Fig.2,LOWrepresents the minimum,Rrepresents the average level,UPrepresents the maximum.

Because the prediction processes of three variables such asLOW,RandUPare similar, the prediction model of improved LS-SVM based on CPSO is established by takingLOW(the minimum value of each window) as an example. Firstly, the data normalization ofLOWis processed. The data normalization process converts all data into numbers between [0,1], for canceling the difference in magnitude between the data of each dimension. The normalized value is shown in Fig.3.

Fig.3 Normalization of LOW value

5.3 Analysis and discussion of combined forecasting model

TheLOWvalue is normalized and input into the LS-SVM model for training. The parameters of the LS-SVM model are optimized by using the CPSO algorithm. After the iteration of 300 times, the optimal model parameters are obtained, that isC=270.501 1,σ=1.635 2, and theLOWvalue passenger flow forecasting model is established. The fitting results are shown in Fig.4. It shows that the passenger flow fitting value of CPSO-LSSVM model toLOWvalue is very close to the actual value, and the fluctuation between them is very small, which can better reflect the nonlinear variation of passenger flow. The simulation results show that the CPSO-LS-SVM model has good fitting degree between the predicted value and the actual value when the passenger flow data sample is trained.

Fig.4 Comparison of forecast results of LOW value training sample passenger flow

Fig.5 shows that the maximum relative error of the CPSO-LS-SVM model is less than 3%, which indicates that the fitting accuracy of the model is more than 97% and meets the requirement of fitting accuracy.

Based on the established CPSO-LSSVM model, the early peak traffic of the last 10 weekdays is predicted. The forecasting results of passenger flow test samples are shown in Fig.6. It shows that the output predicted value of CPSO-LS-SVM model is very close to the actual value, and the variation curves of the prediction value and the actual value are extremely similar. The predicted results show that the predicted value of passenger flow is consistent with the actual value, which shows that passenger flow forecasting model based on CPSO-LS-SVM has better generalization ability and strong forecasting ability.

Fig.5 Relative error of LOW value training sample

Fig.6 Comparison of forecast results of LOW value test sample passenger flow

As seen in Fig.7, the maximum relative error of the CPSO-LS-SVM model to test sample prediction is -1.8%, the minimum relative error is -0.115%, the relative error is controlled within 2%, the prediction accuracy of the model is up to 98% or more. It is shown that the CPSO-LS-SVM passenger flow model has higher prediction accuracy ofLOWvalue and has good generalization ability.

By the same method, the CPSO-LS-SVM prediction model was used to obtainR(average) andUP(maximum). Taking one hour (12 sampling points) as a window, the early peak passenger flow for the last 10 weekdays is forecasted. The prediction results are shown in Table 1.

Fig.7 Relative error of LOW value test sample

No．LOWActualvaluePredictedvalueRActualvaluePredictedvalueUPActualvaluePredictedvalue1806791896890956961284884192793396096338348288998911052106048388338848791001100556045998458489499516812804877871940948782981487288392694185825728418289919989887878936926997100410852851883878930932

5.4 Contrast and analysis

In order to further verify the validity of the model proposed in this paper, several commonly used prediction models are selected for comparison and analysis, which are BP neural network and standard LS-SVM. The forecasting results of the prediction models are shown in Table 2. Based on the characteristics of each component, the relative error, the root mean square error (RMSE) and the mean absolute percentage error (MAPE) are used as the evaluation indexes of the three prediction models. The relative error of three models are shown in Table 3, the RMSE and MAPE of the predicted results are shown in Table 4.

From Tables 2-4, it can be seen that the three passenger flow forecasting models can predict the fluctuation range of short-term passenger flow, actual values of the passenger flow are within the range predicted by the three models, however, the ranges and accuracies of the three models vary greatly.

The BP neural network model itself has the ability of adaptive learning, but it is affected by the initial random weights and thresholds and the prediction results are not stable, what’s worse, it is prone to overfitting phenomenon and the prediction accuracy is not high. The standard LS-SVM is more accurate than BP neural network prediction model, but the prediction accuracy of the model is easily affected by its own parameters, and it is easy to fall into the local optimal solution. Compared with the other two methods, the three values (LOW,R,UP) of the CPSO-LS-SVM prediction model are the lowest on RE, RMSE and MAPE, and the predictions are more accurate.

Table 2 Fluctuation forecasting results of other passenger flow models

Table 3 Relative error of three models (%)

Table 4 Error index of three models (%)

6 Conclusion

1) Based on the characteristics of nonlinear and cyclical fluctuation of urban rail transit traffic, and the difficulty in selecting parameters for LS-SVM model, a combined forecasting model of passenger flow based on FIG and CPSO-LS-SVM is proposed in this paper, which can effectively predict the fluctuation range of passenger flow.

2) The proposed combination forecasting model is used in the case test, the results show that the forecasting method has high prediction accuracy and good generalization performance in the prediction of early peak. Compared with the traditional forecasting method, the prediction accuracy of passenger flow is obviously improved, which provides an effective method for the prediction of passenger flow.

3) The proposed combination forecasting model has a better forecasting effect on the fluctuation range of passenger flow. The model can predict the fluctuation range of short-term passenger flow in the future, and provide a new decision-making method for the daily operation of urban rail transit, which plays a guiding role in the operation and management and has certain practical application value.

4) The proposed combination forecasting model considers only the early peak passenger flow on weekdays, however, the sudden large passenger flow caused by the large-scale activities and holidays are different from the normal passenger flow. In the follow-up work, it is necessary to further study and analyze the unexpected large passenger flow under the abnormal condition.

[1] Ma C Q， Chen K M， Wang Y P. Forecasting model of urban rail transit volume. Journal of Chang’an University (Natural Science Edition), 2010, 30(5): 69-74.

[2] Shitan M, Karmokar P K, Lerd N Y. Time series modeling and forecasting of AMPANG LINE passenger ridership in Malasia. Pakistan Journal of Statistics, 2014, 30(3): 385-396.

[3] Blinova T O. Analysis of possibility of using neural network to forecast passenger traffic flow in Russia. Aviation, 2007, 11(1): 28-34.

[4] Wang Y， Han B M， Zhang Q， et al. Forecasting of entering passenger flow volume in Beijing subway based on SARIMA Model. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(6): 205-211.

[5] Zhou J Z，Zhang D Y. Direct ridership forecast model of urban rail transit stations based on spatial weighted LS-SVM. Journal of the China Railway Society, 2014, 36(1): 1-7.

[6] Yao E J， Cheng X， Liu S S， et al. Accessibility-based forecast on passenger flow entering and departing existing urban railway stations. Journal of the China Railway Society, 2016, 38(1): 1-7.

[7] Zadeh L A. Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic. Fuzzy Sets and System, 1997, 90(2): 111-127.

[8] Pawlak Z. Granularity of knowledge, indiscernibility and rough sets. In: Proceedings of IEEE World Congress on Computation Intelligence, Piscataway, 1998: 4-9.

[9] Zhang L, Zhang B. Theory of fuzzy quotient space(methods of fuzzy granular computing). Journal of Software, 2003, 14(4): 770-776.

[10] Wang H，Hu Z J，Zhang M L. A combined forecasting model for range of wind power fluctuation based on fuzzy information granulation and least squares support vector machine. Transactions of China Electrotechnical Society, 2014, 29(12): 218-224.

[11] Vapnik V N. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 1999, 10(5): 988-999.

[12] Rhuma A, Naqvi S M, Chambers J. An improved directed acyclic graph support vector machine. Journal of Measurement Science and Instrumentation, 2011, 2(4): 367-370.

[13] Geng L Y, Zhang T W, Zhao P. Forecast of railway freight volumes based on LS-SVM with grey correlation analysis. Journal of the China Railway Society, 2012, 34(3): 1-6.

[14] Deng H N, Zhu X S, Zhang Q, et al. Prediction of short-term pubic transportation flow based on multiple-kernel least square support vector machine. Journal of Transportation Engineering and Information, 2012, 10(2): 84-88.

[15] Qiao Z L, Zhang L, Zhou J X, et al. Soft sensor modeling method based on improved CPSO-LSSVM and its applications. Chinese Journal of Scientific Instrument, 2014, 35(1): 234-240.

[16] Zhang J, Liu X D. Prediction of concrete strength based on least square support vector machine optimized by chaotic particle swarm optimization. Journal of Jilin University (Engineering and Technology Edition), 2016, 46(4): 1097-1102.

[17] Liao R J, Zheng H B, Grzybowski S, et al. Particle swarm optimization-least squares support vector regression based forecasting model on dissolved gases in oil-filled power transformers. Electric Power Systems Research, 2011, 81(12): 2074-2080.

[18] Zhang X, Zhang Z J, Chen B L. Dynamic compensation for sensors based on particle swarm optimization and realization on LabVIEW. Journal of Measurement Science and Instrumentation, 2014, 5(1): 25-28.

[19] Xiao H Y, Sheng M P, Wu W H. Optimization analysis for a new type of broadband dynamic absorber based on particle swarm optimization. Journal of Vibration and Shock, 2011, 30(1): 98-101.

[20] Zhang J L, Tan Z F. Prediction of the chaotic time series using hybrid method. Systems Engineering-Theory & Practice, 2013, 33(3): 763-769.