Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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

A Fast Approach for Reoptimization of Railway Train Platforming in Case of Train Delays Hindawi Journal of Advanced Transportation Volume 2020, Article ID 5609524, 20 pages https://doi.org/10.1155/2020/5609524 Research Article A Fast Approach for Reoptimization of Railway Train Platforming in Case of Train Delays 1,2,3 1,2,3 1,2,3 1,2,3 Yongxiang Zhang, Qingwei Zhong, Yong Yin , Xu Yan , 1,2,3 and Qiyuan Peng School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China National United Engineering Laboratory of Integrated and Intelligent Transportation, Southwest Jiaotong University, Chengdu 610031, China National Engineering Laboratory of Integrated Transportation Big Data Application Technology, Southwest Jiaotong University, Chengdu 610031, China Correspondence should be addressed to Yong Yin; yinyong@swjtu.edu.cn Received 18 January 2020; Revised 24 February 2020; Accepted 20 May 2020; Published 3 June 2020 Academic Editor: Yu Jiang Copyright © 2020 Yongxiang Zhang et al. *is is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Train platforming is critical for ensuring the safety and efficiency of train operations within the stations, especially when un- expected train delays occur. *is 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. *e 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. Moreover, the railway planning process includes the net- 1. Introduction work design and line planning at the strategic level, the train Railroad transportation plays an important role in providing timetabling, train platforming, rolling stock scheduling and economic and environment-friendly transport services for crew scheduling at the tactical level, and the real-time traffic passengers and goods. In particular, transport demand of management at the operational level [2]. As a result, the core railroad transportation is increasing rapidly in some parts of of the computer-aided decision systems is to develop ef- regional markets. For instance, according to the statistical fective optimization techniques for the different railway data of the National Bureau of Statistics of China, the volume planning and operation stages. We refer the readers to Assad of passenger and freight traffic of China railway in 2018 has [3], Cordeau [4], and Lusby et al. [2] for excellent surveys on increased by 9.44% and 9.15%, compared with the volume in the related optimization methods. In general, train time- 2017 [1]. *us, more and more trains are required to be tabling stage can determine the arrival and departure times operated on the railway network with limited infrastructure of the trains at each of the visiting stations from an aggregate capacity to satisfy the large demand. *erefore, the railway perspective [5–8]. Train operations at the stations, including operators need to adopt advanced and reliable computer- the train routing on the arrival and departure routes and the aided decision systems to improve train operation efficiency. train platform assignment decisions, are usually optimized 2 Journal of Advanced Transportation train sequencing variables in the big-M modeling by solving the train platforming problem [8]. Apart from the boarding and alighting of passengers as well as the loading framework can be avoided. and unloading of goods at the station platforms, many other (3) An efficient heuristic algorithm is designed to complicated operation tasks can be performed at the sta- quickly obtain the near-optimal solutions for the tions, such as the train turn-around movement and the real-time reoptimization of train platforming. shunting work. *us, it is of critical importance to develop (4) A set of real-life experiments is performed to show efficient and effective optimization techniques to improve the efficiency and effectiveness of the proposed the train operation efficiency at the stations without causing model and algorithm. any conflicts. *e rest of this paper is structured as follows. Section 2 Due to the complex layout of large railway stations and provides a comprehensive literature review on the optimi- the associated dense train traffic, it is usually a challenging zation and reoptimization of train platforming problems. task for the train dispatchers to make a high-quality train *e method on how to describe the discretized platform operation plan within a station in a short period. Kroon et al. track time-space resources is introduced in Section 3. In [9] have already proven that the train platforming problem is Section 4, we propose a new MILP model based on the an NP-complete combinational optimization problem. As a discretized platform track time-space resources, as well as result, many researchers have developed sophisticated and some valid equalities to strengthen the resulting MILP efficient models and algorithms to deal with the train plat- model. Section 5 presents the detailed algorithmic steps of a forming problem, such as the node packing model and the heuristic algorithm, i.e., the genetic and simulated annealing branch-and-cut algorithm in Zwaneveld et al. [10, 11] and the hybrid algorithm, for solving the reoptimization problem in set packing model and the branch-and-price algorithm in a real-time manner. *e efficiency and effectiveness of the Lusby et al. [12, 13]. In practice, however, trains may suffer proposed methods are verified through a set of real-life from all kinds of disturbances and disruptions, such as bad experiments in Section 6. Section 7 gives the concluding weather, equipment failure, and management factors [14]. remarks and possible further research directions. 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 2. Literature Review any potential conflicts [15–18]. However, with regard to the Train platforming problem is a key optimization stage in the train platforming problem, two managerial aspects lack in- railway hierarchical planning process, and it has attracted depth study. First, most of the researchers study the train the attention of many researchers around the world [2]. platforming problem without considering train delays, and Given the information of train arrival and departure times thus they do not consider the situation where it could be and the train running directions obtained at the train impossible to make a feasible train operation plan at the timetabling stage, the train dispatchers need to decide how stations with the given train timetable. Second, in order to to schedule the trains at the stations to avoid the train delays generate a disposition timetable during the train rescheduling caused by the cross interference between train operations. process as soon as possible, the detailed train operations at the *e complexity of the train platforming problem grows stations are neglected, and the aggregate station capacity is quickly as the number of trains increases and the station adopted instead [17, 18]. layout becomes more and more complicated. *erefore, a lot In this study, we aim to bridge the research gaps lying in of excellent works have been done regarding the train the train platforming and train rescheduling problems. More platforming problem, such as Carey [19], Zwaneveld et al. specifically, we reoptimize the train platforming problem in [10], Lusby et al. [12], Chakroborty and Vikram [20], case of train delays and generate a new train operation plan Caprara et al. [21], and Kang et al. [22]. We next review these within the station in real time. Our solution is to develop a works mainly from two aspects, i.e., the train platforming mixed integer linear programming (MILP) model, where the problem at the tactical level and the train platforming train station is modeled using the discretized platform track problem considering the negative impact of train delays. time-space resources, and to propose an efficient heuristic *e studies on the train platforming problem at the algorithm. *e goal of the proposed model and algorithm is tactical level were initially focused on scheduling the train to simultaneously minimize the deviation from the train movements at the stations efficiently and economically with timetable and the total train operating costs, realizing the the fixed or slightly relaxed train arrival and departure times. coherence between train operations and the station man- Zwaneveld et al. [10] developed the first node packing model agement. *e theoretical and practical contributions of this for the train platforming problem, and the station routes study mainly include the following four aspects: were classified as the inbound route, outbound route, and (1) *e train arrival and departure times and the train complete. In addition, small deviations from the planned platform assignment are optimized simultaneously train arrival and departure times were considered to increase so that the negative influence of train delays can be the possibility of finding a feasible solution, and an improved minimized. branch-and-cut algorithm was designed to find the optimal (2) *e novel modeling method based on the discretized solutions with the goal of maximizing the number of platform track time-space resources can describe the trains routed through the station. Kroon et al. [9] proved train conflicts accurately, where the complex binary that the node packing model in Zwaneveld et al. [10] was Journal of Advanced Transportation 3 searching method was adopted to solve the resulting model. NP-complete once each train had more than three routing possibilities. Based on the work in Zwaneveld et al. [10], In addition, the arrival and departure headways between two trains were enforced to guarantee the train running safety. Zwaneveld et al. [11] further proposed a weighted node packing model for the train platforming problem, where Dorfman and Medanic [30] proposed a discrete event model several hierarchical objectives can be considered with the to schedule the trains in the railway network, where the train unified weighted sum form. However, the node packing routes were assumed to be fixed for simplicity. D’ariano et al. model has its own deficiencies to be put into practice. For [31] formulated the train scheduling problem through the instance, all of the conflicting train movements need to be alternative graph modeling approach, and an efficient identified in advance in the node packing model, and it branch-and-bound algorithm was designed to solve the MILP model. Rodriguez [32] proposed a combined con- usually results in a large-scale optimization model. As a result, Lusby et al. [12] built a set packing model of the train straint programming and simulation method for scheduling trains in the junctions, where the constraint programming platforming problem, and a branch-and-price algorithm was designed such that the feasible train routes can be dy- model representing the signalling system behaviour and the simulation model can reflect the train and driver behaviour. namically generated. Besides, the train platforming problem can be also reformulated as a graph colouring problem, More recently, D’Ariano et al. [33] and Zhang et al. [8] where the number of colours is determined by the available studied the integrated train timetabling and maintenance tracks in the stations [23]. An integer programming model task scheduling problems at the microscopic level, and ef- that was equivalent to graph colouring problem in Cardillo ficient heuristic algorithms based on the commercial solvers and Mione [23] was developed by Billionnet [24]. Caprara were developed accordingly. et al. [21] also allowed a slight relaxation on the ideal arrival Some works were also performed on the optimization of a delay resistant train platforming plan and the real-time and departure times of the trains at the platforms, and they presented a 0-1 quadratic programming model to solve the reoptimization of train platforming problem in case of unexpected train delays. Herrman [34] studied the stable train platforming problem. In particular, the quadratic term in the objective function was designed to consider the soft train routing problem, where the goal was to keep the train schedule to be conflict-free as much as possible in case of incompatibility costs between train paths. Sels et al. [25] developed a new MILP model to schedule the trains in the perturbations. In addition, a local search heuristic approach current and future train set, and penalty costs were con- was designed to solve the train schedule stabilization ˇ ´ sidered in the objective when a train was cancelled or problem. Besinovic and Goverde [35] proposed a max-plus assigned to a different platform. automata model for the station capacity assessment and a Apart from the exact solution methods, some researchers delay propagation model for the robustness evaluation of the also developed heuristic algorithms for the train platforming train platforming plan. Based on these two models, the objectives of minimization of capacity occupation and problem [26–29]. Carey and Carville [26] introduced a se- quential construction heuristic algorithm for the train plat- maximization of robustness were then achieved with a heuristic approach. Kang et al. [22] introduced the concept forming problem at a single station, which was designed according to the train dispatchers’ manual methods. In ad- of stochastic schedule with uncertain train arrival and de- dition, trains can be delayed in the planning process to generate parture times, and a simulated annealing algorithm was a feasible solution, and the assignment of trains to the un- developed to solve the corresponding train platforming desired platforms was penalized. Carey and Crawford [27] problem. D’Ariano et al. [36] designed a rolling horizon further extended the work in Carey and Carville [26] by approach for the real-time train rescheduling problem, and considering the train scheduling and platforming problems at the alternative graph formulation was adopted for solving multiple stations, where those stations were connected by the smaller subproblem in each rolling period. Chakroborty several one-way lines. Similarly, trains can be also delayed when and Vikram [20] developed a MILP model for optimally allocating trains to the platform tracks, where the accurate they were scheduled from one station to the corresponding next station. Kang et al. [28] proposed a simulated annealing train arrival times can only be available shortly before the train arrives at the station such that trains could be reas- heuristic algorithm with the goal of achieving the balanced occupation of station turnouts while minimizing the total signed to different platforms. Besides, the headway between occupation times of the station turnouts. Wu et al. [29] de- two trains was also considered while delaying the train veloped a mean-variance optimization model for the train arrival and departure times. Lusby et al. [13] proposed a set platforming problem based on Markowitz’s portfolio theory, packing model for rescheduling the trains in the junctions in which was aimed to minimize the total occupation time costs of case of disruptions. In particular, a branch-and-price al- groups of turnouts. Moreover, an efficient simulated annealing gorithm was introduced to solve the set packing model, and the objective was to minimize the weighted deviations from heuristic algorithm was designed to solve the resulting mixed integer nonlinear programming (MINLP) model. the trains’ scheduled arrival times. Liu et al. [37] developed a MINLP model to reallocate the tracks of trains at the stations Some researchers also tried to integrate the two stages of train timetabling and train platforming problems to further in a real-time manner, where the goal was to minimize average use time of groups of turnouts without changing the increase the railway network capacity utilization. Carey [19] proposed an integrated optimization model to simulta- planned train times. Moreover, a genetic simulated neously optimize the lines, platforms, and routes of the annealing algorithm was also designed to solve the MINLP trains in a railway network, and an improved sequential model efficiently. 4 Journal of Advanced Transportation Table 1 summarizes the modeling approaches, objectives, corresponding matrix R of a feasible usage plan are de- solution methods, and other characteristics of relevant scribed in Figures 2(a) and 2(b), respectively. *e application publications on the optimization and reoptimization of train requirements of the time-space resources modeling method platforming problems, and major highlights can be drawn for the reoptimization of train platforming problem can be from Table 1. First, most of the studies focus on the train formulated as follows: platforming problem at the tactical level, and the scheduled (1) Inseparability. A train must occupy only one plat- train arrival and departure times at the stations are usually form track and cannot occupy more than one assumed to be fixed. *erefore, the optimization objectives platform track simultaneously. of those studies are generally minimizing the total costs or (2) Exclusivity. One platform track can only store one maximizing the total benefits. Second, exact algorithms train at any time unit to prevent the train conflicts. account for the majority of the solution methods to solve the optimization or reoptimization of the train platforming (3) Continuity. A train operation on one platform track problems. *erefore, efficient and flexible heuristic algo- with the duration equal to Δt time units cannot be rithms are required, especially for the real-time reoptim- interrupted. If one train starts to use track i at time t, ization of the train platforming problem. *ird, among the it continues to occupy the platform track i until studies that consider the negative influence of train delays, t + Δt, i.e., r � r � r � . . . � r � 1. i,t i,t+1 i,t+2 i,t+Δt only one research by Chakroborty and Vikram [20] si- multaneously incorporates the factors of train delay, reas- 4. Mathematical Modeling for signment of platform, and deviations from scheduled train Reoptimization of Train Platforming arrival and departure times. However, they adopt a com- mercial solver to deal with the MILP model. In this study, we 4.1. Modeling Assumptions. Without loss of generality, we develop a new MILP model for the reoptimization of the make the following key modeling assumptions to facilitate train platforming problem based on the discretized time- the modeling process. space resources, and we also design an efficient heuristic (1) When it is impossible to eliminate the conflicts algorithm to guarantee the achievement of real-time through reassignment of platforms, the train arrival reoptimization. and departure times can only be delayed to resolve the conflicts. 3. Analysis of Platform Track Time- (2) One minute is applied to discretize the platform Space Resources track time-space resources, and smaller time units can be adopted if necessary. Let T be the planning horizon; we handle the time resources as small time units of length Δτ. *e number of time units is (3) Trains are modeled as single objects moving in the equal to |T| � [T/Δτ] in the entire planning horizon. In railway station, and thus the influence of train addition, the number of platform tracks in a station is lengths on the clearing times of the platform tracks is denoted by |I|, i.e., the maximum spatial capacity. Hence, the not considered. platform track time-space resources of a station can be (4) By enforcing the arrival and departure headways represented by a two-dimensional matrix R: between two trains running in the same direction as r r ... r well the safety time interval for platform track op- 1,1 1,2 1,|T | ⎢ ⎥ ⎡ ⎢ ⎤ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ eration, it can be guaranteed that there are no ⎢ ⎥ ⎢ ⎥ ⎢ r r ... r ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 2,1 2,2 2,|T | ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ conflicts between any two trains. R � 􏽨r 􏽩 � ⎢ ⎥, (1) ⎢ ⎥ i,t ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ... ... ... ... ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ (5) All trains will pass through the railway station, and r r ... r turn-around movements of the trains are not con- | I |,1 | I |,2 |I |, | T| sidered for simplicity. where i and t are the indexes of the platform track and the time unit, respectively, and a binary variable r in matrix R i,t denotes the occupation and vacancy state of the platform 4.2. Definitions of Sets, Parameters, and Variables. Sets, track time-space resource (i, t), where parameters, and variables of this study are defined in Table 2. In particular, we assume that all parameter values related to 1, platform track time − space resource (i, t) is used, r � 􏼨 time are multiples of the time unit Δτ. i,t 0, othewise. (2) 4.3. Objective Function. *e objective function in equation Figure 1 provides an illustrative example of the modeling (3) contains the weighted sum of two parts of costs. *e first method of platform track time-space resources. Suppose that part is the sum of train arrival and departure delays, con- 5 trains successively arrive at or depart from station N which sidering the train priority P and the weighting factor α. *e has 6 platform tracks within the planning horizon of 60 min. second part is the total platform track assignment costs. In *e detailed schedules of train operations in both directions particular, the more that train l is preferred for platform are given in Figures 1(b) and 1(c), and the time unit Δτ is set track i, the smaller is the corresponding platform track to 5 min. Platform track time-space resources and the assignment cost c . Note that value of c can be determined l,i l,i Journal of Advanced Transportation 5 Table 1: Summary of relevant publications on the optimization and reoptimization of the train platforming problems. Deviations Computation Modeling Solution Train Reassignment from Largest times (in Publication Objective approach method delay of platform scheduled instance solved seconds) of the train times largest instance A railway Max the Zwaneveld station with 17 BILP number of Branch-and-cut √ 85 et al. [10] platforms and routed trains 27 trains A railway Iterative Cardillo and station with 16 GC Feasibility heuristic 0.67 Mione [23] tracks and 242 algorithm trains A railway Billionnet Optimization station with 14 BILP Feasibility 1.64 [24] software tracks and 200 trains Min the costs of Iterative A railway deviations from Carey and sequential station with 29 MILP preferred times, √ √ — Carville [26] searching subproblems platforms, and method and 491 trains lines A 15.18 km Rodriguez long railway CP Min train delays Tree search √ √ 54.76 [32] junction with 24 trains A railway junction with Lusby et al. Max total Branch-and- BILP 64 block 26.4 [12] benefits price sections and 45 trains A railway Caprara et al. Branch-and- station with 14 BQP Min total costs 350 [21] cut-and-price platforms and 237 trains A railway Min total Commercial station with 14 Sels et al. [25] MILP √ 3.0 penalties solvers platforms and 160 trains Min total train A railway journey times Iterative network with Zhang et al. MILP and heuristic 27 stations, 55 7200 [8] maintenance algorithm segments, and tardiness costs 58 trains Genetic A railway Min average use simulated station with 11 Liu et al. [37] MINLP time of groups √ 1800 annealing tracks and 30 of turnouts algorithm trains Min total A railway occupation Kang et al. Simulated station with 11 MILP times and √ 726 [22] annealing tracks and 28 balanced track trains occupation A railway Chakroborty Commercial station with 9 and Vikram MILP Min total costs √ √ √ 600 solver platforms and [20] 110 trains A railway junction with Lusby et al. Min total Branch-and- BILP √ √ 524 track 151.55 [13] deviations price sections and 66 trains 6 Journal of Advanced Transportation Table 1: Continued. Deviations Computation Modeling Solution Train Reassignment from Largest times (in Publication Objective approach method delay of platform scheduled instance solved seconds) of the train times largest instance Genetic and A railway simulated station with 11 *is paper MILP Min total costs annealing √ √ √ 32.92 platforms and hybrid 70 trains algorithm Note. 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. Downstream entrance Downstream exit 27 4 2 3 9 13 25 24 20 16 23 35 7 11 22 19 12 II 37 28 8 1 5 15 17 21 30 14 10 Upstream exit Upstream entrance 39 32 (a) l l l l l 1 3 5 4 2 15 20 35 0 10 510 30 15 20 l l l l l 3 1 5 2 4 (b) (c) Figure 1: Layout and train timetables of station N: (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. Platform track Platform track 0 1 1100100 5 0 3 5 0 l l l 0 0 l 0 0 0 1000000 1 1 1 5 0 0 0000000 I 3 0 0 l 0 0 0 0 0 0 0 0 0000000 II I 0 0 0 0 0 0 0 0 0 0 4 0 1000000 111100000 6 II 0 0 0 0 0 0 0 0 0 t 5 10 15 20 25 30 35 40 45 4 0 0 l 0 0 0 0 0 0 6 l l l l 0 0 0 0 0 2 2 2 2 0 5 1015202530354045 t (a) (b) 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. according to several influence factors, including the initial min z � α 􏽘 P 􏽨􏼐y − t 􏼑 + 􏼐y − t − D􏼑􏽩 + 􏽘 􏽘 w c . l l,a l,a l,d l,d l,i l,i platform track assignment plan, the convenience of pas- i∈I l∈L l∈L senger boarding and alighting, and other special require- (3) ments for train operations. *erefore, the smaller the value of c is, the more the train l prefers the platform track i. l,i Journal of Advanced Transportation 7 4.4. Constraints 􏽘 x ≤ 1, ∀i ∈ I, t ∈ {1, 2, . . . , MT}. l,i,t (9) l∈L 4.4.1. Relation between Platform Track State Variables. According to definitions of platform track state variables x , u , and v , constraint (4) expresses the relationship l,i,t l,i,t l,i,t among those three platform track state variables. In par- 4.4.5. Continuous Train Operation on the Platform Track. ticular, when both the variables u and v are equal to 0, it Constraints (10)–(12) guarantee that train operations on the l,i,t l,i,t can be known that train l is occupying the platform track i at platform tracks should be performed continuously, by time t, i.e., x � 1. Figure 3 shows an illustrative example enforcing the relationship between the values of variables l,i,t on how to calculate the value of x according to the values u and v . For instance, if w � 1 in constraint (10), l,i,t l,i,t l,i,t l,i of the variables u and v . More specifically, train l which implies that train l is assigned to the platform track i, l,i,t l,i,t 1 arrives at the platform track 5 in Figure 1 at time 5 and it constraint (10) changes to u ≥ u . According to the l,i,t l,i,t+1 leaves from the corresponding platform track at time 20. definition of u in Section 4.2, the condition u ≥ u is l,i,t l,i,t l,i,t+1 *erefore, Figures 3(a) and 3(b) present the values of the obviously satisfied. On the other hand, if w � 0 in con- l,i variables u and v for train l according to its actual straint (10), constraint (10) is no longer valid. Similarly, l,i,t l,i,t 1 arrival and departure times. In addition, according to constraints (11) and (12) define the relationships between constraint (4), the values of v in Figure 3(c) can be easily v and v as well as between u and u . l,i,t l,i,t l,i,t+1 l,i,t l,i,t+1 obtained. u ≥ u + w − 1, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT − 1}, l,i,t l,i,t+1 l,i x � 1 − 􏼐u + v 􏼑, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}. l,i,t l,i,t l,i,t (10) (4) v ≤ v − w + 1, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT − 1}, l,i,t l,i,t+1 l,i (11) 4.4.2. Actual Train Arrival and Departure Times. u ≤ u + w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT − 1}. Constraints (5) and (6) show that values of actual arrival l,i,t l,i,t+1 l,i time y and actual departure time y of train l can be (12) l,a l,d inferred from the values of platform track utilization state variable u and the platform track clearance state variable l,i,t v . l,i,t 4.4.6. Safety Headway between Two Trains. Constraints MT (13)–(18) impose the required safety headway between two y � MT − 􏽘 􏽘􏼐1 − u 􏼑, ∀l ∈ L, (5) l,a l,i,t arrival or departure trains running in the same direction, and i∈I t�1 the train sequencing variables λ and μ as well as the l,k l,k MT platform track choice variables w and e are also embedded l,i l,k y � MT − 􏽘 􏽘 v , ∀l ∈ L. (6) in those constraints. Constraint (13) enforces the safety l,d l,i,t i∈I t�1 headway between two arrival trains in the same direction, and it is valid only if λ � 1, i.e., train l arrives at the station before l,k train k. When λ � 1 in constraint (13), it can be shown that l,k the safety headway between trains l and k depends on the 4.4.3. Platform Track Assignment Constraint. Constraint (7) value of the variable e . More specifically, if e � 1, trains l l,k l,k requires that each train l can only be assigned to one and k are assigned to the same platform track, and they are platform track, and the corresponding platform track has to separated by the safety time interval D. Otherwise, trains l and be in the set I . Furthermore, constraint (8) enforces that a k are assigned to two different platform tracks, and they are train l cannot be assigned to forbidden platform tracks, i.e., separated by the arrival headway h . Meanwhile, constraint tracks that are not in the set I . Constraints (7)-(8) provide a (14) guarantees the safety headway between two departure flexible method to restrict the platform track choices of the trains in the same direction. Constraint (15) ensures that if trains. both the variables w and w are equal to 1, the value of the l,i k,i variable e can be enforced to be 1. Furthermore, constraint l,k 􏽘 w � 1, ∀l ∈ L, l,i (7) (16) describes that the values of the two variables e and e l,k k,l i∈I for two different trains l and k are equal. Besides, constraints (17) and (18) guarantee that only one of the train sequencing w � 0, ∀l ∈ L, i ∈ I\I . (8) l,i l variables λ and λ or μ and μ between any two different l,k k,l l,k k,l trains is equal to 1. y − y ≥ 􏼐1 − e 􏼑h + e D − λ M, l,a k,a l,k a l,k l,k 4.4.4. Platform Track Capacity Constraint. Constraint (9) (13) ∀l, k ∈ L: l ≠ k, π � π , ensures that any platform track i can only be occupied by at l k most one train at any time t, such that no conflicts can occur between any two trains that are assigned to the same y − y ≥ 􏼐1 − e 􏼑h + e D − μ M, l,d k,d l,k d l,k l,k (14) platform track. ∀l, k ∈ L: l ≠ k, π � π , l k 8 Journal of Advanced Transportation Table 2: Sets, parameters, and variables. Symbol Definition Sets L Set of trains, indexed by l L Set of delayed trains, L ⊆L 1 1 I Set of platform tracks, indexed by i I Set of platform tracks that train l can utilize, I ⊆I l l T Set of time intervals in the planning horizon, indexed by t Parameters c Cost of assigning train l to platform track i l,i π 0-1 parameter is equal to 1 if train l is running in the downstream direction; 0, otherwise q 0-1 parameter is equal to 1 if train l was initially assigned to platform track i before a delay occurs; 0, otherwise l,i S *e time when the information of train delays is updated t Scheduled arrival time of train l l,a t Scheduled departure time of train l l,d t Estimated arrival time of train l when a delay occurs l,a t Estimated departure time of train l when a delay occurs l,d Δ Dwell time of train l P Priority of train l D Safety time interval for platform track operation MT Sum of the length of the planning horizon T and the safety time interval for platform track operation D Δ Maximum value of dwell times of all trains max h Headway between two arrival trains running in the same direction h Headway between two departure trains running in the same direction α Objective function weighting factor M A sufficiently large number Variables w 0-1 platform track assignment variable � 1 if train l is assigned to platform track i; � 0 otherwise l,i e 0-1 same platform track choice variable � 1 if train l and train k choose the same platform track; � 0 otherwise l,k x 0-1 platform track occupancy state variable � 1 if train l occupies platform track i at moment t; � 0 otherwise l,i,t u 0-1 platform track utilization state variable � 1 if train l has not yet arrived at platform track i at moment t; � 0 otherwise l,i,t v 0-1 platform track clearance state variable � 1 if train l has left platform track i at moment t; � 0 otherwise l,i,t λ 0-1 train arrival sequence variable � 1 if train l arrives at the station before train k; � 0 otherwise l,k μ 0-1 train departure sequence variable � 1 if train l departs from the station before train k; � 0 otherwise l,k y Actual arrival time of train l at the station l,a y Actual departure time of train l at the station l,d Platform track Platform track 5 1 0 0 0 0 0 0 0 0 5 001 01 0 11 1 3 1 1 1 1 1 1 1 1 1 3 0 0 0 0 0 0 0 0 0 I 1 1 1 1 1 1 1 1 1 I 0 0 0 0 0 0 0 0 0 II 1 1 1 1 1 1 1 1 1 II 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 4 0 0 0 0 0 0 0 0 0 6 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 5 1015202530354045 t 0 5 1015202530354045 t (a) (b) Platform track 5 01 1 1 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 II 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 5 1015202530354045 t (c) Figure 3: An illustrative example showing the values of platform track state variables u , v , and x : (a) values of the variable u ; l,i,t l,i,t l,i,t l,i,t (b) values of the variable v ; (c) values of the variable x , and x � 1− (u + v ). l,i,t l,i,t l,i,t l,i,t l,i,t Journal of Advanced Transportation 9 ranges of constrains (13)–(18), we simply approximate the e ≥ w + w − 1, ∀l, k ∈ L, i ∈ I ∩I : k > l, π � π , l,k l,i k,i l k l k number of constraints (13)–(18) without considering those (15) filter conditions. As a result, the upper bound on the number of constraints of the MILP model is equal to e � e , ∀l, k ∈ L: k > l, π � π , (16) l,k k,l l k MT|I|(2|L| + 1) + 6|L| + |L| (5 + |I|) + (|I| − |I |), l∈L l which increases polynomial as the number of trains |L|, the λ + λ � 1, ∀l, k ∈ L: k > l, π � π , (17) number of platform tracks |I|, and the length of planning l,k k,l l k horizon T increase. Similarly, the upper bound on the number of variables is equal to |L| · |I|(1 + MT) + |L| . μ + μ � 1, ∀l, k ∈ L: k > l, π � π . (18) l k l,k k,l 4.5. Valid Inequalities. Valid equalities are additional con- 4.4.7. Minimum Train Dwell Time Constraint. Constraint straints that have been implicitly satisfied according to other (19) enforces the minimum dwell time for each train l. In necessary model constraints (4)–(25). However, they can be particular, the right-hand side of constraint (19) can only be applied to strengthen the model formulation [17, 38]. valid when w � 1, i.e., train l is assigned to the platform Constraints (26)–(29) define the four valid inequalities that l,i track i. Note that the safety time interval for platform track are related to the variables u , v , x , and w . Note that l,i,t l,i,t l,i,t l,i operation D is also included in the right-hand side of the the valid inequalities are only implemented in a commercial constraints so that the required safety time interval for trains solver to speed up the solving process of the commercial assigned to the same platform track is imposed. In addition, solver. the minimum dwell time Δ of a train l is a deterministic u ≥ 1 − w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (26) l,i,t l,i value. MT v ≤ w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (27) l,i,t l,i 􏽘 x ≥ w Δ + D􏼁 , ∀l ∈ L, i ∈ I. (19) l,i,t l,i l t�1 x ≤ w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (28) l,i,t l,i 4.4.8. Actual Train Arrival Time and Departure Time x � 0, ∀l ∈ L, i ∈ I, t ∈ 􏽮1, 2, . . . , t − 1􏽯 ∨ t ∈ 􏽮t l,i,t l,a l,d Constraint. Constraints (20)–(22) specify that the actual + Δ + D + 1, . . . , MT . max arrival and departure times of the trains should be no less (29) than the corresponding planned arrival and departure times, respectively. Note that safety time interval D is introduced *e principles of building valid inequalities (26)–(29) are into the right-hand sides of constraints (21)-(22), such that similar. For instance, in valid inequality (26), if train l oc- the safety time interval D for platform track operation is cupies platform track i, then valid inequality (26) is implicitly satisfied between the departure time y of train l l,d equivalent to u ≥ 0 which turns out to be ineffective. l,i,t and the arrival time of any other trains that are assigned to However, if train l does not occupy the platform track i, then the same platform track. valid inequality (26) is equivalent to u ≥ 1 which implies l,i,t y ≥ t , ∀l ∈ L, (20) u � 1. Valid inequality (29) considers when the station l,a l,a l,i,t capacity is not sufficient and two conflicting trains need to be assigned to the same platform track, then one of the two y ≥ t + D, ∀l ∈ L, (21) l,d l,d trains with lower priority can be delayed at most by Δ , max which means x can be constrained to 0 when l,i,t y ≥ y + Δ + D, ∀l ∈ L. (22) l,d l,a l t ∈ 􏽮1, 2, . . . , t − 1􏽯 or t ∈ 􏽮t + Δ + D + 1, . . . , MT􏽯. l,a l,d max Overall, a total of 4MT|L| · |I| − |I|(t + Δ + D − t + 1) additional l∈L l,d max l,a 4.4.9. Domain of Variables. Constraints (23)–(25) define the constraints are added into the model after introducing the domain of variables. Note that the variables x , y , and l,i,t l,a valid inequalities (26)–(29). y are intermediate variables to facilitate the model l,d building process, and their values can be directly inferred 5. Genetic and Simulated Annealing from the variables u and v . l,i,t l,i,t Hybrid Algorithm w � {0, 1}, ∀l ∈ L, i ∈ I, (23) l,i In order to recover the train operations as soon as possible in case of train delays, a genetic and simulated annealing hybrid u , v � {0, 1}, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (24) l,i,t l,i,t algorithm (GSAHA) is designed to solve the reoptimization model efficiently and effectively [37, 39, 40]. In particular, e , λ , μ � {0, 1}, ∀l, k ∈ L: l ≠ k, π � π . (25) l,k l,k l,k l k the simulated annealing algorithm (SA) has good ability in In short, formulations (3)–(25) constitute the complete jumping out of local optimal solutions, and its convergence MILP model for the reoptimization of train platforming performance is robust against the generated initial solutions. problem. Due to the complicated filter conditions for the However, the convergence speed of SA is generally slow. On 10 Journal of Advanced Transportation the other hand, the genetic algorithm (GA) is a parallel Generating initial population search algorithm that usually converges very fast, while GA (Sections 5.1 and 5.2) is more likely to be trapped into local optimal solutions and it is not robust against the generated initial solutions. As a Obtaining feasible solutions (Section 5.3) result, the GSAHA algorithm combines the advantages of GA and SA. *erefore, GSAHA is robust on the convergence Calculating fitness of individuals (Section 5.4) 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 Selecting the best individual in the current generation and the global best individual section names corresponding to some key algorithmic steps. *e implementation details for the components of GSAHA are illustrated as follows. Lowering the temperature (Section 5.5) 5.1. Chromosome Representation. Figure 5 shows the one- dimensional real-value encoding method that is used to Objective value of the global No best individual remains unchanged for m represent chromosomes. Each chromosome denotes a generations? platform track assignment plan. In particular, if the value of th th the l gene is equal to i, the l train is assigned to platform Yes track i with its scheduled arrival and departure times. Lifting the temperature to R Furthermore, the length of each chromosome is equal to the 1 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 Maximal number of generations Yes gene is located within the range [1, |I|], and thus there could K is reached or objective value of global |L| best individual equals 0? be |I| possible chromosomes in total. No 5.2. Generating Initial Population. Considering diversity and Performing n times of neighborhood search rationality of individuals in the initial population, the fol- operations (Section 5.6.1) lowing strategies are proposed to generate the initial population. Recalculating fitness of every individual (Section 5.4) Step 1. Denote platform tracks whose numbers are smaller than the number of platform tracks |I| as the set I . Reselecting the global best individual Step 2. Select [|L|/(|I| − 1)] trains that have not been selected yet and assign those trains to one of the un- Performing selection, crossover, and mutation operations (Sections 5.6.2, 5.6.3, assigned platform tracks in set I . and 5.6.4) Step 3. Repeat Step 1 until all platform tracks in set I are assigned and assign the remaining Outputting the objective value of the global |L|− [|L|/(|I| − 1)]·(|I| − 1) trains to the last platform best individual track numbered as |I|. Figure 4: Solution framework of the GSAHA algorithm. Step 4. Repeat Step 2 and Step 3 until all individuals in the initial population are generated. Platform track 5 2 3 6 ... 4 7 1 5.3. Obtaining Feasible Solutions. *e chromosome designed Train 1234 ... |L|–2 |L|–1 |L| in Section 5.1 only assigns trains to the platform tracks, i.e., Figure 5: Illustration of the chromosome representation. 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 5.4. Fitness Function. *e fitness function in equation (30) is track temporal resources due to the violation of safety designed to evaluate each individual such that the algorithm headway requirements, including the safety time interval can achieve a better convergence performance. between two trains assigned to the same platform track D, headway between two arrival trains running in the same f(i) − f min f r � exp − , (30) 􏼁 􏼨 􏼩 i k direction h , and headway between two departure trains running in the same direction h . Hence, a heuristic rule is th where r represents the temperature at the k generation, designed to resolve the temporal conflicts according to the th f(i) represents the objective value of the i chromosome, constraints defined in Section 4.5. Journal of Advanced Transportation 11 For each train i (1 ≤ i ≤ |L|) For each train j (1 ≤ j < i) If train i conflicts with train j Fix the arrival and departure times of train i and record the weighted sum delay amount ϑ after resolving the conflicts of trains numbered before train i; Fix the arrival and departure times of train j and record the weighted sum delay amount ϑ after resolving the conflicts of trains numbered before train i; If ϑ ≤ ϑ i i Adopt the adjust method by fixing the arrival and departure times of train i; Else Adopt the adjust method by fixing the arrival and departure times of train j; End If ϑ ≤ ϑ i i End If train i conflicts with train j End For each train j (1 ≤ j < i) End For each train i (1 ≤ i ≤ |L|) Step 5. Sort all trains in descending order by their scheduled or estimated arrival times and number them from 1 to |L|. Step 6. Use Algorithm 1 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. *is operation considers all trains in set L and the platform track assignment costs, and thus the value calculated during this step serves as the objective value of the chromosome. ALGORITHM 1: A heuristic method to resolve the temporal conflicts between trains with given train order. th f represents the minimal objective value at the k search space with the probability of resulting in better so- min generation, and f (r ) represents fitness value of the lutions. Moreover, neighborhood search operator is one of i k th i chromosome when the temperature is r . Fitness function the main operators that can increase population diversity in equation (30) is an important feature of the SA algorithm, when the algorithm is trapped into local optimal solutions. and it has a good capacity to accelerate the convergence of the algorithm. 5.6.2. Selection. *e roulette method is adopted to select parents according to the cumulative probability, as shown in 5.5. Temperature Decline Function. After determining the the following equation: initial temperature R, the temperature decline function in 􏽐 f k�1 equation (31) is used to lower the temperature at each C � , (33) 􏽐 f iteration. k�1 k r � R · η , (31) where N represents the number of individuals in the population. A random number δ is generated within [0, 1); th where r represents the temperature at the k generation k if δ ∈ (C , C ), then chromosome j is chosen as a parent. 2 i j and the constant η represents the temperature decline rate. *e 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 5.6. Genetic Operators the algorithm is trapped into a local optimal solution too early. 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 chro- 5.6.3. Crossover. Two individuals are chosen as parents each mosome i randomly to generate a new chromosome j, and time and a random number δ is generated within the range the objective value f(j) of chromosome j is recalculated. [0, 1). If δ is greater than or equal to the given crossover rate Chromosome j is accepted or rejected to replace chromo- λ , the crossover operator is not used and the two parents are some i according to the probability P (r ) in the following ij k reserved as children directly. Otherwise, the 2-opt crossover equation: operator is performed. Figure 6 shows an example of the f(j) − f(i) crossover operator where both the number of trains (i.e., |L|) P r 􏼁 � min􏼨1, exp􏼠− 􏼡􏼩. (32) ij k and the number of platform tracks (i.e., |I|) are equal to 6. If P (r ) is greater than the random number δ gen- ij k 1 erated within the range [0, 1), then chromosome i is replaced 5.6.4. Mutation. For each gene of a chromosome, a random by chromosome j. Neighborhood search operator is an number δ is generated within the range [0, 1). If δ is 4 4 important feature of the SA algorithm and it can enlarge the smaller than the given mutation rate λ , then the mutation 12 Journal of Advanced Transportation Parent 1 5 2 3 6 1 4 Child 1 5 2 4 2 1 4 Parent 2 1 6 4 2 3 5 Child 2 1 6 3 6 3 5 Train 1 2 3 4 5 6 Train 1 2 3 4 5 6 Figure 6: Illustration of the crossover operator. operator is applied, i.e., a different platform track is ran- specifically, u is set to 1 and v is to 0 for all trains l ∈ L l,i,1 l,i,1 domly assigned to the gene. 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 w , y , and y are set 6. Numerical Experiments l,i l,a l,d to their initial values before the train delay occurs, i.e., *e proposed model is applied to a railway passenger station w � q , y � t , and y � t for all trains l ∈ L and l,i l,i l,a l,a l,d l,d as shown in Figure 7, with five platform tracks (I, 3, 5, 7, 9, platform tracks i ∈ I with the condition of t < S. l,a 11) in the downstream direction and four platform tracks (II, Based on the initial scheduled arrival and departure 4, 6, 8, 10) in the upstream direction. *e time unit Δτ is set times as well as the input data and parameters of 70 trains to 1 min, which is practical for ensuring safe train operations in Tables 3–7, a total of 21 scenarios are generated with the at the stations [22, 25, 37]. Moreover, there are 70 down- number of trains ranging from 10 to 70, and 3 scenarios stream and upstream trains, which need to conduct the are generated for each fixed number of trains. For in- necessary operations from 16:00 to 22:00. *e initial stance, three scenarios (10, 2, 0), (10, 2, 1), and (10, 2, 2) scheduled arrival and departure times of the 70 trains are are generated when the number of trains is equal to 10. available at a repository on the ResearchGate website (DOI: Specifically, the first number “10” in the triple (10, 2, 0) 10.13140/RG.2.2.18253.79849), and trains are assigned with denotes the number of trains, the second number “2” in priority values ranging from 1 to 3. *e initial platform track the triple (10, 2, 0) represents the number of delayed assignment plan is listed in Table 3, and the corresponding trains. Besides, the third number in a triple can take the initially scheduled train operation plan is illustrated in values of 0, 1, and 2 corresponding to the three scenarios, Figure 8. Additionally, the platform track assignment costs so that the estimated arrival and departure times for for the downstream and upstream trains are given in Tables 4 delayed trains in Table 6 are randomly increased with and 5, respectively. In particular, there is a penalty of 10,000 values in the ranges of (0, 0), (− 1, 1), and (− 2, 2), for trains that use the platform tracks in the opposite respectively. direction. *e MILP models for the 21 scenarios in Section 4 are *e train delay information is available at the time of 18: solved by the commercial solver CPLEX 12.7.0 with (i.e., 38, and it is known that 6 downstream trains and 4 upstream CPLEX-WV) and without (i.e., CPLEX-WOV) including the trains are delayed, and the estimated arrival and departure valid inequalities in Section 4.5. Furthermore, the maximum times of those delayed trains are provided in Table 6. computation times of CPLEX-WV and CPLEX-WOV are Moreover, the 10 delayed trains in both directions are both set to 3600 s. *e GSAHA is implemented in C++ marked with the blue colour in Figure 8. Table 7 provides the programming language. Moreover, the algorithmic pa- parameter values used in the model. *e maximum value of rameters for GSAHA are set as follows. *e number of dwell times of all trains Δ equals 43 min, and the length of individuals in the population N is 50, the maximum number max the planning horizon T equals 360 min. *e safety time of generations K is 300, the crossover rate λ is 0.98, the interval on the platform track D equals 6 min, and the mutation rate λ is 0.1, the initial temperature R is 80,000 C, headway between two arrival trains h and the headway the temperature decline rate η is 0.9, and the temperature is between two departure trains h in the same direction are increased to R � 40,000 C if the objective value of the best d 1 both set to 5 min. *e weighting factor α in the objective individual in the current generation remains unchanged for function is set to 200, which is determined after discussing m � 5 iterations and n � 3 times of neighborhood search with the train dispatchers, and the value of α can be adjusted operations are performed each time. In addition, all of the flexibly according to the preferences of the train dispatchers. models and algorithms are tested on a computer with Intel Note that the value of α can be flexibly adjusted by the train (R) Core (TM) i7-5600U 2.6 GHZ CPU and 12G RAM. Tables 8 and 9 list the detailed computation results of dispatchers according to their experiences. In addition, we believe that keeping trains on time with guaranteed train CPLEX-WOV, CPLEX-WV, and GSAHA for the 21 sce- service quality is more important than assigning the trains to narios. More specifically, the columns “Obj 1 value (min)” their preferred platform tracks, and thus the penalty pa- and “Obj 2 value” in Table 8 represent the two components rameters on train delays are relatively larger than the of objective values, i.e., the sum of train arrival and departure platform track occupancy costs. Moreover, when the values delays and total platform track assignment costs, respec- of input parameters are known, the initial values of the tively. In Table 9, the column “Obj value” denotes the overall decision variables should be set in advance before running objective values, the column “CPU time (s)” represents the the GSAHA algorithm or commercial solvers. More computation times in sections, and the column “GAP with Journal of Advanced Transportation 13 80 36 7 34 71 48 Downstream entrance Downstream exit 61 63 74 44 19 11 13 21 23 33 35 55 75 32 30 24 22 16 14 4 2 59 72 40 7 19 6 37 56 50 49 18 II 39 47 28 26 20 12 10 8 35 15 17 29 31 41 51 58 53 66 Upstream exit 43 52 Upstream entrance 45 85 Figure 7: Layout of the railway passenger station. Table 3: Initial platform tack assignment plan between 16:00 and 22:00. Platform track number Occupation trains 11 T , T 9 29 9 T , T , T , T , T 5 19 31 41 49 7 T , T , T , T , T , T , T , T , T 11 21 27 33 43 47 55 63 69 5 T , T , T , T , T , T , T , T , T , T 1 7 15 25 35 39 53 61 67 73 3 T , T , T , T , T , T , T , T , T , T , T , T 3 13 17 23 37 45 51 57 59 65 71 75 II 4 T , T , T , T , T , T , T , T , T , T , T , T 2 8 18 22 30 34 40 42 48 54 60 64 6 T , T , T , T , T , T , T , T , T , T 4 12 16 24 32 38 44 50 56 62 8 T , T , T , T , T , T , T , T 6 14 20 28 36 46 52 58 10 T , T 10 26 T T 9 29 T T T T T 5 19 31 41 49 T T T T T T T T T 11 21 27 33 43 47 55 63 69 T T T T T T T T T T 15 25 35 39 53 61 67 73 1 7 T T T T T T T T T T T T 3 13 17 23 37 45 51 57 59 65 71 75 II T T T T T T T T T T T T 2 8 18 22 30 34 40 42 48 54 60 64 T T T T T T T T T T 4 12 16 24 32 38 44 50 56 62 T T T T T T T T 6 14 20 28 36 46 52 58 T T 10 26 16:00 17:00 18:00 19:00 20:00 21:00 22:00 Figure 8: Initial platform track utilization scheme between 16:00 and 22:00. 14 Journal of Advanced Transportation Table 4: Platform track assignment costs for downstream trains with different priorities. Platform track number Train direction Train priority I 3 5 7 9 11 1 600 6 12 24 48 96 Downstream 2 300 3 6 12 24 48 3 200 2 4 8 16 32 Table 5: Platform track assignment costs for upstream trains with different priorities. Platform track number Train direction Train priority II 4 6 8 10 II 1 600 6 12 24 48 600 Upstream 2 300 3 6 12 24 300 3 200 2 4 8 16 200 Table 6: Estimated arrival and departure times for delayed trains. Train Arrival delay Expected arrival time Expected departure time Dwell time Priority T 20 187 210 23 1 T 25 197 209 12 3 T 25 203 220 17 3 T 27 211 227 16 1 T 30 240 260 20 3 T 30 266 286 20 3 T 30 202 217 15 3 T 32 227 250 23 3 T 35 235 243 8 3 T 40 272 283 11 1 Table 7: Input parameters of the model. Parameter Value Maximum value of dwell times of all trains Δ 43 min max Length of the planning horizon T 360 min Safety time interval for platform track operation D 6 min Sum of the length of the planning horizon and the safety time interval for platform track operation MT 366 min Headway between two arrival trains h 5 min Headway between two departure trains h 5 min Objective function weighting factor α 200 CPLEX-WV (%)” indicates the relative gap between the speed up the solving process of CPLEX. More specifically, objective values of GSAHA and CPLEX-WV. CPLEX-WOV cannot obtain optimal solutions for the in- *ree points can be drawn from the computation results stances with the number of trains larger than or equal to 60 in Tables 8 and 9. First, the computation times of CPLEX- trains within 3600 s, which results in large objective values. In order to illustrate the feasibility of our proposed MILP WOV, CPLEX-WV, and GSAHA increase gradually as the number of trains increases, and the maximum computation model, the optimization solution of the scenario (70, 10, 0) times of those three solution methods are equal to 3600 s, using CPLEX-WV is illustrated in detail. Table 10 shows that 679.48 s, and 28.96 s, respectively. In particular, even if the arrival and departure times of 11 trains are delayed after CPLEX is sped up with the valid inequalities, the compu- the reoptimization, and the new platform track assignment tation times of GSAHA are still much fewer than that of plan is provided in Table 11. Besides, the platform track CPLEX. *erefore, it can be shown that our proposed utilization scheme is illustrated in Figure 9, and it can be GSAHA can solve the reoptimization problem more effi- seen from Figure 9 that all safety headway requirements are ciently in a real-time manner. Second, the objective values of satisfied. Note that the 14 trains in Table 11 with bold fonts GSAHA are close to those of CPLEX-WV with the maxi- represent that those trains have been reassigned to different mum gap value equal to 5.66%. *ird, after comparing the platform tracks, and those 14 trains are marked with the red colour in Figure 9. Besides, the convergence process of computation times of CPLEX-WOV and CPLEX-WV, it can be seen the valid inequalities in Section 4.5 can significantly Journal of Advanced Transportation 15 Table 8: Two components of objective values of CPLEX-WOV, CPLEX-WV, and GSAHA under different scenarios. CPLEX-WOV CPLEX-WV GSAHA Scenario Obj 1 value (min) Obj 2 value Obj 1 value (min) Obj 2 value Obj 1 value (min) Obj 2 value (10, 2, 0) 800 50 800 50 800 50 (10, 2, 1) 1200 50 1200 50 1200 50 (10, 2, 2) 800 50 800 50 800 50 (20, 3, 0) 1200 174 1200 174 1200 188 (20, 3, 1) 1800 174 1800 174 1800 174 (20, 3, 2) 1400 174 1400 174 1400 174 (30, 4, 0) 5200 278 5200 278 5200 286 (30, 4, 1) 5600 282 5600 282 5600 294 (30, 4, 2) 4400 278 4400 278 4400 283 (40, 6, 0) 800 363 800 363 800 379 (40, 6, 1) 1200 363 1200 363 1200 385 (40, 6, 2) 1200 363 1200 363 1200 395 (50, 7, 0) 8400 469 8400 469 8400 533 (50, 7, 1) 7000 469 7000 469 7000 545 (50, 7, 2) 8200 469 8200 469 8200 513 (60, 9, 0) 340400 1600 23600 583 24400 737 (60, 9, 1) 722400 2885 24200 575 25000 682 (60, 9, 2) 237800 2647 18200 579 18200 690 (70, 10, 0) 195400 1989 16400 659 16848 764 (70, 10, 1) 161600 1593 16800 685 17600 768 (70, 10, 2) 149800 2708 14600 659 15400 722 Table 9: Objective values and computation times of CPLEX-WOV, CPLEX-WV, and GSAHA under different scenarios. CPLEX-WOV CPLEX-WV GSAHA Scenario Obj value CPU time (s) Obj value CPU time (s) Obj value CPU time (s) GAP with CPLEX-WV (%) (10, 2, 0) 850 124.31 850 8.17 850 2.40 0 (10, 2, 1) 1250 51.73 1250 8.75 1250 2.43 0 (10, 2, 2) 850 67.49 850 8.23 850 2.34 0 (20, 3, 0) 1374 361.25 1374 24.66 1388 3.21 1.02 (20, 3, 1) 1974 377.20 1974 25.19 1974 3.10 0 (20, 3, 2) 1574 340.83 1574 24.02 1574 3.33 0 (30, 4, 0) 5478 326.84 5478 46.05 5486 4.75 0.15 (30, 4, 1) 5882 517.27 5882 53.25 5894 5.22 0.20 (30, 4, 2) 4678 208.92 4678 37.53 4683 5.01 0.11 (40, 6, 0) 1163 766.13 1163 46.30 1179 7.78 1.38 (40, 6, 1) 1563 480.83 1563 53.66 1585 7.83 1.41 (40, 6, 2) 1563 954.16 1563 55.27 1595 7.85 2.05 (50, 7, 0) 8869 1335.45 8869 105.22 8933 12.86 0.72 (50, 7, 1) 7469 1010.09 7469 87.42 7545 13.32 1.02 (50, 7, 2) 8669 1052.38 8669 121.58 8713 12.79 0.51 (60, 9, 0) 342000 3600 24183 661.22 25137 20.25 3.94 (60, 9, 1) 725285 3600 24775 678.17 25682 20.07 3.66 (60, 9, 2) 240447 3600 18779 604.38 18890 21.61 0.59 (70, 10, 0) 197389 3600 17059 679.48 17612 27.08 3.24 (70, 10, 1) 163193 3600 17485 344.52 18368 27.89 5.05 (70, 10, 2) 152508 3600 15259 529.75 16122 28.96 5.66 GSAHA is shown in Figure 10, where the algorithm can removing the second part of the objective function, which is reach the near-optimal solution only after 70 iterations. aimed to simulate the case that α takes an infinity value. *e Meanwhile, for the scenario (70, 10, 0) in Tables 8 and 9, optimization results of CPLEX-WV and GSAHA are listed sensitivity analysis of different values of weighting factor α is in Table 12, and the parameter settings for the GSAHA performed by increasing the value of α from 0 to 10 with the remain unchanged. In addition, we take the objective value step size equal to 1 for small values of α and from 40 to 440 of GSAHA for the average optimization results of 20 runs. It with the step size equal to 40 for relatively larger values of α. can be shown that the objective values of CPLEX-WV and Moreover, one special case is designed by setting α � 1 and GSAHA increase as the value of α increases, and the solution 16 Journal of Advanced Transportation Table 10: Amount of secondary delay for the trains obtained by CPLEX-WV for the scenario (70, 10, 0). Train Priority Secondary arrival delay (min) Secondary departure delay (min) T 1 0 4 T 3 0 2 T 3 0 3 T 3 2 2 T 3 2 2 T 1 5 5 T 2 2 2 T 1 2 2 T 1 0 1 T 3 2 2 T 1 2 2 Table 11: Platform tack assignment plan after the reoptimization using CPLEX-WV for the scenario (70, 10, 0). Platform track number Occupation trains 11 T , T 9 29 9 T , T , T , T , T , T 5 19 31 41 49 55 7 T , T , T , T , T , T , T , T 11 21 27 33 43 53 63 69 5 T , T , T , T , T , T , T , T , T , T 1 7 15 25 35 45 47 61 67 73 3 T , T , T , T , T , T , T , T , T , T , T , T 3 13 17 23 37 39 51 57 59 65 71 75 II 4 T , T , T , T , T , T , T , T , T , T , T , T 2 8 18 22 28 34 40 42 48 44 60 64 6 T , T , T , T , T , T , T , T , T , T , T 4 12 16 24 30 32 38 50 54 58 62 8 T , T , T , T , T 6 14 20 46 56 10 T , T , T , T 10 26 36 52 T T 9 29 T T T T T T 5 19 31 41 49 55 T T T T T T T T 11 21 27 33 43 53 63 69 T T T T T T T T T T 1 7 15 25 35 45 47 61 67 73 T T T T T T T T T T T T 3 13 17 23 37 39 51 57 59 65 71 75 II T T T T T T T T T T T T 2 8 18 22 28 34 40 42 48 44 60 64 T T T T T T T T T T T 4 12 16 24 30 32 38 50 54 58 62 T T T T T 6 14 20 46 56 T T T T 10 26 36 52 16:00 17:00 18:00 19:00 20:00 21:00 22:00 Figure 9: Platform track utilization scheme after the reoptimization using CPLEX-WV for the scenario (70, 10, 0). Journal of Advanced Transportation 17 85,000 80,000 75,000 70,000 65,000 60,000 55,000 50,000 45,000 40,000 35,000 30,000 25,000 20,000 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 Number of iterations Figure 10: Convergence process of GSAHA for the scenario (70, 10, 0). Table 12: Optimization results of CPLEX-WV and GSAHA with different values of weighting factor α. CPLEX-WV GSAHA Weighting Obj 1 value Obj 2 Obj CPU time Obj 1 value Obj 2 Obj CPU time GAP with CPLEX- factor α (min) value value (s) (min) value value (s) WV (%) 0 0 587 587 3600 0 477 477 32.92 − 18.74 1 104 621 725 490.90 112 651 763 30.85 5.24 2 164 659 823 541 188 670 858 28.97 4.25 3 246 659 905 540.47 270 672 942 29.05 4.09 4 328 663 991 607.41 336 697 1033 29.17 4.24 5 410 663 1073 731.23 420 704 1124 29.33 4.75 6 492 659 1151 544.47 504 706 1210 29.02 5.13 7 574 659 1233 547.19 588 702 1290 28.99 4.62 8 656 663 1319 651.16 672 709 1381 29.07 4.70 9 738 669 1407 934.73 756 704 1460 29.09 3.77 10 820 663 1483 718.23 841 715 1556 28.30 4.92 40 3280 659 3939 740.22 3376 764 4140 27.60 5.10 80 6560 659 7219 589.28 6736 771 7507 28.20 3.99 120 9840 659 10499 764.37 10142 772 10914 27.52 3.95 160 13120 663 13783 447.63 13449 784 14233 27.51 3.26 200 16400 659 17059 679.48 16848 764 17612 27.08 3.24 240 19680 659 20339 388.56 20182 769 20951 27.25 3.01 280 22960 659 23619 359.88 23468 874 24342 27.49 3.06 320 26240 659 26899 595.69 26924 757 27681 27.65 2.91 360 29520 659 30179 329.28 30261 808 31069 28.23 2.95 400 32800 659 33459 340.13 33631 771 34402 28.77 2.82 440 36080 659 36739 412.67 37089 719 37808 28.22 2.91 ∞ 82 0 82 256.36 84 0 84 30.04 2.44 times of CPLEX-WV range from 256.36 to 3600 seconds while GSAHA can obtain a solution that is much smaller while the solution times of GSAHA only range from 27.08 to than that of CPLEX-WV. In addition, for the case of α � ∞, 32.92 seconds. *e last column in Table 12 shows that the it can be shown that the minimum value of the first part of objective values of GSAHA are − 18.74%–5.10% larger than the objective function is equal to 82 min, and GSAHA can those of CPLEX-WV. In particular, CPLEX-WV cannot also obtain an objective value of 84 min. Note that the obtain the optimal solution for α � 0 within the time limit, optimality gaps of GSAHA compared with CPLEX could be Objective value 18 Journal of Advanced Transportation due to two reasons in particular. First, the spatial and Data Availability temporal resources are allocated separately in GSAHA. *e data used to support the findings of this study are Second, a heuristic method is developed to resolve the available from the corresponding author upon request. temporal conflicts between trains. Overall, the stable per- formance of GSAHA regarding the solution quality and solving times shows that our proposed GSAHA is suitable to Conflicts of Interest serve as an effective computer-aided decision-making tool for the train dispatchers in case of train delays. *e authors declare that they have no conflicts of interest. 7. Conclusions Acknowledgments *e problem of reoptimization of the train platforming is *is study was supported by the National Key R&D Program essential in recovering the train operations within the station (grant no. 2017YFB1200700), National Natural Science while minimizing the negative impact of train delays. *is Foundation of China (grant no. U1834209), and Open Fund paper proposes a MILP model for the reoptimization Project of Chongqing Key Laboratory of Traffic & Trans- problem, where the train station is represented with the portation (grant no. 2018TE01). discretized platform track time-space resources. In addition, a set of valid inequalities is developed to improve the per- References formance of the commercial solver. In addition, in order to achieve the real-time reoptimization of the train platforming [1] National Bureau of Statistics of China, 2020, http://data.stats. problem and provide a reliable decision tool for the train gov.cn/english/easyquery.htm?cn=C01. dispatchers, a heuristic algorithm called GSAHA that [2] R. M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan, “Railway combines the advantages of SA and GA algorithms is track allocation: models and methods,” OR Spectrum, vol. 33, designed. Moreover, GSAHA first allocates the spatial re- no. 4, pp. 843–883, 2011. sources for the trains, and the temporal conflicts between [3] A. A. Assad, “Models for rail transportation,” Transportation trains are further resolved through a specialized heuristic Research Part A: General, vol. 14, no. 3, pp. 205–220, 1980. rule. To test the efficiency and effectiveness of the proposed [4] J.-F. Cordeau, P. Toth, and D. Vigo, “A survey of optimization models for train routing and scheduling,” Transportation model and algorithm, a set of real-life instances is solved by a Science, vol. 32, no. 4, pp. 380–404, 1998. commercial solver and GSAHA. *e computational results [5] U. Brannlund, ¨ P. O. Lindberg, A. Nõu, and J.-E. Nilsson, show the proposed MILP model can effectively achieve the “Railway timetabling using Lagrangian relaxation,” Trans- reoptimization of the train platforming problem, and the portation Science, vol. 32, no. 4, pp. 358–369, 1998. proposed heuristic algorithm can further speed up the [6] A. Caprara, M. Fischetti, and P. Toth, “Modeling and solving solving process of the commercial solver with near-optimal the train timetabling problem,” Operations Research, vol. 50, solutions. In addition, the computational results also show no. 5, pp. 851–861, 2002. that the performance of GSAHA is stable even when the [7] Y. Zhang, Q. Peng, Y. Yao, X. Zhang, and X. Zhou, “Solving values of weighting factor α vary from 40 to 440. cyclic train timetabling problem through model reformula- *e work in this paper can be extended in the following tion: extended time-space network construct and Alternating several interesting directions. First, instead of ensuring the Direction Method of Multipliers methods,” Transportation Research Part B: Methodological, vol. 128, pp. 344–379, 2019. arrival and departure safety headway between two different [8] Y. Zhang, A. D’Ariano, B. He, and Q. Peng, “Microscopic trains running in the same direction, the explicit consid- optimization model and algorithm for integrating train eration of train entrance and exit route conflicts can increase timetabling and track maintenance task scheduling,” Trans- the station throughput capacity and reduce the train delays portation Research Part B: Methodological, vol. 127, pp. 237– [10, 20]. Second, the MILP model and the heuristic algo- 278, 2019. rithm GSAHA proposed in this paper can be further de- [9] L. G. Kroon, H. Edwin Romeijn, and P. J. Zwaneveld, veloped to consider different station types, such as the “Routing trains through railway stations: complexity issues,” terminal station where trains need to perform the turn- European Journal of Operational Research, vol. 98, no. 3, around movement that makes the train platforming problem pp. 485–498, 1997. more complicated [42, 43]. *ird, the train movements at [10] P. J. Zwaneveld, L. G. Kroon, H. E. Romeijn et al., “Routing the stations can be viewed as a set of space-time paths, and trains through railway stations: model formulation and al- gorithms,” Transportation Science, vol. 30, no. 3, pp. 181–194, thus more efficient dual decomposition methods could be developed accordingly [7, 44, 45]. Fourth, more efficient [11] P. J. Zwaneveld, L. G. Kroon, and S. P. M. Van Hoesel, solution algorithms can be developed for the simultaneous “Routing trains through a railway station based on a node reoptimization of several interconnected railway stations in packing model,” European Journal of Operational Research, a railway line or even a regional railway network with more vol. 128, no. 1, pp. 14–33, 2001. complicated structure so that the joint optimization of delay [12] R. Lusby, J. Larsen, D. Ryan, and M. Ehrgott, “Routing trains situations and train timetabling problems can be achieved through railway junctions: a new set-packing approach,” [8, 19, 27, 46–49]. Finally, the integration of energy-efficient Transportation Science, vol. 45, no. 2, pp. 228–245, 2011. train movement with the reoptimization of train platforming [13] R. M. Lusby, J. Larsen, M. Ehrgott, and D. M. Ryan, “A set can be considered for more system-wide benefits [50, 51]. packing inspired method for real-time junction train routing,” Journal of Advanced Transportation 19 Computers & Operations Research, vol. 40, no. 3, pp. 713–724, [30] M. J. Dorfman and J. Medanic, “Scheduling trains on a railway 2013. network using a discrete event model of railway traffic,” [14] V. Cacchiani, D. Huisman, M. Kidd et al., “An overview of Transportation Research Part B: Methodological, vol. 38, no. 1, recovery models and algorithms for real-time railway pp. 81–98, 2004. rescheduling,” Transportation Research Part B: Methodolog- [31] A. D’ariano, D. Pacciarelli, and M. Pranzo, “A branch and ical, vol. 63, pp. 15–37, 2014. bound algorithm for scheduling trains in a railway network,” [15] L. Meng and X. Zhou, “Robust single-track train dispatching European Journal of Operational Research, vol. 183, no. 2, model under a dynamic and stochastic environment: a sce- pp. 643–657, 2007. [32] J. Rodriguez, “A constraint programming model for real-time nario-based rolling horizon solution approach,” Trans- portation Research Part B: Methodological, vol. 45, no. 7, train scheduling at junctions,” Transportation Research Part B: pp. 1080–1102, 2011. Methodological, vol. 41, no. 2, pp. 231–245, 2007. [16] L. Meng and X. Zhou, “Simultaneous train rerouting and [33] A. D’Ariano, L. Meng, G. Centulio, and F. Corman, “Inte- rescheduling on an N-track network: a model reformulation grated stochastic optimization approaches for tactical with network-based cumulative flow variables,” Trans- scheduling of trains and railway infrastructure maintenance,” portation Research Part B: Methodological, vol. 67, pp. 208– Computers & Industrial Engineering, vol. 127, pp. 1315–1335, 234, 2014. [17] S. Zhan, L. G. Kroon, L. P. Veelenturf, and J. C. Wagenaar, [34] T. M. Herrman, Stability of timetables and train routings through station regions, Ph.D. thesis, Swiss Federal Insitute of “Real-time high-speed train rescheduling in case of a complete blockage,” Transportation Research Part B: Methodological, Technology Zurich, Zurich, ¨ Switzerland, 2006. [35] N. Beˇsinovi´c and R. M. Goverde, “Stable and robust train vol. 78, pp. 182–201, 2015. [18] S. Zhan, L. G. Kroon, J. Zhao, and Q. Peng, “A rolling horizon routing in station areas with balanced infrastructure capacity approach to the high speed train rescheduling problem in case occupation,” Public Transport, vol. 11, no. 2, pp. 211–236, of a partial segment blockage,” Transportation Research Part 2019. E: Logistics and Transportation Review, vol. 95, pp. 32–61, [36] A. D’Ariano and M. Pranzo, “An advanced real-time train dispatching system for minimizing the propagation of delays [19] M. Carey, “A model and strategy for train pathing with choice in a dispatching area under severe disturbances,” Networks and Spatial Economics, vol. 9, no. 1, pp. 63–84, 2009. of lines, platforms, and routes,” Transportation Research Part B: Methodological, vol. 28, no. 5, pp. 333–353, 1994. [37] W. Liu, X. Zhu, and L. Kang, “Real-time track reallocation for emergency incidents at large railway stations,” Mathematical [20] P. Chakroborty and D. Vikram, “Optimum assignment of trains to platforms under partial schedule compliance,” Problems in Engineering, vol. 2015, Article ID 296394, Transportation Research Part B: Methodological, vol. 42, no. 2, 11 pages, 2015. pp. 169–184, 2008. [38] L. Kang, S. Chen, and Q. Meng, “Bus and driver scheduling [21] A. Caprara, L. Galli, and P. Toth, “Solution of the train with mealtime windows for a single public bus route,” platforming problem,” Transportation Science, vol. 45, no. 2, Transportation Research Part C: Emerging Technologies, pp. 246–257, 2011. vol. 101, pp. 145–160, 2019. [22] L. Kang, Z. Lu, and Q. Meng, “Stochastic schedule–based [39] W. Xing and J. Xie, Modern Optimization optimization model for track allocations in large railway Methodspp. 113–147, Tsinghua University Press, Beijing, China, 2nd edition, 2006. stations,” Journal of Transportation Engineering, Part A: Systems, vol. 145, no. 3, Article ID 04019001, 2019. [40] H. Yu, H. Fang, P. Yao, and Y. Yuan, “A combined genetic algorithm/simulated annealing algorithm for large scale [23] D. D. L. Cardillo and N. Mione, “k L-list λ colouring of graphs,” European Journal of Operational Research, vol. 106, system energy integration,” Computers & Chemical Engi- no. 1, pp. 160–164, 1998. neering, vol. 24, no. 8, pp. 2023–2035, 2000. [24] A. Billionnet, “Using integer programming to solve the train- [41] H. Du, J. Fan, X. He, and M. W. Feldman, “A genetic sim- platforming problem,” Transportation Science, vol. 37, no. 2, ulated annealing algorithm to optimize the small-world network generating process,” Complexity, vol. 2018, Article ID pp. 213–222, 2003. [25] P. Sels, P. Vansteenwegen, T. Dewilde, D. Cattrysse, 1453898, 12 pages, 2018. [42] Q. Zhong, R. M. Lusby, J. Larsen, Y. Zhang, and Q. Peng, B. Waquet, and A. Joubert, “*e train platforming problem: the infrastructure management company perspective,” “Rolling stock scheduling with maintenance requirements at the Chinese high-speed railway,” Transportation Research Transportation Research Part B: Methodological, vol. 61, pp. 55–72, 2014. Part B: Methodological, vol. 126, pp. 24–44, 2019. [26] M. Carey and S. Carville, “Scheduling and platforming trains [43] Q. Zhong, Y. Zhang, D. Wang, Q. Zhong, C. Wen, and at busy complex stations,” Transportation Research Part A: Q. Peng, “A mixed integer linear programming model for Policy and Practice, vol. 37, no. 3, pp. 195–224, 2003. rolling stock deadhead routing before the operation period in [27] M. Carey and I. Crawford, “Scheduling trains on a network of an urban rail transit line,” Journal of Advanced Trans- busy complex stations,” Transportation Research Part B: portation, vol. 2020, Article ID 3809734, 18 pages, 2020. [44] X. Zhou, L. Tong, M. Mahmoudi et al., “Open-source VRPLite Methodological, vol. 41, no. 2, pp. 159–178, 2007. [28] L. Kang, J. Wu, and H. Sun, “Using simulated annealing in a package for vehicle routing with pickup and delivery: a path finding engine for scheduled transportation systems,” Urban bottleneck optimization model at railway stations,” Journal of Transportation Engineering, vol. 138, no. 11, pp. 1396–1402, Rail Transit, vol. 4, no. 2, pp. 68–85, 2018. 2012. [45] X. Chen, S. He, Y. Zhang, L. Tong, P. Shang, and X. Zhou, [29] J. Wu, L. Kang, H. Sun, and X. Jia, “Track allocation opti- “Yard crane and AGV scheduling in automated container mization in railway station: mean-variance model and case terminal: a multi-robot task allocation framework,” Trans- study,” Journal of Transportation Engineering, vol. 139, no. 5, portation Research Part C: Emerging Technologies, vol. 114, pp. 540–547, 2013. pp. 241–271, 2020. 20 Journal of Advanced Transportation [46] L. Kang, J. Wu, H. Sun, X. Zhu, and B. Wang, “A practical model for last train rescheduling with train delay in urban railway transit networks,” Omega, vol. 50, pp. 29–42, 2015. [47] L. Kang, X. Zhu, H. Sun, J. Wu, Z. Gao, and B. Hu, “Last train timetabling optimization and bus bridging service manage- ment in urban railway transit networks,” Omega, vol. 84, pp. 31–44, 2019. [48] L. Kang and Q. Meng, “Two-phase decomposition method for the last train departure time choice in subway networks,” Transportation Research Part B: Methodological, vol. 104, pp. 568–582, 2017. [49] L. Kang, J. Wu, H. Sun, X. Zhu, and Z. Gao, “A case study on the coordination of last trains for the Beijing subway net- work,” Transportation Research Part B: Methodological, vol. 72, pp. 112–127, 2015. [50] W. Li, Q. Peng, Q. Li, C. Wen, Y. Zhang, and J. Lessan, “Joint operating revenue and passenger travel cost optimization in urban rail transit,” Journal of Advanced Transportation, vol. 2018, Article ID 7805168, 15 pages, 2018. [51] W. Li, Q. Peng, C. Wen, S. Li, X. Yan, and X. Xu, “Integrated optimization on energy saving and quality of service of urban rail transit system,” Journal of Advanced Transportation, vol. 2020, Article ID 3474020, 22 pages, 2020. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Advanced Transportation Hindawi Publishing Corporation

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

Loading next page...
 
/lp/hindawi-publishing-corporation/a-fast-approach-for-reoptimization-of-railway-train-platforming-in-NiWWUi7sZb

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Hindawi Publishing Corporation
Copyright
Copyright © 2020 Yongxiang Zhang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
ISSN
0197-6729
eISSN
2042-3195
DOI
10.1155/2020/5609524
Publisher site
See Article on Publisher Site

Abstract

Hindawi Journal of Advanced Transportation Volume 2020, Article ID 5609524, 20 pages https://doi.org/10.1155/2020/5609524 Research Article A Fast Approach for Reoptimization of Railway Train Platforming in Case of Train Delays 1,2,3 1,2,3 1,2,3 1,2,3 Yongxiang Zhang, Qingwei Zhong, Yong Yin , Xu Yan , 1,2,3 and Qiyuan Peng School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China National United Engineering Laboratory of Integrated and Intelligent Transportation, Southwest Jiaotong University, Chengdu 610031, China National Engineering Laboratory of Integrated Transportation Big Data Application Technology, Southwest Jiaotong University, Chengdu 610031, China Correspondence should be addressed to Yong Yin; yinyong@swjtu.edu.cn Received 18 January 2020; Revised 24 February 2020; Accepted 20 May 2020; Published 3 June 2020 Academic Editor: Yu Jiang Copyright © 2020 Yongxiang Zhang et al. *is is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Train platforming is critical for ensuring the safety and efficiency of train operations within the stations, especially when un- expected train delays occur. *is 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. *e 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. Moreover, the railway planning process includes the net- 1. Introduction work design and line planning at the strategic level, the train Railroad transportation plays an important role in providing timetabling, train platforming, rolling stock scheduling and economic and environment-friendly transport services for crew scheduling at the tactical level, and the real-time traffic passengers and goods. In particular, transport demand of management at the operational level [2]. As a result, the core railroad transportation is increasing rapidly in some parts of of the computer-aided decision systems is to develop ef- regional markets. For instance, according to the statistical fective optimization techniques for the different railway data of the National Bureau of Statistics of China, the volume planning and operation stages. We refer the readers to Assad of passenger and freight traffic of China railway in 2018 has [3], Cordeau [4], and Lusby et al. [2] for excellent surveys on increased by 9.44% and 9.15%, compared with the volume in the related optimization methods. In general, train time- 2017 [1]. *us, more and more trains are required to be tabling stage can determine the arrival and departure times operated on the railway network with limited infrastructure of the trains at each of the visiting stations from an aggregate capacity to satisfy the large demand. *erefore, the railway perspective [5–8]. Train operations at the stations, including operators need to adopt advanced and reliable computer- the train routing on the arrival and departure routes and the aided decision systems to improve train operation efficiency. train platform assignment decisions, are usually optimized 2 Journal of Advanced Transportation train sequencing variables in the big-M modeling by solving the train platforming problem [8]. Apart from the boarding and alighting of passengers as well as the loading framework can be avoided. and unloading of goods at the station platforms, many other (3) An efficient heuristic algorithm is designed to complicated operation tasks can be performed at the sta- quickly obtain the near-optimal solutions for the tions, such as the train turn-around movement and the real-time reoptimization of train platforming. shunting work. *us, it is of critical importance to develop (4) A set of real-life experiments is performed to show efficient and effective optimization techniques to improve the efficiency and effectiveness of the proposed the train operation efficiency at the stations without causing model and algorithm. any conflicts. *e rest of this paper is structured as follows. Section 2 Due to the complex layout of large railway stations and provides a comprehensive literature review on the optimi- the associated dense train traffic, it is usually a challenging zation and reoptimization of train platforming problems. task for the train dispatchers to make a high-quality train *e method on how to describe the discretized platform operation plan within a station in a short period. Kroon et al. track time-space resources is introduced in Section 3. In [9] have already proven that the train platforming problem is Section 4, we propose a new MILP model based on the an NP-complete combinational optimization problem. As a discretized platform track time-space resources, as well as result, many researchers have developed sophisticated and some valid equalities to strengthen the resulting MILP efficient models and algorithms to deal with the train plat- model. Section 5 presents the detailed algorithmic steps of a forming problem, such as the node packing model and the heuristic algorithm, i.e., the genetic and simulated annealing branch-and-cut algorithm in Zwaneveld et al. [10, 11] and the hybrid algorithm, for solving the reoptimization problem in set packing model and the branch-and-price algorithm in a real-time manner. *e efficiency and effectiveness of the Lusby et al. [12, 13]. In practice, however, trains may suffer proposed methods are verified through a set of real-life from all kinds of disturbances and disruptions, such as bad experiments in Section 6. Section 7 gives the concluding weather, equipment failure, and management factors [14]. remarks and possible further research directions. 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 2. Literature Review any potential conflicts [15–18]. However, with regard to the Train platforming problem is a key optimization stage in the train platforming problem, two managerial aspects lack in- railway hierarchical planning process, and it has attracted depth study. First, most of the researchers study the train the attention of many researchers around the world [2]. platforming problem without considering train delays, and Given the information of train arrival and departure times thus they do not consider the situation where it could be and the train running directions obtained at the train impossible to make a feasible train operation plan at the timetabling stage, the train dispatchers need to decide how stations with the given train timetable. Second, in order to to schedule the trains at the stations to avoid the train delays generate a disposition timetable during the train rescheduling caused by the cross interference between train operations. process as soon as possible, the detailed train operations at the *e complexity of the train platforming problem grows stations are neglected, and the aggregate station capacity is quickly as the number of trains increases and the station adopted instead [17, 18]. layout becomes more and more complicated. *erefore, a lot In this study, we aim to bridge the research gaps lying in of excellent works have been done regarding the train the train platforming and train rescheduling problems. More platforming problem, such as Carey [19], Zwaneveld et al. specifically, we reoptimize the train platforming problem in [10], Lusby et al. [12], Chakroborty and Vikram [20], case of train delays and generate a new train operation plan Caprara et al. [21], and Kang et al. [22]. We next review these within the station in real time. Our solution is to develop a works mainly from two aspects, i.e., the train platforming mixed integer linear programming (MILP) model, where the problem at the tactical level and the train platforming train station is modeled using the discretized platform track problem considering the negative impact of train delays. time-space resources, and to propose an efficient heuristic *e studies on the train platforming problem at the algorithm. *e goal of the proposed model and algorithm is tactical level were initially focused on scheduling the train to simultaneously minimize the deviation from the train movements at the stations efficiently and economically with timetable and the total train operating costs, realizing the the fixed or slightly relaxed train arrival and departure times. coherence between train operations and the station man- Zwaneveld et al. [10] developed the first node packing model agement. *e theoretical and practical contributions of this for the train platforming problem, and the station routes study mainly include the following four aspects: were classified as the inbound route, outbound route, and (1) *e train arrival and departure times and the train complete. In addition, small deviations from the planned platform assignment are optimized simultaneously train arrival and departure times were considered to increase so that the negative influence of train delays can be the possibility of finding a feasible solution, and an improved minimized. branch-and-cut algorithm was designed to find the optimal (2) *e novel modeling method based on the discretized solutions with the goal of maximizing the number of platform track time-space resources can describe the trains routed through the station. Kroon et al. [9] proved train conflicts accurately, where the complex binary that the node packing model in Zwaneveld et al. [10] was Journal of Advanced Transportation 3 searching method was adopted to solve the resulting model. NP-complete once each train had more than three routing possibilities. Based on the work in Zwaneveld et al. [10], In addition, the arrival and departure headways between two trains were enforced to guarantee the train running safety. Zwaneveld et al. [11] further proposed a weighted node packing model for the train platforming problem, where Dorfman and Medanic [30] proposed a discrete event model several hierarchical objectives can be considered with the to schedule the trains in the railway network, where the train unified weighted sum form. However, the node packing routes were assumed to be fixed for simplicity. D’ariano et al. model has its own deficiencies to be put into practice. For [31] formulated the train scheduling problem through the instance, all of the conflicting train movements need to be alternative graph modeling approach, and an efficient identified in advance in the node packing model, and it branch-and-bound algorithm was designed to solve the MILP model. Rodriguez [32] proposed a combined con- usually results in a large-scale optimization model. As a result, Lusby et al. [12] built a set packing model of the train straint programming and simulation method for scheduling trains in the junctions, where the constraint programming platforming problem, and a branch-and-price algorithm was designed such that the feasible train routes can be dy- model representing the signalling system behaviour and the simulation model can reflect the train and driver behaviour. namically generated. Besides, the train platforming problem can be also reformulated as a graph colouring problem, More recently, D’Ariano et al. [33] and Zhang et al. [8] where the number of colours is determined by the available studied the integrated train timetabling and maintenance tracks in the stations [23]. An integer programming model task scheduling problems at the microscopic level, and ef- that was equivalent to graph colouring problem in Cardillo ficient heuristic algorithms based on the commercial solvers and Mione [23] was developed by Billionnet [24]. Caprara were developed accordingly. et al. [21] also allowed a slight relaxation on the ideal arrival Some works were also performed on the optimization of a delay resistant train platforming plan and the real-time and departure times of the trains at the platforms, and they presented a 0-1 quadratic programming model to solve the reoptimization of train platforming problem in case of unexpected train delays. Herrman [34] studied the stable train platforming problem. In particular, the quadratic term in the objective function was designed to consider the soft train routing problem, where the goal was to keep the train schedule to be conflict-free as much as possible in case of incompatibility costs between train paths. Sels et al. [25] developed a new MILP model to schedule the trains in the perturbations. In addition, a local search heuristic approach current and future train set, and penalty costs were con- was designed to solve the train schedule stabilization ˇ ´ sidered in the objective when a train was cancelled or problem. Besinovic and Goverde [35] proposed a max-plus assigned to a different platform. automata model for the station capacity assessment and a Apart from the exact solution methods, some researchers delay propagation model for the robustness evaluation of the also developed heuristic algorithms for the train platforming train platforming plan. Based on these two models, the objectives of minimization of capacity occupation and problem [26–29]. Carey and Carville [26] introduced a se- quential construction heuristic algorithm for the train plat- maximization of robustness were then achieved with a heuristic approach. Kang et al. [22] introduced the concept forming problem at a single station, which was designed according to the train dispatchers’ manual methods. In ad- of stochastic schedule with uncertain train arrival and de- dition, trains can be delayed in the planning process to generate parture times, and a simulated annealing algorithm was a feasible solution, and the assignment of trains to the un- developed to solve the corresponding train platforming desired platforms was penalized. Carey and Crawford [27] problem. D’Ariano et al. [36] designed a rolling horizon further extended the work in Carey and Carville [26] by approach for the real-time train rescheduling problem, and considering the train scheduling and platforming problems at the alternative graph formulation was adopted for solving multiple stations, where those stations were connected by the smaller subproblem in each rolling period. Chakroborty several one-way lines. Similarly, trains can be also delayed when and Vikram [20] developed a MILP model for optimally allocating trains to the platform tracks, where the accurate they were scheduled from one station to the corresponding next station. Kang et al. [28] proposed a simulated annealing train arrival times can only be available shortly before the train arrives at the station such that trains could be reas- heuristic algorithm with the goal of achieving the balanced occupation of station turnouts while minimizing the total signed to different platforms. Besides, the headway between occupation times of the station turnouts. Wu et al. [29] de- two trains was also considered while delaying the train veloped a mean-variance optimization model for the train arrival and departure times. Lusby et al. [13] proposed a set platforming problem based on Markowitz’s portfolio theory, packing model for rescheduling the trains in the junctions in which was aimed to minimize the total occupation time costs of case of disruptions. In particular, a branch-and-price al- groups of turnouts. Moreover, an efficient simulated annealing gorithm was introduced to solve the set packing model, and the objective was to minimize the weighted deviations from heuristic algorithm was designed to solve the resulting mixed integer nonlinear programming (MINLP) model. the trains’ scheduled arrival times. Liu et al. [37] developed a MINLP model to reallocate the tracks of trains at the stations Some researchers also tried to integrate the two stages of train timetabling and train platforming problems to further in a real-time manner, where the goal was to minimize average use time of groups of turnouts without changing the increase the railway network capacity utilization. Carey [19] proposed an integrated optimization model to simulta- planned train times. Moreover, a genetic simulated neously optimize the lines, platforms, and routes of the annealing algorithm was also designed to solve the MINLP trains in a railway network, and an improved sequential model efficiently. 4 Journal of Advanced Transportation Table 1 summarizes the modeling approaches, objectives, corresponding matrix R of a feasible usage plan are de- solution methods, and other characteristics of relevant scribed in Figures 2(a) and 2(b), respectively. *e application publications on the optimization and reoptimization of train requirements of the time-space resources modeling method platforming problems, and major highlights can be drawn for the reoptimization of train platforming problem can be from Table 1. First, most of the studies focus on the train formulated as follows: platforming problem at the tactical level, and the scheduled (1) Inseparability. A train must occupy only one plat- train arrival and departure times at the stations are usually form track and cannot occupy more than one assumed to be fixed. *erefore, the optimization objectives platform track simultaneously. of those studies are generally minimizing the total costs or (2) Exclusivity. One platform track can only store one maximizing the total benefits. Second, exact algorithms train at any time unit to prevent the train conflicts. account for the majority of the solution methods to solve the optimization or reoptimization of the train platforming (3) Continuity. A train operation on one platform track problems. *erefore, efficient and flexible heuristic algo- with the duration equal to Δt time units cannot be rithms are required, especially for the real-time reoptim- interrupted. If one train starts to use track i at time t, ization of the train platforming problem. *ird, among the it continues to occupy the platform track i until studies that consider the negative influence of train delays, t + Δt, i.e., r � r � r � . . . � r � 1. i,t i,t+1 i,t+2 i,t+Δt only one research by Chakroborty and Vikram [20] si- multaneously incorporates the factors of train delay, reas- 4. Mathematical Modeling for signment of platform, and deviations from scheduled train Reoptimization of Train Platforming arrival and departure times. However, they adopt a com- mercial solver to deal with the MILP model. In this study, we 4.1. Modeling Assumptions. Without loss of generality, we develop a new MILP model for the reoptimization of the make the following key modeling assumptions to facilitate train platforming problem based on the discretized time- the modeling process. space resources, and we also design an efficient heuristic (1) When it is impossible to eliminate the conflicts algorithm to guarantee the achievement of real-time through reassignment of platforms, the train arrival reoptimization. and departure times can only be delayed to resolve the conflicts. 3. Analysis of Platform Track Time- (2) One minute is applied to discretize the platform Space Resources track time-space resources, and smaller time units can be adopted if necessary. Let T be the planning horizon; we handle the time resources as small time units of length Δτ. *e number of time units is (3) Trains are modeled as single objects moving in the equal to |T| � [T/Δτ] in the entire planning horizon. In railway station, and thus the influence of train addition, the number of platform tracks in a station is lengths on the clearing times of the platform tracks is denoted by |I|, i.e., the maximum spatial capacity. Hence, the not considered. platform track time-space resources of a station can be (4) By enforcing the arrival and departure headways represented by a two-dimensional matrix R: between two trains running in the same direction as r r ... r well the safety time interval for platform track op- 1,1 1,2 1,|T | ⎢ ⎥ ⎡ ⎢ ⎤ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ eration, it can be guaranteed that there are no ⎢ ⎥ ⎢ ⎥ ⎢ r r ... r ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 2,1 2,2 2,|T | ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ conflicts between any two trains. R � 􏽨r 􏽩 � ⎢ ⎥, (1) ⎢ ⎥ i,t ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ... ... ... ... ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ (5) All trains will pass through the railway station, and r r ... r turn-around movements of the trains are not con- | I |,1 | I |,2 |I |, | T| sidered for simplicity. where i and t are the indexes of the platform track and the time unit, respectively, and a binary variable r in matrix R i,t denotes the occupation and vacancy state of the platform 4.2. Definitions of Sets, Parameters, and Variables. Sets, track time-space resource (i, t), where parameters, and variables of this study are defined in Table 2. In particular, we assume that all parameter values related to 1, platform track time − space resource (i, t) is used, r � 􏼨 time are multiples of the time unit Δτ. i,t 0, othewise. (2) 4.3. Objective Function. *e objective function in equation Figure 1 provides an illustrative example of the modeling (3) contains the weighted sum of two parts of costs. *e first method of platform track time-space resources. Suppose that part is the sum of train arrival and departure delays, con- 5 trains successively arrive at or depart from station N which sidering the train priority P and the weighting factor α. *e has 6 platform tracks within the planning horizon of 60 min. second part is the total platform track assignment costs. In *e detailed schedules of train operations in both directions particular, the more that train l is preferred for platform are given in Figures 1(b) and 1(c), and the time unit Δτ is set track i, the smaller is the corresponding platform track to 5 min. Platform track time-space resources and the assignment cost c . Note that value of c can be determined l,i l,i Journal of Advanced Transportation 5 Table 1: Summary of relevant publications on the optimization and reoptimization of the train platforming problems. Deviations Computation Modeling Solution Train Reassignment from Largest times (in Publication Objective approach method delay of platform scheduled instance solved seconds) of the train times largest instance A railway Max the Zwaneveld station with 17 BILP number of Branch-and-cut √ 85 et al. [10] platforms and routed trains 27 trains A railway Iterative Cardillo and station with 16 GC Feasibility heuristic 0.67 Mione [23] tracks and 242 algorithm trains A railway Billionnet Optimization station with 14 BILP Feasibility 1.64 [24] software tracks and 200 trains Min the costs of Iterative A railway deviations from Carey and sequential station with 29 MILP preferred times, √ √ — Carville [26] searching subproblems platforms, and method and 491 trains lines A 15.18 km Rodriguez long railway CP Min train delays Tree search √ √ 54.76 [32] junction with 24 trains A railway junction with Lusby et al. Max total Branch-and- BILP 64 block 26.4 [12] benefits price sections and 45 trains A railway Caprara et al. Branch-and- station with 14 BQP Min total costs 350 [21] cut-and-price platforms and 237 trains A railway Min total Commercial station with 14 Sels et al. [25] MILP √ 3.0 penalties solvers platforms and 160 trains Min total train A railway journey times Iterative network with Zhang et al. MILP and heuristic 27 stations, 55 7200 [8] maintenance algorithm segments, and tardiness costs 58 trains Genetic A railway Min average use simulated station with 11 Liu et al. [37] MINLP time of groups √ 1800 annealing tracks and 30 of turnouts algorithm trains Min total A railway occupation Kang et al. Simulated station with 11 MILP times and √ 726 [22] annealing tracks and 28 balanced track trains occupation A railway Chakroborty Commercial station with 9 and Vikram MILP Min total costs √ √ √ 600 solver platforms and [20] 110 trains A railway junction with Lusby et al. Min total Branch-and- BILP √ √ 524 track 151.55 [13] deviations price sections and 66 trains 6 Journal of Advanced Transportation Table 1: Continued. Deviations Computation Modeling Solution Train Reassignment from Largest times (in Publication Objective approach method delay of platform scheduled instance solved seconds) of the train times largest instance Genetic and A railway simulated station with 11 *is paper MILP Min total costs annealing √ √ √ 32.92 platforms and hybrid 70 trains algorithm Note. 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. Downstream entrance Downstream exit 27 4 2 3 9 13 25 24 20 16 23 35 7 11 22 19 12 II 37 28 8 1 5 15 17 21 30 14 10 Upstream exit Upstream entrance 39 32 (a) l l l l l 1 3 5 4 2 15 20 35 0 10 510 30 15 20 l l l l l 3 1 5 2 4 (b) (c) Figure 1: Layout and train timetables of station N: (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. Platform track Platform track 0 1 1100100 5 0 3 5 0 l l l 0 0 l 0 0 0 1000000 1 1 1 5 0 0 0000000 I 3 0 0 l 0 0 0 0 0 0 0 0 0000000 II I 0 0 0 0 0 0 0 0 0 0 4 0 1000000 111100000 6 II 0 0 0 0 0 0 0 0 0 t 5 10 15 20 25 30 35 40 45 4 0 0 l 0 0 0 0 0 0 6 l l l l 0 0 0 0 0 2 2 2 2 0 5 1015202530354045 t (a) (b) 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. according to several influence factors, including the initial min z � α 􏽘 P 􏽨􏼐y − t 􏼑 + 􏼐y − t − D􏼑􏽩 + 􏽘 􏽘 w c . l l,a l,a l,d l,d l,i l,i platform track assignment plan, the convenience of pas- i∈I l∈L l∈L senger boarding and alighting, and other special require- (3) ments for train operations. *erefore, the smaller the value of c is, the more the train l prefers the platform track i. l,i Journal of Advanced Transportation 7 4.4. Constraints 􏽘 x ≤ 1, ∀i ∈ I, t ∈ {1, 2, . . . , MT}. l,i,t (9) l∈L 4.4.1. Relation between Platform Track State Variables. According to definitions of platform track state variables x , u , and v , constraint (4) expresses the relationship l,i,t l,i,t l,i,t among those three platform track state variables. In par- 4.4.5. Continuous Train Operation on the Platform Track. ticular, when both the variables u and v are equal to 0, it Constraints (10)–(12) guarantee that train operations on the l,i,t l,i,t can be known that train l is occupying the platform track i at platform tracks should be performed continuously, by time t, i.e., x � 1. Figure 3 shows an illustrative example enforcing the relationship between the values of variables l,i,t on how to calculate the value of x according to the values u and v . For instance, if w � 1 in constraint (10), l,i,t l,i,t l,i,t l,i of the variables u and v . More specifically, train l which implies that train l is assigned to the platform track i, l,i,t l,i,t 1 arrives at the platform track 5 in Figure 1 at time 5 and it constraint (10) changes to u ≥ u . According to the l,i,t l,i,t+1 leaves from the corresponding platform track at time 20. definition of u in Section 4.2, the condition u ≥ u is l,i,t l,i,t l,i,t+1 *erefore, Figures 3(a) and 3(b) present the values of the obviously satisfied. On the other hand, if w � 0 in con- l,i variables u and v for train l according to its actual straint (10), constraint (10) is no longer valid. Similarly, l,i,t l,i,t 1 arrival and departure times. In addition, according to constraints (11) and (12) define the relationships between constraint (4), the values of v in Figure 3(c) can be easily v and v as well as between u and u . l,i,t l,i,t l,i,t+1 l,i,t l,i,t+1 obtained. u ≥ u + w − 1, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT − 1}, l,i,t l,i,t+1 l,i x � 1 − 􏼐u + v 􏼑, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}. l,i,t l,i,t l,i,t (10) (4) v ≤ v − w + 1, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT − 1}, l,i,t l,i,t+1 l,i (11) 4.4.2. Actual Train Arrival and Departure Times. u ≤ u + w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT − 1}. Constraints (5) and (6) show that values of actual arrival l,i,t l,i,t+1 l,i time y and actual departure time y of train l can be (12) l,a l,d inferred from the values of platform track utilization state variable u and the platform track clearance state variable l,i,t v . l,i,t 4.4.6. Safety Headway between Two Trains. Constraints MT (13)–(18) impose the required safety headway between two y � MT − 􏽘 􏽘􏼐1 − u 􏼑, ∀l ∈ L, (5) l,a l,i,t arrival or departure trains running in the same direction, and i∈I t�1 the train sequencing variables λ and μ as well as the l,k l,k MT platform track choice variables w and e are also embedded l,i l,k y � MT − 􏽘 􏽘 v , ∀l ∈ L. (6) in those constraints. Constraint (13) enforces the safety l,d l,i,t i∈I t�1 headway between two arrival trains in the same direction, and it is valid only if λ � 1, i.e., train l arrives at the station before l,k train k. When λ � 1 in constraint (13), it can be shown that l,k the safety headway between trains l and k depends on the 4.4.3. Platform Track Assignment Constraint. Constraint (7) value of the variable e . More specifically, if e � 1, trains l l,k l,k requires that each train l can only be assigned to one and k are assigned to the same platform track, and they are platform track, and the corresponding platform track has to separated by the safety time interval D. Otherwise, trains l and be in the set I . Furthermore, constraint (8) enforces that a k are assigned to two different platform tracks, and they are train l cannot be assigned to forbidden platform tracks, i.e., separated by the arrival headway h . Meanwhile, constraint tracks that are not in the set I . Constraints (7)-(8) provide a (14) guarantees the safety headway between two departure flexible method to restrict the platform track choices of the trains in the same direction. Constraint (15) ensures that if trains. both the variables w and w are equal to 1, the value of the l,i k,i variable e can be enforced to be 1. Furthermore, constraint l,k 􏽘 w � 1, ∀l ∈ L, l,i (7) (16) describes that the values of the two variables e and e l,k k,l i∈I for two different trains l and k are equal. Besides, constraints (17) and (18) guarantee that only one of the train sequencing w � 0, ∀l ∈ L, i ∈ I\I . (8) l,i l variables λ and λ or μ and μ between any two different l,k k,l l,k k,l trains is equal to 1. y − y ≥ 􏼐1 − e 􏼑h + e D − λ M, l,a k,a l,k a l,k l,k 4.4.4. Platform Track Capacity Constraint. Constraint (9) (13) ∀l, k ∈ L: l ≠ k, π � π , ensures that any platform track i can only be occupied by at l k most one train at any time t, such that no conflicts can occur between any two trains that are assigned to the same y − y ≥ 􏼐1 − e 􏼑h + e D − μ M, l,d k,d l,k d l,k l,k (14) platform track. ∀l, k ∈ L: l ≠ k, π � π , l k 8 Journal of Advanced Transportation Table 2: Sets, parameters, and variables. Symbol Definition Sets L Set of trains, indexed by l L Set of delayed trains, L ⊆L 1 1 I Set of platform tracks, indexed by i I Set of platform tracks that train l can utilize, I ⊆I l l T Set of time intervals in the planning horizon, indexed by t Parameters c Cost of assigning train l to platform track i l,i π 0-1 parameter is equal to 1 if train l is running in the downstream direction; 0, otherwise q 0-1 parameter is equal to 1 if train l was initially assigned to platform track i before a delay occurs; 0, otherwise l,i S *e time when the information of train delays is updated t Scheduled arrival time of train l l,a t Scheduled departure time of train l l,d t Estimated arrival time of train l when a delay occurs l,a t Estimated departure time of train l when a delay occurs l,d Δ Dwell time of train l P Priority of train l D Safety time interval for platform track operation MT Sum of the length of the planning horizon T and the safety time interval for platform track operation D Δ Maximum value of dwell times of all trains max h Headway between two arrival trains running in the same direction h Headway between two departure trains running in the same direction α Objective function weighting factor M A sufficiently large number Variables w 0-1 platform track assignment variable � 1 if train l is assigned to platform track i; � 0 otherwise l,i e 0-1 same platform track choice variable � 1 if train l and train k choose the same platform track; � 0 otherwise l,k x 0-1 platform track occupancy state variable � 1 if train l occupies platform track i at moment t; � 0 otherwise l,i,t u 0-1 platform track utilization state variable � 1 if train l has not yet arrived at platform track i at moment t; � 0 otherwise l,i,t v 0-1 platform track clearance state variable � 1 if train l has left platform track i at moment t; � 0 otherwise l,i,t λ 0-1 train arrival sequence variable � 1 if train l arrives at the station before train k; � 0 otherwise l,k μ 0-1 train departure sequence variable � 1 if train l departs from the station before train k; � 0 otherwise l,k y Actual arrival time of train l at the station l,a y Actual departure time of train l at the station l,d Platform track Platform track 5 1 0 0 0 0 0 0 0 0 5 001 01 0 11 1 3 1 1 1 1 1 1 1 1 1 3 0 0 0 0 0 0 0 0 0 I 1 1 1 1 1 1 1 1 1 I 0 0 0 0 0 0 0 0 0 II 1 1 1 1 1 1 1 1 1 II 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 4 0 0 0 0 0 0 0 0 0 6 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 5 1015202530354045 t 0 5 1015202530354045 t (a) (b) Platform track 5 01 1 1 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 II 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 5 1015202530354045 t (c) Figure 3: An illustrative example showing the values of platform track state variables u , v , and x : (a) values of the variable u ; l,i,t l,i,t l,i,t l,i,t (b) values of the variable v ; (c) values of the variable x , and x � 1− (u + v ). l,i,t l,i,t l,i,t l,i,t l,i,t Journal of Advanced Transportation 9 ranges of constrains (13)–(18), we simply approximate the e ≥ w + w − 1, ∀l, k ∈ L, i ∈ I ∩I : k > l, π � π , l,k l,i k,i l k l k number of constraints (13)–(18) without considering those (15) filter conditions. As a result, the upper bound on the number of constraints of the MILP model is equal to e � e , ∀l, k ∈ L: k > l, π � π , (16) l,k k,l l k MT|I|(2|L| + 1) + 6|L| + |L| (5 + |I|) + (|I| − |I |), l∈L l which increases polynomial as the number of trains |L|, the λ + λ � 1, ∀l, k ∈ L: k > l, π � π , (17) number of platform tracks |I|, and the length of planning l,k k,l l k horizon T increase. Similarly, the upper bound on the number of variables is equal to |L| · |I|(1 + MT) + |L| . μ + μ � 1, ∀l, k ∈ L: k > l, π � π . (18) l k l,k k,l 4.5. Valid Inequalities. Valid equalities are additional con- 4.4.7. Minimum Train Dwell Time Constraint. Constraint straints that have been implicitly satisfied according to other (19) enforces the minimum dwell time for each train l. In necessary model constraints (4)–(25). However, they can be particular, the right-hand side of constraint (19) can only be applied to strengthen the model formulation [17, 38]. valid when w � 1, i.e., train l is assigned to the platform Constraints (26)–(29) define the four valid inequalities that l,i track i. Note that the safety time interval for platform track are related to the variables u , v , x , and w . Note that l,i,t l,i,t l,i,t l,i operation D is also included in the right-hand side of the the valid inequalities are only implemented in a commercial constraints so that the required safety time interval for trains solver to speed up the solving process of the commercial assigned to the same platform track is imposed. In addition, solver. the minimum dwell time Δ of a train l is a deterministic u ≥ 1 − w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (26) l,i,t l,i value. MT v ≤ w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (27) l,i,t l,i 􏽘 x ≥ w Δ + D􏼁 , ∀l ∈ L, i ∈ I. (19) l,i,t l,i l t�1 x ≤ w , ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (28) l,i,t l,i 4.4.8. Actual Train Arrival Time and Departure Time x � 0, ∀l ∈ L, i ∈ I, t ∈ 􏽮1, 2, . . . , t − 1􏽯 ∨ t ∈ 􏽮t l,i,t l,a l,d Constraint. Constraints (20)–(22) specify that the actual + Δ + D + 1, . . . , MT . max arrival and departure times of the trains should be no less (29) than the corresponding planned arrival and departure times, respectively. Note that safety time interval D is introduced *e principles of building valid inequalities (26)–(29) are into the right-hand sides of constraints (21)-(22), such that similar. For instance, in valid inequality (26), if train l oc- the safety time interval D for platform track operation is cupies platform track i, then valid inequality (26) is implicitly satisfied between the departure time y of train l l,d equivalent to u ≥ 0 which turns out to be ineffective. l,i,t and the arrival time of any other trains that are assigned to However, if train l does not occupy the platform track i, then the same platform track. valid inequality (26) is equivalent to u ≥ 1 which implies l,i,t y ≥ t , ∀l ∈ L, (20) u � 1. Valid inequality (29) considers when the station l,a l,a l,i,t capacity is not sufficient and two conflicting trains need to be assigned to the same platform track, then one of the two y ≥ t + D, ∀l ∈ L, (21) l,d l,d trains with lower priority can be delayed at most by Δ , max which means x can be constrained to 0 when l,i,t y ≥ y + Δ + D, ∀l ∈ L. (22) l,d l,a l t ∈ 􏽮1, 2, . . . , t − 1􏽯 or t ∈ 􏽮t + Δ + D + 1, . . . , MT􏽯. l,a l,d max Overall, a total of 4MT|L| · |I| − |I|(t + Δ + D − t + 1) additional l∈L l,d max l,a 4.4.9. Domain of Variables. Constraints (23)–(25) define the constraints are added into the model after introducing the domain of variables. Note that the variables x , y , and l,i,t l,a valid inequalities (26)–(29). y are intermediate variables to facilitate the model l,d building process, and their values can be directly inferred 5. Genetic and Simulated Annealing from the variables u and v . l,i,t l,i,t Hybrid Algorithm w � {0, 1}, ∀l ∈ L, i ∈ I, (23) l,i In order to recover the train operations as soon as possible in case of train delays, a genetic and simulated annealing hybrid u , v � {0, 1}, ∀l ∈ L, i ∈ I, t ∈ {1, 2, . . . , MT}, (24) l,i,t l,i,t algorithm (GSAHA) is designed to solve the reoptimization model efficiently and effectively [37, 39, 40]. In particular, e , λ , μ � {0, 1}, ∀l, k ∈ L: l ≠ k, π � π . (25) l,k l,k l,k l k the simulated annealing algorithm (SA) has good ability in In short, formulations (3)–(25) constitute the complete jumping out of local optimal solutions, and its convergence MILP model for the reoptimization of train platforming performance is robust against the generated initial solutions. problem. Due to the complicated filter conditions for the However, the convergence speed of SA is generally slow. On 10 Journal of Advanced Transportation the other hand, the genetic algorithm (GA) is a parallel Generating initial population search algorithm that usually converges very fast, while GA (Sections 5.1 and 5.2) is more likely to be trapped into local optimal solutions and it is not robust against the generated initial solutions. As a Obtaining feasible solutions (Section 5.3) result, the GSAHA algorithm combines the advantages of GA and SA. *erefore, GSAHA is robust on the convergence Calculating fitness of individuals (Section 5.4) 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 Selecting the best individual in the current generation and the global best individual section names corresponding to some key algorithmic steps. *e implementation details for the components of GSAHA are illustrated as follows. Lowering the temperature (Section 5.5) 5.1. Chromosome Representation. Figure 5 shows the one- dimensional real-value encoding method that is used to Objective value of the global No best individual remains unchanged for m represent chromosomes. Each chromosome denotes a generations? platform track assignment plan. In particular, if the value of th th the l gene is equal to i, the l train is assigned to platform Yes track i with its scheduled arrival and departure times. Lifting the temperature to R Furthermore, the length of each chromosome is equal to the 1 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 Maximal number of generations Yes gene is located within the range [1, |I|], and thus there could K is reached or objective value of global |L| best individual equals 0? be |I| possible chromosomes in total. No 5.2. Generating Initial Population. Considering diversity and Performing n times of neighborhood search rationality of individuals in the initial population, the fol- operations (Section 5.6.1) lowing strategies are proposed to generate the initial population. Recalculating fitness of every individual (Section 5.4) Step 1. Denote platform tracks whose numbers are smaller than the number of platform tracks |I| as the set I . Reselecting the global best individual Step 2. Select [|L|/(|I| − 1)] trains that have not been selected yet and assign those trains to one of the un- Performing selection, crossover, and mutation operations (Sections 5.6.2, 5.6.3, assigned platform tracks in set I . and 5.6.4) Step 3. Repeat Step 1 until all platform tracks in set I are assigned and assign the remaining Outputting the objective value of the global |L|− [|L|/(|I| − 1)]·(|I| − 1) trains to the last platform best individual track numbered as |I|. Figure 4: Solution framework of the GSAHA algorithm. Step 4. Repeat Step 2 and Step 3 until all individuals in the initial population are generated. Platform track 5 2 3 6 ... 4 7 1 5.3. Obtaining Feasible Solutions. *e chromosome designed Train 1234 ... |L|–2 |L|–1 |L| in Section 5.1 only assigns trains to the platform tracks, i.e., Figure 5: Illustration of the chromosome representation. 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 5.4. Fitness Function. *e fitness function in equation (30) is track temporal resources due to the violation of safety designed to evaluate each individual such that the algorithm headway requirements, including the safety time interval can achieve a better convergence performance. between two trains assigned to the same platform track D, headway between two arrival trains running in the same f(i) − f min f r � exp − , (30) 􏼁 􏼨 􏼩 i k direction h , and headway between two departure trains running in the same direction h . Hence, a heuristic rule is th where r represents the temperature at the k generation, designed to resolve the temporal conflicts according to the th f(i) represents the objective value of the i chromosome, constraints defined in Section 4.5. Journal of Advanced Transportation 11 For each train i (1 ≤ i ≤ |L|) For each train j (1 ≤ j < i) If train i conflicts with train j Fix the arrival and departure times of train i and record the weighted sum delay amount ϑ after resolving the conflicts of trains numbered before train i; Fix the arrival and departure times of train j and record the weighted sum delay amount ϑ after resolving the conflicts of trains numbered before train i; If ϑ ≤ ϑ i i Adopt the adjust method by fixing the arrival and departure times of train i; Else Adopt the adjust method by fixing the arrival and departure times of train j; End If ϑ ≤ ϑ i i End If train i conflicts with train j End For each train j (1 ≤ j < i) End For each train i (1 ≤ i ≤ |L|) Step 5. Sort all trains in descending order by their scheduled or estimated arrival times and number them from 1 to |L|. Step 6. Use Algorithm 1 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. *is operation considers all trains in set L and the platform track assignment costs, and thus the value calculated during this step serves as the objective value of the chromosome. ALGORITHM 1: A heuristic method to resolve the temporal conflicts between trains with given train order. th f represents the minimal objective value at the k search space with the probability of resulting in better so- min generation, and f (r ) represents fitness value of the lutions. Moreover, neighborhood search operator is one of i k th i chromosome when the temperature is r . Fitness function the main operators that can increase population diversity in equation (30) is an important feature of the SA algorithm, when the algorithm is trapped into local optimal solutions. and it has a good capacity to accelerate the convergence of the algorithm. 5.6.2. Selection. *e roulette method is adopted to select parents according to the cumulative probability, as shown in 5.5. Temperature Decline Function. After determining the the following equation: initial temperature R, the temperature decline function in 􏽐 f k�1 equation (31) is used to lower the temperature at each C � , (33) 􏽐 f iteration. k�1 k r � R · η , (31) where N represents the number of individuals in the population. A random number δ is generated within [0, 1); th where r represents the temperature at the k generation k if δ ∈ (C , C ), then chromosome j is chosen as a parent. 2 i j and the constant η represents the temperature decline rate. *e 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 5.6. Genetic Operators the algorithm is trapped into a local optimal solution too early. 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 chro- 5.6.3. Crossover. Two individuals are chosen as parents each mosome i randomly to generate a new chromosome j, and time and a random number δ is generated within the range the objective value f(j) of chromosome j is recalculated. [0, 1). If δ is greater than or equal to the given crossover rate Chromosome j is accepted or rejected to replace chromo- λ , the crossover operator is not used and the two parents are some i according to the probability P (r ) in the following ij k reserved as children directly. Otherwise, the 2-opt crossover equation: operator is performed. Figure 6 shows an example of the f(j) − f(i) crossover operator where both the number of trains (i.e., |L|) P r 􏼁 � min􏼨1, exp􏼠− 􏼡􏼩. (32) ij k and the number of platform tracks (i.e., |I|) are equal to 6. If P (r ) is greater than the random number δ gen- ij k 1 erated within the range [0, 1), then chromosome i is replaced 5.6.4. Mutation. For each gene of a chromosome, a random by chromosome j. Neighborhood search operator is an number δ is generated within the range [0, 1). If δ is 4 4 important feature of the SA algorithm and it can enlarge the smaller than the given mutation rate λ , then the mutation 12 Journal of Advanced Transportation Parent 1 5 2 3 6 1 4 Child 1 5 2 4 2 1 4 Parent 2 1 6 4 2 3 5 Child 2 1 6 3 6 3 5 Train 1 2 3 4 5 6 Train 1 2 3 4 5 6 Figure 6: Illustration of the crossover operator. operator is applied, i.e., a different platform track is ran- specifically, u is set to 1 and v is to 0 for all trains l ∈ L l,i,1 l,i,1 domly assigned to the gene. 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 w , y , and y are set 6. Numerical Experiments l,i l,a l,d to their initial values before the train delay occurs, i.e., *e proposed model is applied to a railway passenger station w � q , y � t , and y � t for all trains l ∈ L and l,i l,i l,a l,a l,d l,d as shown in Figure 7, with five platform tracks (I, 3, 5, 7, 9, platform tracks i ∈ I with the condition of t < S. l,a 11) in the downstream direction and four platform tracks (II, Based on the initial scheduled arrival and departure 4, 6, 8, 10) in the upstream direction. *e time unit Δτ is set times as well as the input data and parameters of 70 trains to 1 min, which is practical for ensuring safe train operations in Tables 3–7, a total of 21 scenarios are generated with the at the stations [22, 25, 37]. Moreover, there are 70 down- number of trains ranging from 10 to 70, and 3 scenarios stream and upstream trains, which need to conduct the are generated for each fixed number of trains. For in- necessary operations from 16:00 to 22:00. *e initial stance, three scenarios (10, 2, 0), (10, 2, 1), and (10, 2, 2) scheduled arrival and departure times of the 70 trains are are generated when the number of trains is equal to 10. available at a repository on the ResearchGate website (DOI: Specifically, the first number “10” in the triple (10, 2, 0) 10.13140/RG.2.2.18253.79849), and trains are assigned with denotes the number of trains, the second number “2” in priority values ranging from 1 to 3. *e initial platform track the triple (10, 2, 0) represents the number of delayed assignment plan is listed in Table 3, and the corresponding trains. Besides, the third number in a triple can take the initially scheduled train operation plan is illustrated in values of 0, 1, and 2 corresponding to the three scenarios, Figure 8. Additionally, the platform track assignment costs so that the estimated arrival and departure times for for the downstream and upstream trains are given in Tables 4 delayed trains in Table 6 are randomly increased with and 5, respectively. In particular, there is a penalty of 10,000 values in the ranges of (0, 0), (− 1, 1), and (− 2, 2), for trains that use the platform tracks in the opposite respectively. direction. *e MILP models for the 21 scenarios in Section 4 are *e train delay information is available at the time of 18: solved by the commercial solver CPLEX 12.7.0 with (i.e., 38, and it is known that 6 downstream trains and 4 upstream CPLEX-WV) and without (i.e., CPLEX-WOV) including the trains are delayed, and the estimated arrival and departure valid inequalities in Section 4.5. Furthermore, the maximum times of those delayed trains are provided in Table 6. computation times of CPLEX-WV and CPLEX-WOV are Moreover, the 10 delayed trains in both directions are both set to 3600 s. *e GSAHA is implemented in C++ marked with the blue colour in Figure 8. Table 7 provides the programming language. Moreover, the algorithmic pa- parameter values used in the model. *e maximum value of rameters for GSAHA are set as follows. *e number of dwell times of all trains Δ equals 43 min, and the length of individuals in the population N is 50, the maximum number max the planning horizon T equals 360 min. *e safety time of generations K is 300, the crossover rate λ is 0.98, the interval on the platform track D equals 6 min, and the mutation rate λ is 0.1, the initial temperature R is 80,000 C, headway between two arrival trains h and the headway the temperature decline rate η is 0.9, and the temperature is between two departure trains h in the same direction are increased to R � 40,000 C if the objective value of the best d 1 both set to 5 min. *e weighting factor α in the objective individual in the current generation remains unchanged for function is set to 200, which is determined after discussing m � 5 iterations and n � 3 times of neighborhood search with the train dispatchers, and the value of α can be adjusted operations are performed each time. In addition, all of the flexibly according to the preferences of the train dispatchers. models and algorithms are tested on a computer with Intel Note that the value of α can be flexibly adjusted by the train (R) Core (TM) i7-5600U 2.6 GHZ CPU and 12G RAM. Tables 8 and 9 list the detailed computation results of dispatchers according to their experiences. In addition, we believe that keeping trains on time with guaranteed train CPLEX-WOV, CPLEX-WV, and GSAHA for the 21 sce- service quality is more important than assigning the trains to narios. More specifically, the columns “Obj 1 value (min)” their preferred platform tracks, and thus the penalty pa- and “Obj 2 value” in Table 8 represent the two components rameters on train delays are relatively larger than the of objective values, i.e., the sum of train arrival and departure platform track occupancy costs. Moreover, when the values delays and total platform track assignment costs, respec- of input parameters are known, the initial values of the tively. In Table 9, the column “Obj value” denotes the overall decision variables should be set in advance before running objective values, the column “CPU time (s)” represents the the GSAHA algorithm or commercial solvers. More computation times in sections, and the column “GAP with Journal of Advanced Transportation 13 80 36 7 34 71 48 Downstream entrance Downstream exit 61 63 74 44 19 11 13 21 23 33 35 55 75 32 30 24 22 16 14 4 2 59 72 40 7 19 6 37 56 50 49 18 II 39 47 28 26 20 12 10 8 35 15 17 29 31 41 51 58 53 66 Upstream exit 43 52 Upstream entrance 45 85 Figure 7: Layout of the railway passenger station. Table 3: Initial platform tack assignment plan between 16:00 and 22:00. Platform track number Occupation trains 11 T , T 9 29 9 T , T , T , T , T 5 19 31 41 49 7 T , T , T , T , T , T , T , T , T 11 21 27 33 43 47 55 63 69 5 T , T , T , T , T , T , T , T , T , T 1 7 15 25 35 39 53 61 67 73 3 T , T , T , T , T , T , T , T , T , T , T , T 3 13 17 23 37 45 51 57 59 65 71 75 II 4 T , T , T , T , T , T , T , T , T , T , T , T 2 8 18 22 30 34 40 42 48 54 60 64 6 T , T , T , T , T , T , T , T , T , T 4 12 16 24 32 38 44 50 56 62 8 T , T , T , T , T , T , T , T 6 14 20 28 36 46 52 58 10 T , T 10 26 T T 9 29 T T T T T 5 19 31 41 49 T T T T T T T T T 11 21 27 33 43 47 55 63 69 T T T T T T T T T T 15 25 35 39 53 61 67 73 1 7 T T T T T T T T T T T T 3 13 17 23 37 45 51 57 59 65 71 75 II T T T T T T T T T T T T 2 8 18 22 30 34 40 42 48 54 60 64 T T T T T T T T T T 4 12 16 24 32 38 44 50 56 62 T T T T T T T T 6 14 20 28 36 46 52 58 T T 10 26 16:00 17:00 18:00 19:00 20:00 21:00 22:00 Figure 8: Initial platform track utilization scheme between 16:00 and 22:00. 14 Journal of Advanced Transportation Table 4: Platform track assignment costs for downstream trains with different priorities. Platform track number Train direction Train priority I 3 5 7 9 11 1 600 6 12 24 48 96 Downstream 2 300 3 6 12 24 48 3 200 2 4 8 16 32 Table 5: Platform track assignment costs for upstream trains with different priorities. Platform track number Train direction Train priority II 4 6 8 10 II 1 600 6 12 24 48 600 Upstream 2 300 3 6 12 24 300 3 200 2 4 8 16 200 Table 6: Estimated arrival and departure times for delayed trains. Train Arrival delay Expected arrival time Expected departure time Dwell time Priority T 20 187 210 23 1 T 25 197 209 12 3 T 25 203 220 17 3 T 27 211 227 16 1 T 30 240 260 20 3 T 30 266 286 20 3 T 30 202 217 15 3 T 32 227 250 23 3 T 35 235 243 8 3 T 40 272 283 11 1 Table 7: Input parameters of the model. Parameter Value Maximum value of dwell times of all trains Δ 43 min max Length of the planning horizon T 360 min Safety time interval for platform track operation D 6 min Sum of the length of the planning horizon and the safety time interval for platform track operation MT 366 min Headway between two arrival trains h 5 min Headway between two departure trains h 5 min Objective function weighting factor α 200 CPLEX-WV (%)” indicates the relative gap between the speed up the solving process of CPLEX. More specifically, objective values of GSAHA and CPLEX-WV. CPLEX-WOV cannot obtain optimal solutions for the in- *ree points can be drawn from the computation results stances with the number of trains larger than or equal to 60 in Tables 8 and 9. First, the computation times of CPLEX- trains within 3600 s, which results in large objective values. In order to illustrate the feasibility of our proposed MILP WOV, CPLEX-WV, and GSAHA increase gradually as the number of trains increases, and the maximum computation model, the optimization solution of the scenario (70, 10, 0) times of those three solution methods are equal to 3600 s, using CPLEX-WV is illustrated in detail. Table 10 shows that 679.48 s, and 28.96 s, respectively. In particular, even if the arrival and departure times of 11 trains are delayed after CPLEX is sped up with the valid inequalities, the compu- the reoptimization, and the new platform track assignment tation times of GSAHA are still much fewer than that of plan is provided in Table 11. Besides, the platform track CPLEX. *erefore, it can be shown that our proposed utilization scheme is illustrated in Figure 9, and it can be GSAHA can solve the reoptimization problem more effi- seen from Figure 9 that all safety headway requirements are ciently in a real-time manner. Second, the objective values of satisfied. Note that the 14 trains in Table 11 with bold fonts GSAHA are close to those of CPLEX-WV with the maxi- represent that those trains have been reassigned to different mum gap value equal to 5.66%. *ird, after comparing the platform tracks, and those 14 trains are marked with the red colour in Figure 9. Besides, the convergence process of computation times of CPLEX-WOV and CPLEX-WV, it can be seen the valid inequalities in Section 4.5 can significantly Journal of Advanced Transportation 15 Table 8: Two components of objective values of CPLEX-WOV, CPLEX-WV, and GSAHA under different scenarios. CPLEX-WOV CPLEX-WV GSAHA Scenario Obj 1 value (min) Obj 2 value Obj 1 value (min) Obj 2 value Obj 1 value (min) Obj 2 value (10, 2, 0) 800 50 800 50 800 50 (10, 2, 1) 1200 50 1200 50 1200 50 (10, 2, 2) 800 50 800 50 800 50 (20, 3, 0) 1200 174 1200 174 1200 188 (20, 3, 1) 1800 174 1800 174 1800 174 (20, 3, 2) 1400 174 1400 174 1400 174 (30, 4, 0) 5200 278 5200 278 5200 286 (30, 4, 1) 5600 282 5600 282 5600 294 (30, 4, 2) 4400 278 4400 278 4400 283 (40, 6, 0) 800 363 800 363 800 379 (40, 6, 1) 1200 363 1200 363 1200 385 (40, 6, 2) 1200 363 1200 363 1200 395 (50, 7, 0) 8400 469 8400 469 8400 533 (50, 7, 1) 7000 469 7000 469 7000 545 (50, 7, 2) 8200 469 8200 469 8200 513 (60, 9, 0) 340400 1600 23600 583 24400 737 (60, 9, 1) 722400 2885 24200 575 25000 682 (60, 9, 2) 237800 2647 18200 579 18200 690 (70, 10, 0) 195400 1989 16400 659 16848 764 (70, 10, 1) 161600 1593 16800 685 17600 768 (70, 10, 2) 149800 2708 14600 659 15400 722 Table 9: Objective values and computation times of CPLEX-WOV, CPLEX-WV, and GSAHA under different scenarios. CPLEX-WOV CPLEX-WV GSAHA Scenario Obj value CPU time (s) Obj value CPU time (s) Obj value CPU time (s) GAP with CPLEX-WV (%) (10, 2, 0) 850 124.31 850 8.17 850 2.40 0 (10, 2, 1) 1250 51.73 1250 8.75 1250 2.43 0 (10, 2, 2) 850 67.49 850 8.23 850 2.34 0 (20, 3, 0) 1374 361.25 1374 24.66 1388 3.21 1.02 (20, 3, 1) 1974 377.20 1974 25.19 1974 3.10 0 (20, 3, 2) 1574 340.83 1574 24.02 1574 3.33 0 (30, 4, 0) 5478 326.84 5478 46.05 5486 4.75 0.15 (30, 4, 1) 5882 517.27 5882 53.25 5894 5.22 0.20 (30, 4, 2) 4678 208.92 4678 37.53 4683 5.01 0.11 (40, 6, 0) 1163 766.13 1163 46.30 1179 7.78 1.38 (40, 6, 1) 1563 480.83 1563 53.66 1585 7.83 1.41 (40, 6, 2) 1563 954.16 1563 55.27 1595 7.85 2.05 (50, 7, 0) 8869 1335.45 8869 105.22 8933 12.86 0.72 (50, 7, 1) 7469 1010.09 7469 87.42 7545 13.32 1.02 (50, 7, 2) 8669 1052.38 8669 121.58 8713 12.79 0.51 (60, 9, 0) 342000 3600 24183 661.22 25137 20.25 3.94 (60, 9, 1) 725285 3600 24775 678.17 25682 20.07 3.66 (60, 9, 2) 240447 3600 18779 604.38 18890 21.61 0.59 (70, 10, 0) 197389 3600 17059 679.48 17612 27.08 3.24 (70, 10, 1) 163193 3600 17485 344.52 18368 27.89 5.05 (70, 10, 2) 152508 3600 15259 529.75 16122 28.96 5.66 GSAHA is shown in Figure 10, where the algorithm can removing the second part of the objective function, which is reach the near-optimal solution only after 70 iterations. aimed to simulate the case that α takes an infinity value. *e Meanwhile, for the scenario (70, 10, 0) in Tables 8 and 9, optimization results of CPLEX-WV and GSAHA are listed sensitivity analysis of different values of weighting factor α is in Table 12, and the parameter settings for the GSAHA performed by increasing the value of α from 0 to 10 with the remain unchanged. In addition, we take the objective value step size equal to 1 for small values of α and from 40 to 440 of GSAHA for the average optimization results of 20 runs. It with the step size equal to 40 for relatively larger values of α. can be shown that the objective values of CPLEX-WV and Moreover, one special case is designed by setting α � 1 and GSAHA increase as the value of α increases, and the solution 16 Journal of Advanced Transportation Table 10: Amount of secondary delay for the trains obtained by CPLEX-WV for the scenario (70, 10, 0). Train Priority Secondary arrival delay (min) Secondary departure delay (min) T 1 0 4 T 3 0 2 T 3 0 3 T 3 2 2 T 3 2 2 T 1 5 5 T 2 2 2 T 1 2 2 T 1 0 1 T 3 2 2 T 1 2 2 Table 11: Platform tack assignment plan after the reoptimization using CPLEX-WV for the scenario (70, 10, 0). Platform track number Occupation trains 11 T , T 9 29 9 T , T , T , T , T , T 5 19 31 41 49 55 7 T , T , T , T , T , T , T , T 11 21 27 33 43 53 63 69 5 T , T , T , T , T , T , T , T , T , T 1 7 15 25 35 45 47 61 67 73 3 T , T , T , T , T , T , T , T , T , T , T , T 3 13 17 23 37 39 51 57 59 65 71 75 II 4 T , T , T , T , T , T , T , T , T , T , T , T 2 8 18 22 28 34 40 42 48 44 60 64 6 T , T , T , T , T , T , T , T , T , T , T 4 12 16 24 30 32 38 50 54 58 62 8 T , T , T , T , T 6 14 20 46 56 10 T , T , T , T 10 26 36 52 T T 9 29 T T T T T T 5 19 31 41 49 55 T T T T T T T T 11 21 27 33 43 53 63 69 T T T T T T T T T T 1 7 15 25 35 45 47 61 67 73 T T T T T T T T T T T T 3 13 17 23 37 39 51 57 59 65 71 75 II T T T T T T T T T T T T 2 8 18 22 28 34 40 42 48 44 60 64 T T T T T T T T T T T 4 12 16 24 30 32 38 50 54 58 62 T T T T T 6 14 20 46 56 T T T T 10 26 36 52 16:00 17:00 18:00 19:00 20:00 21:00 22:00 Figure 9: Platform track utilization scheme after the reoptimization using CPLEX-WV for the scenario (70, 10, 0). Journal of Advanced Transportation 17 85,000 80,000 75,000 70,000 65,000 60,000 55,000 50,000 45,000 40,000 35,000 30,000 25,000 20,000 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 Number of iterations Figure 10: Convergence process of GSAHA for the scenario (70, 10, 0). Table 12: Optimization results of CPLEX-WV and GSAHA with different values of weighting factor α. CPLEX-WV GSAHA Weighting Obj 1 value Obj 2 Obj CPU time Obj 1 value Obj 2 Obj CPU time GAP with CPLEX- factor α (min) value value (s) (min) value value (s) WV (%) 0 0 587 587 3600 0 477 477 32.92 − 18.74 1 104 621 725 490.90 112 651 763 30.85 5.24 2 164 659 823 541 188 670 858 28.97 4.25 3 246 659 905 540.47 270 672 942 29.05 4.09 4 328 663 991 607.41 336 697 1033 29.17 4.24 5 410 663 1073 731.23 420 704 1124 29.33 4.75 6 492 659 1151 544.47 504 706 1210 29.02 5.13 7 574 659 1233 547.19 588 702 1290 28.99 4.62 8 656 663 1319 651.16 672 709 1381 29.07 4.70 9 738 669 1407 934.73 756 704 1460 29.09 3.77 10 820 663 1483 718.23 841 715 1556 28.30 4.92 40 3280 659 3939 740.22 3376 764 4140 27.60 5.10 80 6560 659 7219 589.28 6736 771 7507 28.20 3.99 120 9840 659 10499 764.37 10142 772 10914 27.52 3.95 160 13120 663 13783 447.63 13449 784 14233 27.51 3.26 200 16400 659 17059 679.48 16848 764 17612 27.08 3.24 240 19680 659 20339 388.56 20182 769 20951 27.25 3.01 280 22960 659 23619 359.88 23468 874 24342 27.49 3.06 320 26240 659 26899 595.69 26924 757 27681 27.65 2.91 360 29520 659 30179 329.28 30261 808 31069 28.23 2.95 400 32800 659 33459 340.13 33631 771 34402 28.77 2.82 440 36080 659 36739 412.67 37089 719 37808 28.22 2.91 ∞ 82 0 82 256.36 84 0 84 30.04 2.44 times of CPLEX-WV range from 256.36 to 3600 seconds while GSAHA can obtain a solution that is much smaller while the solution times of GSAHA only range from 27.08 to than that of CPLEX-WV. In addition, for the case of α � ∞, 32.92 seconds. *e last column in Table 12 shows that the it can be shown that the minimum value of the first part of objective values of GSAHA are − 18.74%–5.10% larger than the objective function is equal to 82 min, and GSAHA can those of CPLEX-WV. In particular, CPLEX-WV cannot also obtain an objective value of 84 min. Note that the obtain the optimal solution for α � 0 within the time limit, optimality gaps of GSAHA compared with CPLEX could be Objective value 18 Journal of Advanced Transportation due to two reasons in particular. First, the spatial and Data Availability temporal resources are allocated separately in GSAHA. *e data used to support the findings of this study are Second, a heuristic method is developed to resolve the available from the corresponding author upon request. temporal conflicts between trains. Overall, the stable per- formance of GSAHA regarding the solution quality and solving times shows that our proposed GSAHA is suitable to Conflicts of Interest serve as an effective computer-aided decision-making tool for the train dispatchers in case of train delays. *e authors declare that they have no conflicts of interest. 7. Conclusions Acknowledgments *e problem of reoptimization of the train platforming is *is study was supported by the National Key R&D Program essential in recovering the train operations within the station (grant no. 2017YFB1200700), National Natural Science while minimizing the negative impact of train delays. *is Foundation of China (grant no. U1834209), and Open Fund paper proposes a MILP model for the reoptimization Project of Chongqing Key Laboratory of Traffic & Trans- problem, where the train station is represented with the portation (grant no. 2018TE01). discretized platform track time-space resources. In addition, a set of valid inequalities is developed to improve the per- References formance of the commercial solver. In addition, in order to achieve the real-time reoptimization of the train platforming [1] National Bureau of Statistics of China, 2020, http://data.stats. problem and provide a reliable decision tool for the train gov.cn/english/easyquery.htm?cn=C01. dispatchers, a heuristic algorithm called GSAHA that [2] R. M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan, “Railway combines the advantages of SA and GA algorithms is track allocation: models and methods,” OR Spectrum, vol. 33, designed. Moreover, GSAHA first allocates the spatial re- no. 4, pp. 843–883, 2011. sources for the trains, and the temporal conflicts between [3] A. A. Assad, “Models for rail transportation,” Transportation trains are further resolved through a specialized heuristic Research Part A: General, vol. 14, no. 3, pp. 205–220, 1980. rule. To test the efficiency and effectiveness of the proposed [4] J.-F. Cordeau, P. Toth, and D. Vigo, “A survey of optimization models for train routing and scheduling,” Transportation model and algorithm, a set of real-life instances is solved by a Science, vol. 32, no. 4, pp. 380–404, 1998. commercial solver and GSAHA. *e computational results [5] U. Brannlund, ¨ P. O. Lindberg, A. Nõu, and J.-E. Nilsson, show the proposed MILP model can effectively achieve the “Railway timetabling using Lagrangian relaxation,” Trans- reoptimization of the train platforming problem, and the portation Science, vol. 32, no. 4, pp. 358–369, 1998. proposed heuristic algorithm can further speed up the [6] A. Caprara, M. Fischetti, and P. Toth, “Modeling and solving solving process of the commercial solver with near-optimal the train timetabling problem,” Operations Research, vol. 50, solutions. In addition, the computational results also show no. 5, pp. 851–861, 2002. that the performance of GSAHA is stable even when the [7] Y. Zhang, Q. Peng, Y. Yao, X. Zhang, and X. Zhou, “Solving values of weighting factor α vary from 40 to 440. cyclic train timetabling problem through model reformula- *e work in this paper can be extended in the following tion: extended time-space network construct and Alternating several interesting directions. First, instead of ensuring the Direction Method of Multipliers methods,” Transportation Research Part B: Methodological, vol. 128, pp. 344–379, 2019. arrival and departure safety headway between two different [8] Y. Zhang, A. D’Ariano, B. He, and Q. Peng, “Microscopic trains running in the same direction, the explicit consid- optimization model and algorithm for integrating train eration of train entrance and exit route conflicts can increase timetabling and track maintenance task scheduling,” Trans- the station throughput capacity and reduce the train delays portation Research Part B: Methodological, vol. 127, pp. 237– [10, 20]. Second, the MILP model and the heuristic algo- 278, 2019. rithm GSAHA proposed in this paper can be further de- [9] L. G. Kroon, H. Edwin Romeijn, and P. J. Zwaneveld, veloped to consider different station types, such as the “Routing trains through railway stations: complexity issues,” terminal station where trains need to perform the turn- European Journal of Operational Research, vol. 98, no. 3, around movement that makes the train platforming problem pp. 485–498, 1997. more complicated [42, 43]. *ird, the train movements at [10] P. J. Zwaneveld, L. G. Kroon, H. E. Romeijn et al., “Routing the stations can be viewed as a set of space-time paths, and trains through railway stations: model formulation and al- gorithms,” Transportation Science, vol. 30, no. 3, pp. 181–194, thus more efficient dual decomposition methods could be developed accordingly [7, 44, 45]. Fourth, more efficient [11] P. J. Zwaneveld, L. G. Kroon, and S. P. M. Van Hoesel, solution algorithms can be developed for the simultaneous “Routing trains through a railway station based on a node reoptimization of several interconnected railway stations in packing model,” European Journal of Operational Research, a railway line or even a regional railway network with more vol. 128, no. 1, pp. 14–33, 2001. complicated structure so that the joint optimization of delay [12] R. Lusby, J. Larsen, D. Ryan, and M. Ehrgott, “Routing trains situations and train timetabling problems can be achieved through railway junctions: a new set-packing approach,” [8, 19, 27, 46–49]. Finally, the integration of energy-efficient Transportation Science, vol. 45, no. 2, pp. 228–245, 2011. train movement with the reoptimization of train platforming [13] R. M. Lusby, J. Larsen, M. Ehrgott, and D. M. Ryan, “A set can be considered for more system-wide benefits [50, 51]. packing inspired method for real-time junction train routing,” Journal of Advanced Transportation 19 Computers & Operations Research, vol. 40, no. 3, pp. 713–724, [30] M. J. Dorfman and J. Medanic, “Scheduling trains on a railway 2013. network using a discrete event model of railway traffic,” [14] V. Cacchiani, D. Huisman, M. Kidd et al., “An overview of Transportation Research Part B: Methodological, vol. 38, no. 1, recovery models and algorithms for real-time railway pp. 81–98, 2004. rescheduling,” Transportation Research Part B: Methodolog- [31] A. D’ariano, D. Pacciarelli, and M. Pranzo, “A branch and ical, vol. 63, pp. 15–37, 2014. bound algorithm for scheduling trains in a railway network,” [15] L. Meng and X. Zhou, “Robust single-track train dispatching European Journal of Operational Research, vol. 183, no. 2, model under a dynamic and stochastic environment: a sce- pp. 643–657, 2007. [32] J. Rodriguez, “A constraint programming model for real-time nario-based rolling horizon solution approach,” Trans- portation Research Part B: Methodological, vol. 45, no. 7, train scheduling at junctions,” Transportation Research Part B: pp. 1080–1102, 2011. Methodological, vol. 41, no. 2, pp. 231–245, 2007. [16] L. Meng and X. Zhou, “Simultaneous train rerouting and [33] A. D’Ariano, L. Meng, G. Centulio, and F. Corman, “Inte- rescheduling on an N-track network: a model reformulation grated stochastic optimization approaches for tactical with network-based cumulative flow variables,” Trans- scheduling of trains and railway infrastructure maintenance,” portation Research Part B: Methodological, vol. 67, pp. 208– Computers & Industrial Engineering, vol. 127, pp. 1315–1335, 234, 2014. [17] S. Zhan, L. G. Kroon, L. P. Veelenturf, and J. C. Wagenaar, [34] T. M. Herrman, Stability of timetables and train routings through station regions, Ph.D. thesis, Swiss Federal Insitute of “Real-time high-speed train rescheduling in case of a complete blockage,” Transportation Research Part B: Methodological, Technology Zurich, Zurich, ¨ Switzerland, 2006. [35] N. Beˇsinovi´c and R. M. Goverde, “Stable and robust train vol. 78, pp. 182–201, 2015. [18] S. Zhan, L. G. Kroon, J. Zhao, and Q. Peng, “A rolling horizon routing in station areas with balanced infrastructure capacity approach to the high speed train rescheduling problem in case occupation,” Public Transport, vol. 11, no. 2, pp. 211–236, of a partial segment blockage,” Transportation Research Part 2019. E: Logistics and Transportation Review, vol. 95, pp. 32–61, [36] A. D’Ariano and M. Pranzo, “An advanced real-time train dispatching system for minimizing the propagation of delays [19] M. Carey, “A model and strategy for train pathing with choice in a dispatching area under severe disturbances,” Networks and Spatial Economics, vol. 9, no. 1, pp. 63–84, 2009. of lines, platforms, and routes,” Transportation Research Part B: Methodological, vol. 28, no. 5, pp. 333–353, 1994. [37] W. Liu, X. Zhu, and L. Kang, “Real-time track reallocation for emergency incidents at large railway stations,” Mathematical [20] P. Chakroborty and D. Vikram, “Optimum assignment of trains to platforms under partial schedule compliance,” Problems in Engineering, vol. 2015, Article ID 296394, Transportation Research Part B: Methodological, vol. 42, no. 2, 11 pages, 2015. pp. 169–184, 2008. [38] L. Kang, S. Chen, and Q. Meng, “Bus and driver scheduling [21] A. Caprara, L. Galli, and P. Toth, “Solution of the train with mealtime windows for a single public bus route,” platforming problem,” Transportation Science, vol. 45, no. 2, Transportation Research Part C: Emerging Technologies, pp. 246–257, 2011. vol. 101, pp. 145–160, 2019. [22] L. Kang, Z. Lu, and Q. Meng, “Stochastic schedule–based [39] W. Xing and J. Xie, Modern Optimization optimization model for track allocations in large railway Methodspp. 113–147, Tsinghua University Press, Beijing, China, 2nd edition, 2006. stations,” Journal of Transportation Engineering, Part A: Systems, vol. 145, no. 3, Article ID 04019001, 2019. [40] H. Yu, H. Fang, P. Yao, and Y. Yuan, “A combined genetic algorithm/simulated annealing algorithm for large scale [23] D. D. L. Cardillo and N. Mione, “k L-list λ colouring of graphs,” European Journal of Operational Research, vol. 106, system energy integration,” Computers & Chemical Engi- no. 1, pp. 160–164, 1998. neering, vol. 24, no. 8, pp. 2023–2035, 2000. [24] A. Billionnet, “Using integer programming to solve the train- [41] H. Du, J. Fan, X. He, and M. W. Feldman, “A genetic sim- platforming problem,” Transportation Science, vol. 37, no. 2, ulated annealing algorithm to optimize the small-world network generating process,” Complexity, vol. 2018, Article ID pp. 213–222, 2003. [25] P. Sels, P. Vansteenwegen, T. Dewilde, D. Cattrysse, 1453898, 12 pages, 2018. [42] Q. Zhong, R. M. Lusby, J. Larsen, Y. Zhang, and Q. Peng, B. Waquet, and A. Joubert, “*e train platforming problem: the infrastructure management company perspective,” “Rolling stock scheduling with maintenance requirements at the Chinese high-speed railway,” Transportation Research Transportation Research Part B: Methodological, vol. 61, pp. 55–72, 2014. Part B: Methodological, vol. 126, pp. 24–44, 2019. [26] M. Carey and S. Carville, “Scheduling and platforming trains [43] Q. Zhong, Y. Zhang, D. Wang, Q. Zhong, C. Wen, and at busy complex stations,” Transportation Research Part A: Q. Peng, “A mixed integer linear programming model for Policy and Practice, vol. 37, no. 3, pp. 195–224, 2003. rolling stock deadhead routing before the operation period in [27] M. Carey and I. Crawford, “Scheduling trains on a network of an urban rail transit line,” Journal of Advanced Trans- busy complex stations,” Transportation Research Part B: portation, vol. 2020, Article ID 3809734, 18 pages, 2020. [44] X. Zhou, L. Tong, M. Mahmoudi et al., “Open-source VRPLite Methodological, vol. 41, no. 2, pp. 159–178, 2007. [28] L. Kang, J. Wu, and H. Sun, “Using simulated annealing in a package for vehicle routing with pickup and delivery: a path finding engine for scheduled transportation systems,” Urban bottleneck optimization model at railway stations,” Journal of Transportation Engineering, vol. 138, no. 11, pp. 1396–1402, Rail Transit, vol. 4, no. 2, pp. 68–85, 2018. 2012. [45] X. Chen, S. He, Y. Zhang, L. Tong, P. Shang, and X. Zhou, [29] J. Wu, L. Kang, H. Sun, and X. Jia, “Track allocation opti- “Yard crane and AGV scheduling in automated container mization in railway station: mean-variance model and case terminal: a multi-robot task allocation framework,” Trans- study,” Journal of Transportation Engineering, vol. 139, no. 5, portation Research Part C: Emerging Technologies, vol. 114, pp. 540–547, 2013. pp. 241–271, 2020. 20 Journal of Advanced Transportation [46] L. Kang, J. Wu, H. Sun, X. Zhu, and B. Wang, “A practical model for last train rescheduling with train delay in urban railway transit networks,” Omega, vol. 50, pp. 29–42, 2015. [47] L. Kang, X. Zhu, H. Sun, J. Wu, Z. Gao, and B. Hu, “Last train timetabling optimization and bus bridging service manage- ment in urban railway transit networks,” Omega, vol. 84, pp. 31–44, 2019. [48] L. Kang and Q. Meng, “Two-phase decomposition method for the last train departure time choice in subway networks,” Transportation Research Part B: Methodological, vol. 104, pp. 568–582, 2017. [49] L. Kang, J. Wu, H. Sun, X. Zhu, and Z. Gao, “A case study on the coordination of last trains for the Beijing subway net- work,” Transportation Research Part B: Methodological, vol. 72, pp. 112–127, 2015. [50] W. Li, Q. Peng, Q. Li, C. Wen, Y. Zhang, and J. Lessan, “Joint operating revenue and passenger travel cost optimization in urban rail transit,” Journal of Advanced Transportation, vol. 2018, Article ID 7805168, 15 pages, 2018. [51] W. Li, Q. Peng, C. Wen, S. Li, X. Yan, and X. Xu, “Integrated optimization on energy saving and quality of service of urban rail transit system,” Journal of Advanced Transportation, vol. 2020, Article ID 3474020, 22 pages, 2020.

Journal

Journal of Advanced TransportationHindawi Publishing Corporation

Published: Jun 3, 2020

References