# Genetic Algorithm-Based Particle Swarm Optimization Approach to Reschedule High-Speed Railway Timetables: A Case Study in China

Authors: Mingming Wang; Li Wang; Xinyue Xu; Yong Qin; Lingqiao Qin
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

In this study, a mixed integer programming model is proposed to address timetable rescheduling problem under primary delays. The model considers timetable rescheduling strategies such as retiming, reordering, and adjusting stop pattern. A genetic algorithm-based particle swarm optimization algorithm is developed where position vector and genetic evolution operators are reconstructed based on departure and arrival time of each train at stations. Finally, a numerical experiment of Beijing-Shanghai high-speed railway corridor is implemented to test the proposed model and algorithm. The results show that the objective value of proposed method is decreased by 15.6%, 48.8%, and 25.7% compared with the first-come-first-service strategy, the first-schedule-first-service strategy, and the particle swarm optimization, respectively. The gap between the best solution obtained by the proposed method and the optimum solution computed by CPLEX solver is around 19.6%. All delay cases are addressed within acceptable time (within 1.5 min). Moreover, the case study gives insight into the correlation between delay propagation and headway. The primary delays occur in high-density period (scheduled headway closes to the minimum headway), which results in a great delay propagation.


---

## Body

## 1. Introduction

Primary delays inevitably occur during traffic operations [1] and may cause the delay propagation, especially in high-speed railway systems with dense passenger flow. Hence, railway traffic rescheduling has been a critical issue in the field of high-speed operations. Timetable rescheduling is the base of other rescheduling phases, i.e., rolling stock and crew rescheduling [2, 3]. It is essential to reduce primary delays propagation in daily operation. Therefore, the timetable rescheduling problem is chosen as the focus of this paper.Ample research studies have addressed the train timetable rescheduling problem [4–8]. Different models are also investigated to optimize timetable rescheduling. The most common objectives of these studies are train-oriented (i.e., minimize the deviation from the original timetable and the number of trains cancelled) and passenger-oriented [3, 9]. To minimize the total train delays and the number of cancellation trains, a mixed integer programming model was formulated subject to capacity constraints based on an event-activity network [2, 10]. To compute the total delays, a discrete-event dynamic railway scheduling model was developed based on the timed event graph [11, 12]. Specifically, the constraints (e.g., operational constraints) that simulate multiple trains operation on railway networks should be considered during the modeling process of train timetable rescheduling [10, 13–16]. For example, a train can overtake other trains only if at least two tracks are available at stations, and one block section can only be used by one train at the same time. The models for timetable rescheduling have so far mostly focused on tackling the large disruption [2, 10, 17, 18]. However, these models are not suitable for slight disturbances which often occur in daily operation. Therefore, the developed method is effectively able to solve disturbances in daily operation, and the optimum solution offers aids in decision making for daily dispatch.To solve the train rescheduling problem, retiming, reordering, and rerouting are commonly accepted rescheduling strategies [14]. The purpose of retiming is to reschedule the departure and arrival times based on the running time supplements and the dwell buffer time. Goverde (2007) [11] computed delays considering running time supplements and dwell buffer time. The reordering concerns optimizing the sequence of trains at the conflict junctions. Goverde (2010) [12] obtained better results when optimizing the departure orders. Sato, Tamura, & Tomii (2013) [19] also changed the departure orders to obtain the optimum train rescheduling. The rerouting focuses on changing the occupied tracks when some tracks cannot be used. Moreover, if these strategies are combined together and optimized at the conflict conjunctions, a better solution can be obtained [13, 20, 21]. There is also a collection of papers applying multiple strategies to reschedule the train timetable [22–25]. In this paper, multistrategies such as retiming, reordering, changing stop pattern are applied to minimize the total delays and the number of train services.In general, the train scheduling problem is a huge job shop scheduling problem with no-store constraints and is also an NP-complete problem [26]. Thus, it is hard to obtain an optimal solution using mathematical optimization approaches in reasonable computational time, especially for a large-scale problem. For example, a branch and bound algorithm was proposed to solve the train timetable rescheduling problem, but some instances were unsolved within two hours of computation time [23]. The computation time of a Lagrangian relaxation decomposition algorithm was larger than 25 minutes under the circumstance where the planning horizon was 120 minutes and the number of trains was 20 [27]. Louwerse & Huisman (2014) [17] proposed integer programming formulations for timetable rescheduling, where all instances were solved by CPLEX 12.4 within 30 minutes.Fortunately, the heuristic approach provides the possibility of obtaining an approximately optimal solution within an acceptable computation time (approximately 10 minutes) [20, 28, 29]. On one hand, the particle swarm optimization (PSO) algorithm is widely used in solving the NP-complete problem due to its advantages such as high search efficiency and fast convergence speed. On the other hand, the PSO may be trapped in local optima when it is used to solve complex problems. Thus, the hybrid PSO has been proposed to solve the train timetable rescheduling problem [30, 31]. Moreover, genetic algorithm (GA) adopts the mutation operation with certain probability to avoid the local optima and is widely employed to solve real-world problems [32, 33]. The GA-PSO algorithm is also applied to solve nonlinear constrained optimization problems [34, 35]. Hence, a GA-PSO algorithm is developed in this paper to address the above-mentioned drawbacks (i.e., trapped in local optima) of the traditional PSO to solve the train timetable rescheduling problem.In this paper, accommodating retiming, reordering, and adjusting stop patterns for train services are focused on to minimize delays in a real-world corridor and the method of GA-PSO is developed. The main contributions are summarized as follows.(1) A mixed integer programming (MIP) model is formulated for timetable rescheduling problem, where the infrastructure capacity and rescheduling strategies such as retiming, reordering, and changing stop pattern are considered; (2) a novel GA-PSO method is developed, where the position vector and genetic evolution operators are reconstructed based on the departure time and arrival time of each train at every station; (3) the proposed model and algorithm are tested on the busiest Beijing-Shanghai high-speed railway corridor with primary delays. The objective value of the proposed GA-PSO is reduced by 15.6%, 48.8%, and 25.7% compared with the first-come-first-service (FCFS) strategy, the first-schedule-first-service (FSFS) strategy, and the PSO, respectively. Moreover, the case study gives insight into the situation where the primary delays occur in peak hours, which results in a great delay propagation.This paper is structured as follows. Section2 presents the problem definition. The timetable rescheduling model is developed in Section 3. The GA-PSO approach is presented in Section 4. The computational test is analyzed in Section 5. Finally, the conclusions are discussed in Section 6.


## 2. Problem Definition

In this section, the characteristic of timetable rescheduling problem is discussed. The delay propagation phenomenon and rescheduling strategies are introduced. Along with that, assumptions and notations of the proposed timetable rescheduling model are illustrated.


### 2.1. Problem Description

Primary delays may cause a serious influence on the network including delay propagation phenomena because of route conflict. For example, there are four stations, three block sections, and two train services dispatched in the network as shown in Figure1. Train services t1 and t2 are scheduled to stop at station B, where the scheduled arrival time of t1 is earlier than that of t2. However, if train service t1 arrives late at station B, train service t2 will also be delayed because that train services t1 and t2 occupy the same siding of station B in sequence. The primary delays of train service t1 propagate to train service t2.Figure 1
Example of the layout for timetable rescheduling.Next, to reduce the total delays (i.e., the sum of knock-on delays), changing the sequence of train services belongs to one of the timetable rescheduling strategies. For example, an unscheduled stop is appointed at station C, where train servicet2 overtakes train service t1. The corresponding rescheduled timetable is generated, as shown in Figure 2. Note that the scheduled and rescheduled train paths are represented by blue solid lines and red dashed lines, respectively.Figure 2
The rescheduled time-distance diagram based on multistrategies (the retiming, reordering, and stop pattern adjusting).In this study, primary delays in daily operation are considered. The arrival and departure time at stations can be rescheduled, the stop patterns can be adjusted, and the sequence of train services can be reordered to solve the timetable rescheduling problem.


### 2.2. Assumptions

To facilitate problem formulation, five assumptions are made as follows:(1) Train services cannot be cancelled under the influence of disturbance.(2) Characteristics of the rolling stock are neglected, such as their types, scheduling, maintenance appointments, and capacities.(3) Crew planning, such as the duration of duties, breaks, and other rules, is not considered.(4) Stations are regarded as nodes with a given capacity (i.e., the number of siding tracks) in the railway network.(5) Homogeneous traffic is considered in a high-speed railway network.In this paper, slight disturbances with minor impact are considered. To guarantee service quality, original train services cannot be cancelled (assumption (1)). The rolling stock and crew planning can be disrupted (assumption (2)-(3)). To tackle large-scale instances effectively (within acceptable computational time), a macroscopic model where stations are regarded as nodes with a given capacity (assumption (4)) is formulated. Moreover, since the intercity trains are dominant with a 90% share [36] in Chinese high-speed railway corridors, homogeneous traffic is considered (assumption (5)). Thus, these assumptions are reasonable.


### 2.3. Notation

The parameters and decision variables of the optimization process are as shown in Table1.Table 1 Parameters Description NTrain Set of train services, indexed byi,i∈1,2,⋯,n Sstation Set of stations, indexed byj,j∈1,2,⋯,m Sstationnextj Stations next to stationj O i,Di Origin station and destination station of train servicei, respectively Pi Set of stations on which train servicei runs, Pi⊂Sstation a^ji Scheduled arrival time of train servicei at station j d^ji Scheduled departure time of train servicei from station j ω 1, ω2 Penalty per time unit for delays and the number of train services delayed, respectively τj,ri Free-flow time of train servicei at section j,r, r∈Sstationnextj ξji Minimum dwell time of train servicei at station j δ The headway of departure from station for train services θ The headway of arrival at station for train services Δtj,delayi Primary delays of traini at station j Qdelay Maximum delays of each train service Δ t s t a r t r u n,Δtstoprun Additional time caused by starting and stopping at station, respectively Cj Set of available tracks at stationj C s , j, Cm.j Set of available siding and main tracks at stationj, respectively (Cs,j+Cm.j=Cj) Ltrack Minimum interval time of the same track occupied by adjacent train services  Decision variables Description  aji Actual arrival time of train servicei at station j dji Actual departure time of train servicei from station j xj,arri,k Binary variable that represents whether train servicei precedes train service k arrival at station j (1 indicates yes) xj,depi,k Binary variable that represents whether train servicei precedes train service k departure from station j (1 indicates yes) yi,j Binary variable that represents whether train servicei stops at station j (1 indicates yes) zji,κ Binary variable that represents whether train servicei occupies track κ of station j,κ∈Cj (1 indicates yes)


## 2.1. Problem Description

Primary delays may cause a serious influence on the network including delay propagation phenomena because of route conflict. For example, there are four stations, three block sections, and two train services dispatched in the network as shown in Figure1. Train services t1 and t2 are scheduled to stop at station B, where the scheduled arrival time of t1 is earlier than that of t2. However, if train service t1 arrives late at station B, train service t2 will also be delayed because that train services t1 and t2 occupy the same siding of station B in sequence. The primary delays of train service t1 propagate to train service t2.Figure 1
Example of the layout for timetable rescheduling.Next, to reduce the total delays (i.e., the sum of knock-on delays), changing the sequence of train services belongs to one of the timetable rescheduling strategies. For example, an unscheduled stop is appointed at station C, where train servicet2 overtakes train service t1. The corresponding rescheduled timetable is generated, as shown in Figure 2. Note that the scheduled and rescheduled train paths are represented by blue solid lines and red dashed lines, respectively.Figure 2
The rescheduled time-distance diagram based on multistrategies (the retiming, reordering, and stop pattern adjusting).In this study, primary delays in daily operation are considered. The arrival and departure time at stations can be rescheduled, the stop patterns can be adjusted, and the sequence of train services can be reordered to solve the timetable rescheduling problem.


## 2.2. Assumptions

To facilitate problem formulation, five assumptions are made as follows:(1) Train services cannot be cancelled under the influence of disturbance.(2) Characteristics of the rolling stock are neglected, such as their types, scheduling, maintenance appointments, and capacities.(3) Crew planning, such as the duration of duties, breaks, and other rules, is not considered.(4) Stations are regarded as nodes with a given capacity (i.e., the number of siding tracks) in the railway network.(5) Homogeneous traffic is considered in a high-speed railway network.In this paper, slight disturbances with minor impact are considered. To guarantee service quality, original train services cannot be cancelled (assumption (1)). The rolling stock and crew planning can be disrupted (assumption (2)-(3)). To tackle large-scale instances effectively (within acceptable computational time), a macroscopic model where stations are regarded as nodes with a given capacity (assumption (4)) is formulated. Moreover, since the intercity trains are dominant with a 90% share [36] in Chinese high-speed railway corridors, homogeneous traffic is considered (assumption (5)). Thus, these assumptions are reasonable.


## 2.3. Notation

The parameters and decision variables of the optimization process are as shown in Table1.Table 1 Parameters Description NTrain Set of train services, indexed byi,i∈1,2,⋯,n Sstation Set of stations, indexed byj,j∈1,2,⋯,m Sstationnextj Stations next to stationj O i,Di Origin station and destination station of train servicei, respectively Pi Set of stations on which train servicei runs, Pi⊂Sstation a^ji Scheduled arrival time of train servicei at station j d^ji Scheduled departure time of train servicei from station j ω 1, ω2 Penalty per time unit for delays and the number of train services delayed, respectively τj,ri Free-flow time of train servicei at section j,r, r∈Sstationnextj ξji Minimum dwell time of train servicei at station j δ The headway of departure from station for train services θ The headway of arrival at station for train services Δtj,delayi Primary delays of traini at station j Qdelay Maximum delays of each train service Δ t s t a r t r u n,Δtstoprun Additional time caused by starting and stopping at station, respectively Cj Set of available tracks at stationj C s , j, Cm.j Set of available siding and main tracks at stationj, respectively (Cs,j+Cm.j=Cj) Ltrack Minimum interval time of the same track occupied by adjacent train services  Decision variables Description  aji Actual arrival time of train servicei at station j dji Actual departure time of train servicei from station j xj,arri,k Binary variable that represents whether train servicei precedes train service k arrival at station j (1 indicates yes) xj,depi,k Binary variable that represents whether train servicei precedes train service k departure from station j (1 indicates yes) yi,j Binary variable that represents whether train servicei stops at station j (1 indicates yes) zji,κ Binary variable that represents whether train servicei occupies track κ of station j,κ∈Cj (1 indicates yes)


## 3. Train Timetable Rescheduling Model

The objectives of the proposed model are to minimize both the total delays of all involved train services and the number of train services delayed, which can be calculated as follows:(1)
Minimize the total delays of all train services:(1)Z1=min⁡∑i∈NTrain∑j∈Piaji-a^ji(2)
Minimize the number of trains whose delays exceed the thresholdQdelay:(2)Z2=min⁡∑i∈NTrain,Di∈SstationσaDii,a^Diiwhere(3)σaDii,a^Dii=0aDii≤a^Dii+Qdelay1otherwise.Two objectives are normalized by setting their penalty weights according to [37]. Therefore, the objective function of the rescheduling model is given as follows:(4)f=min⁡ω1·∑i∈NTrain∑j∈Piaji-a^ji+ω2·∑i∈NTrain,Di∈SstationσaDii,a^Dii


### 3.1. Departure, Running, Dwell, and Delay Time Constraints

(5) d j i ≥ d ^ j i + Δ t j , d e l a y i  ∀ i ∈ N T r a i n ,   j ∈ P i ∖ D i (6) a r i - d j i ≥ τ j , r i + y i , j · Δ t s t a r t r u n + y i , r · Δ t s t o p r u n  ∀ i ∈ N T r a i n ,   j , r ∈ P i ,   r = S s t a t i o n n e x t j (7) d j i - a j i ≥ y i , j · ξ j i  ∀ i ∈ N T r a i n ,   j ∈ P i ∖ O i , D iThe actual departure time of train service i at station j cannot be earlier than the corresponding scheduled time d^ji plus the primary delay time Δtj,delayi, which is considered by constraint (5). In constraint (6), the running time of the section j,r must be larger than the one that is equal to the free-flow running time plus the additional time Δtstartrun and Δtstoprun. Constraint (7) makes sure that the dwell time of train service i at station j satisfies the minimum interval to ensure the necessary time for passengers to alight and board.


### 3.2. Headway Constraints

(8) a j i - a j k ≥ θ - 1 - x j , a r r k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O k (9) a j k - a j i ≥ θ - x j , a r r k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O k (10) d j i - d j k ≥ δ - 1 - x j , d e p k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O k (11) d j k - d j i ≥ δ - x j , d e p k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O kConstraints (8) and (9) describe the sequence between train services i and k arrival at station j. If xj,arrk,i is equal to 1, then constraint (8) is transformed into aji-ajk≥θ and constraint (9) is nonactive with the expression ajk-aji≥θ-M. Constraints (10) and (11) present the sequence between train services i and k departure from station j. Moreover, constraints (8)-(11) implement the sequence adjustment for train services when decision variables xj,arrk,i and xj,depk,i equal different values (i.e., xj,arrk,i=1, xj,depk,i=0 or xj,arrk,i=0, xj,depk,i=1).


### 3.3. Capacity Constraints

(12) a j i - d j k ≥ L t r a c k - 2 - z j i , κ - z j k , κ · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o n ,   κ ∈ C j (13) ∑ κ ∈ C j z j i , κ = 1  ∀ i ∈ N T r a i n ,   j ∈ S s t a t i o n (14) y i , j = ∑ p ∈ C s , j z j i , p  ∀ i ∈ N T r a i n ,   j ∈ S s t a t i o n (15) y k , j ≥ x j , a r r k , i - x j , d e p k , i  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o n (16) y i , j ≥ x j , d e p k , i - x j , a r r k , i  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o n (17) x S s t a t i o n n e x t j , a r r i , k = x j , d e p i , k  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o nConstraints (12) and (13) guarantee the minimum interval when train services i and k occupy the same platform track p and ensure a platform assignment for each train service arriving at station j. Constraint (14) makes sure that siding tracks are used when train service i stops at station j, and main tracks are used when train service i is through station j. Figure 3 visualizes constraints (15) and (16) which ensure the preceding train service must be stopped when the adjacent train service overtakes it at a station. Constraints (17) ensures that the occupied order of adjacent trains is not changed in block section.(18)aji,dri∈Ni∈NTrain,j∈Sstation∖Oi,r∈Sstation∖Di(19)xj,arrk,i,xr,depk,i,∈0,1i,k∈NTrain,i≠k,j∈Sstation∖Oi,r∈Sstation∖Di(20)yi,j∈0,1,zji,κ∈0,1i∈NTrain,j∈Sstation,k∈CjConstraints (18)-(20) indicate that decision variables are formulated as nonnegative continuous or binary variables. M is a sufficiently large positive number. Note that the whole station is regarded as a point with a certain capacity at the macrolevel, and the large-scale instance can be solved with fewer decision variables.Figure 3
The constraints for overtaking between train services at the station. (a) The “stop-pass” pattern. (b) The “stop-stop” pattern.
(a) (b)


## 3.1. Departure, Running, Dwell, and Delay Time Constraints

(5) d j i ≥ d ^ j i + Δ t j , d e l a y i  ∀ i ∈ N T r a i n ,   j ∈ P i ∖ D i (6) a r i - d j i ≥ τ j , r i + y i , j · Δ t s t a r t r u n + y i , r · Δ t s t o p r u n  ∀ i ∈ N T r a i n ,   j , r ∈ P i ,   r = S s t a t i o n n e x t j (7) d j i - a j i ≥ y i , j · ξ j i  ∀ i ∈ N T r a i n ,   j ∈ P i ∖ O i , D iThe actual departure time of train service i at station j cannot be earlier than the corresponding scheduled time d^ji plus the primary delay time Δtj,delayi, which is considered by constraint (5). In constraint (6), the running time of the section j,r must be larger than the one that is equal to the free-flow running time plus the additional time Δtstartrun and Δtstoprun. Constraint (7) makes sure that the dwell time of train service i at station j satisfies the minimum interval to ensure the necessary time for passengers to alight and board.


## 3.2. Headway Constraints

(8) a j i - a j k ≥ θ - 1 - x j , a r r k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O k (9) a j k - a j i ≥ θ - x j , a r r k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O k (10) d j i - d j k ≥ δ - 1 - x j , d e p k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O k (11) d j k - d j i ≥ δ - x j , d e p k , i · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ P i ∩ P k ∖ O i , O kConstraints (8) and (9) describe the sequence between train services i and k arrival at station j. If xj,arrk,i is equal to 1, then constraint (8) is transformed into aji-ajk≥θ and constraint (9) is nonactive with the expression ajk-aji≥θ-M. Constraints (10) and (11) present the sequence between train services i and k departure from station j. Moreover, constraints (8)-(11) implement the sequence adjustment for train services when decision variables xj,arrk,i and xj,depk,i equal different values (i.e., xj,arrk,i=1, xj,depk,i=0 or xj,arrk,i=0, xj,depk,i=1).


## 3.3. Capacity Constraints

(12) a j i - d j k ≥ L t r a c k - 2 - z j i , κ - z j k , κ · M  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o n ,   κ ∈ C j (13) ∑ κ ∈ C j z j i , κ = 1  ∀ i ∈ N T r a i n ,   j ∈ S s t a t i o n (14) y i , j = ∑ p ∈ C s , j z j i , p  ∀ i ∈ N T r a i n ,   j ∈ S s t a t i o n (15) y k , j ≥ x j , a r r k , i - x j , d e p k , i  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o n (16) y i , j ≥ x j , d e p k , i - x j , a r r k , i  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o n (17) x S s t a t i o n n e x t j , a r r i , k = x j , d e p i , k  i , k ∈ N T r a i n ,   i ≠ k ,   j ∈ S s t a t i o nConstraints (12) and (13) guarantee the minimum interval when train services i and k occupy the same platform track p and ensure a platform assignment for each train service arriving at station j. Constraint (14) makes sure that siding tracks are used when train service i stops at station j, and main tracks are used when train service i is through station j. Figure 3 visualizes constraints (15) and (16) which ensure the preceding train service must be stopped when the adjacent train service overtakes it at a station. Constraints (17) ensures that the occupied order of adjacent trains is not changed in block section.(18)aji,dri∈Ni∈NTrain,j∈Sstation∖Oi,r∈Sstation∖Di(19)xj,arrk,i,xr,depk,i,∈0,1i,k∈NTrain,i≠k,j∈Sstation∖Oi,r∈Sstation∖Di(20)yi,j∈0,1,zji,κ∈0,1i∈NTrain,j∈Sstation,k∈CjConstraints (18)-(20) indicate that decision variables are formulated as nonnegative continuous or binary variables. M is a sufficiently large positive number. Note that the whole station is regarded as a point with a certain capacity at the macrolevel, and the large-scale instance can be solved with fewer decision variables.Figure 3
The constraints for overtaking between train services at the station. (a) The “stop-pass” pattern. (b) The “stop-stop” pattern.
(a) (b)


## 4. Genetic Algorithm-Based Particle Swarm Optimization

The high-speed railway timetable rescheduling problem is quite complex because of a variety of hard constraints (such as headway, capacity, and running time constraints) mentioned in Section3. It has been proved that the timetable rescheduling problem belongs to the NP-complete problem [26]. Thus, artificial intelligence approaches are commonly used to solve this problem, such as GA, PSO, and simulated annealing. In this section, the developed GA-PSO are applied to solve this problem. The key phases of the developed GA-PSO (such as the definition of the position and velocity vectors, feasible solution, fitness function, and updating position and velocity vectors) are presented in Sections 4.1–4.4, and the framework of the developed algorithm is illustrated in Section 4.5.


### 4.1. Definition of Position and Velocity Vectors

Departure time and arrival time of each train from each section are chosen as positions for any particles (that is genes for chromosomes), which represents a feasible solution of timetable rescheduling problem in the GA-PSO. Each vectord11,a11,⋯,d1n,a1n;⋯;dm-11,am-11,⋯,dm-1n,am-1n forms a position vector of a particle, where n is the number of trains and m is the number of stations in corridors. For example, according to Figure 1, where the layout contains four stations and two trains, a sample position vector of a particle, which is first divided into m-1 (m equals four) parts for the departure time and arrival time of two trains, is shown in Figure 4. Each section is further divided into 2·n (n equals two). The value represents the departure time or arrival time which is transformed into the length of time from zero o’clock. All values for departure time and arrival time in cells of a particle are rounded to full seconds.Figure 4
A particle for the sample corridor.The velocity vector has the same dimensions as the position vector of a particle. The velocity vector is randomly generated in the range of integers which represents the change of departure and arrival time of each train from each block section.


### 4.2. Feasible Solution

According to the schedule timetable and delay scenarios, the departure and arrival time of trains at each section are generated under constraints (5)-(20). To obtain good feasible solutions, the following approaches are considered.(1) The sequence of adjacent trains occupying the same block section is determined by the FSFS strategy that trains are arranged by the scheduled order [38].(2) The strategy of the same block section occupied by trains is determined by actual arrival or departure time of train services according to the FCFS [23].(3) The actual departure and arrival time of trains from stations are obtained within the neighborhood of scheduled timetable (see (21)-(22)).(21)aji=xx∈U+a^ji+Δtj,delayi,ΘifΔtj,delayidelays  occuryy∈U+a^ji,Θotherwise(22)dji=xx∈U+d^ji+Δtj,delayi,ΘifΔtj,delayidelays  occuryy∈U+d^ji,Θotherwisewhere U+a^ji,Θ is the right neighborhood of a^ji.


### 4.3. Fitness Function

The fitness value of each particle is calculated according to the objective functionf() (see (4)). Next, the individual optimum value and global optimum value are updated using (23)plr=fΧlrfΧlr≤plr-1plr-1otherwise(24)pgr=pgr-1pgr-1≤minl=1,2,⋯,Nplrminl=1,2,⋯,Nplrotherwisewhere Χlr is the lth particle position vector in the rth iteration; plr is the lth individual optimum value in the rth iteration; pgr is the global optimum value in the rth iteration; N is the population number of particles.


### 4.4. Update Position and Velocity Vectors

To update position vectors, the GA operators and the PSO process are applied. First, crossover and mutation are two common operators used in the GA. Specifically, crossover operation is that a value of crossover pointρc is replaced by the value of the same point in another particle with the probability of crossover Pc, shown in Figure 5. Mutation operation is to change the value of mutation point ρm with the probability of mutation Pm. Note that the new particles produced may be infeasible solutions; thus, the infeasible particles must be modified until feasible solutions are generated according to the methods specified in Section 4.2.Figure 5
Crossover operation.Next, during the process of PSO, the velocity and position vectors are updated by the following:(25)Vlr+1=w·Vlr+c1·γ1·plr-Xlr+c2·γ2·pgr-Xlr(26)Xlr+1=Xlr+Vlrwhere Vlr is the lth particle velocity vector in the rth iteration; w is the coefficient of inertia; c1 and c2 are learning coefficients; γ1 and γ2 are randomly generated between zero and one.


### 4.5. Algorithm Framework

The overall algorithm is presented as follows.Step 1 (initialization).
Parameters, such asw, c1, c2,Pc,Pm, maximal iteration numbernum, and precisionerror are initialized. Generate the particle setN with positions and velocities using the methods specified in Section 4.2 to ensure the constraints (5)-(20).Step 2.
Calculate the fitness function for each particle according to (4) and update plr and pgr according to (23)-(24), specified in Section 4.3.Step 3.
Update the velocities and positions of the particles specified in Section4.4.Step 4.
Loop to Step2 untilnumorerroris satisfied and then output the best solution. Note that the criteria to terminate the algorithm are that the iteration reaches the maximal numbernum or the precisionerror is satisfied, then the optimal solution is obtained.


## 4.1. Definition of Position and Velocity Vectors

Departure time and arrival time of each train from each section are chosen as positions for any particles (that is genes for chromosomes), which represents a feasible solution of timetable rescheduling problem in the GA-PSO. Each vectord11,a11,⋯,d1n,a1n;⋯;dm-11,am-11,⋯,dm-1n,am-1n forms a position vector of a particle, where n is the number of trains and m is the number of stations in corridors. For example, according to Figure 1, where the layout contains four stations and two trains, a sample position vector of a particle, which is first divided into m-1 (m equals four) parts for the departure time and arrival time of two trains, is shown in Figure 4. Each section is further divided into 2·n (n equals two). The value represents the departure time or arrival time which is transformed into the length of time from zero o’clock. All values for departure time and arrival time in cells of a particle are rounded to full seconds.Figure 4
A particle for the sample corridor.The velocity vector has the same dimensions as the position vector of a particle. The velocity vector is randomly generated in the range of integers which represents the change of departure and arrival time of each train from each block section.


## 4.2. Feasible Solution

According to the schedule timetable and delay scenarios, the departure and arrival time of trains at each section are generated under constraints (5)-(20). To obtain good feasible solutions, the following approaches are considered.(1) The sequence of adjacent trains occupying the same block section is determined by the FSFS strategy that trains are arranged by the scheduled order [38].(2) The strategy of the same block section occupied by trains is determined by actual arrival or departure time of train services according to the FCFS [23].(3) The actual departure and arrival time of trains from stations are obtained within the neighborhood of scheduled timetable (see (21)-(22)).(21)aji=xx∈U+a^ji+Δtj,delayi,ΘifΔtj,delayidelays  occuryy∈U+a^ji,Θotherwise(22)dji=xx∈U+d^ji+Δtj,delayi,ΘifΔtj,delayidelays  occuryy∈U+d^ji,Θotherwisewhere U+a^ji,Θ is the right neighborhood of a^ji.


## 4.3. Fitness Function

The fitness value of each particle is calculated according to the objective functionf() (see (4)). Next, the individual optimum value and global optimum value are updated using (23)plr=fΧlrfΧlr≤plr-1plr-1otherwise(24)pgr=pgr-1pgr-1≤minl=1,2,⋯,Nplrminl=1,2,⋯,Nplrotherwisewhere Χlr is the lth particle position vector in the rth iteration; plr is the lth individual optimum value in the rth iteration; pgr is the global optimum value in the rth iteration; N is the population number of particles.


## 4.4. Update Position and Velocity Vectors

To update position vectors, the GA operators and the PSO process are applied. First, crossover and mutation are two common operators used in the GA. Specifically, crossover operation is that a value of crossover pointρc is replaced by the value of the same point in another particle with the probability of crossover Pc, shown in Figure 5. Mutation operation is to change the value of mutation point ρm with the probability of mutation Pm. Note that the new particles produced may be infeasible solutions; thus, the infeasible particles must be modified until feasible solutions are generated according to the methods specified in Section 4.2.Figure 5
Crossover operation.Next, during the process of PSO, the velocity and position vectors are updated by the following:(25)Vlr+1=w·Vlr+c1·γ1·plr-Xlr+c2·γ2·pgr-Xlr(26)Xlr+1=Xlr+Vlrwhere Vlr is the lth particle velocity vector in the rth iteration; w is the coefficient of inertia; c1 and c2 are learning coefficients; γ1 and γ2 are randomly generated between zero and one.


## 4.5. Algorithm Framework

The overall algorithm is presented as follows.Step 1 (initialization).
Parameters, such asw, c1, c2,Pc,Pm, maximal iteration numbernum, and precisionerror are initialized. Generate the particle setN with positions and velocities using the methods specified in Section 4.2 to ensure the constraints (5)-(20).Step 2.
Calculate the fitness function for each particle according to (4) and update plr and pgr according to (23)-(24), specified in Section 4.3.Step 3.
Update the velocities and positions of the particles specified in Section4.4.Step 4.
Loop to Step2 untilnumorerroris satisfied and then output the best solution. Note that the criteria to terminate the algorithm are that the iteration reaches the maximal numbernum or the precisionerror is satisfied, then the optimal solution is obtained.


## 5. Case Study

Because of the high-density train services, primary delays can seriously affect the operating efficiency of the Beijing-Shanghai high-speed corridor in daily operation. Thus, computational experiments of the Beijing-Shanghai high-speed railway corridor are tested to demonstrate the performance of the proposed model and algorithm. The experiments are all solved by the proposed GA-PSO and PSO algorithms using java on a PC with an Intel Core i5 with 2.60 GHz and 8 GB RAM, and comparison with different reschedule strategies is analyzed.


### 5.1. Case Description: A Realistic Chinese High-Speed Railway Corridor

The proposed methodology is applied to the busiest high-speed railway corridor from Beijing to Shanghai (more than 95 train services per day). The Beijing-Shanghai high-speed railway corridor, represented by the orange line in Figure6, consists of 23 railway stations and 22 open track sections. Each station with its name and short name, distance from BJN, the capacities of stations, and travel times of those sections are shown in Table 2. The additional times caused by the start-up and stop at the station are 2 minutes and 1 minutes, respectively, and the minimum headway is 5 minutes during peak hours.Table 2
Parameters related to infrastructures.
Station name Short name Distance from BJN (km) Number of tracks (station capacity) Travel times from the previous station (minute) BeijingNan BJN 0 12 0 Langfang LF 59 2 22 TianjinNan TJN 131 3 16 CangzhouXi CZX 219 3 22 DezhouDong DZD 327 4 26 JinanXi JNX 419 8 23 Taian TA 462 4 15 Qufu QF 533 4 18 TengzhouDong TZD 589 2 14 ZaoZhuang ZZ 625 4 9 XuzhouDong XZD 688 7 16 Suzhou Dong SZD 767 3 17 Bengbu Nan BBN 844 7 22 Dingyuan DY 897 2 14 Chuzhou CZ 959 2 16 NanjingNan NJN 1018 5 19 ZhenjiangNan ZJN 1087 3 20 DanyangBei DYB 1112 2 7 ChangzhouBei CZB 1144 3 8 WuxiDong WXD 1201 3 14 SuzhouBei SZB 1227 3 7 KunshanNan KSN 1259 9 8 Hongqiao HQ 1302 11 17Figure 6
The overview of the Chinese high-speed railway network.Next, four delay cases are designed, reported in Table3. The delay cases are identified by the train name, station name, delay type, and delay time. In these experiments, the scheduled timetable contains 40 trains in down direction within the time horizon. Arrival delays, departure delays, and unscheduled stop caused by disturbances (e.g., unscheduled stop, prolonged process, and route conflict) are considered. Moreover, we assume that the disturbance length is very short (i.e., within an hour).Table 3
Delay cases description.
Index of case Train name Station name Type Delay time (min) Case 1 G109 BBN Unscheduled stop 20 Case 2 G123 DZD Departure delay 10 Case 3 G139 NJN Departure delay 10 Case 4 G155 JNX Departure delay 15


### 5.2. Parameters Setting

To determine the GA-PSO algorithm related parameters (i.e.,w,c1,c2,Pc, and Pm), a full factorial design is applied in this section. The relative deviation index (RDI) [30] is proposed to compare the performance of different parameter combinations as follows:(27)RDIi=fiopt-fminfmax-fmin·100where fiopt is the value of the optimum objective function with the ith parameter combination; fmax and fmin are the worst and best objective function values among the parameter combinations, respectively. Punctuality (i.e., the rate of train services whose delays are less than threshold) is an important measure of service quality during daily operation, and it also influences rolling-stock and crew circulation plans. The objective, the number of trains whose delays exceed the threshold, should gain more attention in the proposed model. Thus, penalty weights of total train service delays and the number of trains whose delays exceed the threshold Qdelay (i.e., 4 min) are one and 10000, respectively [37]. According to Jamili et al. (2012) [30],pop is 20 and the termination criterion is that the maximal iterationsnum is 1000 or the precisionerror is 0.05.Next, we record the best solution under the different parameter combinations ofw,c1,Pc, and Pm. Note that w,c1, and pc are in the range of [0.35,0.65], and pm is in the range of [0.05,0.2]. The main effects of the parameter combinations are investigated and depicted in Table 4. The results show that the combination of w=0.65, c1=0.5, pc=0.6, and pm=0.15 is better than other parameter combinations. Furthermore, the parameter c1 is set as 0.5, and c2 is randomly chosen at each time step in the range 0,1.Table 4
The interaction of different parameter combinations.
w , c 1 , P c , P m 0.65,0.5,0.6,0.15 0.4,0.5,0.6,0.15 0.65,0.5,0.6,0.2 0.65,0.6,0.6,0.15 Best objective value 52460 73000 62940 74740 RDI 0 63% 32% 68%


### 5.3. Result Analysis

In this section, the rescheduled timetable and results are analyzed. First, the best rescheduled timetable is obtained by the proposed GA-PSO as shown in Figure7, where grey and blue lines represent the scheduled train service paths and rescheduled train service paths, respectively. To reduce the number of delayed trains and total delay time, the sequence of adjacent trains occupying the same block section is changed in the best solution. For instance, the order of which the trains named G109 and G111 enter the BBN-DY section is changed, which makes sure that G111 is operated with scheduled time (see left red circle in Figure 7) and the number of delayed trains is reduced. Furthermore, the increase of dwell time can avoid route conflict. For example, since the dwell time of the train named G147 at ZJN station is increased (i.e., 180 sec), the conflict among trains disappear (see right red circle in Figure 7).Figure 7
The best rescheduled time-distance diagram based on the proposed GA-PSO.Next, the results, such as primary delays, knock-on delays, knock-on delayed trains, objective function value, and computational time, are reported in Table5. All delay cases 1, 2, 3, and 4 can be solved in less than one minute. From the delay case 1 to delay case 4, the minimum headway of disrupted adjacent trains is ten, five, eight, and seven minutes, respectively. The results show that large value of the objective function corresponds to great impact illustrated by knock-on delays and the number of knock-on delayed trains on scheduled timetable. For example, the impact of delay case 3 (with objective value 180) is small, and the impact of delay case 1 and delay case 2 (with objective value 20600 and 21080, respectively) is stronger. The distribution of delays of each train is shown in Figure 8. According to the obtained results, two general conclusions are revealed.Table 5
Results of delay cases.
Index of case Delays Knock-on delayed trains Best objective value Computational time (sec) Primary delays (sec) Knock-on delays (sec) Case 1 1200 600 G113, G1 20600 42 Case 2 600 1080 G411, G127 21080 56 Case 3 600 180 --- 180 31 Case 4 900 600 G149 10600 40Figure 8
The delays distribution of each train.(1) Greater primary delays will result in stronger impact on the scheduled timetable when approximately the same minimum headway is considered.(2) High-density traffic flow has a great delay propagation on the railway network when same primary delays occur (the same point also refers to [39]).


### 5.4. Comparison of Different Approaches

In this section, the performance of the proposed method is tested compared with other heuristic algorithms (i.e., the FSFS strategy, FCFS strategy, and the PSO). Moreover, the gap between the best solution obtained by the proposed method and the optimal solution computed by CPLEX solver is analyzed.The FSFS and FCFS rescheduling strategies (mentioned in Section4.2) and the PSO algorithm are applied to investigate delay cases, respectively. The objective obtained by FSFS, FCFS rescheduling strategies, and CPLEX solver is as the benchmark solution. All delay cases are considered together in this section and the results obtained by different approaches are shown in Figure 9. Note that the initial solution (with value 105880) of the GA-PSO and the PSO algorithm is set considering FSFS strategy. The objective of FSFS strategy is the upper bound value, and the optimal objective computed by CPLEX solver is the lower bound value.Figure 9
Comparison of different approaches.According to the results, the objective value (52460) obtained by the proposed GA-PSO algorithm outperforms that of the FCFS strategy. Specifically, the objective value of the GA-PSO is reduced by 15.6%, 48.8%, and 25.7% compared with the FCFS strategy, the FSFS strategy, and the PSO, respectively, shown in Figure9. The lower bound (with optimal solution 42194) refers to the gap between the CPLEX solver and the proposed method, which is around 19.6% in this case. However, the delay case is solved by the proposed GA-PSO algorithm within 1.5 minutes, which is less than the computational time (more than 10 minutes) of the CPLEX solver. Thus, the results demonstrate that the proposed GA-PSO algorithm can find a best solution within acceptable time more effectively compared with other algorithms above.


### 5.5. Limitations

The proposed method performs well under those assumptions mentioned in Section2.1, which is proved by the illustrated case study. Furthermore, the proposed model and algorithm are suitable for solving slight disturbances such as unscheduled stop, prolonged process, and temporary speed limitation in daily operation. To tackle the large-scale instance effectively, the proposed model is also macroscopic. Nonetheless, when large disruptions such as complete blockage and train breakdown occur, new rescheduled strategies (for example, short-turning [18]) should be considered. Moreover, the applicability of rescheduled timetable should be improved in particular the safety and feasibility at interior block sections of stations. That is, the performance of the proposed method may be doubted and the method need to be minor adjusted accordingly.


## 5.1. Case Description: A Realistic Chinese High-Speed Railway Corridor

The proposed methodology is applied to the busiest high-speed railway corridor from Beijing to Shanghai (more than 95 train services per day). The Beijing-Shanghai high-speed railway corridor, represented by the orange line in Figure6, consists of 23 railway stations and 22 open track sections. Each station with its name and short name, distance from BJN, the capacities of stations, and travel times of those sections are shown in Table 2. The additional times caused by the start-up and stop at the station are 2 minutes and 1 minutes, respectively, and the minimum headway is 5 minutes during peak hours.Table 2
Parameters related to infrastructures.
Station name Short name Distance from BJN (km) Number of tracks (station capacity) Travel times from the previous station (minute) BeijingNan BJN 0 12 0 Langfang LF 59 2 22 TianjinNan TJN 131 3 16 CangzhouXi CZX 219 3 22 DezhouDong DZD 327 4 26 JinanXi JNX 419 8 23 Taian TA 462 4 15 Qufu QF 533 4 18 TengzhouDong TZD 589 2 14 ZaoZhuang ZZ 625 4 9 XuzhouDong XZD 688 7 16 Suzhou Dong SZD 767 3 17 Bengbu Nan BBN 844 7 22 Dingyuan DY 897 2 14 Chuzhou CZ 959 2 16 NanjingNan NJN 1018 5 19 ZhenjiangNan ZJN 1087 3 20 DanyangBei DYB 1112 2 7 ChangzhouBei CZB 1144 3 8 WuxiDong WXD 1201 3 14 SuzhouBei SZB 1227 3 7 KunshanNan KSN 1259 9 8 Hongqiao HQ 1302 11 17Figure 6
The overview of the Chinese high-speed railway network.Next, four delay cases are designed, reported in Table3. The delay cases are identified by the train name, station name, delay type, and delay time. In these experiments, the scheduled timetable contains 40 trains in down direction within the time horizon. Arrival delays, departure delays, and unscheduled stop caused by disturbances (e.g., unscheduled stop, prolonged process, and route conflict) are considered. Moreover, we assume that the disturbance length is very short (i.e., within an hour).Table 3
Delay cases description.
Index of case Train name Station name Type Delay time (min) Case 1 G109 BBN Unscheduled stop 20 Case 2 G123 DZD Departure delay 10 Case 3 G139 NJN Departure delay 10 Case 4 G155 JNX Departure delay 15


## 5.2. Parameters Setting

To determine the GA-PSO algorithm related parameters (i.e.,w,c1,c2,Pc, and Pm), a full factorial design is applied in this section. The relative deviation index (RDI) [30] is proposed to compare the performance of different parameter combinations as follows:(27)RDIi=fiopt-fminfmax-fmin·100where fiopt is the value of the optimum objective function with the ith parameter combination; fmax and fmin are the worst and best objective function values among the parameter combinations, respectively. Punctuality (i.e., the rate of train services whose delays are less than threshold) is an important measure of service quality during daily operation, and it also influences rolling-stock and crew circulation plans. The objective, the number of trains whose delays exceed the threshold, should gain more attention in the proposed model. Thus, penalty weights of total train service delays and the number of trains whose delays exceed the threshold Qdelay (i.e., 4 min) are one and 10000, respectively [37]. According to Jamili et al. (2012) [30],pop is 20 and the termination criterion is that the maximal iterationsnum is 1000 or the precisionerror is 0.05.Next, we record the best solution under the different parameter combinations ofw,c1,Pc, and Pm. Note that w,c1, and pc are in the range of [0.35,0.65], and pm is in the range of [0.05,0.2]. The main effects of the parameter combinations are investigated and depicted in Table 4. The results show that the combination of w=0.65, c1=0.5, pc=0.6, and pm=0.15 is better than other parameter combinations. Furthermore, the parameter c1 is set as 0.5, and c2 is randomly chosen at each time step in the range 0,1.Table 4
The interaction of different parameter combinations.
w , c 1 , P c , P m 0.65,0.5,0.6,0.15 0.4,0.5,0.6,0.15 0.65,0.5,0.6,0.2 0.65,0.6,0.6,0.15 Best objective value 52460 73000 62940 74740 RDI 0 63% 32% 68%


## 5.3. Result Analysis

In this section, the rescheduled timetable and results are analyzed. First, the best rescheduled timetable is obtained by the proposed GA-PSO as shown in Figure7, where grey and blue lines represent the scheduled train service paths and rescheduled train service paths, respectively. To reduce the number of delayed trains and total delay time, the sequence of adjacent trains occupying the same block section is changed in the best solution. For instance, the order of which the trains named G109 and G111 enter the BBN-DY section is changed, which makes sure that G111 is operated with scheduled time (see left red circle in Figure 7) and the number of delayed trains is reduced. Furthermore, the increase of dwell time can avoid route conflict. For example, since the dwell time of the train named G147 at ZJN station is increased (i.e., 180 sec), the conflict among trains disappear (see right red circle in Figure 7).Figure 7
The best rescheduled time-distance diagram based on the proposed GA-PSO.Next, the results, such as primary delays, knock-on delays, knock-on delayed trains, objective function value, and computational time, are reported in Table5. All delay cases 1, 2, 3, and 4 can be solved in less than one minute. From the delay case 1 to delay case 4, the minimum headway of disrupted adjacent trains is ten, five, eight, and seven minutes, respectively. The results show that large value of the objective function corresponds to great impact illustrated by knock-on delays and the number of knock-on delayed trains on scheduled timetable. For example, the impact of delay case 3 (with objective value 180) is small, and the impact of delay case 1 and delay case 2 (with objective value 20600 and 21080, respectively) is stronger. The distribution of delays of each train is shown in Figure 8. According to the obtained results, two general conclusions are revealed.Table 5
Results of delay cases.
Index of case Delays Knock-on delayed trains Best objective value Computational time (sec) Primary delays (sec) Knock-on delays (sec) Case 1 1200 600 G113, G1 20600 42 Case 2 600 1080 G411, G127 21080 56 Case 3 600 180 --- 180 31 Case 4 900 600 G149 10600 40Figure 8
The delays distribution of each train.(1) Greater primary delays will result in stronger impact on the scheduled timetable when approximately the same minimum headway is considered.(2) High-density traffic flow has a great delay propagation on the railway network when same primary delays occur (the same point also refers to [39]).


## 5.4. Comparison of Different Approaches

In this section, the performance of the proposed method is tested compared with other heuristic algorithms (i.e., the FSFS strategy, FCFS strategy, and the PSO). Moreover, the gap between the best solution obtained by the proposed method and the optimal solution computed by CPLEX solver is analyzed.The FSFS and FCFS rescheduling strategies (mentioned in Section4.2) and the PSO algorithm are applied to investigate delay cases, respectively. The objective obtained by FSFS, FCFS rescheduling strategies, and CPLEX solver is as the benchmark solution. All delay cases are considered together in this section and the results obtained by different approaches are shown in Figure 9. Note that the initial solution (with value 105880) of the GA-PSO and the PSO algorithm is set considering FSFS strategy. The objective of FSFS strategy is the upper bound value, and the optimal objective computed by CPLEX solver is the lower bound value.Figure 9
Comparison of different approaches.According to the results, the objective value (52460) obtained by the proposed GA-PSO algorithm outperforms that of the FCFS strategy. Specifically, the objective value of the GA-PSO is reduced by 15.6%, 48.8%, and 25.7% compared with the FCFS strategy, the FSFS strategy, and the PSO, respectively, shown in Figure9. The lower bound (with optimal solution 42194) refers to the gap between the CPLEX solver and the proposed method, which is around 19.6% in this case. However, the delay case is solved by the proposed GA-PSO algorithm within 1.5 minutes, which is less than the computational time (more than 10 minutes) of the CPLEX solver. Thus, the results demonstrate that the proposed GA-PSO algorithm can find a best solution within acceptable time more effectively compared with other algorithms above.


## 5.5. Limitations

The proposed method performs well under those assumptions mentioned in Section2.1, which is proved by the illustrated case study. Furthermore, the proposed model and algorithm are suitable for solving slight disturbances such as unscheduled stop, prolonged process, and temporary speed limitation in daily operation. To tackle the large-scale instance effectively, the proposed model is also macroscopic. Nonetheless, when large disruptions such as complete blockage and train breakdown occur, new rescheduled strategies (for example, short-turning [18]) should be considered. Moreover, the applicability of rescheduled timetable should be improved in particular the safety and feasibility at interior block sections of stations. That is, the performance of the proposed method may be doubted and the method need to be minor adjusted accordingly.


## 6. Conclusions

In this paper, a MIP model and a GA-PSO method are developed to solve the railway timetable rescheduling problem with the consideration of primary delays. The two objectives that included in the proposed train timetable rescheduling model are (1) minimal total delays and (2) the number of train services whose delays exceed the threshold. The constraints consist of original scheduled timetable restrictions and resource capacity restrictions. The developed GA-PSO algorithm integrates the advantages of GA and PSO. Moreover, the method is extended to a real case of the Beijing-Shanghai high-speed railway corridor. The objective value calculated by the developed GA-PSO is reduced by 15.6%, 48.8%, and 25.7% compared with the FCFS strategy, the FSFS strategy, and the PSO, respectively. The real case study verifies the effectiveness of the proposed method. Moreover, the case study gives insight into the correlation between delay propagation and headway. The primary delays occur in high-density period (scheduled headway closes to the minimum headway), which results in a great delay propagation.Currently, the proposed model does not suite solving serious disruptions (for example, complete blockage), since longer lengths and uncertainties of disruptions are not considered in this study. A challenge for the future work is to examine the upper bound of disturbance length, while the method can still be used in acceptable computational time. A microscopic reschedule model with the consideration of interior layout of stations is to be formulated, to further demonstrate detailed safety and feasibility of the proposed dispatching measures. Since recent trend of data-driven approaches applies to transportation field and massive databases of historical traffic data, characteristics of train operation and rescheduling strategies mined by data learning methods are also an interesting direction for future studies.



---

*Source: 6090742-2019-03-20.xml*