Unexpected disruptions in urban rail transit systems cause the infeasibility of the initial train schedule and delays or cancelations of a lot of trains. Even though some recent studies begun to address the rolling stock and timetable optimization problem (RSTO), there is still a large gap between theoretical models and practical applications due to the real-time requirements of train rescheduling decisions. In this work, we first model RSTO using a path-based formulation, in which each path refers to a spatial-temporal trajectory of a rescheduled train in the considered network. The optimal set of paths can minimize the expected cost of train cancelation and train delay time. Our formulation also considers a series of operational constraints, such as train headway constraints, short-turning constraints and rolling stock constraints. We develop an efficient branch-and-price framework that decomposes the problem into a restricted master problem and a set of pricing subproblems, where we iteratively generate promising paths with negative reduce costs. We show that each subproblem is a resource-constrained shortest path problem and can be solved efficiently by an improved label setting algorithm by proving its optimality conditions. We compare the tightness of our new path-based formulation with state-of-art formulations and test our branch-and-price approach on real-world instances from Beijing rail transit. The results show that our approach can generate near-optimal solutions in less than three minutes with small duality gap, which evidently outperforms existing formulations and fulfills the requirement of rail managers in practical applications. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72288101 and 72322022]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0391 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0391 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Express pickup and delivery systems play crucial roles in contemporary urban areas. Couriers within these systems retrieve packages from designated Areas of Interest (AOI) that the express company assigns to them during specific time intervals. The express company traditionally employs historical pickup request data for executing AOI assignments (or pickup request assignments) for couriers, and these assignments are conventionally static and do not evolve over time However, future pickup requests display significant temporal variations. Employing historical data for future assignments is, therefore, somewhat impractical. Furthermore, even if we were to predict future pickup requests beforehand and subsequently employ these predictions for assignments, this two-stage approach proves to be both impractical and trivial, potentially harboring drawbacks. For example, the better prediction results may not necessarily guarantee better clustering outcomes. To address these challenges, we introduce an intelligent end-to-end predict-then-optimize clustering method that simultaneously forecasts future pickup requests for AOIs and dynamically allocates AOIs to couriers through clustering. Initially, we propose a deep learning-based prediction model for predicting order quantities within AOIs. Subsequently, we present a differential constrainedK-means clustering method for AOI clustering based on the prediction results. Finally, we introduce a one-stage end-to-end predict-then-optimize clustering approach for the rational, dynamic, and intelligent allocation of AOIs to couriers. Our results demonstrate that this one-stage predict-then-optimize method significantly enhances optimization outcomes, namely the quality of clustering results. This study offers valuable insights that are relevant to predict-then-optimize-related tasks, particularly when addressing stochastic assignment problems within all types of express systems.

Due to the inventible disruptions caused by e.g., flood, hurricane and blizzard, metro managers in recent years have gradually shifted their attention from prevention of disruptions to ability to withstand and quick recovery from these disruptions, hence the need for enhancing the resilience of an urban rail system. In this paper, we propose a resilience-oriented train rescheduling framework, which helps the rail transit system recover to the normal state as soon as possible in case of disruptions, with the help of pre-allocated rolling stocks at the depots, side tracks and timetable rescheduling of grains. Specifically, we first construct an event-activity network for an urban rail line with multiple depots and side tracks, in which the arrival and departure of trains are modeled as a set of events. Several groups of decision variables and linear constraints are denoted to model the rescheduling of trains. Considering the use of short-turning train rescheduling strategy and pre-allocated rolling stocks, we then formulate the problem into a mixed-integer linear programming (MILP) model, where the objective is to maximize the resilience of the urban rail line against disruptions. Through the analysis of model properties, we develop a branch-and-cut algorithm by deriving a series of linear inequalities, which we prove are valid inequalities, to strength the tightness of the MILP model. Finally, numerical experiments based on real-world data of Beijing metro are conducted to verify the effectiveness of our approach.

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 ].

In metro systems, a tactical train schedule with the rolling stock circulation plan aims to determine the movements of all physical trains. To utilize the regenerative energy as much as possible, this paper proposes an integrated model to simultaneously generate the optimal train schedule and rolling stock circulation plan, in which the brake-traction overlapping time at stations is maximized. In particular, our model rigorously considers the train turn-around constraints, train circulation constraints, and dynamic passenger demands to tackle the train loading capacity constraints. To eliminate the effect of non-linear constraints, we reformulate the original model into its equivalent linear model that can be efficiently solved by linear programming solvers. Finally, the numerical experiments based on Beijing Yizhuang Metro Line are implemented to demonstrate the effectiveness of our proposed model.

Energy-efficient train operation is regarded as an effective way to reduce the operational cost and carbon emissions in metro systems. Reduction of the traction energy and increasing of the regenerative energy are two important ways for saving energy, which is closely related to the train timetable and driving strategy. To minimize the systematic net energy consumption, i.e., the difference between the traction energy consumption and the reused regenerative energy, this paper proposes an integrated train operation approach by jointly optimizing the train timetable and driving strategy. A precise train driving strategy is presented and the timetable model considers the headway between successive trains, the distribution of the trip time, and passenger demand in this paper. In addition, a distributed regenerative braking energy model is proposed, based on which the integrated optimization model is formulated. Then, a two-level approach is proposed to solve the problem. At the driving strategy level, the train control problem is transferred into a multi-step decision problem and the Dynamic Programming method is introduced to calculate the energy-efficient driving strategy with the given trip time. As for the timetable level, the trip times and headway of trains are optimized by using the Simulated Annealing algorithm based on the results of dynamic programming method. The timetable optimization level balances the mechanical traction energy of multi-interstations and the amount of the reused regenerative energy such that the net mechanical energy consumption of the metro system is minimized. Furthermore, two numerical examples are conducted for train operations in the peak and off-peak hours separately based on the real-world data of a metro line. The simulation results illustrate that the proposed approach can produce a good performance on energy-saving.

Owing to environmental concerns, the energy-efficient subway train scheduling problem is necessary in subway operation management. This paper designs an approximate dynamic programming (DP) approach for energy-efficient subway train scheduling problem with time-dependent demand. The train traffic model is proposed with the dynamic equations for the evolution of train headway, train passenger loads, and the energy consumption along the subway line. For the dynamic changing of the onboard passengers with time, the total train energy usage is modeled as the sum of energy consumptions from the traction system and auxiliary facilities. A nonlinear DP problem is formulated to generate a near optimal timetable to realize the tradeoff among the utilization of trains, passenger waiting time, service levels, and energy consumption. To overcome the curse of dimensionality in this optimization problem, we construct an approximate DP framework, where the conceptions of states, policies, state transitions, and reward function are introduced. And this algorithm is able to converge to a good solution with a short time compared to the genetic algorithm and differential evolution algorithm. Finally, the numerical experiments are given to demonstrate the effectiveness of the proposed model and algorithm.

In high-speed railways equipped with advanced train control systems, the train-to-train or train-to-ground communication technologies enable the trains to follow their former trains with a constant headway. Due to some disturbances (e.g., weather condition, train re-routing), the train following headway may be inconsistent between successive trains, which requires real-time headway adjustment to coordinate train operations by selecting proper speed curves to improve system performances (e.g., line capacity, energy consumption, power demand, etc) with constrains of safety, punctuality and comfort. This paper proposes a multi-train control model based on cooperative control to adjust train following headway. In particular, this train cooperative control model considers several practical constraints, e.g., train controller output constraints, safe train following distance. Then, this control problem is solved through a rolling horizon approach by calculating the Riccati equation with Lagrangian multipliers. Finally, two case studies are given through simulation experiments. The simulation results are analyzed which demonstrate the effectiveness of the proposed approach.

This paper puts forward a systems approach for the parallel control and management of the high-speed maglev system (HMS). An artificial HMS is first established by using a multiagent-based technique, and we demonstrate its consistence with the actual HMS. We then conduct some computational experiments and summarize some operational rules for the artificial HMS. Finally, the parallel control and management for the HMS are achieved by parallel execution of the artificial and actual HMSs with parallel interactions between them. We evaluate our approach overall by ensuring the safety and reliability of the HMS through parallel control and management. The solutions and recommendations for the safety control and effective management of the HMS can be provided by the proposed approach.

The majority of existing studies in subway train operations focus on timetable optimization and vehicle tracking methods, which may be infeasible with disturbances in actual operations. To deal with uncertain passenger demands and realize real-time train operations (RTOs) satisfying multiobjectives, including overspeed protection, punctuality, riding comfort, and energy consumption, this paper proposes two RTO algorithms via expert knowledge and an online learning approach. The first RTO algorithm is developed by a knowledge-based system to ensure the multiple objectives with a constant timetable. Then, by considering uncertain passenger demand at each station and random running time errors, we convert the train operation problem into a Markov decision process with nondeterministic state transition probabilities in which the aim is to minimize the reward for both the total time delay and energy consumption in a subway line. After designing policy, reward, and transition probability, we develop an integrated train operation (ITO) algorithm based on Q-learning to realize RTOs with online adjusting the timetable. Finally, we present some numerical examples to test the proposed algorithms with real detected data in the Yizhuang Line of Beijing Subway. The results indicate that, taking the multiple objectives into account, the RTO algorithm outperforms both manual driving and automatic train operations. In addition, the ITO algorithm is capable of dealing with uncertain disturbances, keeping the total time delay within 2 s and reducing the energy consumption.

Current research in automatic train operation concentrates on optimizing an energy-efficient speed profile and designing control algorithms to track the speed profile, which may reduce the comfort of passengers and impair the intelligence of train operation. Different from previous studies, this paper presents two intelligent train operation (ITO) algorithms without using precise train model information and offline optimized speed profiles. The first algorithm, i.e., ITOe, is based on an expert system that contains expert rules and a heuristic expert inference method. Then, in order to minimize the energy consumption of train operation online, an ITOr algorithm based on reinforcement learning (RL) is developed via designing an RL policy, reward, and value function. In addition, from the field data in the Yizhuang Line of the Beijing Subway, we choose the manual driving data with the best performance as ITOm. Finally, we present some numerical examples to test the ITO algorithms on the simulation platform established with actual data. The results indicate that, compared with ITOm, both ITOe and ITOr can improve punctuality and reduce energy consumption on the basis of ensuring passenger comfort. Moreover, ITOr can save about 10% energy consumption more than ITOe. In addition, ITOr is capable of adjusting the trip time dynamically, even in the case of accidents.