A train dispatching model based on fuzzy passenger demand forecasting during holidays

Fei Dou^1,2, Jie Xu², Li Wang^1,2, Limin Jia²

¹State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University,

²School of Traffic and Transportation Beijing Jiaotong University (China)

 

Received: October 2012

Accepted: March 2013

 

Dou, F., Xu, J., Wang, L., & Jia, L. (2013). A train dispatching model based on fuzzy passenger demand forecasting during holidays. Journal of Industrial Engineering and Management, 6(1), 320-335. http://dx.doi.org/10.3926/jiem.699

 

---------------------

Abstract:

Purpose: The train dispatching is a crucial issue in the train operation adjustment when passenger flow outbursts. During holidays, the train dispatching is to meet passenger demand to the greatest extent, and ensure safety, speediness and punctuality of the train operation. In this paper, a fuzzy passenger demand forecasting model is put up, then a train dispatching optimization model is established based on passenger demand so as to evacuate stranded passengers effectively during holidays.

Design/methodology/approach: First, the complex features and regularity of passenger flow during holidays are analyzed, and then a fuzzy passenger demand forecasting model is put forward based on the fuzzy set theory and time series theory. Next, the bi-objective of the train dispatching optimization model is to minimize the total operation cost of the train dispatching and unserved passenger volume during holidays. Finally, the validity of this model is illustrated with a case concerned with the Beijing-Shanghai high-speed railway in China.

Findings: The case study shows that the fuzzy passenger demand forecasting model can predict outcomes more precisely than ARIMA model. Thus train dispatching optimization plan proves that a small number of trains are able to serve unserved passengers reasonably and effectively.

Originality/value: On the basis of the passenger demand predictive values, the train dispatching optimization model is established, which enables train dispatching to meet passenger demand in condition that passenger flow outbursts, so as to maximize passenger demand by offering the optimal operation plan.

Keywords: railway transportation, passenger demand forecasting, train dispatching, fuzzy logical relationships, optimization model

---------------------

1. Introduction

With the constant improvement of China's high-speed railway network and the enhancement of connectivity within the area of the road network, inter-regional passenger demand increases. The train can’t ensure the safety and punctuality of the train operation, also unable to meet the passenger demand. A large number of passengers are stranded at the station or transfer to other modes of transport to travel. Especially in the traditional holiday, the amount of travel passenger reached a peak value in a short period of time because of the sudden increase in passenger traffic and the uneven distribution. Some trains lack of staff and run without passengers, which causes great waste in transport capacity and increases the total costs of consumption invisible. It’s very necessary to develop detailed train dispatching program, distribute and transport passenger planned.

Train dispatching is a multi-variable, multi-constraint, large-scale and multi-objective combination of optimization. In 1971, Amit and Goldfarb applied mathematical programming methods to train scheduling problem. Experts and scholars studied extensively train scheduling problem with mathematical programming theory (Dejax & Crainic, 1987; Beaujon & Turnquist,1991). Scholars did a large number of valuable researches in train deployment method. For example, the concept of all passengers traveler time is proposed (Ghoseiri et al., 2004), which is the index to evaluate passenger satisfaction. He also established dual goal programming model, whose target is to minimize all travelers’ time and energy consumption. Objective optimization model (Higgins et al., 1996; Chen et al.2003), which could minimize the total train delays and operating costs, is established. The mixed integer programming model (Kraay et al., 1991) to minimize train delay and total energy consumption is proposed. The integer programming model (Zhou & Zhong, 2005; Zhang & Jin, 2005) on considering the waiting time in train station and all the train travel time is established. Fuzzy expected value model by fuzzy variables (Yang et al., 2009), which goal is to minimize all passenger travel time and energy consumption, is estimated. It took tabu search algorithm to solve the train scheduling problem. And the objective function is the minimum rate of train delays. (Dong, Wang and Yan, 2005).

Study of train dispatching issues was not able to meet passenger demand, so we must firstly forecast and assess passenger demand. Existing short-term railway passenger demand forecasting contained the relevant model predictions method and time model prediction method. Some researchers established model for passenger demand forecast on considering the transport competition, OD partition, the level of socio-economic development, national income and other factors. The model contained neural network model, Logit model (Peter, Aura & Tommaso, 1996), multiple regression model and the MD model (Butkevicius, Mindaugas, Vladas & Skirmantas, 2004; Fabio, 2006). Time model prediction methods included passenger demand forecasting method based on time series analysis, the gray mode l(Chen, 2008), ARIMA model and BP neural network model (Guo, Qiao, 2008; Wang, 2006).

This paper analyzed the holiday passenger flow characteristics based on passenger data from Beijing South Railway Station to Langfang station during 2011 National Day holidays. Then established the passenger change rate of fuzzy logical relationship based on fuzzy theory and time series theory, and proposed fuzzy passenger demand forecasting model. A bi-objective programming model is established and the goal is to minimize the total operation cost of the train dispatching and unserved passenger volume. In this model, passenger demand is known, the constraints are station capacity restrictions, section capacity restrictions, the required number of trains restrictions and train set configuration restrictions. Thus, an interior-penalty method is used to solve this difficult problem. This paper took the Beijing-Shanghai high-speed railway for example. The results showed that the train dispatching optimization model is reasonable and effective, and better able to meet the actual passenger demand. The structure of this paper is as following Figure 1.

Figure 1. The structure of a train dispatching model based on fuzzy passenger demand forecasting during holidays

2. Analysis of passenger flow features during holidays

Holidays are the main reason for sudden large passenger flow and railway passenger is increased substantially. Passenger flow characteristics associated with time are mainly nonlinear fluctuation and quasi-periodic fluctuation of short-term passenger, as is shown in Figure 2.

Figure 2. Change trend of passenger flow

2.1. Nonlinear fluctuation of passenger flow

Sudden large passenger flow during holidays, which is imbalance, has the characteristics of instant sudden, passenger structural complexity and unidirectional. During holidays, start and end points of passenger are clear, which result in the increase of passenger flow is single-direction in a certain period. The passenger flow during holidays is mainly consist of civil servants, businessman, tourism, students and workers. The passengers’ arrival and leaving time mainly focus on two periods, before and after the holidays’ beginning and ending. The passenger volume will reach the peak in a short time and the peak time is outstanding. Therefore, the railway passenger flow during holidays is impacted by a variety of factors, and passenger flow change rate in short time is nonlinear fluctuation.

2.2. Quasi-periodic fluctuation of passenger flow

The running speed of high-speed train is accelerating gradually, which shorten the distance between cities indirectly. The high-speed railway passenger flow is growing year by year during the holiday, daily morning and evening peak traffic is large and flat peak period passenger flow is gentle. The passenger flow quasi-periodic fluctuations are significant.

 
 3. Fuzzy passenger demand forecast

Variable Description

t: Passenger flow periods, i.e., one hour.

p(t): The passenger flow in period t.

: The passenger flow predictive value in period t.

n: The number of period in historical passenger flow.

v(t): The change rate from p(t) to p(t+1).

p_max: The maximum value of the historical passenger flow.

p_min: The minimum value of the historical passenger flow.

u_i: The rate range of different changes in passenger flow.

u´_i: The intermediate values of passenger flow change rate range u_i.

k_i: The number of the passenger flow change rate belongs to passenger flow change rate range u_i.

M: The last period in all of passenger flow periods.

3.1. Regularity of passenger flow

The passenger flow between the two stations in high-speed passenger railway line is statistical by a certain period of time. The history passenger flow in different periods is p(1), p(2),…p(t‑1),p(t),p(t+1),…p(n-1), p(n). Take into account the passenger flow change rates between adjacent periods, which are denoted by v(1), v(2),…v(t‑1),v(t),v(t+1),…v(n-2), p(n‑1). Then analyze the passenger flow change rate, summarize up the regularity of the changes in passenger flow of the adjacent period.

In order to express passenger flow trend in adjacent period clearly and more accurately, passenger flow change rate is normalized. Define standardized passenger flow change rate is

.                   (1)

·         When p(t+1)-p(t)<0, the passenger flow descends from period t to t+1.

·         When p(t+1)-p(t)=0, the passenger flow doesn’t change from period t to t+1.

·         When p(t+1)-p(t)>0, the passenger flow increasing from period t to t+1.

In order to reflect the regularity of the passenger flow trend clearly and express varying degrees of passenger flow change respectively, we divide passenger flow change rate into eight intervals applying Zadeh's fuzzy set theory(Zadeh, 1999).

Define the universe of discourse U={u₁,u₂,u₃,u₄,u₅,u₆,u₇,u₈}, and partition it into equal length intervals u₁=[-1,-0.75], u₂=[-0.75,-0.5], u₃=[-0.5,-0.25], u₄=[-0.25,0], u₅=[0,0.25], u₆=[0.25,0.5], u₇=[0.5,0.75], u₈=[0.75,1]. Define each fuzzy set A_i based on the re-divided intervals, fuzzy set A_i denotes a linguistic value of the passenger flow represented by a fuzzy set, 1<i<8.

A₁ denotes that passenger flow decrease is too large, A₂ denotes that passenger flow decrease is larger, A₃ denotes that passenger flow decrease is micro-large, A₄ denotes that passenger flow decrease is less, A₅ denotes that passenger flow increase is less, A₆ denotes that passenger flow increase is micro-large, A₇ denotes that passenger flow increase is larger, A₈ denotes that passenger flow decrease is too large.

Determine the membership function of fuzzy subset A_i using assign method, namely:

when,;when , ; when , .

Define fuzzy subset A_i as follows:

, ,

, ,

, ,

, .

 

Establish fuzzy logical relationships based on the fuzzed passenger flow change rates:

A_{j è}A_p, A_pèA_q, …, A_sèA_t

A_{q è}A_p, A_pèA_s, …, A_sèA_r

_…

”A_jèA_p” denotes that ”if the fuzzed passenger flow rate from period t-1 to t is A_j, the fuzzed passenger flow rate from period t to t+1 will be A_p”. For example, information of passenger flow is shown in Table 1.

Table 1. Information of passenger flow

Following the above example, the fuzzy passenger flow change rate for 8:00-9:00 is A₅, and for 9:00-10:00 is A₃. Hence, we can establish a fuzzy logical relationship is A₅èA₃. Similarly, from Table 1, we can get fuzzy logical relationships are A₅èA₃, A₃èA₅, A₅èA₄, A₄èA₈, etc. Therefore, the fuzzy logical relationships of the passenger flow change rate are shown in Table 2.

Table 2. Fuzzy logical relationships

From Table 2, fuzzy passenger flow change rate is A₅ in previous period, in the following period fuzzy passenger flow change rate are A₃, A₄, and A₄, just as A₅èA₃, A₅èA₄ and A₅èA₄.

 

3.2. Fuzzy passenger demand forecasting model

The establishment of fuzzy passenger demand forecasting model is based on fuzzy logical relationships and time series theory, and the steps are as follows:

·         Step1: Start with period l=n+1 to predict passenger flow.

·         Step2: Use Eq.(1) to calculate the passenger flow change rate v(n-1) in period n-1 to n, and fuzzy passenger flow change rate is A_i. We can find the next fuzzy passenger flow change rate A_j according to fuzzy logical relationships. k_i is the number of the passenger flow change rate A_j which belongs to passenger flow change rate range.

·         Step3: Calculate the passenger flow change rate in period l=n+1, which is

.

·         Step4: Calculate predictive value, and add predictive value to the data of passenger flow, repeat Step2 to Step3 with regard to l=l+1 until l=M.

·         Step5: Calculate the root mean squared error (RMSE) between the actual values and predictive values, which is .

 

3.3. Analysis of model effectiveness

 
The 800 passenger flow data are the passenger flow between Beijing and Tianjin in Beijing-Shanghai high-speed railway, and half an hour is an interval between 8:00 and 18:00 from September 21, 2011 to October 30, 2012. 720 passenger flow data of first 36 days is historical passenger flow data, 80 passenger flow data of last 4 days is test data. All the computer programs are written in Matlab 7.1. The predictive values and actual values are shown in Figure 3.

Figure 3. Comparison of predictive value and real value

Furthermore, the results show that the fuzzy passenger demand forecasting model has a better prediction value, compared with ARIMA model. Three statistics are used to compare, they are mean absolute error (MAE), mean absolute percentage error (MAPE) and root mean square error (RSME), as is shown in Table 3.

Table 3 The comparison of prediction model

 4. Train dispatching optimization model

 
The whole procedure of the model including minimize the total operation cost of the train dispatching and unserved passenger volume. If the operation plan doesn’t satisfy the passenger demand, operation plan would be dispatched for passenger flow assignment, in order to attain the passenger demand.

 4.1. Notation

 
Input data

l: The train type.

T: The planned operating period, i.e., one day.

F_l: The variable operating cost for train l running one kilometer.

F^´_l: The variable operating cost for train l empty running one kilometer.

L_ij: The distance between stations i and j.

N_i,j: The required number of train l between stations i and j.

u_l: The seat capacity of train l.

U_ij: The unserved passengers volume between stations i and j.

C^k_ij: The carrying capacity between stations i and j on the railway line k.

D: The fixed overhead cost for one train.

C_t: The carrying capacity of station t for the planned operating period T.

C_k: The carrying capacity of section k for the planned operating period T.

Decision variables

X_i,j,l: The number of train l between stations i and j.

y_i,j,l: The number of the empty running train l between stations i and j.

x^t_i,j,l: The number of train l stops at station t between stations i and j.

y^t_i,j,l: The number of the empty running train l stops at station t between stations i and j.

x^k_i,j,l: The number of train l runs in section k between stations i and j.

y^k_i,j,l: The number of the empty running train l runs in section k between stations i and j.

 

4.2. Objective function

 
Train set configuration is to meet the demand of passenger flow outburst. In this case, the minimum total operation cost of the train dispatching and unserved passenger volume are the objective functions to meet the passenger demand.

·         Minimize the total operation cost, which includes the fixed overhead cost, variable operating cost for running and variable operating cost for the train empty running.

.

·         Minimize the unserved passengers volume for successfully to meet the passenger demand.

.

 

4.3. Constraint conditions

·         The required number of trains restrictions:

.

 

 

 

·         Station capacity restrictions:

.

·         Section capacity restrictions:

.

·         Train set configuration restrictions: if the round-trip trains are no-load, it can’t satisfy the condition of passenger flow outburst between stations i and j.

.

4.4. Model of the train dispatching optimization

 

          

     

The train dispatching optimization model is a nonlinear complementarity constraints program. An interior-penalty method (Dou, 2011; Fletcher et al., 2004; Hu & Ralph, 2004) is used to solve this difficult problem.

5. Case study

In Table 4, the data is the passenger flow between Beijing and Jinan in Beijing-Shanghai high-speed railway, an hour is an interval between 8:00 and 20:00 from September 27, 2011 to October 10, 2012. All the computer programs are written in Matlab 7.1. The passenger flow predictive values are shown as Figure 4.

Table 4. Information of the historical passenger flow data

 

Figure 4. Passenger demand forecasting value

 

The passenger flow from Beijing to Jinan is 4088. Similarly, the passenger demand forecasting values are shown in Table 5.

Table 5. Passenger demand forecasting value

 

Assume that the fixed overhead cost for one train is 10000 yuan. There is only one type train, and this type of train u₁ can accommodate 1200 passengers. In addition, the required number of train l between stations i and j is N₁₂=N₂₁=2, N₁₃=N₃₁=4, N₁₄=N₄₁=3, N₂₃=N₃₂=3, N₂₄=N₄₂=2, N₃₄=N₄₃=3, the carrying capacity of section between station i and station j is shown in Table 6.(unit: train). The carrying capacity of station is shown in Table 7.(unit: train).

Table 6. Section capacity

 

Table 7. Station capacity

 

In the process of train dispatching between stations i and j, the variable operating cost F_l · L_ij for running is shown in Table 8. (unit: yuan).

Table 8. Variable operating cost for running

 

In the process of train dispatching between stations i and j, the variable operating cost F´_l·L_ij for empty running is shown in Table 9. (unit: yuan).

Table 9. Variable operating cost for empty running

 

We can calculate the minimum total cost of the train dispatching is 2.17 million yuan, and there are not round-trip and no-loading trains from the result. The train dispatching scheme achieved maximum utilization. Line plan of BJ station-JN station in high-speed railway can also be got, as is shown in figure 5.

Figure 5. Line plan of BJ station-JN station in high-speed railway

6. Conclusions

The train dispatching optimization model is a large-scale combinatorial optimization problem, there are many factors and the relationship between the factors is complex. Fuzzy set theory, portfolio optimization and train operation adjustment theory are applied in this paper. First, fuzzy passenger demand forecasting model is established to predictive passenger during holidays. The results showed that the fuzzy passenger forecasts predict is more accurate than ARIMA model. Then, train deployment theory in sudden large passenger flow is studied on considering the total operation cost of the train dispatching, unserved passenger volume, the required number of trains, station capacity, section capacity and train set configuration. Finally, train dispatching optimization model is established, the validity of this model is illustrated with a case study.

With the increase in passenger flow during holidays, train dispatching is influenced by more factors and there are more constraints to consider. Further discussion is need for model and more detailed analysis of the railway line is still need in the case.

Acknowledgement

This work has been supported by the National Natural Science Foundation of China (Grant: 61074151), the National Key Technology R&D Program (Grant:  2009BAG12A10), the Research Fund of the State Key Laboratory of Rail Traffic Control and Safety (Grant: RCS2008ZZ003, RCS2009ZT002), and the Research Fund of Beijing Jiaotong University (Grant: 2011YJS035).

References

Beaujon, G.J., & Turnquist, M.A. (1991). A model for fleet sizing and vehicle allocation. Transportation Science, 25, 19-45. http://dx.doi.org/10.1287/trsc.25.1.19

Butkevicius, J., Mindaugas, M., Vladas, I., & Skirmantas, M. (2004). Analysis and forecast of the dynamics of passenger transportation by public land transport. Transport, 19, 3-8.

Chen, J.L. (2008). Railway passenger traffic volume forecasting from Chongqing to Chengdu based on grey theory. China New Technologies and Products, 4, 20-21.

Chen, Y.R., Peng, Q.Y., & Jiang, Y.S. (2003). Research on a model for adjusting train diagram on double track railway with satisfactory optimization. Journal of the China Railway Society, 25(3), 8-12.

Dejax, P.J., & Crainic, T.G. (1987). A review of empty flows and fleet management models in freight transportation. Transportation Science, 21(4), 227-247. http://dx.doi.org/10.1287/trsc.21.4.227

Dong, S.Q., Wang, J.Y., & Yan, H.F. (2005). Tabu search for train operation adjustment on double-track line. China Railway Science, 26(4), 114-119.

Dou, F. (2011). Study on train deployment model and algorithms during holidays. Beijing Jiaotong University.

Fabio, S. (2006). An integrated forecasting and regulation framework for light rail transit systems. Journal of Intelligent Transportation Systems, 7, 59-73.

Fletcher, R., & Leyffer, S. (2004). Solving mathematical program with complementarity constraints as nonlinear programs. Optimization Methods and Software, 19(1), 15-40. http://dx.doi.org/10.1080/10556780410001654241

Ghoseiri, K., Szidarovszky, F., &  Asgharpour, M.J. (2004). A multi-objective train scheduling model and solution. Transportation Research Part B, 38(10), 927-952. http://dx.doi.org/10.1016/j.trb.2004.02.004

Guo, W., & Qiao, Y.Z. (2008). The forecasting research of railway passenger capacity based on neural network optimized by GA. Journal of Shandong University of Technology, 5, 25-27.

Higgins, A., Kozan, E., & Ferreira, L. (1996).Optimal scheduling of trains on a single line track. Transportation Research Part B, 30(2), 147-161. http://dx.doi.org/10.1016/0191-2615(95)00022-4

Hu, X.M., & Ralph, D. (2004). Convergence of a penalty method for mathematical programming with complementarity constraints. Journal of Optimization Theory and Applications, 123(2), 365-390. http://dx.doi.org/10.1007/s10957-004-5154-0

Kraay, D., Harker, P.T., & Chen, B. (1991). Optimal pacing of trains in freight railroads: Model formulation and solution. Operations Research, 39(1), 82-99. http://dx.doi.org/10.1287/opre.39.1.82

Peter, N., Aura, R., & Tommaso, T. (1996). Modelling inter-urban transport flows in italy a comparison between neural network analysis and logit analysis. Transport Research, 6, 323-328.

Wang, F. (2006). Research of short-term passenger transportation volume forecasting methods. Beijing Jiaotong University.

Yang, L.X., Li, K.P., & Gao, Z.Y. (2009). Train timetable problem on a single-line railway with fuzzy passenger demand. IEEE Transactions on Fuzzy Systems, 17(3), 617-629. http://dx.doi.org/10.1109/TFUZZ.2008.924198

Zadeh, L.A. (1999). Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Fuzzy Systems, 100, 9-34. http://dx.doi.org/10.1016/S0165-0114(99)80004-9

Zhang, Y.S., & Jin, W.D. (2005). Model and algorithm for train operation adjustment on single-track railways based on genetic algorithm. Journal of Southwest Jiaotong University, 40(2), 147-152.

Zhou, X.S., & Zhong, M. (2005). Bicriteria train scheduling for high-speed passenger railroad planning applications. European Journal of Operational Research, 167(3), 752-771. http://dx.doi.org/10.1016/j.ejor.2004.07.019