Search

This paper analyzes the relation of arrival-departure tracks and the platforms of various types of stations, and the minimum dwelling time and adjacent train arrival interval to avoid contact of the boarding and alighting passengers. It constructs an integrated model of high-speed train rescheduling and the arrival-departure tracks utilization planning, taking the minimum dwelling time at stations, train tracking interval, minimum train running time in sections, and the arrival-departure tracks occupation as the constraints. The genetic algorithm based on the tabu search strategy is utilized to address the problem. A comparison is conducted between the computational results based on the classical genetic algorithm and the designed algorithm, revealing a 18.92% reduction in total calculation time consumption and a 1.11% improvement in accuracy. The proposed method can provide decision support for train dispatching work in epidemic situations. [ABSTRACT FROM AUTHOR]

Train rescheduling problem has been a hot topic in the field of railway transportation organization work. Train rescheduling plan is the key of train operation organization that determines the transportation efficiency. To improve the efficiency of generating the train rescheduling plan, we constructed a train rescheduling model, taking the total delay time as the optimization goal and interval between trains, minimum running time in sections, minimum dwelling time as the constraints. A new kind of particle swarm optimization algorithm-hybrid fuzzy particle swarm optimization algorithm is proposed to find the solution of the model. The computing case shows the computing efficiency of the novel algorithm and the effectiveness of the model. The overall consumption time of hybrid fuzzy particle swarm optimization algorithm is reduced by 9.91%, compared with typical partical optimization algorithm. The approach presented in this paper can offer decision information for the dispatchers of railways. [ABSTRACT FROM AUTHOR]

Railway traffic management focuses on regulating train movements and delivering improved service quality to passengers; however, such efforts are subject to many uncertainties in terms of disruptions and passenger demand on a rail transit line. In contrast to most existing studies, which focus on the rescheduling of passenger timetables in a deterministic framework, this study proposes a two-stage stochastic optimization model for allocating backup rolling stocks (BRS) to storage lines to reschedule the timetable and serve passengers delayed by disruptions. The first stage is an assignment problem to determine the optimal plan for the allocation of BRS to storage lines to achieve a good trade-off between the investment cost for the BRS and the expected travel time of delayed passengers across different stochastic scenarios. The second stage is explicitly formulated as a network flow model to optimize the timetable of the delayed trains on the tracks and the BRS from the storage lines such that the passenger travel time is minimized under each stochastic scenario. To improve the efficiency of convergence, we develop an improved L-shaped method with several accelerating techniques. Among these, we show that the classical integer L-shaped cut can be tightened given the property of the second-stage problem, which can also be generalized to other two-stage integer stochastic programs. Real-world case studies based on historical data from the Beijing metro verify the effectiveness of the proposed approach in reducing the travel time for passengers. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This research was supported by the National Natural Science Foundation of China [Grants 71621001, 71825004, and 71901016]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1233] or is available from the IJOC GitHub software repository (https://github.com/INFORMSJoC) at [http://dx.doi.org/10.5281/zenodo.6892548]. [ABSTRACT FROM AUTHOR]

When major disruptions occur in a rail network, the infrastructure manager and train operating companies may be forced to stop trains until the normal status is recovered. A crucial aspect is to identify, for each train, a location (a safe place) where the train can hold during the disruption, avoiding to disconnect the network and allowing a quick recovering of the plan, at restart. We give necessary and sufficient conditions for a safe place assignment to have the desired property. We then translate such conditions into constraints of a suitable binary formulation of the problem. Computational results on a set of instances provided by a class 1 U.S. railroad show how the approach can be used effectively in the real-life setting that motivates the study, by returning optimal assignments in a fraction of a second. [ABSTRACT FROM AUTHOR]

In train rescheduling, the arrival and departure times of trains at stations are normally constrained by many operations rules that must be respected. Therefore, different methods were proposed to describe train operations for preventing train conflicts, especially concerning the safety headways. This paper develops a virtual resource-based method in place of the commonly used big-M method and 'either-or' constraints for reformulating the safety headway of opposing trains arriving at the same station on a single-track rail. This new formulation can provide an efficient decomposition mechanism by decomposing the original complex problem into several single train-based subproblems. A resource-oriented mixed-integer linear programming model based on a time-space network is developed to minimize the total train delay time with cumulative flow variables used to describe time-space resources occupation. We also present a set of numerical experiments based on a single-track railway line in China to evaluate the validity of the proposed method. [ABSTRACT FROM AUTHOR]

• An integrated space-time network for both train rescheduling and passenger routing is developed for an incident of complete blockage. • A two-layer decomposition approach based on alternating direction method of multipliers (ADMM) algorithm is developed to solve the integrated model. • The model is tested for case studies of Chinese high-speed railway networks. Trains normally run as scheduled in a non-disrupted situation. However, due to external and/or internal factors, trains may deviate from their original timetable during daily operations. To this end, the involved dispatchers are required to reschedule disrupted trains to efficiently transport delayed passengers to their destinations as soon as possible. In this study, we focus on train rescheduling in a seriously disrupted situation where a track segment is completely blocked for a relatively long period of time, e.g., two hours. In this situation, trains cannot pass the disrupted segment, meaning that passengers will be unable to travel as scheduled. We simultaneously rescheduled trains and passenger routes from both the operator's and passengers' perspectives. This integrated train rescheduling and passenger rerouting problem was formulated with an Integer Linear Programming model based on a space-time network. We decomposed the integrated model into two subproblems, a train rescheduling problem and a passenger routing problem, using the alternating direction method of multipliers (ADMM) algorithm. Both subproblems could be further decomposed into a series of shortest path problems for trains or passengers, and solved by a dynamic programming algorithm. Finally, we tested our models and algorithms on both a small hypothetical railway network and a part of the Chinese high-speed railway network. [ABSTRACT FROM AUTHOR]

Railway disturbance management is inherently a multi-objective optimization problem that concerns both the operators' cost and passenger's service level. This study proposes a multi-objective simulation-based optimization framework to effectively manage the train conflicts after the occurrences of a disturbance caused by a temporary line blockage. The simulation model enhanced with a dynamic priority dispatching rule in order to speed up the optimization procedure. A multi-objective variable neighborhood search meta-heuristic is proposed to solve the train rescheduling model. The obtained Pareto optimal solutions for disturbance management model support the decision maker to find a trade-off between both user and operator viewpoints. The proposed approach has been validated on a set of disruption scenarios covering a large part of the Iranian rail network. The computational results prove that the proposed model can generate good-quality timetables with the minimum passenger delay and deviation from the initial timetable. The outcomes indicate that the developed simulation-based optimization approach has substantial advantages in producing practical solution quickly when compared to currently accepted solutions. Abbreviation: MOVNS: multi-objective variable neighbourhood search; DES: discrete-event simulation; SO: simulation-optimization; AG: Alternative Graph; FCFS: First Come First Served; MIP: mixed integer programming; MILP: mixed-integer linear programming; B&B: branch and bound algorithm; VND: Variable Neighborhood Descent; NSGA-II: Non-dominated Sorting Genetic Algorithm–II; CD: crowding distance; DP: dynamic priority; EDD: earliest due date first; SRTT: shortest remaining traveling time; LST: least slack time first [ABSTRACT FROM AUTHOR]

This paper investigates the integrated optimization problem of train rescheduling and train control for high-speed railway lines, where perturbations occur and cause Temporary Speed Restriction (TSR) to trains. We consider microscopic details (i.e., block sections) for ensuring the feasibility of the solution from a train signaling point of view, and an even higher level of detail, to accurately represent the train speed profiles. Running time and headway time are variable, at the same time depending from, and affecting, traffic. We optimize train speed profiles by considering vehicle and infrastructure constraints (e.g., traction, slopes). The model naturally considers the transition along the normal, disturbed and the recovery operation periods. A mixed-integer nonlinear programming (MINLP) model is first developed to simultaneously optimize train orders, routes, and departure and arrival times, as well as train speed profiles, aiming at reducing total train deviation time. The MINLP model is difficult to solve; thus we further reformulate it into a mixed-integer linear programming (MILP) model by means of piecewise linear approximation. A two-step approach is designed to speed up the solving procedure of the MILP model: first estimate the upper/lower bounds of train speeds and then solve the MILP model based on the estimated bounds of train speeds. Three instances (i.e., a small-scale line, a medium-scale line, and a large-scale network) are used to highlight the performance of the approach, verify the benefit of the integration, and its dependence on the parameters used. According to the experimental results, our integrated optimization method leads to an average improvement of 3%-36% in solution quality, compared with the integrated approach without train rerouting measure. Moreover, the integrated optimization method outperforms the sequential approach, achieving 6%-9% improvement in solution quality. • We investigate the integrated optimization problem of train rescheduling and train control in a detailed way to deal with Temporary Speed Restriction (TSR) disruptions that occur in high-speed railways. • We propose a MILP model to simultaneously identify the train orders, routes, departure and arrival times, and speed profiles, which could precisely model the effect and dynamics of TSR. • We use three instances with small/medium/large scale to demonstrate the effectiveness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

We consider the real-time resolution of conflicts arising in real-world train management applications. In particular, given a nominal timetable for a set of trains and a set of modifications due to delays or other resources unavailability, we are aiming at defining a set of actions which must be implemented to grant safety, e.g., to avoid potential conflicts such as train collisions or headway violations, and restore quality by reducing the delays. To be compatible with real-time management, the required actions must be determined in a few seconds, hence specialized fast heuristics must be used. We propose a fast and effective parallel algorithm that is based on an iterated greedy scheduling of trains on a time-space network. The algorithm uses several sortings to define the initial train dispatching rule and different shaking methods between iterations. The performance is further enhanced by using various sparsification methods for the time-space network. The best algorithm configuration is determined through extensive experiments, conducted on a set of instances derived from real-world networks and instances from the literature. The resulting heuristic proved able to consistently resolve the existing conflicts and obtaining excellent solution quality within just two seconds of computing time on a standard personal computer, for instances involving up to 151 trains and two hours of planning time horizon. [ABSTRACT FROM AUTHOR]

This paper reschedules train services on a double-track high speed railway in a disrupted situation, where one track of a segment is temporarily unavailable. We have to decide the sequence of train services passing through the blocked segment, the arrival and departure time of each train service at each station, and the canceled train services. Three practical train rescheduling strategies are explicitly compared and formulated by three MILP models. The uncertain duration of the disruption is handled. A rolling horizon approach is applied to solve our models. The models are tested on a real-world instance of the Beijing-Shanghai high speed railway. [ABSTRACT FROM AUTHOR]

Optimal rail network infrastructure and rolling stock utilization can be achieved with use of different scheduling tools by extensive planning a long time before actual operations. The initial train timetable takes into account possible smaller disturbances, which can be compensated within the schedule. Bigger disruptions, such as accidents, rolling stock breakdown, prolonged passenger boarding, and changed speed limit cause delays that require train rescheduling. In this paper, we introduce a train rescheduling method based on reinforcement learning, and more specifically, Q-learning. We present here the Q-learning principles for train rescheduling, which consist of a learning agent and its actions, environment and its states, as well as rewards. The use of the proposed approach is first illustrated on a simple rescheduling problem comprising a single-lane track with three trains. The evaluation of the approach is performed on extensive set of experiments carried out on a real-world railway network in Slovenia. The empirical results show that Q-learning lead to rescheduling solutions that are at least equivalent and often superior to those of several basic rescheduling methods that do not rely on learning agents. The solutions are learned within reasonable computational time, a crucial factor for real-time applications. [ABSTRACT FROM AUTHOR]

Considering an incident on a track of a double-track subway line, this paper formulates an optimization model to find near-optimal rescheduled timetables with the least total delay time compared to the original one, in which crossover tracks connecting two parallel subway lines are particularly taken into consideration for balancing the service quality under emergent situations. On the basis of a discrete event model where the train position state transitions are characterized as a series of discrete events, an efficient train rescheduling strategy (ETRS) is developed for solving the proposed model, in which a well-developed capacity check algorithm is particularly integrated to prevent the potential deadlocks. By using the infrastructure data of Beijing Yizhuang subway line of China, numerical case studies are implemented to demonstrate the effectiveness and efficiency of the proposed model and algorithm. [ABSTRACT FROM AUTHOR]

This paper focuses on real-time rescheduling of railway traffic on a high speed railway line in case of a complete blockage of the railway infrastructure. Due to the disruption, all tracks in a railway segment are out of order for a certain period of time. In the situation that we consider, trains that are blocked by the disruption do not return to their origin by taking over train services in the opposite direction, but wait inside the stations until the disruption is over. Thus the main decisions to be taken are the following: in which stations do trains have to wait, in which order do they have to leave when the disruption is over, and which trains have to be canceled? A Mixed Integer Programming model is formulated to minimize the total weighted train delay and the number of canceled trains, while adhering to headway and station capacity constraints. Most instances can be solved in a single optimization run, but for the most complex instances we propose a two-stage optimization approach to improve the computational efficiency. The model is tested on real-world instances of the Beijing–Shanghai high speed railway line. The results show that the model is promising for reducing the effect of a disruption on passenger service, especially in comparison with a heuristic method used in practice. [ABSTRACT FROM AUTHOR]

Train rescheduling is an important decision process in railway management. It aims to minimize the negative effects arising from the disturbances via real-time traffic management. Two main challenges are how to formulate the dynamic and complex rescheduling problem as an optimization model, and how to obtain a good solution within a short time limit. Focusing on the stochastic capacity recovery times of blocked tracks, we propose a new track-backup rescheduling (TBR) approach which optimally assigns each affected train a backup track, based on the estimation of recovery time, the original timetable, and track changing cost. Then, we formulate a mixed integer programming (MIP) model to obtain a conflict-free timetable which minimizes the delay cost and the expected track changing cost. A greedy algorithm is designed to reorder trains and reschedule the arrival and departure times, and then we use an MIP algorithm to solve the optimal track backup strategy. Based on the Beijing–Shanghai high-speed railway line, we conduct extensive experimental studies which show that the TBR approach can reduce the rescheduling cost by an average of 10.17% compared with traditional approaches. More important, the greedy-based algorithm is shown to be able to obtain good solutions (with an average error of only 2.85%) within 1.5 s, which implies the high potential of our approach in a real-time traffic management system where fast response is critical. [ABSTRACT FROM AUTHOR]

• A space–time-speed network is used to model train rescheduling in a major disruption. • The trade-off between energy consumption and train-arrival delay is investigated. • We decompose the train rescheduling model by ADMM algorithm. Disruptions are inevitable in daily train operations, and can cause high-speed trains to deviate from their official schedules. Therefore, the efficient rescheduling of disrupted trains is critical for ensuring smooth daily operations. We sought to determine the appropriate arrival and departure times and orders of trains at each station during a disruption, and the speed profile of each train, to reduce the delay costs and energy consumption. To embed the train speed profile corresponding to energy saving into the train rescheduling problem, a space–time–speed network is applied for problem formulation. Thus, the energy-efficient train speed profile is embedded in the speed dimension in the space–time–speed hypernetwork. The detailed train speed profile between two stations is formulated as a multiple-phase optimal control model, which is solved using a pseudospectral method. Then, an integer linear programming model based on multicommodity flow is built to solve the train rescheduling problem. We decompose it via the alternating direction method of multipliers into a series of easy-to-solve shortest path subproblems. Each subproblem is then efficiently solved using a dynamic programming algorithm. Finally, the Xi'an–Chengdu high-speed railway line is used to test our model and algorithms, thereby demonstrating the trade-off between passenger-service quality and energy efficiency. [ABSTRACT FROM AUTHOR]

Severe weather conditions and inherent uncertainties in various components of railway traffic systems can lead to equipment breakdown and reduced capacity on tracks and stations. This paper formulates a two-stage fuzzy optimization model to obtain a robust rescheduling plan under irregular traffic conditions, and a scenario-based representation is adapted to characterize fuzzy recovery time durations on a double-track railway line. The model aims to minimize the expected total delay time in the rescheduled train schedule with respect to the original timetable. Two decomposed sub-models are further developed corresponding to the trains in different directions, and then GAMS optimization software is used to obtain the robust rescheduling plan. The numerical experiments demonstrate the effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

• A method to solve train rescheduling and passenger reassignment simultaneously. • An integrated optimization model is formulated with a bi-objective function. • Our method can facilitate real-time rescheduling and re-ticketing efficiently. • Non-dominated train rescheduling and passenger reassignment solutions are obtained. During railway operations, unexpected events may influence normal traffic flows. This paper focuses on a train rescheduling problem for handling large disruptions, such as a rolling stock breakdown leading to a cancelled train service, where passenger reassignment strategies have to be considered. A novel mixed-integer linear programming formulation is established with consideration of train retiming, reordering, rerouting, and reservicing (addition of extra stops). The proposed mathematical formulation considers planning extra stops for non-canceled trains in order to transport the disrupted passengers, which were supposed to travel on the canceled train, to their pre-planned destination stations. Other constraints deal with limited seat capacity and track capacity, and mapping train rescheduling with passenger reassignment. A bi-objective function is optimized by a weighted-sum method to maximize the number of disrupted passengers reaching their destination stations and to minimize the weighted total train delay for all non-canceled trains at their destinations. A series of numerical experiments based on a part of the Beijing-Shanghai high-speed railway line is carried out to verify the effectiveness and efficiency of the proposed model and to perform a sensitivity analysis of various performance factors. The results show that an optimal reassignment plan of disrupted passengers is important to achieve real-time efficiency of traffic and re-ticketing. The impact of passenger reassignment on train rescheduling is influenced by the weights for objectives, duration of disruption, allowed additional dwell and running times, and relationship between passenger demand and total available train capacity. [ABSTRACT FROM AUTHOR]

In railway traffic systems, whenever disturbances occur, it is important to effectively reschedule trains while optimizing the goals of various stakeholders. Algorithms can provide significant benefits to support the traffic controllers in train rescheduling, if well integrated into the overall traffic management process. In the railway research literature, many algorithms are proposed to tackle different versions of the train rescheduling problem. However, limited research has been performed to assess the capabilities and performance of alternative approaches, with the purpose of identifying their main strengths and weaknesses. Evaluation of train rescheduling algorithms enables practitioners and decision support systems to select a suitable algorithm based on the properties of the type of disturbance scenario in focus. It also guides researchers and algorithm designers in improving the algorithms. In this paper, we (1) propose an evaluation framework for train rescheduling algorithms, (2) present two train rescheduling algorithms: a heuristic and a MILP-based exact algorithm, and (3) conduct an experiment to compare the two multi-objective algorithms using the proposed framework (a proof-of-concept). It is found that the heuristic algorithm is suitable for solving simpler disturbance scenarios since it is quick in producing decent solutions. For complex disturbances wherein multiple trains experience a primary delay due to an infrastructure failure, the exact algorithm is found to be more appropriate. [ABSTRACT FROM AUTHOR]