# Models and Algorithms of Conflict Detection and Scheduling Optimization for High-Speed Train Operations Based on MPC

Authors: Zhihui Wang; Yonghua Zhou; Deng Liu
Journal: Journal of Control Science and Engineering
 (2018)

---

## Abstract

The high-speed train with high transport speed and punctuality rate has become a leading tool of daily traveling. Compared with the general-speed railway transportation, the high-speed railway transportation requires a timely and automatic adjustment capability in the centralized traffic control (CTC) system. In order to improve the capability, this paper mainly explores the models and algorithms of conflict detection and scheduling optimization of high-speed train operations. They are implemented under the mechanism of model predictive control (MPC) over the rolling prediction horizon. A train movement prediction model with conflict resolution is established. The mechanism of conflict detection and scheduling optimization is implemented through a case study. The simulation results demonstrate the effectiveness of the proposed mechanism.


---

## Body

## 1. Introduction

High-speed train operations may be inevitably disturbed by unexpected events such as bad weather or equipment failure. In these cases, the delays of some trains in a railway network will cause operation conflicts to take place, and actual train operations will deviate from preset timetables. If there is no timely adjustment to train operation plans, transportation efficiency will be decreased and, even, operation safety may be endangered. Therefore, the centralized traffic control (CTC) system requires timely detection of potential operation conflicts and engendering optimal scheduling strategies in advance.Some literature has dealt with train scheduling and rescheduling problems. Szpigel [1] studied the problem of train scheduling on a single track line and modeled it as a job shop scheduling problem which is solved by the branch and bound algorithm. After that, train scheduling problem had aroused the interests to the scholars from various countries. Cordeau et al. [2] conducted a comprehensive survey on train scheduling and routing problems. Chiang et al. [3] put up a knowledge-based scheduling approach, employing global scheduling to deal with main plans and local scheduling to handle conflicts. Caprara et al. [4] put forward a solution method of a timetabling problem, utilizing Lagrangian relaxation to deal with constraints. D’Ariano et al. [5] proposed an alternative graph to describe scheduling strategies and adopted the branch and bound algorithm to solve the rescheduling problem under disturbances. D’Ariano et al. [6] proposed a branch and bound algorithm for the train scheduling problem in railway networks. Salido et al. [7] utilized graph decomposition technique to break a train scheduling problem into several subproblems. Zhou and Zhong [8] proposed a Lagrangian relaxation approach to provide a lower bound to the branch and bound algorithm which is utilized to solve the single-line timetabling problem. Cacchiani et al. [9] proposed an exact and heuristic algorithm to solve the train timetabling problem based on linear programming (LP) relaxation of an integer linear programming (ILP) formulation. Khan and Zhou [10] established a stochastic optimization model of timetabling problem and proposed a heuristic sequence solution method. Mu and Dessouky [11] presented an optimization scheduling approach using genetic algorithm for freight trains. Yang et al. [12] explored the fuzzy and stochastic programming for freight transportation and utilized genetic algorithm to solve the chance constraint programming model. Yalçinkaya and Bayhan [13] put up a random simulation approach to produce feasible timetables. Krasemann [14] proposed a greedy algorithm using depth-first searching and evaluation function ordering to find the satisfactory solution of a train scheduling problem. Chevrier et al. [15] explored the energy-efficient timetabling problem using multiobjective evolution approach. Espinosa-Aranda and García-Ródenas [16] put up a heuristic algorithm using alternative arcs to minimize the traveling delay time. Li et al. [17] proposed the greedy algorithm to solve the train rescheduling problem with random delay. Kang et al. [18] presented the model and genetic solution algorithm of train rescheduling in urban railway transit networks. Zhan et al. [19] established a two-stage algorithm for the mixed programming model of high-speed train rescheduling problem to decide the wait stations and leave orders of scheduled trains. Šemrov et al. [20] proposed a reinforcement learning approach for the train rescheduling problem and compared its superiority with the rescheduling methods without learning. Kersbergen et al. [21] presented a dynamic model predictive control for railway traffic management which can improve calculation speeds and achieve good performances. Bettinelli et al. [22] proposed a real-time processing algorithm to avoid potential conflicts for railway traffic management. Eaton et al. [23] explored the ability of ant colony optimization to engender nondominated solutions for the dynamic multiobjective train rescheduling problem.Statistics pointed out that 16% of the working hours for train dispatchers are to modify and implement train operation plans, only 4% of the time is to develop conflict resolution strategies, and the remaining 80% of the time is used to identify train operation conflicts. It can be seen that the discovery and settlement of train operation conflicts due to random disturbances are the most important work of dispatchers. How to utilize the advanced computer technology to timely and accurately detect train operation conflicts and optimize scheduling strategies has great practical significance to reduce the workload of dispatchers.Model predictive control (MPC) has been successfully applied into industrial control, such as chemical, petroleum, metallurgy, and electric power control [24, 25]. The mechanism of prediction, feedback, and optimization in MPC is also applicable to the conflict resolution and scheduling optimization. This paper attempts to establish the framework of conflict resolution and scheduling optimization under the mechanism of MPC, focusing on the global framework elucidation, conflict detection approaches, and prediction model construction with conflict resolution [26, 27], which are different from the current literature.The remainder of this paper is organized as follows. In Section2, the framework is outlined. Section 3 addresses the conflict detection approaches and resolution strategies. Section 4 establishes the train movement prediction model taking conflict resolution into account. Section 5 elucidates the optimization scheduling model and algorithm. Section 6 demonstrates the case study. Finally, the concluding remarks are given in Section 7 to summarize the contribution of this paper.


## 2. Conflict Detection and Scheduling Optimization Framework

MPC is a computer-based optimization control methodology in industry. Based on the current states of a system and the prediction model, the future states of the system are predicted in the prediction horizon under the presumed control input sequences. The control inputs are optimized such that the predicted states approach the preset ones. Such a process repeats at a regular period or is driven by an event, and the prediction horizon rolls forward. MPC has various implementation ways in industrial control systems but is composed of three basic parts: prediction model, rolling optimization, and feedback adjustment.In this paper, the mechanism of MPC is introduced into the conflict detection and scheduling optimization for high-speed railway traffic. The basic framework is shown in Figure1. Train safe and punctual operations are regarded as the control objectives. In accordance with the MPC mechanism, the conflict detection and scheduling optimization are implemented over the rolling prediction horizon so that the predicted timetable approaches the preset one, and, moreover, train operation safety is guaranteed.Figure 1
The framework of conflict detection and scheduling optimization of train operations based on model predictive control.The main implementation procedure is described as follows.Step 1.
At current instant, sample the train operation state information such as positions and speeds.Step 2.
According to train operation models, predict train operation states in the prediction horizon on the basis of acquired position and speed information.Step 3.
Detect if there exist operation conflicts in the prediction horizon. If conflicts occur, produce feasible scheduling strategies. Scheduling strategies are optimized so that no conflicts occur and predicted timetable approaches the preset one.Step 4.
The prediction horizon moves forward a specified period. Go toStep1.


## 3. Conflict Detection and Resolution

According to tempo-spatial constraints of high-speed train operations, operation conflicts can be categorized into the main four types, that is, section conflict, departure time conflict, arrival time conflict, and track number conflict, which are critical to train operation safety and often are paid great attention in practice. The section conflict means the operation time (or space) interval between two adjacent trains does not satisfy the safe constraint. The departure time conflict denotes the fact that the departure time interval from a station between two trains does not meet the minimum departure interval constraint, and the arrival time conflict represents the arrival time interval at a station between two trains not meeting the minimum arrival interval constraint. The track number conflict refers to the fact that the number of trains to dwell at or pass through a station has exceeded the number capacity of station tracks for trains’ arrival and departure. Notations section (The Symbols’ Definition of Conflict Detection and Scheduling Optimization) defines the symbols related to conflict description and conflict resolution.


### 3.1. Section Conflict and Resolution

When two adjacent trains run between stations, the distance between them is less than the minimum safety interval, and the running speed of the rear train is higher than that of the front one, the section conflict occurs, as shown in Figure2. Figure 2 demonstrates the running trajectories of position (vertical) versus time (horizontal) of two trains. Train m runs faster than train n. The intersection point between two running lines is the collision place, which locates between stations.Figure 2
Section conflict and resolution.
(a)
Trainm runs more slowly (b)
Trainn runs faster (c)
Trainm stops at the passing station (d)
Trainn stops at the passing stationThe section conflict between two adjacent trains running in the same direction can be formulated as(1)tm,kD-tn,kDtm,lA-tn,lA<0.Equation (1) signifies the fact that the orders that trains m and n depart from station k and arrive at station l are different.Two main approaches can be utilized to resolve the section conflict.( 1 ) When there is no passing station between stations k and l, the conflict can be prevented by driving the rear train m towards a smaller maximum running speed as shown by the dashed line (m′) in Figure 2(a). The cost is the delay of train m. Otherwise, it can be achieved through driving the front train n towards a bigger maximum running speed as shown by the dashed line (n′) in Figure 2(b) without delaying train m.( 2 ) When there is a passing station between stations k and l, let train m or n stop at the passing station for a while to resolve the conflict, as shown by the dashed line (m′ or n′) in Figure 2(c) or 2(d), respectively. The cost is the delay of train m or n.


### 3.2. Departure Time Conflict and Resolution

When two adjacent trains depart from the same station, the relevant technical standards should be satisfied; that is, the departure time interval cannot be less than the configured minimum value, or the conflict will arise as shown in Figure3.Figure 3
Departure time conflict and resolution.
(a)
Delay the departure of trainn (b)
Delay the departure of trainmAccording to Figure3, the departure time conflict is expressed as(2)tm,kD-tn,kD<TDminm,n∈T,k∈S.Equation (2) denotes the departure time interval between trains m and n being less than the limit of minimum departure time interval.The possible methods to resolve the conflict are as follows.(  1) Transform the Operation Line of Train n. The departure time of train n is delayed so that the departure time interval between trains m and n is greater than or equal to the limit of minimum departure time interval, as shown by the dashed line (n′) in Figure 3(a).(  2) Transform the Operation Line of Train m. The departure time of train m is delayed to meet the technical standard of departure time intervals, as shown by the dashed line (m′) in Figure 3(b).


### 3.3. Arrival Time Conflict and Resolution

When two adjacent trains arrive at the same station, the arrival time interval at the same station should be greater than the configured minimum value; otherwise the conflict disobeying the technical standards will occur as shown in Figure4.Figure 4
Arrival time conflict and resolution.
(a)
Slow down trainn (b)
Speed up trainmAs Figure4 indicates, the arrival time conflict at a station is identified as(3)tm,lA-tn,lA<TAminm,n∈T,l∈S.Equation (3) reveals the case dissatisfying the technical standard of arrival time constraints.To resolve the arrival time conflict, the following measures can be taken.(  1) Slow Down Train n. As shown by the dashed line (n′) in Figure 4(a), when the maximum operation speed of train n decreases, the requirement of arrival time interval at a station can be satisfied.(  2) Speed Up Train m. The dashed line (m′) in Figure 4(b) demonstrates that increasing the operation speed of train m is a possible measure to make the arrival time interval at a station between two trains greater than the minimum value specified by the technical standard.


### 3.4. Track Number Conflict and Resolution

The total number of trains to arrive at or pass through a station cannot exceed the capacity that the station can provide. If a train is approaching or directly passing through a station, but there is no surplus track at the station to accommodate the train, the track number conflict will be brought about. The judgement rule of track number conflict is represented as(4)∑m∈Tαm,k>Mkk∈S.When a track number conflict takes place at a station, the alternative strategy to resolve it is to command the related train to slow down towards the station or even stop outside the station.


## 3.1. Section Conflict and Resolution

When two adjacent trains run between stations, the distance between them is less than the minimum safety interval, and the running speed of the rear train is higher than that of the front one, the section conflict occurs, as shown in Figure2. Figure 2 demonstrates the running trajectories of position (vertical) versus time (horizontal) of two trains. Train m runs faster than train n. The intersection point between two running lines is the collision place, which locates between stations.Figure 2
Section conflict and resolution.
(a)
Trainm runs more slowly (b)
Trainn runs faster (c)
Trainm stops at the passing station (d)
Trainn stops at the passing stationThe section conflict between two adjacent trains running in the same direction can be formulated as(1)tm,kD-tn,kDtm,lA-tn,lA<0.Equation (1) signifies the fact that the orders that trains m and n depart from station k and arrive at station l are different.Two main approaches can be utilized to resolve the section conflict.( 1 ) When there is no passing station between stations k and l, the conflict can be prevented by driving the rear train m towards a smaller maximum running speed as shown by the dashed line (m′) in Figure 2(a). The cost is the delay of train m. Otherwise, it can be achieved through driving the front train n towards a bigger maximum running speed as shown by the dashed line (n′) in Figure 2(b) without delaying train m.( 2 ) When there is a passing station between stations k and l, let train m or n stop at the passing station for a while to resolve the conflict, as shown by the dashed line (m′ or n′) in Figure 2(c) or 2(d), respectively. The cost is the delay of train m or n.


## 3.2. Departure Time Conflict and Resolution

When two adjacent trains depart from the same station, the relevant technical standards should be satisfied; that is, the departure time interval cannot be less than the configured minimum value, or the conflict will arise as shown in Figure3.Figure 3
Departure time conflict and resolution.
(a)
Delay the departure of trainn (b)
Delay the departure of trainmAccording to Figure3, the departure time conflict is expressed as(2)tm,kD-tn,kD<TDminm,n∈T,k∈S.Equation (2) denotes the departure time interval between trains m and n being less than the limit of minimum departure time interval.The possible methods to resolve the conflict are as follows.(  1) Transform the Operation Line of Train n. The departure time of train n is delayed so that the departure time interval between trains m and n is greater than or equal to the limit of minimum departure time interval, as shown by the dashed line (n′) in Figure 3(a).(  2) Transform the Operation Line of Train m. The departure time of train m is delayed to meet the technical standard of departure time intervals, as shown by the dashed line (m′) in Figure 3(b).


## 3.3. Arrival Time Conflict and Resolution

When two adjacent trains arrive at the same station, the arrival time interval at the same station should be greater than the configured minimum value; otherwise the conflict disobeying the technical standards will occur as shown in Figure4.Figure 4
Arrival time conflict and resolution.
(a)
Slow down trainn (b)
Speed up trainmAs Figure4 indicates, the arrival time conflict at a station is identified as(3)tm,lA-tn,lA<TAminm,n∈T,l∈S.Equation (3) reveals the case dissatisfying the technical standard of arrival time constraints.To resolve the arrival time conflict, the following measures can be taken.(  1) Slow Down Train n. As shown by the dashed line (n′) in Figure 4(a), when the maximum operation speed of train n decreases, the requirement of arrival time interval at a station can be satisfied.(  2) Speed Up Train m. The dashed line (m′) in Figure 4(b) demonstrates that increasing the operation speed of train m is a possible measure to make the arrival time interval at a station between two trains greater than the minimum value specified by the technical standard.


## 3.4. Track Number Conflict and Resolution

The total number of trains to arrive at or pass through a station cannot exceed the capacity that the station can provide. If a train is approaching or directly passing through a station, but there is no surplus track at the station to accommodate the train, the track number conflict will be brought about. The judgement rule of track number conflict is represented as(4)∑m∈Tαm,k>Mkk∈S.When a track number conflict takes place at a station, the alternative strategy to resolve it is to command the related train to slow down towards the station or even stop outside the station.


## 4. Train Operation Simulation and Prediction

### 4.1. Train Operation Simulation

In the moving-block train control system, a train runs according to the preset logical processes. At first, the equipment of automatic train protection (ATP) constantly judges whether the current train speed exceeds the speed limit along a railway line. If an overspeed phenomenon occurs, according to the overspeed degree, the corresponding braking deceleration will be implemented. The more the speed exceeds a limit, the bigger deceleration will be adopted. Figure5 demonstrates the application ranges of service braking (SB) and emergency braking (EB). On the other hand, the onboard control equipment of a train determines if braking should be applied according to the braking reference distance of a train to its front adjacent train. If braking is not applied, the train can accelerate towards the maximum speed or hold its current speed. Otherwise, the train will decelerate towards the target speed at the target point.Figure 5
The application ranges of service braking and emergency braking.The symbols for train movements are defined in Notations section (The Symbols’ Definition of Train Movement Model). The train movement model for simulation and prediction is described as follows, where the speed, acceleration, and deceleration are in the time unit, so the time unit is omitted in the rules of speed and position update.(i)
Speed Update(1)
IF (v(i)≤250km/h AND v(i)-vlim(x(i))>5km/h AND v(i)-vlim(x(i))≤10km/h) OR(2)
(v(i)>250 km/h AND v(i)-vlim(x(i))>5 km/h  AND v(i)-vlim(x(i))≤15km/h)(3)
v(i+1)=max(v(i)-bs,0)(4)
ENDIF(5)
IF (v(i)≤250km/h AND v(i)-vlim(x(i))>10km/h) OR(6)
(v(i)>250 km/h AND v(i)-vlim(x(i))>15 km/h)(7)
v(i+1)=max(v(i)-be,0)(8)
ENDIF(9)
IFdt(i)>dr,  v(i+1)=min(v(i)+a,vmax)(10)
ELSEIFdt(i)=dr,  v(i+1)=v(i)(11)
ELSE(12)
v(i+1)=max(v(i)-bs,vt)(13)
ENDIF(ii)
Position update(14)
x(i+1)=x(i)+v(i)In the train movement model, sentences(1) to (4) indicate the service braking application case according to Figure 5, while sentences (5) to (8) represent the emergency braking application case. Sentence (9) implies that if the distance of a train to its operation target point is greater than the braking reference distance, the train will accelerate towards the maximum speed; sentence (10) shows the case that the train holds its current speed; sentence (12) denotes that the target speed for deceleration is vt. Sentence (14) demonstrates the position update within the unit time.


### 4.2. Conflict Resolution in the Prediction Horizon

According to the discussion in Section2, the conflict resolution algorithm in the prediction horizon is described as follows:(1)
IF(tm,kD-tn,kD)(tm,lA-tn,lA)<0 after prediction(2)
vm(i+1)=min⁡(v(i)+a,vmaxs) if train maccelerates,(3)
or vn(i+1)=min⁡(v(i)+a,vmaxb) if train naccelerates,(4)
or if there is a passing station, stop at the passingstation for train m or n.(5)
ENDIF(6)
IFtm,kD-tn,kD<TDmin(7)
Delay the departure time of train m or n.(8)
ENDIF(9)
IFtm,lA-tn,lA<TAmin10
vmi+1=min⁡vi+a,vmaxb if train maccelerates,(11)
or vn(i+1)=min⁡(v(i)+a,vmaxs) if train naccelerates.(12)
ENDIF13
IF∑m∈Tαm,k>Mk(14)
Train m decelerates towards or even stops outside  the arrival station.(15)
ENDIn the above conflict resolution algorithm, sentences(1) to (5) deal with the section conflict, sentences (6) to (8) the departure time conflict, sentences (9) to (12) the arrival time conflict, and sentences (13) to (15) the track number conflict, which are based on Section 3. In sentences (9) to (12), train m or n runs at different maximum running speeds.


## 4.1. Train Operation Simulation

In the moving-block train control system, a train runs according to the preset logical processes. At first, the equipment of automatic train protection (ATP) constantly judges whether the current train speed exceeds the speed limit along a railway line. If an overspeed phenomenon occurs, according to the overspeed degree, the corresponding braking deceleration will be implemented. The more the speed exceeds a limit, the bigger deceleration will be adopted. Figure5 demonstrates the application ranges of service braking (SB) and emergency braking (EB). On the other hand, the onboard control equipment of a train determines if braking should be applied according to the braking reference distance of a train to its front adjacent train. If braking is not applied, the train can accelerate towards the maximum speed or hold its current speed. Otherwise, the train will decelerate towards the target speed at the target point.Figure 5
The application ranges of service braking and emergency braking.The symbols for train movements are defined in Notations section (The Symbols’ Definition of Train Movement Model). The train movement model for simulation and prediction is described as follows, where the speed, acceleration, and deceleration are in the time unit, so the time unit is omitted in the rules of speed and position update.(i)
Speed Update(1)
IF (v(i)≤250km/h AND v(i)-vlim(x(i))>5km/h AND v(i)-vlim(x(i))≤10km/h) OR(2)
(v(i)>250 km/h AND v(i)-vlim(x(i))>5 km/h  AND v(i)-vlim(x(i))≤15km/h)(3)
v(i+1)=max(v(i)-bs,0)(4)
ENDIF(5)
IF (v(i)≤250km/h AND v(i)-vlim(x(i))>10km/h) OR(6)
(v(i)>250 km/h AND v(i)-vlim(x(i))>15 km/h)(7)
v(i+1)=max(v(i)-be,0)(8)
ENDIF(9)
IFdt(i)>dr,  v(i+1)=min(v(i)+a,vmax)(10)
ELSEIFdt(i)=dr,  v(i+1)=v(i)(11)
ELSE(12)
v(i+1)=max(v(i)-bs,vt)(13)
ENDIF(ii)
Position update(14)
x(i+1)=x(i)+v(i)In the train movement model, sentences(1) to (4) indicate the service braking application case according to Figure 5, while sentences (5) to (8) represent the emergency braking application case. Sentence (9) implies that if the distance of a train to its operation target point is greater than the braking reference distance, the train will accelerate towards the maximum speed; sentence (10) shows the case that the train holds its current speed; sentence (12) denotes that the target speed for deceleration is vt. Sentence (14) demonstrates the position update within the unit time.


## 4.2. Conflict Resolution in the Prediction Horizon

According to the discussion in Section2, the conflict resolution algorithm in the prediction horizon is described as follows:(1)
IF(tm,kD-tn,kD)(tm,lA-tn,lA)<0 after prediction(2)
vm(i+1)=min⁡(v(i)+a,vmaxs) if train maccelerates,(3)
or vn(i+1)=min⁡(v(i)+a,vmaxb) if train naccelerates,(4)
or if there is a passing station, stop at the passingstation for train m or n.(5)
ENDIF(6)
IFtm,kD-tn,kD<TDmin(7)
Delay the departure time of train m or n.(8)
ENDIF(9)
IFtm,lA-tn,lA<TAmin10
vmi+1=min⁡vi+a,vmaxb if train maccelerates,(11)
or vn(i+1)=min⁡(v(i)+a,vmaxs) if train naccelerates.(12)
ENDIF13
IF∑m∈Tαm,k>Mk(14)
Train m decelerates towards or even stops outside  the arrival station.(15)
ENDIn the above conflict resolution algorithm, sentences(1) to (5) deal with the section conflict, sentences (6) to (8) the departure time conflict, sentences (9) to (12) the arrival time conflict, and sentences (13) to (15) the track number conflict, which are based on Section 3. In sentences (9) to (12), train m or n runs at different maximum running speeds.


## 5. Scheduling Optimization

The objective of scheduling optimization is to generate new scheduling strategies if there exist potential operation conflicts or the deviation between the practical timetable and the preset timetable is too large. The new scheduling strategies must meet the following conditions:(1)
They resolve the existing operation conflicts(2)
There is no new conflict in the newly generated timetable(3)
The difference between the new timetable and the preset timetable is minimized.Therefore, the objective function and constraint conditions are described as(5)min∑j∈S∑m∈Twmtm,j-tm,j′(6)s.t.tm,k-tn,k≥Tminm,n∈T,k∈B(7)tm,kD-tm,kA≥DTkminm∈T,k∈S(8)tm,kD-tn,kD≥TDminm,n∈T,k∈S(9)tm,kA-tn,kA≥TAminm,n∈T,k∈S(10)∑m∈Tαm,k≤Mkk∈S,where wm is the weighting coefficient of train m. The higher the priority of train m is, the bigger the weight wm is. Equation (6) represents the constraint of safe time interval between two adjacent trains arriving at a section to avoid section conflicts. Equation (7) implies that the dwelling time at a station cannot be less than the specified minimum value. Equation (8) points out the limitation condition of departure time interval between two trains from a station. Equation (9) shows the restraint of arrival time interval between two trains at a station. Equation (10) demonstrates the fact that the number of trains arriving at a station cannot exceed the capacity limit of the station.Branch and Bound (B&B) algorithm is an important method to solve the combinatorial optimization problem. It searches the solution of a problem in the solution space tree. The core idea of the B&B algorithm is to expand the whole feasible solution space for the optimization problem with constraints and gradually decide the optimal solution satisfying constraint conditions.The two core steps of the B&B algorithm are bounding and pruning. Bounding is to determine a reasonable range of objective function values, and the reasonable reference boundary is further provided to the pruning operation. For the maximization problem, bounding is to determine the lower bound of the objective function values. For the minimization problem, bounding is to find out the upper bound of the objective function values. The main function of pruning is to remove the branches that cannot produce the optimal solution so as to improve the search efficiency of the algorithm.When applying the B&B algorithm to the conflict detection and scheduling optimization problem in the prediction horizon, each feasible solution for the conflict resolution in Section3 has a new timetable corresponding to it. The B&B algorithm takes the possible maximum deviation between the newly generated timetable and the preset timetable as the upper bound (UB). The procedure of B&B algorithm to solve the optimization problem is described as follows.Step 1.
Determine the initial boundary of objective function values [0, UB] through train operation simulation.Step 2.
Initialize the list of live nodes to be empty.Step 3.
Take the place where the conflict occurs as a potential extension node to implement branch operation.Step 4.
Find the node with the smallest objective function value Val in the list of live nodes with regard to the newly generated tree.
Step 4.1. Calculate Val of a child node x in the list of live nodes according to train operation simulation.
Step 4.2. If Val ≤ UB, add the child node x to the list of live nodes.
Step 4.3. If the node x is the leaf node and its Val is the smallest in the list of live nodes, the corresponding scheduling strategy is optimal. Output the scheduling strategy, and the algorithm is finished.
Step 4.4. If node xis a leaf node but its Val is not the smallest in the list of live nodes, then let UB = Val, and, at the same time, delete the nodes whose Vals are greater than UB.
Step 4.5. Return toStep 4.1.


## 6. Case Study

The simulation is performed around a node, Changsha South Station in the China’s “four vertical and four horizontal” high-speed railway network, as shown in Figure6. Two railway lines are involved in the simulation, that is, Beijing-Guangzhou line (in red) and Shanghai-Kunming line (in green).Figure 6
High-speed railway network.The layout of Changsha South Station is shown in Figure7. At the entrance of 20 km away from the Changsha South Station, two railway lines are merged. Two platforms are provided at Changsha South Station. At the exit of 20 km away from the Changsha South Station, there exist two forks towards different terminal stations. The maximum speed of the trains on the Shanghai-Kunming line is 80 m/s and the dwelling time at Changsha South Station is 150 s. The maximum speed of the trains on the Beijing-Guangzhou line is 100 m/s and the dwelling time is 50 s. The minimum departure and arrival time intervals are 50 s. The minimum safe time interval is also 50 s. The prediction horizon is set to be 600 s, and the control horizon is equal to the prediction horizon. The sample period is configured to be equal to the simulation period.Figure 7
Changsha South Station layout.In the simulation test, we set that there are four trains on the Beijing-Guangzhou line, and train numbers are 001, 003, 005, and 007. There are three trains on the Shanghai-Kunming line, and train numbers are 002, 004, and 006. The preset timetables of the trains are shown in Table1.Table 1
The preset timetables of the trains.
Train number Turnout 1 Turnout 2 Turnout 3 Turnout 4 001 0 200 250 450 002 50 300 450 700 003 150 350 400 600 004 200 450 600 850 005 300 500 550 750 006 350 600 750 1000 007 450 650 700 900The global implementation procedure of the MPC mechanism for conflict detection and scheduling optimization can refer to Section2. An unexpected disturbance is configured, which causes a delay of 200 s for train 001 at turnout 1, based on the prediction of train operations considering current feedback information of train positions and speeds. According to the preset timetable, it should be train 004 which passes through turnout 1 at 200 s. However, due to the delay propagation in the whole network, train operation conflicts are gradually detected and resolved through the models and algorithms in Sections 3 and 4. Consequently, the new timetables are produced through the common First Come First Served (FCFS) and the B&B scheduling strategies represented in Section 5, which are listed in Tables 2 and 3, respectively. It can be calculated that the total delays of the trains are 4350 s and 4150 s in the timetables generated by FCFS and B&B strategies, respectively. The B&B strategy can achieve less delay than FCFS.Table 2
The obtained timetable through FCFS algorithm in case of delay.
Train number Turnout 1 Turnout 2 Turnout 3 Turnout 4 001 200 400 450 650 002 250 500 650 900 003 300 550 600 800 004 350 600 750 1000 005 400 650 700 950 006 450 700 850 1100 007 500 750 800 1050Table 3
The newly generated timetable through B&B algorithm in case of delay.
Train number Turnout 1 Turnout 2 Turnout 3 Turnout 4 001 200 400 450 650 003 250 450 500 700 005 300 500 550 750 002 350 600 800 1050 004 400 650 850 1100 007 450 700 750 950 006 500 750 900 1150In order to further verify the validity and superiority of B&B algorithm used in the conflict detection and scheduling optimization, the delay times vary from 50 s to 350 s. The objective function and bound values for the B&B strategy are demonstrated in Table4 and Figure 8. It can be seen that with the increase of the overall delay time, the B&B scheduling strategy will gradually demonstrate its superiority over the FCFS algorithm.Table 4
Objective function and bound values in case of different delays.
Delay time 50 100 150 200 250 300 350 FCFS 550 1600 2900 4350 5750 7150 8550 B&B 550 1600 2900 4150 5000 6600 8000 Bound value 1400 2800 4200 5600 7000 8400 9800Figure 8
Simulation results in case of different delays.


## 7. Conclusions

In this paper, the framework of conflict detection and scheduling optimization is proposed under the mechanism of MPC. Centering on the framework, conflict detection approaches and resolution strategies are outlined, a prediction model is established with conflict resolution, and the optimization model and algorithm are developed to unify the conflict resolution and scheduling optimization in the prediction horizon. A numerical experiment is carried out to justify the effectiveness of the proposed framework. The simulation results demonstrate that the proposed framework has a favorable performance.



---

*Source: 3473175-2018-04-08.xml*