Particle swarm optimization for train schedule of Y-type train routing in urban rail transit

WEI Zi-wen

(China Railway First Survey and Design Institute Group Co., Ltd., Xi’an 710043， China)

Abstract： The train schedule usually includes train stop schedule, routing scheme and formation scheme. It is the basis of subway transportation. Combining the practical experience of transport organizations and the principle of the best match between transport capacity and passenger flow demand, taking the minimum value of passenger travel costs and corporation operating costs as the goal, considering the constraints of the maximum rail capacity, the minimum departure frequency and the maximum available electric multiple unit, an optimization model for city subway Y-type operation mode is constructed to determine the operation section of mainline as well as branch line and the train frequency of the Y-type operation mode. The particle swarm optimization (PSO) algorithm based on classification learning is used to solve the model, and the effectiveness of the model and algorithm is verified by a practical case. The results show that the length of branch line in Y-type operation affects the cost of waiting time of passengers significantly.

Key words： urban traffic; train schedule； particle swarm optimization (PSO)； classification learning； Y-type train routing

0 Introduction

The operating mode of Y-type train routing is a special form of the train routing mode in urban rail transit, and its generation is closely related to the characteristics of passenger flow along the line. In general, belt-shaped urban forms, construction of major projects and multi-target strategic layout of cities will form the operating mode of the Y-type train routing[1].

Domestic and foreign scholars have conducted many studies on the train schedule. In terms of traffic organization, domestic and foreign scholars regard the actual passenger flow data or predicted passenger flow data along the line as the basis to analyze the spatial and temporal distribution characteristics of the passenger flow[2-3], and to study the routing scheme, train formation[4]and vehicle selection. Research in China and foreign countries mainly focused on high-speed railway[5], urban rail transit lines[6-7]and subway trains, also on the choice of the train scheme and optimization of the train scheme,etc. In the study of urban rail transit lines, most focused on linear lines, especially super-long line[8-16]using the long-short train routing of urban rail transit.

Based on the above research from both domestic and overseas, it can be concluded that scholars from both domestic and overseas have conducted adequate research on the train schedule of the long-short routing, but research on the Y-type train routing is scarce[1,17]. We will study and reference the research methods of the long-short train routing to study Y-type train routing, and optimize it with the particle swarm optimization (PSO) based on classification learning method.

1 Brief description of Y-type operation

Up to now, the operating and planning the urban rail transit lines which adopt Y-type train routing mode in China consist of one main line and one branch line. Combining with our national conditions, the urban rail transit line composed of a main line and a branch line is selected as the research object in this paper. It can give a better play to the great role of urban rail transit in the transportation system. And it can also achieve a win-win situation between enterprise and passengers by reasonably determining the train schedule.

Y-type train routing mode in the urban rail transit is shown in Fig.1.

Fig.1 Y-type train routing mode diagram

As shown in Fig.1, the train on the main line arrives and departs with the frequency off1within its operating zonesM1,M2andM3; the train on the branch line arrives and departs with the frequency off2within its operating zonesM2andM4. The main line and the trains on the branch line run together in the zoneM2, which has a large passenger flow. The number of the stations on the line is shown in Fig.1. Among them, station “a” is the turn-back station of the branch line, and station “b” is the junction station of the main line and branch line of Y-type mode. Other general stations and intermediate turn-back stations are not shown in Fig.1.

2 Train schedule model

Urban rail transit serves passengers. To highlight its service function and improve its service level, we should pay more attention to reduce passengers’ travel time during peak hours. At the same time, the cost of subway operation should be taken into consideration for meeting the passenger demand as much as possible.

2.1 Basic assumptions of model

We make the following assumptions based on the characteristics of the Y-type train routing mode.

Hypothesis 1: Trains running on the lines of Y-type train routing mode stop at each station;

Hypothesis 2: Considering traveling preferences of passengers on the line, they will choose the direct route firstly, without considering the situation of passengers stranded;

Hypothesis 3: Vehicle rotation is used independently, and the selection of the train is the same;

Hypothesis 4: Running trains are not affected by the line conditions, and the trains in upper and lower directions run at the same speed.

Hypothesis 5: Considering the complexity of train operation organization, the layers of each interval is 2 at most.

Hypothesis 6: During the study period, the departure intervals of the trains on main line and the branch lines remain the same, and the trains in upper and lower directions run in pairs.

2.2 Function definition

For the convenience of description, we make the following function definitions.

2.3 Passengers’ travel cost

Passenger travel cost is mainly characterized by passengers’ waiting time cost, including the en-route waiting time and the time waiting for the train. It can be expressed as

Cost(P)=cwTw+cdTd,

(1)

wherecwandcdare the unit time value of the time waiting for the train and the en-route waiting time, respectively;TwandTdare the time waiting for the train and the en-route waiting time, respectively.

2.3.1 En-route waiting time

The en-route waiting timeTdrefers to the sum of the running time in each section and the stopping time at each station of passenger flow in each origin-destination (OD).

2.3.2 Time waiting for the train

The time waiting for the trainTwis calculated as follows: Passenger waiting time equals that each OD passenger flow multiply averages waiting time of each OD passenger flow. Due to the high density of traffic in urban rail transit and the short running interval, the arrival of passengers can be seen being independent of the arrival time of trains. It is a random normal distribution. The existing studies on this have shown[7]that the average waiting time of passenger flow on the line approaches half of the running interval when the running interval is short (usually less than 10 min).

According to the difference of passenger travel OD, the passenger flow can be divided into the following categories.

The first category is that the travel OD of passengers on the mainline is not in the same zone. The times waiting for trains in the lower and upper directions (Tw11,Tw21) are calculated by

(2)

The second category is that the travel OD of passengers on the mainline is in the same zone (excepting for the collinear section). The times of waiting for trains in the lower and upper directions (Tw12,Tw22) are calculated by

(3)

The third category is waiting time of the collinear section of mainline and branch line. The passengers’ waiting times in the lower and upper directions (Tw13,Tw23) are calculated by

(4)

The fourth category is the waiting time in the lower and upper directions on the branch line, and they are calculated by

(5)

where the first item denotes the waiting time of passengers that travel in different ODs, and the second item denotes the waiting time of passengers that travel in the same ODs.

The fifth category is the waiting time of passengers who need to transfer, and they are calculated by

(6)

Therefore, the lowest cost of passengers is the minimum value of theCost(P) which can be calculated by Eq.(1), andTwandTdare obtained, respectively.

2.4 Corporation’s operating cost

The operating cost of an enterprise can be mainly divided into two parts: fixed costs (referring to vehicle purchase cost) and variable costs (which are mainly determined by the length that trains have travelled). The corporation’s operating cost is calculated by

Cost(O)=VNy+CLz,

(7)

whereVrepresents the purchase expense per vehicle;Nyrepresents the expense per vehicle when travelling;Crepresents the number of vehicles required for operation;Lzrepresents the total length traveled by the trains during the study period.

2.4.1 Vehicle purchase cost

The number of trains required for operation can be obtained by

(8)

whereT1andT2represent the turn-around times of trains on the mainline and branch line, respectively.

2.4.2 Train operation cost

The total number of kilometers travelled by the train can be obtained by

(9)

whereL1andL2represent the distances travelled by the mainline and the branch line, respectively.

2.5 Optimization model and its constraints

Considering the interests of passengers and operating enterprise at the same time, the optimization model can be constructed by using ideal point method. Then the model can be transformed as

Z=min(UZ1,Z2),

(10)

whereZ1andZ2are the function values of two targets under the following constraints: the two targets are the passengers’ travel costZ1and the corporation’s operating costZ2, respectively;UZ1,Z2is the evaluation function which is an ideal point method used. The evaluation function is expressed as

(11)

Analyzing the influence factors of the train scheme of the Y-type train routing, the constraints of the model are given by

f1∈N,f2∈N,

(12)

1≤a≤b≤N≤n,

(13)

(14)

f1≥f0,f2≥f0,

(15)

(16)

Among these constraints, Eqs.(12) and (13) are basic constraints which restrict the value range of variables; Eq.(14) is to meet the trains’ minimum running interval; Eq.(15) is to meet limit of minimum departure frequency; Eq.(16) is a constraint on the number of trains required.

3 Model-solving algorithm

In summary, the model above is a multiple objective optimization model and there is a contradiction each other. If we mainly focus on the interest of passengers, the travel cost of passengers will be the minimum, but departure frequency of the trains and the number of trains required will increase, so that the operation cost of enterprise will increase, which has an adverse effect on the operating enterprises; If we mainly focus on the interest of the operating enterprises, the corporation’s operating cost can reach the minimum, but passengers will wait much longer, and then the transportation service is poor, which does not satisfy the principle of human oriented. Therefore, both of them cannot achieve the minimum cost simultaneously. These two sides contradict each other.

3.1 Principle of algorithm

We use the particle swarm algorithm (PSO)[18]based on classification learning method to solve the model. According to the function value of each particle, this algorithm divides particle swarms into three small groups: the good, the medium and the poor. The particles in each group adopt different learning strategies to update their velocity in order to increase the diversity of particles.

The learning strategies of the three types of particles are as follows:

1) The good particles continue to update along their learning direction as shown in Eq.(17), and do not learn from other particles. Comparing with the standard PSO, only the first two items are retained, and the third item (social learning) is abandoned.

2) The medium particles update their velocity in the way which is the same as the standard PSO, as shown in Eq.(18).

3) The poor particles randomly choose two particles’ historical optimums which are chosen from the good as their two learning objects, as shown in Eq.(19). Comparing with the standard PSO, the first item (that is to say the memory item which includes the last velocity) is abandoned as

(17)

(18)

vid(t+1)=c1r1[rand(pbetter1(t))-xid(t)]+

c2r2[rand(pbetter2(t))-xid(t)],

(19)

In addition, considering that the optimization process of each particle is a nonlinear and complex process, inertia weight uses the logarithmic decrement strategy to replace the linear decrement strategy previously to reflect the particle’s real searching process well. In order to balance the particle’s global algorithm searching and local searching capabilities, two learning factors change dynamically, respectively.

3.2 Optimization process of algorithm

Step 1: Initialization of parameters of the algorithm and line. Under certain constraints,N(the number of particle population is set to be 40) feasible solutions are randomly generated. Each feasible solution containsDdecision variables (the dimension of the pending optimization problem is 3, that is to say, turn-back station “a”, the departure frequency on the mainline“f1”and branch line“f2”.), and the maximum number of iterations is given asM(it is set to be 100);

Step 2: Calculation of the adaptive value of the objective function. According to the adaptation value of the particle, the particle population is divided into three categories: the good, the medium and the poor at a ratio of 1∶2∶1;

Step 3: Updating the particle velocity and particle position, and checking whether the set boundary is exceeded;

Step 4: Updating the global optimal and historical optimum;

Step 5: Checking whether the maximum number of iterations (M) is reached. If it reachesM, it should stop, otherwise, its procedure will return to Step 2.

The global optimum finally obtained by the steps above is the optimal solution we need.

4 Case study

4.1 Parameter settings

Taking an urban rail transit line as an example, there are a total of 31 stations on this rail transit line which has a total length of about 36 km. Numbering the 31 stations on the line according to the principle of numbering the main line firstly and then the branch line. Among them, stations which are numbered with No.1, 4, 7, 11, 16, 21, 24, 28 and 31 have the turn-back capability. The parameters of the line and train operating parameters，such as station dwelling time, interval length and running time in the interval are known during the study period.

The symbols and their definitions of the variables in the model are shown in Table 1, including the minimum departure frequency, maximum number of trains available and operating expenses, etc.

Table 1 Symbols and definitions of variables in the model

4.2 Results and analysis

Based on the given parameters and the OD distribution matrix of passengers during the evening peak of the day, the improved PSO algorithm was used by programming in Matlab to solve the model.

The optimization processes are shown as follows. Firstly, the passenger flow distribution characteristics on the line are investigated and analyzed. Then, according to the characteristics of Y-type train routing mode, the constraint conditions are added when the feasible solution set is generated. Finally, the improved algorithm is used to find the optimal train schedule in the feasible solution set, and then the optimal schedule is evaluated and compared with the current train schedule.

Fig.2 gives the global optimal and average fitness convergence curves.

Fig.2 Global optimal and average fitness convergence curve

As shown it can be seen from Fig.2 that not only the optimal solution can be found rapidly, but also the local optimizations can be avoide better.

Table 2 compares the passengers waiting time, the number of trains required, and the total length of the Y-type train routing mode that the trains travel adopting the optimal solution and current train schedule.

Table 2 Operation indicators results of all train schedules

TrainscheduleTurn-backstationDeparturefrequencyWaiting time (min)Travel length on two lines (km)Train required on two linesOptimalNo.2410:11430 820 431.858, 14.73919, 3CurrentNo.116:1555 465 690.972, 627.44430, 27

It can be concluded from Table 2 that after considering both interests of them, the waiting time of passengers increases dramatically, but the cost of operation enterprise reduces significantly. Table 3 lists the comparison results of different train schedules. The schedules list in Table 3 are compared with current schedule, respectively.

Table 3 Operation indicators comparison of different train schedules

TrainschedulesWaiting timechange(%) Travel costschange(%)Travel length change(%)Trainsrequired change(%)Operating costs change(%)(1,25,15)-26.06-0.5529.4929.8329.83(24,10,10)680.5114.28-66.23-61.41-61.41

Train schedules listed in Table 3 are optimal schedules which take 3 targets as its goal respectively(The schedules taking travel length or trains required minimum as its goal are the same). Compared with the current operating schedule, the waiting time for passengers on the entire line is decreased by more than 1/4 when the departure frequency of the mainline increases to 25 only. Accordingly, the operating cost of the enterprise increases more than the passenger travel cost. Similarly, when the turn-back station is set at the junction station, the waiting time for passengers increases by nearly 6 times, but it is beneficial to reduce the total cost.

4.3 Sensitivity analysis of decision variables

The control variable method is used to analyze the sensitivity. The sensitivity of the turn-back station of the Y-type train routing mode is analyzed firstly, as shown in Fig.3, and sensitivety analysis diagrams of departure frequencies of mainline and branch line are shown in Figs.4 and 5, respectively.

Fig.3 Sensitivity analysis diagram of turn-back station

Fig.4 Sensitivity analysis diagram of departure frequency of mainline

Fig.5 Sensitivity analysis diagram of departure frequency of branch line

5 Conclusion

Verified by cases, the results show that the trains in urban rail transit have a great influence on the interests of both passengers and enterprise. The analysis of the Y-type train routing mode’s characteristics and the sensitivity of 3 decision variables (position of the turn-back station and the departure frequency of 2 lines) in its model leads to the following conclusions.

1) The Y-type train routing mode is analyzed and the model is established;

2) PSO algorithm based on the classified learning is designed to solve the model;

3) Combined with the practical case, the model and algorithm are proved to be feasible and effective, and the solving efficiency of the algorithm used is relatively high. That the length of the section operating together is neither too long nor too short cannot maximize the interests of both parties. The selection of turn-back station has a great impact on the cost, and the turn-back station realizing the largest cost saving is not necessarily the maximum abrupt point of passenger flow in the section;

4) Combining with the real passenger flow distribution situation, it is recommended that the operating enterprise can appropriately shorten the operating section of the branch line so as to effectively reduce the operating cost while passengers’ interest is essentially constant.