# A Fast Approach for Reoptimization of Railway Train Platforming in Case of Train Delays

Authors: Yongxiang Zhang; Qingwei Zhong; Yong Yin; Xu Yan; Qiyuan Peng
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

Train platforming is critical for ensuring the safety and efficiency of train operations within the stations, especially when unexpected train delays occur. This paper studies the problem of reoptimization of train platforming in case of train delays, where the train station is modeled using the discretization of the platform track time-space resources. To solve the reoptimization problem, we propose a mixed integer linear programming (MILP) model, which minimizes the weighted sum of total train delays and the platform track assignment costs, subject to constraints defined by operational requirements. Moreover, we design an efficient heuristic algorithm to solve the MILP model such that it can speed up the reoptimization process with good solution precision. Furthermore, a real-world case is taken as an example to show the efficiency and effectiveness of the proposed model and algorithm. The computational results show that the MILP model established in this paper can describe the reoptimization of train platforming accurately, and it can be solved quickly by the proposed heuristic algorithm. In addition, the model and algorithm developed in this paper can provide an effective computer-aided decision-making tool for the train dispatchers in case of train delays.


---

## Body

## 1. Introduction

Railroad transportation plays an important role in providing economic and environment-friendly transport services for passengers and goods. In particular, transport demand of railroad transportation is increasing rapidly in some parts of regional markets. For instance, according to the statistical data of the National Bureau of Statistics of China, the volume of passenger and freight traffic of China railway in 2018 has increased by 9.44% and 9.15%, compared with the volume in 2017 [1]. Thus, more and more trains are required to be operated on the railway network with limited infrastructure capacity to satisfy the large demand. Therefore, the railway operators need to adopt advanced and reliable computer-aided decision systems to improve train operation efficiency. Moreover, the railway planning process includes the network design and line planning at the strategic level, the train timetabling, train platforming, rolling stock scheduling and crew scheduling at the tactical level, and the real-time traffic management at the operational level [2]. As a result, the core of the computer-aided decision systems is to develop effective optimization techniques for the different railway planning and operation stages. We refer the readers to Assad [3], Cordeau [4], and Lusby et al. [2] for excellent surveys on the related optimization methods. In general, train timetabling stage can determine the arrival and departure times of the trains at each of the visiting stations from an aggregate perspective [5–8]. Train operations at the stations, including the train routing on the arrival and departure routes and the train platform assignment decisions, are usually optimized by solving the train platforming problem [8]. Apart from the boarding and alighting of passengers as well as the loading and unloading of goods at the station platforms, many other complicated operation tasks can be performed at the stations, such as the train turn-around movement and the shunting work. Thus, it is of critical importance to develop efficient and effective optimization techniques to improve the train operation efficiency at the stations without causing any conflicts.Due to the complex layout of large railway stations and the associated dense train traffic, it is usually a challenging task for the train dispatchers to make a high-quality train operation plan within a station in a short period. Kroon et al. [9] have already proven that the train platforming problem is an NP-complete combinational optimization problem. As a result, many researchers have developed sophisticated and efficient models and algorithms to deal with the train platforming problem, such as the node packing model and the branch-and-cut algorithm in Zwaneveld et al. [10, 11] and the set packing model and the branch-and-price algorithm in Lusby et al. [12, 13]. In practice, however, trains may suffer from all kinds of disturbances and disruptions, such as bad weather, equipment failure, and management factors [14]. When train delays occur, the scheduled train timetable needs to be rescheduled in real time, and thus the train operations within the stations need to be reoptimized quickly to prevent any potential conflicts [15–18]. However, with regard to the train platforming problem, two managerial aspects lack in-depth study. First, most of the researchers study the train platforming problem without considering train delays, and thus they do not consider the situation where it could be impossible to make a feasible train operation plan at the stations with the given train timetable. Second, in order to generate a disposition timetable during the train rescheduling process as soon as possible, the detailed train operations at the stations are neglected, and the aggregate station capacity is adopted instead [17, 18].In this study, we aim to bridge the research gaps lying in the train platforming and train rescheduling problems. More specifically, we reoptimize the train platforming problem in case of train delays and generate a new train operation plan within the station in real time. Our solution is to develop a mixed integer linear programming (MILP) model, where the train station is modeled using the discretized platform track time-space resources, and to propose an efficient heuristic algorithm. The goal of the proposed model and algorithm is to simultaneously minimize the deviation from the train timetable and the total train operating costs, realizing the coherence between train operations and the station management. The theoretical and practical contributions of this study mainly include the following four aspects:(1)
The train arrival and departure times and the train platform assignment are optimized simultaneously so that the negative influence of train delays can be minimized.(2)
The novel modeling method based on the discretized platform track time-space resources can describe the train conflicts accurately, where the complex binary train sequencing variables in the big-M modeling framework can be avoided.(3)
An efficient heuristic algorithm is designed to quickly obtain the near-optimal solutions for the real-time reoptimization of train platforming.(4)
A set of real-life experiments is performed to show the efficiency and effectiveness of the proposed model and algorithm.The rest of this paper is structured as follows. Section2 provides a comprehensive literature review on the optimization and reoptimization of train platforming problems. The method on how to describe the discretized platform track time-space resources is introduced in Section 3. In Section 4, we propose a new MILP model based on the discretized platform track time-space resources, as well as some valid equalities to strengthen the resulting MILP model. Section 5 presents the detailed algorithmic steps of a heuristic algorithm, i.e., the genetic and simulated annealing hybrid algorithm, for solving the reoptimization problem in a real-time manner. The efficiency and effectiveness of the proposed methods are verified through a set of real-life experiments in Section 6. Section 7 gives the concluding remarks and possible further research directions.


## 2. Literature Review

Train platforming problem is a key optimization stage in the railway hierarchical planning process, and it has attracted the attention of many researchers around the world [2]. Given the information of train arrival and departure times and the train running directions obtained at the train timetabling stage, the train dispatchers need to decide how to schedule the trains at the stations to avoid the train delays caused by the cross interference between train operations. The complexity of the train platforming problem grows quickly as the number of trains increases and the station layout becomes more and more complicated. Therefore, a lot of excellent works have been done regarding the train platforming problem, such as Carey [19], Zwaneveld et al. [10], Lusby et al. [12], Chakroborty and Vikram [20], Caprara et al. [21], and Kang et al. [22]. We next review these works mainly from two aspects, i.e., the train platforming problem at the tactical level and the train platforming problem considering the negative impact of train delays.The studies on the train platforming problem at the tactical level were initially focused on scheduling the train movements at the stations efficiently and economically with the fixed or slightly relaxed train arrival and departure times. Zwaneveld et al. [10] developed the first node packing model for the train platforming problem, and the station routes were classified as the inbound route, outbound route, and complete. In addition, small deviations from the planned train arrival and departure times were considered to increase the possibility of finding a feasible solution, and an improved branch-and-cut algorithm was designed to find the optimal solutions with the goal of maximizing the number of trains routed through the station. Kroon et al. [9] proved that the node packing model in Zwaneveld et al. [10] was NP-complete once each train had more than three routing possibilities. Based on the work in Zwaneveld et al. [10], Zwaneveld et al. [11] further proposed a weighted node packing model for the train platforming problem, where several hierarchical objectives can be considered with the unified weighted sum form. However, the node packing model has its own deficiencies to be put into practice. For instance, all of the conflicting train movements need to be identified in advance in the node packing model, and it usually results in a large-scale optimization model. As a result, Lusby et al. [12] built a set packing model of the train platforming problem, and a branch-and-price algorithm was designed such that the feasible train routes can be dynamically generated. Besides, the train platforming problem can be also reformulated as a graph colouring problem, where the number of colours is determined by the available tracks in the stations [23]. An integer programming model that was equivalent to graph colouring problem in Cardillo and Mione [23] was developed by Billionnet [24]. Caprara et al. [21] also allowed a slight relaxation on the ideal arrival and departure times of the trains at the platforms, and they presented a 0-1 quadratic programming model to solve the train platforming problem. In particular, the quadratic term in the objective function was designed to consider the soft incompatibility costs between train paths. Sels et al. [25] developed a new MILP model to schedule the trains in the current and future train set, and penalty costs were considered in the objective when a train was cancelled or assigned to a different platform.Apart from the exact solution methods, some researchers also developed heuristic algorithms for the train platforming problem [26–29]. Carey and Carville [26] introduced a sequential construction heuristic algorithm for the train platforming problem at a single station, which was designed according to the train dispatchers’ manual methods. In addition, trains can be delayed in the planning process to generate a feasible solution, and the assignment of trains to the undesired platforms was penalized. Carey and Crawford [27] further extended the work in Carey and Carville [26] by considering the train scheduling and platforming problems at multiple stations, where those stations were connected by several one-way lines. Similarly, trains can be also delayed when they were scheduled from one station to the corresponding next station. Kang et al. [28] proposed a simulated annealing heuristic algorithm with the goal of achieving the balanced occupation of station turnouts while minimizing the total occupation times of the station turnouts. Wu et al. [29] developed a mean-variance optimization model for the train platforming problem based on Markowitz’s portfolio theory, which was aimed to minimize the total occupation time costs of groups of turnouts. Moreover, an efficient simulated annealing heuristic algorithm was designed to solve the resulting mixed integer nonlinear programming (MINLP) model.Some researchers also tried to integrate the two stages of train timetabling and train platforming problems to further increase the railway network capacity utilization. Carey [19] proposed an integrated optimization model to simultaneously optimize the lines, platforms, and routes of the trains in a railway network, and an improved sequential searching method was adopted to solve the resulting model. In addition, the arrival and departure headways between two trains were enforced to guarantee the train running safety. Dorfman and Medanic [30] proposed a discrete event model to schedule the trains in the railway network, where the train routes were assumed to be fixed for simplicity. D’ariano et al. [31] formulated the train scheduling problem through the alternative graph modeling approach, and an efficient branch-and-bound algorithm was designed to solve the MILP model. Rodriguez [32] proposed a combined constraint programming and simulation method for scheduling trains in the junctions, where the constraint programming model representing the signalling system behaviour and the simulation model can reflect the train and driver behaviour. More recently, D’Ariano et al. [33] and Zhang et al. [8] studied the integrated train timetabling and maintenance task scheduling problems at the microscopic level, and efficient heuristic algorithms based on the commercial solvers were developed accordingly.Some works were also performed on the optimization of a delay resistant train platforming plan and the real-time reoptimization of train platforming problem in case of unexpected train delays. Herrman [34] studied the stable train routing problem, where the goal was to keep the train schedule to be conflict-free as much as possible in case of perturbations. In addition, a local search heuristic approach was designed to solve the train schedule stabilization problem. Bešinović and Goverde [35] proposed a max-plus automata model for the station capacity assessment and a delay propagation model for the robustness evaluation of the train platforming plan. Based on these two models, the objectives of minimization of capacity occupation and maximization of robustness were then achieved with a heuristic approach. Kang et al. [22] introduced the concept of stochastic schedule with uncertain train arrival and departure times, and a simulated annealing algorithm was developed to solve the corresponding train platforming problem. D’Ariano et al. [36] designed a rolling horizon approach for the real-time train rescheduling problem, and the alternative graph formulation was adopted for solving the smaller subproblem in each rolling period. Chakroborty and Vikram [20] developed a MILP model for optimally allocating trains to the platform tracks, where the accurate train arrival times can only be available shortly before the train arrives at the station such that trains could be reassigned to different platforms. Besides, the headway between two trains was also considered while delaying the train arrival and departure times. Lusby et al. [13] proposed a set packing model for rescheduling the trains in the junctions in case of disruptions. In particular, a branch-and-price algorithm was introduced to solve the set packing model, and the objective was to minimize the weighted deviations from the trains’ scheduled arrival times. Liu et al. [37] developed a MINLP model to reallocate the tracks of trains at the stations in a real-time manner, where the goal was to minimize average use time of groups of turnouts without changing the planned train times. Moreover, a genetic simulated annealing algorithm was also designed to solve the MINLP model efficiently.Table1 summarizes the modeling approaches, objectives, solution methods, and other characteristics of relevant publications on the optimization and reoptimization of train platforming problems, and major highlights can be drawn from Table 1. First, most of the studies focus on the train platforming problem at the tactical level, and the scheduled train arrival and departure times at the stations are usually assumed to be fixed. Therefore, the optimization objectives of those studies are generally minimizing the total costs or maximizing the total benefits. Second, exact algorithms account for the majority of the solution methods to solve the optimization or reoptimization of the train platforming problems. Therefore, efficient and flexible heuristic algorithms are required, especially for the real-time reoptimization of the train platforming problem. Third, among the studies that consider the negative influence of train delays, only one research by Chakroborty and Vikram [20] simultaneously incorporates the factors of train delay, reassignment of platform, and deviations from scheduled train arrival and departure times. However, they adopt a commercial solver to deal with the MILP model. In this study, we develop a new MILP model for the reoptimization of the train platforming problem based on the discretized time-space resources, and we also design an efficient heuristic algorithm to guarantee the achievement of real-time reoptimization.Table 1
Summary of relevant publications on the optimization and reoptimization of the train platforming problems.
PublicationModeling approachObjectiveSolution methodTrain delayReassignment of platformDeviations from scheduled train timesLargest instance solvedComputation times (in seconds) of the largest instanceZwaneveld et al. [10]BILPMax the number of routed trainsBranch-and-cut√A railway station with 17 platforms and 27 trains85Cardillo and Mione [23]GCFeasibilityIterative heuristic algorithmA railway station with 16 tracks and 242 trains0.67Billionnet [24]BILPFeasibilityOptimization softwareA railway station with 14 tracks and 200 trains1.64Carey and Carville [26]MILPMin the costs of deviations from preferred times, platforms, and linesIterative sequential searching method√√A railway station with 29 subproblems and 491 trains—Rodriguez [32]CPMin train delaysTree search√√A 15.18 km long railway junction with 24 trains54.76Lusby et al. [12]BILPMax total benefitsBranch-and-priceA railway junction with 64 block sections and 45 trains26.4Caprara et al. [21]BQPMin total costsBranch-and-cut-and-priceA railway station with 14 platforms and 237 trains350Sels et al. [25]MILPMin total penaltiesCommercial solvers√A railway station with 14 platforms and 160 trains3.0Zhang et al. [8]MILPMin total train journey times and maintenance tardiness costsIterative heuristic algorithmA railway network with 27 stations, 55 segments, and 58 trains7200Liu et al. [37]MINLPMin average use time of groups of turnoutsGenetic simulated annealing algorithm√A railway station with 11 tracks and 30 trains1800Kang et al. [22]MILPMin total occupation times and balanced track occupationSimulated annealing√A railway station with 11 tracks and 28 trains726Chakroborty and Vikram [20]MILPMin total costsCommercial solver√√√A railway station with 9 platforms and 110 trains600Lusby et al. [13]BILPMin total deviationsBranch-and-price√√A railway junction with 524 track sections and 66 trains151.55This paperMILPMin total costsGenetic and simulated annealing hybrid algorithm√√√A railway station with 11 platforms and 70 trains32.92Note. BILP represents 0-1 integer linear programming; GC represents graph colouring; MILP represents mixed integer linear programming; CP represents constraint programming; BQP represents 0-1 quadratic programming; “—” represents no specific information is available.


## 3. Analysis of Platform Track Time-Space Resources

LetT be the planning horizon; we handle the time resources as small time units of length Δτ. The number of time units is equal to T=T/Δτ in the entire planning horizon. In addition, the number of platform tracks in a station is denoted by I, i.e., the maximum spatial capacity. Hence, the platform track time-space resources of a station can be represented by a two-dimensional matrix R:(1)R=ri,t=r1,1r1,2...r1,|Tr2,1r2,2...r2,|T............rI,1rI,2...rI,T,where i and t are the indexes of the platform track and the time unit, respectively, and a binary variable ri,t in matrix R denotes the occupation and vacancy state of the platform track time-space resource i,t, where(2)ri,t=1,platform track time−space resourcei,tis used,0,othewise.Figure1 provides an illustrative example of the modeling method of platform track time-space resources. Suppose that 5 trains successively arrive at or depart from station N which has 6 platform tracks within the planning horizon of 60 min. The detailed schedules of train operations in both directions are given in Figures 1(b) and 1(c), and the time unit Δτ is set to 5 min. Platform track time-space resources and the corresponding matrix R of a feasible usage plan are described in Figures 2(a) and 2(b), respectively. The application requirements of the time-space resources modeling method for the reoptimization of train platforming problem can be formulated as follows:(1)
Inseparability. A train must occupy only one platform track and cannot occupy more than one platform track simultaneously.(2)
Exclusivity. One platform track can only store one train at any time unit to prevent the train conflicts.(3)
Continuity. A train operation on one platform track with the duration equal to Δt time units cannot be interrupted. If one train starts to use track i at time t, it continues to occupy the platform track i until t+Δt, i.e., ri,t=ri,t+1=ri,t+2=…=ri,t+Δt=1.Figure 1
Layout and train timetables of stationN: (a) layout of station N; (b) train diagram of station N in the downstream direction; (c) train diagram of station N in the upstream direction.
(a)(b)(c)Figure 2
Platform track time-space resource usage plan and time-space resource matrix: (a) usage of platform track time-space resources; (b) platform track time-space resource matrix.
(a)(b)


## 4. Mathematical Modeling for Reoptimization of Train Platforming

### 4.1. Modeling Assumptions

Without loss of generality, we make the following key modeling assumptions to facilitate the modeling process.(1)
When it is impossible to eliminate the conflicts through reassignment of platforms, the train arrival and departure times can only be delayed to resolve the conflicts.(2)
One minute is applied to discretize the platform track time-space resources, and smaller time units can be adopted if necessary.(3)
Trains are modeled as single objects moving in the railway station, and thus the influence of train lengths on the clearing times of the platform tracks is not considered.(4)
By enforcing the arrival and departure headways between two trains running in the same direction as well the safety time interval for platform track operation, it can be guaranteed that there are no conflicts between any two trains.(5)
All trains will pass through the railway station, and turn-around movements of the trains are not considered for simplicity.


### 4.2. Definitions of Sets, Parameters, and Variables

Sets, parameters, and variables of this study are defined in Table2. In particular, we assume that all parameter values related to time are multiples of the time unit Δτ.Table 2
Sets, parameters, and variables.
SymbolDefinitionSetsLSet of trains, indexed bylL1Set of delayed trains,L1⊆LISet of platform tracks, indexed byiIlSet of platform tracks that trainl can utilize, Il⊆ITSet of time intervals in the planning horizon, indexed bytParameterscl,iCost of assigning trainl to platform track iπl0-1 parameter is equal to 1 if trainl is running in the downstream direction; 0, otherwiseql,i0-1 parameter is equal to 1 if trainl was initially assigned to platform track i before a delay occurs; 0, otherwiseSThe time when the information of train delays is updatedtl,aScheduled arrival time of trainltl,dScheduled departure time of trainltl,a1Estimated arrival time of trainl when a delay occurstl,d1Estimated departure time of trainl when a delay occursΔlDwell time of trainlPlPriority of trainlDSafety time interval for platform track operationMTSum of the length of the planning horizonT and the safety time interval for platform track operation DΔmaxMaximum value of dwell times of all trainshaHeadway between two arrival trains running in the same directionhdHeadway between two departure trains running in the same directionαObjective function weighting factorMA sufficiently large numberVariableswl,i0-1 platform track assignment variable = 1 if trainl is assigned to platform track i; = 0 otherwiseel,k0-1 same platform track choice variable = 1 if trainl and train k choose the same platform track; = 0 otherwisexl,i,t0-1 platform track occupancy state variable = 1 if trainl occupies platform track i at moment t; = 0 otherwiseul,i,t0-1 platform track utilization state variable = 1 if trainl has not yet arrived at platform track i at moment t; = 0 otherwisevl,i,t0-1 platform track clearance state variable = 1 if trainl has left platform track i at moment t; = 0 otherwiseλl,k0-1 train arrival sequence variable = 1 if trainl arrives at the station before train k; = 0 otherwiseμl,k0-1 train departure sequence variable = 1 if trainl departs from the station before train k; = 0 otherwiseyl,aActual arrival time of trainl at the stationyl,dActual departure time of trainl at the station


### 4.3. Objective Function

The objective function in equation (3) contains the weighted sum of two parts of costs. The first part is the sum of train arrival and departure delays, considering the train priority Pl and the weighting factor α. The second part is the total platform track assignment costs. In particular, the more that train l is preferred for platform track i, the smaller is the corresponding platform track assignment cost cl,i. Note that value of cl,i can be determined according to several influence factors, including the initial platform track assignment plan, the convenience of passenger boarding and alighting, and other special requirements for train operations. Therefore, the smaller the value of cl,i is, the more the train l prefers the platform track i.(3)minz=α∑l∈LPlyl,a−tl,a+yl,d−tl,d−D+∑l∈L∑i∈Ilwl,icl,i.


### 4.4. Constraints

#### 4.4.1. Relation between Platform Track State Variables

According to definitions of platform track state variablesxl,i,t, ul,i,t, and vl,i,t, constraint (4) expresses the relationship among those three platform track state variables. In particular, when both the variables ul,i,t and vl,i,t are equal to 0, it can be known that train l is occupying the platform track i at time t, i.e., xl,i,t=1. Figure 3 shows an illustrative example on how to calculate the value of xl,i,t according to the values of the variables ul,i,t and vl,i,t. More specifically, train l1 arrives at the platform track 5 in Figure 1 at time 5 and it leaves from the corresponding platform track at time 20. Therefore, Figures 3(a) and 3(b) present the values of the variables ul,i,t and vl,i,t for train l1 according to its actual arrival and departure times. In addition, according to constraint (4), the values of vl,i,t in Figure 3(c) can be easily obtained.(4)xl,i,t=1−ul,i,t+vl,i,t,∀l∈L,i∈I,t∈1,2,…,MT.Figure 3
An illustrative example showing the values of platform track state variablesul,i,t, vl,i,t, and xl,i,t: (a) values of the variable ul,i,t; (b) values of the variable vl,i,t; (c) values of the variable xl,i,t, and xl,i,t = 1−(ul,i,t + vl,i,t).
(a)(b)(c)


#### 4.4.2. Actual Train Arrival and Departure Times

Constraints (5) and (6) show that values of actual arrival time yl,a and actual departure time yl,d of train l can be inferred from the values of platform track utilization state variable ul,i,t and the platform track clearance state variable vl,i,t.(5)yl,a=MT−∑i∈I∑t=1MT1−ul,i,t,∀l∈L,(6)yl,d=MT−∑i∈I∑t=1MTvl,i,t,∀l∈L.


#### 4.4.3. Platform Track Assignment Constraint

Constraint (7) requires that each train l can only be assigned to one platform track, and the corresponding platform track has to be in the set Il. Furthermore, constraint (8) enforces that a train l cannot be assigned to forbidden platform tracks, i.e., tracks that are not in the set Il. Constraints (7)-(8) provide a flexible method to restrict the platform track choices of the trains.(7)∑i∈Ilwl,i=1,∀l∈L,(8)wl,i=0,∀l∈L,i∈I\Il.


#### 4.4.4. Platform Track Capacity Constraint

Constraint (9) ensures that any platform track i can only be occupied by at most one train at any time t, such that no conflicts can occur between any two trains that are assigned to the same platform track.(9)∑l∈Lxl,i,t≤1,∀i∈I,t∈1,2,…,MT.


#### 4.4.5. Continuous Train Operation on the Platform Track

Constraints (10)–(12) guarantee that train operations on the platform tracks should be performed continuously, by enforcing the relationship between the values of variables ul,i,t and vl,i,t. For instance, if wl,i=1 in constraint (10), which implies that train l is assigned to the platform track i, constraint (10) changes to ul,i,t≥ul,i,t+1. According to the definition of ul,i,t in Section 4.2, the condition ul,i,t≥ul,i,t+1 is obviously satisfied. On the other hand, if wl,i=0 in constraint (10), constraint (10) is no longer valid. Similarly, constraints (11) and (12) define the relationships between vl,i,t and vl,i,t+1 as well as between ul,i,t and ul,i,t+1.(10)ul,i,t≥ul,i,t+1+wl,i−1,∀l∈L,i∈I,t∈1,2,…,MT−1,(11)vl,i,t≤vl,i,t+1−wl,i+1,∀l∈L,i∈I,t∈1,2,…,MT−1,(12)ul,i,t≤ul,i,t+1+wl,i,∀l∈L,i∈I,t∈1,2,…,MT−1.


#### 4.4.6. Safety Headway between Two Trains

Constraints (13)–(18) impose the required safety headway between two arrival or departure trains running in the same direction, and the train sequencing variables λl,k and μl,k as well as the platform track choice variables wl,i and el,k are also embedded in those constraints. Constraint (13) enforces the safety headway between two arrival trains in the same direction, and it is valid only if λl,k=1, i.e., train l arrives at the station before train k. When λl,k=1 in constraint (13), it can be shown that the safety headway between trains l and k depends on the value of the variable el,k. More specifically, if el,k=1, trains l and k are assigned to the same platform track, and they are separated by the safety time interval D. Otherwise, trains l and k are assigned to two different platform tracks, and they are separated by the arrival headway ha. Meanwhile, constraint (14) guarantees the safety headway between two departure trains in the same direction. Constraint (15) ensures that if both the variables wl,i and wk,i are equal to 1, the value of the variable el,k can be enforced to be 1. Furthermore, constraint (16) describes that the values of the two variables el,k and ek,l for two different trains l and k are equal. Besides, constraints (17) and (18) guarantee that only one of the train sequencing variables λl,k and λk,l or μl,k and μk,l between any two different trains is equal to 1.(13)yl,a−yk,a≥1−el,kha+el,kD−λl,kM,∀l,k∈L:l≠k,πl=πk,(14)yl,d−yk,d≥1−el,khd+el,kD−μl,kM,∀l,k∈L:l≠k,πl=πk,(15)el,k≥wl,i+wk,i−1,∀l,k∈L,i∈Il∩Ik:k>l,πl=πk,(16)el,k=ek,l,∀l,k∈L:k>l,πl=πk,(17)λl,k+λk,l=1,∀l,k∈L:k>l,πl=πk,(18)μl,k+μk,l=1,∀l,k∈L:k>l,πl=πk.


#### 4.4.7. Minimum Train Dwell Time Constraint

Constraint (19) enforces the minimum dwell time for each train l. In particular, the right-hand side of constraint (19) can only be valid when wl,i=1, i.e., train l is assigned to the platform track i. Note that the safety time interval for platform track operation D is also included in the right-hand side of the constraints so that the required safety time interval for trains assigned to the same platform track is imposed. In addition, the minimum dwell time Δl of a train l is a deterministic value.(19)∑t=1MTxl,i,t≥wl,iΔl+D,∀l∈L,i∈I.


#### 4.4.8. Actual Train Arrival Time and Departure Time Constraint

Constraints (20)–(22) specify that the actual arrival and departure times of the trains should be no less than the corresponding planned arrival and departure times, respectively. Note that safety time interval D is introduced into the right-hand sides of constraints (21)-(22), such that the safety time interval D for platform track operation is implicitly satisfied between the departure time yl,d of train l and the arrival time of any other trains that are assigned to the same platform track.(20)yl,a≥tl,a,∀l∈L,(21)yl,d≥tl,d+D,∀l∈L,(22)yl,d≥yl,a+Δl+D,∀l∈L.


#### 4.4.9. Domain of Variables

Constraints (23)–(25) define the domain of variables. Note that the variables xl,i,t, yl,a, and yl,d are intermediate variables to facilitate the model building process, and their values can be directly inferred from the variables ul,i,t and vl,i,t.(23)wl,i=0,1,∀l∈L,i∈I,(24)ul,i,t,vl,i,t=0,1,∀l∈L,i∈I,t∈1,2,…,MT,(25)el,k,λl,k,μl,k=0,1,∀l,k∈L:l≠k,πl=πk.In short, formulations (3)–(25) constitute the complete MILP model for the reoptimization of train platforming problem. Due to the complicated filter conditions for the ranges of constrains (13)–(18), we simply approximate the number of constraints (13)–(18) without considering those filter conditions. As a result, the upper bound on the number of constraints of the MILP model is equal to MTI2L+1+6L+L25+I+∑l∈LI−Il, which increases polynomial as the number of trains L, the number of platform tracks I, and the length of planning horizon T increase. Similarly, the upper bound on the number of variables is equal to L⋅I1+MT+L2.


### 4.5. Valid Inequalities

Valid equalities are additional constraints that have been implicitly satisfied according to other necessary model constraints (4)–(25). However, they can be applied to strengthen the model formulation [17, 38]. Constraints (26)–(29) define the four valid inequalities that are related to the variables ul,i,t, vl,i,t, xl,i,t, and wl,i. Note that the valid inequalities are only implemented in a commercial solver to speed up the solving process of the commercial solver.(26)ul,i,t≥1−wl,i,∀l∈L,i∈I,t∈1,2,…,MT,(27)vl,i,t≤wl,i,∀l∈L,i∈I,t∈1,2,…,MT,(28)xl,i,t≤wl,i,∀l∈L,i∈I,t∈1,2,…,MT,(29)xl,i,t=0,∀l∈L,i∈I,t∈1,2,…,tl,a−1∨t∈tl,d+Δmax+D+1,…,MT.The principles of building valid inequalities (26)–(29) are similar. For instance, in valid inequality (26), if train l occupies platform track i, then valid inequality (26) is equivalent to ul,i,t≥0 which turns out to be ineffective. However, if train l does not occupy the platform track i, then valid inequality (26) is equivalent to ul,i,t≥1 which implies ul,i,t=1. Valid inequality (29) considers when the station capacity is not sufficient and two conflicting trains need to be assigned to the same platform track, then one of the two trains with lower priority can be delayed at most by Δmax, which means xl,i,t can be constrained to 0 when t∈1,2,…,tl,a−1 or t∈tl,d+Δmax+D+1,…,MT. Overall, a total of 4MTL⋅I−∑l∈LItl,d+Δmax+D−tl,a+1 additional constraints are added into the model after introducing the valid inequalities (26)–(29).


## 4.1. Modeling Assumptions

Without loss of generality, we make the following key modeling assumptions to facilitate the modeling process.(1)
When it is impossible to eliminate the conflicts through reassignment of platforms, the train arrival and departure times can only be delayed to resolve the conflicts.(2)
One minute is applied to discretize the platform track time-space resources, and smaller time units can be adopted if necessary.(3)
Trains are modeled as single objects moving in the railway station, and thus the influence of train lengths on the clearing times of the platform tracks is not considered.(4)
By enforcing the arrival and departure headways between two trains running in the same direction as well the safety time interval for platform track operation, it can be guaranteed that there are no conflicts between any two trains.(5)
All trains will pass through the railway station, and turn-around movements of the trains are not considered for simplicity.


## 4.2. Definitions of Sets, Parameters, and Variables

Sets, parameters, and variables of this study are defined in Table2. In particular, we assume that all parameter values related to time are multiples of the time unit Δτ.Table 2
Sets, parameters, and variables.
SymbolDefinitionSetsLSet of trains, indexed bylL1Set of delayed trains,L1⊆LISet of platform tracks, indexed byiIlSet of platform tracks that trainl can utilize, Il⊆ITSet of time intervals in the planning horizon, indexed bytParameterscl,iCost of assigning trainl to platform track iπl0-1 parameter is equal to 1 if trainl is running in the downstream direction; 0, otherwiseql,i0-1 parameter is equal to 1 if trainl was initially assigned to platform track i before a delay occurs; 0, otherwiseSThe time when the information of train delays is updatedtl,aScheduled arrival time of trainltl,dScheduled departure time of trainltl,a1Estimated arrival time of trainl when a delay occurstl,d1Estimated departure time of trainl when a delay occursΔlDwell time of trainlPlPriority of trainlDSafety time interval for platform track operationMTSum of the length of the planning horizonT and the safety time interval for platform track operation DΔmaxMaximum value of dwell times of all trainshaHeadway between two arrival trains running in the same directionhdHeadway between two departure trains running in the same directionαObjective function weighting factorMA sufficiently large numberVariableswl,i0-1 platform track assignment variable = 1 if trainl is assigned to platform track i; = 0 otherwiseel,k0-1 same platform track choice variable = 1 if trainl and train k choose the same platform track; = 0 otherwisexl,i,t0-1 platform track occupancy state variable = 1 if trainl occupies platform track i at moment t; = 0 otherwiseul,i,t0-1 platform track utilization state variable = 1 if trainl has not yet arrived at platform track i at moment t; = 0 otherwisevl,i,t0-1 platform track clearance state variable = 1 if trainl has left platform track i at moment t; = 0 otherwiseλl,k0-1 train arrival sequence variable = 1 if trainl arrives at the station before train k; = 0 otherwiseμl,k0-1 train departure sequence variable = 1 if trainl departs from the station before train k; = 0 otherwiseyl,aActual arrival time of trainl at the stationyl,dActual departure time of trainl at the station


## 4.3. Objective Function

The objective function in equation (3) contains the weighted sum of two parts of costs. The first part is the sum of train arrival and departure delays, considering the train priority Pl and the weighting factor α. The second part is the total platform track assignment costs. In particular, the more that train l is preferred for platform track i, the smaller is the corresponding platform track assignment cost cl,i. Note that value of cl,i can be determined according to several influence factors, including the initial platform track assignment plan, the convenience of passenger boarding and alighting, and other special requirements for train operations. Therefore, the smaller the value of cl,i is, the more the train l prefers the platform track i.(3)minz=α∑l∈LPlyl,a−tl,a+yl,d−tl,d−D+∑l∈L∑i∈Ilwl,icl,i.


## 4.4. Constraints

### 4.4.1. Relation between Platform Track State Variables

According to definitions of platform track state variablesxl,i,t, ul,i,t, and vl,i,t, constraint (4) expresses the relationship among those three platform track state variables. In particular, when both the variables ul,i,t and vl,i,t are equal to 0, it can be known that train l is occupying the platform track i at time t, i.e., xl,i,t=1. Figure 3 shows an illustrative example on how to calculate the value of xl,i,t according to the values of the variables ul,i,t and vl,i,t. More specifically, train l1 arrives at the platform track 5 in Figure 1 at time 5 and it leaves from the corresponding platform track at time 20. Therefore, Figures 3(a) and 3(b) present the values of the variables ul,i,t and vl,i,t for train l1 according to its actual arrival and departure times. In addition, according to constraint (4), the values of vl,i,t in Figure 3(c) can be easily obtained.(4)xl,i,t=1−ul,i,t+vl,i,t,∀l∈L,i∈I,t∈1,2,…,MT.Figure 3
An illustrative example showing the values of platform track state variablesul,i,t, vl,i,t, and xl,i,t: (a) values of the variable ul,i,t; (b) values of the variable vl,i,t; (c) values of the variable xl,i,t, and xl,i,t = 1−(ul,i,t + vl,i,t).
(a)(b)(c)


### 4.4.2. Actual Train Arrival and Departure Times

Constraints (5) and (6) show that values of actual arrival time yl,a and actual departure time yl,d of train l can be inferred from the values of platform track utilization state variable ul,i,t and the platform track clearance state variable vl,i,t.(5)yl,a=MT−∑i∈I∑t=1MT1−ul,i,t,∀l∈L,(6)yl,d=MT−∑i∈I∑t=1MTvl,i,t,∀l∈L.


### 4.4.3. Platform Track Assignment Constraint

Constraint (7) requires that each train l can only be assigned to one platform track, and the corresponding platform track has to be in the set Il. Furthermore, constraint (8) enforces that a train l cannot be assigned to forbidden platform tracks, i.e., tracks that are not in the set Il. Constraints (7)-(8) provide a flexible method to restrict the platform track choices of the trains.(7)∑i∈Ilwl,i=1,∀l∈L,(8)wl,i=0,∀l∈L,i∈I\Il.


### 4.4.4. Platform Track Capacity Constraint

Constraint (9) ensures that any platform track i can only be occupied by at most one train at any time t, such that no conflicts can occur between any two trains that are assigned to the same platform track.(9)∑l∈Lxl,i,t≤1,∀i∈I,t∈1,2,…,MT.


### 4.4.5. Continuous Train Operation on the Platform Track

Constraints (10)–(12) guarantee that train operations on the platform tracks should be performed continuously, by enforcing the relationship between the values of variables ul,i,t and vl,i,t. For instance, if wl,i=1 in constraint (10), which implies that train l is assigned to the platform track i, constraint (10) changes to ul,i,t≥ul,i,t+1. According to the definition of ul,i,t in Section 4.2, the condition ul,i,t≥ul,i,t+1 is obviously satisfied. On the other hand, if wl,i=0 in constraint (10), constraint (10) is no longer valid. Similarly, constraints (11) and (12) define the relationships between vl,i,t and vl,i,t+1 as well as between ul,i,t and ul,i,t+1.(10)ul,i,t≥ul,i,t+1+wl,i−1,∀l∈L,i∈I,t∈1,2,…,MT−1,(11)vl,i,t≤vl,i,t+1−wl,i+1,∀l∈L,i∈I,t∈1,2,…,MT−1,(12)ul,i,t≤ul,i,t+1+wl,i,∀l∈L,i∈I,t∈1,2,…,MT−1.


### 4.4.6. Safety Headway between Two Trains

Constraints (13)–(18) impose the required safety headway between two arrival or departure trains running in the same direction, and the train sequencing variables λl,k and μl,k as well as the platform track choice variables wl,i and el,k are also embedded in those constraints. Constraint (13) enforces the safety headway between two arrival trains in the same direction, and it is valid only if λl,k=1, i.e., train l arrives at the station before train k. When λl,k=1 in constraint (13), it can be shown that the safety headway between trains l and k depends on the value of the variable el,k. More specifically, if el,k=1, trains l and k are assigned to the same platform track, and they are separated by the safety time interval D. Otherwise, trains l and k are assigned to two different platform tracks, and they are separated by the arrival headway ha. Meanwhile, constraint (14) guarantees the safety headway between two departure trains in the same direction. Constraint (15) ensures that if both the variables wl,i and wk,i are equal to 1, the value of the variable el,k can be enforced to be 1. Furthermore, constraint (16) describes that the values of the two variables el,k and ek,l for two different trains l and k are equal. Besides, constraints (17) and (18) guarantee that only one of the train sequencing variables λl,k and λk,l or μl,k and μk,l between any two different trains is equal to 1.(13)yl,a−yk,a≥1−el,kha+el,kD−λl,kM,∀l,k∈L:l≠k,πl=πk,(14)yl,d−yk,d≥1−el,khd+el,kD−μl,kM,∀l,k∈L:l≠k,πl=πk,(15)el,k≥wl,i+wk,i−1,∀l,k∈L,i∈Il∩Ik:k>l,πl=πk,(16)el,k=ek,l,∀l,k∈L:k>l,πl=πk,(17)λl,k+λk,l=1,∀l,k∈L:k>l,πl=πk,(18)μl,k+μk,l=1,∀l,k∈L:k>l,πl=πk.


### 4.4.7. Minimum Train Dwell Time Constraint

Constraint (19) enforces the minimum dwell time for each train l. In particular, the right-hand side of constraint (19) can only be valid when wl,i=1, i.e., train l is assigned to the platform track i. Note that the safety time interval for platform track operation D is also included in the right-hand side of the constraints so that the required safety time interval for trains assigned to the same platform track is imposed. In addition, the minimum dwell time Δl of a train l is a deterministic value.(19)∑t=1MTxl,i,t≥wl,iΔl+D,∀l∈L,i∈I.


### 4.4.8. Actual Train Arrival Time and Departure Time Constraint

Constraints (20)–(22) specify that the actual arrival and departure times of the trains should be no less than the corresponding planned arrival and departure times, respectively. Note that safety time interval D is introduced into the right-hand sides of constraints (21)-(22), such that the safety time interval D for platform track operation is implicitly satisfied between the departure time yl,d of train l and the arrival time of any other trains that are assigned to the same platform track.(20)yl,a≥tl,a,∀l∈L,(21)yl,d≥tl,d+D,∀l∈L,(22)yl,d≥yl,a+Δl+D,∀l∈L.


### 4.4.9. Domain of Variables

Constraints (23)–(25) define the domain of variables. Note that the variables xl,i,t, yl,a, and yl,d are intermediate variables to facilitate the model building process, and their values can be directly inferred from the variables ul,i,t and vl,i,t.(23)wl,i=0,1,∀l∈L,i∈I,(24)ul,i,t,vl,i,t=0,1,∀l∈L,i∈I,t∈1,2,…,MT,(25)el,k,λl,k,μl,k=0,1,∀l,k∈L:l≠k,πl=πk.In short, formulations (3)–(25) constitute the complete MILP model for the reoptimization of train platforming problem. Due to the complicated filter conditions for the ranges of constrains (13)–(18), we simply approximate the number of constraints (13)–(18) without considering those filter conditions. As a result, the upper bound on the number of constraints of the MILP model is equal to MTI2L+1+6L+L25+I+∑l∈LI−Il, which increases polynomial as the number of trains L, the number of platform tracks I, and the length of planning horizon T increase. Similarly, the upper bound on the number of variables is equal to L⋅I1+MT+L2.


## 4.4.1. Relation between Platform Track State Variables

According to definitions of platform track state variablesxl,i,t, ul,i,t, and vl,i,t, constraint (4) expresses the relationship among those three platform track state variables. In particular, when both the variables ul,i,t and vl,i,t are equal to 0, it can be known that train l is occupying the platform track i at time t, i.e., xl,i,t=1. Figure 3 shows an illustrative example on how to calculate the value of xl,i,t according to the values of the variables ul,i,t and vl,i,t. More specifically, train l1 arrives at the platform track 5 in Figure 1 at time 5 and it leaves from the corresponding platform track at time 20. Therefore, Figures 3(a) and 3(b) present the values of the variables ul,i,t and vl,i,t for train l1 according to its actual arrival and departure times. In addition, according to constraint (4), the values of vl,i,t in Figure 3(c) can be easily obtained.(4)xl,i,t=1−ul,i,t+vl,i,t,∀l∈L,i∈I,t∈1,2,…,MT.Figure 3
An illustrative example showing the values of platform track state variablesul,i,t, vl,i,t, and xl,i,t: (a) values of the variable ul,i,t; (b) values of the variable vl,i,t; (c) values of the variable xl,i,t, and xl,i,t = 1−(ul,i,t + vl,i,t).
(a)(b)(c)


## 4.4.2. Actual Train Arrival and Departure Times

Constraints (5) and (6) show that values of actual arrival time yl,a and actual departure time yl,d of train l can be inferred from the values of platform track utilization state variable ul,i,t and the platform track clearance state variable vl,i,t.(5)yl,a=MT−∑i∈I∑t=1MT1−ul,i,t,∀l∈L,(6)yl,d=MT−∑i∈I∑t=1MTvl,i,t,∀l∈L.


## 4.4.3. Platform Track Assignment Constraint

Constraint (7) requires that each train l can only be assigned to one platform track, and the corresponding platform track has to be in the set Il. Furthermore, constraint (8) enforces that a train l cannot be assigned to forbidden platform tracks, i.e., tracks that are not in the set Il. Constraints (7)-(8) provide a flexible method to restrict the platform track choices of the trains.(7)∑i∈Ilwl,i=1,∀l∈L,(8)wl,i=0,∀l∈L,i∈I\Il.


## 4.4.4. Platform Track Capacity Constraint

Constraint (9) ensures that any platform track i can only be occupied by at most one train at any time t, such that no conflicts can occur between any two trains that are assigned to the same platform track.(9)∑l∈Lxl,i,t≤1,∀i∈I,t∈1,2,…,MT.


## 4.4.5. Continuous Train Operation on the Platform Track

Constraints (10)–(12) guarantee that train operations on the platform tracks should be performed continuously, by enforcing the relationship between the values of variables ul,i,t and vl,i,t. For instance, if wl,i=1 in constraint (10), which implies that train l is assigned to the platform track i, constraint (10) changes to ul,i,t≥ul,i,t+1. According to the definition of ul,i,t in Section 4.2, the condition ul,i,t≥ul,i,t+1 is obviously satisfied. On the other hand, if wl,i=0 in constraint (10), constraint (10) is no longer valid. Similarly, constraints (11) and (12) define the relationships between vl,i,t and vl,i,t+1 as well as between ul,i,t and ul,i,t+1.(10)ul,i,t≥ul,i,t+1+wl,i−1,∀l∈L,i∈I,t∈1,2,…,MT−1,(11)vl,i,t≤vl,i,t+1−wl,i+1,∀l∈L,i∈I,t∈1,2,…,MT−1,(12)ul,i,t≤ul,i,t+1+wl,i,∀l∈L,i∈I,t∈1,2,…,MT−1.


## 4.4.6. Safety Headway between Two Trains

Constraints (13)–(18) impose the required safety headway between two arrival or departure trains running in the same direction, and the train sequencing variables λl,k and μl,k as well as the platform track choice variables wl,i and el,k are also embedded in those constraints. Constraint (13) enforces the safety headway between two arrival trains in the same direction, and it is valid only if λl,k=1, i.e., train l arrives at the station before train k. When λl,k=1 in constraint (13), it can be shown that the safety headway between trains l and k depends on the value of the variable el,k. More specifically, if el,k=1, trains l and k are assigned to the same platform track, and they are separated by the safety time interval D. Otherwise, trains l and k are assigned to two different platform tracks, and they are separated by the arrival headway ha. Meanwhile, constraint (14) guarantees the safety headway between two departure trains in the same direction. Constraint (15) ensures that if both the variables wl,i and wk,i are equal to 1, the value of the variable el,k can be enforced to be 1. Furthermore, constraint (16) describes that the values of the two variables el,k and ek,l for two different trains l and k are equal. Besides, constraints (17) and (18) guarantee that only one of the train sequencing variables λl,k and λk,l or μl,k and μk,l between any two different trains is equal to 1.(13)yl,a−yk,a≥1−el,kha+el,kD−λl,kM,∀l,k∈L:l≠k,πl=πk,(14)yl,d−yk,d≥1−el,khd+el,kD−μl,kM,∀l,k∈L:l≠k,πl=πk,(15)el,k≥wl,i+wk,i−1,∀l,k∈L,i∈Il∩Ik:k>l,πl=πk,(16)el,k=ek,l,∀l,k∈L:k>l,πl=πk,(17)λl,k+λk,l=1,∀l,k∈L:k>l,πl=πk,(18)μl,k+μk,l=1,∀l,k∈L:k>l,πl=πk.


## 4.4.7. Minimum Train Dwell Time Constraint

Constraint (19) enforces the minimum dwell time for each train l. In particular, the right-hand side of constraint (19) can only be valid when wl,i=1, i.e., train l is assigned to the platform track i. Note that the safety time interval for platform track operation D is also included in the right-hand side of the constraints so that the required safety time interval for trains assigned to the same platform track is imposed. In addition, the minimum dwell time Δl of a train l is a deterministic value.(19)∑t=1MTxl,i,t≥wl,iΔl+D,∀l∈L,i∈I.


## 4.4.8. Actual Train Arrival Time and Departure Time Constraint

Constraints (20)–(22) specify that the actual arrival and departure times of the trains should be no less than the corresponding planned arrival and departure times, respectively. Note that safety time interval D is introduced into the right-hand sides of constraints (21)-(22), such that the safety time interval D for platform track operation is implicitly satisfied between the departure time yl,d of train l and the arrival time of any other trains that are assigned to the same platform track.(20)yl,a≥tl,a,∀l∈L,(21)yl,d≥tl,d+D,∀l∈L,(22)yl,d≥yl,a+Δl+D,∀l∈L.


## 4.4.9. Domain of Variables

Constraints (23)–(25) define the domain of variables. Note that the variables xl,i,t, yl,a, and yl,d are intermediate variables to facilitate the model building process, and their values can be directly inferred from the variables ul,i,t and vl,i,t.(23)wl,i=0,1,∀l∈L,i∈I,(24)ul,i,t,vl,i,t=0,1,∀l∈L,i∈I,t∈1,2,…,MT,(25)el,k,λl,k,μl,k=0,1,∀l,k∈L:l≠k,πl=πk.In short, formulations (3)–(25) constitute the complete MILP model for the reoptimization of train platforming problem. Due to the complicated filter conditions for the ranges of constrains (13)–(18), we simply approximate the number of constraints (13)–(18) without considering those filter conditions. As a result, the upper bound on the number of constraints of the MILP model is equal to MTI2L+1+6L+L25+I+∑l∈LI−Il, which increases polynomial as the number of trains L, the number of platform tracks I, and the length of planning horizon T increase. Similarly, the upper bound on the number of variables is equal to L⋅I1+MT+L2.


## 4.5. Valid Inequalities

Valid equalities are additional constraints that have been implicitly satisfied according to other necessary model constraints (4)–(25). However, they can be applied to strengthen the model formulation [17, 38]. Constraints (26)–(29) define the four valid inequalities that are related to the variables ul,i,t, vl,i,t, xl,i,t, and wl,i. Note that the valid inequalities are only implemented in a commercial solver to speed up the solving process of the commercial solver.(26)ul,i,t≥1−wl,i,∀l∈L,i∈I,t∈1,2,…,MT,(27)vl,i,t≤wl,i,∀l∈L,i∈I,t∈1,2,…,MT,(28)xl,i,t≤wl,i,∀l∈L,i∈I,t∈1,2,…,MT,(29)xl,i,t=0,∀l∈L,i∈I,t∈1,2,…,tl,a−1∨t∈tl,d+Δmax+D+1,…,MT.The principles of building valid inequalities (26)–(29) are similar. For instance, in valid inequality (26), if train l occupies platform track i, then valid inequality (26) is equivalent to ul,i,t≥0 which turns out to be ineffective. However, if train l does not occupy the platform track i, then valid inequality (26) is equivalent to ul,i,t≥1 which implies ul,i,t=1. Valid inequality (29) considers when the station capacity is not sufficient and two conflicting trains need to be assigned to the same platform track, then one of the two trains with lower priority can be delayed at most by Δmax, which means xl,i,t can be constrained to 0 when t∈1,2,…,tl,a−1 or t∈tl,d+Δmax+D+1,…,MT. Overall, a total of 4MTL⋅I−∑l∈LItl,d+Δmax+D−tl,a+1 additional constraints are added into the model after introducing the valid inequalities (26)–(29).


## 5. Genetic and Simulated Annealing Hybrid Algorithm

In order to recover the train operations as soon as possible in case of train delays, a genetic and simulated annealing hybrid algorithm (GSAHA) is designed to solve the reoptimization model efficiently and effectively [37, 39, 40]. In particular, the simulated annealing algorithm (SA) has good ability in jumping out of local optimal solutions, and its convergence performance is robust against the generated initial solutions. However, the convergence speed of SA is generally slow. On the other hand, the genetic algorithm (GA) is a parallel search algorithm that usually converges very fast, while GA is more likely to be trapped into local optimal solutions and it is not robust against the generated initial solutions. As a result, the GSAHA algorithm combines the advantages of GA and SA. Therefore, GSAHA is robust on the convergence performance while avoiding being trapped into the local optimal solutions [37, 40, 41]. Figure 4 demonstrates the solution framework of the GSAHA algorithm, including the section names corresponding to some key algorithmic steps. The implementation details for the components of GSAHA are illustrated as follows.Figure 4
Solution framework of the GSAHA algorithm.


### 5.1. Chromosome Representation

Figure5 shows the one-dimensional real-value encoding method that is used to represent chromosomes. Each chromosome denotes a platform track assignment plan. In particular, if the value of the lth gene is equal to i, the lth train is assigned to platform track i with its scheduled arrival and departure times. Furthermore, the length of each chromosome is equal to the number of trains L, and the genes of a chromosome are numbered in descending order according to the scheduled arrival times of trains. Moreover, the value range of each gene is located within the range 1,I, and thus there could be IL possible chromosomes in total.Figure 5
Illustration of the chromosome representation.


### 5.2. Generating Initial Population

Considering diversity and rationality of individuals in the initial population, the following strategies are proposed to generate the initial population.Step 1. Denote platform tracks whose numbers are smaller than the number of platform tracksI as the set I1.Step 2. Select [L/I−1] trains that have not been selected yet and assign those trains to one of the unassigned platform tracks in set I1.Step 3. Repeat Step 1 until all platform tracks in setI1 are assigned and assign the remaining L−[L/I−1]⋅I−1 trains to the last platform track numbered as I.Step 4. Repeat Step 2 and Step 3 until all individuals in the initial population are generated.


### 5.3. Obtaining Feasible Solutions

The chromosome designed in Section5.1 only assigns trains to the platform tracks, i.e., to determine the platform track spatial resources that each train occupies. However, it is still possible that two trains may conflict with each other on the occupation of platform track temporal resources due to the violation of safety headway requirements, including the safety time interval between two trains assigned to the same platform track D, headway between two arrival trains running in the same direction ha, and headway between two departure trains running in the same direction hd. Hence, a heuristic rule is designed to resolve the temporal conflicts according to the constraints defined in Section 4.5.Algorithm 1:A heuristic method to resolve the temporal conflicts between trains with given train order.
For each train i1≤i≤LFor each train j1≤j<iIf train i conflicts with train jFix the arrival and departure times of traini and record the weighted sum delay amount ϑi after resolving the conflicts of trains numbered before train i;Fix the arrival and departure times of trainj and record the weighted sum delay amount ϑj after resolving the conflicts of trains numbered before train i;Ifϑi≤ϑiAdopt the adjust method by fixing the arrival and departure times of traini;ElseAdopt the adjust method by fixing the arrival and departure times of trainj;End Ifϑi≤ϑiEnd If train i conflicts with train jEnd For each train j1≤j<iEnd For each train i1≤i≤LStep 5. Sort all trains in descending order by their scheduled or estimated arrival times and number them from 1 toL.Step 6. Use Algorithm1 to resolve the temporal conflicts between any two trains in the order given in Step 1. Note that Algorithm 1 will not lead to a deadlock between trains where trains can always be delayed to resolve the temporal conflicts.Step 7. Calculate the weighted sum of arrival and departure delays compared to the corresponding scheduled or estimated train arrival and departure times. This operation considers all trains in setL and the platform track assignment costs, and thus the value calculated during this step serves as the objective value of the chromosome.


### 5.4. Fitness Function

The fitness function in equation (30) is designed to evaluate each individual such that the algorithm can achieve a better convergence performance.(30)firk=exp−fi−fminrk,where rk represents the temperature at the kth generation, fi represents the objective value of the ith chromosome, fmin represents the minimal objective value at the kth generation, and firk represents fitness value of the ithchromosome when the temperature is rk. Fitness function in equation (30) is an important feature of the SA algorithm, and it has a good capacity to accelerate the convergence of the algorithm.


### 5.5. Temperature Decline Function

After determining the initial temperatureR, the temperature decline function in equation (31) is used to lower the temperature at each iteration.(31)rk=R⋅ηk,where rk represents the temperature at the kth generation and the constant η represents the temperature decline rate.


### 5.6. Genetic Operators

#### 5.6.1. Neighborhood Search

Neighborhood search operator is applied to every chromosome. For instance, neighborhood search operator modifies the value of one gene in chromosomei randomly to generate a new chromosome j, and the objective value fj of chromosome j is recalculated. Chromosome j is accepted or rejected to replace chromosome i according to the probability Pijrk in the following equation:(32)Pijrk=min1,exp−fj−firk.IfPijrk is greater than the random number δ1 generated within the range [0, 1), then chromosome i is replaced by chromosome j. Neighborhood search operator is an important feature of the SA algorithm and it can enlarge the search space with the probability of resulting in better solutions. Moreover, neighborhood search operator is one of the main operators that can increase population diversity when the algorithm is trapped into local optimal solutions.


#### 5.6.2. Selection

The roulette method is adopted to select parents according to the cumulative probability, as shown in the following equation:(33)Ci=∑k=1ifk∑k=1Nfk,where N represents the number of individuals in the population. A random number δ2 is generated within [0, 1); if δ2∈Ci,Cj, then chromosome j is chosen as a parent. The elitism strategy is used to reduce randomness of the algorithm. Additionally, individuals are restricted to be consecutively chosen as parents to avoid the situation when the algorithm is trapped into a local optimal solution too early.


#### 5.6.3. Crossover

Two individuals are chosen as parents each time and a random numberδ3 is generated within the range [0, 1). If δ3 is greater than or equal to the given crossover rate λc, the crossover operator is not used and the two parents are reserved as children directly. Otherwise, the 2-opt crossover operator is performed. Figure 6 shows an example of the crossover operator where both the number of trains (i.e., L) and the number of platform tracks (i.e., I) are equal to 6.Figure 6
Illustration of the crossover operator.


#### 5.6.4. Mutation

For each gene of a chromosome, a random numberδ4 is generated within the range [0, 1). If δ4 is smaller than the given mutation rate λm, then the mutation operator is applied, i.e., a different platform track is randomly assigned to the gene.


## 5.1. Chromosome Representation

Figure5 shows the one-dimensional real-value encoding method that is used to represent chromosomes. Each chromosome denotes a platform track assignment plan. In particular, if the value of the lth gene is equal to i, the lth train is assigned to platform track i with its scheduled arrival and departure times. Furthermore, the length of each chromosome is equal to the number of trains L, and the genes of a chromosome are numbered in descending order according to the scheduled arrival times of trains. Moreover, the value range of each gene is located within the range 1,I, and thus there could be IL possible chromosomes in total.Figure 5
Illustration of the chromosome representation.


## 5.2. Generating Initial Population

Considering diversity and rationality of individuals in the initial population, the following strategies are proposed to generate the initial population.Step 1. Denote platform tracks whose numbers are smaller than the number of platform tracksI as the set I1.Step 2. Select [L/I−1] trains that have not been selected yet and assign those trains to one of the unassigned platform tracks in set I1.Step 3. Repeat Step 1 until all platform tracks in setI1 are assigned and assign the remaining L−[L/I−1]⋅I−1 trains to the last platform track numbered as I.Step 4. Repeat Step 2 and Step 3 until all individuals in the initial population are generated.


## 5.3. Obtaining Feasible Solutions

The chromosome designed in Section5.1 only assigns trains to the platform tracks, i.e., to determine the platform track spatial resources that each train occupies. However, it is still possible that two trains may conflict with each other on the occupation of platform track temporal resources due to the violation of safety headway requirements, including the safety time interval between two trains assigned to the same platform track D, headway between two arrival trains running in the same direction ha, and headway between two departure trains running in the same direction hd. Hence, a heuristic rule is designed to resolve the temporal conflicts according to the constraints defined in Section 4.5.Algorithm 1:A heuristic method to resolve the temporal conflicts between trains with given train order.
For each train i1≤i≤LFor each train j1≤j<iIf train i conflicts with train jFix the arrival and departure times of traini and record the weighted sum delay amount ϑi after resolving the conflicts of trains numbered before train i;Fix the arrival and departure times of trainj and record the weighted sum delay amount ϑj after resolving the conflicts of trains numbered before train i;Ifϑi≤ϑiAdopt the adjust method by fixing the arrival and departure times of traini;ElseAdopt the adjust method by fixing the arrival and departure times of trainj;End Ifϑi≤ϑiEnd If train i conflicts with train jEnd For each train j1≤j<iEnd For each train i1≤i≤LStep 5. Sort all trains in descending order by their scheduled or estimated arrival times and number them from 1 toL.Step 6. Use Algorithm1 to resolve the temporal conflicts between any two trains in the order given in Step 1. Note that Algorithm 1 will not lead to a deadlock between trains where trains can always be delayed to resolve the temporal conflicts.Step 7. Calculate the weighted sum of arrival and departure delays compared to the corresponding scheduled or estimated train arrival and departure times. This operation considers all trains in setL and the platform track assignment costs, and thus the value calculated during this step serves as the objective value of the chromosome.


## 5.4. Fitness Function

The fitness function in equation (30) is designed to evaluate each individual such that the algorithm can achieve a better convergence performance.(30)firk=exp−fi−fminrk,where rk represents the temperature at the kth generation, fi represents the objective value of the ith chromosome, fmin represents the minimal objective value at the kth generation, and firk represents fitness value of the ithchromosome when the temperature is rk. Fitness function in equation (30) is an important feature of the SA algorithm, and it has a good capacity to accelerate the convergence of the algorithm.


## 5.5. Temperature Decline Function

After determining the initial temperatureR, the temperature decline function in equation (31) is used to lower the temperature at each iteration.(31)rk=R⋅ηk,where rk represents the temperature at the kth generation and the constant η represents the temperature decline rate.


## 5.6. Genetic Operators

### 5.6.1. Neighborhood Search

Neighborhood search operator is applied to every chromosome. For instance, neighborhood search operator modifies the value of one gene in chromosomei randomly to generate a new chromosome j, and the objective value fj of chromosome j is recalculated. Chromosome j is accepted or rejected to replace chromosome i according to the probability Pijrk in the following equation:(32)Pijrk=min1,exp−fj−firk.IfPijrk is greater than the random number δ1 generated within the range [0, 1), then chromosome i is replaced by chromosome j. Neighborhood search operator is an important feature of the SA algorithm and it can enlarge the search space with the probability of resulting in better solutions. Moreover, neighborhood search operator is one of the main operators that can increase population diversity when the algorithm is trapped into local optimal solutions.


### 5.6.2. Selection

The roulette method is adopted to select parents according to the cumulative probability, as shown in the following equation:(33)Ci=∑k=1ifk∑k=1Nfk,where N represents the number of individuals in the population. A random number δ2 is generated within [0, 1); if δ2∈Ci,Cj, then chromosome j is chosen as a parent. The elitism strategy is used to reduce randomness of the algorithm. Additionally, individuals are restricted to be consecutively chosen as parents to avoid the situation when the algorithm is trapped into a local optimal solution too early.


### 5.6.3. Crossover

Two individuals are chosen as parents each time and a random numberδ3 is generated within the range [0, 1). If δ3 is greater than or equal to the given crossover rate λc, the crossover operator is not used and the two parents are reserved as children directly. Otherwise, the 2-opt crossover operator is performed. Figure 6 shows an example of the crossover operator where both the number of trains (i.e., L) and the number of platform tracks (i.e., I) are equal to 6.Figure 6
Illustration of the crossover operator.


### 5.6.4. Mutation

For each gene of a chromosome, a random numberδ4 is generated within the range [0, 1). If δ4 is smaller than the given mutation rate λm, then the mutation operator is applied, i.e., a different platform track is randomly assigned to the gene.


## 5.6.1. Neighborhood Search

Neighborhood search operator is applied to every chromosome. For instance, neighborhood search operator modifies the value of one gene in chromosomei randomly to generate a new chromosome j, and the objective value fj of chromosome j is recalculated. Chromosome j is accepted or rejected to replace chromosome i according to the probability Pijrk in the following equation:(32)Pijrk=min1,exp−fj−firk.IfPijrk is greater than the random number δ1 generated within the range [0, 1), then chromosome i is replaced by chromosome j. Neighborhood search operator is an important feature of the SA algorithm and it can enlarge the search space with the probability of resulting in better solutions. Moreover, neighborhood search operator is one of the main operators that can increase population diversity when the algorithm is trapped into local optimal solutions.


## 5.6.2. Selection

The roulette method is adopted to select parents according to the cumulative probability, as shown in the following equation:(33)Ci=∑k=1ifk∑k=1Nfk,where N represents the number of individuals in the population. A random number δ2 is generated within [0, 1); if δ2∈Ci,Cj, then chromosome j is chosen as a parent. The elitism strategy is used to reduce randomness of the algorithm. Additionally, individuals are restricted to be consecutively chosen as parents to avoid the situation when the algorithm is trapped into a local optimal solution too early.


## 5.6.3. Crossover

Two individuals are chosen as parents each time and a random numberδ3 is generated within the range [0, 1). If δ3 is greater than or equal to the given crossover rate λc, the crossover operator is not used and the two parents are reserved as children directly. Otherwise, the 2-opt crossover operator is performed. Figure 6 shows an example of the crossover operator where both the number of trains (i.e., L) and the number of platform tracks (i.e., I) are equal to 6.Figure 6
Illustration of the crossover operator.


## 5.6.4. Mutation

For each gene of a chromosome, a random numberδ4 is generated within the range [0, 1). If δ4 is smaller than the given mutation rate λm, then the mutation operator is applied, i.e., a different platform track is randomly assigned to the gene.


## 6. Numerical Experiments

The proposed model is applied to a railway passenger station as shown in Figure7, with five platform tracks (I, 3, 5, 7, 9, 11) in the downstream direction and four platform tracks (II, 4, 6, 8, 10) in the upstream direction. The time unit Δτ is set to 1 min, which is practical for ensuring safe train operations at the stations [22, 25, 37]. Moreover, there are 70 downstream and upstream trains, which need to conduct the necessary operations from 16:00 to 22:00. The initial scheduled arrival and departure times of the 70 trains are available at a repository on the ResearchGate website (DOI: 10.13140/RG.2.2.18253.79849), and trains are assigned with priority values ranging from 1 to 3. The initial platform track assignment plan is listed in Table 3, and the corresponding initially scheduled train operation plan is illustrated in Figure 8. Additionally, the platform track assignment costs for the downstream and upstream trains are given in Tables 4 and 5, respectively. In particular, there is a penalty of 10,000 for trains that use the platform tracks in the opposite direction.Figure 7
Layout of the railway passenger station.Table 3
Initial platform tack assignment plan between 16:00 and 22:00.
Platform track numberOccupation trains11T9, T299T5, T19, T31, T41, T497T11, T21, T27, T33, T43, T47, T55, T63, T695T1, T7, T15, T25, T35, T39, T53, T61, T67, T733T3, T13, T17, T23, T37, T45, T51, T57, T59, T65, T71, T75III4T2, T8, T18, T22, T30, T34, T40, T42, T48, T54, T60, T646T4, T12, T16, T24, T32, T38, T44, T50, T56, T628T6, T14, T20, T28, T36, T46, T52, T5810T10, T26Figure 8
Initial platform track utilization scheme between 16:00 and 22:00.Table 4
Platform track assignment costs for downstream trains with different priorities.
Train directionTrain priorityPlatform track numberI357911Downstream160061224489623003612244832002481632Table 5
Platform track assignment costs for upstream trains with different priorities.
Train directionTrain priorityPlatform track numberII46810IIUpstream160061224486002300361224300320024816200The train delay information is available at the time of 18:38, and it is known that 6 downstream trains and 4 upstream trains are delayed, and the estimated arrival and departure times of those delayed trains are provided in Table6. Moreover, the 10 delayed trains in both directions are marked with the blue colour in Figure 8. Table 7 provides the parameter values used in the model. The maximum value of dwell times of all trains Δmax equals 43 min, and the length of the planning horizon T equals 360 min. The safety time interval on the platform track D equals 6 min, and the headway between two arrival trains ha and the headway between two departure trains hd in the same direction are both set to 5 min. The weighting factor α in the objective function is set to 200, which is determined after discussing with the train dispatchers, and the value of α can be adjusted flexibly according to the preferences of the train dispatchers. Note that the value of α can be flexibly adjusted by the train dispatchers according to their experiences. In addition, we believe that keeping trains on time with guaranteed train service quality is more important than assigning the trains to their preferred platform tracks, and thus the penalty parameters on train delays are relatively larger than the platform track occupancy costs. Moreover, when the values of input parameters are known, the initial values of the decision variables should be set in advance before running the GSAHA algorithm or commercial solvers. More specifically, ul,i,1 is set to 1 and vl,i,1 is to 0 for all trains l∈L and platform tracks i∈I, such that no trains have arrived at or left the platform track at the beginning of the planning horizon. Furthermore, the variables wl,i, yl,a, and yl,d are set to their initial values before the train delay occurs, i.e., wl,i=ql,i, yl,a=tl,a, and yl,d=tl,d for all trains l∈L and platform tracks i∈I with the condition of tl,a<S.Table 6
Estimated arrival and departure times for delayed trains.
TrainArrival delayExpected arrival timeExpected departure timeDwell timePriorityT3920187210231T4125197209123T4325203220173T4527211227161T4730240260203T5530266286203T3230202217153T3632227250233T383523524383T4440272283111Table 7
Input parameters of the model.
ParameterValueMaximum value of dwell times of all trainsΔmax43 minLength of the planning horizonT360 minSafety time interval for platform track operationD6 minSum of the length of the planning horizon and the safety time interval for platform track operationMT366 minHeadway between two arrival trainsha5 minHeadway between two departure trainshd5 minObjective function weighting factorα200Based on the initial scheduled arrival and departure times as well as the input data and parameters of 70 trains in Tables3–7, a total of 21 scenarios are generated with the number of trains ranging from 10 to 70, and 3 scenarios are generated for each fixed number of trains. For instance, three scenarios (10, 2, 0), (10, 2, 1), and (10, 2, 2) are generated when the number of trains is equal to 10. Specifically, the first number “10” in the triple (10, 2, 0) denotes the number of trains, the second number “2” in the triple (10, 2, 0) represents the number of delayed trains. Besides, the third number in a triple can take the values of 0, 1, and 2 corresponding to the three scenarios, so that the estimated arrival and departure times for delayed trains in Table 6 are randomly increased with values in the ranges of (0, 0), (−1, 1), and (−2, 2), respectively.The MILP models for the 21 scenarios in Section4 are solved by the commercial solver CPLEX 12.7.0 with (i.e., CPLEX-WV) and without (i.e., CPLEX-WOV) including the valid inequalities in Section 4.5. Furthermore, the maximum computation times of CPLEX-WV and CPLEX-WOV are both set to 3600 s. The GSAHA is implemented in C++ programming language. Moreover, the algorithmic parameters for GSAHA are set as follows. The number of individuals in the population N is 50, the maximum number of generations K is 300, the crossover rate λc is 0.98, the mutation rate λm is 0.1, the initial temperature R is 80,000°C, the temperature decline rate η is 0.9, and the temperature is increased to R1 = 40,000°C if the objective value of the best individual in the current generation remains unchanged for m = 5 iterations and n = 3 times of neighborhood search operations are performed each time. In addition, all of the models and algorithms are tested on a computer with Intel (R) Core (TM) i7-5600U 2.6 GHZ CPU and 12G RAM. Tables 8 and 9 list the detailed computation results of CPLEX-WOV, CPLEX-WV, and GSAHA for the 21 scenarios. More specifically, the columns “Obj 1 value (min)” and “Obj 2 value” in Table 8 represent the two components of objective values, i.e., the sum of train arrival and departure delays and total platform track assignment costs, respectively. In Table 9, the column “Obj value” denotes the overall objective values, the column “CPU time (s)” represents the computation times in sections, and the column “GAP with CPLEX-WV (%)” indicates the relative gap between the objective values of GSAHA and CPLEX-WV.Table 8
Two components of objective values of CPLEX-WOV, CPLEX-WV, and GSAHA under different scenarios.
ScenarioCPLEX-WOVCPLEX-WVGSAHAObj 1 value (min)Obj 2 valueObj 1 value (min)Obj 2 valueObj 1 value (min)Obj 2 value(10, 2, 0)800508005080050(10, 2, 1)120050120050120050(10, 2, 2)800508005080050(20, 3, 0)120017412001741200188(20, 3, 1)180017418001741800174(20, 3, 2)140017414001741400174(30, 4, 0)520027852002785200286(30, 4, 1)560028256002825600294(30, 4, 2)440027844002784400283(40, 6, 0)800363800363800379(40, 6, 1)120036312003631200385(40, 6, 2)120036312003631200395(50, 7, 0)840046984004698400533(50, 7, 1)700046970004697000545(50, 7, 2)820046982004698200513(60, 9, 0)34040016002360058324400737(60, 9, 1)72240028852420057525000682(60, 9, 2)23780026471820057918200690(70, 10, 0)19540019891640065916848764(70, 10, 1)16160015931680068517600768(70, 10, 2)14980027081460065915400722Table 9
Objective values and computation times of CPLEX-WOV, CPLEX-WV, and GSAHA under different scenarios.
ScenarioCPLEX-WOVCPLEX-WVGSAHAObj valueCPU time (s)Obj valueCPU time (s)Obj valueCPU time (s)GAP with CPLEX-WV (%)(10, 2, 0)850124.318508.178502.400(10, 2, 1)125051.7312508.7512502.430(10, 2, 2)85067.498508.238502.340(20, 3, 0)1374361.25137424.6613883.211.02(20, 3, 1)1974377.20197425.1919743.100(20, 3, 2)1574340.83157424.0215743.330(30, 4, 0)5478326.84547846.0554864.750.15(30, 4, 1)5882517.27588253.2558945.220.20(30, 4, 2)4678208.92467837.5346835.010.11(40, 6, 0)1163766.13116346.3011797.781.38(40, 6, 1)1563480.83156353.6615857.831.41(40, 6, 2)1563954.16156355.2715957.852.05(50, 7, 0)88691335.458869105.22893312.860.72(50, 7, 1)74691010.09746987.42754513.321.02(50, 7, 2)86691052.388669121.58871312.790.51(60, 9, 0)342000360024183661.222513720.253.94(60, 9, 1)725285360024775678.172568220.073.66(60, 9, 2)240447360018779604.381889021.610.59(70, 10, 0)197389360017059679.481761227.083.24(70, 10, 1)163193360017485344.521836827.895.05(70, 10, 2)152508360015259529.751612228.965.66Three points can be drawn from the computation results in Tables8 and 9. First, the computation times of CPLEX-WOV, CPLEX-WV, and GSAHA increase gradually as the number of trains increases, and the maximum computation times of those three solution methods are equal to 3600 s, 679.48 s, and 28.96 s, respectively. In particular, even if CPLEX is sped up with the valid inequalities, the computation times of GSAHA are still much fewer than that of CPLEX. Therefore, it can be shown that our proposed GSAHA can solve the reoptimization problem more efficiently in a real-time manner. Second, the objective values of GSAHA are close to those of CPLEX-WV with the maximum gap value equal to 5.66%. Third, after comparing the computation times of CPLEX-WOV and CPLEX-WV, it can be seen the valid inequalities in Section 4.5 can significantly speed up the solving process of CPLEX. More specifically, CPLEX-WOV cannot obtain optimal solutions for the instances with the number of trains larger than or equal to 60 trains within 3600 s, which results in large objective values. In order to illustrate the feasibility of our proposed MILP model, the optimization solution of the scenario (70, 10, 0) using CPLEX-WV is illustrated in detail. Table 10 shows that the arrival and departure times of 11 trains are delayed after the reoptimization, and the new platform track assignment plan is provided in Table 11. Besides, the platform track utilization scheme is illustrated in Figure 9, and it can be seen from Figure 9 that all safety headway requirements are satisfied. Note that the 14 trains in Table 11 with bold fonts represent that those trains have been reassigned to different platform tracks, and those 14 trains are marked with the red colour in Figure 9. Besides, the convergence process of GSAHA is shown in Figure 10, where the algorithm can reach the near-optimal solution only after 70 iterations.Table 10
Amount of secondary delay for the trains obtained by CPLEX-WV for the scenario (70, 10, 0).
TrainPrioritySecondary arrival delay (min)Secondary departure delay (min)T39104T55302T32303T38322T40322T42155T46222T48122T50101T52322T54122Table 11
Platform tack assignment plan after the reoptimization using CPLEX-WV for the scenario (70, 10, 0).
Platform track numberOccupation trains11T9, T299T5, T19, T31, T41, T49, T557T11, T21, T27, T33, T43, T53, T63, T695T1, T7, T15, T25, T35, T45, T47, T61, T67, T733T3, T13, T17, T23, T37, T39, T51, T57, T59, T65, T71, T75III4T2, T8, T18, T22, T28, T34, T40, T42, T48, T44, T60, T646T4, T12, T16, T24, T30, T32, T38, T50, T54, T58, T628T6, T14, T20, T46, T5610T10, T26, T36, T52Figure 9
Platform track utilization scheme after the reoptimization using CPLEX-WV for the scenario (70, 10, 0).Figure 10
Convergence process of GSAHA for the scenario (70, 10, 0).Meanwhile, for the scenario (70, 10, 0) in Tables8 and 9, sensitivity analysis of different values of weighting factor α is performed by increasing the value of α from 0 to 10 with the step size equal to 1 for small values of α and from 40 to 440 with the step size equal to 40 for relatively larger values of α. Moreover, one special case is designed by setting α=1 and removing the second part of the objective function, which is aimed to simulate the case that α takes an infinity value. The optimization results of CPLEX-WV and GSAHA are listed in Table 12, and the parameter settings for the GSAHA remain unchanged. In addition, we take the objective value of GSAHA for the average optimization results of 20 runs. It can be shown that the objective values of CPLEX-WV and GSAHA increase as the value of α increases, and the solution times of CPLEX-WV range from 256.36 to 3600 seconds while the solution times of GSAHA only range from 27.08 to 32.92 seconds. The last column in Table 12 shows that the objective values of GSAHA are −18.74%–5.10% larger than those of CPLEX-WV. In particular, CPLEX-WV cannot obtain the optimal solution for α=0 within the time limit, while GSAHA can obtain a solution that is much smaller than that of CPLEX-WV. In addition, for the case of α=∞, it can be shown that the minimum value of the first part of the objective function is equal to 82 min, and GSAHA can also obtain an objective value of 84 min. Note that the optimality gaps of GSAHA compared with CPLEX could be due to two reasons in particular. First, the spatial and temporal resources are allocated separately in GSAHA. Second, a heuristic method is developed to resolve the temporal conflicts between trains. Overall, the stable performance of GSAHA regarding the solution quality and solving times shows that our proposed GSAHA is suitable to serve as an effective computer-aided decision-making tool for the train dispatchers in case of train delays.Table 12
Optimization results of CPLEX-WV and GSAHA with different values of weighting factorα.
Weighting factorαCPLEX-WVGSAHAObj 1 value (min)Obj 2 valueObj valueCPU time (s)Obj 1 value (min)Obj 2 valueObj valueCPU time (s)GAP with CPLEX-WV (%)005875873600047747732.92−18.741104621725490.9011265176330.855.24216465982354118867085828.974.253246659905540.4727067294229.054.094328663991607.41336697103329.174.2454106631073731.23420704112429.334.7564926591151544.47504706121029.025.1375746591233547.19588702129028.994.6286566631319651.16672709138129.074.7097386691407934.73756704146029.093.77108206631483718.23841715155628.304.924032806593939740.223376764414027.605.108065606597219589.286736771750728.203.99120984065910499764.37101427721091427.523.951601312066313783447.63134497841423327.513.262001640065917059679.48168487641761227.083.242401968065920339388.56201827692095127.253.012802296065923619359.88234688742434227.493.063202624065926899595.69269247572768127.652.913602952065930179329.28302618083106928.232.954003280065933459340.13336317713440228.772.824403608065936739412.67370897193780828.222.91∞82082256.368408430.042.44


## 7. Conclusions

The problem of reoptimization of the train platforming is essential in recovering the train operations within the station while minimizing the negative impact of train delays. This paper proposes a MILP model for the reoptimization problem, where the train station is represented with the discretized platform track time-space resources. In addition, a set of valid inequalities is developed to improve the performance of the commercial solver. In addition, in order to achieve the real-time reoptimization of the train platforming problem and provide a reliable decision tool for the train dispatchers, a heuristic algorithm called GSAHA that combines the advantages of SA and GA algorithms is designed. Moreover, GSAHA first allocates the spatial resources for the trains, and the temporal conflicts between trains are further resolved through a specialized heuristic rule. To test the efficiency and effectiveness of the proposed model and algorithm, a set of real-life instances is solved by a commercial solver and GSAHA. The computational results show the proposed MILP model can effectively achieve the reoptimization of the train platforming problem, and the proposed heuristic algorithm can further speed up the solving process of the commercial solver with near-optimal solutions. In addition, the computational results also show that the performance of GSAHA is stable even when the values of weighting factorα vary from 40 to 440.The work in this paper can be extended in the following several interesting directions. First, instead of ensuring the arrival and departure safety headway between two different trains running in the same direction, the explicit consideration of train entrance and exit route conflicts can increase the station throughput capacity and reduce the train delays [10, 20]. Second, the MILP model and the heuristic algorithm GSAHA proposed in this paper can be further developed to consider different station types, such as the terminal station where trains need to perform the turn-around movement that makes the train platforming problem more complicated [42, 43]. Third, the train movements at the stations can be viewed as a set of space-time paths, and thus more efficient dual decomposition methods could be developed accordingly [7, 44, 45]. Fourth, more efficient solution algorithms can be developed for the simultaneous reoptimization of several interconnected railway stations in a railway line or even a regional railway network with more complicated structure so that the joint optimization of delay situations and train timetabling problems can be achieved [8, 19, 27, 46–49]. Finally, the integration of energy-efficient train movement with the reoptimization of train platforming can be considered for more system-wide benefits [50, 51].



---

*Source: 5609524-2020-06-03.xml*